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/Target/TargetData.h"
  19 #include "llvm/Pass.h"
  20 #include "llvm/Type.h"
  21 #include "llvm/iMemory.h"
  22 #include "llvm/BasicBlock.h"
  23 #include "llvm/Support/CFG.h"
  24 #include <algorithm>
  25 #include <set>
  26
  27 namespace {
  28   // FIXME: This should not be a FunctionPass.
  29   struct LoadVN : public FunctionPass, public ValueNumbering {
  30
  31     /// Pass Implementation stuff.  This doesn't do any analysis.
  32     ///
  33     bool runOnFunction(Function &) { return false; }
  34
  35     /// getAnalysisUsage - Does not modify anything.  It uses Value Numbering
  36     /// and Alias Analysis.
  37     ///
  38     virtual void getAnalysisUsage(AnalysisUsage &AU) const;
  39
  40     /// getEqualNumberNodes - Return nodes with the same value number as the
  41     /// specified Value.  This fills in the argument vector with any equal
  42     /// values.
  43     ///
  44     virtual void getEqualNumberNodes(Value *V1,
  45                                      std::vector<Value*> &RetVals) const;
  46   private:
  47     /// haveEqualValueNumber - Given two load instructions, determine if they
  48     /// both produce the same value on every execution of the program, assuming
  49     /// that their source operands always give the same value.  This uses the
  50     /// AliasAnalysis implementation to invalidate loads when stores or function
  51     /// calls occur that could modify the value produced by the load.
  52     ///
  53     bool haveEqualValueNumber(LoadInst *LI, LoadInst *LI2, AliasAnalysis &AA,
  54                               DominatorSet &DomSetInfo) const;
  55     bool haveEqualValueNumber(LoadInst *LI, StoreInst *SI, AliasAnalysis &AA,
  56                               DominatorSet &DomSetInfo) const;
  57   };
  58
  59   // Register this pass...
  60   RegisterOpt<LoadVN> X("load-vn", "Load Value Numbering");
  61
  62   // Declare that we implement the ValueNumbering interface
  63   RegisterAnalysisGroup<ValueNumbering, LoadVN> Y;
  64 }
  65
  66
  67
  68 Pass *createLoadValueNumberingPass() { return new LoadVN(); }
  69
  70
  71 /// getAnalysisUsage - Does not modify anything.  It uses Value Numbering and
  72 /// Alias Analysis.
  73 ///
  74 void LoadVN::getAnalysisUsage(AnalysisUsage &AU) const {
  75   AU.setPreservesAll();
  76   AU.addRequired<AliasAnalysis>();
  77   AU.addRequired<ValueNumbering>();
  78   AU.addRequired<DominatorSet>();
  79   AU.addRequired<TargetData>();
  80 }
  81
  82 // getEqualNumberNodes - Return nodes with the same value number as the
  83 // specified Value.  This fills in the argument vector with any equal values.
  84 //
  85 void LoadVN::getEqualNumberNodes(Value *V,
  86                                  std::vector<Value*> &RetVals) const {
  87   // If the alias analysis has any must alias information to share with us, we
  88   // can definitely use it.
  89   if (isa<PointerType>(V->getType()))
  90     getAnalysis<AliasAnalysis>().getMustAliases(V, RetVals);
  91
  92   if (LoadInst *LI = dyn_cast<LoadInst>(V)) {
  93     // Volatile loads cannot be replaced with the value of other loads.
  94     if (LI->isVolatile())
  95       return getAnalysis<ValueNumbering>().getEqualNumberNodes(V, RetVals);
  96
  97     // If we have a load instruction, find all of the load and store
  98     // instructions that use the same source operand.  We implement this
  99     // recursively, because there could be a load of a load of a load that are
 100     // all identical.  We are guaranteed that this cannot be an infinite
 101     // recursion because load instructions would have to pass through a PHI node
 102     // in order for there to be a cycle.  The PHI node would be handled by the
 103     // else case here, breaking the infinite recursion.
 104     //
 105     std::vector<Value*> PointerSources;
 106     getEqualNumberNodes(LI->getOperand(0), PointerSources);
 107     PointerSources.push_back(LI->getOperand(0));
 108
 109     Function *F = LI->getParent()->getParent();
 110
 111     // Now that we know the set of equivalent source pointers for the load
 112     // instruction, look to see if there are any load or store candidates that
 113     // are identical.
 114     //
 115     std::vector<LoadInst*> CandidateLoads;
 116     std::vector<StoreInst*> CandidateStores;
 117
 118     while (!PointerSources.empty()) {
 119       Value *Source = PointerSources.back();
 120       PointerSources.pop_back();                // Get a source pointer...
 121
 122       for (Value::use_iterator UI = Source->use_begin(), UE = Source->use_end();
 123            UI != UE; ++UI)
 124         if (LoadInst *Cand = dyn_cast<LoadInst>(*UI)) {// Is a load of source?
 125           if (Cand->getParent()->getParent() == F &&   // In the same function?
 126               Cand != LI && !Cand->isVolatile())       // Not LI itself?
 127             CandidateLoads.push_back(Cand);     // Got one...
 128         } else if (StoreInst *Cand = dyn_cast<StoreInst>(*UI)) {
 129           if (Cand->getParent()->getParent() == F && !Cand->isVolatile() &&
 130               Cand->getOperand(1) == Source)  // It's a store THROUGH the ptr...
 131             CandidateStores.push_back(Cand);
 132         }
 133     }
 134
 135     // Remove duplicates from the CandidateLoads list because alias analysis
 136     // processing may be somewhat expensive and we don't want to do more work
 137     // than necessary.
 138     //
 139     unsigned OldSize = CandidateLoads.size();
 140     std::sort(CandidateLoads.begin(), CandidateLoads.end());
 141     CandidateLoads.erase(std::unique(CandidateLoads.begin(),
 142                                      CandidateLoads.end()),
 143                          CandidateLoads.end());
 144     // FIXME: REMOVE THIS SORTING AND UNIQUING IF IT CAN'T HAPPEN
 145     assert(CandidateLoads.size() == OldSize && "Shrunk the candloads list?");
 146
 147     // Get Alias Analysis...
 148     AliasAnalysis &AA = getAnalysis<AliasAnalysis>();
 149     DominatorSet &DomSetInfo = getAnalysis<DominatorSet>();
 150
 151     // Loop over all of the candidate loads.  If they are not invalidated by
 152     // stores or calls between execution of them and LI, then add them to
 153     // RetVals.
 154     for (unsigned i = 0, e = CandidateLoads.size(); i != e; ++i)
 155       if (haveEqualValueNumber(LI, CandidateLoads[i], AA, DomSetInfo))
 156         RetVals.push_back(CandidateLoads[i]);
 157     for (unsigned i = 0, e = CandidateStores.size(); i != e; ++i)
 158       if (haveEqualValueNumber(LI, CandidateStores[i], AA, DomSetInfo))
 159         RetVals.push_back(CandidateStores[i]->getOperand(0));
 160
 161   } else {
 162     assert(&getAnalysis<ValueNumbering>() != (ValueNumbering*)this &&
 163            "getAnalysis() returned this!");
 164
 165     // Not a load instruction?  Just chain to the base value numbering
 166     // implementation to satisfy the request...
 167     return getAnalysis<ValueNumbering>().getEqualNumberNodes(V, RetVals);
 168   }
 169 }
 170
 171 // CheckForInvalidatingInst - Return true if BB or any of the predecessors of BB
 172 // (until DestBB) contain an instruction that might invalidate Ptr.
 173 //
 174 static bool CheckForInvalidatingInst(BasicBlock *BB, BasicBlock *DestBB,
 175                                      Value *Ptr, unsigned Size,
 176                                      AliasAnalysis &AA,
 177                                      std::set<BasicBlock*> &VisitedSet) {
 178   // Found the termination point!
 179   if (BB == DestBB || VisitedSet.count(BB)) return false;
 180
 181   // Avoid infinite recursion!
 182   VisitedSet.insert(BB);
 183
 184   // Can this basic block modify Ptr?
 185   if (AA.canBasicBlockModify(*BB, Ptr, Size))
 186     return true;
 187
 188   // Check all of our predecessor blocks...
 189   for (pred_iterator PI = pred_begin(BB), PE = pred_end(BB); PI != PE; ++PI)
 190     if (CheckForInvalidatingInst(*PI, DestBB, Ptr, Size, AA, VisitedSet))
 191       return true;
 192
 193   // None of our predecessor blocks contain an invalidating instruction, and we
 194   // don't either!
 195   return false;
 196 }
 197
 198
 199 /// haveEqualValueNumber - Given two load instructions, determine if they both
 200 /// produce the same value on every execution of the program, assuming that
 201 /// their source operands always give the same value.  This uses the
 202 /// AliasAnalysis implementation to invalidate loads when stores or function
 203 /// calls occur that could modify the value produced by the load.
 204 ///
 205 bool LoadVN::haveEqualValueNumber(LoadInst *L1, LoadInst *L2,
 206                                   AliasAnalysis &AA,
 207                                   DominatorSet &DomSetInfo) const {
 208   // Figure out which load dominates the other one.  If neither dominates the
 209   // other we cannot eliminate them.
 210   //
 211   // FIXME: This could be enhanced to some cases with a shared dominator!
 212   //
 213   if (DomSetInfo.dominates(L2, L1))
 214     std::swap(L1, L2);   // Make L1 dominate L2
 215   else if (!DomSetInfo.dominates(L1, L2))
 216     return false;  // Neither instruction dominates the other one...
 217
 218   BasicBlock *BB1 = L1->getParent(), *BB2 = L2->getParent();
 219   Value *LoadAddress = L1->getOperand(0);
 220
 221   assert(L1->getType() == L2->getType() &&
 222          "How could the same source pointer return different types?");
 223
 224   // Find out how many bytes of memory are loaded by the load instruction...
 225   unsigned LoadSize = getAnalysis<TargetData>().getTypeSize(L1->getType());
 226
 227   // L1 now dominates L2.  Check to see if the intervening instructions between
 228   // the two loads include a store or call...
 229   //
 230   if (BB1 == BB2) {  // In same basic block?
 231     // In this degenerate case, no checking of global basic blocks has to occur
 232     // just check the instructions BETWEEN L1 & L2...
 233     //
 234     if (AA.canInstructionRangeModify(*L1, *L2, LoadAddress, LoadSize))
 235       return false;   // Cannot eliminate load
 236
 237     // No instructions invalidate the loads, they produce the same value!
 238     return true;
 239   } else {
 240     // Make sure that there are no store instructions between L1 and the end of
 241     // its basic block...
 242     //
 243     if (AA.canInstructionRangeModify(*L1, *BB1->getTerminator(), LoadAddress,
 244                                      LoadSize))
 245       return false;   // Cannot eliminate load
 246
 247     // Make sure that there are no store instructions between the start of BB2
 248     // and the second load instruction...
 249     //
 250     if (AA.canInstructionRangeModify(BB2->front(), *L2, LoadAddress, LoadSize))
 251       return false;   // Cannot eliminate load
 252
 253     // Do a depth first traversal of the inverse CFG starting at L2's block,
 254     // looking for L1's block.  The inverse CFG is made up of the predecessor
 255     // nodes of a block... so all of the edges in the graph are "backward".
 256     //
 257     std::set<BasicBlock*> VisitedSet;
 258     for (pred_iterator PI = pred_begin(BB2), PE = pred_end(BB2); PI != PE; ++PI)
 259       if (CheckForInvalidatingInst(*PI, BB1, LoadAddress, LoadSize, AA,
 260                                    VisitedSet))
 261         return false;
 262
 263     // If we passed all of these checks then we are sure that the two loads
 264     // produce the same value.
 265     return true;
 266   }
 267 }
 268
 269
 270 /// haveEqualValueNumber - Given a load instruction and a store instruction,
 271 /// determine if the stored value reaches the loaded value unambiguously on
 272 /// every execution of the program.  This uses the AliasAnalysis implementation
 273 /// to invalidate the stored value when stores or function calls occur that
 274 /// could modify the value produced by the load.
 275 ///
 276 bool LoadVN::haveEqualValueNumber(LoadInst *Load, StoreInst *Store,
 277                                   AliasAnalysis &AA,
 278                                   DominatorSet &DomSetInfo) const {
 279   // If the store does not dominate the load, we cannot do anything...
 280   if (!DomSetInfo.dominates(Store, Load))
 281     return false;
 282
 283   BasicBlock *BB1 = Store->getParent(), *BB2 = Load->getParent();
 284   Value *LoadAddress = Load->getOperand(0);
 285
 286   assert(LoadAddress->getType() == Store->getOperand(1)->getType() &&
 287          "How could the same source pointer return different types?");
 288
 289   // Find out how many bytes of memory are loaded by the load instruction...
 290   unsigned LoadSize = getAnalysis<TargetData>().getTypeSize(Load->getType());
 291
 292   // Compute a basic block iterator pointing to the instruction after the store.
 293   BasicBlock::iterator StoreIt = Store; ++StoreIt;
 294
 295   // Check to see if the intervening instructions between the two store and load
 296   // include a store or call...
 297   //
 298   if (BB1 == BB2) {  // In same basic block?
 299     // In this degenerate case, no checking of global basic blocks has to occur
 300     // just check the instructions BETWEEN Store & Load...
 301     //
 302     if (AA.canInstructionRangeModify(*StoreIt, *Load, LoadAddress, LoadSize))
 303       return false;   // Cannot eliminate load
 304
 305     // No instructions invalidate the stored value, they produce the same value!
 306     return true;
 307   } else {
 308     // Make sure that there are no store instructions between the Store and the
 309     // end of its basic block...
 310     //
 311     if (AA.canInstructionRangeModify(*StoreIt, *BB1->getTerminator(),
 312                                      LoadAddress, LoadSize))
 313       return false;   // Cannot eliminate load
 314
 315     // Make sure that there are no store instructions between the start of BB2
 316     // and the second load instruction...
 317     //
 318     if (AA.canInstructionRangeModify(BB2->front(), *Load, LoadAddress,LoadSize))
 319       return false;   // Cannot eliminate load
 320
 321     // Do a depth first traversal of the inverse CFG starting at L2's block,
 322     // looking for L1's block.  The inverse CFG is made up of the predecessor
 323     // nodes of a block... so all of the edges in the graph are "backward".
 324     //
 325     std::set<BasicBlock*> VisitedSet;
 326     for (pred_iterator PI = pred_begin(BB2), PE = pred_end(BB2); PI != PE; ++PI)
 327       if (CheckForInvalidatingInst(*PI, BB1, LoadAddress, LoadSize, AA,
 328                                    VisitedSet))
 329         return false;
 330
 331     // If we passed all of these checks then we are sure that the two loads
 332     // produce the same value.
 333     return true;
 334   }
 335 }