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"
35 // FIXME: This should not be a FunctionPass.
36 struct LoadVN : public FunctionPass, public ValueNumbering {
38 /// Pass Implementation stuff. This doesn't do any analysis.
40 bool runOnFunction(Function &) { return false; }
42 /// getAnalysisUsage - Does not modify anything. It uses Value Numbering
43 /// and Alias Analysis.
45 virtual void getAnalysisUsage(AnalysisUsage &AU) const;
47 /// getEqualNumberNodes - Return nodes with the same value number as the
48 /// specified Value. This fills in the argument vector with any equal
51 virtual void getEqualNumberNodes(Value *V1,
52 std::vector<Value*> &RetVals) const;
55 // Register this pass...
56 RegisterOpt<LoadVN> X("load-vn", "Load Value Numbering");
58 // Declare that we implement the ValueNumbering interface
59 RegisterAnalysisGroup<ValueNumbering, LoadVN> Y;
62 Pass *llvm::createLoadValueNumberingPass() { return new LoadVN(); }
65 /// getAnalysisUsage - Does not modify anything. It uses Value Numbering and
68 void LoadVN::getAnalysisUsage(AnalysisUsage &AU) const {
70 AU.addRequired<AliasAnalysis>();
71 AU.addRequired<ValueNumbering>();
72 AU.addRequired<DominatorSet>();
73 AU.addRequired<TargetData>();
76 static bool isPathTransparentTo(BasicBlock *CurBlock, BasicBlock *Dom,
77 Value *Ptr, unsigned Size, AliasAnalysis &AA,
78 std::set<BasicBlock*> &Visited,
79 std::map<BasicBlock*, bool> &TransparentBlocks){
80 // If we have already checked out this path, or if we reached our destination,
81 // stop searching, returning success.
82 if (CurBlock == Dom || !Visited.insert(CurBlock).second)
85 // Check whether this block is known transparent or not.
86 std::map<BasicBlock*, bool>::iterator TBI =
87 TransparentBlocks.lower_bound(CurBlock);
89 if (TBI == TransparentBlocks.end() || TBI->first != CurBlock) {
90 // If this basic block can modify the memory location, then the path is not
92 if (AA.canBasicBlockModify(*CurBlock, Ptr, Size)) {
93 TransparentBlocks.insert(TBI, std::make_pair(CurBlock, false));
96 TransparentBlocks.insert(TBI, std::make_pair(CurBlock, true));
97 } else if (!TBI->second)
98 // This block is known non-transparent, so that path can't be either.
101 // The current block is known to be transparent. The entire path is
102 // transparent if all of the predecessors paths to the parent is also
103 // transparent to the memory location.
104 for (pred_iterator PI = pred_begin(CurBlock), E = pred_end(CurBlock);
106 if (!isPathTransparentTo(*PI, Dom, Ptr, Size, AA, Visited,
113 // getEqualNumberNodes - Return nodes with the same value number as the
114 // specified Value. This fills in the argument vector with any equal values.
116 void LoadVN::getEqualNumberNodes(Value *V,
117 std::vector<Value*> &RetVals) const {
118 // If the alias analysis has any must alias information to share with us, we
119 // can definitely use it.
120 if (isa<PointerType>(V->getType()))
121 getAnalysis<AliasAnalysis>().getMustAliases(V, RetVals);
123 if (!isa<LoadInst>(V)) {
124 // Not a load instruction? Just chain to the base value numbering
125 // implementation to satisfy the request...
126 assert(&getAnalysis<ValueNumbering>() != (ValueNumbering*)this &&
127 "getAnalysis() returned this!");
129 return getAnalysis<ValueNumbering>().getEqualNumberNodes(V, RetVals);
132 // Volatile loads cannot be replaced with the value of other loads.
133 LoadInst *LI = cast<LoadInst>(V);
134 if (LI->isVolatile())
135 return getAnalysis<ValueNumbering>().getEqualNumberNodes(V, RetVals);
137 // If we have a load instruction, find all of the load and store instructions
138 // that use the same source operand. We implement this recursively, because
139 // there could be a load of a load of a load that are all identical. We are
140 // guaranteed that this cannot be an infinite recursion because load
141 // instructions would have to pass through a PHI node in order for there to be
142 // a cycle. The PHI node would be handled by the else case here, breaking the
143 // infinite recursion.
145 std::vector<Value*> PointerSources;
146 getEqualNumberNodes(LI->getOperand(0), PointerSources);
147 PointerSources.push_back(LI->getOperand(0));
149 BasicBlock *LoadBB = LI->getParent();
150 Function *F = LoadBB->getParent();
152 // Now that we know the set of equivalent source pointers for the load
153 // instruction, look to see if there are any load or store candidates that are
156 std::map<BasicBlock*, std::vector<LoadInst*> > CandidateLoads;
157 std::map<BasicBlock*, std::vector<StoreInst*> > CandidateStores;
159 while (!PointerSources.empty()) {
160 Value *Source = PointerSources.back();
161 PointerSources.pop_back(); // Get a source pointer...
163 for (Value::use_iterator UI = Source->use_begin(), UE = Source->use_end();
165 if (LoadInst *Cand = dyn_cast<LoadInst>(*UI)) {// Is a load of source?
166 if (Cand->getParent()->getParent() == F && // In the same function?
167 Cand != LI && !Cand->isVolatile()) // Not LI itself?
168 CandidateLoads[Cand->getParent()].push_back(Cand); // Got one...
169 } else if (StoreInst *Cand = dyn_cast<StoreInst>(*UI)) {
170 if (Cand->getParent()->getParent() == F && !Cand->isVolatile() &&
171 Cand->getOperand(1) == Source) // It's a store THROUGH the ptr...
172 CandidateStores[Cand->getParent()].push_back(Cand);
176 // Get alias analysis & dominators.
177 AliasAnalysis &AA = getAnalysis<AliasAnalysis>();
178 DominatorSet &DomSetInfo = getAnalysis<DominatorSet>();
179 Value *LoadPtr = LI->getOperand(0);
180 // Find out how many bytes of memory are loaded by the load instruction...
181 unsigned LoadSize = getAnalysis<TargetData>().getTypeSize(LI->getType());
183 // Find all of the candidate loads and stores that are in the same block as
184 // the defining instruction.
185 std::set<Instruction*> Instrs;
186 Instrs.insert(CandidateLoads[LoadBB].begin(), CandidateLoads[LoadBB].end());
187 CandidateLoads.erase(LoadBB);
188 Instrs.insert(CandidateStores[LoadBB].begin(), CandidateStores[LoadBB].end());
189 CandidateStores.erase(LoadBB);
191 // Figure out if the load is invalidated from the entry of the block it is in
192 // until the actual instruction. This scans the block backwards from LI. If
193 // we see any candidate load or store instructions, then we know that the
194 // candidates have the same value # as LI.
195 bool LoadInvalidatedInBBBefore = false;
196 for (BasicBlock::iterator I = LI; I != LoadBB->begin(); ) {
198 // If this instruction is a candidate load before LI, we know there are no
199 // invalidating instructions between it and LI, so they have the same value
201 if (isa<LoadInst>(I) && Instrs.count(I)) {
202 RetVals.push_back(I);
206 if (AA.getModRefInfo(I, LoadPtr, LoadSize) & AliasAnalysis::Mod) {
207 // If the invalidating instruction is a store, and its in our candidate
208 // set, then we can do store-load forwarding: the load has the same value
209 // # as the stored value.
210 if (isa<StoreInst>(I) && Instrs.count(I)) {
212 RetVals.push_back(I->getOperand(0));
215 LoadInvalidatedInBBBefore = true;
220 // Figure out if the load is invalidated between the load and the exit of the
221 // block it is defined in. While we are scanning the current basic block, if
222 // we see any candidate loads, then we know they have the same value # as LI.
224 bool LoadInvalidatedInBBAfter = false;
225 for (BasicBlock::iterator I = LI->getNext(); I != LoadBB->end(); ++I) {
226 // If this instruction is a load, then this instruction returns the same
228 if (isa<LoadInst>(I) && Instrs.count(I)) {
229 RetVals.push_back(I);
233 if (AA.getModRefInfo(I, LoadPtr, LoadSize) & AliasAnalysis::Mod) {
234 LoadInvalidatedInBBAfter = true;
239 // If there is anything left in the Instrs set, it could not possibly equal
243 // TransparentBlocks - For each basic block the load/store is alive across,
244 // figure out if the pointer is invalidated or not. If it is invalidated, the
245 // boolean is set to false, if it's not it is set to true. If we don't know
246 // yet, the entry is not in the map.
247 std::map<BasicBlock*, bool> TransparentBlocks;
249 // Loop over all of the basic blocks that also load the value. If the value
250 // is live across the CFG from the source to destination blocks, and if the
251 // value is not invalidated in either the source or destination blocks, add it
252 // to the equivalence sets.
253 for (std::map<BasicBlock*, std::vector<LoadInst*> >::iterator
254 I = CandidateLoads.begin(), E = CandidateLoads.end(); I != E; ++I) {
255 bool CantEqual = false;
257 // Right now we only can handle cases where one load dominates the other.
258 // FIXME: generalize this!
259 BasicBlock *BB1 = I->first, *BB2 = LoadBB;
260 if (DomSetInfo.dominates(BB1, BB2)) {
261 // The other load dominates LI. If the loaded value is killed entering
262 // the LoadBB block, we know the load is not live.
263 if (LoadInvalidatedInBBBefore)
265 } else if (DomSetInfo.dominates(BB2, BB1)) {
266 std::swap(BB1, BB2); // Canonicalize
267 // LI dominates the other load. If the loaded value is killed exiting
268 // the LoadBB block, we know the load is not live.
269 if (LoadInvalidatedInBBAfter)
272 // None of these loads can VN the same.
277 // Ok, at this point, we know that BB1 dominates BB2, and that there is
278 // nothing in the LI block that kills the loaded value. Check to see if
279 // the value is live across the CFG.
280 std::set<BasicBlock*> Visited;
281 for (pred_iterator PI = pred_begin(BB2), E = pred_end(BB2); PI!=E; ++PI)
282 if (!isPathTransparentTo(*PI, BB1, LoadPtr, LoadSize, AA,
283 Visited, TransparentBlocks)) {
284 // None of these loads can VN the same.
290 // If the loads can equal so far, scan the basic block that contains the
291 // loads under consideration to see if they are invalidated in the block.
292 // For any loads that are not invalidated, add them to the equivalence
295 Instrs.insert(I->second.begin(), I->second.end());
297 // If LI dominates the block in question, check to see if any of the
298 // loads in this block are invalidated before they are reached.
299 for (BasicBlock::iterator BBI = I->first->begin(); ; ++BBI) {
300 if (isa<LoadInst>(BBI) && Instrs.count(BBI)) {
301 // The load is in the set!
302 RetVals.push_back(BBI);
304 if (Instrs.empty()) break;
305 } else if (AA.getModRefInfo(BBI, LoadPtr, LoadSize)
306 & AliasAnalysis::Mod) {
307 // If there is a modifying instruction, nothing below it will value
313 // If the block dominates LI, make sure that the loads in the block are
314 // not invalidated before the block ends.
315 BasicBlock::iterator BBI = I->first->end();
318 if (isa<LoadInst>(BBI) && Instrs.count(BBI)) {
319 // The load is in the set!
320 RetVals.push_back(BBI);
322 if (Instrs.empty()) break;
323 } else if (AA.getModRefInfo(BBI, LoadPtr, LoadSize)
324 & AliasAnalysis::Mod) {
325 // If there is a modifying instruction, nothing above it will value
336 // Handle candidate stores. If the loaded location is clobbered on entrance
337 // to the LoadBB, no store outside of the LoadBB can value number equal, so
339 if (LoadInvalidatedInBBBefore)
342 for (std::map<BasicBlock*, std::vector<StoreInst*> >::iterator
343 I = CandidateStores.begin(), E = CandidateStores.end(); I != E; ++I)
344 if (DomSetInfo.dominates(I->first, LoadBB)) {
345 // Check to see if the path from the store to the load is transparent
346 // w.r.t. the memory location.
347 bool CantEqual = false;
348 std::set<BasicBlock*> Visited;
349 for (pred_iterator PI = pred_begin(LoadBB), E = pred_end(LoadBB);
351 if (!isPathTransparentTo(*PI, I->first, LoadPtr, LoadSize, AA,
352 Visited, TransparentBlocks)) {
353 // None of these stores can VN the same.
359 // Okay, the path from the store block to the load block is clear, and
360 // we know that there are no invalidating instructions from the start
361 // of the load block to the load itself. Now we just scan the store
364 BasicBlock::iterator BBI = I->first->end();
367 if (AA.getModRefInfo(BBI, LoadPtr, LoadSize)& AliasAnalysis::Mod){
368 // If the invalidating instruction is one of the candidates,
369 // then it provides the value the load loads.
370 if (StoreInst *SI = dyn_cast<StoreInst>(BBI))
371 if (std::find(I->second.begin(), I->second.end(), SI) !=
373 RetVals.push_back(SI->getOperand(0));