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 numbers load and call
  11 // instructions.  To do this, it finds lexically identical load instructions,
  12 // and uses alias analysis to determine which loads are guaranteed to produce
  13 // the same value.  To value number call instructions, it looks for calls to
  14 // functions that do not write to memory which do not have intervening
  15 // instructions that clobber the memory that is read from.
  16 //
  17 // This pass builds off of another value numbering pass to implement value
  18 // numbering for non-load and non-call instructions.  It uses Alias Analysis so
  19 // that it can disambiguate the load instructions.  The more powerful these base
  20 // analyses are, the more powerful the resultant value numbering will be.
  21 //
  22 //===----------------------------------------------------------------------===//
  23
  24 #include "llvm/Analysis/LoadValueNumbering.h"
  25 #include "llvm/Constants.h"
  26 #include "llvm/Function.h"
  27 #include "llvm/Instructions.h"
  28 #include "llvm/Pass.h"
  29 #include "llvm/Type.h"
  30 #include "llvm/Analysis/ValueNumbering.h"
  31 #include "llvm/Analysis/AliasAnalysis.h"
  32 #include "llvm/Analysis/Dominators.h"
  33 #include "llvm/Support/CFG.h"
  34 #include "llvm/Target/TargetData.h"
  35 #include <set>
  36 #include <algorithm>
  37 using namespace llvm;
  38
  39 namespace {
  40   // FIXME: This should not be a FunctionPass.
  41   struct LoadVN : public FunctionPass, public ValueNumbering {
  42
  43     /// Pass Implementation stuff.  This doesn't do any analysis.
  44     ///
  45     bool runOnFunction(Function &) { return false; }
  46
  47     /// getAnalysisUsage - Does not modify anything.  It uses Value Numbering
  48     /// and Alias Analysis.
  49     ///
  50     virtual void getAnalysisUsage(AnalysisUsage &AU) const;
  51
  52     /// getEqualNumberNodes - Return nodes with the same value number as the
  53     /// specified Value.  This fills in the argument vector with any equal
  54     /// values.
  55     ///
  56     virtual void getEqualNumberNodes(Value *V1,
  57                                      std::vector<Value*> &RetVals) const;
  58
  59     /// deleteValue - This method should be called whenever an LLVM Value is
  60     /// deleted from the program, for example when an instruction is found to be
  61     /// redundant and is eliminated.
  62     ///
  63     virtual void deleteValue(Value *V) {
  64       getAnalysis<AliasAnalysis>().deleteValue(V);
  65     }
  66
  67     /// copyValue - This method should be used whenever a preexisting value in
  68     /// the program is copied or cloned, introducing a new value.  Note that
  69     /// analysis implementations should tolerate clients that use this method to
  70     /// introduce the same value multiple times: if the analysis already knows
  71     /// about a value, it should ignore the request.
  72     ///
  73     virtual void copyValue(Value *From, Value *To) {
  74       getAnalysis<AliasAnalysis>().copyValue(From, To);
  75     }
  76
  77     /// getCallEqualNumberNodes - Given a call instruction, find other calls
  78     /// that have the same value number.
  79     void getCallEqualNumberNodes(CallInst *CI,
  80                                  std::vector<Value*> &RetVals) const;
  81   };
  82
  83   // Register this pass...
  84   RegisterOpt<LoadVN> X("load-vn", "Load Value Numbering");
  85
  86   // Declare that we implement the ValueNumbering interface
  87   RegisterAnalysisGroup<ValueNumbering, LoadVN> Y;
  88 }
  89
  90 FunctionPass *llvm::createLoadValueNumberingPass() { return new LoadVN(); }
  91
  92
  93 /// getAnalysisUsage - Does not modify anything.  It uses Value Numbering and
  94 /// Alias Analysis.
  95 ///
  96 void LoadVN::getAnalysisUsage(AnalysisUsage &AU) const {
  97   AU.setPreservesAll();
  98   AU.addRequired<AliasAnalysis>();
  99   AU.addRequired<ValueNumbering>();
 100   AU.addRequired<DominatorSet>();
 101   AU.addRequired<TargetData>();
 102 }
 103
 104 static bool isPathTransparentTo(BasicBlock *CurBlock, BasicBlock *Dom,
 105                                 Value *Ptr, unsigned Size, AliasAnalysis &AA,
 106                                 std::set<BasicBlock*> &Visited,
 107                                 std::map<BasicBlock*, bool> &TransparentBlocks){
 108   // If we have already checked out this path, or if we reached our destination,
 109   // stop searching, returning success.
 110   if (CurBlock == Dom || !Visited.insert(CurBlock).second)
 111     return true;
 112
 113   // Check whether this block is known transparent or not.
 114   std::map<BasicBlock*, bool>::iterator TBI =
 115     TransparentBlocks.lower_bound(CurBlock);
 116
 117   if (TBI == TransparentBlocks.end() || TBI->first != CurBlock) {
 118     // If this basic block can modify the memory location, then the path is not
 119     // transparent!
 120     if (AA.canBasicBlockModify(*CurBlock, Ptr, Size)) {
 121       TransparentBlocks.insert(TBI, std::make_pair(CurBlock, false));
 122       return false;
 123     }
 124     TransparentBlocks.insert(TBI, std::make_pair(CurBlock, true));
 125   } else if (!TBI->second)
 126     // This block is known non-transparent, so that path can't be either.
 127     return false;
 128
 129   // The current block is known to be transparent.  The entire path is
 130   // transparent if all of the predecessors paths to the parent is also
 131   // transparent to the memory location.
 132   for (pred_iterator PI = pred_begin(CurBlock), E = pred_end(CurBlock);
 133        PI != E; ++PI)
 134     if (!isPathTransparentTo(*PI, Dom, Ptr, Size, AA, Visited,
 135                              TransparentBlocks))
 136       return false;
 137   return true;
 138 }
 139
 140 /// getCallEqualNumberNodes - Given a call instruction, find other calls that
 141 /// have the same value number.
 142 void LoadVN::getCallEqualNumberNodes(CallInst *CI,
 143                                      std::vector<Value*> &RetVals) const {
 144   Function *CF = CI->getCalledFunction();
 145   if (CF == 0) return;  // Indirect call.
 146   AliasAnalysis &AA = getAnalysis<AliasAnalysis>();
 147   AliasAnalysis::ModRefBehavior MRB = AA.getModRefBehavior(CF, CI);
 148   if (MRB != AliasAnalysis::DoesNotAccessMemory &&
 149       MRB != AliasAnalysis::OnlyReadsMemory)
 150     return;  // Nothing we can do for now.
 151
 152   // Scan all of the arguments of the function, looking for one that is not
 153   // global.  In particular, we would prefer to have an argument or instruction
 154   // operand to chase the def-use chains of.
 155   Value *Op = CF;
 156   for (unsigned i = 1, e = CI->getNumOperands(); i != e; ++i)
 157     if (isa<Argument>(CI->getOperand(i)) ||
 158         isa<Instruction>(CI->getOperand(i))) {
 159       Op = CI->getOperand(i);
 160       break;
 161     }
 162
 163   // Identify all lexically identical calls in this function.
 164   std::vector<CallInst*> IdenticalCalls;
 165
 166   Function *CIFunc = CI->getParent()->getParent();
 167   for (Value::use_iterator UI = Op->use_begin(), E = Op->use_end(); UI != E;
 168        ++UI)
 169     if (CallInst *C = dyn_cast<CallInst>(*UI))
 170       if (C->getNumOperands() == CI->getNumOperands() &&
 171           C->getOperand(0) == CI->getOperand(0) &&
 172           C->getParent()->getParent() == CIFunc && C != CI) {
 173         bool AllOperandsEqual = true;
 174         for (unsigned i = 1, e = CI->getNumOperands(); i != e; ++i)
 175           if (C->getOperand(i) != CI->getOperand(i)) {
 176             AllOperandsEqual = false;
 177             break;
 178           }
 179
 180         if (AllOperandsEqual)
 181           IdenticalCalls.push_back(C);
 182       }
 183
 184   if (IdenticalCalls.empty()) return;
 185
 186   // Eliminate duplicates, which could occur if we chose a value that is passed
 187   // into a call site multiple times.
 188   std::sort(IdenticalCalls.begin(), IdenticalCalls.end());
 189   IdenticalCalls.erase(std::unique(IdenticalCalls.begin(),IdenticalCalls.end()),
 190                        IdenticalCalls.end());
 191
 192   // If the call reads memory, we must make sure that there are no stores
 193   // between the calls in question.
 194   //
 195   // FIXME: This should use mod/ref information.  What we really care about it
 196   // whether an intervening instruction could modify memory that is read, not
 197   // ANY memory.
 198   //
 199   if (MRB == AliasAnalysis::OnlyReadsMemory) {
 200     DominatorSet &DomSetInfo = getAnalysis<DominatorSet>();
 201     BasicBlock *CIBB = CI->getParent();
 202     for (unsigned i = 0; i != IdenticalCalls.size(); ++i) {
 203       CallInst *C = IdenticalCalls[i];
 204       bool CantEqual = false;
 205
 206       if (DomSetInfo.dominates(CIBB, C->getParent())) {
 207         // FIXME: we currently only handle the case where both calls are in the
 208         // same basic block.
 209         if (CIBB != C->getParent()) {
 210           CantEqual = true;
 211         } else {
 212           Instruction *First = CI, *Second = C;
 213           if (!DomSetInfo.dominates(CI, C))
 214             std::swap(First, Second);
 215
 216           // Scan the instructions between the calls, checking for stores or
 217           // calls to dangerous functions.
 218           BasicBlock::iterator I = First;
 219           for (++First; I != BasicBlock::iterator(Second); ++I) {
 220             if (isa<StoreInst>(I)) {
 221               // FIXME: We could use mod/ref information to make this much
 222               // better!
 223               CantEqual = true;
 224               break;
 225             } else if (CallInst *CI = dyn_cast<CallInst>(I)) {
 226               if (CI->getCalledFunction() == 0 ||
 227                   !AA.onlyReadsMemory(CI->getCalledFunction())) {
 228                 CantEqual = true;
 229                 break;
 230               }
 231             } else if (I->mayWriteToMemory()) {
 232               CantEqual = true;
 233               break;
 234             }
 235           }
 236         }
 237
 238       } else if (DomSetInfo.dominates(C->getParent(), CIBB)) {
 239         // FIXME: We could implement this, but we don't for now.
 240         CantEqual = true;
 241       } else {
 242         // FIXME: if one doesn't dominate the other, we can't tell yet.
 243         CantEqual = true;
 244       }
 245
 246
 247       if (CantEqual) {
 248         // This call does not produce the same value as the one in the query.
 249         std::swap(IdenticalCalls[i--], IdenticalCalls.back());
 250         IdenticalCalls.pop_back();
 251       }
 252     }
 253   }
 254
 255   // Any calls that are identical and not destroyed will produce equal values!
 256   for (unsigned i = 0, e = IdenticalCalls.size(); i != e; ++i)
 257     RetVals.push_back(IdenticalCalls[i]);
 258 }
 259
 260 // getEqualNumberNodes - Return nodes with the same value number as the
 261 // specified Value.  This fills in the argument vector with any equal values.
 262 //
 263 void LoadVN::getEqualNumberNodes(Value *V,
 264                                  std::vector<Value*> &RetVals) const {
 265   // If the alias analysis has any must alias information to share with us, we
 266   // can definitely use it.
 267   if (isa<PointerType>(V->getType()))
 268     getAnalysis<AliasAnalysis>().getMustAliases(V, RetVals);
 269
 270   if (!isa<LoadInst>(V)) {
 271     if (CallInst *CI = dyn_cast<CallInst>(V))
 272       getCallEqualNumberNodes(CI, RetVals);
 273
 274     // Not a load instruction?  Just chain to the base value numbering
 275     // implementation to satisfy the request...
 276     assert(&getAnalysis<ValueNumbering>() != (ValueNumbering*)this &&
 277            "getAnalysis() returned this!");
 278
 279     return getAnalysis<ValueNumbering>().getEqualNumberNodes(V, RetVals);
 280   }
 281
 282   // Volatile loads cannot be replaced with the value of other loads.
 283   LoadInst *LI = cast<LoadInst>(V);
 284   if (LI->isVolatile())
 285     return getAnalysis<ValueNumbering>().getEqualNumberNodes(V, RetVals);
 286
 287   Value *LoadPtr = LI->getOperand(0);
 288   BasicBlock *LoadBB = LI->getParent();
 289   Function *F = LoadBB->getParent();
 290
 291   // Find out how many bytes of memory are loaded by the load instruction...
 292   unsigned LoadSize = getAnalysis<TargetData>().getTypeSize(LI->getType());
 293   AliasAnalysis &AA = getAnalysis<AliasAnalysis>();
 294
 295   // Figure out if the load is invalidated from the entry of the block it is in
 296   // until the actual instruction.  This scans the block backwards from LI.  If
 297   // we see any candidate load or store instructions, then we know that the
 298   // candidates have the same value # as LI.
 299   bool LoadInvalidatedInBBBefore = false;
 300   for (BasicBlock::iterator I = LI; I != LoadBB->begin(); ) {
 301     --I;
 302     // If this instruction is a candidate load before LI, we know there are no
 303     // invalidating instructions between it and LI, so they have the same value
 304     // number.
 305     if (isa<LoadInst>(I) && cast<LoadInst>(I)->getOperand(0) == LoadPtr) {
 306       RetVals.push_back(I);
 307     } else if (I == LoadPtr) {
 308       // If we run into an allocation of the value being loaded, then the
 309       // contents are not initialized.
 310       if (isa<AllocationInst>(I))
 311         RetVals.push_back(UndefValue::get(LI->getType()));
 312
 313       // Otherwise, since this is the definition of what we are loading, this
 314       // loaded value cannot occur before this block.
 315       LoadInvalidatedInBBBefore = true;
 316       break;
 317     }
 318
 319     if (AA.getModRefInfo(I, LoadPtr, LoadSize) & AliasAnalysis::Mod) {
 320       // If the invalidating instruction is a store, and its in our candidate
 321       // set, then we can do store-load forwarding: the load has the same value
 322       // # as the stored value.
 323       if (isa<StoreInst>(I) && I->getOperand(1) == LoadPtr)
 324         RetVals.push_back(I->getOperand(0));
 325
 326       LoadInvalidatedInBBBefore = true;
 327       break;
 328     }
 329   }
 330
 331   // Figure out if the load is invalidated between the load and the exit of the
 332   // block it is defined in.  While we are scanning the current basic block, if
 333   // we see any candidate loads, then we know they have the same value # as LI.
 334   //
 335   bool LoadInvalidatedInBBAfter = false;
 336   for (BasicBlock::iterator I = LI->getNext(); I != LoadBB->end(); ++I) {
 337     // If this instruction is a load, then this instruction returns the same
 338     // value as LI.
 339     if (isa<LoadInst>(I) && cast<LoadInst>(I)->getOperand(0) == LoadPtr)
 340       RetVals.push_back(I);
 341
 342     if (AA.getModRefInfo(I, LoadPtr, LoadSize) & AliasAnalysis::Mod) {
 343       LoadInvalidatedInBBAfter = true;
 344       break;
 345     }
 346   }
 347
 348   // If the pointer is clobbered on entry and on exit to the function, there is
 349   // no need to do any global analysis at all.
 350   if (LoadInvalidatedInBBBefore && LoadInvalidatedInBBAfter)
 351     return;
 352
 353   // Now that we know the set of equivalent source pointers for the load
 354   // instruction, look to see if there are any load or store candidates that are
 355   // identical.
 356   //
 357   std::map<BasicBlock*, std::vector<LoadInst*> >  CandidateLoads;
 358   std::map<BasicBlock*, std::vector<StoreInst*> > CandidateStores;
 359
 360   for (Value::use_iterator UI = LoadPtr->use_begin(), UE = LoadPtr->use_end();
 361        UI != UE; ++UI)
 362     if (LoadInst *Cand = dyn_cast<LoadInst>(*UI)) {// Is a load of source?
 363       if (Cand->getParent()->getParent() == F &&   // In the same function?
 364           // Not in LI's block?
 365           Cand->getParent() != LoadBB && !Cand->isVolatile())
 366         CandidateLoads[Cand->getParent()].push_back(Cand);     // Got one...
 367     } else if (StoreInst *Cand = dyn_cast<StoreInst>(*UI)) {
 368       if (Cand->getParent()->getParent() == F && !Cand->isVolatile() &&
 369           Cand->getParent() != LoadBB &&
 370           Cand->getOperand(1) == LoadPtr) // It's a store THROUGH the ptr.
 371         CandidateStores[Cand->getParent()].push_back(Cand);
 372     }
 373
 374   // Get dominators.
 375   DominatorSet &DomSetInfo = getAnalysis<DominatorSet>();
 376
 377   // Find all of the candidate loads and stores that are in the same block as
 378   // the defining instruction.
 379   std::set<Instruction*> Instrs;
 380   Instrs.insert(CandidateLoads[LoadBB].begin(), CandidateLoads[LoadBB].end());
 381   CandidateLoads.erase(LoadBB);
 382   Instrs.insert(CandidateStores[LoadBB].begin(), CandidateStores[LoadBB].end());
 383   CandidateStores.erase(LoadBB);
 384
 385   // If there is anything left in the Instrs set, it could not possibly equal
 386   // LI.
 387   Instrs.clear();
 388
 389   // TransparentBlocks - For each basic block the load/store is alive across,
 390   // figure out if the pointer is invalidated or not.  If it is invalidated, the
 391   // boolean is set to false, if it's not it is set to true.  If we don't know
 392   // yet, the entry is not in the map.
 393   std::map<BasicBlock*, bool> TransparentBlocks;
 394
 395   // Loop over all of the basic blocks that also load the value.  If the value
 396   // is live across the CFG from the source to destination blocks, and if the
 397   // value is not invalidated in either the source or destination blocks, add it
 398   // to the equivalence sets.
 399   for (std::map<BasicBlock*, std::vector<LoadInst*> >::iterator
 400          I = CandidateLoads.begin(), E = CandidateLoads.end(); I != E; ++I) {
 401     bool CantEqual = false;
 402
 403     // Right now we only can handle cases where one load dominates the other.
 404     // FIXME: generalize this!
 405     BasicBlock *BB1 = I->first, *BB2 = LoadBB;
 406     if (DomSetInfo.dominates(BB1, BB2)) {
 407       // The other load dominates LI.  If the loaded value is killed entering
 408       // the LoadBB block, we know the load is not live.
 409       if (LoadInvalidatedInBBBefore)
 410         CantEqual = true;
 411     } else if (DomSetInfo.dominates(BB2, BB1)) {
 412       std::swap(BB1, BB2);          // Canonicalize
 413       // LI dominates the other load.  If the loaded value is killed exiting
 414       // the LoadBB block, we know the load is not live.
 415       if (LoadInvalidatedInBBAfter)
 416         CantEqual = true;
 417     } else {
 418       // None of these loads can VN the same.
 419       CantEqual = true;
 420     }
 421
 422     if (!CantEqual) {
 423       // Ok, at this point, we know that BB1 dominates BB2, and that there is
 424       // nothing in the LI block that kills the loaded value.  Check to see if
 425       // the value is live across the CFG.
 426       std::set<BasicBlock*> Visited;
 427       for (pred_iterator PI = pred_begin(BB2), E = pred_end(BB2); PI!=E; ++PI)
 428         if (!isPathTransparentTo(*PI, BB1, LoadPtr, LoadSize, AA,
 429                                  Visited, TransparentBlocks)) {
 430           // None of these loads can VN the same.
 431           CantEqual = true;
 432           break;
 433         }
 434     }
 435
 436     // If the loads can equal so far, scan the basic block that contains the
 437     // loads under consideration to see if they are invalidated in the block.
 438     // For any loads that are not invalidated, add them to the equivalence
 439     // set!
 440     if (!CantEqual) {
 441       Instrs.insert(I->second.begin(), I->second.end());
 442       if (BB1 == LoadBB) {
 443         // If LI dominates the block in question, check to see if any of the
 444         // loads in this block are invalidated before they are reached.
 445         for (BasicBlock::iterator BBI = I->first->begin(); ; ++BBI) {
 446           if (isa<LoadInst>(BBI) && Instrs.count(BBI)) {
 447             // The load is in the set!
 448             RetVals.push_back(BBI);
 449             Instrs.erase(BBI);
 450             if (Instrs.empty()) break;
 451           } else if (AA.getModRefInfo(BBI, LoadPtr, LoadSize)
 452                              & AliasAnalysis::Mod) {
 453             // If there is a modifying instruction, nothing below it will value
 454             // # the same.
 455             break;
 456           }
 457         }
 458       } else {
 459         // If the block dominates LI, make sure that the loads in the block are
 460         // not invalidated before the block ends.
 461         BasicBlock::iterator BBI = I->first->end();
 462         while (1) {
 463           --BBI;
 464           if (isa<LoadInst>(BBI) && Instrs.count(BBI)) {
 465             // The load is in the set!
 466             RetVals.push_back(BBI);
 467             Instrs.erase(BBI);
 468             if (Instrs.empty()) break;
 469           } else if (AA.getModRefInfo(BBI, LoadPtr, LoadSize)
 470                              & AliasAnalysis::Mod) {
 471             // If there is a modifying instruction, nothing above it will value
 472             // # the same.
 473             break;
 474           }
 475         }
 476       }
 477
 478       Instrs.clear();
 479     }
 480   }
 481
 482   // Handle candidate stores.  If the loaded location is clobbered on entrance
 483   // to the LoadBB, no store outside of the LoadBB can value number equal, so
 484   // quick exit.
 485   if (LoadInvalidatedInBBBefore)
 486     return;
 487
 488   for (std::map<BasicBlock*, std::vector<StoreInst*> >::iterator
 489          I = CandidateStores.begin(), E = CandidateStores.end(); I != E; ++I)
 490     if (DomSetInfo.dominates(I->first, LoadBB)) {
 491       // Check to see if the path from the store to the load is transparent
 492       // w.r.t. the memory location.
 493       bool CantEqual = false;
 494       std::set<BasicBlock*> Visited;
 495       for (pred_iterator PI = pred_begin(LoadBB), E = pred_end(LoadBB);
 496            PI != E; ++PI)
 497         if (!isPathTransparentTo(*PI, I->first, LoadPtr, LoadSize, AA,
 498                                  Visited, TransparentBlocks)) {
 499           // None of these stores can VN the same.
 500           CantEqual = true;
 501           break;
 502         }
 503       Visited.clear();
 504       if (!CantEqual) {
 505         // Okay, the path from the store block to the load block is clear, and
 506         // we know that there are no invalidating instructions from the start
 507         // of the load block to the load itself.  Now we just scan the store
 508         // block.
 509
 510         BasicBlock::iterator BBI = I->first->end();
 511         while (1) {
 512           assert(BBI != I->first->begin() &&
 513                  "There is a store in this block of the pointer, but the store"
 514                  " doesn't mod the address being stored to??  Must be a bug in"
 515                  " the alias analysis implementation!");
 516           --BBI;
 517           if (AA.getModRefInfo(BBI, LoadPtr, LoadSize) & AliasAnalysis::Mod) {
 518             // If the invalidating instruction is one of the candidates,
 519             // then it provides the value the load loads.
 520             if (StoreInst *SI = dyn_cast<StoreInst>(BBI))
 521               if (std::find(I->second.begin(), I->second.end(), SI) !=
 522                   I->second.end())
 523                 RetVals.push_back(SI->getOperand(0));
 524             break;
 525           }
 526         }
 527       }
 528     }
 529 }