1 //===- LoadValueNumbering.cpp - Load Value #'ing Implementation -*- C++ -*-===//
3 // The LLVM Compiler Infrastructure
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.
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/Constant.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"
40 // FIXME: This should not be a FunctionPass.
41 struct LoadVN : public FunctionPass, public ValueNumbering {
43 /// Pass Implementation stuff. This doesn't do any analysis.
45 bool runOnFunction(Function &) { return false; }
47 /// getAnalysisUsage - Does not modify anything. It uses Value Numbering
48 /// and Alias Analysis.
50 virtual void getAnalysisUsage(AnalysisUsage &AU) const;
52 /// getEqualNumberNodes - Return nodes with the same value number as the
53 /// specified Value. This fills in the argument vector with any equal
56 virtual void getEqualNumberNodes(Value *V1,
57 std::vector<Value*> &RetVals) const;
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.
63 virtual void deleteValue(Value *V) {
64 getAnalysis<AliasAnalysis>().deleteValue(V);
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.
73 virtual void copyValue(Value *From, Value *To) {
74 getAnalysis<AliasAnalysis>().copyValue(From, To);
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;
83 // Register this pass...
84 RegisterOpt<LoadVN> X("load-vn", "Load Value Numbering");
86 // Declare that we implement the ValueNumbering interface
87 RegisterAnalysisGroup<ValueNumbering, LoadVN> Y;
90 FunctionPass *llvm::createLoadValueNumberingPass() { return new LoadVN(); }
93 /// getAnalysisUsage - Does not modify anything. It uses Value Numbering and
96 void LoadVN::getAnalysisUsage(AnalysisUsage &AU) const {
98 AU.addRequired<AliasAnalysis>();
99 AU.addRequired<ValueNumbering>();
100 AU.addRequired<DominatorSet>();
101 AU.addRequired<TargetData>();
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)
113 // Check whether this block is known transparent or not.
114 std::map<BasicBlock*, bool>::iterator TBI =
115 TransparentBlocks.lower_bound(CurBlock);
117 if (TBI == TransparentBlocks.end() || TBI->first != CurBlock) {
118 // If this basic block can modify the memory location, then the path is not
120 if (AA.canBasicBlockModify(*CurBlock, Ptr, Size)) {
121 TransparentBlocks.insert(TBI, std::make_pair(CurBlock, false));
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.
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);
134 if (!isPathTransparentTo(*PI, Dom, Ptr, Size, AA, Visited,
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 if (!AA.onlyReadsMemory(CF)) return; // Nothing we can do.
149 // Scan all of the arguments of the function, looking for one that is not
150 // global. In particular, we would prefer to have an argument or instruction
151 // operand to chase the def-use chains of.
153 for (unsigned i = 1, e = CI->getNumOperands(); i != e; ++i)
154 if (isa<Argument>(CI->getOperand(i)) ||
155 isa<Instruction>(CI->getOperand(i))) {
156 Op = CI->getOperand(i);
160 // Identify all lexically identical calls in this function.
161 std::vector<CallInst*> IdenticalCalls;
163 Function *CIFunc = CI->getParent()->getParent();
164 for (Value::use_iterator UI = Op->use_begin(), E = Op->use_end(); UI != E;
166 if (CallInst *C = dyn_cast<CallInst>(*UI))
167 if (C->getNumOperands() == CI->getNumOperands() &&
168 C->getOperand(0) == CI->getOperand(0) &&
169 C->getParent()->getParent() == CIFunc && C != CI) {
170 bool AllOperandsEqual = true;
171 for (unsigned i = 1, e = CI->getNumOperands(); i != e; ++i)
172 if (C->getOperand(i) != CI->getOperand(i)) {
173 AllOperandsEqual = false;
177 if (AllOperandsEqual)
178 IdenticalCalls.push_back(C);
181 if (IdenticalCalls.empty()) return;
183 // Eliminate duplicates, which could occur if we chose a value that is passed
184 // into a call site multiple times.
185 std::sort(IdenticalCalls.begin(), IdenticalCalls.end());
186 IdenticalCalls.erase(std::unique(IdenticalCalls.begin(),IdenticalCalls.end()),
187 IdenticalCalls.end());
189 // If the call reads memory, we must make sure that there are no stores
190 // between the calls in question.
192 // FIXME: This should use mod/ref information. What we really care about it
193 // whether an intervening instruction could modify memory that is read, not
196 if (!AA.doesNotAccessMemory(CF)) {
197 DominatorSet &DomSetInfo = getAnalysis<DominatorSet>();
198 BasicBlock *CIBB = CI->getParent();
199 for (unsigned i = 0; i != IdenticalCalls.size(); ++i) {
200 CallInst *C = IdenticalCalls[i];
201 bool CantEqual = false;
203 if (DomSetInfo.dominates(CIBB, C->getParent())) {
204 // FIXME: we currently only handle the case where both calls are in the
206 if (CIBB != C->getParent()) {
209 Instruction *First = CI, *Second = C;
210 if (!DomSetInfo.dominates(CI, C))
211 std::swap(First, Second);
213 // Scan the instructions between the calls, checking for stores or
214 // calls to dangerous functions.
215 BasicBlock::iterator I = First;
216 for (++First; I != BasicBlock::iterator(Second); ++I) {
217 if (isa<StoreInst>(I)) {
218 // FIXME: We could use mod/ref information to make this much
222 } else if (CallInst *CI = dyn_cast<CallInst>(I)) {
223 if (CI->getCalledFunction() == 0 ||
224 !AA.onlyReadsMemory(CI->getCalledFunction())) {
228 } else if (I->mayWriteToMemory()) {
235 } else if (DomSetInfo.dominates(C->getParent(), CIBB)) {
236 // FIXME: We could implement this, but we don't for now.
239 // FIXME: if one doesn't dominate the other, we can't tell yet.
245 // This call does not produce the same value as the one in the query.
246 std::swap(IdenticalCalls[i--], IdenticalCalls.back());
247 IdenticalCalls.pop_back();
252 // Any calls that are identical and not destroyed will produce equal values!
253 for (unsigned i = 0, e = IdenticalCalls.size(); i != e; ++i)
254 RetVals.push_back(IdenticalCalls[i]);
257 // getEqualNumberNodes - Return nodes with the same value number as the
258 // specified Value. This fills in the argument vector with any equal values.
260 void LoadVN::getEqualNumberNodes(Value *V,
261 std::vector<Value*> &RetVals) const {
262 // If the alias analysis has any must alias information to share with us, we
263 // can definitely use it.
264 if (isa<PointerType>(V->getType()))
265 getAnalysis<AliasAnalysis>().getMustAliases(V, RetVals);
267 if (!isa<LoadInst>(V)) {
268 if (CallInst *CI = dyn_cast<CallInst>(V))
269 getCallEqualNumberNodes(CI, RetVals);
271 // Not a load instruction? Just chain to the base value numbering
272 // implementation to satisfy the request...
273 assert(&getAnalysis<ValueNumbering>() != (ValueNumbering*)this &&
274 "getAnalysis() returned this!");
276 return getAnalysis<ValueNumbering>().getEqualNumberNodes(V, RetVals);
279 // Volatile loads cannot be replaced with the value of other loads.
280 LoadInst *LI = cast<LoadInst>(V);
281 if (LI->isVolatile())
282 return getAnalysis<ValueNumbering>().getEqualNumberNodes(V, RetVals);
284 // If we have a load instruction, find all of the load and store instructions
285 // that use the same source operand. We implement this recursively, because
286 // there could be a load of a load of a load that are all identical. We are
287 // guaranteed that this cannot be an infinite recursion because load
288 // instructions would have to pass through a PHI node in order for there to be
289 // a cycle. The PHI node would be handled by the else case here, breaking the
290 // infinite recursion.
292 std::vector<Value*> PointerSources;
293 getEqualNumberNodes(LI->getOperand(0), PointerSources);
294 PointerSources.push_back(LI->getOperand(0));
296 BasicBlock *LoadBB = LI->getParent();
297 Function *F = LoadBB->getParent();
299 // Now that we know the set of equivalent source pointers for the load
300 // instruction, look to see if there are any load or store candidates that are
303 std::map<BasicBlock*, std::vector<LoadInst*> > CandidateLoads;
304 std::map<BasicBlock*, std::vector<StoreInst*> > CandidateStores;
305 std::set<AllocationInst*> Allocations;
307 while (!PointerSources.empty()) {
308 Value *Source = PointerSources.back();
309 PointerSources.pop_back(); // Get a source pointer...
311 if (AllocationInst *AI = dyn_cast<AllocationInst>(Source))
312 Allocations.insert(AI);
314 for (Value::use_iterator UI = Source->use_begin(), UE = Source->use_end();
316 if (LoadInst *Cand = dyn_cast<LoadInst>(*UI)) {// Is a load of source?
317 if (Cand->getParent()->getParent() == F && // In the same function?
318 Cand != LI && !Cand->isVolatile()) // Not LI itself?
319 CandidateLoads[Cand->getParent()].push_back(Cand); // Got one...
320 } else if (StoreInst *Cand = dyn_cast<StoreInst>(*UI)) {
321 if (Cand->getParent()->getParent() == F && !Cand->isVolatile() &&
322 Cand->getOperand(1) == Source) // It's a store THROUGH the ptr...
323 CandidateStores[Cand->getParent()].push_back(Cand);
327 // Get alias analysis & dominators.
328 AliasAnalysis &AA = getAnalysis<AliasAnalysis>();
329 DominatorSet &DomSetInfo = getAnalysis<DominatorSet>();
330 Value *LoadPtr = LI->getOperand(0);
331 // Find out how many bytes of memory are loaded by the load instruction...
332 unsigned LoadSize = getAnalysis<TargetData>().getTypeSize(LI->getType());
334 // Find all of the candidate loads and stores that are in the same block as
335 // the defining instruction.
336 std::set<Instruction*> Instrs;
337 Instrs.insert(CandidateLoads[LoadBB].begin(), CandidateLoads[LoadBB].end());
338 CandidateLoads.erase(LoadBB);
339 Instrs.insert(CandidateStores[LoadBB].begin(), CandidateStores[LoadBB].end());
340 CandidateStores.erase(LoadBB);
342 // Figure out if the load is invalidated from the entry of the block it is in
343 // until the actual instruction. This scans the block backwards from LI. If
344 // we see any candidate load or store instructions, then we know that the
345 // candidates have the same value # as LI.
346 bool LoadInvalidatedInBBBefore = false;
347 for (BasicBlock::iterator I = LI; I != LoadBB->begin(); ) {
349 // If this instruction is a candidate load before LI, we know there are no
350 // invalidating instructions between it and LI, so they have the same value
352 if (isa<LoadInst>(I) && Instrs.count(I)) {
353 RetVals.push_back(I);
355 } else if (AllocationInst *AI = dyn_cast<AllocationInst>(I)) {
356 // If we run into an allocation of the value being loaded, then the
357 // contenxt are not initialized. We can return any value, so we will
359 if (Allocations.count(AI)) {
360 LoadInvalidatedInBBBefore = true;
361 RetVals.push_back(Constant::getNullValue(LI->getType()));
366 if (AA.getModRefInfo(I, LoadPtr, LoadSize) & AliasAnalysis::Mod) {
367 // If the invalidating instruction is a store, and its in our candidate
368 // set, then we can do store-load forwarding: the load has the same value
369 // # as the stored value.
370 if (isa<StoreInst>(I) && Instrs.count(I)) {
372 RetVals.push_back(I->getOperand(0));
375 LoadInvalidatedInBBBefore = true;
380 // Figure out if the load is invalidated between the load and the exit of the
381 // block it is defined in. While we are scanning the current basic block, if
382 // we see any candidate loads, then we know they have the same value # as LI.
384 bool LoadInvalidatedInBBAfter = false;
385 for (BasicBlock::iterator I = LI->getNext(); I != LoadBB->end(); ++I) {
386 // If this instruction is a load, then this instruction returns the same
388 if (isa<LoadInst>(I) && Instrs.count(I)) {
389 RetVals.push_back(I);
393 if (AA.getModRefInfo(I, LoadPtr, LoadSize) & AliasAnalysis::Mod) {
394 LoadInvalidatedInBBAfter = true;
399 // If there is anything left in the Instrs set, it could not possibly equal
403 // TransparentBlocks - For each basic block the load/store is alive across,
404 // figure out if the pointer is invalidated or not. If it is invalidated, the
405 // boolean is set to false, if it's not it is set to true. If we don't know
406 // yet, the entry is not in the map.
407 std::map<BasicBlock*, bool> TransparentBlocks;
409 // Loop over all of the basic blocks that also load the value. If the value
410 // is live across the CFG from the source to destination blocks, and if the
411 // value is not invalidated in either the source or destination blocks, add it
412 // to the equivalence sets.
413 for (std::map<BasicBlock*, std::vector<LoadInst*> >::iterator
414 I = CandidateLoads.begin(), E = CandidateLoads.end(); I != E; ++I) {
415 bool CantEqual = false;
417 // Right now we only can handle cases where one load dominates the other.
418 // FIXME: generalize this!
419 BasicBlock *BB1 = I->first, *BB2 = LoadBB;
420 if (DomSetInfo.dominates(BB1, BB2)) {
421 // The other load dominates LI. If the loaded value is killed entering
422 // the LoadBB block, we know the load is not live.
423 if (LoadInvalidatedInBBBefore)
425 } else if (DomSetInfo.dominates(BB2, BB1)) {
426 std::swap(BB1, BB2); // Canonicalize
427 // LI dominates the other load. If the loaded value is killed exiting
428 // the LoadBB block, we know the load is not live.
429 if (LoadInvalidatedInBBAfter)
432 // None of these loads can VN the same.
437 // Ok, at this point, we know that BB1 dominates BB2, and that there is
438 // nothing in the LI block that kills the loaded value. Check to see if
439 // the value is live across the CFG.
440 std::set<BasicBlock*> Visited;
441 for (pred_iterator PI = pred_begin(BB2), E = pred_end(BB2); PI!=E; ++PI)
442 if (!isPathTransparentTo(*PI, BB1, LoadPtr, LoadSize, AA,
443 Visited, TransparentBlocks)) {
444 // None of these loads can VN the same.
450 // If the loads can equal so far, scan the basic block that contains the
451 // loads under consideration to see if they are invalidated in the block.
452 // For any loads that are not invalidated, add them to the equivalence
455 Instrs.insert(I->second.begin(), I->second.end());
457 // If LI dominates the block in question, check to see if any of the
458 // loads in this block are invalidated before they are reached.
459 for (BasicBlock::iterator BBI = I->first->begin(); ; ++BBI) {
460 if (isa<LoadInst>(BBI) && Instrs.count(BBI)) {
461 // The load is in the set!
462 RetVals.push_back(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 below it will value
473 // If the block dominates LI, make sure that the loads in the block are
474 // not invalidated before the block ends.
475 BasicBlock::iterator BBI = I->first->end();
478 if (isa<LoadInst>(BBI) && Instrs.count(BBI)) {
479 // The load is in the set!
480 RetVals.push_back(BBI);
482 if (Instrs.empty()) break;
483 } else if (AA.getModRefInfo(BBI, LoadPtr, LoadSize)
484 & AliasAnalysis::Mod) {
485 // If there is a modifying instruction, nothing above it will value
496 // Handle candidate stores. If the loaded location is clobbered on entrance
497 // to the LoadBB, no store outside of the LoadBB can value number equal, so
499 if (LoadInvalidatedInBBBefore)
502 for (std::map<BasicBlock*, std::vector<StoreInst*> >::iterator
503 I = CandidateStores.begin(), E = CandidateStores.end(); I != E; ++I)
504 if (DomSetInfo.dominates(I->first, LoadBB)) {
505 // Check to see if the path from the store to the load is transparent
506 // w.r.t. the memory location.
507 bool CantEqual = false;
508 std::set<BasicBlock*> Visited;
509 for (pred_iterator PI = pred_begin(LoadBB), E = pred_end(LoadBB);
511 if (!isPathTransparentTo(*PI, I->first, LoadPtr, LoadSize, AA,
512 Visited, TransparentBlocks)) {
513 // None of these stores can VN the same.
519 // Okay, the path from the store block to the load block is clear, and
520 // we know that there are no invalidating instructions from the start
521 // of the load block to the load itself. Now we just scan the store
524 BasicBlock::iterator BBI = I->first->end();
526 assert(BBI != I->first->begin() &&
527 "There is a store in this block of the pointer, but the store"
528 " doesn't mod the address being stored to?? Must be a bug in"
529 " the alias analysis implementation!");
531 if (AA.getModRefInfo(BBI, LoadPtr, LoadSize) & AliasAnalysis::Mod) {
532 // If the invalidating instruction is one of the candidates,
533 // then it provides the value the load loads.
534 if (StoreInst *SI = dyn_cast<StoreInst>(BBI))
535 if (std::find(I->second.begin(), I->second.end(), SI) !=
537 RetVals.push_back(SI->getOperand(0));