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 *PointerSource = LI->getOperand(0);
 288
 289   BasicBlock *LoadBB = LI->getParent();
 290   Function *F = LoadBB->getParent();
 291
 292   // Now that we know the set of equivalent source pointers for the load
 293   // instruction, look to see if there are any load or store candidates that are
 294   // identical.
 295   //
 296   std::map<BasicBlock*, std::vector<LoadInst*> >  CandidateLoads;
 297   std::map<BasicBlock*, std::vector<StoreInst*> > CandidateStores;
 298
 299   for (Value::use_iterator UI = PointerSource->use_begin(),
 300          UE = PointerSource->use_end(); UI != UE; ++UI)
 301     if (LoadInst *Cand = dyn_cast<LoadInst>(*UI)) {// Is a load of source?
 302       if (Cand->getParent()->getParent() == F &&   // In the same function?
 303           Cand != LI && !Cand->isVolatile())       // Not LI itself?
 304         CandidateLoads[Cand->getParent()].push_back(Cand);     // Got one...
 305     } else if (StoreInst *Cand = dyn_cast<StoreInst>(*UI)) {
 306       if (Cand->getParent()->getParent() == F && !Cand->isVolatile() &&
 307           Cand->getOperand(1) == PointerSource) // It's a store THROUGH the ptr.
 308         CandidateStores[Cand->getParent()].push_back(Cand);
 309     }
 310
 311   // Get alias analysis & dominators.
 312   AliasAnalysis &AA = getAnalysis<AliasAnalysis>();
 313   DominatorSet &DomSetInfo = getAnalysis<DominatorSet>();
 314   Value *LoadPtr = LI->getOperand(0);
 315   // Find out how many bytes of memory are loaded by the load instruction...
 316   unsigned LoadSize = getAnalysis<TargetData>().getTypeSize(LI->getType());
 317
 318   // Find all of the candidate loads and stores that are in the same block as
 319   // the defining instruction.
 320   std::set<Instruction*> Instrs;
 321   Instrs.insert(CandidateLoads[LoadBB].begin(), CandidateLoads[LoadBB].end());
 322   CandidateLoads.erase(LoadBB);
 323   Instrs.insert(CandidateStores[LoadBB].begin(), CandidateStores[LoadBB].end());
 324   CandidateStores.erase(LoadBB);
 325
 326   // Figure out if the load is invalidated from the entry of the block it is in
 327   // until the actual instruction.  This scans the block backwards from LI.  If
 328   // we see any candidate load or store instructions, then we know that the
 329   // candidates have the same value # as LI.
 330   bool LoadInvalidatedInBBBefore = false;
 331   for (BasicBlock::iterator I = LI; I != LoadBB->begin(); ) {
 332     --I;
 333     // If this instruction is a candidate load before LI, we know there are no
 334     // invalidating instructions between it and LI, so they have the same value
 335     // number.
 336     if (isa<LoadInst>(I) && Instrs.count(I)) {
 337       RetVals.push_back(I);
 338       Instrs.erase(I);
 339     } else if (AllocationInst *AI = dyn_cast<AllocationInst>(I)) {
 340       // If we run into an allocation of the value being loaded, then the
 341       // contents are not initialized.
 342       if ((Value*)AI == PointerSource) {
 343         LoadInvalidatedInBBBefore = true;
 344         RetVals.push_back(UndefValue::get(LI->getType()));
 345         break;
 346       }
 347     }
 348
 349     if (AA.getModRefInfo(I, LoadPtr, LoadSize) & AliasAnalysis::Mod) {
 350       // If the invalidating instruction is a store, and its in our candidate
 351       // set, then we can do store-load forwarding: the load has the same value
 352       // # as the stored value.
 353       if (isa<StoreInst>(I) && Instrs.count(I)) {
 354         Instrs.erase(I);
 355         RetVals.push_back(I->getOperand(0));
 356       }
 357
 358       LoadInvalidatedInBBBefore = true;
 359       break;
 360     }
 361   }
 362
 363   // Figure out if the load is invalidated between the load and the exit of the
 364   // block it is defined in.  While we are scanning the current basic block, if
 365   // we see any candidate loads, then we know they have the same value # as LI.
 366   //
 367   bool LoadInvalidatedInBBAfter = false;
 368   for (BasicBlock::iterator I = LI->getNext(); I != LoadBB->end(); ++I) {
 369     // If this instruction is a load, then this instruction returns the same
 370     // value as LI.
 371     if (isa<LoadInst>(I) && Instrs.count(I)) {
 372       RetVals.push_back(I);
 373       Instrs.erase(I);
 374     }
 375
 376     if (AA.getModRefInfo(I, LoadPtr, LoadSize) & AliasAnalysis::Mod) {
 377       LoadInvalidatedInBBAfter = true;
 378       break;
 379     }
 380   }
 381
 382   // If there is anything left in the Instrs set, it could not possibly equal
 383   // LI.
 384   Instrs.clear();
 385
 386   // TransparentBlocks - For each basic block the load/store is alive across,
 387   // figure out if the pointer is invalidated or not.  If it is invalidated, the
 388   // boolean is set to false, if it's not it is set to true.  If we don't know
 389   // yet, the entry is not in the map.
 390   std::map<BasicBlock*, bool> TransparentBlocks;
 391
 392   // Loop over all of the basic blocks that also load the value.  If the value
 393   // is live across the CFG from the source to destination blocks, and if the
 394   // value is not invalidated in either the source or destination blocks, add it
 395   // to the equivalence sets.
 396   for (std::map<BasicBlock*, std::vector<LoadInst*> >::iterator
 397          I = CandidateLoads.begin(), E = CandidateLoads.end(); I != E; ++I) {
 398     bool CantEqual = false;
 399
 400     // Right now we only can handle cases where one load dominates the other.
 401     // FIXME: generalize this!
 402     BasicBlock *BB1 = I->first, *BB2 = LoadBB;
 403     if (DomSetInfo.dominates(BB1, BB2)) {
 404       // The other load dominates LI.  If the loaded value is killed entering
 405       // the LoadBB block, we know the load is not live.
 406       if (LoadInvalidatedInBBBefore)
 407         CantEqual = true;
 408     } else if (DomSetInfo.dominates(BB2, BB1)) {
 409       std::swap(BB1, BB2);          // Canonicalize
 410       // LI dominates the other load.  If the loaded value is killed exiting
 411       // the LoadBB block, we know the load is not live.
 412       if (LoadInvalidatedInBBAfter)
 413         CantEqual = true;
 414     } else {
 415       // None of these loads can VN the same.
 416       CantEqual = true;
 417     }
 418
 419     if (!CantEqual) {
 420       // Ok, at this point, we know that BB1 dominates BB2, and that there is
 421       // nothing in the LI block that kills the loaded value.  Check to see if
 422       // the value is live across the CFG.
 423       std::set<BasicBlock*> Visited;
 424       for (pred_iterator PI = pred_begin(BB2), E = pred_end(BB2); PI!=E; ++PI)
 425         if (!isPathTransparentTo(*PI, BB1, LoadPtr, LoadSize, AA,
 426                                  Visited, TransparentBlocks)) {
 427           // None of these loads can VN the same.
 428           CantEqual = true;
 429           break;
 430         }
 431     }
 432
 433     // If the loads can equal so far, scan the basic block that contains the
 434     // loads under consideration to see if they are invalidated in the block.
 435     // For any loads that are not invalidated, add them to the equivalence
 436     // set!
 437     if (!CantEqual) {
 438       Instrs.insert(I->second.begin(), I->second.end());
 439       if (BB1 == LoadBB) {
 440         // If LI dominates the block in question, check to see if any of the
 441         // loads in this block are invalidated before they are reached.
 442         for (BasicBlock::iterator BBI = I->first->begin(); ; ++BBI) {
 443           if (isa<LoadInst>(BBI) && Instrs.count(BBI)) {
 444             // The load is in the set!
 445             RetVals.push_back(BBI);
 446             Instrs.erase(BBI);
 447             if (Instrs.empty()) break;
 448           } else if (AA.getModRefInfo(BBI, LoadPtr, LoadSize)
 449                              & AliasAnalysis::Mod) {
 450             // If there is a modifying instruction, nothing below it will value
 451             // # the same.
 452             break;
 453           }
 454         }
 455       } else {
 456         // If the block dominates LI, make sure that the loads in the block are
 457         // not invalidated before the block ends.
 458         BasicBlock::iterator BBI = I->first->end();
 459         while (1) {
 460           --BBI;
 461           if (isa<LoadInst>(BBI) && Instrs.count(BBI)) {
 462             // The load is in the set!
 463             RetVals.push_back(BBI);
 464             Instrs.erase(BBI);
 465             if (Instrs.empty()) break;
 466           } else if (AA.getModRefInfo(BBI, LoadPtr, LoadSize)
 467                              & AliasAnalysis::Mod) {
 468             // If there is a modifying instruction, nothing above it will value
 469             // # the same.
 470             break;
 471           }
 472         }
 473       }
 474
 475       Instrs.clear();
 476     }
 477   }
 478
 479   // Handle candidate stores.  If the loaded location is clobbered on entrance
 480   // to the LoadBB, no store outside of the LoadBB can value number equal, so
 481   // quick exit.
 482   if (LoadInvalidatedInBBBefore)
 483     return;
 484
 485   for (std::map<BasicBlock*, std::vector<StoreInst*> >::iterator
 486          I = CandidateStores.begin(), E = CandidateStores.end(); I != E; ++I)
 487     if (DomSetInfo.dominates(I->first, LoadBB)) {
 488       // Check to see if the path from the store to the load is transparent
 489       // w.r.t. the memory location.
 490       bool CantEqual = false;
 491       std::set<BasicBlock*> Visited;
 492       for (pred_iterator PI = pred_begin(LoadBB), E = pred_end(LoadBB);
 493            PI != E; ++PI)
 494         if (!isPathTransparentTo(*PI, I->first, LoadPtr, LoadSize, AA,
 495                                  Visited, TransparentBlocks)) {
 496           // None of these stores can VN the same.
 497           CantEqual = true;
 498           break;
 499         }
 500       Visited.clear();
 501       if (!CantEqual) {
 502         // Okay, the path from the store block to the load block is clear, and
 503         // we know that there are no invalidating instructions from the start
 504         // of the load block to the load itself.  Now we just scan the store
 505         // block.
 506
 507         BasicBlock::iterator BBI = I->first->end();
 508         while (1) {
 509           assert(BBI != I->first->begin() &&
 510                  "There is a store in this block of the pointer, but the store"
 511                  " doesn't mod the address being stored to??  Must be a bug in"
 512                  " the alias analysis implementation!");
 513           --BBI;
 514           if (AA.getModRefInfo(BBI, LoadPtr, LoadSize) & AliasAnalysis::Mod) {
 515             // If the invalidating instruction is one of the candidates,
 516             // then it provides the value the load loads.
 517             if (StoreInst *SI = dyn_cast<StoreInst>(BBI))
 518               if (std::find(I->second.begin(), I->second.end(), SI) !=
 519                   I->second.end())
 520                 RetVals.push_back(SI->getOperand(0));
 521             break;
 522           }
 523         }
 524       }
 525     }
 526 }