lib/Analysis/LoadValueNumbering.cpp

   1 //===- LoadValueNumbering.cpp - Load Value #'ing Implementation -*- C++ -*-===//
   2 //
   3 // This file implements a value numbering pass that value #'s load instructions.
   4 // To do this, it finds lexically identical load instructions, and uses alias
   5 // analysis to determine which loads are guaranteed to produce the same value.
   6 //
   7 // This pass builds off of another value numbering pass to implement value
   8 // numbering for non-load instructions.  It uses Alias Analysis so that it can
   9 // disambiguate the load instructions.  The more powerful these base analyses
  10 // are, the more powerful the resultant analysis will be.
  11 //
  12 //===----------------------------------------------------------------------===//
  13
  14 #include "llvm/Analysis/LoadValueNumbering.h"
  15 #include "llvm/Analysis/ValueNumbering.h"
  16 #include "llvm/Analysis/AliasAnalysis.h"
  17 #include "llvm/Analysis/Dominators.h"
  18 #include "llvm/Pass.h"
  19 #include "llvm/iMemory.h"
  20 #include "llvm/BasicBlock.h"
  21 #include "llvm/Support/CFG.h"
  22 #include <algorithm>
  23 #include <set>
  24
  25 namespace {
  26   // FIXME: This should not be a functionpass.
  27   struct LoadVN : public FunctionPass, public ValueNumbering {
  28
  29     /// Pass Implementation stuff.  This doesn't do any analysis.
  30     ///
  31     bool runOnFunction(Function &) { return false; }
  32
  33     /// getAnalysisUsage - Does not modify anything.  It uses Value Numbering
  34     /// and Alias Analysis.
  35     ///
  36     virtual void getAnalysisUsage(AnalysisUsage &AU) const;
  37
  38     /// getEqualNumberNodes - Return nodes with the same value number as the
  39     /// specified Value.  This fills in the argument vector with any equal
  40     /// values.
  41     ///
  42     virtual void getEqualNumberNodes(Value *V1,
  43                                      std::vector<Value*> &RetVals) const;
  44   private:
  45     /// haveEqualValueNumber - Given two load instructions, determine if they
  46     /// both produce the same value on every execution of the program, assuming
  47     /// that their source operands always give the same value.  This uses the
  48     /// AliasAnalysis implementation to invalidate loads when stores or function
  49     /// calls occur that could modify the value produced by the load.
  50     ///
  51     bool haveEqualValueNumber(LoadInst *LI, LoadInst *LI2, AliasAnalysis &AA,
  52                               DominatorSet &DomSetInfo) const;
  53   };
  54
  55   // Register this pass...
  56   RegisterOpt<LoadVN> X("load-vn", "Load Value Numbering");
  57
  58   // Declare that we implement the ValueNumbering interface
  59   RegisterAnalysisGroup<ValueNumbering, LoadVN> Y;
  60 }
  61
  62
  63
  64 Pass *createLoadValueNumberingPass() { return new LoadVN(); }
  65
  66
  67 /// getAnalysisUsage - Does not modify anything.  It uses Value Numbering and
  68 /// Alias Analysis.
  69 ///
  70 void LoadVN::getAnalysisUsage(AnalysisUsage &AU) const {
  71   AU.setPreservesAll();
  72   AU.addRequired<AliasAnalysis>();
  73   AU.addRequired<ValueNumbering>();
  74   AU.addRequired<DominatorSet>();
  75 }
  76
  77 // getEqualNumberNodes - Return nodes with the same value number as the
  78 // specified Value.  This fills in the argument vector with any equal values.
  79 //
  80 void LoadVN::getEqualNumberNodes(Value *V,
  81                                  std::vector<Value*> &RetVals) const {
  82
  83   if (LoadInst *LI = dyn_cast<LoadInst>(V)) {
  84     // If we have a load instruction find all of the load instructions that use
  85     // the same source operand.  We implement this recursively, because there
  86     // could be a load of a load of a load that are all identical.  We are
  87     // guaranteed that this cannot be an infinite recursion because load
  88     // instructions would have to pass through a PHI node in order for there to
  89     // be a cycle.  The PHI node would be handled by the else case here,
  90     // breaking the infinite recursion.
  91     //
  92     std::vector<Value*> PointerSources;
  93     getEqualNumberNodes(LI->getOperand(0), PointerSources);
  94     PointerSources.push_back(LI->getOperand(0));
  95
  96     Function *F = LI->getParent()->getParent();
  97
  98     // Now that we know the set of equivalent source pointers for the load
  99     // instruction, look to see if there are any load candiates that are
 100     // identical.
 101     //
 102     std::vector<LoadInst*> CandidateLoads;
 103     while (!PointerSources.empty()) {
 104       Value *Source = PointerSources.back();
 105       PointerSources.pop_back();                // Get a source pointer...
 106
 107       for (Value::use_iterator UI = Source->use_begin(), UE = Source->use_end();
 108            UI != UE; ++UI)
 109         if (LoadInst *Cand = dyn_cast<LoadInst>(*UI))  // Is a load of source?
 110           if (Cand->getParent()->getParent() == F &&   // In the same function?
 111               Cand != LI)                              // Not LI itself?
 112             CandidateLoads.push_back(Cand);     // Got one...
 113     }
 114
 115     // Remove duplicates from the CandidateLoads list because alias analysis
 116     // processing may be somewhat expensive and we don't want to do more work
 117     // than neccesary.
 118     //
 119     std::sort(CandidateLoads.begin(), CandidateLoads.end());
 120     CandidateLoads.erase(std::unique(CandidateLoads.begin(),
 121                                      CandidateLoads.end()),
 122                          CandidateLoads.end());
 123
 124     // Get Alias Analysis...
 125     AliasAnalysis &AA = getAnalysis<AliasAnalysis>();
 126     DominatorSet &DomSetInfo = getAnalysis<DominatorSet>();
 127
 128     // Loop over all of the candindate loads.  If they are not invalidated by
 129     // stores or calls between execution of them and LI, then add them to
 130     // RetVals.
 131     for (unsigned i = 0, e = CandidateLoads.size(); i != e; ++i)
 132       if (haveEqualValueNumber(LI, CandidateLoads[i], AA, DomSetInfo))
 133         RetVals.push_back(CandidateLoads[i]);
 134
 135   } else {
 136     // Make sure passmanager doesn't try to fulfill our request with ourself!
 137     assert(&getAnalysis<ValueNumbering>() != (ValueNumbering*)this &&
 138            "getAnalysis() returned this!");
 139
 140     // Not a load instruction?  Just chain to the base value numbering
 141     // implementation to satisfy the request...
 142     return getAnalysis<ValueNumbering>().getEqualNumberNodes(V, RetVals);
 143   }
 144 }
 145
 146 // CheckForInvalidatingInst - Return true if BB or any of the predecessors of BB
 147 // (until DestBB) contain an instruction that might invalidate Ptr.
 148 //
 149 static bool CheckForInvalidatingInst(BasicBlock *BB, BasicBlock *DestBB,
 150                                      Value *Ptr, AliasAnalysis &AA,
 151                                      std::set<BasicBlock*> &VisitedSet) {
 152   // Found the termination point!
 153   if (BB == DestBB || VisitedSet.count(BB)) return false;
 154
 155   // Avoid infinite recursion!
 156   VisitedSet.insert(BB);
 157
 158   // Can this basic block modify Ptr?
 159   if (AA.canBasicBlockModify(*BB, Ptr))
 160     return true;
 161
 162   // Check all of our predecessor blocks...
 163   for (pred_iterator PI = pred_begin(BB), PE = pred_end(BB); PI != PE; ++PI)
 164     if (CheckForInvalidatingInst(*PI, DestBB, Ptr, AA, VisitedSet))
 165       return true;
 166
 167   // None of our predecessor blocks contain an invalidating instruction, and we
 168   // don't either!
 169   return false;
 170 }
 171
 172
 173 /// haveEqualValueNumber - Given two load instructions, determine if they both
 174 /// produce the same value on every execution of the program, assuming that
 175 /// their source operands always give the same value.  This uses the
 176 /// AliasAnalysis implementation to invalidate loads when stores or function
 177 /// calls occur that could modify the value produced by the load.
 178 ///
 179 bool LoadVN::haveEqualValueNumber(LoadInst *L1, LoadInst *L2,
 180                                   AliasAnalysis &AA,
 181                                   DominatorSet &DomSetInfo) const {
 182   // Figure out which load dominates the other one.  If neither dominates the
 183   // other we cannot eliminate them.
 184   //
 185   // FIXME: This could be enhanced to some cases with a shared dominator!
 186   //
 187   if (DomSetInfo.dominates(L2, L1))
 188     std::swap(L1, L2);   // Make L1 dominate L2
 189   else if (!DomSetInfo.dominates(L1, L2))
 190     return false;  // Neither instruction dominates the other one...
 191
 192   BasicBlock *BB1 = L1->getParent(), *BB2 = L2->getParent();
 193   Value *LoadAddress = L1->getOperand(0);
 194
 195   // L1 now dominates L2.  Check to see if the intervening instructions between
 196   // the two loads include a store or call...
 197   //
 198   if (BB1 == BB2) {  // In same basic block?
 199     // In this degenerate case, no checking of global basic blocks has to occur
 200     // just check the instructions BETWEEN L1 & L2...
 201     //
 202     if (AA.canInstructionRangeModify(*L1, *L2, LoadAddress))
 203       return false;   // Cannot eliminate load
 204
 205     // No instructions invalidate the loads, they produce the same value!
 206     return true;
 207   } else {
 208     // Make sure that there are no store instructions between L1 and the end of
 209     // it's basic block...
 210     //
 211     if (AA.canInstructionRangeModify(*L1, *BB1->getTerminator(), LoadAddress))
 212       return false;   // Cannot eliminate load
 213
 214     // Make sure that there are no store instructions between the start of BB2
 215     // and the second load instruction...
 216     //
 217     if (AA.canInstructionRangeModify(BB2->front(), *L2, LoadAddress))
 218       return false;   // Cannot eliminate load
 219
 220     // Do a depth first traversal of the inverse CFG starting at L2's block,
 221     // looking for L1's block.  The inverse CFG is made up of the predecessor
 222     // nodes of a block... so all of the edges in the graph are "backward".
 223     //
 224     std::set<BasicBlock*> VisitedSet;
 225     for (pred_iterator PI = pred_begin(BB2), PE = pred_end(BB2); PI != PE; ++PI)
 226       if (CheckForInvalidatingInst(*PI, BB1, LoadAddress, AA, VisitedSet))
 227         return false;
 228
 229     // If we passed all of these checks then we are sure that the two loads
 230     // produce the same value.
 231     return true;
 232   }
 233 }