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/iMemory.h"
21 #include "llvm/BasicBlock.h"
22 #include "llvm/Support/CFG.h"
27 // FIXME: This should not be a functionpass.
28 struct LoadVN : public FunctionPass, public ValueNumbering {
30 /// Pass Implementation stuff. This doesn't do any analysis.
32 bool runOnFunction(Function &) { return false; }
34 /// getAnalysisUsage - Does not modify anything. It uses Value Numbering
35 /// and Alias Analysis.
37 virtual void getAnalysisUsage(AnalysisUsage &AU) const;
39 /// getEqualNumberNodes - Return nodes with the same value number as the
40 /// specified Value. This fills in the argument vector with any equal
43 virtual void getEqualNumberNodes(Value *V1,
44 std::vector<Value*> &RetVals) const;
46 /// haveEqualValueNumber - Given two load instructions, determine if they
47 /// both produce the same value on every execution of the program, assuming
48 /// that their source operands always give the same value. This uses the
49 /// AliasAnalysis implementation to invalidate loads when stores or function
50 /// calls occur that could modify the value produced by the load.
52 bool haveEqualValueNumber(LoadInst *LI, LoadInst *LI2, AliasAnalysis &AA,
53 DominatorSet &DomSetInfo) const;
56 // Register this pass...
57 RegisterOpt<LoadVN> X("load-vn", "Load Value Numbering");
59 // Declare that we implement the ValueNumbering interface
60 RegisterAnalysisGroup<ValueNumbering, LoadVN> Y;
65 Pass *createLoadValueNumberingPass() { return new LoadVN(); }
68 /// getAnalysisUsage - Does not modify anything. It uses Value Numbering and
71 void LoadVN::getAnalysisUsage(AnalysisUsage &AU) const {
73 AU.addRequired<AliasAnalysis>();
74 AU.addRequired<ValueNumbering>();
75 AU.addRequired<DominatorSet>();
76 AU.addRequired<TargetData>();
79 // getEqualNumberNodes - Return nodes with the same value number as the
80 // specified Value. This fills in the argument vector with any equal values.
82 void LoadVN::getEqualNumberNodes(Value *V,
83 std::vector<Value*> &RetVals) const {
85 if (LoadInst *LI = dyn_cast<LoadInst>(V)) {
86 // If we have a load instruction, find all of the load instructions that use
87 // the same source operand. We implement this recursively, because there
88 // could be a load of a load of a load that are all identical. We are
89 // guaranteed that this cannot be an infinite recursion because load
90 // instructions would have to pass through a PHI node in order for there to
91 // be a cycle. The PHI node would be handled by the else case here,
92 // breaking the infinite recursion.
94 std::vector<Value*> PointerSources;
95 getEqualNumberNodes(LI->getOperand(0), PointerSources);
96 PointerSources.push_back(LI->getOperand(0));
98 Function *F = LI->getParent()->getParent();
100 // Now that we know the set of equivalent source pointers for the load
101 // instruction, look to see if there are any load candiates that are
104 std::vector<LoadInst*> CandidateLoads;
105 while (!PointerSources.empty()) {
106 Value *Source = PointerSources.back();
107 PointerSources.pop_back(); // Get a source pointer...
109 for (Value::use_iterator UI = Source->use_begin(), UE = Source->use_end();
111 if (LoadInst *Cand = dyn_cast<LoadInst>(*UI)) // Is a load of source?
112 if (Cand->getParent()->getParent() == F && // In the same function?
113 Cand != LI) // Not LI itself?
114 CandidateLoads.push_back(Cand); // Got one...
117 // Remove duplicates from the CandidateLoads list because alias analysis
118 // processing may be somewhat expensive and we don't want to do more work
121 std::sort(CandidateLoads.begin(), CandidateLoads.end());
122 CandidateLoads.erase(std::unique(CandidateLoads.begin(),
123 CandidateLoads.end()),
124 CandidateLoads.end());
126 // Get Alias Analysis...
127 AliasAnalysis &AA = getAnalysis<AliasAnalysis>();
128 DominatorSet &DomSetInfo = getAnalysis<DominatorSet>();
130 // Loop over all of the candindate loads. If they are not invalidated by
131 // stores or calls between execution of them and LI, then add them to
133 for (unsigned i = 0, e = CandidateLoads.size(); i != e; ++i)
134 if (haveEqualValueNumber(LI, CandidateLoads[i], AA, DomSetInfo))
135 RetVals.push_back(CandidateLoads[i]);
138 // Make sure passmanager doesn't try to fulfill our request with ourself!
139 assert(&getAnalysis<ValueNumbering>() != (ValueNumbering*)this &&
140 "getAnalysis() returned this!");
142 // Not a load instruction? Just chain to the base value numbering
143 // implementation to satisfy the request...
144 return getAnalysis<ValueNumbering>().getEqualNumberNodes(V, RetVals);
148 // CheckForInvalidatingInst - Return true if BB or any of the predecessors of BB
149 // (until DestBB) contain an instruction that might invalidate Ptr.
151 static bool CheckForInvalidatingInst(BasicBlock *BB, BasicBlock *DestBB,
152 Value *Ptr, unsigned Size,
154 std::set<BasicBlock*> &VisitedSet) {
155 // Found the termination point!
156 if (BB == DestBB || VisitedSet.count(BB)) return false;
158 // Avoid infinite recursion!
159 VisitedSet.insert(BB);
161 // Can this basic block modify Ptr?
162 if (AA.canBasicBlockModify(*BB, Ptr, Size))
165 // Check all of our predecessor blocks...
166 for (pred_iterator PI = pred_begin(BB), PE = pred_end(BB); PI != PE; ++PI)
167 if (CheckForInvalidatingInst(*PI, DestBB, Ptr, Size, AA, VisitedSet))
170 // None of our predecessor blocks contain an invalidating instruction, and we
176 /// haveEqualValueNumber - Given two load instructions, determine if they both
177 /// produce the same value on every execution of the program, assuming that
178 /// their source operands always give the same value. This uses the
179 /// AliasAnalysis implementation to invalidate loads when stores or function
180 /// calls occur that could modify the value produced by the load.
182 bool LoadVN::haveEqualValueNumber(LoadInst *L1, LoadInst *L2,
184 DominatorSet &DomSetInfo) const {
185 // Figure out which load dominates the other one. If neither dominates the
186 // other we cannot eliminate them.
188 // FIXME: This could be enhanced to some cases with a shared dominator!
190 if (DomSetInfo.dominates(L2, L1))
191 std::swap(L1, L2); // Make L1 dominate L2
192 else if (!DomSetInfo.dominates(L1, L2))
193 return false; // Neither instruction dominates the other one...
195 BasicBlock *BB1 = L1->getParent(), *BB2 = L2->getParent();
196 Value *LoadAddress = L1->getOperand(0);
198 assert(L1->getType() == L2->getType() &&
199 "How could the same source pointer return different types?");
201 // Find out how many bytes of memory are loaded by the load instruction...
202 unsigned LoadSize = getAnalysis<TargetData>().getTypeSize(L1->getType());
204 // L1 now dominates L2. Check to see if the intervening instructions between
205 // the two loads include a store or call...
207 if (BB1 == BB2) { // In same basic block?
208 // In this degenerate case, no checking of global basic blocks has to occur
209 // just check the instructions BETWEEN L1 & L2...
211 if (AA.canInstructionRangeModify(*L1, *L2, LoadAddress, LoadSize))
212 return false; // Cannot eliminate load
214 // No instructions invalidate the loads, they produce the same value!
217 // Make sure that there are no store instructions between L1 and the end of
218 // it's basic block...
220 if (AA.canInstructionRangeModify(*L1, *BB1->getTerminator(), LoadAddress,
222 return false; // Cannot eliminate load
224 // Make sure that there are no store instructions between the start of BB2
225 // and the second load instruction...
227 if (AA.canInstructionRangeModify(BB2->front(), *L2, LoadAddress, LoadSize))
228 return false; // Cannot eliminate load
230 // Do a depth first traversal of the inverse CFG starting at L2's block,
231 // looking for L1's block. The inverse CFG is made up of the predecessor
232 // nodes of a block... so all of the edges in the graph are "backward".
234 std::set<BasicBlock*> VisitedSet;
235 for (pred_iterator PI = pred_begin(BB2), PE = pred_end(BB2); PI != PE; ++PI)
236 if (CheckForInvalidatingInst(*PI, BB1, LoadAddress, LoadSize, AA,
240 // If we passed all of these checks then we are sure that the two loads
241 // produce the same value.