LLVM  mainline
EarlyCSE.cpp
Go to the documentation of this file.
00001 //===- EarlyCSE.cpp - Simple and fast CSE pass ----------------------------===//
00002 //
00003 //                     The LLVM Compiler Infrastructure
00004 //
00005 // This file is distributed under the University of Illinois Open Source
00006 // License. See LICENSE.TXT for details.
00007 //
00008 //===----------------------------------------------------------------------===//
00009 //
00010 // This pass performs a simple dominator tree walk that eliminates trivially
00011 // redundant instructions.
00012 //
00013 //===----------------------------------------------------------------------===//
00014 
00015 #include "llvm/Transforms/Scalar/EarlyCSE.h"
00016 #include "llvm/ADT/Hashing.h"
00017 #include "llvm/ADT/ScopedHashTable.h"
00018 #include "llvm/ADT/Statistic.h"
00019 #include "llvm/Analysis/GlobalsModRef.h"
00020 #include "llvm/Analysis/AssumptionCache.h"
00021 #include "llvm/Analysis/InstructionSimplify.h"
00022 #include "llvm/Analysis/TargetLibraryInfo.h"
00023 #include "llvm/Analysis/TargetTransformInfo.h"
00024 #include "llvm/IR/DataLayout.h"
00025 #include "llvm/IR/Dominators.h"
00026 #include "llvm/IR/Instructions.h"
00027 #include "llvm/IR/IntrinsicInst.h"
00028 #include "llvm/IR/PatternMatch.h"
00029 #include "llvm/Pass.h"
00030 #include "llvm/Support/Debug.h"
00031 #include "llvm/Support/RecyclingAllocator.h"
00032 #include "llvm/Support/raw_ostream.h"
00033 #include "llvm/Transforms/Scalar.h"
00034 #include "llvm/Transforms/Utils/Local.h"
00035 #include <deque>
00036 using namespace llvm;
00037 using namespace llvm::PatternMatch;
00038 
00039 #define DEBUG_TYPE "early-cse"
00040 
00041 STATISTIC(NumSimplify, "Number of instructions simplified or DCE'd");
00042 STATISTIC(NumCSE,      "Number of instructions CSE'd");
00043 STATISTIC(NumCSELoad,  "Number of load instructions CSE'd");
00044 STATISTIC(NumCSECall,  "Number of call instructions CSE'd");
00045 STATISTIC(NumDSE,      "Number of trivial dead stores removed");
00046 
00047 //===----------------------------------------------------------------------===//
00048 // SimpleValue
00049 //===----------------------------------------------------------------------===//
00050 
00051 namespace {
00052 /// \brief Struct representing the available values in the scoped hash table.
00053 struct SimpleValue {
00054   Instruction *Inst;
00055 
00056   SimpleValue(Instruction *I) : Inst(I) {
00057     assert((isSentinel() || canHandle(I)) && "Inst can't be handled!");
00058   }
00059 
00060   bool isSentinel() const {
00061     return Inst == DenseMapInfo<Instruction *>::getEmptyKey() ||
00062            Inst == DenseMapInfo<Instruction *>::getTombstoneKey();
00063   }
00064 
00065   static bool canHandle(Instruction *Inst) {
00066     // This can only handle non-void readnone functions.
00067     if (CallInst *CI = dyn_cast<CallInst>(Inst))
00068       return CI->doesNotAccessMemory() && !CI->getType()->isVoidTy();
00069     return isa<CastInst>(Inst) || isa<BinaryOperator>(Inst) ||
00070            isa<GetElementPtrInst>(Inst) || isa<CmpInst>(Inst) ||
00071            isa<SelectInst>(Inst) || isa<ExtractElementInst>(Inst) ||
00072            isa<InsertElementInst>(Inst) || isa<ShuffleVectorInst>(Inst) ||
00073            isa<ExtractValueInst>(Inst) || isa<InsertValueInst>(Inst);
00074   }
00075 };
00076 }
00077 
00078 namespace llvm {
00079 template <> struct DenseMapInfo<SimpleValue> {
00080   static inline SimpleValue getEmptyKey() {
00081     return DenseMapInfo<Instruction *>::getEmptyKey();
00082   }
00083   static inline SimpleValue getTombstoneKey() {
00084     return DenseMapInfo<Instruction *>::getTombstoneKey();
00085   }
00086   static unsigned getHashValue(SimpleValue Val);
00087   static bool isEqual(SimpleValue LHS, SimpleValue RHS);
00088 };
00089 }
00090 
00091 unsigned DenseMapInfo<SimpleValue>::getHashValue(SimpleValue Val) {
00092   Instruction *Inst = Val.Inst;
00093   // Hash in all of the operands as pointers.
00094   if (BinaryOperator *BinOp = dyn_cast<BinaryOperator>(Inst)) {
00095     Value *LHS = BinOp->getOperand(0);
00096     Value *RHS = BinOp->getOperand(1);
00097     if (BinOp->isCommutative() && BinOp->getOperand(0) > BinOp->getOperand(1))
00098       std::swap(LHS, RHS);
00099 
00100     if (isa<OverflowingBinaryOperator>(BinOp)) {
00101       // Hash the overflow behavior
00102       unsigned Overflow =
00103           BinOp->hasNoSignedWrap() * OverflowingBinaryOperator::NoSignedWrap |
00104           BinOp->hasNoUnsignedWrap() *
00105               OverflowingBinaryOperator::NoUnsignedWrap;
00106       return hash_combine(BinOp->getOpcode(), Overflow, LHS, RHS);
00107     }
00108 
00109     return hash_combine(BinOp->getOpcode(), LHS, RHS);
00110   }
00111 
00112   if (CmpInst *CI = dyn_cast<CmpInst>(Inst)) {
00113     Value *LHS = CI->getOperand(0);
00114     Value *RHS = CI->getOperand(1);
00115     CmpInst::Predicate Pred = CI->getPredicate();
00116     if (Inst->getOperand(0) > Inst->getOperand(1)) {
00117       std::swap(LHS, RHS);
00118       Pred = CI->getSwappedPredicate();
00119     }
00120     return hash_combine(Inst->getOpcode(), Pred, LHS, RHS);
00121   }
00122 
00123   if (CastInst *CI = dyn_cast<CastInst>(Inst))
00124     return hash_combine(CI->getOpcode(), CI->getType(), CI->getOperand(0));
00125 
00126   if (const ExtractValueInst *EVI = dyn_cast<ExtractValueInst>(Inst))
00127     return hash_combine(EVI->getOpcode(), EVI->getOperand(0),
00128                         hash_combine_range(EVI->idx_begin(), EVI->idx_end()));
00129 
00130   if (const InsertValueInst *IVI = dyn_cast<InsertValueInst>(Inst))
00131     return hash_combine(IVI->getOpcode(), IVI->getOperand(0),
00132                         IVI->getOperand(1),
00133                         hash_combine_range(IVI->idx_begin(), IVI->idx_end()));
00134 
00135   assert((isa<CallInst>(Inst) || isa<BinaryOperator>(Inst) ||
00136           isa<GetElementPtrInst>(Inst) || isa<SelectInst>(Inst) ||
00137           isa<ExtractElementInst>(Inst) || isa<InsertElementInst>(Inst) ||
00138           isa<ShuffleVectorInst>(Inst)) &&
00139          "Invalid/unknown instruction");
00140 
00141   // Mix in the opcode.
00142   return hash_combine(
00143       Inst->getOpcode(),
00144       hash_combine_range(Inst->value_op_begin(), Inst->value_op_end()));
00145 }
00146 
00147 bool DenseMapInfo<SimpleValue>::isEqual(SimpleValue LHS, SimpleValue RHS) {
00148   Instruction *LHSI = LHS.Inst, *RHSI = RHS.Inst;
00149 
00150   if (LHS.isSentinel() || RHS.isSentinel())
00151     return LHSI == RHSI;
00152 
00153   if (LHSI->getOpcode() != RHSI->getOpcode())
00154     return false;
00155   if (LHSI->isIdenticalTo(RHSI))
00156     return true;
00157 
00158   // If we're not strictly identical, we still might be a commutable instruction
00159   if (BinaryOperator *LHSBinOp = dyn_cast<BinaryOperator>(LHSI)) {
00160     if (!LHSBinOp->isCommutative())
00161       return false;
00162 
00163     assert(isa<BinaryOperator>(RHSI) &&
00164            "same opcode, but different instruction type?");
00165     BinaryOperator *RHSBinOp = cast<BinaryOperator>(RHSI);
00166 
00167     // Check overflow attributes
00168     if (isa<OverflowingBinaryOperator>(LHSBinOp)) {
00169       assert(isa<OverflowingBinaryOperator>(RHSBinOp) &&
00170              "same opcode, but different operator type?");
00171       if (LHSBinOp->hasNoUnsignedWrap() != RHSBinOp->hasNoUnsignedWrap() ||
00172           LHSBinOp->hasNoSignedWrap() != RHSBinOp->hasNoSignedWrap())
00173         return false;
00174     }
00175 
00176     // Commuted equality
00177     return LHSBinOp->getOperand(0) == RHSBinOp->getOperand(1) &&
00178            LHSBinOp->getOperand(1) == RHSBinOp->getOperand(0);
00179   }
00180   if (CmpInst *LHSCmp = dyn_cast<CmpInst>(LHSI)) {
00181     assert(isa<CmpInst>(RHSI) &&
00182            "same opcode, but different instruction type?");
00183     CmpInst *RHSCmp = cast<CmpInst>(RHSI);
00184     // Commuted equality
00185     return LHSCmp->getOperand(0) == RHSCmp->getOperand(1) &&
00186            LHSCmp->getOperand(1) == RHSCmp->getOperand(0) &&
00187            LHSCmp->getSwappedPredicate() == RHSCmp->getPredicate();
00188   }
00189 
00190   return false;
00191 }
00192 
00193 //===----------------------------------------------------------------------===//
00194 // CallValue
00195 //===----------------------------------------------------------------------===//
00196 
00197 namespace {
00198 /// \brief Struct representing the available call values in the scoped hash
00199 /// table.
00200 struct CallValue {
00201   Instruction *Inst;
00202 
00203   CallValue(Instruction *I) : Inst(I) {
00204     assert((isSentinel() || canHandle(I)) && "Inst can't be handled!");
00205   }
00206 
00207   bool isSentinel() const {
00208     return Inst == DenseMapInfo<Instruction *>::getEmptyKey() ||
00209            Inst == DenseMapInfo<Instruction *>::getTombstoneKey();
00210   }
00211 
00212   static bool canHandle(Instruction *Inst) {
00213     // Don't value number anything that returns void.
00214     if (Inst->getType()->isVoidTy())
00215       return false;
00216 
00217     CallInst *CI = dyn_cast<CallInst>(Inst);
00218     if (!CI || !CI->onlyReadsMemory())
00219       return false;
00220     return true;
00221   }
00222 };
00223 }
00224 
00225 namespace llvm {
00226 template <> struct DenseMapInfo<CallValue> {
00227   static inline CallValue getEmptyKey() {
00228     return DenseMapInfo<Instruction *>::getEmptyKey();
00229   }
00230   static inline CallValue getTombstoneKey() {
00231     return DenseMapInfo<Instruction *>::getTombstoneKey();
00232   }
00233   static unsigned getHashValue(CallValue Val);
00234   static bool isEqual(CallValue LHS, CallValue RHS);
00235 };
00236 }
00237 
00238 unsigned DenseMapInfo<CallValue>::getHashValue(CallValue Val) {
00239   Instruction *Inst = Val.Inst;
00240   // Hash all of the operands as pointers and mix in the opcode.
00241   return hash_combine(
00242       Inst->getOpcode(),
00243       hash_combine_range(Inst->value_op_begin(), Inst->value_op_end()));
00244 }
00245 
00246 bool DenseMapInfo<CallValue>::isEqual(CallValue LHS, CallValue RHS) {
00247   Instruction *LHSI = LHS.Inst, *RHSI = RHS.Inst;
00248   if (LHS.isSentinel() || RHS.isSentinel())
00249     return LHSI == RHSI;
00250   return LHSI->isIdenticalTo(RHSI);
00251 }
00252 
00253 //===----------------------------------------------------------------------===//
00254 // EarlyCSE implementation
00255 //===----------------------------------------------------------------------===//
00256 
00257 namespace {
00258 /// \brief A simple and fast domtree-based CSE pass.
00259 ///
00260 /// This pass does a simple depth-first walk over the dominator tree,
00261 /// eliminating trivially redundant instructions and using instsimplify to
00262 /// canonicalize things as it goes. It is intended to be fast and catch obvious
00263 /// cases so that instcombine and other passes are more effective. It is
00264 /// expected that a later pass of GVN will catch the interesting/hard cases.
00265 class EarlyCSE {
00266 public:
00267   const TargetLibraryInfo &TLI;
00268   const TargetTransformInfo &TTI;
00269   DominatorTree &DT;
00270   AssumptionCache &AC;
00271   typedef RecyclingAllocator<
00272       BumpPtrAllocator, ScopedHashTableVal<SimpleValue, Value *>> AllocatorTy;
00273   typedef ScopedHashTable<SimpleValue, Value *, DenseMapInfo<SimpleValue>,
00274                           AllocatorTy> ScopedHTType;
00275 
00276   /// \brief A scoped hash table of the current values of all of our simple
00277   /// scalar expressions.
00278   ///
00279   /// As we walk down the domtree, we look to see if instructions are in this:
00280   /// if so, we replace them with what we find, otherwise we insert them so
00281   /// that dominated values can succeed in their lookup.
00282   ScopedHTType AvailableValues;
00283 
00284   /// A scoped hash table of the current values of previously encounted memory
00285   /// locations.
00286   ///
00287   /// This allows us to get efficient access to dominating loads or stores when
00288   /// we have a fully redundant load.  In addition to the most recent load, we
00289   /// keep track of a generation count of the read, which is compared against
00290   /// the current generation count.  The current generation count is incremented
00291   /// after every possibly writing memory operation, which ensures that we only
00292   /// CSE loads with other loads that have no intervening store.  Ordering
00293   /// events (such as fences or atomic instructions) increment the generation
00294   /// count as well; essentially, we model these as writes to all possible
00295   /// locations.  Note that atomic and/or volatile loads and stores can be
00296   /// present the table; it is the responsibility of the consumer to inspect
00297   /// the atomicity/volatility if needed.
00298   struct LoadValue {
00299     Value *Data;
00300     unsigned Generation;
00301     int MatchingId;
00302     bool IsAtomic;
00303     LoadValue()
00304       : Data(nullptr), Generation(0), MatchingId(-1), IsAtomic(false) {}
00305     LoadValue(Value *Data, unsigned Generation, unsigned MatchingId,
00306               bool IsAtomic)
00307       : Data(Data), Generation(Generation), MatchingId(MatchingId),
00308         IsAtomic(IsAtomic) {}
00309   };
00310   typedef RecyclingAllocator<BumpPtrAllocator,
00311                              ScopedHashTableVal<Value *, LoadValue>>
00312       LoadMapAllocator;
00313   typedef ScopedHashTable<Value *, LoadValue, DenseMapInfo<Value *>,
00314                           LoadMapAllocator> LoadHTType;
00315   LoadHTType AvailableLoads;
00316 
00317   /// \brief A scoped hash table of the current values of read-only call
00318   /// values.
00319   ///
00320   /// It uses the same generation count as loads.
00321   typedef ScopedHashTable<CallValue, std::pair<Value *, unsigned>> CallHTType;
00322   CallHTType AvailableCalls;
00323 
00324   /// \brief This is the current generation of the memory value.
00325   unsigned CurrentGeneration;
00326 
00327   /// \brief Set up the EarlyCSE runner for a particular function.
00328   EarlyCSE(const TargetLibraryInfo &TLI, const TargetTransformInfo &TTI,
00329            DominatorTree &DT, AssumptionCache &AC)
00330       : TLI(TLI), TTI(TTI), DT(DT), AC(AC), CurrentGeneration(0) {}
00331 
00332   bool run();
00333 
00334 private:
00335   // Almost a POD, but needs to call the constructors for the scoped hash
00336   // tables so that a new scope gets pushed on. These are RAII so that the
00337   // scope gets popped when the NodeScope is destroyed.
00338   class NodeScope {
00339   public:
00340     NodeScope(ScopedHTType &AvailableValues, LoadHTType &AvailableLoads,
00341               CallHTType &AvailableCalls)
00342         : Scope(AvailableValues), LoadScope(AvailableLoads),
00343           CallScope(AvailableCalls) {}
00344 
00345   private:
00346     NodeScope(const NodeScope &) = delete;
00347     void operator=(const NodeScope &) = delete;
00348 
00349     ScopedHTType::ScopeTy Scope;
00350     LoadHTType::ScopeTy LoadScope;
00351     CallHTType::ScopeTy CallScope;
00352   };
00353 
00354   // Contains all the needed information to create a stack for doing a depth
00355   // first tranversal of the tree. This includes scopes for values, loads, and
00356   // calls as well as the generation. There is a child iterator so that the
00357   // children do not need to be store spearately.
00358   class StackNode {
00359   public:
00360     StackNode(ScopedHTType &AvailableValues, LoadHTType &AvailableLoads,
00361               CallHTType &AvailableCalls, unsigned cg, DomTreeNode *n,
00362               DomTreeNode::iterator child, DomTreeNode::iterator end)
00363         : CurrentGeneration(cg), ChildGeneration(cg), Node(n), ChildIter(child),
00364           EndIter(end), Scopes(AvailableValues, AvailableLoads, AvailableCalls),
00365           Processed(false) {}
00366 
00367     // Accessors.
00368     unsigned currentGeneration() { return CurrentGeneration; }
00369     unsigned childGeneration() { return ChildGeneration; }
00370     void childGeneration(unsigned generation) { ChildGeneration = generation; }
00371     DomTreeNode *node() { return Node; }
00372     DomTreeNode::iterator childIter() { return ChildIter; }
00373     DomTreeNode *nextChild() {
00374       DomTreeNode *child = *ChildIter;
00375       ++ChildIter;
00376       return child;
00377     }
00378     DomTreeNode::iterator end() { return EndIter; }
00379     bool isProcessed() { return Processed; }
00380     void process() { Processed = true; }
00381 
00382   private:
00383     StackNode(const StackNode &) = delete;
00384     void operator=(const StackNode &) = delete;
00385 
00386     // Members.
00387     unsigned CurrentGeneration;
00388     unsigned ChildGeneration;
00389     DomTreeNode *Node;
00390     DomTreeNode::iterator ChildIter;
00391     DomTreeNode::iterator EndIter;
00392     NodeScope Scopes;
00393     bool Processed;
00394   };
00395 
00396   /// \brief Wrapper class to handle memory instructions, including loads,
00397   /// stores and intrinsic loads and stores defined by the target.
00398   class ParseMemoryInst {
00399   public:
00400     ParseMemoryInst(Instruction *Inst, const TargetTransformInfo &TTI)
00401       : IsTargetMemInst(false), Inst(Inst) {
00402       if (IntrinsicInst *II = dyn_cast<IntrinsicInst>(Inst))
00403         if (TTI.getTgtMemIntrinsic(II, Info) && Info.NumMemRefs == 1)
00404           IsTargetMemInst = true;
00405     }
00406     bool isLoad() const {
00407       if (IsTargetMemInst) return Info.ReadMem;
00408       return isa<LoadInst>(Inst);
00409     }
00410     bool isStore() const {
00411       if (IsTargetMemInst) return Info.WriteMem;
00412       return isa<StoreInst>(Inst);
00413     }
00414     bool isAtomic() const {
00415       if (IsTargetMemInst) {
00416         assert(Info.IsSimple && "need to refine IsSimple in TTI");
00417         return false;
00418       }
00419       return Inst->isAtomic();
00420     }
00421     bool isUnordered() const {
00422       if (IsTargetMemInst) {
00423         assert(Info.IsSimple && "need to refine IsSimple in TTI");
00424         return true;
00425       }
00426       if (LoadInst *LI = dyn_cast<LoadInst>(Inst)) {
00427         return LI->isUnordered();
00428       } else if (StoreInst *SI = dyn_cast<StoreInst>(Inst)) {
00429         return SI->isUnordered();
00430       }
00431       // Conservative answer
00432       return !Inst->isAtomic();
00433     }
00434 
00435     bool isVolatile() const {
00436       if (IsTargetMemInst) {
00437         assert(Info.IsSimple && "need to refine IsSimple in TTI");
00438         return false;
00439       }
00440       if (LoadInst *LI = dyn_cast<LoadInst>(Inst)) {
00441         return LI->isVolatile();
00442       } else if (StoreInst *SI = dyn_cast<StoreInst>(Inst)) {
00443         return SI->isVolatile();
00444       }
00445       // Conservative answer
00446       return true;
00447     }
00448 
00449     
00450     bool isMatchingMemLoc(const ParseMemoryInst &Inst) const {
00451       return (getPointerOperand() == Inst.getPointerOperand() &&
00452               getMatchingId() == Inst.getMatchingId());
00453     }
00454     bool isValid() const { return getPointerOperand() != nullptr; }
00455 
00456     // For regular (non-intrinsic) loads/stores, this is set to -1. For
00457     // intrinsic loads/stores, the id is retrieved from the corresponding
00458     // field in the MemIntrinsicInfo structure.  That field contains
00459     // non-negative values only.
00460     int getMatchingId() const {
00461       if (IsTargetMemInst) return Info.MatchingId;
00462       return -1;
00463     }
00464     Value *getPointerOperand() const {
00465       if (IsTargetMemInst) return Info.PtrVal;
00466       if (LoadInst *LI = dyn_cast<LoadInst>(Inst)) {
00467         return LI->getPointerOperand();
00468       } else if (StoreInst *SI = dyn_cast<StoreInst>(Inst)) {
00469         return SI->getPointerOperand();
00470       }
00471       return nullptr;
00472     }
00473     bool mayReadFromMemory() const {
00474       if (IsTargetMemInst) return Info.ReadMem;
00475       return Inst->mayReadFromMemory();
00476     }
00477     bool mayWriteToMemory() const {
00478       if (IsTargetMemInst) return Info.WriteMem;
00479       return Inst->mayWriteToMemory();
00480     }
00481 
00482   private:
00483     bool IsTargetMemInst;
00484     MemIntrinsicInfo Info;
00485     Instruction *Inst;
00486   };
00487 
00488   bool processNode(DomTreeNode *Node);
00489 
00490   Value *getOrCreateResult(Value *Inst, Type *ExpectedType) const {
00491     if (LoadInst *LI = dyn_cast<LoadInst>(Inst))
00492       return LI;
00493     else if (StoreInst *SI = dyn_cast<StoreInst>(Inst))
00494       return SI->getValueOperand();
00495     assert(isa<IntrinsicInst>(Inst) && "Instruction not supported");
00496     return TTI.getOrCreateResultFromMemIntrinsic(cast<IntrinsicInst>(Inst),
00497                                                  ExpectedType);
00498   }
00499 };
00500 }
00501 
00502 bool EarlyCSE::processNode(DomTreeNode *Node) {
00503   BasicBlock *BB = Node->getBlock();
00504 
00505   // If this block has a single predecessor, then the predecessor is the parent
00506   // of the domtree node and all of the live out memory values are still current
00507   // in this block.  If this block has multiple predecessors, then they could
00508   // have invalidated the live-out memory values of our parent value.  For now,
00509   // just be conservative and invalidate memory if this block has multiple
00510   // predecessors.
00511   if (!BB->getSinglePredecessor())
00512     ++CurrentGeneration;
00513 
00514   // If this node has a single predecessor which ends in a conditional branch,
00515   // we can infer the value of the branch condition given that we took this
00516   // path.  We need the single predeccesor to ensure there's not another path
00517   // which reaches this block where the condition might hold a different
00518   // value.  Since we're adding this to the scoped hash table (like any other
00519   // def), it will have been popped if we encounter a future merge block.
00520   if (BasicBlock *Pred = BB->getSinglePredecessor())
00521     if (auto *BI = dyn_cast<BranchInst>(Pred->getTerminator()))
00522       if (BI->isConditional())
00523         if (auto *CondInst = dyn_cast<Instruction>(BI->getCondition()))
00524           if (SimpleValue::canHandle(CondInst)) {
00525             assert(BI->getSuccessor(0) == BB || BI->getSuccessor(1) == BB);
00526             auto *ConditionalConstant = (BI->getSuccessor(0) == BB) ?
00527               ConstantInt::getTrue(BB->getContext()) :
00528               ConstantInt::getFalse(BB->getContext());
00529             AvailableValues.insert(CondInst, ConditionalConstant);
00530             DEBUG(dbgs() << "EarlyCSE CVP: Add conditional value for '"
00531                   << CondInst->getName() << "' as " << *ConditionalConstant
00532                   << " in " << BB->getName() << "\n");
00533             // Replace all dominated uses with the known value
00534             replaceDominatedUsesWith(CondInst, ConditionalConstant, DT,
00535                                      BasicBlockEdge(Pred, BB));
00536           }
00537 
00538   /// LastStore - Keep track of the last non-volatile store that we saw... for
00539   /// as long as there in no instruction that reads memory.  If we see a store
00540   /// to the same location, we delete the dead store.  This zaps trivial dead
00541   /// stores which can occur in bitfield code among other things.
00542   Instruction *LastStore = nullptr;
00543 
00544   bool Changed = false;
00545   const DataLayout &DL = BB->getModule()->getDataLayout();
00546 
00547   // See if any instructions in the block can be eliminated.  If so, do it.  If
00548   // not, add them to AvailableValues.
00549   for (BasicBlock::iterator I = BB->begin(), E = BB->end(); I != E;) {
00550     Instruction *Inst = &*I++;
00551 
00552     // Dead instructions should just be removed.
00553     if (isInstructionTriviallyDead(Inst, &TLI)) {
00554       DEBUG(dbgs() << "EarlyCSE DCE: " << *Inst << '\n');
00555       Inst->eraseFromParent();
00556       Changed = true;
00557       ++NumSimplify;
00558       continue;
00559     }
00560 
00561     // Skip assume intrinsics, they don't really have side effects (although
00562     // they're marked as such to ensure preservation of control dependencies),
00563     // and this pass will not disturb any of the assumption's control
00564     // dependencies.
00565     if (match(Inst, m_Intrinsic<Intrinsic::assume>())) {
00566       DEBUG(dbgs() << "EarlyCSE skipping assumption: " << *Inst << '\n');
00567       continue;
00568     }
00569 
00570     // If the instruction can be simplified (e.g. X+0 = X) then replace it with
00571     // its simpler value.
00572     if (Value *V = SimplifyInstruction(Inst, DL, &TLI, &DT, &AC)) {
00573       DEBUG(dbgs() << "EarlyCSE Simplify: " << *Inst << "  to: " << *V << '\n');
00574       Inst->replaceAllUsesWith(V);
00575       Inst->eraseFromParent();
00576       Changed = true;
00577       ++NumSimplify;
00578       continue;
00579     }
00580 
00581     // If this is a simple instruction that we can value number, process it.
00582     if (SimpleValue::canHandle(Inst)) {
00583       // See if the instruction has an available value.  If so, use it.
00584       if (Value *V = AvailableValues.lookup(Inst)) {
00585         DEBUG(dbgs() << "EarlyCSE CSE: " << *Inst << "  to: " << *V << '\n');
00586         Inst->replaceAllUsesWith(V);
00587         Inst->eraseFromParent();
00588         Changed = true;
00589         ++NumCSE;
00590         continue;
00591       }
00592 
00593       // Otherwise, just remember that this value is available.
00594       AvailableValues.insert(Inst, Inst);
00595       continue;
00596     }
00597 
00598     ParseMemoryInst MemInst(Inst, TTI);
00599     // If this is a non-volatile load, process it.
00600     if (MemInst.isValid() && MemInst.isLoad()) {
00601       // (conservatively) we can't peak past the ordering implied by this
00602       // operation, but we can add this load to our set of available values
00603       if (MemInst.isVolatile() || !MemInst.isUnordered()) {
00604         LastStore = nullptr;
00605         ++CurrentGeneration;
00606       }
00607 
00608       // If we have an available version of this load, and if it is the right
00609       // generation, replace this instruction.
00610       LoadValue InVal = AvailableLoads.lookup(MemInst.getPointerOperand());
00611       if (InVal.Data != nullptr && InVal.Generation == CurrentGeneration &&
00612           InVal.MatchingId == MemInst.getMatchingId() &&
00613           // We don't yet handle removing loads with ordering of any kind.
00614           !MemInst.isVolatile() && MemInst.isUnordered() &&
00615           // We can't replace an atomic load with one which isn't also atomic.
00616           InVal.IsAtomic >= MemInst.isAtomic()) {
00617         Value *Op = getOrCreateResult(InVal.Data, Inst->getType());
00618         if (Op != nullptr) {
00619           DEBUG(dbgs() << "EarlyCSE CSE LOAD: " << *Inst
00620                        << "  to: " << *InVal.Data << '\n');
00621           if (!Inst->use_empty())
00622             Inst->replaceAllUsesWith(Op);
00623           Inst->eraseFromParent();
00624           Changed = true;
00625           ++NumCSELoad;
00626           continue;
00627         }
00628       }
00629 
00630       // Otherwise, remember that we have this instruction.
00631       AvailableLoads.insert(
00632           MemInst.getPointerOperand(),
00633           LoadValue(Inst, CurrentGeneration, MemInst.getMatchingId(),
00634                     MemInst.isAtomic()));
00635       LastStore = nullptr;
00636       continue;
00637     }
00638 
00639     // If this instruction may read from memory, forget LastStore.
00640     // Load/store intrinsics will indicate both a read and a write to
00641     // memory.  The target may override this (e.g. so that a store intrinsic
00642     // does not read  from memory, and thus will be treated the same as a
00643     // regular store for commoning purposes).
00644     if (Inst->mayReadFromMemory() &&
00645         !(MemInst.isValid() && !MemInst.mayReadFromMemory()))
00646       LastStore = nullptr;
00647 
00648     // If this is a read-only call, process it.
00649     if (CallValue::canHandle(Inst)) {
00650       // If we have an available version of this call, and if it is the right
00651       // generation, replace this instruction.
00652       std::pair<Value *, unsigned> InVal = AvailableCalls.lookup(Inst);
00653       if (InVal.first != nullptr && InVal.second == CurrentGeneration) {
00654         DEBUG(dbgs() << "EarlyCSE CSE CALL: " << *Inst
00655                      << "  to: " << *InVal.first << '\n');
00656         if (!Inst->use_empty())
00657           Inst->replaceAllUsesWith(InVal.first);
00658         Inst->eraseFromParent();
00659         Changed = true;
00660         ++NumCSECall;
00661         continue;
00662       }
00663 
00664       // Otherwise, remember that we have this instruction.
00665       AvailableCalls.insert(
00666           Inst, std::pair<Value *, unsigned>(Inst, CurrentGeneration));
00667       continue;
00668     }
00669 
00670     // A release fence requires that all stores complete before it, but does
00671     // not prevent the reordering of following loads 'before' the fence.  As a
00672     // result, we don't need to consider it as writing to memory and don't need
00673     // to advance the generation.  We do need to prevent DSE across the fence,
00674     // but that's handled above.
00675     if (FenceInst *FI = dyn_cast<FenceInst>(Inst))
00676       if (FI->getOrdering() == Release) {
00677         assert(Inst->mayReadFromMemory() && "relied on to prevent DSE above");
00678         continue;
00679       }
00680 
00681     // write back DSE - If we write back the same value we just loaded from
00682     // the same location and haven't passed any intervening writes or ordering
00683     // operations, we can remove the write.  The primary benefit is in allowing
00684     // the available load table to remain valid and value forward past where
00685     // the store originally was.
00686     if (MemInst.isValid() && MemInst.isStore()) {
00687       LoadValue InVal = AvailableLoads.lookup(MemInst.getPointerOperand());
00688       if (InVal.Data &&
00689           InVal.Data == getOrCreateResult(Inst, InVal.Data->getType()) &&
00690           InVal.Generation == CurrentGeneration &&
00691           InVal.MatchingId == MemInst.getMatchingId() &&
00692           // We don't yet handle removing stores with ordering of any kind.
00693           !MemInst.isVolatile() && MemInst.isUnordered()) {
00694         assert((!LastStore ||
00695                 ParseMemoryInst(LastStore, TTI).getPointerOperand() ==
00696                 MemInst.getPointerOperand()) &&
00697                "can't have an intervening store!");
00698         DEBUG(dbgs() << "EarlyCSE DSE (writeback): " << *Inst << '\n');
00699         Inst->eraseFromParent();
00700         Changed = true;
00701         ++NumDSE;
00702         // We can avoid incrementing the generation count since we were able
00703         // to eliminate this store.
00704         continue;
00705       }
00706     }
00707 
00708     // Okay, this isn't something we can CSE at all.  Check to see if it is
00709     // something that could modify memory.  If so, our available memory values
00710     // cannot be used so bump the generation count.
00711     if (Inst->mayWriteToMemory()) {
00712       ++CurrentGeneration;
00713 
00714       if (MemInst.isValid() && MemInst.isStore()) {
00715         // We do a trivial form of DSE if there are two stores to the same
00716         // location with no intervening loads.  Delete the earlier store.
00717         // At the moment, we don't remove ordered stores, but do remove
00718         // unordered atomic stores.  There's no special requirement (for
00719         // unordered atomics) about removing atomic stores only in favor of
00720         // other atomic stores since we we're going to execute the non-atomic
00721         // one anyway and the atomic one might never have become visible.
00722         if (LastStore) {
00723           ParseMemoryInst LastStoreMemInst(LastStore, TTI);
00724           assert(LastStoreMemInst.isUnordered() &&
00725                  !LastStoreMemInst.isVolatile() &&
00726                  "Violated invariant");
00727           if (LastStoreMemInst.isMatchingMemLoc(MemInst)) {
00728             DEBUG(dbgs() << "EarlyCSE DEAD STORE: " << *LastStore
00729                          << "  due to: " << *Inst << '\n');
00730             LastStore->eraseFromParent();
00731             Changed = true;
00732             ++NumDSE;
00733             LastStore = nullptr;
00734           }
00735           // fallthrough - we can exploit information about this store
00736         }
00737 
00738         // Okay, we just invalidated anything we knew about loaded values.  Try
00739         // to salvage *something* by remembering that the stored value is a live
00740         // version of the pointer.  It is safe to forward from volatile stores
00741         // to non-volatile loads, so we don't have to check for volatility of
00742         // the store.
00743         AvailableLoads.insert(
00744             MemInst.getPointerOperand(),
00745             LoadValue(Inst, CurrentGeneration, MemInst.getMatchingId(),
00746                       MemInst.isAtomic()));
00747 
00748         // Remember that this was the last unordered store we saw for DSE. We
00749         // don't yet handle DSE on ordered or volatile stores since we don't
00750         // have a good way to model the ordering requirement for following
00751         // passes  once the store is removed.  We could insert a fence, but
00752         // since fences are slightly stronger than stores in their ordering,
00753         // it's not clear this is a profitable transform. Another option would
00754         // be to merge the ordering with that of the post dominating store.
00755         if (MemInst.isUnordered() && !MemInst.isVolatile())
00756           LastStore = Inst;
00757         else
00758           LastStore = nullptr;
00759       }
00760     }
00761   }
00762 
00763   return Changed;
00764 }
00765 
00766 bool EarlyCSE::run() {
00767   // Note, deque is being used here because there is significant performance
00768   // gains over vector when the container becomes very large due to the
00769   // specific access patterns. For more information see the mailing list
00770   // discussion on this:
00771   // http://lists.llvm.org/pipermail/llvm-commits/Week-of-Mon-20120116/135228.html
00772   std::deque<StackNode *> nodesToProcess;
00773 
00774   bool Changed = false;
00775 
00776   // Process the root node.
00777   nodesToProcess.push_back(new StackNode(
00778       AvailableValues, AvailableLoads, AvailableCalls, CurrentGeneration,
00779       DT.getRootNode(), DT.getRootNode()->begin(), DT.getRootNode()->end()));
00780 
00781   // Save the current generation.
00782   unsigned LiveOutGeneration = CurrentGeneration;
00783 
00784   // Process the stack.
00785   while (!nodesToProcess.empty()) {
00786     // Grab the first item off the stack. Set the current generation, remove
00787     // the node from the stack, and process it.
00788     StackNode *NodeToProcess = nodesToProcess.back();
00789 
00790     // Initialize class members.
00791     CurrentGeneration = NodeToProcess->currentGeneration();
00792 
00793     // Check if the node needs to be processed.
00794     if (!NodeToProcess->isProcessed()) {
00795       // Process the node.
00796       Changed |= processNode(NodeToProcess->node());
00797       NodeToProcess->childGeneration(CurrentGeneration);
00798       NodeToProcess->process();
00799     } else if (NodeToProcess->childIter() != NodeToProcess->end()) {
00800       // Push the next child onto the stack.
00801       DomTreeNode *child = NodeToProcess->nextChild();
00802       nodesToProcess.push_back(
00803           new StackNode(AvailableValues, AvailableLoads, AvailableCalls,
00804                         NodeToProcess->childGeneration(), child, child->begin(),
00805                         child->end()));
00806     } else {
00807       // It has been processed, and there are no more children to process,
00808       // so delete it and pop it off the stack.
00809       delete NodeToProcess;
00810       nodesToProcess.pop_back();
00811     }
00812   } // while (!nodes...)
00813 
00814   // Reset the current generation.
00815   CurrentGeneration = LiveOutGeneration;
00816 
00817   return Changed;
00818 }
00819 
00820 PreservedAnalyses EarlyCSEPass::run(Function &F,
00821                                     AnalysisManager<Function> *AM) {
00822   auto &TLI = AM->getResult<TargetLibraryAnalysis>(F);
00823   auto &TTI = AM->getResult<TargetIRAnalysis>(F);
00824   auto &DT = AM->getResult<DominatorTreeAnalysis>(F);
00825   auto &AC = AM->getResult<AssumptionAnalysis>(F);
00826 
00827   EarlyCSE CSE(TLI, TTI, DT, AC);
00828 
00829   if (!CSE.run())
00830     return PreservedAnalyses::all();
00831 
00832   // CSE preserves the dominator tree because it doesn't mutate the CFG.
00833   // FIXME: Bundle this with other CFG-preservation.
00834   PreservedAnalyses PA;
00835   PA.preserve<DominatorTreeAnalysis>();
00836   return PA;
00837 }
00838 
00839 namespace {
00840 /// \brief A simple and fast domtree-based CSE pass.
00841 ///
00842 /// This pass does a simple depth-first walk over the dominator tree,
00843 /// eliminating trivially redundant instructions and using instsimplify to
00844 /// canonicalize things as it goes. It is intended to be fast and catch obvious
00845 /// cases so that instcombine and other passes are more effective. It is
00846 /// expected that a later pass of GVN will catch the interesting/hard cases.
00847 class EarlyCSELegacyPass : public FunctionPass {
00848 public:
00849   static char ID;
00850 
00851   EarlyCSELegacyPass() : FunctionPass(ID) {
00852     initializeEarlyCSELegacyPassPass(*PassRegistry::getPassRegistry());
00853   }
00854 
00855   bool runOnFunction(Function &F) override {
00856     if (skipOptnoneFunction(F))
00857       return false;
00858 
00859     auto &TLI = getAnalysis<TargetLibraryInfoWrapperPass>().getTLI();
00860     auto &TTI = getAnalysis<TargetTransformInfoWrapperPass>().getTTI(F);
00861     auto &DT = getAnalysis<DominatorTreeWrapperPass>().getDomTree();
00862     auto &AC = getAnalysis<AssumptionCacheTracker>().getAssumptionCache(F);
00863 
00864     EarlyCSE CSE(TLI, TTI, DT, AC);
00865 
00866     return CSE.run();
00867   }
00868 
00869   void getAnalysisUsage(AnalysisUsage &AU) const override {
00870     AU.addRequired<AssumptionCacheTracker>();
00871     AU.addRequired<DominatorTreeWrapperPass>();
00872     AU.addRequired<TargetLibraryInfoWrapperPass>();
00873     AU.addRequired<TargetTransformInfoWrapperPass>();
00874     AU.addPreserved<GlobalsAAWrapperPass>();
00875     AU.setPreservesCFG();
00876   }
00877 };
00878 }
00879 
00880 char EarlyCSELegacyPass::ID = 0;
00881 
00882 FunctionPass *llvm::createEarlyCSEPass() { return new EarlyCSELegacyPass(); }
00883 
00884 INITIALIZE_PASS_BEGIN(EarlyCSELegacyPass, "early-cse", "Early CSE", false,
00885                       false)
00886 INITIALIZE_PASS_DEPENDENCY(TargetTransformInfoWrapperPass)
00887 INITIALIZE_PASS_DEPENDENCY(AssumptionCacheTracker)
00888 INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
00889 INITIALIZE_PASS_DEPENDENCY(TargetLibraryInfoWrapperPass)
00890 INITIALIZE_PASS_END(EarlyCSELegacyPass, "early-cse", "Early CSE", false, false)