/Users/buildslave/jenkins/sharedspace/clang-stage2-coverage-R@2/llvm/lib/Transforms/Utils/SSAUpdater.cpp
Line | Count | Source (jump to first uncovered line) |
1 | | //===- SSAUpdater.cpp - Unstructured SSA Update Tool ----------------------===// |
2 | | // |
3 | | // The LLVM Compiler Infrastructure |
4 | | // |
5 | | // This file is distributed under the University of Illinois Open Source |
6 | | // License. See LICENSE.TXT for details. |
7 | | // |
8 | | //===----------------------------------------------------------------------===// |
9 | | // |
10 | | // This file implements the SSAUpdater class. |
11 | | // |
12 | | //===----------------------------------------------------------------------===// |
13 | | |
14 | | #include "llvm/Transforms/Utils/SSAUpdater.h" |
15 | | #include "llvm/ADT/DenseMap.h" |
16 | | #include "llvm/ADT/STLExtras.h" |
17 | | #include "llvm/ADT/SmallVector.h" |
18 | | #include "llvm/ADT/StringRef.h" |
19 | | #include "llvm/ADT/TinyPtrVector.h" |
20 | | #include "llvm/Analysis/InstructionSimplify.h" |
21 | | #include "llvm/IR/BasicBlock.h" |
22 | | #include "llvm/IR/CFG.h" |
23 | | #include "llvm/IR/Constants.h" |
24 | | #include "llvm/IR/DebugLoc.h" |
25 | | #include "llvm/IR/Instruction.h" |
26 | | #include "llvm/IR/Instructions.h" |
27 | | #include "llvm/IR/Module.h" |
28 | | #include "llvm/IR/Use.h" |
29 | | #include "llvm/IR/Value.h" |
30 | | #include "llvm/IR/ValueHandle.h" |
31 | | #include "llvm/Support/Casting.h" |
32 | | #include "llvm/Support/Debug.h" |
33 | | #include "llvm/Support/raw_ostream.h" |
34 | | #include "llvm/Transforms/Utils/SSAUpdaterImpl.h" |
35 | | #include <cassert> |
36 | | #include <utility> |
37 | | |
38 | | using namespace llvm; |
39 | | |
40 | | #define DEBUG_TYPE "ssaupdater" |
41 | | |
42 | | typedef DenseMap<BasicBlock*, Value*> AvailableValsTy; |
43 | 5.68M | static AvailableValsTy &getAvailableVals(void *AV) { |
44 | 5.68M | return *static_cast<AvailableValsTy*>(AV); |
45 | 5.68M | } |
46 | | |
47 | | SSAUpdater::SSAUpdater(SmallVectorImpl<PHINode*> *NewPHI) |
48 | 1.21M | : InsertedPHIs(NewPHI) {} |
49 | | |
50 | 1.21M | SSAUpdater::~SSAUpdater() { |
51 | 1.21M | delete static_cast<AvailableValsTy*>(AV); |
52 | 1.21M | } |
53 | | |
54 | 1.32M | void SSAUpdater::Initialize(Type *Ty, StringRef Name) { |
55 | 1.32M | if (!AV) |
56 | 1.19M | AV = new AvailableValsTy(); |
57 | 1.32M | else |
58 | 132k | getAvailableVals(AV).clear(); |
59 | 1.32M | ProtoType = Ty; |
60 | 1.32M | ProtoName = Name; |
61 | 1.32M | } |
62 | | |
63 | 2.39M | bool SSAUpdater::HasValueForBlock(BasicBlock *BB) const { |
64 | 2.39M | return getAvailableVals(AV).count(BB); |
65 | 2.39M | } |
66 | | |
67 | 1.95M | void SSAUpdater::AddAvailableValue(BasicBlock *BB, Value *V) { |
68 | 1.95M | assert(ProtoType && "Need to initialize SSAUpdater"); |
69 | 1.95M | assert(ProtoType == V->getType() && |
70 | 1.95M | "All rewritten values must have the same type"); |
71 | 1.95M | getAvailableVals(AV)[BB] = V; |
72 | 1.95M | } |
73 | | |
74 | | static bool IsEquivalentPHI(PHINode *PHI, |
75 | 79.8k | SmallDenseMap<BasicBlock*, Value*, 8> &ValueMapping) { |
76 | 79.8k | unsigned PHINumValues = PHI->getNumIncomingValues(); |
77 | 79.8k | if (PHINumValues != ValueMapping.size()) |
78 | 20 | return false; |
79 | 79.7k | |
80 | 79.7k | // Scan the phi to see if it matches. |
81 | 204k | for (unsigned i = 0, e = PHINumValues; 79.7k i != e204k ; ++i124k ) |
82 | 143k | if (143k ValueMapping[PHI->getIncomingBlock(i)] != |
83 | 143k | PHI->getIncomingValue(i)) { |
84 | 18.0k | return false; |
85 | 18.0k | } |
86 | 79.7k | |
87 | 61.7k | return true; |
88 | 79.8k | } |
89 | | |
90 | 1.19M | Value *SSAUpdater::GetValueAtEndOfBlock(BasicBlock *BB) { |
91 | 1.19M | Value *Res = GetValueAtEndOfBlockInternal(BB); |
92 | 1.19M | return Res; |
93 | 1.19M | } |
94 | | |
95 | 772k | Value *SSAUpdater::GetValueInMiddleOfBlock(BasicBlock *BB) { |
96 | 772k | // If there is no definition of the renamed variable in this block, just use |
97 | 772k | // GetValueAtEndOfBlock to do our work. |
98 | 772k | if (!HasValueForBlock(BB)) |
99 | 500k | return GetValueAtEndOfBlock(BB); |
100 | 271k | |
101 | 271k | // Otherwise, we have the hard case. Get the live-in values for each |
102 | 271k | // predecessor. |
103 | 271k | SmallVector<std::pair<BasicBlock*, Value*>, 8> PredValues; |
104 | 271k | Value *SingularValue = nullptr; |
105 | 271k | |
106 | 271k | // We can get our predecessor info by walking the pred_iterator list, but it |
107 | 271k | // is relatively slow. If we already have PHI nodes in this block, walk one |
108 | 271k | // of them to get the predecessor list instead. |
109 | 271k | if (PHINode *SomePhi271k = dyn_cast<PHINode>(BB->begin())) { |
110 | 270k | for (unsigned i = 0, e = SomePhi->getNumIncomingValues(); i != e270k ; ++i182k ) { |
111 | 182k | BasicBlock *PredBB = SomePhi->getIncomingBlock(i); |
112 | 182k | Value *PredVal = GetValueAtEndOfBlock(PredBB); |
113 | 182k | PredValues.push_back(std::make_pair(PredBB, PredVal)); |
114 | 182k | |
115 | 182k | // Compute SingularValue. |
116 | 182k | if (i == 0) |
117 | 88.0k | SingularValue = PredVal; |
118 | 94.1k | else if (94.1k PredVal != SingularValue94.1k ) |
119 | 69.7k | SingularValue = nullptr; |
120 | 182k | } |
121 | 271k | } else { |
122 | 183k | bool isFirstPred = true; |
123 | 453k | for (pred_iterator PI = pred_begin(BB), E = pred_end(BB); PI != E453k ; ++PI269k ) { |
124 | 269k | BasicBlock *PredBB = *PI; |
125 | 269k | Value *PredVal = GetValueAtEndOfBlock(PredBB); |
126 | 269k | PredValues.push_back(std::make_pair(PredBB, PredVal)); |
127 | 269k | |
128 | 269k | // Compute SingularValue. |
129 | 269k | if (isFirstPred269k ) { |
130 | 183k | SingularValue = PredVal; |
131 | 183k | isFirstPred = false; |
132 | 269k | } else if (85.7k PredVal != SingularValue85.7k ) |
133 | 2.16k | SingularValue = nullptr; |
134 | 269k | } |
135 | 183k | } |
136 | 271k | |
137 | 271k | // If there are no predecessors, just return undef. |
138 | 271k | if (PredValues.empty()) |
139 | 0 | return UndefValue::get(ProtoType); |
140 | 271k | |
141 | 271k | // Otherwise, if all the merged values are the same, just use it. |
142 | 271k | if (271k SingularValue271k ) |
143 | 201k | return SingularValue; |
144 | 70.3k | |
145 | 70.3k | // Otherwise, we do need a PHI: check to see if we already have one available |
146 | 70.3k | // in this block that produces the right value. |
147 | 70.3k | if (70.3k isa<PHINode>(BB->begin())70.3k ) { |
148 | 68.2k | SmallDenseMap<BasicBlock*, Value*, 8> ValueMapping(PredValues.begin(), |
149 | 68.2k | PredValues.end()); |
150 | 68.2k | PHINode *SomePHI; |
151 | 68.2k | for (BasicBlock::iterator It = BB->begin(); |
152 | 86.3k | (SomePHI = dyn_cast<PHINode>(It))86.3k ; ++It18.0k ) { |
153 | 79.8k | if (IsEquivalentPHI(SomePHI, ValueMapping)) |
154 | 61.7k | return SomePHI; |
155 | 79.8k | } |
156 | 68.2k | } |
157 | 70.3k | |
158 | 70.3k | // Ok, we have no way out, insert a new one now. |
159 | 8.56k | PHINode *InsertedPHI = PHINode::Create(ProtoType, PredValues.size(), |
160 | 8.56k | ProtoName, &BB->front()); |
161 | 8.56k | |
162 | 8.56k | // Fill in all the predecessors of the PHI. |
163 | 8.56k | for (const auto &PredValue : PredValues) |
164 | 18.0k | InsertedPHI->addIncoming(PredValue.second, PredValue.first); |
165 | 8.56k | |
166 | 8.56k | // See if the PHI node can be merged to a single value. This can happen in |
167 | 8.56k | // loop cases when we get a PHI of itself and one other value. |
168 | 8.56k | if (Value *V = |
169 | 0 | SimplifyInstruction(InsertedPHI, BB->getModule()->getDataLayout())) { |
170 | 0 | InsertedPHI->eraseFromParent(); |
171 | 0 | return V; |
172 | 0 | } |
173 | 8.56k | |
174 | 8.56k | // Set the DebugLoc of the inserted PHI, if available. |
175 | 8.56k | DebugLoc DL; |
176 | 8.56k | if (const Instruction *I = BB->getFirstNonPHI()) |
177 | 8.56k | DL = I->getDebugLoc(); |
178 | 8.56k | InsertedPHI->setDebugLoc(DL); |
179 | 8.56k | |
180 | 8.56k | // If the client wants to know about all new instructions, tell it. |
181 | 8.56k | if (InsertedPHIs8.56k ) InsertedPHIs->push_back(InsertedPHI)8.42k ; |
182 | 8.56k | |
183 | 8.56k | DEBUG(dbgs() << " Inserted PHI: " << *InsertedPHI << "\n"); |
184 | 772k | return InsertedPHI; |
185 | 772k | } |
186 | | |
187 | 971k | void SSAUpdater::RewriteUse(Use &U) { |
188 | 971k | Instruction *User = cast<Instruction>(U.getUser()); |
189 | 971k | |
190 | 971k | Value *V; |
191 | 971k | if (PHINode *UserPN = dyn_cast<PHINode>(User)) |
192 | 244k | V = GetValueAtEndOfBlock(UserPN->getIncomingBlock(U)); |
193 | 971k | else |
194 | 727k | V = GetValueInMiddleOfBlock(User->getParent()); |
195 | 971k | |
196 | 971k | // Notify that users of the existing value that it is being replaced. |
197 | 971k | Value *OldVal = U.get(); |
198 | 971k | if (OldVal != V && 971k OldVal->hasValueHandle()917k ) |
199 | 89.9k | ValueHandleBase::ValueIsRAUWd(OldVal, V); |
200 | 971k | |
201 | 971k | U.set(V); |
202 | 971k | } |
203 | | |
204 | 47 | void SSAUpdater::RewriteUseAfterInsertions(Use &U) { |
205 | 47 | Instruction *User = cast<Instruction>(U.getUser()); |
206 | 47 | |
207 | 47 | Value *V; |
208 | 47 | if (PHINode *UserPN = dyn_cast<PHINode>(User)) |
209 | 35 | V = GetValueAtEndOfBlock(UserPN->getIncomingBlock(U)); |
210 | 47 | else |
211 | 12 | V = GetValueAtEndOfBlock(User->getParent()); |
212 | 47 | |
213 | 47 | U.set(V); |
214 | 47 | } |
215 | | |
216 | | namespace llvm { |
217 | | |
218 | | template<> |
219 | | class SSAUpdaterTraits<SSAUpdater> { |
220 | | public: |
221 | | typedef BasicBlock BlkT; |
222 | | typedef Value *ValT; |
223 | | typedef PHINode PhiT; |
224 | | |
225 | | typedef succ_iterator BlkSucc_iterator; |
226 | 4.40M | static BlkSucc_iterator BlkSucc_begin(BlkT *BB) { return succ_begin(BB); } |
227 | 4.40M | static BlkSucc_iterator BlkSucc_end(BlkT *BB) { return succ_end(BB); } |
228 | | |
229 | | class PHI_iterator { |
230 | | private: |
231 | | PHINode *PHI; |
232 | | unsigned idx; |
233 | | |
234 | | public: |
235 | | explicit PHI_iterator(PHINode *P) // begin iterator |
236 | 437k | : PHI(P), idx(0) {} |
237 | | PHI_iterator(PHINode *P, bool) // end iterator |
238 | 437k | : PHI(P), idx(PHI->getNumIncomingValues()) {} |
239 | | |
240 | 180k | PHI_iterator &operator++() { ++idx; return *this; } |
241 | 618k | bool operator==(const PHI_iterator& x) const { return idx == x.idx; } |
242 | 618k | bool operator!=(const PHI_iterator& x) const { return !operator==(x); } |
243 | | |
244 | 559k | Value *getIncomingValue() { return PHI->getIncomingValue(idx); } |
245 | 559k | BasicBlock *getIncomingBlock() { return PHI->getIncomingBlock(idx); } |
246 | | }; |
247 | | |
248 | 437k | static PHI_iterator PHI_begin(PhiT *PHI) { return PHI_iterator(PHI); } |
249 | 437k | static PHI_iterator PHI_end(PhiT *PHI) { |
250 | 437k | return PHI_iterator(PHI, true); |
251 | 437k | } |
252 | | |
253 | | /// FindPredecessorBlocks - Put the predecessors of Info->BB into the Preds |
254 | | /// vector, set Info->NumPreds, and allocate space in Info->Preds. |
255 | | static void FindPredecessorBlocks(BasicBlock *BB, |
256 | 3.37M | SmallVectorImpl<BasicBlock*> *Preds) { |
257 | 3.37M | // We can get our predecessor info by walking the pred_iterator list, |
258 | 3.37M | // but it is relatively slow. If we already have PHI nodes in this |
259 | 3.37M | // block, walk one of them to get the predecessor list instead. |
260 | 3.37M | if (PHINode *SomePhi3.37M = dyn_cast<PHINode>(BB->begin())) { |
261 | 752k | Preds->append(SomePhi->block_begin(), SomePhi->block_end()); |
262 | 3.37M | } else { |
263 | 5.63M | for (pred_iterator PI = pred_begin(BB), E = pred_end(BB); PI != E5.63M ; ++PI3.01M ) |
264 | 3.01M | Preds->push_back(*PI); |
265 | 2.62M | } |
266 | 3.37M | } |
267 | | |
268 | | /// GetUndefVal - Get an undefined value of the same type as the value |
269 | | /// being handled. |
270 | 13 | static Value *GetUndefVal(BasicBlock *BB, SSAUpdater *Updater) { |
271 | 13 | return UndefValue::get(Updater->ProtoType); |
272 | 13 | } |
273 | | |
274 | | /// CreateEmptyPHI - Create a new PHI instruction in the specified block. |
275 | | /// Reserve space for the operands but do not fill them in yet. |
276 | | static Value *CreateEmptyPHI(BasicBlock *BB, unsigned NumPreds, |
277 | 171k | SSAUpdater *Updater) { |
278 | 171k | PHINode *PHI = PHINode::Create(Updater->ProtoType, NumPreds, |
279 | 171k | Updater->ProtoName, &BB->front()); |
280 | 171k | return PHI; |
281 | 171k | } |
282 | | |
283 | | /// AddPHIOperand - Add the specified value as an operand of the PHI for |
284 | | /// the specified predecessor block. |
285 | 380k | static void AddPHIOperand(PHINode *PHI, Value *Val, BasicBlock *Pred) { |
286 | 380k | PHI->addIncoming(Val, Pred); |
287 | 380k | } |
288 | | |
289 | | /// InstrIsPHI - Check if an instruction is a PHI. |
290 | | /// |
291 | 566k | static PHINode *InstrIsPHI(Instruction *I) { |
292 | 566k | return dyn_cast<PHINode>(I); |
293 | 566k | } |
294 | | |
295 | | /// ValueIsPHI - Check if a value is a PHI. |
296 | | /// |
297 | 318k | static PHINode *ValueIsPHI(Value *Val, SSAUpdater *Updater) { |
298 | 318k | return dyn_cast<PHINode>(Val); |
299 | 318k | } |
300 | | |
301 | | /// ValueIsNewPHI - Like ValueIsPHI but also check if the PHI has no source |
302 | | /// operands, i.e., it was just added. |
303 | 187k | static PHINode *ValueIsNewPHI(Value *Val, SSAUpdater *Updater) { |
304 | 187k | PHINode *PHI = ValueIsPHI(Val, Updater); |
305 | 187k | if (PHI && 187k PHI->getNumIncomingValues() == 0187k ) |
306 | 171k | return PHI; |
307 | 16.2k | return nullptr; |
308 | 16.2k | } |
309 | | |
310 | | /// GetPHIValue - For the specified PHI instruction, return the value |
311 | | /// that it defines. |
312 | 58.6k | static Value *GetPHIValue(PHINode *PHI) { |
313 | 58.6k | return PHI; |
314 | 58.6k | } |
315 | | }; |
316 | | |
317 | | } // end namespace llvm |
318 | | |
319 | | /// Check to see if AvailableVals has an entry for the specified BB and if so, |
320 | | /// return it. If not, construct SSA form by first calculating the required |
321 | | /// placement of PHIs and then inserting new PHIs where needed. |
322 | 1.19M | Value *SSAUpdater::GetValueAtEndOfBlockInternal(BasicBlock *BB) { |
323 | 1.19M | AvailableValsTy &AvailableVals = getAvailableVals(AV); |
324 | 1.19M | if (Value *V = AvailableVals[BB]) |
325 | 351k | return V; |
326 | 847k | |
327 | 847k | SSAUpdaterImpl<SSAUpdater> Impl(this, &AvailableVals, InsertedPHIs); |
328 | 847k | return Impl.GetValue(BB); |
329 | 847k | } |
330 | | |
331 | | //===----------------------------------------------------------------------===// |
332 | | // LoadAndStorePromoter Implementation |
333 | | //===----------------------------------------------------------------------===// |
334 | | |
335 | | LoadAndStorePromoter:: |
336 | | LoadAndStorePromoter(ArrayRef<const Instruction*> Insts, |
337 | 2.54k | SSAUpdater &S, StringRef BaseName) : SSA(S) { |
338 | 2.54k | if (Insts.empty()2.54k ) return0 ; |
339 | 2.54k | |
340 | 2.54k | const Value *SomeVal; |
341 | 2.54k | if (const LoadInst *LI = dyn_cast<LoadInst>(Insts[0])) |
342 | 393 | SomeVal = LI; |
343 | 2.54k | else |
344 | 2.15k | SomeVal = cast<StoreInst>(Insts[0])->getOperand(0); |
345 | 2.54k | |
346 | 2.54k | if (BaseName.empty()) |
347 | 2.54k | BaseName = SomeVal->getName(); |
348 | 2.54k | SSA.Initialize(SomeVal->getType(), BaseName); |
349 | 2.54k | } |
350 | | |
351 | | void LoadAndStorePromoter:: |
352 | 2.54k | run(const SmallVectorImpl<Instruction*> &Insts) const { |
353 | 2.54k | // First step: bucket up uses of the alloca by the block they occur in. |
354 | 2.54k | // This is important because we have to handle multiple defs/uses in a block |
355 | 2.54k | // ourselves: SSAUpdater is purely for cross-block references. |
356 | 2.54k | DenseMap<BasicBlock*, TinyPtrVector<Instruction*>> UsesByBlock; |
357 | 2.54k | |
358 | 2.54k | for (Instruction *User : Insts) |
359 | 4.88k | UsesByBlock[User->getParent()].push_back(User); |
360 | 2.54k | |
361 | 2.54k | // Okay, now we can iterate over all the blocks in the function with uses, |
362 | 2.54k | // processing them. Keep track of which loads are loading a live-in value. |
363 | 2.54k | // Walk the uses in the use-list order to be determinstic. |
364 | 2.54k | SmallVector<LoadInst*, 32> LiveInLoads; |
365 | 2.54k | DenseMap<Value*, Value*> ReplacedLoads; |
366 | 2.54k | |
367 | 4.88k | for (Instruction *User : Insts) { |
368 | 4.88k | BasicBlock *BB = User->getParent(); |
369 | 4.88k | TinyPtrVector<Instruction*> &BlockUses = UsesByBlock[BB]; |
370 | 4.88k | |
371 | 4.88k | // If this block has already been processed, ignore this repeat use. |
372 | 4.88k | if (BlockUses.empty()4.88k ) continue1.69k ; |
373 | 3.19k | |
374 | 3.19k | // Okay, this is the first use in the block. If this block just has a |
375 | 3.19k | // single user in it, we can rewrite it trivially. |
376 | 3.19k | if (3.19k BlockUses.size() == 13.19k ) { |
377 | 1.94k | // If it is a store, it is a trivial def of the value in the block. |
378 | 1.94k | if (StoreInst *SI1.94k = dyn_cast<StoreInst>(User)) { |
379 | 1.65k | updateDebugInfo(SI); |
380 | 1.65k | SSA.AddAvailableValue(BB, SI->getOperand(0)); |
381 | 1.65k | } else |
382 | 1.94k | // Otherwise it is a load, queue it to rewrite as a live-in load. |
383 | 294 | LiveInLoads.push_back(cast<LoadInst>(User)); |
384 | 1.94k | BlockUses.clear(); |
385 | 1.94k | continue; |
386 | 1.94k | } |
387 | 1.24k | |
388 | 1.24k | // Otherwise, check to see if this block is all loads. |
389 | 1.24k | bool HasStore = false; |
390 | 1.61k | for (Instruction *I : BlockUses) { |
391 | 1.61k | if (isa<StoreInst>(I)1.61k ) { |
392 | 1.20k | HasStore = true; |
393 | 1.20k | break; |
394 | 1.20k | } |
395 | 1.24k | } |
396 | 1.24k | |
397 | 1.24k | // If so, we can queue them all as live in loads. We don't have an |
398 | 1.24k | // efficient way to tell which on is first in the block and don't want to |
399 | 1.24k | // scan large blocks, so just add all loads as live ins. |
400 | 1.24k | if (!HasStore1.24k ) { |
401 | 38 | for (Instruction *I : BlockUses) |
402 | 76 | LiveInLoads.push_back(cast<LoadInst>(I)); |
403 | 38 | BlockUses.clear(); |
404 | 38 | continue; |
405 | 38 | } |
406 | 1.20k | |
407 | 1.20k | // Otherwise, we have mixed loads and stores (or just a bunch of stores). |
408 | 1.20k | // Since SSAUpdater is purely for cross-block values, we need to determine |
409 | 1.20k | // the order of these instructions in the block. If the first use in the |
410 | 1.20k | // block is a load, then it uses the live in value. The last store defines |
411 | 1.20k | // the live out value. We handle this by doing a linear scan of the block. |
412 | 1.20k | Value *StoredValue = nullptr; |
413 | 53.2k | for (Instruction &I : *BB) { |
414 | 53.2k | if (LoadInst *L53.2k = dyn_cast<LoadInst>(&I)) { |
415 | 9.43k | // If this is a load from an unrelated pointer, ignore it. |
416 | 9.43k | if (!isInstInList(L, Insts)9.43k ) continue8.23k ; |
417 | 1.20k | |
418 | 1.20k | // If we haven't seen a store yet, this is a live in use, otherwise |
419 | 1.20k | // use the stored value. |
420 | 1.20k | if (1.20k StoredValue1.20k ) { |
421 | 149 | replaceLoadWithValue(L, StoredValue); |
422 | 149 | L->replaceAllUsesWith(StoredValue); |
423 | 149 | ReplacedLoads[L] = StoredValue; |
424 | 1.20k | } else { |
425 | 1.05k | LiveInLoads.push_back(L); |
426 | 1.05k | } |
427 | 9.43k | continue; |
428 | 9.43k | } |
429 | 43.8k | |
430 | 43.8k | if (StoreInst *43.8k SI43.8k = dyn_cast<StoreInst>(&I)) { |
431 | 5.36k | // If this is a store to an unrelated pointer, ignore it. |
432 | 5.36k | if (!isInstInList(SI, Insts)5.36k ) continue3.69k ; |
433 | 1.66k | updateDebugInfo(SI); |
434 | 1.66k | |
435 | 1.66k | // Remember that this is the active value in the block. |
436 | 1.66k | StoredValue = SI->getOperand(0); |
437 | 1.66k | } |
438 | 53.2k | } |
439 | 4.88k | |
440 | 4.88k | // The last stored value that happened is the live-out for the block. |
441 | 4.88k | assert(StoredValue && "Already checked that there is a store in block"); |
442 | 4.88k | SSA.AddAvailableValue(BB, StoredValue); |
443 | 4.88k | BlockUses.clear(); |
444 | 4.88k | } |
445 | 2.54k | |
446 | 2.54k | // Okay, now we rewrite all loads that use live-in values in the loop, |
447 | 2.54k | // inserting PHI nodes as necessary. |
448 | 1.42k | for (LoadInst *ALoad : LiveInLoads) { |
449 | 1.42k | Value *NewVal = SSA.GetValueInMiddleOfBlock(ALoad->getParent()); |
450 | 1.42k | replaceLoadWithValue(ALoad, NewVal); |
451 | 1.42k | |
452 | 1.42k | // Avoid assertions in unreachable code. |
453 | 1.42k | if (NewVal == ALoad1.42k ) NewVal = UndefValue::get(NewVal->getType())0 ; |
454 | 1.42k | ALoad->replaceAllUsesWith(NewVal); |
455 | 1.42k | ReplacedLoads[ALoad] = NewVal; |
456 | 1.42k | } |
457 | 2.54k | |
458 | 2.54k | // Allow the client to do stuff before we start nuking things. |
459 | 2.54k | doExtraRewritesBeforeFinalDeletion(); |
460 | 2.54k | |
461 | 2.54k | // Now that everything is rewritten, delete the old instructions from the |
462 | 2.54k | // function. They should all be dead now. |
463 | 4.88k | for (Instruction *User : Insts) { |
464 | 4.88k | // If this is a load that still has uses, then the load must have been added |
465 | 4.88k | // as a live value in the SSAUpdate data structure for a block (e.g. because |
466 | 4.88k | // the loaded value was stored later). In this case, we need to recursively |
467 | 4.88k | // propagate the updates until we get to the real value. |
468 | 4.88k | if (!User->use_empty()4.88k ) { |
469 | 5 | Value *NewVal = ReplacedLoads[User]; |
470 | 5 | assert(NewVal && "not a replaced load?"); |
471 | 5 | |
472 | 5 | // Propagate down to the ultimate replacee. The intermediately loads |
473 | 5 | // could theoretically already have been deleted, so we don't want to |
474 | 5 | // dereference the Value*'s. |
475 | 5 | DenseMap<Value*, Value*>::iterator RLI = ReplacedLoads.find(NewVal); |
476 | 5 | while (RLI != ReplacedLoads.end()5 ) { |
477 | 0 | NewVal = RLI->second; |
478 | 0 | RLI = ReplacedLoads.find(NewVal); |
479 | 0 | } |
480 | 5 | |
481 | 5 | replaceLoadWithValue(cast<LoadInst>(User), NewVal); |
482 | 5 | User->replaceAllUsesWith(NewVal); |
483 | 5 | } |
484 | 4.88k | |
485 | 4.88k | instructionDeleted(User); |
486 | 4.88k | User->eraseFromParent(); |
487 | 4.88k | } |
488 | 2.54k | } |
489 | | |
490 | | bool |
491 | | LoadAndStorePromoter::isInstInList(Instruction *I, |
492 | | const SmallVectorImpl<Instruction*> &Insts) |
493 | 124 | const { |
494 | 124 | return is_contained(Insts, I); |
495 | 124 | } |