1 //===- LoadValueNumbering.cpp - Load Value #'ing Implementation -*- C++ -*-===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
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.
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.
22 //===----------------------------------------------------------------------===//
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/Support/Compiler.h"
35 #include "llvm/Target/TargetData.h"
41 // FIXME: This should not be a FunctionPass.
42 struct VISIBILITY_HIDDEN LoadVN : public FunctionPass, public ValueNumbering {
43 static char ID; // Class identification, replacement for typeinfo
44 LoadVN() : FunctionPass((intptr_t)&ID) {}
46 /// isAnalysis - Return true if this pass is implementing an analysis pass.
47 virtual bool isAnalysis() const { return true; }
49 /// Pass Implementation stuff. This doesn't do any analysis.
51 bool runOnFunction(Function &) { return false; }
53 /// getAnalysisUsage - Does not modify anything. It uses Value Numbering
54 /// and Alias Analysis.
56 virtual void getAnalysisUsage(AnalysisUsage &AU) const;
58 /// getEqualNumberNodes - Return nodes with the same value number as the
59 /// specified Value. This fills in the argument vector with any equal
62 virtual void getEqualNumberNodes(Value *V1,
63 std::vector<Value*> &RetVals) const;
65 /// deleteValue - This method should be called whenever an LLVM Value is
66 /// deleted from the program, for example when an instruction is found to be
67 /// redundant and is eliminated.
69 virtual void deleteValue(Value *V) {
70 getAnalysis<AliasAnalysis>().deleteValue(V);
73 /// copyValue - This method should be used whenever a preexisting value in
74 /// the program is copied or cloned, introducing a new value. Note that
75 /// analysis implementations should tolerate clients that use this method to
76 /// introduce the same value multiple times: if the analysis already knows
77 /// about a value, it should ignore the request.
79 virtual void copyValue(Value *From, Value *To) {
80 getAnalysis<AliasAnalysis>().copyValue(From, To);
83 /// getCallEqualNumberNodes - Given a call instruction, find other calls
84 /// that have the same value number.
85 void getCallEqualNumberNodes(CallInst *CI,
86 std::vector<Value*> &RetVals) const;
90 // Register this pass...
91 RegisterPass<LoadVN> X("load-vn", "Load Value Numbering");
93 // Declare that we implement the ValueNumbering interface
94 RegisterAnalysisGroup<ValueNumbering> Y(X);
97 FunctionPass *llvm::createLoadValueNumberingPass() { return new LoadVN(); }
100 /// getAnalysisUsage - Does not modify anything. It uses Value Numbering and
103 void LoadVN::getAnalysisUsage(AnalysisUsage &AU) const {
104 AU.setPreservesAll();
105 AU.addRequiredTransitive<AliasAnalysis>();
106 AU.addRequired<ValueNumbering>();
107 AU.addRequiredTransitive<DominatorTree>();
108 AU.addRequiredTransitive<TargetData>();
111 static bool isPathTransparentTo(BasicBlock *CurBlock, BasicBlock *Dom,
112 Value *Ptr, unsigned Size, AliasAnalysis &AA,
113 std::set<BasicBlock*> &Visited,
114 std::map<BasicBlock*, bool> &TransparentBlocks){
115 // If we have already checked out this path, or if we reached our destination,
116 // stop searching, returning success.
117 if (CurBlock == Dom || !Visited.insert(CurBlock).second)
120 // Check whether this block is known transparent or not.
121 std::map<BasicBlock*, bool>::iterator TBI =
122 TransparentBlocks.lower_bound(CurBlock);
124 if (TBI == TransparentBlocks.end() || TBI->first != CurBlock) {
125 // If this basic block can modify the memory location, then the path is not
127 if (AA.canBasicBlockModify(*CurBlock, Ptr, Size)) {
128 TransparentBlocks.insert(TBI, std::make_pair(CurBlock, false));
131 TransparentBlocks.insert(TBI, std::make_pair(CurBlock, true));
132 } else if (!TBI->second)
133 // This block is known non-transparent, so that path can't be either.
136 // The current block is known to be transparent. The entire path is
137 // transparent if all of the predecessors paths to the parent is also
138 // transparent to the memory location.
139 for (pred_iterator PI = pred_begin(CurBlock), E = pred_end(CurBlock);
141 if (!isPathTransparentTo(*PI, Dom, Ptr, Size, AA, Visited,
147 /// getCallEqualNumberNodes - Given a call instruction, find other calls that
148 /// have the same value number.
149 void LoadVN::getCallEqualNumberNodes(CallInst *CI,
150 std::vector<Value*> &RetVals) const {
151 Function *CF = CI->getCalledFunction();
152 if (CF == 0) return; // Indirect call.
153 AliasAnalysis &AA = getAnalysis<AliasAnalysis>();
154 AliasAnalysis::ModRefBehavior MRB = AA.getModRefBehavior(CI);
155 if (MRB != AliasAnalysis::DoesNotAccessMemory &&
156 MRB != AliasAnalysis::OnlyReadsMemory)
157 return; // Nothing we can do for now.
159 // Scan all of the arguments of the function, looking for one that is not
160 // global. In particular, we would prefer to have an argument or instruction
161 // operand to chase the def-use chains of.
163 for (unsigned i = 1, e = CI->getNumOperands(); i != e; ++i)
164 if (isa<Argument>(CI->getOperand(i)) ||
165 isa<Instruction>(CI->getOperand(i))) {
166 Op = CI->getOperand(i);
170 // Identify all lexically identical calls in this function.
171 std::vector<CallInst*> IdenticalCalls;
173 Function *CIFunc = CI->getParent()->getParent();
174 for (Value::use_iterator UI = Op->use_begin(), E = Op->use_end(); UI != E;
176 if (CallInst *C = dyn_cast<CallInst>(*UI))
177 if (C->getNumOperands() == CI->getNumOperands() &&
178 C->getOperand(0) == CI->getOperand(0) &&
179 C->getParent()->getParent() == CIFunc && C != CI) {
180 bool AllOperandsEqual = true;
181 for (unsigned i = 1, e = CI->getNumOperands(); i != e; ++i)
182 if (C->getOperand(i) != CI->getOperand(i)) {
183 AllOperandsEqual = false;
187 if (AllOperandsEqual)
188 IdenticalCalls.push_back(C);
191 if (IdenticalCalls.empty()) return;
193 // Eliminate duplicates, which could occur if we chose a value that is passed
194 // into a call site multiple times.
195 std::sort(IdenticalCalls.begin(), IdenticalCalls.end());
196 IdenticalCalls.erase(std::unique(IdenticalCalls.begin(),IdenticalCalls.end()),
197 IdenticalCalls.end());
199 // If the call reads memory, we must make sure that there are no stores
200 // between the calls in question.
202 // FIXME: This should use mod/ref information. What we really care about it
203 // whether an intervening instruction could modify memory that is read, not
206 if (MRB == AliasAnalysis::OnlyReadsMemory) {
207 DominatorTree &DT = getAnalysis<DominatorTree>();
208 BasicBlock *CIBB = CI->getParent();
209 for (unsigned i = 0; i != IdenticalCalls.size(); ++i) {
210 CallInst *C = IdenticalCalls[i];
211 bool CantEqual = false;
213 if (DT.dominates(CIBB, C->getParent())) {
214 // FIXME: we currently only handle the case where both calls are in the
216 if (CIBB != C->getParent()) {
219 Instruction *First = CI, *Second = C;
220 if (!DT.dominates(CI, C))
221 std::swap(First, Second);
223 // Scan the instructions between the calls, checking for stores or
224 // calls to dangerous functions.
225 BasicBlock::iterator I = First;
226 for (++First; I != BasicBlock::iterator(Second); ++I) {
227 if (isa<StoreInst>(I)) {
228 // FIXME: We could use mod/ref information to make this much
232 } else if (CallInst *CI = dyn_cast<CallInst>(I)) {
233 if (!AA.onlyReadsMemory(CI)) {
237 } else if (I->mayWriteToMemory()) {
244 } else if (DT.dominates(C->getParent(), CIBB)) {
245 // FIXME: We could implement this, but we don't for now.
248 // FIXME: if one doesn't dominate the other, we can't tell yet.
254 // This call does not produce the same value as the one in the query.
255 std::swap(IdenticalCalls[i--], IdenticalCalls.back());
256 IdenticalCalls.pop_back();
261 // Any calls that are identical and not destroyed will produce equal values!
262 for (unsigned i = 0, e = IdenticalCalls.size(); i != e; ++i)
263 RetVals.push_back(IdenticalCalls[i]);
266 // getEqualNumberNodes - Return nodes with the same value number as the
267 // specified Value. This fills in the argument vector with any equal values.
269 void LoadVN::getEqualNumberNodes(Value *V,
270 std::vector<Value*> &RetVals) const {
271 // If the alias analysis has any must alias information to share with us, we
272 // can definitely use it.
273 if (isa<PointerType>(V->getType()))
274 getAnalysis<AliasAnalysis>().getMustAliases(V, RetVals);
276 if (!isa<LoadInst>(V)) {
277 if (CallInst *CI = dyn_cast<CallInst>(V))
278 getCallEqualNumberNodes(CI, RetVals);
280 // Not a load instruction? Just chain to the base value numbering
281 // implementation to satisfy the request...
282 assert(&getAnalysis<ValueNumbering>() != (ValueNumbering*)this &&
283 "getAnalysis() returned this!");
285 return getAnalysis<ValueNumbering>().getEqualNumberNodes(V, RetVals);
288 // Volatile loads cannot be replaced with the value of other loads.
289 LoadInst *LI = cast<LoadInst>(V);
290 if (LI->isVolatile())
291 return getAnalysis<ValueNumbering>().getEqualNumberNodes(V, RetVals);
293 Value *LoadPtr = LI->getOperand(0);
294 BasicBlock *LoadBB = LI->getParent();
295 Function *F = LoadBB->getParent();
297 // Find out how many bytes of memory are loaded by the load instruction...
298 unsigned LoadSize = getAnalysis<TargetData>().getTypeStoreSize(LI->getType());
299 AliasAnalysis &AA = getAnalysis<AliasAnalysis>();
301 // Figure out if the load is invalidated from the entry of the block it is in
302 // until the actual instruction. This scans the block backwards from LI. If
303 // we see any candidate load or store instructions, then we know that the
304 // candidates have the same value # as LI.
305 bool LoadInvalidatedInBBBefore = false;
306 for (BasicBlock::iterator I = LI; I != LoadBB->begin(); ) {
309 // If we run into an allocation of the value being loaded, then the
310 // contents are not initialized.
311 if (isa<AllocationInst>(I))
312 RetVals.push_back(UndefValue::get(LI->getType()));
314 // Otherwise, since this is the definition of what we are loading, this
315 // loaded value cannot occur before this block.
316 LoadInvalidatedInBBBefore = true;
318 } else if (LoadInst *LI = dyn_cast<LoadInst>(I)) {
319 // If this instruction is a candidate load before LI, we know there are no
320 // invalidating instructions between it and LI, so they have the same
322 if (LI->getOperand(0) == LoadPtr && !LI->isVolatile())
323 RetVals.push_back(I);
326 if (AA.getModRefInfo(I, LoadPtr, LoadSize) & AliasAnalysis::Mod) {
327 // If the invalidating instruction is a store, and its in our candidate
328 // set, then we can do store-load forwarding: the load has the same value
329 // # as the stored value.
330 if (StoreInst *SI = dyn_cast<StoreInst>(I))
331 if (SI->getOperand(1) == LoadPtr)
332 RetVals.push_back(I->getOperand(0));
334 LoadInvalidatedInBBBefore = true;
339 // Figure out if the load is invalidated between the load and the exit of the
340 // block it is defined in. While we are scanning the current basic block, if
341 // we see any candidate loads, then we know they have the same value # as LI.
343 bool LoadInvalidatedInBBAfter = false;
345 BasicBlock::iterator I = LI;
346 for (++I; I != LoadBB->end(); ++I) {
347 // If this instruction is a load, then this instruction returns the same
349 if (isa<LoadInst>(I) && cast<LoadInst>(I)->getOperand(0) == LoadPtr)
350 RetVals.push_back(I);
352 if (AA.getModRefInfo(I, LoadPtr, LoadSize) & AliasAnalysis::Mod) {
353 LoadInvalidatedInBBAfter = true;
359 // If the pointer is clobbered on entry and on exit to the function, there is
360 // no need to do any global analysis at all.
361 if (LoadInvalidatedInBBBefore && LoadInvalidatedInBBAfter)
364 // Now that we know the value is not neccesarily killed on entry or exit to
365 // the BB, find out how many load and store instructions (to this location)
366 // live in each BB in the function.
368 std::map<BasicBlock*, unsigned> CandidateLoads;
369 std::set<BasicBlock*> CandidateStores;
371 for (Value::use_iterator UI = LoadPtr->use_begin(), UE = LoadPtr->use_end();
373 if (LoadInst *Cand = dyn_cast<LoadInst>(*UI)) {// Is a load of source?
374 if (Cand->getParent()->getParent() == F && // In the same function?
375 // Not in LI's block?
376 Cand->getParent() != LoadBB && !Cand->isVolatile())
377 ++CandidateLoads[Cand->getParent()]; // Got one.
378 } else if (StoreInst *Cand = dyn_cast<StoreInst>(*UI)) {
379 if (Cand->getParent()->getParent() == F && !Cand->isVolatile() &&
380 Cand->getOperand(1) == LoadPtr) // It's a store THROUGH the ptr.
381 CandidateStores.insert(Cand->getParent());
385 DominatorTree &DT = getAnalysis<DominatorTree>();
387 // TransparentBlocks - For each basic block the load/store is alive across,
388 // figure out if the pointer is invalidated or not. If it is invalidated, the
389 // boolean is set to false, if it's not it is set to true. If we don't know
390 // yet, the entry is not in the map.
391 std::map<BasicBlock*, bool> TransparentBlocks;
393 // Loop over all of the basic blocks that also load the value. If the value
394 // is live across the CFG from the source to destination blocks, and if the
395 // value is not invalidated in either the source or destination blocks, add it
396 // to the equivalence sets.
397 for (std::map<BasicBlock*, unsigned>::iterator
398 I = CandidateLoads.begin(), E = CandidateLoads.end(); I != E; ++I) {
399 bool CantEqual = false;
401 // Right now we only can handle cases where one load dominates the other.
402 // FIXME: generalize this!
403 BasicBlock *BB1 = I->first, *BB2 = LoadBB;
404 if (DT.dominates(BB1, BB2)) {
405 // The other load dominates LI. If the loaded value is killed entering
406 // the LoadBB block, we know the load is not live.
407 if (LoadInvalidatedInBBBefore)
409 } else if (DT.dominates(BB2, BB1)) {
410 std::swap(BB1, BB2); // Canonicalize
411 // LI dominates the other load. If the loaded value is killed exiting
412 // the LoadBB block, we know the load is not live.
413 if (LoadInvalidatedInBBAfter)
416 // None of these loads can VN the same.
421 // Ok, at this point, we know that BB1 dominates BB2, and that there is
422 // nothing in the LI block that kills the loaded value. Check to see if
423 // the value is live across the CFG.
424 std::set<BasicBlock*> Visited;
425 for (pred_iterator PI = pred_begin(BB2), E = pred_end(BB2); PI!=E; ++PI)
426 if (!isPathTransparentTo(*PI, BB1, LoadPtr, LoadSize, AA,
427 Visited, TransparentBlocks)) {
428 // None of these loads can VN the same.
434 // If the loads can equal so far, scan the basic block that contains the
435 // loads under consideration to see if they are invalidated in the block.
436 // For any loads that are not invalidated, add them to the equivalence
439 unsigned NumLoads = I->second;
441 // If LI dominates the block in question, check to see if any of the
442 // loads in this block are invalidated before they are reached.
443 for (BasicBlock::iterator BBI = I->first->begin(); ; ++BBI) {
444 if (LoadInst *LI = dyn_cast<LoadInst>(BBI)) {
445 if (LI->getOperand(0) == LoadPtr && !LI->isVolatile()) {
446 // The load is in the set!
447 RetVals.push_back(BBI);
448 if (--NumLoads == 0) break; // Found last load to check.
450 } else if (AA.getModRefInfo(BBI, LoadPtr, LoadSize)
451 & AliasAnalysis::Mod) {
452 // If there is a modifying instruction, nothing below it will value
458 // If the block dominates LI, make sure that the loads in the block are
459 // not invalidated before the block ends.
460 BasicBlock::iterator BBI = I->first->end();
463 if (LoadInst *LI = dyn_cast<LoadInst>(BBI)) {
464 if (LI->getOperand(0) == LoadPtr && !LI->isVolatile()) {
465 // The load is the same as this load!
466 RetVals.push_back(BBI);
467 if (--NumLoads == 0) break; // Found all of the laods.
469 } else if (AA.getModRefInfo(BBI, LoadPtr, LoadSize)
470 & AliasAnalysis::Mod) {
471 // If there is a modifying instruction, nothing above it will value
480 // Handle candidate stores. If the loaded location is clobbered on entrance
481 // to the LoadBB, no store outside of the LoadBB can value number equal, so
483 if (LoadInvalidatedInBBBefore)
486 // Stores in the load-bb are handled above.
487 CandidateStores.erase(LoadBB);
489 for (std::set<BasicBlock*>::iterator I = CandidateStores.begin(),
490 E = CandidateStores.end(); I != E; ++I)
491 if (DT.dominates(*I, LoadBB)) {
492 BasicBlock *StoreBB = *I;
494 // Check to see if the path from the store to the load is transparent
495 // w.r.t. the memory location.
496 bool CantEqual = false;
497 std::set<BasicBlock*> Visited;
498 for (pred_iterator PI = pred_begin(LoadBB), E = pred_end(LoadBB);
500 if (!isPathTransparentTo(*PI, StoreBB, LoadPtr, LoadSize, AA,
501 Visited, TransparentBlocks)) {
502 // None of these stores can VN the same.
508 // Okay, the path from the store block to the load block is clear, and
509 // we know that there are no invalidating instructions from the start
510 // of the load block to the load itself. Now we just scan the store
513 BasicBlock::iterator BBI = StoreBB->end();
515 assert(BBI != StoreBB->begin() &&
516 "There is a store in this block of the pointer, but the store"
517 " doesn't mod the address being stored to?? Must be a bug in"
518 " the alias analysis implementation!");
520 if (AA.getModRefInfo(BBI, LoadPtr, LoadSize) & AliasAnalysis::Mod) {
521 // If the invalidating instruction is one of the candidates,
522 // then it provides the value the load loads.
523 if (StoreInst *SI = dyn_cast<StoreInst>(BBI))
524 if (SI->getOperand(1) == LoadPtr)
525 RetVals.push_back(SI->getOperand(0));