EarlyCSE.cpp revision a12ba39a1d4d22c8c2d348f1397d52be58391177
1//===- EarlyCSE.cpp - Simple and fast CSE pass ----------------------------===//
2//
3//                     The LLVM Compiler Infrastructure
4//
5// This file is distributed under the University of Illinois Open Source
6// License. See LICENSE.TXT for details.
7//
8//===----------------------------------------------------------------------===//
9//
10// This pass performs a simple dominator tree walk that eliminates trivially
11// redundant instructions.
12//
13//===----------------------------------------------------------------------===//
14
15#define DEBUG_TYPE "early-cse"
16#include "llvm/Transforms/Scalar.h"
17#include "llvm/Instructions.h"
18#include "llvm/Pass.h"
19#include "llvm/Analysis/Dominators.h"
20#include "llvm/Analysis/InstructionSimplify.h"
21#include "llvm/Target/TargetData.h"
22#include "llvm/Transforms/Utils/Local.h"
23#include "llvm/Support/Debug.h"
24#include "llvm/Support/RecyclingAllocator.h"
25#include "llvm/ADT/ScopedHashTable.h"
26#include "llvm/ADT/Statistic.h"
27using namespace llvm;
28
29STATISTIC(NumSimplify, "Number of instructions simplified or DCE'd");
30STATISTIC(NumCSE,      "Number of instructions CSE'd");
31STATISTIC(NumCSELoad,  "Number of load instructions CSE'd");
32STATISTIC(NumCSECall,  "Number of call instructions CSE'd");
33STATISTIC(NumDSE,      "Number of trivial dead stores removed");
34
35static unsigned getHash(const void *V) {
36  return DenseMapInfo<const void*>::getHashValue(V);
37}
38
39//===----------------------------------------------------------------------===//
40// SimpleValue
41//===----------------------------------------------------------------------===//
42
43namespace {
44  /// SimpleValue - Instances of this struct represent available values in the
45  /// scoped hash table.
46  struct SimpleValue {
47    Instruction *Inst;
48
49    SimpleValue(Instruction *I) : Inst(I) {
50      assert((isSentinel() || canHandle(I)) && "Inst can't be handled!");
51    }
52
53    bool isSentinel() const {
54      return Inst == DenseMapInfo<Instruction*>::getEmptyKey() ||
55             Inst == DenseMapInfo<Instruction*>::getTombstoneKey();
56    }
57
58    static bool canHandle(Instruction *Inst) {
59      return isa<CastInst>(Inst) || isa<BinaryOperator>(Inst) ||
60             isa<GetElementPtrInst>(Inst) || isa<CmpInst>(Inst) ||
61             isa<SelectInst>(Inst) || isa<ExtractElementInst>(Inst) ||
62             isa<InsertElementInst>(Inst) || isa<ShuffleVectorInst>(Inst) ||
63             isa<ExtractValueInst>(Inst) || isa<InsertValueInst>(Inst);
64    }
65  };
66}
67
68namespace llvm {
69// SimpleValue is POD.
70template<> struct isPodLike<SimpleValue> {
71  static const bool value = true;
72};
73
74template<> struct DenseMapInfo<SimpleValue> {
75  static inline SimpleValue getEmptyKey() {
76    return DenseMapInfo<Instruction*>::getEmptyKey();
77  }
78  static inline SimpleValue getTombstoneKey() {
79    return DenseMapInfo<Instruction*>::getTombstoneKey();
80  }
81  static unsigned getHashValue(SimpleValue Val);
82  static bool isEqual(SimpleValue LHS, SimpleValue RHS);
83};
84}
85
86unsigned DenseMapInfo<SimpleValue>::getHashValue(SimpleValue Val) {
87  Instruction *Inst = Val.Inst;
88
89  // Hash in all of the operands as pointers.
90  unsigned Res = 0;
91  for (unsigned i = 0, e = Inst->getNumOperands(); i != e; ++i)
92    Res ^= getHash(Inst->getOperand(i)) << i;
93
94  if (CastInst *CI = dyn_cast<CastInst>(Inst))
95    Res ^= getHash(CI->getType());
96  else if (CmpInst *CI = dyn_cast<CmpInst>(Inst))
97    Res ^= CI->getPredicate();
98  else if (const ExtractValueInst *EVI = dyn_cast<ExtractValueInst>(Inst)) {
99    for (ExtractValueInst::idx_iterator I = EVI->idx_begin(),
100         E = EVI->idx_end(); I != E; ++I)
101      Res ^= *I;
102  } else if (const InsertValueInst *IVI = dyn_cast<InsertValueInst>(Inst)) {
103    for (InsertValueInst::idx_iterator I = IVI->idx_begin(),
104         E = IVI->idx_end(); I != E; ++I)
105      Res ^= *I;
106  } else {
107    // nothing extra to hash in.
108    assert((isa<BinaryOperator>(Inst) || isa<GetElementPtrInst>(Inst) ||
109            isa<SelectInst>(Inst) || isa<ExtractElementInst>(Inst) ||
110            isa<InsertElementInst>(Inst) || isa<ShuffleVectorInst>(Inst)) &&
111           "Invalid/unknown instruction");
112  }
113
114  // Mix in the opcode.
115  return (Res << 1) ^ Inst->getOpcode();
116}
117
118bool DenseMapInfo<SimpleValue>::isEqual(SimpleValue LHS, SimpleValue RHS) {
119  Instruction *LHSI = LHS.Inst, *RHSI = RHS.Inst;
120
121  if (LHS.isSentinel() || RHS.isSentinel())
122    return LHSI == RHSI;
123
124  if (LHSI->getOpcode() != RHSI->getOpcode()) return false;
125  return LHSI->isIdenticalTo(RHSI);
126}
127
128//===----------------------------------------------------------------------===//
129// CallValue
130//===----------------------------------------------------------------------===//
131
132namespace {
133  /// CallValue - Instances of this struct represent available call values in
134  /// the scoped hash table.
135  struct CallValue {
136    Instruction *Inst;
137
138    CallValue(Instruction *I) : Inst(I) {
139      assert((isSentinel() || canHandle(I)) && "Inst can't be handled!");
140    }
141
142    bool isSentinel() const {
143      return Inst == DenseMapInfo<Instruction*>::getEmptyKey() ||
144             Inst == DenseMapInfo<Instruction*>::getTombstoneKey();
145    }
146
147    static bool canHandle(Instruction *Inst) {
148      CallInst *CI = dyn_cast<CallInst>(Inst);
149      if (CI == 0 || !CI->onlyReadsMemory())
150        return false;
151
152      // Check that there are no metadata operands.
153      for (unsigned i = 0, e = CI->getNumOperands(); i != e; ++i)
154        if (CI->getOperand(i)->getType()->isMetadataTy())
155          return false;
156      return true;
157    }
158  };
159}
160
161namespace llvm {
162  // CallValue is POD.
163  template<> struct isPodLike<CallValue> {
164    static const bool value = true;
165  };
166
167  template<> struct DenseMapInfo<CallValue> {
168    static inline CallValue getEmptyKey() {
169      return DenseMapInfo<Instruction*>::getEmptyKey();
170    }
171    static inline CallValue getTombstoneKey() {
172      return DenseMapInfo<Instruction*>::getTombstoneKey();
173    }
174    static unsigned getHashValue(CallValue Val);
175    static bool isEqual(CallValue LHS, CallValue RHS);
176  };
177}
178unsigned DenseMapInfo<CallValue>::getHashValue(CallValue Val) {
179  Instruction *Inst = Val.Inst;
180  // Hash in all of the operands as pointers.
181  unsigned Res = 0;
182  for (unsigned i = 0, e = Inst->getNumOperands(); i != e; ++i)
183    Res ^= getHash(Inst->getOperand(i)) << i;
184  // Mix in the opcode.
185  return (Res << 1) ^ Inst->getOpcode();
186}
187
188bool DenseMapInfo<CallValue>::isEqual(CallValue LHS, CallValue RHS) {
189  Instruction *LHSI = LHS.Inst, *RHSI = RHS.Inst;
190  if (LHS.isSentinel() || RHS.isSentinel())
191    return LHSI == RHSI;
192  return LHSI->isIdenticalTo(RHSI);
193}
194
195
196//===----------------------------------------------------------------------===//
197// EarlyCSE pass.
198//===----------------------------------------------------------------------===//
199
200namespace {
201
202/// EarlyCSE - This pass does a simple depth-first walk over the dominator
203/// tree, eliminating trivially redundant instructions and using instsimplify
204/// to canonicalize things as it goes.  It is intended to be fast and catch
205/// obvious cases so that instcombine and other passes are more effective.  It
206/// is expected that a later pass of GVN will catch the interesting/hard
207/// cases.
208class EarlyCSE : public FunctionPass {
209public:
210  const TargetData *TD;
211  DominatorTree *DT;
212  typedef RecyclingAllocator<BumpPtrAllocator,
213                      ScopedHashTableVal<SimpleValue, Value*> > AllocatorTy;
214  typedef ScopedHashTable<SimpleValue, Value*, DenseMapInfo<SimpleValue>,
215                          AllocatorTy> ScopedHTType;
216
217  /// AvailableValues - This scoped hash table contains the current values of
218  /// all of our simple scalar expressions.  As we walk down the domtree, we
219  /// look to see if instructions are in this: if so, we replace them with what
220  /// we find, otherwise we insert them so that dominated values can succeed in
221  /// their lookup.
222  ScopedHTType *AvailableValues;
223
224  /// AvailableLoads - This scoped hash table contains the current values
225  /// of loads.  This allows us to get efficient access to dominating loads when
226  /// we have a fully redundant load.  In addition to the most recent load, we
227  /// keep track of a generation count of the read, which is compared against
228  /// the current generation count.  The current generation count is
229  /// incremented after every possibly writing memory operation, which ensures
230  /// that we only CSE loads with other loads that have no intervening store.
231  typedef RecyclingAllocator<BumpPtrAllocator,
232    ScopedHashTableVal<Value*, std::pair<Value*, unsigned> > > LoadMapAllocator;
233  typedef ScopedHashTable<Value*, std::pair<Value*, unsigned>,
234                          DenseMapInfo<Value*>, LoadMapAllocator> LoadHTType;
235  LoadHTType *AvailableLoads;
236
237  /// AvailableCalls - This scoped hash table contains the current values
238  /// of read-only call values.  It uses the same generation count as loads.
239  typedef ScopedHashTable<CallValue, std::pair<Value*, unsigned> > CallHTType;
240  CallHTType *AvailableCalls;
241
242  /// CurrentGeneration - This is the current generation of the memory value.
243  unsigned CurrentGeneration;
244
245  static char ID;
246  explicit EarlyCSE() : FunctionPass(ID) {
247    initializeEarlyCSEPass(*PassRegistry::getPassRegistry());
248  }
249
250  bool runOnFunction(Function &F);
251
252private:
253
254  bool processNode(DomTreeNode *Node);
255
256  // This transformation requires dominator postdominator info
257  virtual void getAnalysisUsage(AnalysisUsage &AU) const {
258    AU.addRequired<DominatorTree>();
259    AU.setPreservesCFG();
260  }
261};
262}
263
264char EarlyCSE::ID = 0;
265
266// createEarlyCSEPass - The public interface to this file.
267FunctionPass *llvm::createEarlyCSEPass() {
268  return new EarlyCSE();
269}
270
271INITIALIZE_PASS_BEGIN(EarlyCSE, "early-cse", "Early CSE", false, false)
272INITIALIZE_PASS_DEPENDENCY(DominatorTree)
273INITIALIZE_PASS_END(EarlyCSE, "early-cse", "Early CSE", false, false)
274
275bool EarlyCSE::processNode(DomTreeNode *Node) {
276  // Define a scope in the scoped hash table.  When we are done processing this
277  // domtree node and recurse back up to our parent domtree node, this will pop
278  // off all the values we install.
279  ScopedHTType::ScopeTy Scope(*AvailableValues);
280
281  // Define a scope for the load values so that anything we add will get
282  // popped when we recurse back up to our parent domtree node.
283  LoadHTType::ScopeTy LoadScope(*AvailableLoads);
284
285  // Define a scope for the call values so that anything we add will get
286  // popped when we recurse back up to our parent domtree node.
287  CallHTType::ScopeTy CallScope(*AvailableCalls);
288
289  BasicBlock *BB = Node->getBlock();
290
291  // If this block has a single predecessor, then the predecessor is the parent
292  // of the domtree node and all of the live out memory values are still current
293  // in this block.  If this block has multiple predecessors, then they could
294  // have invalidated the live-out memory values of our parent value.  For now,
295  // just be conservative and invalidate memory if this block has multiple
296  // predecessors.
297  if (BB->getSinglePredecessor() == 0)
298    ++CurrentGeneration;
299
300  /// LastStore - Keep track of the last non-volatile store that we saw... for
301  /// as long as there in no instruction that reads memory.  If we see a store
302  /// to the same location, we delete the dead store.  This zaps trivial dead
303  /// stores which can occur in bitfield code among other things.
304  StoreInst *LastStore = 0;
305
306  bool Changed = false;
307
308  // See if any instructions in the block can be eliminated.  If so, do it.  If
309  // not, add them to AvailableValues.
310  for (BasicBlock::iterator I = BB->begin(), E = BB->end(); I != E; ) {
311    Instruction *Inst = I++;
312
313    // Dead instructions should just be removed.
314    if (isInstructionTriviallyDead(Inst)) {
315      DEBUG(dbgs() << "EarlyCSE DCE: " << *Inst << '\n');
316      Inst->eraseFromParent();
317      Changed = true;
318      ++NumSimplify;
319      continue;
320    }
321
322    // If the instruction can be simplified (e.g. X+0 = X) then replace it with
323    // its simpler value.
324    if (Value *V = SimplifyInstruction(Inst, TD, DT)) {
325      DEBUG(dbgs() << "EarlyCSE Simplify: " << *Inst << "  to: " << *V << '\n');
326      Inst->replaceAllUsesWith(V);
327      Inst->eraseFromParent();
328      Changed = true;
329      ++NumSimplify;
330      continue;
331    }
332
333    // If this is a simple instruction that we can value number, process it.
334    if (SimpleValue::canHandle(Inst)) {
335      // See if the instruction has an available value.  If so, use it.
336      if (Value *V = AvailableValues->lookup(Inst)) {
337        DEBUG(dbgs() << "EarlyCSE CSE: " << *Inst << "  to: " << *V << '\n');
338        Inst->replaceAllUsesWith(V);
339        Inst->eraseFromParent();
340        Changed = true;
341        ++NumCSE;
342        continue;
343      }
344
345      // Otherwise, just remember that this value is available.
346      AvailableValues->insert(Inst, Inst);
347      continue;
348    }
349
350    // If this is a non-volatile load, process it.
351    if (LoadInst *LI = dyn_cast<LoadInst>(Inst)) {
352      // Ignore volatile loads.
353      if (LI->isVolatile()) {
354        LastStore = 0;
355        continue;
356      }
357
358      // If we have an available version of this load, and if it is the right
359      // generation, replace this instruction.
360      std::pair<Value*, unsigned> InVal =
361        AvailableLoads->lookup(Inst->getOperand(0));
362      if (InVal.first != 0 && InVal.second == CurrentGeneration) {
363        DEBUG(dbgs() << "EarlyCSE CSE LOAD: " << *Inst << "  to: "
364              << *InVal.first << '\n');
365        if (!Inst->use_empty()) Inst->replaceAllUsesWith(InVal.first);
366        Inst->eraseFromParent();
367        Changed = true;
368        ++NumCSELoad;
369        continue;
370      }
371
372      // Otherwise, remember that we have this instruction.
373      AvailableLoads->insert(Inst->getOperand(0),
374                          std::pair<Value*, unsigned>(Inst, CurrentGeneration));
375      LastStore = 0;
376      continue;
377    }
378
379    // If this instruction may read from memory, forget LastStore.
380    if (Inst->mayReadFromMemory())
381      LastStore = 0;
382
383    // If this is a read-only call, process it.
384    if (CallValue::canHandle(Inst)) {
385      // If we have an available version of this call, and if it is the right
386      // generation, replace this instruction.
387      std::pair<Value*, unsigned> InVal = AvailableCalls->lookup(Inst);
388      if (InVal.first != 0 && InVal.second == CurrentGeneration) {
389        DEBUG(dbgs() << "EarlyCSE CSE CALL: " << *Inst << "  to: "
390                     << *InVal.first << '\n');
391        if (!Inst->use_empty()) Inst->replaceAllUsesWith(InVal.first);
392        Inst->eraseFromParent();
393        Changed = true;
394        ++NumCSECall;
395        continue;
396      }
397
398      // Otherwise, remember that we have this instruction.
399      AvailableCalls->insert(Inst,
400                         std::pair<Value*, unsigned>(Inst, CurrentGeneration));
401      continue;
402    }
403
404    // Okay, this isn't something we can CSE at all.  Check to see if it is
405    // something that could modify memory.  If so, our available memory values
406    // cannot be used so bump the generation count.
407    if (Inst->mayWriteToMemory()) {
408      ++CurrentGeneration;
409
410      if (StoreInst *SI = dyn_cast<StoreInst>(Inst)) {
411        // We do a trivial form of DSE if there are two stores to the same
412        // location with no intervening loads.  Delete the earlier store.
413        if (LastStore &&
414            LastStore->getPointerOperand() == SI->getPointerOperand()) {
415          DEBUG(dbgs() << "EarlyCSE DEAD STORE: " << *LastStore << "  due to: "
416                       << *Inst << '\n');
417          LastStore->eraseFromParent();
418          Changed = true;
419          ++NumDSE;
420          LastStore = 0;
421          continue;
422        }
423
424        // Okay, we just invalidated anything we knew about loaded values.  Try
425        // to salvage *something* by remembering that the stored value is a live
426        // version of the pointer.  It is safe to forward from volatile stores
427        // to non-volatile loads, so we don't have to check for volatility of
428        // the store.
429        AvailableLoads->insert(SI->getPointerOperand(),
430         std::pair<Value*, unsigned>(SI->getValueOperand(), CurrentGeneration));
431
432        // Remember that this was the last store we saw for DSE.
433        if (!SI->isVolatile())
434          LastStore = SI;
435      }
436    }
437  }
438
439  unsigned LiveOutGeneration = CurrentGeneration;
440  for (DomTreeNode::iterator I = Node->begin(), E = Node->end(); I != E; ++I) {
441    Changed |= processNode(*I);
442    // Pop any generation changes off the stack from the recursive walk.
443    CurrentGeneration = LiveOutGeneration;
444  }
445  return Changed;
446}
447
448
449bool EarlyCSE::runOnFunction(Function &F) {
450  TD = getAnalysisIfAvailable<TargetData>();
451  DT = &getAnalysis<DominatorTree>();
452
453  // Tables that the pass uses when walking the domtree.
454  ScopedHTType AVTable;
455  AvailableValues = &AVTable;
456  LoadHTType LoadTable;
457  AvailableLoads = &LoadTable;
458  CallHTType CallTable;
459  AvailableCalls = &CallTable;
460
461  CurrentGeneration = 0;
462  return processNode(DT->getRootNode());
463}
464