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 #'s load instructions.
11 // To do this, it finds lexically identical load instructions, and uses alias
12 // analysis to determine which loads are guaranteed to produce the same value.
14 // This pass builds off of another value numbering pass to implement value
15 // numbering for non-load instructions. It uses Alias Analysis so that it can
16 // disambiguate the load instructions. The more powerful these base analyses
17 // are, the more powerful the resultant analysis will be.
19 //===----------------------------------------------------------------------===//
21 #include "llvm/Analysis/LoadValueNumbering.h"
22 #include "llvm/Analysis/ValueNumbering.h"
23 #include "llvm/Analysis/AliasAnalysis.h"
24 #include "llvm/Analysis/Dominators.h"
25 #include "llvm/Target/TargetData.h"
26 #include "llvm/Pass.h"
27 #include "llvm/Type.h"
28 #include "llvm/iMemory.h"
29 #include "llvm/BasicBlock.h"
30 #include "llvm/Support/CFG.h"
37 // FIXME: This should not be a FunctionPass.
38 struct LoadVN : public FunctionPass, public ValueNumbering {
40 /// Pass Implementation stuff. This doesn't do any analysis.
42 bool runOnFunction(Function &) { return false; }
44 /// getAnalysisUsage - Does not modify anything. It uses Value Numbering
45 /// and Alias Analysis.
47 virtual void getAnalysisUsage(AnalysisUsage &AU) const;
49 /// getEqualNumberNodes - Return nodes with the same value number as the
50 /// specified Value. This fills in the argument vector with any equal
53 virtual void getEqualNumberNodes(Value *V1,
54 std::vector<Value*> &RetVals) const;
56 /// haveEqualValueNumber - Given two load instructions, determine if they
57 /// both produce the same value on every execution of the program, assuming
58 /// that their source operands always give the same value. This uses the
59 /// AliasAnalysis implementation to invalidate loads when stores or function
60 /// calls occur that could modify the value produced by the load.
62 bool haveEqualValueNumber(LoadInst *LI, LoadInst *LI2, AliasAnalysis &AA,
63 DominatorSet &DomSetInfo) const;
64 bool haveEqualValueNumber(LoadInst *LI, StoreInst *SI, AliasAnalysis &AA,
65 DominatorSet &DomSetInfo) const;
68 // Register this pass...
69 RegisterOpt<LoadVN> X("load-vn", "Load Value Numbering");
71 // Declare that we implement the ValueNumbering interface
72 RegisterAnalysisGroup<ValueNumbering, LoadVN> Y;
75 Pass *createLoadValueNumberingPass() { return new LoadVN(); }
78 /// getAnalysisUsage - Does not modify anything. It uses Value Numbering and
81 void LoadVN::getAnalysisUsage(AnalysisUsage &AU) const {
83 AU.addRequired<AliasAnalysis>();
84 AU.addRequired<ValueNumbering>();
85 AU.addRequired<DominatorSet>();
86 AU.addRequired<TargetData>();
89 // getEqualNumberNodes - Return nodes with the same value number as the
90 // specified Value. This fills in the argument vector with any equal values.
92 void LoadVN::getEqualNumberNodes(Value *V,
93 std::vector<Value*> &RetVals) const {
94 // If the alias analysis has any must alias information to share with us, we
95 // can definitely use it.
96 if (isa<PointerType>(V->getType()))
97 getAnalysis<AliasAnalysis>().getMustAliases(V, RetVals);
99 if (LoadInst *LI = dyn_cast<LoadInst>(V)) {
100 // Volatile loads cannot be replaced with the value of other loads.
101 if (LI->isVolatile())
102 return getAnalysis<ValueNumbering>().getEqualNumberNodes(V, RetVals);
104 // If we have a load instruction, find all of the load and store
105 // instructions that use the same source operand. We implement this
106 // recursively, because there could be a load of a load of a load that are
107 // all identical. We are guaranteed that this cannot be an infinite
108 // recursion because load instructions would have to pass through a PHI node
109 // in order for there to be a cycle. The PHI node would be handled by the
110 // else case here, breaking the infinite recursion.
112 std::vector<Value*> PointerSources;
113 getEqualNumberNodes(LI->getOperand(0), PointerSources);
114 PointerSources.push_back(LI->getOperand(0));
116 Function *F = LI->getParent()->getParent();
118 // Now that we know the set of equivalent source pointers for the load
119 // instruction, look to see if there are any load or store candidates that
122 std::vector<LoadInst*> CandidateLoads;
123 std::vector<StoreInst*> CandidateStores;
125 while (!PointerSources.empty()) {
126 Value *Source = PointerSources.back();
127 PointerSources.pop_back(); // Get a source pointer...
129 for (Value::use_iterator UI = Source->use_begin(), UE = Source->use_end();
131 if (LoadInst *Cand = dyn_cast<LoadInst>(*UI)) {// Is a load of source?
132 if (Cand->getParent()->getParent() == F && // In the same function?
133 Cand != LI && !Cand->isVolatile()) // Not LI itself?
134 CandidateLoads.push_back(Cand); // Got one...
135 } else if (StoreInst *Cand = dyn_cast<StoreInst>(*UI)) {
136 if (Cand->getParent()->getParent() == F && !Cand->isVolatile() &&
137 Cand->getOperand(1) == Source) // It's a store THROUGH the ptr...
138 CandidateStores.push_back(Cand);
142 // Remove duplicates from the CandidateLoads list because alias analysis
143 // processing may be somewhat expensive and we don't want to do more work
146 unsigned OldSize = CandidateLoads.size();
147 std::sort(CandidateLoads.begin(), CandidateLoads.end());
148 CandidateLoads.erase(std::unique(CandidateLoads.begin(),
149 CandidateLoads.end()),
150 CandidateLoads.end());
151 // FIXME: REMOVE THIS SORTING AND UNIQUING IF IT CAN'T HAPPEN
152 assert(CandidateLoads.size() == OldSize && "Shrunk the candloads list?");
154 // Get Alias Analysis...
155 AliasAnalysis &AA = getAnalysis<AliasAnalysis>();
156 DominatorSet &DomSetInfo = getAnalysis<DominatorSet>();
158 // Loop over all of the candidate loads. If they are not invalidated by
159 // stores or calls between execution of them and LI, then add them to
161 for (unsigned i = 0, e = CandidateLoads.size(); i != e; ++i)
162 if (haveEqualValueNumber(LI, CandidateLoads[i], AA, DomSetInfo))
163 RetVals.push_back(CandidateLoads[i]);
164 for (unsigned i = 0, e = CandidateStores.size(); i != e; ++i)
165 if (haveEqualValueNumber(LI, CandidateStores[i], AA, DomSetInfo))
166 RetVals.push_back(CandidateStores[i]->getOperand(0));
169 assert(&getAnalysis<ValueNumbering>() != (ValueNumbering*)this &&
170 "getAnalysis() returned this!");
172 // Not a load instruction? Just chain to the base value numbering
173 // implementation to satisfy the request...
174 return getAnalysis<ValueNumbering>().getEqualNumberNodes(V, RetVals);
178 // CheckForInvalidatingInst - Return true if BB or any of the predecessors of BB
179 // (until DestBB) contain an instruction that might invalidate Ptr.
181 static bool CheckForInvalidatingInst(BasicBlock *BB, BasicBlock *DestBB,
182 Value *Ptr, unsigned Size,
184 std::set<BasicBlock*> &VisitedSet) {
185 // Found the termination point!
186 if (BB == DestBB || VisitedSet.count(BB)) return false;
188 // Avoid infinite recursion!
189 VisitedSet.insert(BB);
191 // Can this basic block modify Ptr?
192 if (AA.canBasicBlockModify(*BB, Ptr, Size))
195 // Check all of our predecessor blocks...
196 for (pred_iterator PI = pred_begin(BB), PE = pred_end(BB); PI != PE; ++PI)
197 if (CheckForInvalidatingInst(*PI, DestBB, Ptr, Size, AA, VisitedSet))
200 // None of our predecessor blocks contain an invalidating instruction, and we
206 /// haveEqualValueNumber - Given two load instructions, determine if they both
207 /// produce the same value on every execution of the program, assuming that
208 /// their source operands always give the same value. This uses the
209 /// AliasAnalysis implementation to invalidate loads when stores or function
210 /// calls occur that could modify the value produced by the load.
212 bool LoadVN::haveEqualValueNumber(LoadInst *L1, LoadInst *L2,
214 DominatorSet &DomSetInfo) const {
215 assert(L1 != L2 && "haveEqualValueNumber assumes differing loads!");
216 assert(L1->getType() == L2->getType() &&
217 "How could the same source pointer return different types?");
218 Value *LoadAddress = L1->getOperand(0);
220 // Find out how many bytes of memory are loaded by the load instruction...
221 unsigned LoadSize = getAnalysis<TargetData>().getTypeSize(L1->getType());
223 // If the two loads are in the same basic block, just do a local analysis.
224 if (L1->getParent() == L2->getParent()) {
225 // It can be _very_ expensive to determine which instruction occurs first in
226 // the basic block if the block is large (see PR209). For this reason,
227 // instead of figuring out which block is first, then scanning all of the
228 // instructions, we scan the instructions both ways from L1 until we find
229 // L2. Along the way if we find a potentially modifying instruction, we
230 // kill the search. This helps in cases where we have large blocks the have
231 // potentially modifying instructions in them which stop the search.
233 BasicBlock *BB = L1->getParent();
234 BasicBlock::iterator UpIt = L1, DownIt = L1; ++DownIt;
235 bool NoModifiesUp = true, NoModifiesDown = true;
237 // Scan up and down looking for L2, a modifying instruction, or the end of a
239 while (UpIt != BB->begin() && DownIt != BB->end()) {
243 return NoModifiesUp; // No instructions invalidate the loads!
246 !(AA.getModRefInfo(UpIt, LoadAddress, LoadSize) & AliasAnalysis::Mod);
249 return NoModifiesDown;
252 !(AA.getModRefInfo(DownIt, LoadAddress, LoadSize)
253 & AliasAnalysis::Mod);
257 // If we got here, we ran into one end of the basic block or the other.
258 if (UpIt != BB->begin()) {
259 // If we know that the upward scan found a modifier, return false.
260 if (!NoModifiesUp) return false;
262 // Otherwise, continue the scan looking for a modifier or L2.
263 for (--UpIt; &*UpIt != L2; --UpIt)
264 if (AA.getModRefInfo(UpIt, LoadAddress, LoadSize) & AliasAnalysis::Mod)
268 // If we know that the downward scan found a modifier, return false.
269 assert(DownIt != B->end() && "Didn't find instructions??");
270 if (!NoModifiesDown) return false;
272 // Otherwise, continue the scan looking for a modifier or L2.
273 for (; &*DownIt != L2; ++DownIt) {
274 if (AA.getModRefInfo(DownIt, LoadAddress, LoadSize) &AliasAnalysis::Mod)
280 // Figure out which load dominates the other one. If neither dominates the
281 // other we cannot eliminate them.
283 // FIXME: This could be enhanced greatly!
285 if (DomSetInfo.dominates(L2, L1))
286 std::swap(L1, L2); // Make L1 dominate L2
287 else if (!DomSetInfo.dominates(L1, L2))
288 return false; // Neither instruction dominates the other one...
290 BasicBlock *BB1 = L1->getParent(), *BB2 = L2->getParent();
292 // L1 now dominates L2. Check to see if the intervening instructions
293 // between the two loads might modify the loaded location.
295 // Make sure that there are no modifying instructions between L1 and the end
296 // of its basic block.
298 if (AA.canInstructionRangeModify(*L1, *BB1->getTerminator(), LoadAddress,
300 return false; // Cannot eliminate load
302 // Make sure that there are no modifying instructions between the start of
303 // BB2 and the second load instruction.
305 if (AA.canInstructionRangeModify(BB2->front(), *L2, LoadAddress, LoadSize))
306 return false; // Cannot eliminate load
308 // Do a depth first traversal of the inverse CFG starting at L2's block,
309 // looking for L1's block. The inverse CFG is made up of the predecessor
310 // nodes of a block... so all of the edges in the graph are "backward".
312 std::set<BasicBlock*> VisitedSet;
313 for (pred_iterator PI = pred_begin(BB2), PE = pred_end(BB2); PI != PE; ++PI)
314 if (CheckForInvalidatingInst(*PI, BB1, LoadAddress, LoadSize, AA,
318 // If we passed all of these checks then we are sure that the two loads
319 // produce the same value.
325 /// haveEqualValueNumber - Given a load instruction and a store instruction,
326 /// determine if the stored value reaches the loaded value unambiguously on
327 /// every execution of the program. This uses the AliasAnalysis implementation
328 /// to invalidate the stored value when stores or function calls occur that
329 /// could modify the value produced by the load.
331 bool LoadVN::haveEqualValueNumber(LoadInst *Load, StoreInst *Store,
333 DominatorSet &DomSetInfo) const {
334 // If the store does not dominate the load, we cannot do anything...
335 if (!DomSetInfo.dominates(Store, Load))
338 BasicBlock *BB1 = Store->getParent(), *BB2 = Load->getParent();
339 Value *LoadAddress = Load->getOperand(0);
341 assert(LoadAddress->getType() == Store->getOperand(1)->getType() &&
342 "How could the same source pointer return different types?");
344 // Find out how many bytes of memory are loaded by the load instruction...
345 unsigned LoadSize = getAnalysis<TargetData>().getTypeSize(Load->getType());
347 // Compute a basic block iterator pointing to the instruction after the store.
348 BasicBlock::iterator StoreIt = Store; ++StoreIt;
350 // Check to see if the intervening instructions between the two store and load
351 // include a store or call...
353 if (BB1 == BB2) { // In same basic block?
354 // In this degenerate case, no checking of global basic blocks has to occur
355 // just check the instructions BETWEEN Store & Load...
357 if (AA.canInstructionRangeModify(*StoreIt, *Load, LoadAddress, LoadSize))
358 return false; // Cannot eliminate load
360 // No instructions invalidate the stored value, they produce the same value!
363 // Make sure that there are no store instructions between the Store and the
364 // end of its basic block...
366 if (AA.canInstructionRangeModify(*StoreIt, *BB1->getTerminator(),
367 LoadAddress, LoadSize))
368 return false; // Cannot eliminate load
370 // Make sure that there are no store instructions between the start of BB2
371 // and the second load instruction...
373 if (AA.canInstructionRangeModify(BB2->front(), *Load, LoadAddress,LoadSize))
374 return false; // Cannot eliminate load
376 // Do a depth first traversal of the inverse CFG starting at L2's block,
377 // looking for L1's block. The inverse CFG is made up of the predecessor
378 // nodes of a block... so all of the edges in the graph are "backward".
380 std::set<BasicBlock*> VisitedSet;
381 for (pred_iterator PI = pred_begin(BB2), PE = pred_end(BB2); PI != PE; ++PI)
382 if (CheckForInvalidatingInst(*PI, BB1, LoadAddress, LoadSize, AA,
386 // If we passed all of these checks then we are sure that the two loads
387 // produce the same value.
392 } // End llvm namespace