1 //===- LoadValueNumbering.cpp - Load Value #'ing Implementation -*- C++ -*-===//
3 // This file implements a value numbering pass that value #'s load instructions.
4 // To do this, it finds lexically identical load instructions, and uses alias
5 // analysis to determine which loads are guaranteed to produce the same value.
7 // This pass builds off of another value numbering pass to implement value
8 // numbering for non-load instructions. It uses Alias Analysis so that it can
9 // disambiguate the load instructions. The more powerful these base analyses
10 // are, the more powerful the resultant analysis will be.
12 //===----------------------------------------------------------------------===//
14 #include "llvm/Analysis/LoadValueNumbering.h"
15 #include "llvm/Analysis/ValueNumbering.h"
16 #include "llvm/Analysis/AliasAnalysis.h"
17 #include "llvm/Analysis/Dominators.h"
18 #include "llvm/Target/TargetData.h"
19 #include "llvm/Pass.h"
20 #include "llvm/Type.h"
21 #include "llvm/iMemory.h"
22 #include "llvm/BasicBlock.h"
23 #include "llvm/Support/CFG.h"
28 // FIXME: This should not be a FunctionPass.
29 struct LoadVN : public FunctionPass, public ValueNumbering {
31 /// Pass Implementation stuff. This doesn't do any analysis.
33 bool runOnFunction(Function &) { return false; }
35 /// getAnalysisUsage - Does not modify anything. It uses Value Numbering
36 /// and Alias Analysis.
38 virtual void getAnalysisUsage(AnalysisUsage &AU) const;
40 /// getEqualNumberNodes - Return nodes with the same value number as the
41 /// specified Value. This fills in the argument vector with any equal
44 virtual void getEqualNumberNodes(Value *V1,
45 std::vector<Value*> &RetVals) const;
47 /// haveEqualValueNumber - Given two load instructions, determine if they
48 /// both produce the same value on every execution of the program, assuming
49 /// that their source operands always give the same value. This uses the
50 /// AliasAnalysis implementation to invalidate loads when stores or function
51 /// calls occur that could modify the value produced by the load.
53 bool haveEqualValueNumber(LoadInst *LI, LoadInst *LI2, AliasAnalysis &AA,
54 DominatorSet &DomSetInfo) const;
55 bool haveEqualValueNumber(LoadInst *LI, StoreInst *SI, AliasAnalysis &AA,
56 DominatorSet &DomSetInfo) const;
59 // Register this pass...
60 RegisterOpt<LoadVN> X("load-vn", "Load Value Numbering");
62 // Declare that we implement the ValueNumbering interface
63 RegisterAnalysisGroup<ValueNumbering, LoadVN> Y;
68 Pass *createLoadValueNumberingPass() { return new LoadVN(); }
71 /// getAnalysisUsage - Does not modify anything. It uses Value Numbering and
74 void LoadVN::getAnalysisUsage(AnalysisUsage &AU) const {
76 AU.addRequired<AliasAnalysis>();
77 AU.addRequired<ValueNumbering>();
78 AU.addRequired<DominatorSet>();
79 AU.addRequired<TargetData>();
82 // getEqualNumberNodes - Return nodes with the same value number as the
83 // specified Value. This fills in the argument vector with any equal values.
85 void LoadVN::getEqualNumberNodes(Value *V,
86 std::vector<Value*> &RetVals) const {
87 // If the alias analysis has any must alias information to share with us, we
88 // can definitely use it.
89 if (isa<PointerType>(V->getType()))
90 getAnalysis<AliasAnalysis>().getMustAliases(V, RetVals);
92 if (LoadInst *LI = dyn_cast<LoadInst>(V)) {
93 // Volatile loads cannot be replaced with the value of other loads.
95 return getAnalysis<ValueNumbering>().getEqualNumberNodes(V, RetVals);
97 // If we have a load instruction, find all of the load and store
98 // instructions that use the same source operand. We implement this
99 // recursively, because there could be a load of a load of a load that are
100 // all identical. We are guaranteed that this cannot be an infinite
101 // recursion because load instructions would have to pass through a PHI node
102 // in order for there to be a cycle. The PHI node would be handled by the
103 // else case here, breaking the infinite recursion.
105 std::vector<Value*> PointerSources;
106 getEqualNumberNodes(LI->getOperand(0), PointerSources);
107 PointerSources.push_back(LI->getOperand(0));
109 Function *F = LI->getParent()->getParent();
111 // Now that we know the set of equivalent source pointers for the load
112 // instruction, look to see if there are any load or store candidates that
115 std::vector<LoadInst*> CandidateLoads;
116 std::vector<StoreInst*> CandidateStores;
118 while (!PointerSources.empty()) {
119 Value *Source = PointerSources.back();
120 PointerSources.pop_back(); // Get a source pointer...
122 for (Value::use_iterator UI = Source->use_begin(), UE = Source->use_end();
124 if (LoadInst *Cand = dyn_cast<LoadInst>(*UI)) {// Is a load of source?
125 if (Cand->getParent()->getParent() == F && // In the same function?
126 Cand != LI && !Cand->isVolatile()) // Not LI itself?
127 CandidateLoads.push_back(Cand); // Got one...
128 } else if (StoreInst *Cand = dyn_cast<StoreInst>(*UI)) {
129 if (Cand->getParent()->getParent() == F && !Cand->isVolatile() &&
130 Cand->getOperand(1) == Source) // It's a store THROUGH the ptr...
131 CandidateStores.push_back(Cand);
135 // Remove duplicates from the CandidateLoads list because alias analysis
136 // processing may be somewhat expensive and we don't want to do more work
139 unsigned OldSize = CandidateLoads.size();
140 std::sort(CandidateLoads.begin(), CandidateLoads.end());
141 CandidateLoads.erase(std::unique(CandidateLoads.begin(),
142 CandidateLoads.end()),
143 CandidateLoads.end());
144 // FIXME: REMOVE THIS SORTING AND UNIQUING IF IT CAN'T HAPPEN
145 assert(CandidateLoads.size() == OldSize && "Shrunk the candloads list?");
147 // Get Alias Analysis...
148 AliasAnalysis &AA = getAnalysis<AliasAnalysis>();
149 DominatorSet &DomSetInfo = getAnalysis<DominatorSet>();
151 // Loop over all of the candidate loads. If they are not invalidated by
152 // stores or calls between execution of them and LI, then add them to
154 for (unsigned i = 0, e = CandidateLoads.size(); i != e; ++i)
155 if (haveEqualValueNumber(LI, CandidateLoads[i], AA, DomSetInfo))
156 RetVals.push_back(CandidateLoads[i]);
157 for (unsigned i = 0, e = CandidateStores.size(); i != e; ++i)
158 if (haveEqualValueNumber(LI, CandidateStores[i], AA, DomSetInfo))
159 RetVals.push_back(CandidateStores[i]->getOperand(0));
162 assert(&getAnalysis<ValueNumbering>() != (ValueNumbering*)this &&
163 "getAnalysis() returned this!");
165 // Not a load instruction? Just chain to the base value numbering
166 // implementation to satisfy the request...
167 return getAnalysis<ValueNumbering>().getEqualNumberNodes(V, RetVals);
171 // CheckForInvalidatingInst - Return true if BB or any of the predecessors of BB
172 // (until DestBB) contain an instruction that might invalidate Ptr.
174 static bool CheckForInvalidatingInst(BasicBlock *BB, BasicBlock *DestBB,
175 Value *Ptr, unsigned Size,
177 std::set<BasicBlock*> &VisitedSet) {
178 // Found the termination point!
179 if (BB == DestBB || VisitedSet.count(BB)) return false;
181 // Avoid infinite recursion!
182 VisitedSet.insert(BB);
184 // Can this basic block modify Ptr?
185 if (AA.canBasicBlockModify(*BB, Ptr, Size))
188 // Check all of our predecessor blocks...
189 for (pred_iterator PI = pred_begin(BB), PE = pred_end(BB); PI != PE; ++PI)
190 if (CheckForInvalidatingInst(*PI, DestBB, Ptr, Size, AA, VisitedSet))
193 // None of our predecessor blocks contain an invalidating instruction, and we
199 /// haveEqualValueNumber - Given two load instructions, determine if they both
200 /// produce the same value on every execution of the program, assuming that
201 /// their source operands always give the same value. This uses the
202 /// AliasAnalysis implementation to invalidate loads when stores or function
203 /// calls occur that could modify the value produced by the load.
205 bool LoadVN::haveEqualValueNumber(LoadInst *L1, LoadInst *L2,
207 DominatorSet &DomSetInfo) const {
208 // Figure out which load dominates the other one. If neither dominates the
209 // other we cannot eliminate them.
211 // FIXME: This could be enhanced to some cases with a shared dominator!
213 if (DomSetInfo.dominates(L2, L1))
214 std::swap(L1, L2); // Make L1 dominate L2
215 else if (!DomSetInfo.dominates(L1, L2))
216 return false; // Neither instruction dominates the other one...
218 BasicBlock *BB1 = L1->getParent(), *BB2 = L2->getParent();
219 Value *LoadAddress = L1->getOperand(0);
221 assert(L1->getType() == L2->getType() &&
222 "How could the same source pointer return different types?");
224 // Find out how many bytes of memory are loaded by the load instruction...
225 unsigned LoadSize = getAnalysis<TargetData>().getTypeSize(L1->getType());
227 // L1 now dominates L2. Check to see if the intervening instructions between
228 // the two loads include a store or call...
230 if (BB1 == BB2) { // In same basic block?
231 // In this degenerate case, no checking of global basic blocks has to occur
232 // just check the instructions BETWEEN L1 & L2...
234 if (AA.canInstructionRangeModify(*L1, *L2, LoadAddress, LoadSize))
235 return false; // Cannot eliminate load
237 // No instructions invalidate the loads, they produce the same value!
240 // Make sure that there are no store instructions between L1 and the end of
241 // its basic block...
243 if (AA.canInstructionRangeModify(*L1, *BB1->getTerminator(), LoadAddress,
245 return false; // Cannot eliminate load
247 // Make sure that there are no store instructions between the start of BB2
248 // and the second load instruction...
250 if (AA.canInstructionRangeModify(BB2->front(), *L2, LoadAddress, LoadSize))
251 return false; // Cannot eliminate load
253 // Do a depth first traversal of the inverse CFG starting at L2's block,
254 // looking for L1's block. The inverse CFG is made up of the predecessor
255 // nodes of a block... so all of the edges in the graph are "backward".
257 std::set<BasicBlock*> VisitedSet;
258 for (pred_iterator PI = pred_begin(BB2), PE = pred_end(BB2); PI != PE; ++PI)
259 if (CheckForInvalidatingInst(*PI, BB1, LoadAddress, LoadSize, AA,
263 // If we passed all of these checks then we are sure that the two loads
264 // produce the same value.
270 /// haveEqualValueNumber - Given a load instruction and a store instruction,
271 /// determine if the stored value reaches the loaded value unambiguously on
272 /// every execution of the program. This uses the AliasAnalysis implementation
273 /// to invalidate the stored value when stores or function calls occur that
274 /// could modify the value produced by the load.
276 bool LoadVN::haveEqualValueNumber(LoadInst *Load, StoreInst *Store,
278 DominatorSet &DomSetInfo) const {
279 // If the store does not dominate the load, we cannot do anything...
280 if (!DomSetInfo.dominates(Store, Load))
283 BasicBlock *BB1 = Store->getParent(), *BB2 = Load->getParent();
284 Value *LoadAddress = Load->getOperand(0);
286 assert(LoadAddress->getType() == Store->getOperand(1)->getType() &&
287 "How could the same source pointer return different types?");
289 // Find out how many bytes of memory are loaded by the load instruction...
290 unsigned LoadSize = getAnalysis<TargetData>().getTypeSize(Load->getType());
292 // Compute a basic block iterator pointing to the instruction after the store.
293 BasicBlock::iterator StoreIt = Store; ++StoreIt;
295 // Check to see if the intervening instructions between the two store and load
296 // include a store or call...
298 if (BB1 == BB2) { // In same basic block?
299 // In this degenerate case, no checking of global basic blocks has to occur
300 // just check the instructions BETWEEN Store & Load...
302 if (AA.canInstructionRangeModify(*StoreIt, *Load, LoadAddress, LoadSize))
303 return false; // Cannot eliminate load
305 // No instructions invalidate the stored value, they produce the same value!
308 // Make sure that there are no store instructions between the Store and the
309 // end of its basic block...
311 if (AA.canInstructionRangeModify(*StoreIt, *BB1->getTerminator(),
312 LoadAddress, LoadSize))
313 return false; // Cannot eliminate load
315 // Make sure that there are no store instructions between the start of BB2
316 // and the second load instruction...
318 if (AA.canInstructionRangeModify(BB2->front(), *Load, LoadAddress,LoadSize))
319 return false; // Cannot eliminate load
321 // Do a depth first traversal of the inverse CFG starting at L2's block,
322 // looking for L1's block. The inverse CFG is made up of the predecessor
323 // nodes of a block... so all of the edges in the graph are "backward".
325 std::set<BasicBlock*> VisitedSet;
326 for (pred_iterator PI = pred_begin(BB2), PE = pred_end(BB2); PI != PE; ++PI)
327 if (CheckForInvalidatingInst(*PI, BB1, LoadAddress, LoadSize, AA,
331 // If we passed all of these checks then we are sure that the two loads
332 // produce the same value.