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