• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
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 #include "llvm/Transforms/Scalar/EarlyCSE.h"
16 #include "llvm/ADT/Hashing.h"
17 #include "llvm/ADT/ScopedHashTable.h"
18 #include "llvm/ADT/Statistic.h"
19 #include "llvm/Analysis/AssumptionCache.h"
20 #include "llvm/Analysis/GlobalsModRef.h"
21 #include "llvm/Analysis/InstructionSimplify.h"
22 #include "llvm/Analysis/TargetLibraryInfo.h"
23 #include "llvm/Analysis/TargetTransformInfo.h"
24 #include "llvm/IR/DataLayout.h"
25 #include "llvm/IR/Dominators.h"
26 #include "llvm/IR/Instructions.h"
27 #include "llvm/IR/IntrinsicInst.h"
28 #include "llvm/IR/PatternMatch.h"
29 #include "llvm/Pass.h"
30 #include "llvm/Support/Debug.h"
31 #include "llvm/Support/RecyclingAllocator.h"
32 #include "llvm/Support/raw_ostream.h"
33 #include "llvm/Transforms/Scalar.h"
34 #include "llvm/Transforms/Utils/Local.h"
35 #include <deque>
36 using namespace llvm;
37 using namespace llvm::PatternMatch;
38 
39 #define DEBUG_TYPE "early-cse"
40 
41 STATISTIC(NumSimplify, "Number of instructions simplified or DCE'd");
42 STATISTIC(NumCSE,      "Number of instructions CSE'd");
43 STATISTIC(NumCSECVP,   "Number of compare instructions CVP'd");
44 STATISTIC(NumCSELoad,  "Number of load instructions CSE'd");
45 STATISTIC(NumCSECall,  "Number of call instructions CSE'd");
46 STATISTIC(NumDSE,      "Number of trivial dead stores removed");
47 
48 //===----------------------------------------------------------------------===//
49 // SimpleValue
50 //===----------------------------------------------------------------------===//
51 
52 namespace {
53 /// \brief Struct representing the available values in the scoped hash table.
54 struct SimpleValue {
55   Instruction *Inst;
56 
SimpleValue__anon5dbebb2a0111::SimpleValue57   SimpleValue(Instruction *I) : Inst(I) {
58     assert((isSentinel() || canHandle(I)) && "Inst can't be handled!");
59   }
60 
isSentinel__anon5dbebb2a0111::SimpleValue61   bool isSentinel() const {
62     return Inst == DenseMapInfo<Instruction *>::getEmptyKey() ||
63            Inst == DenseMapInfo<Instruction *>::getTombstoneKey();
64   }
65 
canHandle__anon5dbebb2a0111::SimpleValue66   static bool canHandle(Instruction *Inst) {
67     // This can only handle non-void readnone functions.
68     if (CallInst *CI = dyn_cast<CallInst>(Inst))
69       return CI->doesNotAccessMemory() && !CI->getType()->isVoidTy();
70     return isa<CastInst>(Inst) || isa<BinaryOperator>(Inst) ||
71            isa<GetElementPtrInst>(Inst) || isa<CmpInst>(Inst) ||
72            isa<SelectInst>(Inst) || isa<ExtractElementInst>(Inst) ||
73            isa<InsertElementInst>(Inst) || isa<ShuffleVectorInst>(Inst) ||
74            isa<ExtractValueInst>(Inst) || isa<InsertValueInst>(Inst);
75   }
76 };
77 }
78 
79 namespace llvm {
80 template <> struct DenseMapInfo<SimpleValue> {
getEmptyKeyllvm::DenseMapInfo81   static inline SimpleValue getEmptyKey() {
82     return DenseMapInfo<Instruction *>::getEmptyKey();
83   }
getTombstoneKeyllvm::DenseMapInfo84   static inline SimpleValue getTombstoneKey() {
85     return DenseMapInfo<Instruction *>::getTombstoneKey();
86   }
87   static unsigned getHashValue(SimpleValue Val);
88   static bool isEqual(SimpleValue LHS, SimpleValue RHS);
89 };
90 }
91 
getHashValue(SimpleValue Val)92 unsigned DenseMapInfo<SimpleValue>::getHashValue(SimpleValue Val) {
93   Instruction *Inst = Val.Inst;
94   // Hash in all of the operands as pointers.
95   if (BinaryOperator *BinOp = dyn_cast<BinaryOperator>(Inst)) {
96     Value *LHS = BinOp->getOperand(0);
97     Value *RHS = BinOp->getOperand(1);
98     if (BinOp->isCommutative() && BinOp->getOperand(0) > BinOp->getOperand(1))
99       std::swap(LHS, RHS);
100 
101     return hash_combine(BinOp->getOpcode(), LHS, RHS);
102   }
103 
104   if (CmpInst *CI = dyn_cast<CmpInst>(Inst)) {
105     Value *LHS = CI->getOperand(0);
106     Value *RHS = CI->getOperand(1);
107     CmpInst::Predicate Pred = CI->getPredicate();
108     if (Inst->getOperand(0) > Inst->getOperand(1)) {
109       std::swap(LHS, RHS);
110       Pred = CI->getSwappedPredicate();
111     }
112     return hash_combine(Inst->getOpcode(), Pred, LHS, RHS);
113   }
114 
115   if (CastInst *CI = dyn_cast<CastInst>(Inst))
116     return hash_combine(CI->getOpcode(), CI->getType(), CI->getOperand(0));
117 
118   if (const ExtractValueInst *EVI = dyn_cast<ExtractValueInst>(Inst))
119     return hash_combine(EVI->getOpcode(), EVI->getOperand(0),
120                         hash_combine_range(EVI->idx_begin(), EVI->idx_end()));
121 
122   if (const InsertValueInst *IVI = dyn_cast<InsertValueInst>(Inst))
123     return hash_combine(IVI->getOpcode(), IVI->getOperand(0),
124                         IVI->getOperand(1),
125                         hash_combine_range(IVI->idx_begin(), IVI->idx_end()));
126 
127   assert((isa<CallInst>(Inst) || isa<BinaryOperator>(Inst) ||
128           isa<GetElementPtrInst>(Inst) || isa<SelectInst>(Inst) ||
129           isa<ExtractElementInst>(Inst) || isa<InsertElementInst>(Inst) ||
130           isa<ShuffleVectorInst>(Inst)) &&
131          "Invalid/unknown instruction");
132 
133   // Mix in the opcode.
134   return hash_combine(
135       Inst->getOpcode(),
136       hash_combine_range(Inst->value_op_begin(), Inst->value_op_end()));
137 }
138 
isEqual(SimpleValue LHS,SimpleValue RHS)139 bool DenseMapInfo<SimpleValue>::isEqual(SimpleValue LHS, SimpleValue RHS) {
140   Instruction *LHSI = LHS.Inst, *RHSI = RHS.Inst;
141 
142   if (LHS.isSentinel() || RHS.isSentinel())
143     return LHSI == RHSI;
144 
145   if (LHSI->getOpcode() != RHSI->getOpcode())
146     return false;
147   if (LHSI->isIdenticalToWhenDefined(RHSI))
148     return true;
149 
150   // If we're not strictly identical, we still might be a commutable instruction
151   if (BinaryOperator *LHSBinOp = dyn_cast<BinaryOperator>(LHSI)) {
152     if (!LHSBinOp->isCommutative())
153       return false;
154 
155     assert(isa<BinaryOperator>(RHSI) &&
156            "same opcode, but different instruction type?");
157     BinaryOperator *RHSBinOp = cast<BinaryOperator>(RHSI);
158 
159     // Commuted equality
160     return LHSBinOp->getOperand(0) == RHSBinOp->getOperand(1) &&
161            LHSBinOp->getOperand(1) == RHSBinOp->getOperand(0);
162   }
163   if (CmpInst *LHSCmp = dyn_cast<CmpInst>(LHSI)) {
164     assert(isa<CmpInst>(RHSI) &&
165            "same opcode, but different instruction type?");
166     CmpInst *RHSCmp = cast<CmpInst>(RHSI);
167     // Commuted equality
168     return LHSCmp->getOperand(0) == RHSCmp->getOperand(1) &&
169            LHSCmp->getOperand(1) == RHSCmp->getOperand(0) &&
170            LHSCmp->getSwappedPredicate() == RHSCmp->getPredicate();
171   }
172 
173   return false;
174 }
175 
176 //===----------------------------------------------------------------------===//
177 // CallValue
178 //===----------------------------------------------------------------------===//
179 
180 namespace {
181 /// \brief Struct representing the available call values in the scoped hash
182 /// table.
183 struct CallValue {
184   Instruction *Inst;
185 
CallValue__anon5dbebb2a0211::CallValue186   CallValue(Instruction *I) : Inst(I) {
187     assert((isSentinel() || canHandle(I)) && "Inst can't be handled!");
188   }
189 
isSentinel__anon5dbebb2a0211::CallValue190   bool isSentinel() const {
191     return Inst == DenseMapInfo<Instruction *>::getEmptyKey() ||
192            Inst == DenseMapInfo<Instruction *>::getTombstoneKey();
193   }
194 
canHandle__anon5dbebb2a0211::CallValue195   static bool canHandle(Instruction *Inst) {
196     // Don't value number anything that returns void.
197     if (Inst->getType()->isVoidTy())
198       return false;
199 
200     CallInst *CI = dyn_cast<CallInst>(Inst);
201     if (!CI || !CI->onlyReadsMemory())
202       return false;
203     return true;
204   }
205 };
206 }
207 
208 namespace llvm {
209 template <> struct DenseMapInfo<CallValue> {
getEmptyKeyllvm::DenseMapInfo210   static inline CallValue getEmptyKey() {
211     return DenseMapInfo<Instruction *>::getEmptyKey();
212   }
getTombstoneKeyllvm::DenseMapInfo213   static inline CallValue getTombstoneKey() {
214     return DenseMapInfo<Instruction *>::getTombstoneKey();
215   }
216   static unsigned getHashValue(CallValue Val);
217   static bool isEqual(CallValue LHS, CallValue RHS);
218 };
219 }
220 
getHashValue(CallValue Val)221 unsigned DenseMapInfo<CallValue>::getHashValue(CallValue Val) {
222   Instruction *Inst = Val.Inst;
223   // Hash all of the operands as pointers and mix in the opcode.
224   return hash_combine(
225       Inst->getOpcode(),
226       hash_combine_range(Inst->value_op_begin(), Inst->value_op_end()));
227 }
228 
isEqual(CallValue LHS,CallValue RHS)229 bool DenseMapInfo<CallValue>::isEqual(CallValue LHS, CallValue RHS) {
230   Instruction *LHSI = LHS.Inst, *RHSI = RHS.Inst;
231   if (LHS.isSentinel() || RHS.isSentinel())
232     return LHSI == RHSI;
233   return LHSI->isIdenticalTo(RHSI);
234 }
235 
236 //===----------------------------------------------------------------------===//
237 // EarlyCSE implementation
238 //===----------------------------------------------------------------------===//
239 
240 namespace {
241 /// \brief A simple and fast domtree-based CSE pass.
242 ///
243 /// This pass does a simple depth-first walk over the dominator tree,
244 /// eliminating trivially redundant instructions and using instsimplify to
245 /// canonicalize things as it goes. It is intended to be fast and catch obvious
246 /// cases so that instcombine and other passes are more effective. It is
247 /// expected that a later pass of GVN will catch the interesting/hard cases.
248 class EarlyCSE {
249 public:
250   const TargetLibraryInfo &TLI;
251   const TargetTransformInfo &TTI;
252   DominatorTree &DT;
253   AssumptionCache &AC;
254   typedef RecyclingAllocator<
255       BumpPtrAllocator, ScopedHashTableVal<SimpleValue, Value *>> AllocatorTy;
256   typedef ScopedHashTable<SimpleValue, Value *, DenseMapInfo<SimpleValue>,
257                           AllocatorTy> ScopedHTType;
258 
259   /// \brief A scoped hash table of the current values of all of our simple
260   /// scalar expressions.
261   ///
262   /// As we walk down the domtree, we look to see if instructions are in this:
263   /// if so, we replace them with what we find, otherwise we insert them so
264   /// that dominated values can succeed in their lookup.
265   ScopedHTType AvailableValues;
266 
267   /// A scoped hash table of the current values of previously encounted memory
268   /// locations.
269   ///
270   /// This allows us to get efficient access to dominating loads or stores when
271   /// we have a fully redundant load.  In addition to the most recent load, we
272   /// keep track of a generation count of the read, which is compared against
273   /// the current generation count.  The current generation count is incremented
274   /// after every possibly writing memory operation, which ensures that we only
275   /// CSE loads with other loads that have no intervening store.  Ordering
276   /// events (such as fences or atomic instructions) increment the generation
277   /// count as well; essentially, we model these as writes to all possible
278   /// locations.  Note that atomic and/or volatile loads and stores can be
279   /// present the table; it is the responsibility of the consumer to inspect
280   /// the atomicity/volatility if needed.
281   struct LoadValue {
282     Instruction *DefInst;
283     unsigned Generation;
284     int MatchingId;
285     bool IsAtomic;
286     bool IsInvariant;
LoadValue__anon5dbebb2a0311::EarlyCSE::LoadValue287     LoadValue()
288         : DefInst(nullptr), Generation(0), MatchingId(-1), IsAtomic(false),
289           IsInvariant(false) {}
LoadValue__anon5dbebb2a0311::EarlyCSE::LoadValue290     LoadValue(Instruction *Inst, unsigned Generation, unsigned MatchingId,
291               bool IsAtomic, bool IsInvariant)
292         : DefInst(Inst), Generation(Generation), MatchingId(MatchingId),
293           IsAtomic(IsAtomic), IsInvariant(IsInvariant) {}
294   };
295   typedef RecyclingAllocator<BumpPtrAllocator,
296                              ScopedHashTableVal<Value *, LoadValue>>
297       LoadMapAllocator;
298   typedef ScopedHashTable<Value *, LoadValue, DenseMapInfo<Value *>,
299                           LoadMapAllocator> LoadHTType;
300   LoadHTType AvailableLoads;
301 
302   /// \brief A scoped hash table of the current values of read-only call
303   /// values.
304   ///
305   /// It uses the same generation count as loads.
306   typedef ScopedHashTable<CallValue, std::pair<Instruction *, unsigned>>
307       CallHTType;
308   CallHTType AvailableCalls;
309 
310   /// \brief This is the current generation of the memory value.
311   unsigned CurrentGeneration;
312 
313   /// \brief Set up the EarlyCSE runner for a particular function.
EarlyCSE(const TargetLibraryInfo & TLI,const TargetTransformInfo & TTI,DominatorTree & DT,AssumptionCache & AC)314   EarlyCSE(const TargetLibraryInfo &TLI, const TargetTransformInfo &TTI,
315            DominatorTree &DT, AssumptionCache &AC)
316       : TLI(TLI), TTI(TTI), DT(DT), AC(AC), CurrentGeneration(0) {}
317 
318   bool run();
319 
320 private:
321   // Almost a POD, but needs to call the constructors for the scoped hash
322   // tables so that a new scope gets pushed on. These are RAII so that the
323   // scope gets popped when the NodeScope is destroyed.
324   class NodeScope {
325   public:
NodeScope(ScopedHTType & AvailableValues,LoadHTType & AvailableLoads,CallHTType & AvailableCalls)326     NodeScope(ScopedHTType &AvailableValues, LoadHTType &AvailableLoads,
327               CallHTType &AvailableCalls)
328         : Scope(AvailableValues), LoadScope(AvailableLoads),
329           CallScope(AvailableCalls) {}
330 
331   private:
332     NodeScope(const NodeScope &) = delete;
333     void operator=(const NodeScope &) = delete;
334 
335     ScopedHTType::ScopeTy Scope;
336     LoadHTType::ScopeTy LoadScope;
337     CallHTType::ScopeTy CallScope;
338   };
339 
340   // Contains all the needed information to create a stack for doing a depth
341   // first tranversal of the tree. This includes scopes for values, loads, and
342   // calls as well as the generation. There is a child iterator so that the
343   // children do not need to be store separately.
344   class StackNode {
345   public:
StackNode(ScopedHTType & AvailableValues,LoadHTType & AvailableLoads,CallHTType & AvailableCalls,unsigned cg,DomTreeNode * n,DomTreeNode::iterator child,DomTreeNode::iterator end)346     StackNode(ScopedHTType &AvailableValues, LoadHTType &AvailableLoads,
347               CallHTType &AvailableCalls, unsigned cg, DomTreeNode *n,
348               DomTreeNode::iterator child, DomTreeNode::iterator end)
349         : CurrentGeneration(cg), ChildGeneration(cg), Node(n), ChildIter(child),
350           EndIter(end), Scopes(AvailableValues, AvailableLoads, AvailableCalls),
351           Processed(false) {}
352 
353     // Accessors.
currentGeneration()354     unsigned currentGeneration() { return CurrentGeneration; }
childGeneration()355     unsigned childGeneration() { return ChildGeneration; }
childGeneration(unsigned generation)356     void childGeneration(unsigned generation) { ChildGeneration = generation; }
node()357     DomTreeNode *node() { return Node; }
childIter()358     DomTreeNode::iterator childIter() { return ChildIter; }
nextChild()359     DomTreeNode *nextChild() {
360       DomTreeNode *child = *ChildIter;
361       ++ChildIter;
362       return child;
363     }
end()364     DomTreeNode::iterator end() { return EndIter; }
isProcessed()365     bool isProcessed() { return Processed; }
process()366     void process() { Processed = true; }
367 
368   private:
369     StackNode(const StackNode &) = delete;
370     void operator=(const StackNode &) = delete;
371 
372     // Members.
373     unsigned CurrentGeneration;
374     unsigned ChildGeneration;
375     DomTreeNode *Node;
376     DomTreeNode::iterator ChildIter;
377     DomTreeNode::iterator EndIter;
378     NodeScope Scopes;
379     bool Processed;
380   };
381 
382   /// \brief Wrapper class to handle memory instructions, including loads,
383   /// stores and intrinsic loads and stores defined by the target.
384   class ParseMemoryInst {
385   public:
ParseMemoryInst(Instruction * Inst,const TargetTransformInfo & TTI)386     ParseMemoryInst(Instruction *Inst, const TargetTransformInfo &TTI)
387       : IsTargetMemInst(false), Inst(Inst) {
388       if (IntrinsicInst *II = dyn_cast<IntrinsicInst>(Inst))
389         if (TTI.getTgtMemIntrinsic(II, Info) && Info.NumMemRefs == 1)
390           IsTargetMemInst = true;
391     }
isLoad() const392     bool isLoad() const {
393       if (IsTargetMemInst) return Info.ReadMem;
394       return isa<LoadInst>(Inst);
395     }
isStore() const396     bool isStore() const {
397       if (IsTargetMemInst) return Info.WriteMem;
398       return isa<StoreInst>(Inst);
399     }
isAtomic() const400     bool isAtomic() const {
401       if (IsTargetMemInst) {
402         assert(Info.IsSimple && "need to refine IsSimple in TTI");
403         return false;
404       }
405       return Inst->isAtomic();
406     }
isUnordered() const407     bool isUnordered() const {
408       if (IsTargetMemInst) {
409         assert(Info.IsSimple && "need to refine IsSimple in TTI");
410         return true;
411       }
412       if (LoadInst *LI = dyn_cast<LoadInst>(Inst)) {
413         return LI->isUnordered();
414       } else if (StoreInst *SI = dyn_cast<StoreInst>(Inst)) {
415         return SI->isUnordered();
416       }
417       // Conservative answer
418       return !Inst->isAtomic();
419     }
420 
isVolatile() const421     bool isVolatile() const {
422       if (IsTargetMemInst) {
423         assert(Info.IsSimple && "need to refine IsSimple in TTI");
424         return false;
425       }
426       if (LoadInst *LI = dyn_cast<LoadInst>(Inst)) {
427         return LI->isVolatile();
428       } else if (StoreInst *SI = dyn_cast<StoreInst>(Inst)) {
429         return SI->isVolatile();
430       }
431       // Conservative answer
432       return true;
433     }
434 
isInvariantLoad() const435     bool isInvariantLoad() const {
436       if (auto *LI = dyn_cast<LoadInst>(Inst))
437         return LI->getMetadata(LLVMContext::MD_invariant_load) != nullptr;
438       return false;
439     }
440 
isMatchingMemLoc(const ParseMemoryInst & Inst) const441     bool isMatchingMemLoc(const ParseMemoryInst &Inst) const {
442       return (getPointerOperand() == Inst.getPointerOperand() &&
443               getMatchingId() == Inst.getMatchingId());
444     }
isValid() const445     bool isValid() const { return getPointerOperand() != nullptr; }
446 
447     // For regular (non-intrinsic) loads/stores, this is set to -1. For
448     // intrinsic loads/stores, the id is retrieved from the corresponding
449     // field in the MemIntrinsicInfo structure.  That field contains
450     // non-negative values only.
getMatchingId() const451     int getMatchingId() const {
452       if (IsTargetMemInst) return Info.MatchingId;
453       return -1;
454     }
getPointerOperand() const455     Value *getPointerOperand() const {
456       if (IsTargetMemInst) return Info.PtrVal;
457       if (LoadInst *LI = dyn_cast<LoadInst>(Inst)) {
458         return LI->getPointerOperand();
459       } else if (StoreInst *SI = dyn_cast<StoreInst>(Inst)) {
460         return SI->getPointerOperand();
461       }
462       return nullptr;
463     }
mayReadFromMemory() const464     bool mayReadFromMemory() const {
465       if (IsTargetMemInst) return Info.ReadMem;
466       return Inst->mayReadFromMemory();
467     }
mayWriteToMemory() const468     bool mayWriteToMemory() const {
469       if (IsTargetMemInst) return Info.WriteMem;
470       return Inst->mayWriteToMemory();
471     }
472 
473   private:
474     bool IsTargetMemInst;
475     MemIntrinsicInfo Info;
476     Instruction *Inst;
477   };
478 
479   bool processNode(DomTreeNode *Node);
480 
getOrCreateResult(Value * Inst,Type * ExpectedType) const481   Value *getOrCreateResult(Value *Inst, Type *ExpectedType) const {
482     if (LoadInst *LI = dyn_cast<LoadInst>(Inst))
483       return LI;
484     else if (StoreInst *SI = dyn_cast<StoreInst>(Inst))
485       return SI->getValueOperand();
486     assert(isa<IntrinsicInst>(Inst) && "Instruction not supported");
487     return TTI.getOrCreateResultFromMemIntrinsic(cast<IntrinsicInst>(Inst),
488                                                  ExpectedType);
489   }
490 };
491 }
492 
processNode(DomTreeNode * Node)493 bool EarlyCSE::processNode(DomTreeNode *Node) {
494   bool Changed = false;
495   BasicBlock *BB = Node->getBlock();
496 
497   // If this block has a single predecessor, then the predecessor is the parent
498   // of the domtree node and all of the live out memory values are still current
499   // in this block.  If this block has multiple predecessors, then they could
500   // have invalidated the live-out memory values of our parent value.  For now,
501   // just be conservative and invalidate memory if this block has multiple
502   // predecessors.
503   if (!BB->getSinglePredecessor())
504     ++CurrentGeneration;
505 
506   // If this node has a single predecessor which ends in a conditional branch,
507   // we can infer the value of the branch condition given that we took this
508   // path.  We need the single predecessor to ensure there's not another path
509   // which reaches this block where the condition might hold a different
510   // value.  Since we're adding this to the scoped hash table (like any other
511   // def), it will have been popped if we encounter a future merge block.
512   if (BasicBlock *Pred = BB->getSinglePredecessor())
513     if (auto *BI = dyn_cast<BranchInst>(Pred->getTerminator()))
514       if (BI->isConditional())
515         if (auto *CondInst = dyn_cast<Instruction>(BI->getCondition()))
516           if (SimpleValue::canHandle(CondInst)) {
517             assert(BI->getSuccessor(0) == BB || BI->getSuccessor(1) == BB);
518             auto *ConditionalConstant = (BI->getSuccessor(0) == BB) ?
519               ConstantInt::getTrue(BB->getContext()) :
520               ConstantInt::getFalse(BB->getContext());
521             AvailableValues.insert(CondInst, ConditionalConstant);
522             DEBUG(dbgs() << "EarlyCSE CVP: Add conditional value for '"
523                   << CondInst->getName() << "' as " << *ConditionalConstant
524                   << " in " << BB->getName() << "\n");
525             // Replace all dominated uses with the known value.
526             if (unsigned Count =
527                     replaceDominatedUsesWith(CondInst, ConditionalConstant, DT,
528                                              BasicBlockEdge(Pred, BB))) {
529               Changed = true;
530               NumCSECVP = NumCSECVP + Count;
531             }
532           }
533 
534   /// LastStore - Keep track of the last non-volatile store that we saw... for
535   /// as long as there in no instruction that reads memory.  If we see a store
536   /// to the same location, we delete the dead store.  This zaps trivial dead
537   /// stores which can occur in bitfield code among other things.
538   Instruction *LastStore = nullptr;
539 
540   const DataLayout &DL = BB->getModule()->getDataLayout();
541 
542   // See if any instructions in the block can be eliminated.  If so, do it.  If
543   // not, add them to AvailableValues.
544   for (BasicBlock::iterator I = BB->begin(), E = BB->end(); I != E;) {
545     Instruction *Inst = &*I++;
546 
547     // Dead instructions should just be removed.
548     if (isInstructionTriviallyDead(Inst, &TLI)) {
549       DEBUG(dbgs() << "EarlyCSE DCE: " << *Inst << '\n');
550       Inst->eraseFromParent();
551       Changed = true;
552       ++NumSimplify;
553       continue;
554     }
555 
556     // Skip assume intrinsics, they don't really have side effects (although
557     // they're marked as such to ensure preservation of control dependencies),
558     // and this pass will not disturb any of the assumption's control
559     // dependencies.
560     if (match(Inst, m_Intrinsic<Intrinsic::assume>())) {
561       DEBUG(dbgs() << "EarlyCSE skipping assumption: " << *Inst << '\n');
562       continue;
563     }
564 
565     if (match(Inst, m_Intrinsic<Intrinsic::experimental_guard>())) {
566       if (auto *CondI =
567               dyn_cast<Instruction>(cast<CallInst>(Inst)->getArgOperand(0))) {
568         // The condition we're on guarding here is true for all dominated
569         // locations.
570         if (SimpleValue::canHandle(CondI))
571           AvailableValues.insert(CondI, ConstantInt::getTrue(BB->getContext()));
572       }
573 
574       // Guard intrinsics read all memory, but don't write any memory.
575       // Accordingly, don't update the generation but consume the last store (to
576       // avoid an incorrect DSE).
577       LastStore = nullptr;
578       continue;
579     }
580 
581     // If the instruction can be simplified (e.g. X+0 = X) then replace it with
582     // its simpler value.
583     if (Value *V = SimplifyInstruction(Inst, DL, &TLI, &DT, &AC)) {
584       DEBUG(dbgs() << "EarlyCSE Simplify: " << *Inst << "  to: " << *V << '\n');
585       if (!Inst->use_empty()) {
586         Inst->replaceAllUsesWith(V);
587         Changed = true;
588       }
589       if (isInstructionTriviallyDead(Inst, &TLI)) {
590         Inst->eraseFromParent();
591         Changed = true;
592       }
593       if (Changed) {
594         ++NumSimplify;
595         continue;
596       }
597     }
598 
599     // If this is a simple instruction that we can value number, process it.
600     if (SimpleValue::canHandle(Inst)) {
601       // See if the instruction has an available value.  If so, use it.
602       if (Value *V = AvailableValues.lookup(Inst)) {
603         DEBUG(dbgs() << "EarlyCSE CSE: " << *Inst << "  to: " << *V << '\n');
604         if (auto *I = dyn_cast<Instruction>(V))
605           I->andIRFlags(Inst);
606         Inst->replaceAllUsesWith(V);
607         Inst->eraseFromParent();
608         Changed = true;
609         ++NumCSE;
610         continue;
611       }
612 
613       // Otherwise, just remember that this value is available.
614       AvailableValues.insert(Inst, Inst);
615       continue;
616     }
617 
618     ParseMemoryInst MemInst(Inst, TTI);
619     // If this is a non-volatile load, process it.
620     if (MemInst.isValid() && MemInst.isLoad()) {
621       // (conservatively) we can't peak past the ordering implied by this
622       // operation, but we can add this load to our set of available values
623       if (MemInst.isVolatile() || !MemInst.isUnordered()) {
624         LastStore = nullptr;
625         ++CurrentGeneration;
626       }
627 
628       // If we have an available version of this load, and if it is the right
629       // generation or the load is known to be from an invariant location,
630       // replace this instruction.
631       //
632       // A dominating invariant load implies that the location loaded from is
633       // unchanging beginning at the point of the invariant load, so the load
634       // we're CSE'ing _away_ does not need to be invariant, only the available
635       // load we're CSE'ing _to_ does.
636       LoadValue InVal = AvailableLoads.lookup(MemInst.getPointerOperand());
637       if (InVal.DefInst != nullptr &&
638           (InVal.Generation == CurrentGeneration || InVal.IsInvariant) &&
639           InVal.MatchingId == MemInst.getMatchingId() &&
640           // We don't yet handle removing loads with ordering of any kind.
641           !MemInst.isVolatile() && MemInst.isUnordered() &&
642           // We can't replace an atomic load with one which isn't also atomic.
643           InVal.IsAtomic >= MemInst.isAtomic()) {
644         Value *Op = getOrCreateResult(InVal.DefInst, Inst->getType());
645         if (Op != nullptr) {
646           DEBUG(dbgs() << "EarlyCSE CSE LOAD: " << *Inst
647                        << "  to: " << *InVal.DefInst << '\n');
648           if (!Inst->use_empty())
649             Inst->replaceAllUsesWith(Op);
650           Inst->eraseFromParent();
651           Changed = true;
652           ++NumCSELoad;
653           continue;
654         }
655       }
656 
657       // Otherwise, remember that we have this instruction.
658       AvailableLoads.insert(
659           MemInst.getPointerOperand(),
660           LoadValue(Inst, CurrentGeneration, MemInst.getMatchingId(),
661                     MemInst.isAtomic(), MemInst.isInvariantLoad()));
662       LastStore = nullptr;
663       continue;
664     }
665 
666     // If this instruction may read from memory, forget LastStore.
667     // Load/store intrinsics will indicate both a read and a write to
668     // memory.  The target may override this (e.g. so that a store intrinsic
669     // does not read  from memory, and thus will be treated the same as a
670     // regular store for commoning purposes).
671     if (Inst->mayReadFromMemory() &&
672         !(MemInst.isValid() && !MemInst.mayReadFromMemory()))
673       LastStore = nullptr;
674 
675     // If this is a read-only call, process it.
676     if (CallValue::canHandle(Inst)) {
677       // If we have an available version of this call, and if it is the right
678       // generation, replace this instruction.
679       std::pair<Instruction *, unsigned> InVal = AvailableCalls.lookup(Inst);
680       if (InVal.first != nullptr && InVal.second == CurrentGeneration) {
681         DEBUG(dbgs() << "EarlyCSE CSE CALL: " << *Inst
682                      << "  to: " << *InVal.first << '\n');
683         if (!Inst->use_empty())
684           Inst->replaceAllUsesWith(InVal.first);
685         Inst->eraseFromParent();
686         Changed = true;
687         ++NumCSECall;
688         continue;
689       }
690 
691       // Otherwise, remember that we have this instruction.
692       AvailableCalls.insert(
693           Inst, std::pair<Instruction *, unsigned>(Inst, CurrentGeneration));
694       continue;
695     }
696 
697     // A release fence requires that all stores complete before it, but does
698     // not prevent the reordering of following loads 'before' the fence.  As a
699     // result, we don't need to consider it as writing to memory and don't need
700     // to advance the generation.  We do need to prevent DSE across the fence,
701     // but that's handled above.
702     if (FenceInst *FI = dyn_cast<FenceInst>(Inst))
703       if (FI->getOrdering() == AtomicOrdering::Release) {
704         assert(Inst->mayReadFromMemory() && "relied on to prevent DSE above");
705         continue;
706       }
707 
708     // write back DSE - If we write back the same value we just loaded from
709     // the same location and haven't passed any intervening writes or ordering
710     // operations, we can remove the write.  The primary benefit is in allowing
711     // the available load table to remain valid and value forward past where
712     // the store originally was.
713     if (MemInst.isValid() && MemInst.isStore()) {
714       LoadValue InVal = AvailableLoads.lookup(MemInst.getPointerOperand());
715       if (InVal.DefInst &&
716           InVal.DefInst == getOrCreateResult(Inst, InVal.DefInst->getType()) &&
717           InVal.Generation == CurrentGeneration &&
718           InVal.MatchingId == MemInst.getMatchingId() &&
719           // We don't yet handle removing stores with ordering of any kind.
720           !MemInst.isVolatile() && MemInst.isUnordered()) {
721         assert((!LastStore ||
722                 ParseMemoryInst(LastStore, TTI).getPointerOperand() ==
723                 MemInst.getPointerOperand()) &&
724                "can't have an intervening store!");
725         DEBUG(dbgs() << "EarlyCSE DSE (writeback): " << *Inst << '\n');
726         Inst->eraseFromParent();
727         Changed = true;
728         ++NumDSE;
729         // We can avoid incrementing the generation count since we were able
730         // to eliminate this store.
731         continue;
732       }
733     }
734 
735     // Okay, this isn't something we can CSE at all.  Check to see if it is
736     // something that could modify memory.  If so, our available memory values
737     // cannot be used so bump the generation count.
738     if (Inst->mayWriteToMemory()) {
739       ++CurrentGeneration;
740 
741       if (MemInst.isValid() && MemInst.isStore()) {
742         // We do a trivial form of DSE if there are two stores to the same
743         // location with no intervening loads.  Delete the earlier store.
744         // At the moment, we don't remove ordered stores, but do remove
745         // unordered atomic stores.  There's no special requirement (for
746         // unordered atomics) about removing atomic stores only in favor of
747         // other atomic stores since we we're going to execute the non-atomic
748         // one anyway and the atomic one might never have become visible.
749         if (LastStore) {
750           ParseMemoryInst LastStoreMemInst(LastStore, TTI);
751           assert(LastStoreMemInst.isUnordered() &&
752                  !LastStoreMemInst.isVolatile() &&
753                  "Violated invariant");
754           if (LastStoreMemInst.isMatchingMemLoc(MemInst)) {
755             DEBUG(dbgs() << "EarlyCSE DEAD STORE: " << *LastStore
756                          << "  due to: " << *Inst << '\n');
757             LastStore->eraseFromParent();
758             Changed = true;
759             ++NumDSE;
760             LastStore = nullptr;
761           }
762           // fallthrough - we can exploit information about this store
763         }
764 
765         // Okay, we just invalidated anything we knew about loaded values.  Try
766         // to salvage *something* by remembering that the stored value is a live
767         // version of the pointer.  It is safe to forward from volatile stores
768         // to non-volatile loads, so we don't have to check for volatility of
769         // the store.
770         AvailableLoads.insert(
771             MemInst.getPointerOperand(),
772             LoadValue(Inst, CurrentGeneration, MemInst.getMatchingId(),
773                       MemInst.isAtomic(), /*IsInvariant=*/false));
774 
775         // Remember that this was the last unordered store we saw for DSE. We
776         // don't yet handle DSE on ordered or volatile stores since we don't
777         // have a good way to model the ordering requirement for following
778         // passes  once the store is removed.  We could insert a fence, but
779         // since fences are slightly stronger than stores in their ordering,
780         // it's not clear this is a profitable transform. Another option would
781         // be to merge the ordering with that of the post dominating store.
782         if (MemInst.isUnordered() && !MemInst.isVolatile())
783           LastStore = Inst;
784         else
785           LastStore = nullptr;
786       }
787     }
788   }
789 
790   return Changed;
791 }
792 
run()793 bool EarlyCSE::run() {
794   // Note, deque is being used here because there is significant performance
795   // gains over vector when the container becomes very large due to the
796   // specific access patterns. For more information see the mailing list
797   // discussion on this:
798   // http://lists.llvm.org/pipermail/llvm-commits/Week-of-Mon-20120116/135228.html
799   std::deque<StackNode *> nodesToProcess;
800 
801   bool Changed = false;
802 
803   // Process the root node.
804   nodesToProcess.push_back(new StackNode(
805       AvailableValues, AvailableLoads, AvailableCalls, CurrentGeneration,
806       DT.getRootNode(), DT.getRootNode()->begin(), DT.getRootNode()->end()));
807 
808   // Save the current generation.
809   unsigned LiveOutGeneration = CurrentGeneration;
810 
811   // Process the stack.
812   while (!nodesToProcess.empty()) {
813     // Grab the first item off the stack. Set the current generation, remove
814     // the node from the stack, and process it.
815     StackNode *NodeToProcess = nodesToProcess.back();
816 
817     // Initialize class members.
818     CurrentGeneration = NodeToProcess->currentGeneration();
819 
820     // Check if the node needs to be processed.
821     if (!NodeToProcess->isProcessed()) {
822       // Process the node.
823       Changed |= processNode(NodeToProcess->node());
824       NodeToProcess->childGeneration(CurrentGeneration);
825       NodeToProcess->process();
826     } else if (NodeToProcess->childIter() != NodeToProcess->end()) {
827       // Push the next child onto the stack.
828       DomTreeNode *child = NodeToProcess->nextChild();
829       nodesToProcess.push_back(
830           new StackNode(AvailableValues, AvailableLoads, AvailableCalls,
831                         NodeToProcess->childGeneration(), child, child->begin(),
832                         child->end()));
833     } else {
834       // It has been processed, and there are no more children to process,
835       // so delete it and pop it off the stack.
836       delete NodeToProcess;
837       nodesToProcess.pop_back();
838     }
839   } // while (!nodes...)
840 
841   // Reset the current generation.
842   CurrentGeneration = LiveOutGeneration;
843 
844   return Changed;
845 }
846 
run(Function & F,AnalysisManager<Function> & AM)847 PreservedAnalyses EarlyCSEPass::run(Function &F,
848                                     AnalysisManager<Function> &AM) {
849   auto &TLI = AM.getResult<TargetLibraryAnalysis>(F);
850   auto &TTI = AM.getResult<TargetIRAnalysis>(F);
851   auto &DT = AM.getResult<DominatorTreeAnalysis>(F);
852   auto &AC = AM.getResult<AssumptionAnalysis>(F);
853 
854   EarlyCSE CSE(TLI, TTI, DT, AC);
855 
856   if (!CSE.run())
857     return PreservedAnalyses::all();
858 
859   // CSE preserves the dominator tree because it doesn't mutate the CFG.
860   // FIXME: Bundle this with other CFG-preservation.
861   PreservedAnalyses PA;
862   PA.preserve<DominatorTreeAnalysis>();
863   PA.preserve<GlobalsAA>();
864   return PA;
865 }
866 
867 namespace {
868 /// \brief A simple and fast domtree-based CSE pass.
869 ///
870 /// This pass does a simple depth-first walk over the dominator tree,
871 /// eliminating trivially redundant instructions and using instsimplify to
872 /// canonicalize things as it goes. It is intended to be fast and catch obvious
873 /// cases so that instcombine and other passes are more effective. It is
874 /// expected that a later pass of GVN will catch the interesting/hard cases.
875 class EarlyCSELegacyPass : public FunctionPass {
876 public:
877   static char ID;
878 
EarlyCSELegacyPass()879   EarlyCSELegacyPass() : FunctionPass(ID) {
880     initializeEarlyCSELegacyPassPass(*PassRegistry::getPassRegistry());
881   }
882 
runOnFunction(Function & F)883   bool runOnFunction(Function &F) override {
884     if (skipFunction(F))
885       return false;
886 
887     auto &TLI = getAnalysis<TargetLibraryInfoWrapperPass>().getTLI();
888     auto &TTI = getAnalysis<TargetTransformInfoWrapperPass>().getTTI(F);
889     auto &DT = getAnalysis<DominatorTreeWrapperPass>().getDomTree();
890     auto &AC = getAnalysis<AssumptionCacheTracker>().getAssumptionCache(F);
891 
892     EarlyCSE CSE(TLI, TTI, DT, AC);
893 
894     return CSE.run();
895   }
896 
getAnalysisUsage(AnalysisUsage & AU) const897   void getAnalysisUsage(AnalysisUsage &AU) const override {
898     AU.addRequired<AssumptionCacheTracker>();
899     AU.addRequired<DominatorTreeWrapperPass>();
900     AU.addRequired<TargetLibraryInfoWrapperPass>();
901     AU.addRequired<TargetTransformInfoWrapperPass>();
902     AU.addPreserved<GlobalsAAWrapperPass>();
903     AU.setPreservesCFG();
904   }
905 };
906 }
907 
908 char EarlyCSELegacyPass::ID = 0;
909 
createEarlyCSEPass()910 FunctionPass *llvm::createEarlyCSEPass() { return new EarlyCSELegacyPass(); }
911 
912 INITIALIZE_PASS_BEGIN(EarlyCSELegacyPass, "early-cse", "Early CSE", false,
913                       false)
914 INITIALIZE_PASS_DEPENDENCY(TargetTransformInfoWrapperPass)
915 INITIALIZE_PASS_DEPENDENCY(AssumptionCacheTracker)
916 INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
917 INITIALIZE_PASS_DEPENDENCY(TargetLibraryInfoWrapperPass)
918 INITIALIZE_PASS_END(EarlyCSELegacyPass, "early-cse", "Early CSE", false, false)
919