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