lib/Analysis/LoadValueNumbering.cpp

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