[EarlyCSE] Teach about CSE'ing over invariant.start intrinsics
[lldb.git] / llvm / lib / Transforms / Scalar / EarlyCSE.cpp
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
57   SimpleValue(Instruction *I) : Inst(I) {
58     assert((isSentinel() || canHandle(I)) && "Inst can't be handled!");
59   }
60
61   bool isSentinel() const {
62     return Inst == DenseMapInfo<Instruction *>::getEmptyKey() ||
63            Inst == DenseMapInfo<Instruction *>::getTombstoneKey();
64   }
65
66   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> {
81   static inline SimpleValue getEmptyKey() {
82     return DenseMapInfo<Instruction *>::getEmptyKey();
83   }
84   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
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
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
186   CallValue(Instruction *I) : Inst(I) {
187     assert((isSentinel() || canHandle(I)) && "Inst can't be handled!");
188   }
189
190   bool isSentinel() const {
191     return Inst == DenseMapInfo<Instruction *>::getEmptyKey() ||
192            Inst == DenseMapInfo<Instruction *>::getTombstoneKey();
193   }
194
195   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> {
210   static inline CallValue getEmptyKey() {
211     return DenseMapInfo<Instruction *>::getEmptyKey();
212   }
213   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
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
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;
287     LoadValue()
288         : DefInst(nullptr), Generation(0), MatchingId(-1), IsAtomic(false),
289           IsInvariant(false) {}
290     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.
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:
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:
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.
354     unsigned currentGeneration() { return CurrentGeneration; }
355     unsigned childGeneration() { return ChildGeneration; }
356     void childGeneration(unsigned generation) { ChildGeneration = generation; }
357     DomTreeNode *node() { return Node; }
358     DomTreeNode::iterator childIter() { return ChildIter; }
359     DomTreeNode *nextChild() {
360       DomTreeNode *child = *ChildIter;
361       ++ChildIter;
362       return child;
363     }
364     DomTreeNode::iterator end() { return EndIter; }
365     bool isProcessed() { return Processed; }
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:
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     }
392     bool isLoad() const {
393       if (IsTargetMemInst) return Info.ReadMem;
394       return isa<LoadInst>(Inst);
395     }
396     bool isStore() const {
397       if (IsTargetMemInst) return Info.WriteMem;
398       return isa<StoreInst>(Inst);
399     }
400     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     }
407     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
421     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
435     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
441     bool isMatchingMemLoc(const ParseMemoryInst &Inst) const {
442       return (getPointerOperand() == Inst.getPointerOperand() &&
443               getMatchingId() == Inst.getMatchingId());
444     }
445     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.
451     int getMatchingId() const {
452       if (IsTargetMemInst) return Info.MatchingId;
453       return -1;
454     }
455     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     }
464     bool mayReadFromMemory() const {
465       if (IsTargetMemInst) return Info.ReadMem;
466       return Inst->mayReadFromMemory();
467     }
468     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
481   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
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     // Skip invariant.start intrinsics since they only read memory, and we can
566     // forward values across it. Also, we dont need to consume the last store
567     // since the semantics of invariant.start allow us to perform DSE of the
568     // last store, if there was a store following invariant.start. Consider:
569     //
570     // store 30, i8* p
571     // invariant.start(p)
572     // store 40, i8* p
573     // We can DSE the store to 30, since the store 40 to invariant location p
574     // causes undefined behaviour.
575     if (match(Inst, m_Intrinsic<Intrinsic::invariant_start>()))
576       continue;
577
578     if (match(Inst, m_Intrinsic<Intrinsic::experimental_guard>())) {
579       if (auto *CondI =
580               dyn_cast<Instruction>(cast<CallInst>(Inst)->getArgOperand(0))) {
581         // The condition we're on guarding here is true for all dominated
582         // locations.
583         if (SimpleValue::canHandle(CondI))
584           AvailableValues.insert(CondI, ConstantInt::getTrue(BB->getContext()));
585       }
586
587       // Guard intrinsics read all memory, but don't write any memory.
588       // Accordingly, don't update the generation but consume the last store (to
589       // avoid an incorrect DSE).
590       LastStore = nullptr;
591       continue;
592     }
593
594     // If the instruction can be simplified (e.g. X+0 = X) then replace it with
595     // its simpler value.
596     if (Value *V = SimplifyInstruction(Inst, DL, &TLI, &DT, &AC)) {
597       DEBUG(dbgs() << "EarlyCSE Simplify: " << *Inst << "  to: " << *V << '\n');
598       bool Killed = false;
599       if (!Inst->use_empty()) {
600         Inst->replaceAllUsesWith(V);
601         Changed = true;
602       }
603       if (isInstructionTriviallyDead(Inst, &TLI)) {
604         Inst->eraseFromParent();
605         Changed = true;
606         Killed = true;
607       }
608       if (Changed)
609         ++NumSimplify;
610       if (Killed)
611         continue;
612     }
613
614     // If this is a simple instruction that we can value number, process it.
615     if (SimpleValue::canHandle(Inst)) {
616       // See if the instruction has an available value.  If so, use it.
617       if (Value *V = AvailableValues.lookup(Inst)) {
618         DEBUG(dbgs() << "EarlyCSE CSE: " << *Inst << "  to: " << *V << '\n');
619         if (auto *I = dyn_cast<Instruction>(V))
620           I->andIRFlags(Inst);
621         Inst->replaceAllUsesWith(V);
622         Inst->eraseFromParent();
623         Changed = true;
624         ++NumCSE;
625         continue;
626       }
627
628       // Otherwise, just remember that this value is available.
629       AvailableValues.insert(Inst, Inst);
630       continue;
631     }
632
633     ParseMemoryInst MemInst(Inst, TTI);
634     // If this is a non-volatile load, process it.
635     if (MemInst.isValid() && MemInst.isLoad()) {
636       // (conservatively) we can't peak past the ordering implied by this
637       // operation, but we can add this load to our set of available values
638       if (MemInst.isVolatile() || !MemInst.isUnordered()) {
639         LastStore = nullptr;
640         ++CurrentGeneration;
641       }
642
643       // If we have an available version of this load, and if it is the right
644       // generation or the load is known to be from an invariant location,
645       // replace this instruction.
646       //
647       // A dominating invariant load implies that the location loaded from is
648       // unchanging beginning at the point of the invariant load, so the load
649       // we're CSE'ing _away_ does not need to be invariant, only the available
650       // load we're CSE'ing _to_ does.
651       LoadValue InVal = AvailableLoads.lookup(MemInst.getPointerOperand());
652       if (InVal.DefInst != nullptr &&
653           (InVal.Generation == CurrentGeneration || InVal.IsInvariant) &&
654           InVal.MatchingId == MemInst.getMatchingId() &&
655           // We don't yet handle removing loads with ordering of any kind.
656           !MemInst.isVolatile() && MemInst.isUnordered() &&
657           // We can't replace an atomic load with one which isn't also atomic.
658           InVal.IsAtomic >= MemInst.isAtomic()) {
659         Value *Op = getOrCreateResult(InVal.DefInst, Inst->getType());
660         if (Op != nullptr) {
661           DEBUG(dbgs() << "EarlyCSE CSE LOAD: " << *Inst
662                        << "  to: " << *InVal.DefInst << '\n');
663           if (!Inst->use_empty())
664             Inst->replaceAllUsesWith(Op);
665           Inst->eraseFromParent();
666           Changed = true;
667           ++NumCSELoad;
668           continue;
669         }
670       }
671
672       // Otherwise, remember that we have this instruction.
673       AvailableLoads.insert(
674           MemInst.getPointerOperand(),
675           LoadValue(Inst, CurrentGeneration, MemInst.getMatchingId(),
676                     MemInst.isAtomic(), MemInst.isInvariantLoad()));
677       LastStore = nullptr;
678       continue;
679     }
680
681     // If this instruction may read from memory, forget LastStore.
682     // Load/store intrinsics will indicate both a read and a write to
683     // memory.  The target may override this (e.g. so that a store intrinsic
684     // does not read  from memory, and thus will be treated the same as a
685     // regular store for commoning purposes).
686     if (Inst->mayReadFromMemory() &&
687         !(MemInst.isValid() && !MemInst.mayReadFromMemory()))
688       LastStore = nullptr;
689
690     // If this is a read-only call, process it.
691     if (CallValue::canHandle(Inst)) {
692       // If we have an available version of this call, and if it is the right
693       // generation, replace this instruction.
694       std::pair<Instruction *, unsigned> InVal = AvailableCalls.lookup(Inst);
695       if (InVal.first != nullptr && InVal.second == CurrentGeneration) {
696         DEBUG(dbgs() << "EarlyCSE CSE CALL: " << *Inst
697                      << "  to: " << *InVal.first << '\n');
698         if (!Inst->use_empty())
699           Inst->replaceAllUsesWith(InVal.first);
700         Inst->eraseFromParent();
701         Changed = true;
702         ++NumCSECall;
703         continue;
704       }
705
706       // Otherwise, remember that we have this instruction.
707       AvailableCalls.insert(
708           Inst, std::pair<Instruction *, unsigned>(Inst, CurrentGeneration));
709       continue;
710     }
711
712     // A release fence requires that all stores complete before it, but does
713     // not prevent the reordering of following loads 'before' the fence.  As a
714     // result, we don't need to consider it as writing to memory and don't need
715     // to advance the generation.  We do need to prevent DSE across the fence,
716     // but that's handled above.
717     if (FenceInst *FI = dyn_cast<FenceInst>(Inst))
718       if (FI->getOrdering() == AtomicOrdering::Release) {
719         assert(Inst->mayReadFromMemory() && "relied on to prevent DSE above");
720         continue;
721       }
722
723     // write back DSE - If we write back the same value we just loaded from
724     // the same location and haven't passed any intervening writes or ordering
725     // operations, we can remove the write.  The primary benefit is in allowing
726     // the available load table to remain valid and value forward past where
727     // the store originally was.
728     if (MemInst.isValid() && MemInst.isStore()) {
729       LoadValue InVal = AvailableLoads.lookup(MemInst.getPointerOperand());
730       if (InVal.DefInst &&
731           InVal.DefInst == getOrCreateResult(Inst, InVal.DefInst->getType()) &&
732           InVal.Generation == CurrentGeneration &&
733           InVal.MatchingId == MemInst.getMatchingId() &&
734           // We don't yet handle removing stores with ordering of any kind.
735           !MemInst.isVolatile() && MemInst.isUnordered()) {
736         assert((!LastStore ||
737                 ParseMemoryInst(LastStore, TTI).getPointerOperand() ==
738                 MemInst.getPointerOperand()) &&
739                "can't have an intervening store!");
740         DEBUG(dbgs() << "EarlyCSE DSE (writeback): " << *Inst << '\n');
741         Inst->eraseFromParent();
742         Changed = true;
743         ++NumDSE;
744         // We can avoid incrementing the generation count since we were able
745         // to eliminate this store.
746         continue;
747       }
748     }
749
750     // Okay, this isn't something we can CSE at all.  Check to see if it is
751     // something that could modify memory.  If so, our available memory values
752     // cannot be used so bump the generation count.
753     if (Inst->mayWriteToMemory()) {
754       ++CurrentGeneration;
755
756       if (MemInst.isValid() && MemInst.isStore()) {
757         // We do a trivial form of DSE if there are two stores to the same
758         // location with no intervening loads.  Delete the earlier store.
759         // At the moment, we don't remove ordered stores, but do remove
760         // unordered atomic stores.  There's no special requirement (for
761         // unordered atomics) about removing atomic stores only in favor of
762         // other atomic stores since we we're going to execute the non-atomic
763         // one anyway and the atomic one might never have become visible.
764         if (LastStore) {
765           ParseMemoryInst LastStoreMemInst(LastStore, TTI);
766           assert(LastStoreMemInst.isUnordered() &&
767                  !LastStoreMemInst.isVolatile() &&
768                  "Violated invariant");
769           if (LastStoreMemInst.isMatchingMemLoc(MemInst)) {
770             DEBUG(dbgs() << "EarlyCSE DEAD STORE: " << *LastStore
771                          << "  due to: " << *Inst << '\n');
772             LastStore->eraseFromParent();
773             Changed = true;
774             ++NumDSE;
775             LastStore = nullptr;
776           }
777           // fallthrough - we can exploit information about this store
778         }
779
780         // Okay, we just invalidated anything we knew about loaded values.  Try
781         // to salvage *something* by remembering that the stored value is a live
782         // version of the pointer.  It is safe to forward from volatile stores
783         // to non-volatile loads, so we don't have to check for volatility of
784         // the store.
785         AvailableLoads.insert(
786             MemInst.getPointerOperand(),
787             LoadValue(Inst, CurrentGeneration, MemInst.getMatchingId(),
788                       MemInst.isAtomic(), /*IsInvariant=*/false));
789
790         // Remember that this was the last unordered store we saw for DSE. We
791         // don't yet handle DSE on ordered or volatile stores since we don't
792         // have a good way to model the ordering requirement for following
793         // passes  once the store is removed.  We could insert a fence, but
794         // since fences are slightly stronger than stores in their ordering,
795         // it's not clear this is a profitable transform. Another option would
796         // be to merge the ordering with that of the post dominating store.
797         if (MemInst.isUnordered() && !MemInst.isVolatile())
798           LastStore = Inst;
799         else
800           LastStore = nullptr;
801       }
802     }
803   }
804
805   return Changed;
806 }
807
808 bool EarlyCSE::run() {
809   // Note, deque is being used here because there is significant performance
810   // gains over vector when the container becomes very large due to the
811   // specific access patterns. For more information see the mailing list
812   // discussion on this:
813   // http://lists.llvm.org/pipermail/llvm-commits/Week-of-Mon-20120116/135228.html
814   std::deque<StackNode *> nodesToProcess;
815
816   bool Changed = false;
817
818   // Process the root node.
819   nodesToProcess.push_back(new StackNode(
820       AvailableValues, AvailableLoads, AvailableCalls, CurrentGeneration,
821       DT.getRootNode(), DT.getRootNode()->begin(), DT.getRootNode()->end()));
822
823   // Save the current generation.
824   unsigned LiveOutGeneration = CurrentGeneration;
825
826   // Process the stack.
827   while (!nodesToProcess.empty()) {
828     // Grab the first item off the stack. Set the current generation, remove
829     // the node from the stack, and process it.
830     StackNode *NodeToProcess = nodesToProcess.back();
831
832     // Initialize class members.
833     CurrentGeneration = NodeToProcess->currentGeneration();
834
835     // Check if the node needs to be processed.
836     if (!NodeToProcess->isProcessed()) {
837       // Process the node.
838       Changed |= processNode(NodeToProcess->node());
839       NodeToProcess->childGeneration(CurrentGeneration);
840       NodeToProcess->process();
841     } else if (NodeToProcess->childIter() != NodeToProcess->end()) {
842       // Push the next child onto the stack.
843       DomTreeNode *child = NodeToProcess->nextChild();
844       nodesToProcess.push_back(
845           new StackNode(AvailableValues, AvailableLoads, AvailableCalls,
846                         NodeToProcess->childGeneration(), child, child->begin(),
847                         child->end()));
848     } else {
849       // It has been processed, and there are no more children to process,
850       // so delete it and pop it off the stack.
851       delete NodeToProcess;
852       nodesToProcess.pop_back();
853     }
854   } // while (!nodes...)
855
856   // Reset the current generation.
857   CurrentGeneration = LiveOutGeneration;
858
859   return Changed;
860 }
861
862 PreservedAnalyses EarlyCSEPass::run(Function &F,
863                                     FunctionAnalysisManager &AM) {
864   auto &TLI = AM.getResult<TargetLibraryAnalysis>(F);
865   auto &TTI = AM.getResult<TargetIRAnalysis>(F);
866   auto &DT = AM.getResult<DominatorTreeAnalysis>(F);
867   auto &AC = AM.getResult<AssumptionAnalysis>(F);
868
869   EarlyCSE CSE(TLI, TTI, DT, AC);
870
871   if (!CSE.run())
872     return PreservedAnalyses::all();
873
874   // CSE preserves the dominator tree because it doesn't mutate the CFG.
875   // FIXME: Bundle this with other CFG-preservation.
876   PreservedAnalyses PA;
877   PA.preserve<DominatorTreeAnalysis>();
878   PA.preserve<GlobalsAA>();
879   return PA;
880 }
881
882 namespace {
883 /// \brief A simple and fast domtree-based CSE pass.
884 ///
885 /// This pass does a simple depth-first walk over the dominator tree,
886 /// eliminating trivially redundant instructions and using instsimplify to
887 /// canonicalize things as it goes. It is intended to be fast and catch obvious
888 /// cases so that instcombine and other passes are more effective. It is
889 /// expected that a later pass of GVN will catch the interesting/hard cases.
890 class EarlyCSELegacyPass : public FunctionPass {
891 public:
892   static char ID;
893
894   EarlyCSELegacyPass() : FunctionPass(ID) {
895     initializeEarlyCSELegacyPassPass(*PassRegistry::getPassRegistry());
896   }
897
898   bool runOnFunction(Function &F) override {
899     if (skipFunction(F))
900       return false;
901
902     auto &TLI = getAnalysis<TargetLibraryInfoWrapperPass>().getTLI();
903     auto &TTI = getAnalysis<TargetTransformInfoWrapperPass>().getTTI(F);
904     auto &DT = getAnalysis<DominatorTreeWrapperPass>().getDomTree();
905     auto &AC = getAnalysis<AssumptionCacheTracker>().getAssumptionCache(F);
906
907     EarlyCSE CSE(TLI, TTI, DT, AC);
908
909     return CSE.run();
910   }
911
912   void getAnalysisUsage(AnalysisUsage &AU) const override {
913     AU.addRequired<AssumptionCacheTracker>();
914     AU.addRequired<DominatorTreeWrapperPass>();
915     AU.addRequired<TargetLibraryInfoWrapperPass>();
916     AU.addRequired<TargetTransformInfoWrapperPass>();
917     AU.addPreserved<GlobalsAAWrapperPass>();
918     AU.setPreservesCFG();
919   }
920 };
921 }
922
923 char EarlyCSELegacyPass::ID = 0;
924
925 FunctionPass *llvm::createEarlyCSEPass() { return new EarlyCSELegacyPass(); }
926
927 INITIALIZE_PASS_BEGIN(EarlyCSELegacyPass, "early-cse", "Early CSE", false,
928                       false)
929 INITIALIZE_PASS_DEPENDENCY(TargetTransformInfoWrapperPass)
930 INITIALIZE_PASS_DEPENDENCY(AssumptionCacheTracker)
931 INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
932 INITIALIZE_PASS_DEPENDENCY(TargetLibraryInfoWrapperPass)
933 INITIALIZE_PASS_END(EarlyCSELegacyPass, "early-cse", "Early CSE", false, false)