]>
Commit | Line | Data |
---|---|---|
223e47cc LB |
1 | //===-- LICM.cpp - Loop Invariant Code Motion Pass ------------------------===// |
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 pass performs loop invariant code motion, attempting to remove as much | |
11 | // code from the body of a loop as possible. It does this by either hoisting | |
12 | // code into the preheader block, or by sinking code to the exit blocks if it is | |
13 | // safe. This pass also promotes must-aliased memory locations in the loop to | |
14 | // live in registers, thus hoisting and sinking "invariant" loads and stores. | |
15 | // | |
16 | // This pass uses alias analysis for two purposes: | |
17 | // | |
18 | // 1. Moving loop invariant loads and calls out of loops. If we can determine | |
19 | // that a load or call inside of a loop never aliases anything stored to, | |
20 | // we can hoist it or sink it like any other instruction. | |
21 | // 2. Scalar Promotion of Memory - If there is a store instruction inside of | |
22 | // the loop, we try to move the store to happen AFTER the loop instead of | |
23 | // inside of the loop. This can only happen if a few conditions are true: | |
24 | // A. The pointer stored through is loop invariant | |
25 | // B. There are no stores or loads in the loop which _may_ alias the | |
26 | // pointer. There are no calls in the loop which mod/ref the pointer. | |
27 | // If these conditions are true, we can promote the loads and stores in the | |
28 | // loop of the pointer to use a temporary alloca'd variable. We then use | |
29 | // the SSAUpdater to construct the appropriate SSA form for the value. | |
30 | // | |
31 | //===----------------------------------------------------------------------===// | |
32 | ||
223e47cc | 33 | #include "llvm/Transforms/Scalar.h" |
970d7e83 | 34 | #include "llvm/ADT/Statistic.h" |
223e47cc LB |
35 | #include "llvm/Analysis/AliasAnalysis.h" |
36 | #include "llvm/Analysis/AliasSetTracker.h" | |
37 | #include "llvm/Analysis/ConstantFolding.h" | |
38 | #include "llvm/Analysis/LoopInfo.h" | |
39 | #include "llvm/Analysis/LoopPass.h" | |
1a4d82fc | 40 | #include "llvm/Analysis/ScalarEvolution.h" |
223e47cc | 41 | #include "llvm/Analysis/ValueTracking.h" |
1a4d82fc | 42 | #include "llvm/IR/CFG.h" |
970d7e83 LB |
43 | #include "llvm/IR/Constants.h" |
44 | #include "llvm/IR/DataLayout.h" | |
45 | #include "llvm/IR/DerivedTypes.h" | |
1a4d82fc | 46 | #include "llvm/IR/Dominators.h" |
970d7e83 LB |
47 | #include "llvm/IR/Instructions.h" |
48 | #include "llvm/IR/IntrinsicInst.h" | |
49 | #include "llvm/IR/LLVMContext.h" | |
50 | #include "llvm/IR/Metadata.h" | |
1a4d82fc | 51 | #include "llvm/IR/PredIteratorCache.h" |
223e47cc | 52 | #include "llvm/Support/CommandLine.h" |
223e47cc | 53 | #include "llvm/Support/Debug.h" |
970d7e83 LB |
54 | #include "llvm/Support/raw_ostream.h" |
55 | #include "llvm/Target/TargetLibraryInfo.h" | |
56 | #include "llvm/Transforms/Utils/Local.h" | |
1a4d82fc | 57 | #include "llvm/Transforms/Utils/LoopUtils.h" |
970d7e83 | 58 | #include "llvm/Transforms/Utils/SSAUpdater.h" |
223e47cc LB |
59 | #include <algorithm> |
60 | using namespace llvm; | |
61 | ||
1a4d82fc JJ |
62 | #define DEBUG_TYPE "licm" |
63 | ||
223e47cc LB |
64 | STATISTIC(NumSunk , "Number of instructions sunk out of loop"); |
65 | STATISTIC(NumHoisted , "Number of instructions hoisted out of loop"); | |
66 | STATISTIC(NumMovedLoads, "Number of load insts hoisted or sunk"); | |
67 | STATISTIC(NumMovedCalls, "Number of call insts hoisted or sunk"); | |
68 | STATISTIC(NumPromoted , "Number of memory locations promoted to registers"); | |
69 | ||
70 | static cl::opt<bool> | |
71 | DisablePromotion("disable-licm-promotion", cl::Hidden, | |
72 | cl::desc("Disable memory promotion in LICM pass")); | |
73 | ||
74 | namespace { | |
75 | struct LICM : public LoopPass { | |
76 | static char ID; // Pass identification, replacement for typeid | |
77 | LICM() : LoopPass(ID) { | |
78 | initializeLICMPass(*PassRegistry::getPassRegistry()); | |
79 | } | |
80 | ||
1a4d82fc | 81 | bool runOnLoop(Loop *L, LPPassManager &LPM) override; |
223e47cc LB |
82 | |
83 | /// This transformation requires natural loop information & requires that | |
84 | /// loop preheaders be inserted into the CFG... | |
85 | /// | |
1a4d82fc | 86 | void getAnalysisUsage(AnalysisUsage &AU) const override { |
223e47cc | 87 | AU.setPreservesCFG(); |
1a4d82fc | 88 | AU.addRequired<DominatorTreeWrapperPass>(); |
223e47cc LB |
89 | AU.addRequired<LoopInfo>(); |
90 | AU.addRequiredID(LoopSimplifyID); | |
1a4d82fc JJ |
91 | AU.addPreservedID(LoopSimplifyID); |
92 | AU.addRequiredID(LCSSAID); | |
93 | AU.addPreservedID(LCSSAID); | |
223e47cc LB |
94 | AU.addRequired<AliasAnalysis>(); |
95 | AU.addPreserved<AliasAnalysis>(); | |
1a4d82fc | 96 | AU.addPreserved<ScalarEvolution>(); |
223e47cc LB |
97 | AU.addRequired<TargetLibraryInfo>(); |
98 | } | |
99 | ||
970d7e83 LB |
100 | using llvm::Pass::doFinalization; |
101 | ||
1a4d82fc | 102 | bool doFinalization() override { |
223e47cc LB |
103 | assert(LoopToAliasSetMap.empty() && "Didn't free loop alias sets"); |
104 | return false; | |
105 | } | |
106 | ||
107 | private: | |
108 | AliasAnalysis *AA; // Current AliasAnalysis information | |
109 | LoopInfo *LI; // Current LoopInfo | |
110 | DominatorTree *DT; // Dominator Tree for the current Loop. | |
111 | ||
1a4d82fc | 112 | const DataLayout *DL; // DataLayout for constant folding. |
223e47cc LB |
113 | TargetLibraryInfo *TLI; // TargetLibraryInfo for constant folding. |
114 | ||
115 | // State that is updated as we process loops. | |
116 | bool Changed; // Set to true when we change anything. | |
117 | BasicBlock *Preheader; // The preheader block of the current loop... | |
118 | Loop *CurLoop; // The current loop we are working on... | |
119 | AliasSetTracker *CurAST; // AliasSet information for the current loop... | |
120 | bool MayThrow; // The current loop contains an instruction which | |
121 | // may throw, thus preventing code motion of | |
122 | // instructions with side effects. | |
85aaf69f | 123 | bool HeaderMayThrow; // Same as previous, but specific to loop header |
223e47cc LB |
124 | DenseMap<Loop*, AliasSetTracker*> LoopToAliasSetMap; |
125 | ||
126 | /// cloneBasicBlockAnalysis - Simple Analysis hook. Clone alias set info. | |
1a4d82fc JJ |
127 | void cloneBasicBlockAnalysis(BasicBlock *From, BasicBlock *To, |
128 | Loop *L) override; | |
223e47cc LB |
129 | |
130 | /// deleteAnalysisValue - Simple Analysis hook. Delete value V from alias | |
131 | /// set. | |
1a4d82fc JJ |
132 | void deleteAnalysisValue(Value *V, Loop *L) override; |
133 | ||
134 | /// Simple Analysis hook. Delete loop L from alias set map. | |
135 | void deleteAnalysisLoop(Loop *L) override; | |
223e47cc LB |
136 | |
137 | /// SinkRegion - Walk the specified region of the CFG (defined by all blocks | |
138 | /// dominated by the specified block, and that are in the current loop) in | |
139 | /// reverse depth first order w.r.t the DominatorTree. This allows us to | |
140 | /// visit uses before definitions, allowing us to sink a loop body in one | |
141 | /// pass without iteration. | |
142 | /// | |
143 | void SinkRegion(DomTreeNode *N); | |
144 | ||
145 | /// HoistRegion - Walk the specified region of the CFG (defined by all | |
146 | /// blocks dominated by the specified block, and that are in the current | |
147 | /// loop) in depth first order w.r.t the DominatorTree. This allows us to | |
148 | /// visit definitions before uses, allowing us to hoist a loop body in one | |
149 | /// pass without iteration. | |
150 | /// | |
151 | void HoistRegion(DomTreeNode *N); | |
152 | ||
153 | /// inSubLoop - Little predicate that returns true if the specified basic | |
154 | /// block is in a subloop of the current one, not the current one itself. | |
155 | /// | |
156 | bool inSubLoop(BasicBlock *BB) { | |
157 | assert(CurLoop->contains(BB) && "Only valid if BB is IN the loop"); | |
158 | return LI->getLoopFor(BB) != CurLoop; | |
159 | } | |
160 | ||
161 | /// sink - When an instruction is found to only be used outside of the loop, | |
162 | /// this function moves it to the exit blocks and patches up SSA form as | |
163 | /// needed. | |
164 | /// | |
165 | void sink(Instruction &I); | |
166 | ||
167 | /// hoist - When an instruction is found to only use loop invariant operands | |
168 | /// that is safe to hoist, this instruction is called to do the dirty work. | |
169 | /// | |
170 | void hoist(Instruction &I); | |
171 | ||
172 | /// isSafeToExecuteUnconditionally - Only sink or hoist an instruction if it | |
173 | /// is not a trapping instruction or if it is a trapping instruction and is | |
174 | /// guaranteed to execute. | |
175 | /// | |
176 | bool isSafeToExecuteUnconditionally(Instruction &I); | |
177 | ||
178 | /// isGuaranteedToExecute - Check that the instruction is guaranteed to | |
179 | /// execute. | |
180 | /// | |
181 | bool isGuaranteedToExecute(Instruction &I); | |
182 | ||
183 | /// pointerInvalidatedByLoop - Return true if the body of this loop may | |
184 | /// store into the memory location pointed to by V. | |
185 | /// | |
186 | bool pointerInvalidatedByLoop(Value *V, uint64_t Size, | |
1a4d82fc | 187 | const AAMDNodes &AAInfo) { |
223e47cc | 188 | // Check to see if any of the basic blocks in CurLoop invalidate *V. |
1a4d82fc | 189 | return CurAST->getAliasSetForPointer(V, Size, AAInfo).isMod(); |
223e47cc LB |
190 | } |
191 | ||
192 | bool canSinkOrHoistInst(Instruction &I); | |
193 | bool isNotUsedInLoop(Instruction &I); | |
194 | ||
195 | void PromoteAliasSet(AliasSet &AS, | |
196 | SmallVectorImpl<BasicBlock*> &ExitBlocks, | |
1a4d82fc JJ |
197 | SmallVectorImpl<Instruction*> &InsertPts, |
198 | PredIteratorCache &PIC); | |
199 | ||
200 | /// \brief Create a copy of the instruction in the exit block and patch up | |
201 | /// SSA. | |
202 | /// PN is a user of I in ExitBlock that can be used to get the number and | |
203 | /// list of predecessors fast. | |
204 | Instruction *CloneInstructionInExitBlock(Instruction &I, | |
205 | BasicBlock &ExitBlock, | |
206 | PHINode &PN); | |
223e47cc LB |
207 | }; |
208 | } | |
209 | ||
210 | char LICM::ID = 0; | |
211 | INITIALIZE_PASS_BEGIN(LICM, "licm", "Loop Invariant Code Motion", false, false) | |
1a4d82fc | 212 | INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass) |
223e47cc LB |
213 | INITIALIZE_PASS_DEPENDENCY(LoopInfo) |
214 | INITIALIZE_PASS_DEPENDENCY(LoopSimplify) | |
1a4d82fc JJ |
215 | INITIALIZE_PASS_DEPENDENCY(LCSSA) |
216 | INITIALIZE_PASS_DEPENDENCY(ScalarEvolution) | |
223e47cc LB |
217 | INITIALIZE_PASS_DEPENDENCY(TargetLibraryInfo) |
218 | INITIALIZE_AG_DEPENDENCY(AliasAnalysis) | |
219 | INITIALIZE_PASS_END(LICM, "licm", "Loop Invariant Code Motion", false, false) | |
220 | ||
221 | Pass *llvm::createLICMPass() { return new LICM(); } | |
222 | ||
223 | /// Hoist expressions out of the specified loop. Note, alias info for inner | |
224 | /// loop is not preserved so it is not a good idea to run LICM multiple | |
225 | /// times on one loop. | |
226 | /// | |
227 | bool LICM::runOnLoop(Loop *L, LPPassManager &LPM) { | |
1a4d82fc JJ |
228 | if (skipOptnoneFunction(L)) |
229 | return false; | |
230 | ||
223e47cc LB |
231 | Changed = false; |
232 | ||
233 | // Get our Loop and Alias Analysis information... | |
234 | LI = &getAnalysis<LoopInfo>(); | |
235 | AA = &getAnalysis<AliasAnalysis>(); | |
1a4d82fc | 236 | DT = &getAnalysis<DominatorTreeWrapperPass>().getDomTree(); |
223e47cc | 237 | |
1a4d82fc JJ |
238 | DataLayoutPass *DLP = getAnalysisIfAvailable<DataLayoutPass>(); |
239 | DL = DLP ? &DLP->getDataLayout() : nullptr; | |
223e47cc LB |
240 | TLI = &getAnalysis<TargetLibraryInfo>(); |
241 | ||
1a4d82fc JJ |
242 | assert(L->isLCSSAForm(*DT) && "Loop is not in LCSSA form."); |
243 | ||
223e47cc LB |
244 | CurAST = new AliasSetTracker(*AA); |
245 | // Collect Alias info from subloops. | |
246 | for (Loop::iterator LoopItr = L->begin(), LoopItrE = L->end(); | |
247 | LoopItr != LoopItrE; ++LoopItr) { | |
248 | Loop *InnerL = *LoopItr; | |
249 | AliasSetTracker *InnerAST = LoopToAliasSetMap[InnerL]; | |
250 | assert(InnerAST && "Where is my AST?"); | |
251 | ||
252 | // What if InnerLoop was modified by other passes ? | |
253 | CurAST->add(*InnerAST); | |
254 | ||
255 | // Once we've incorporated the inner loop's AST into ours, we don't need the | |
256 | // subloop's anymore. | |
257 | delete InnerAST; | |
258 | LoopToAliasSetMap.erase(InnerL); | |
259 | } | |
260 | ||
261 | CurLoop = L; | |
262 | ||
263 | // Get the preheader block to move instructions into... | |
264 | Preheader = L->getLoopPreheader(); | |
265 | ||
266 | // Loop over the body of this loop, looking for calls, invokes, and stores. | |
267 | // Because subloops have already been incorporated into AST, we skip blocks in | |
268 | // subloops. | |
269 | // | |
270 | for (Loop::block_iterator I = L->block_begin(), E = L->block_end(); | |
271 | I != E; ++I) { | |
272 | BasicBlock *BB = *I; | |
273 | if (LI->getLoopFor(BB) == L) // Ignore blocks in subloops. | |
274 | CurAST->add(*BB); // Incorporate the specified basic block | |
275 | } | |
276 | ||
85aaf69f SL |
277 | HeaderMayThrow = false; |
278 | BasicBlock *Header = L->getHeader(); | |
279 | for (BasicBlock::iterator I = Header->begin(), E = Header->end(); | |
280 | (I != E) && !HeaderMayThrow; ++I) | |
281 | HeaderMayThrow |= I->mayThrow(); | |
282 | MayThrow = HeaderMayThrow; | |
223e47cc LB |
283 | // TODO: We've already searched for instructions which may throw in subloops. |
284 | // We may want to reuse this information. | |
285 | for (Loop::block_iterator BB = L->block_begin(), BBE = L->block_end(); | |
286 | (BB != BBE) && !MayThrow ; ++BB) | |
287 | for (BasicBlock::iterator I = (*BB)->begin(), E = (*BB)->end(); | |
288 | (I != E) && !MayThrow; ++I) | |
289 | MayThrow |= I->mayThrow(); | |
290 | ||
291 | // We want to visit all of the instructions in this loop... that are not parts | |
292 | // of our subloops (they have already had their invariants hoisted out of | |
293 | // their loop, into this loop, so there is no need to process the BODIES of | |
294 | // the subloops). | |
295 | // | |
296 | // Traverse the body of the loop in depth first order on the dominator tree so | |
297 | // that we are guaranteed to see definitions before we see uses. This allows | |
298 | // us to sink instructions in one pass, without iteration. After sinking | |
299 | // instructions, we perform another pass to hoist them out of the loop. | |
300 | // | |
301 | if (L->hasDedicatedExits()) | |
302 | SinkRegion(DT->getNode(L->getHeader())); | |
303 | if (Preheader) | |
304 | HoistRegion(DT->getNode(L->getHeader())); | |
305 | ||
306 | // Now that all loop invariants have been removed from the loop, promote any | |
307 | // memory references to scalars that we can. | |
1a4d82fc | 308 | if (!DisablePromotion && (Preheader || L->hasDedicatedExits())) { |
223e47cc LB |
309 | SmallVector<BasicBlock *, 8> ExitBlocks; |
310 | SmallVector<Instruction *, 8> InsertPts; | |
1a4d82fc | 311 | PredIteratorCache PIC; |
223e47cc LB |
312 | |
313 | // Loop over all of the alias sets in the tracker object. | |
314 | for (AliasSetTracker::iterator I = CurAST->begin(), E = CurAST->end(); | |
315 | I != E; ++I) | |
1a4d82fc JJ |
316 | PromoteAliasSet(*I, ExitBlocks, InsertPts, PIC); |
317 | ||
318 | // Once we have promoted values across the loop body we have to recursively | |
319 | // reform LCSSA as any nested loop may now have values defined within the | |
320 | // loop used in the outer loop. | |
321 | // FIXME: This is really heavy handed. It would be a bit better to use an | |
322 | // SSAUpdater strategy during promotion that was LCSSA aware and reformed | |
323 | // it as it went. | |
324 | if (Changed) | |
85aaf69f SL |
325 | formLCSSARecursively(*L, *DT, LI, |
326 | getAnalysisIfAvailable<ScalarEvolution>()); | |
223e47cc LB |
327 | } |
328 | ||
1a4d82fc JJ |
329 | // Check that neither this loop nor its parent have had LCSSA broken. LICM is |
330 | // specifically moving instructions across the loop boundary and so it is | |
331 | // especially in need of sanity checking here. | |
332 | assert(L->isLCSSAForm(*DT) && "Loop not left in LCSSA form after LICM!"); | |
333 | assert((!L->getParentLoop() || L->getParentLoop()->isLCSSAForm(*DT)) && | |
334 | "Parent loop not left in LCSSA form after LICM!"); | |
335 | ||
223e47cc | 336 | // Clear out loops state information for the next iteration |
1a4d82fc JJ |
337 | CurLoop = nullptr; |
338 | Preheader = nullptr; | |
223e47cc LB |
339 | |
340 | // If this loop is nested inside of another one, save the alias information | |
341 | // for when we process the outer loop. | |
342 | if (L->getParentLoop()) | |
343 | LoopToAliasSetMap[L] = CurAST; | |
344 | else | |
345 | delete CurAST; | |
346 | return Changed; | |
347 | } | |
348 | ||
349 | /// SinkRegion - Walk the specified region of the CFG (defined by all blocks | |
350 | /// dominated by the specified block, and that are in the current loop) in | |
351 | /// reverse depth first order w.r.t the DominatorTree. This allows us to visit | |
352 | /// uses before definitions, allowing us to sink a loop body in one pass without | |
353 | /// iteration. | |
354 | /// | |
355 | void LICM::SinkRegion(DomTreeNode *N) { | |
1a4d82fc | 356 | assert(N != nullptr && "Null dominator tree node?"); |
223e47cc LB |
357 | BasicBlock *BB = N->getBlock(); |
358 | ||
359 | // If this subregion is not in the top level loop at all, exit. | |
360 | if (!CurLoop->contains(BB)) return; | |
361 | ||
362 | // We are processing blocks in reverse dfo, so process children first. | |
363 | const std::vector<DomTreeNode*> &Children = N->getChildren(); | |
364 | for (unsigned i = 0, e = Children.size(); i != e; ++i) | |
365 | SinkRegion(Children[i]); | |
366 | ||
367 | // Only need to process the contents of this block if it is not part of a | |
368 | // subloop (which would already have been processed). | |
369 | if (inSubLoop(BB)) return; | |
370 | ||
371 | for (BasicBlock::iterator II = BB->end(); II != BB->begin(); ) { | |
372 | Instruction &I = *--II; | |
373 | ||
374 | // If the instruction is dead, we would try to sink it because it isn't used | |
375 | // in the loop, instead, just delete it. | |
376 | if (isInstructionTriviallyDead(&I, TLI)) { | |
377 | DEBUG(dbgs() << "LICM deleting dead inst: " << I << '\n'); | |
378 | ++II; | |
379 | CurAST->deleteValue(&I); | |
380 | I.eraseFromParent(); | |
381 | Changed = true; | |
382 | continue; | |
383 | } | |
384 | ||
385 | // Check to see if we can sink this instruction to the exit blocks | |
386 | // of the loop. We can do this if the all users of the instruction are | |
387 | // outside of the loop. In this case, it doesn't even matter if the | |
388 | // operands of the instruction are loop invariant. | |
389 | // | |
390 | if (isNotUsedInLoop(I) && canSinkOrHoistInst(I)) { | |
391 | ++II; | |
392 | sink(I); | |
393 | } | |
394 | } | |
395 | } | |
396 | ||
397 | /// HoistRegion - Walk the specified region of the CFG (defined by all blocks | |
398 | /// dominated by the specified block, and that are in the current loop) in depth | |
399 | /// first order w.r.t the DominatorTree. This allows us to visit definitions | |
400 | /// before uses, allowing us to hoist a loop body in one pass without iteration. | |
401 | /// | |
402 | void LICM::HoistRegion(DomTreeNode *N) { | |
1a4d82fc | 403 | assert(N != nullptr && "Null dominator tree node?"); |
223e47cc LB |
404 | BasicBlock *BB = N->getBlock(); |
405 | ||
406 | // If this subregion is not in the top level loop at all, exit. | |
407 | if (!CurLoop->contains(BB)) return; | |
408 | ||
409 | // Only need to process the contents of this block if it is not part of a | |
410 | // subloop (which would already have been processed). | |
411 | if (!inSubLoop(BB)) | |
412 | for (BasicBlock::iterator II = BB->begin(), E = BB->end(); II != E; ) { | |
413 | Instruction &I = *II++; | |
414 | ||
415 | // Try constant folding this instruction. If all the operands are | |
416 | // constants, it is technically hoistable, but it would be better to just | |
417 | // fold it. | |
1a4d82fc | 418 | if (Constant *C = ConstantFoldInstruction(&I, DL, TLI)) { |
223e47cc LB |
419 | DEBUG(dbgs() << "LICM folding inst: " << I << " --> " << *C << '\n'); |
420 | CurAST->copyValue(&I, C); | |
421 | CurAST->deleteValue(&I); | |
422 | I.replaceAllUsesWith(C); | |
423 | I.eraseFromParent(); | |
424 | continue; | |
425 | } | |
426 | ||
427 | // Try hoisting the instruction out to the preheader. We can only do this | |
428 | // if all of the operands of the instruction are loop invariant and if it | |
429 | // is safe to hoist the instruction. | |
430 | // | |
431 | if (CurLoop->hasLoopInvariantOperands(&I) && canSinkOrHoistInst(I) && | |
432 | isSafeToExecuteUnconditionally(I)) | |
433 | hoist(I); | |
434 | } | |
435 | ||
436 | const std::vector<DomTreeNode*> &Children = N->getChildren(); | |
437 | for (unsigned i = 0, e = Children.size(); i != e; ++i) | |
438 | HoistRegion(Children[i]); | |
439 | } | |
440 | ||
441 | /// canSinkOrHoistInst - Return true if the hoister and sinker can handle this | |
442 | /// instruction. | |
443 | /// | |
444 | bool LICM::canSinkOrHoistInst(Instruction &I) { | |
445 | // Loads have extra constraints we have to verify before we can hoist them. | |
446 | if (LoadInst *LI = dyn_cast<LoadInst>(&I)) { | |
447 | if (!LI->isUnordered()) | |
448 | return false; // Don't hoist volatile/atomic loads! | |
449 | ||
450 | // Loads from constant memory are always safe to move, even if they end up | |
451 | // in the same alias set as something that ends up being modified. | |
452 | if (AA->pointsToConstantMemory(LI->getOperand(0))) | |
453 | return true; | |
85aaf69f | 454 | if (LI->getMetadata(LLVMContext::MD_invariant_load)) |
223e47cc LB |
455 | return true; |
456 | ||
457 | // Don't hoist loads which have may-aliased stores in loop. | |
458 | uint64_t Size = 0; | |
459 | if (LI->getType()->isSized()) | |
460 | Size = AA->getTypeStoreSize(LI->getType()); | |
1a4d82fc JJ |
461 | |
462 | AAMDNodes AAInfo; | |
463 | LI->getAAMetadata(AAInfo); | |
464 | ||
465 | return !pointerInvalidatedByLoop(LI->getOperand(0), Size, AAInfo); | |
223e47cc LB |
466 | } else if (CallInst *CI = dyn_cast<CallInst>(&I)) { |
467 | // Don't sink or hoist dbg info; it's legal, but not useful. | |
468 | if (isa<DbgInfoIntrinsic>(I)) | |
469 | return false; | |
470 | ||
471 | // Handle simple cases by querying alias analysis. | |
472 | AliasAnalysis::ModRefBehavior Behavior = AA->getModRefBehavior(CI); | |
473 | if (Behavior == AliasAnalysis::DoesNotAccessMemory) | |
474 | return true; | |
475 | if (AliasAnalysis::onlyReadsMemory(Behavior)) { | |
476 | // If this call only reads from memory and there are no writes to memory | |
477 | // in the loop, we can hoist or sink the call as appropriate. | |
478 | bool FoundMod = false; | |
479 | for (AliasSetTracker::iterator I = CurAST->begin(), E = CurAST->end(); | |
480 | I != E; ++I) { | |
481 | AliasSet &AS = *I; | |
482 | if (!AS.isForwardingAliasSet() && AS.isMod()) { | |
483 | FoundMod = true; | |
484 | break; | |
485 | } | |
486 | } | |
487 | if (!FoundMod) return true; | |
488 | } | |
489 | ||
490 | // FIXME: This should use mod/ref information to see if we can hoist or | |
491 | // sink the call. | |
492 | ||
493 | return false; | |
494 | } | |
495 | ||
496 | // Only these instructions are hoistable/sinkable. | |
970d7e83 LB |
497 | if (!isa<BinaryOperator>(I) && !isa<CastInst>(I) && !isa<SelectInst>(I) && |
498 | !isa<GetElementPtrInst>(I) && !isa<CmpInst>(I) && | |
499 | !isa<InsertElementInst>(I) && !isa<ExtractElementInst>(I) && | |
500 | !isa<ShuffleVectorInst>(I) && !isa<ExtractValueInst>(I) && | |
501 | !isa<InsertValueInst>(I)) | |
502 | return false; | |
223e47cc LB |
503 | |
504 | return isSafeToExecuteUnconditionally(I); | |
505 | } | |
506 | ||
1a4d82fc JJ |
507 | /// \brief Returns true if a PHINode is a trivially replaceable with an |
508 | /// Instruction. | |
509 | /// | |
510 | /// This is true when all incoming values are that instruction. This pattern | |
511 | /// occurs most often with LCSSA PHI nodes. | |
512 | static bool isTriviallyReplacablePHI(PHINode &PN, Instruction &I) { | |
513 | for (unsigned i = 0, e = PN.getNumIncomingValues(); i != e; ++i) | |
514 | if (PN.getIncomingValue(i) != &I) | |
515 | return false; | |
516 | ||
517 | return true; | |
518 | } | |
519 | ||
223e47cc LB |
520 | /// isNotUsedInLoop - Return true if the only users of this instruction are |
521 | /// outside of the loop. If this is true, we can sink the instruction to the | |
522 | /// exit blocks of the loop. | |
523 | /// | |
524 | bool LICM::isNotUsedInLoop(Instruction &I) { | |
1a4d82fc JJ |
525 | for (User *U : I.users()) { |
526 | Instruction *UI = cast<Instruction>(U); | |
527 | if (PHINode *PN = dyn_cast<PHINode>(UI)) { | |
528 | // A PHI node where all of the incoming values are this instruction are | |
529 | // special -- they can just be RAUW'ed with the instruction and thus | |
530 | // don't require a use in the predecessor. This is a particular important | |
531 | // special case because it is the pattern found in LCSSA form. | |
532 | if (isTriviallyReplacablePHI(*PN, I)) { | |
533 | if (CurLoop->contains(PN)) | |
534 | return false; | |
535 | else | |
536 | continue; | |
537 | } | |
538 | ||
539 | // Otherwise, PHI node uses occur in predecessor blocks if the incoming | |
540 | // values. Check for such a use being inside the loop. | |
223e47cc LB |
541 | for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) |
542 | if (PN->getIncomingValue(i) == &I) | |
543 | if (CurLoop->contains(PN->getIncomingBlock(i))) | |
544 | return false; | |
1a4d82fc JJ |
545 | |
546 | continue; | |
223e47cc | 547 | } |
1a4d82fc JJ |
548 | |
549 | if (CurLoop->contains(UI)) | |
550 | return false; | |
223e47cc LB |
551 | } |
552 | return true; | |
553 | } | |
554 | ||
1a4d82fc JJ |
555 | Instruction *LICM::CloneInstructionInExitBlock(Instruction &I, |
556 | BasicBlock &ExitBlock, | |
557 | PHINode &PN) { | |
558 | Instruction *New = I.clone(); | |
559 | ExitBlock.getInstList().insert(ExitBlock.getFirstInsertionPt(), New); | |
560 | if (!I.getName().empty()) New->setName(I.getName() + ".le"); | |
561 | ||
562 | // Build LCSSA PHI nodes for any in-loop operands. Note that this is | |
563 | // particularly cheap because we can rip off the PHI node that we're | |
564 | // replacing for the number and blocks of the predecessors. | |
565 | // OPT: If this shows up in a profile, we can instead finish sinking all | |
566 | // invariant instructions, and then walk their operands to re-establish | |
567 | // LCSSA. That will eliminate creating PHI nodes just to nuke them when | |
568 | // sinking bottom-up. | |
569 | for (User::op_iterator OI = New->op_begin(), OE = New->op_end(); OI != OE; | |
570 | ++OI) | |
571 | if (Instruction *OInst = dyn_cast<Instruction>(*OI)) | |
572 | if (Loop *OLoop = LI->getLoopFor(OInst->getParent())) | |
573 | if (!OLoop->contains(&PN)) { | |
574 | PHINode *OpPN = | |
575 | PHINode::Create(OInst->getType(), PN.getNumIncomingValues(), | |
576 | OInst->getName() + ".lcssa", ExitBlock.begin()); | |
577 | for (unsigned i = 0, e = PN.getNumIncomingValues(); i != e; ++i) | |
578 | OpPN->addIncoming(OInst, PN.getIncomingBlock(i)); | |
579 | *OI = OpPN; | |
580 | } | |
581 | return New; | |
582 | } | |
223e47cc LB |
583 | |
584 | /// sink - When an instruction is found to only be used outside of the loop, | |
585 | /// this function moves it to the exit blocks and patches up SSA form as needed. | |
586 | /// This method is guaranteed to remove the original instruction from its | |
587 | /// position, and may either delete it or move it to outside of the loop. | |
588 | /// | |
589 | void LICM::sink(Instruction &I) { | |
590 | DEBUG(dbgs() << "LICM sinking instruction: " << I << "\n"); | |
591 | ||
223e47cc LB |
592 | if (isa<LoadInst>(I)) ++NumMovedLoads; |
593 | else if (isa<CallInst>(I)) ++NumMovedCalls; | |
594 | ++NumSunk; | |
595 | Changed = true; | |
596 | ||
1a4d82fc JJ |
597 | #ifndef NDEBUG |
598 | SmallVector<BasicBlock *, 32> ExitBlocks; | |
599 | CurLoop->getUniqueExitBlocks(ExitBlocks); | |
600 | SmallPtrSet<BasicBlock *, 32> ExitBlockSet(ExitBlocks.begin(), ExitBlocks.end()); | |
601 | #endif | |
602 | ||
603 | // Clones of this instruction. Don't create more than one per exit block! | |
604 | SmallDenseMap<BasicBlock *, Instruction *, 32> SunkCopies; | |
605 | ||
606 | // If this instruction is only used outside of the loop, then all users are | |
607 | // PHI nodes in exit blocks due to LCSSA form. Just RAUW them with clones of | |
608 | // the instruction. | |
609 | while (!I.use_empty()) { | |
610 | Instruction *User = I.user_back(); | |
611 | if (!DT->isReachableFromEntry(User->getParent())) { | |
612 | User->replaceUsesOfWith(&I, UndefValue::get(I.getType())); | |
223e47cc | 613 | continue; |
223e47cc | 614 | } |
1a4d82fc JJ |
615 | // The user must be a PHI node. |
616 | PHINode *PN = cast<PHINode>(User); | |
223e47cc | 617 | |
1a4d82fc JJ |
618 | BasicBlock *ExitBlock = PN->getParent(); |
619 | assert(ExitBlockSet.count(ExitBlock) && | |
620 | "The LCSSA PHI is not in an exit block!"); | |
223e47cc | 621 | |
1a4d82fc JJ |
622 | Instruction *New; |
623 | auto It = SunkCopies.find(ExitBlock); | |
624 | if (It != SunkCopies.end()) | |
625 | New = It->second; | |
626 | else | |
627 | New = SunkCopies[ExitBlock] = | |
628 | CloneInstructionInExitBlock(I, *ExitBlock, *PN); | |
629 | ||
630 | PN->replaceAllUsesWith(New); | |
631 | PN->eraseFromParent(); | |
223e47cc LB |
632 | } |
633 | ||
223e47cc | 634 | CurAST->deleteValue(&I); |
1a4d82fc | 635 | I.eraseFromParent(); |
223e47cc LB |
636 | } |
637 | ||
638 | /// hoist - When an instruction is found to only use loop invariant operands | |
639 | /// that is safe to hoist, this instruction is called to do the dirty work. | |
640 | /// | |
641 | void LICM::hoist(Instruction &I) { | |
642 | DEBUG(dbgs() << "LICM hoisting to " << Preheader->getName() << ": " | |
643 | << I << "\n"); | |
644 | ||
645 | // Move the new node to the Preheader, before its terminator. | |
646 | I.moveBefore(Preheader->getTerminator()); | |
647 | ||
648 | if (isa<LoadInst>(I)) ++NumMovedLoads; | |
649 | else if (isa<CallInst>(I)) ++NumMovedCalls; | |
650 | ++NumHoisted; | |
651 | Changed = true; | |
652 | } | |
653 | ||
654 | /// isSafeToExecuteUnconditionally - Only sink or hoist an instruction if it is | |
655 | /// not a trapping instruction or if it is a trapping instruction and is | |
656 | /// guaranteed to execute. | |
657 | /// | |
658 | bool LICM::isSafeToExecuteUnconditionally(Instruction &Inst) { | |
659 | // If it is not a trapping instruction, it is always safe to hoist. | |
1a4d82fc | 660 | if (isSafeToSpeculativelyExecute(&Inst, DL)) |
223e47cc LB |
661 | return true; |
662 | ||
663 | return isGuaranteedToExecute(Inst); | |
664 | } | |
665 | ||
666 | bool LICM::isGuaranteedToExecute(Instruction &Inst) { | |
667 | ||
85aaf69f | 668 | // We have to check to make sure that the instruction dominates all |
223e47cc LB |
669 | // of the exit blocks. If it doesn't, then there is a path out of the loop |
670 | // which does not execute this instruction, so we can't hoist it. | |
671 | ||
672 | // If the instruction is in the header block for the loop (which is very | |
673 | // common), it is always guaranteed to dominate the exit blocks. Since this | |
674 | // is a common case, and can save some work, check it now. | |
675 | if (Inst.getParent() == CurLoop->getHeader()) | |
85aaf69f SL |
676 | // If there's a throw in the header block, we can't guarantee we'll reach |
677 | // Inst. | |
678 | return !HeaderMayThrow; | |
679 | ||
680 | // Somewhere in this loop there is an instruction which may throw and make us | |
681 | // exit the loop. | |
682 | if (MayThrow) | |
683 | return false; | |
223e47cc LB |
684 | |
685 | // Get the exit blocks for the current loop. | |
686 | SmallVector<BasicBlock*, 8> ExitBlocks; | |
687 | CurLoop->getExitBlocks(ExitBlocks); | |
688 | ||
689 | // Verify that the block dominates each of the exit blocks of the loop. | |
690 | for (unsigned i = 0, e = ExitBlocks.size(); i != e; ++i) | |
691 | if (!DT->dominates(Inst.getParent(), ExitBlocks[i])) | |
692 | return false; | |
693 | ||
694 | // As a degenerate case, if the loop is statically infinite then we haven't | |
695 | // proven anything since there are no exit blocks. | |
696 | if (ExitBlocks.empty()) | |
697 | return false; | |
698 | ||
699 | return true; | |
700 | } | |
701 | ||
702 | namespace { | |
703 | class LoopPromoter : public LoadAndStorePromoter { | |
704 | Value *SomePtr; // Designated pointer to store to. | |
1a4d82fc | 705 | SmallPtrSetImpl<Value*> &PointerMustAliases; |
223e47cc LB |
706 | SmallVectorImpl<BasicBlock*> &LoopExitBlocks; |
707 | SmallVectorImpl<Instruction*> &LoopInsertPts; | |
1a4d82fc | 708 | PredIteratorCache &PredCache; |
223e47cc | 709 | AliasSetTracker &AST; |
1a4d82fc | 710 | LoopInfo &LI; |
223e47cc LB |
711 | DebugLoc DL; |
712 | int Alignment; | |
1a4d82fc JJ |
713 | AAMDNodes AATags; |
714 | ||
715 | Value *maybeInsertLCSSAPHI(Value *V, BasicBlock *BB) const { | |
716 | if (Instruction *I = dyn_cast<Instruction>(V)) | |
717 | if (Loop *L = LI.getLoopFor(I->getParent())) | |
718 | if (!L->contains(BB)) { | |
719 | // We need to create an LCSSA PHI node for the incoming value and | |
720 | // store that. | |
721 | PHINode *PN = PHINode::Create( | |
722 | I->getType(), PredCache.GetNumPreds(BB), | |
723 | I->getName() + ".lcssa", BB->begin()); | |
724 | for (BasicBlock **PI = PredCache.GetPreds(BB); *PI; ++PI) | |
725 | PN->addIncoming(I, *PI); | |
726 | return PN; | |
727 | } | |
728 | return V; | |
729 | } | |
730 | ||
223e47cc | 731 | public: |
1a4d82fc JJ |
732 | LoopPromoter(Value *SP, const SmallVectorImpl<Instruction *> &Insts, |
733 | SSAUpdater &S, SmallPtrSetImpl<Value *> &PMA, | |
734 | SmallVectorImpl<BasicBlock *> &LEB, | |
735 | SmallVectorImpl<Instruction *> &LIP, PredIteratorCache &PIC, | |
736 | AliasSetTracker &ast, LoopInfo &li, DebugLoc dl, int alignment, | |
737 | const AAMDNodes &AATags) | |
738 | : LoadAndStorePromoter(Insts, S), SomePtr(SP), PointerMustAliases(PMA), | |
739 | LoopExitBlocks(LEB), LoopInsertPts(LIP), PredCache(PIC), AST(ast), | |
740 | LI(li), DL(dl), Alignment(alignment), AATags(AATags) {} | |
741 | ||
742 | bool isInstInList(Instruction *I, | |
743 | const SmallVectorImpl<Instruction*> &) const override { | |
223e47cc LB |
744 | Value *Ptr; |
745 | if (LoadInst *LI = dyn_cast<LoadInst>(I)) | |
746 | Ptr = LI->getOperand(0); | |
747 | else | |
748 | Ptr = cast<StoreInst>(I)->getPointerOperand(); | |
749 | return PointerMustAliases.count(Ptr); | |
750 | } | |
751 | ||
1a4d82fc | 752 | void doExtraRewritesBeforeFinalDeletion() const override { |
223e47cc LB |
753 | // Insert stores after in the loop exit blocks. Each exit block gets a |
754 | // store of the live-out values that feed them. Since we've already told | |
755 | // the SSA updater about the defs in the loop and the preheader | |
756 | // definition, it is all set and we can start using it. | |
757 | for (unsigned i = 0, e = LoopExitBlocks.size(); i != e; ++i) { | |
758 | BasicBlock *ExitBlock = LoopExitBlocks[i]; | |
759 | Value *LiveInValue = SSA.GetValueInMiddleOfBlock(ExitBlock); | |
1a4d82fc JJ |
760 | LiveInValue = maybeInsertLCSSAPHI(LiveInValue, ExitBlock); |
761 | Value *Ptr = maybeInsertLCSSAPHI(SomePtr, ExitBlock); | |
223e47cc | 762 | Instruction *InsertPos = LoopInsertPts[i]; |
1a4d82fc | 763 | StoreInst *NewSI = new StoreInst(LiveInValue, Ptr, InsertPos); |
223e47cc LB |
764 | NewSI->setAlignment(Alignment); |
765 | NewSI->setDebugLoc(DL); | |
1a4d82fc | 766 | if (AATags) NewSI->setAAMetadata(AATags); |
223e47cc LB |
767 | } |
768 | } | |
769 | ||
1a4d82fc | 770 | void replaceLoadWithValue(LoadInst *LI, Value *V) const override { |
223e47cc LB |
771 | // Update alias analysis. |
772 | AST.copyValue(LI, V); | |
773 | } | |
1a4d82fc | 774 | void instructionDeleted(Instruction *I) const override { |
223e47cc LB |
775 | AST.deleteValue(I); |
776 | } | |
777 | }; | |
778 | } // end anon namespace | |
779 | ||
780 | /// PromoteAliasSet - Try to promote memory values to scalars by sinking | |
781 | /// stores out of the loop and moving loads to before the loop. We do this by | |
782 | /// looping over the stores in the loop, looking for stores to Must pointers | |
783 | /// which are loop invariant. | |
784 | /// | |
785 | void LICM::PromoteAliasSet(AliasSet &AS, | |
786 | SmallVectorImpl<BasicBlock*> &ExitBlocks, | |
1a4d82fc JJ |
787 | SmallVectorImpl<Instruction*> &InsertPts, |
788 | PredIteratorCache &PIC) { | |
223e47cc LB |
789 | // We can promote this alias set if it has a store, if it is a "Must" alias |
790 | // set, if the pointer is loop invariant, and if we are not eliminating any | |
791 | // volatile loads or stores. | |
792 | if (AS.isForwardingAliasSet() || !AS.isMod() || !AS.isMustAlias() || | |
793 | AS.isVolatile() || !CurLoop->isLoopInvariant(AS.begin()->getValue())) | |
794 | return; | |
795 | ||
796 | assert(!AS.empty() && | |
797 | "Must alias set should have at least one pointer element in it!"); | |
798 | Value *SomePtr = AS.begin()->getValue(); | |
799 | ||
800 | // It isn't safe to promote a load/store from the loop if the load/store is | |
801 | // conditional. For example, turning: | |
802 | // | |
803 | // for () { if (c) *P += 1; } | |
804 | // | |
805 | // into: | |
806 | // | |
807 | // tmp = *P; for () { if (c) tmp +=1; } *P = tmp; | |
808 | // | |
809 | // is not safe, because *P may only be valid to access if 'c' is true. | |
810 | // | |
811 | // It is safe to promote P if all uses are direct load/stores and if at | |
812 | // least one is guaranteed to be executed. | |
813 | bool GuaranteedToExecute = false; | |
814 | ||
815 | SmallVector<Instruction*, 64> LoopUses; | |
816 | SmallPtrSet<Value*, 4> PointerMustAliases; | |
817 | ||
818 | // We start with an alignment of one and try to find instructions that allow | |
819 | // us to prove better alignment. | |
820 | unsigned Alignment = 1; | |
1a4d82fc | 821 | AAMDNodes AATags; |
85aaf69f | 822 | bool HasDedicatedExits = CurLoop->hasDedicatedExits(); |
223e47cc LB |
823 | |
824 | // Check that all of the pointers in the alias set have the same type. We | |
825 | // cannot (yet) promote a memory location that is loaded and stored in | |
1a4d82fc | 826 | // different sizes. While we are at it, collect alignment and AA info. |
223e47cc LB |
827 | for (AliasSet::iterator ASI = AS.begin(), E = AS.end(); ASI != E; ++ASI) { |
828 | Value *ASIV = ASI->getValue(); | |
829 | PointerMustAliases.insert(ASIV); | |
830 | ||
831 | // Check that all of the pointers in the alias set have the same type. We | |
832 | // cannot (yet) promote a memory location that is loaded and stored in | |
833 | // different sizes. | |
834 | if (SomePtr->getType() != ASIV->getType()) | |
835 | return; | |
836 | ||
1a4d82fc | 837 | for (User *U : ASIV->users()) { |
223e47cc | 838 | // Ignore instructions that are outside the loop. |
1a4d82fc JJ |
839 | Instruction *UI = dyn_cast<Instruction>(U); |
840 | if (!UI || !CurLoop->contains(UI)) | |
223e47cc LB |
841 | continue; |
842 | ||
843 | // If there is an non-load/store instruction in the loop, we can't promote | |
844 | // it. | |
1a4d82fc | 845 | if (LoadInst *load = dyn_cast<LoadInst>(UI)) { |
223e47cc LB |
846 | assert(!load->isVolatile() && "AST broken"); |
847 | if (!load->isSimple()) | |
848 | return; | |
1a4d82fc | 849 | } else if (StoreInst *store = dyn_cast<StoreInst>(UI)) { |
223e47cc LB |
850 | // Stores *of* the pointer are not interesting, only stores *to* the |
851 | // pointer. | |
1a4d82fc | 852 | if (UI->getOperand(1) != ASIV) |
223e47cc LB |
853 | continue; |
854 | assert(!store->isVolatile() && "AST broken"); | |
855 | if (!store->isSimple()) | |
856 | return; | |
85aaf69f SL |
857 | // Don't sink stores from loops without dedicated block exits. Exits |
858 | // containing indirect branches are not transformed by loop simplify, | |
859 | // make sure we catch that. An additional load may be generated in the | |
860 | // preheader for SSA updater, so also avoid sinking when no preheader | |
861 | // is available. | |
862 | if (!HasDedicatedExits || !Preheader) | |
863 | return; | |
223e47cc LB |
864 | |
865 | // Note that we only check GuaranteedToExecute inside the store case | |
866 | // so that we do not introduce stores where they did not exist before | |
867 | // (which would break the LLVM concurrency model). | |
868 | ||
869 | // If the alignment of this instruction allows us to specify a more | |
870 | // restrictive (and performant) alignment and if we are sure this | |
871 | // instruction will be executed, update the alignment. | |
872 | // Larger is better, with the exception of 0 being the best alignment. | |
873 | unsigned InstAlignment = store->getAlignment(); | |
970d7e83 | 874 | if ((InstAlignment > Alignment || InstAlignment == 0) && Alignment != 0) |
1a4d82fc | 875 | if (isGuaranteedToExecute(*UI)) { |
223e47cc LB |
876 | GuaranteedToExecute = true; |
877 | Alignment = InstAlignment; | |
878 | } | |
879 | ||
880 | if (!GuaranteedToExecute) | |
1a4d82fc | 881 | GuaranteedToExecute = isGuaranteedToExecute(*UI); |
223e47cc LB |
882 | |
883 | } else | |
884 | return; // Not a load or store. | |
885 | ||
1a4d82fc | 886 | // Merge the AA tags. |
970d7e83 | 887 | if (LoopUses.empty()) { |
1a4d82fc JJ |
888 | // On the first load/store, just take its AA tags. |
889 | UI->getAAMetadata(AATags); | |
890 | } else if (AATags) { | |
891 | UI->getAAMetadata(AATags, /* Merge = */ true); | |
970d7e83 | 892 | } |
1a4d82fc JJ |
893 | |
894 | LoopUses.push_back(UI); | |
223e47cc LB |
895 | } |
896 | } | |
897 | ||
898 | // If there isn't a guaranteed-to-execute instruction, we can't promote. | |
899 | if (!GuaranteedToExecute) | |
900 | return; | |
901 | ||
902 | // Otherwise, this is safe to promote, lets do it! | |
903 | DEBUG(dbgs() << "LICM: Promoting value stored to in loop: " <<*SomePtr<<'\n'); | |
904 | Changed = true; | |
905 | ++NumPromoted; | |
906 | ||
907 | // Grab a debug location for the inserted loads/stores; given that the | |
908 | // inserted loads/stores have little relation to the original loads/stores, | |
909 | // this code just arbitrarily picks a location from one, since any debug | |
910 | // location is better than none. | |
911 | DebugLoc DL = LoopUses[0]->getDebugLoc(); | |
912 | ||
913 | // Figure out the loop exits and their insertion points, if this is the | |
914 | // first promotion. | |
915 | if (ExitBlocks.empty()) { | |
916 | CurLoop->getUniqueExitBlocks(ExitBlocks); | |
917 | InsertPts.resize(ExitBlocks.size()); | |
918 | for (unsigned i = 0, e = ExitBlocks.size(); i != e; ++i) | |
919 | InsertPts[i] = ExitBlocks[i]->getFirstInsertionPt(); | |
920 | } | |
921 | ||
922 | // We use the SSAUpdater interface to insert phi nodes as required. | |
923 | SmallVector<PHINode*, 16> NewPHIs; | |
924 | SSAUpdater SSA(&NewPHIs); | |
925 | LoopPromoter Promoter(SomePtr, LoopUses, SSA, PointerMustAliases, ExitBlocks, | |
1a4d82fc | 926 | InsertPts, PIC, *CurAST, *LI, DL, Alignment, AATags); |
223e47cc LB |
927 | |
928 | // Set up the preheader to have a definition of the value. It is the live-out | |
929 | // value from the preheader that uses in the loop will use. | |
930 | LoadInst *PreheaderLoad = | |
931 | new LoadInst(SomePtr, SomePtr->getName()+".promoted", | |
932 | Preheader->getTerminator()); | |
933 | PreheaderLoad->setAlignment(Alignment); | |
934 | PreheaderLoad->setDebugLoc(DL); | |
1a4d82fc | 935 | if (AATags) PreheaderLoad->setAAMetadata(AATags); |
223e47cc LB |
936 | SSA.AddAvailableValue(Preheader, PreheaderLoad); |
937 | ||
938 | // Rewrite all the loads in the loop and remember all the definitions from | |
939 | // stores in the loop. | |
940 | Promoter.run(LoopUses); | |
941 | ||
942 | // If the SSAUpdater didn't use the load in the preheader, just zap it now. | |
943 | if (PreheaderLoad->use_empty()) | |
944 | PreheaderLoad->eraseFromParent(); | |
945 | } | |
946 | ||
947 | ||
948 | /// cloneBasicBlockAnalysis - Simple Analysis hook. Clone alias set info. | |
949 | void LICM::cloneBasicBlockAnalysis(BasicBlock *From, BasicBlock *To, Loop *L) { | |
950 | AliasSetTracker *AST = LoopToAliasSetMap.lookup(L); | |
951 | if (!AST) | |
952 | return; | |
953 | ||
954 | AST->copyValue(From, To); | |
955 | } | |
956 | ||
957 | /// deleteAnalysisValue - Simple Analysis hook. Delete value V from alias | |
958 | /// set. | |
959 | void LICM::deleteAnalysisValue(Value *V, Loop *L) { | |
960 | AliasSetTracker *AST = LoopToAliasSetMap.lookup(L); | |
961 | if (!AST) | |
962 | return; | |
963 | ||
964 | AST->deleteValue(V); | |
965 | } | |
1a4d82fc JJ |
966 | |
967 | /// Simple Analysis hook. Delete value L from alias set map. | |
968 | void LICM::deleteAnalysisLoop(Loop *L) { | |
969 | AliasSetTracker *AST = LoopToAliasSetMap.lookup(L); | |
970 | if (!AST) | |
971 | return; | |
972 | ||
973 | delete AST; | |
974 | LoopToAliasSetMap.erase(L); | |
975 | } |