/Users/buildslave/jenkins/sharedspace/clang-stage2-coverage-R@2/llvm/lib/Transforms/Scalar/LoopDeletion.cpp
Line | Count | Source (jump to first uncovered line) |
1 | | //===- LoopDeletion.cpp - Dead Loop Deletion 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 file implements the Dead Loop Deletion Pass. This pass is responsible |
11 | | // for eliminating loops with non-infinite computable trip counts that have no |
12 | | // side effects or volatile instructions, and do not contribute to the |
13 | | // computation of the function's return value. |
14 | | // |
15 | | //===----------------------------------------------------------------------===// |
16 | | |
17 | | #include "llvm/Transforms/Scalar/LoopDeletion.h" |
18 | | #include "llvm/ADT/SmallVector.h" |
19 | | #include "llvm/ADT/Statistic.h" |
20 | | #include "llvm/Analysis/GlobalsModRef.h" |
21 | | #include "llvm/Analysis/LoopPass.h" |
22 | | #include "llvm/IR/Dominators.h" |
23 | | #include "llvm/IR/PatternMatch.h" |
24 | | #include "llvm/Transforms/Scalar.h" |
25 | | #include "llvm/Transforms/Scalar/LoopPassManager.h" |
26 | | #include "llvm/Transforms/Utils/LoopUtils.h" |
27 | | using namespace llvm; |
28 | | |
29 | | #define DEBUG_TYPE "loop-delete" |
30 | | |
31 | | STATISTIC(NumDeleted, "Number of loops deleted"); |
32 | | |
33 | | /// This function deletes dead loops. The caller of this function needs to |
34 | | /// guarantee that the loop is infact dead. Here we handle two kinds of dead |
35 | | /// loop. The first kind (\p isLoopDead) is where only invariant values from |
36 | | /// within the loop are used outside of it. The second kind (\p |
37 | | /// isLoopNeverExecuted) is where the loop is provably never executed. We can |
38 | | /// always remove never executed loops since they will not cause any difference |
39 | | /// to program behaviour. |
40 | | /// |
41 | | /// This also updates the relevant analysis information in \p DT, \p SE, and \p |
42 | | /// LI. It also updates the loop PM if an updater struct is provided. |
43 | | // TODO: This function will be used by loop-simplifyCFG as well. So, move this |
44 | | // to LoopUtils.cpp |
45 | | static void deleteDeadLoop(Loop *L, DominatorTree &DT, ScalarEvolution &SE, |
46 | | LoopInfo &LI); |
47 | | |
48 | | enum class LoopDeletionResult { |
49 | | Unmodified, |
50 | | Modified, |
51 | | Deleted, |
52 | | }; |
53 | | |
54 | | /// Determines if a loop is dead. |
55 | | /// |
56 | | /// This assumes that we've already checked for unique exit and exiting blocks, |
57 | | /// and that the code is in LCSSA form. |
58 | | static bool isLoopDead(Loop *L, ScalarEvolution &SE, |
59 | | SmallVectorImpl<BasicBlock *> &ExitingBlocks, |
60 | | BasicBlock *ExitBlock, bool &Changed, |
61 | 257k | BasicBlock *Preheader) { |
62 | 257k | // Make sure that all PHI entries coming from the loop are loop invariant. |
63 | 257k | // Because the code is in LCSSA form, any values used outside of the loop |
64 | 257k | // must pass through a PHI in the exit block, meaning that this check is |
65 | 257k | // sufficient to guarantee that no loop-variant values are used outside |
66 | 257k | // of the loop. |
67 | 257k | BasicBlock::iterator BI = ExitBlock->begin(); |
68 | 257k | bool AllEntriesInvariant = true; |
69 | 257k | bool AllOutgoingValuesSame = true; |
70 | 258k | while (PHINode *P258k = dyn_cast<PHINode>(BI)) { |
71 | 90.4k | Value *incoming = P->getIncomingValueForBlock(ExitingBlocks[0]); |
72 | 90.4k | |
73 | 90.4k | // Make sure all exiting blocks produce the same incoming value for the exit |
74 | 90.4k | // block. If there are different incoming values for different exiting |
75 | 90.4k | // blocks, then it is impossible to statically determine which value should |
76 | 90.4k | // be used. |
77 | 90.4k | AllOutgoingValuesSame = |
78 | 13.0k | all_of(makeArrayRef(ExitingBlocks).slice(1), [&](BasicBlock *BB) { |
79 | 13.0k | return incoming == P->getIncomingValueForBlock(BB); |
80 | 13.0k | }); |
81 | 90.4k | |
82 | 90.4k | if (!AllOutgoingValuesSame) |
83 | 12.2k | break; |
84 | 78.1k | |
85 | 78.1k | if (Instruction *78.1k I78.1k = dyn_cast<Instruction>(incoming)) |
86 | 78.1k | if (78.1k !L->makeLoopInvariant(I, Changed, Preheader->getTerminator())78.1k ) { |
87 | 78.0k | AllEntriesInvariant = false; |
88 | 78.0k | break; |
89 | 78.0k | } |
90 | 71 | |
91 | 71 | ++BI; |
92 | 71 | } |
93 | 257k | |
94 | 257k | if (Changed) |
95 | 3 | SE.forgetLoopDispositions(L); |
96 | 257k | |
97 | 257k | if (!AllEntriesInvariant || 257k !AllOutgoingValuesSame179k ) |
98 | 90.3k | return false; |
99 | 167k | |
100 | 167k | // Make sure that no instructions in the block have potential side-effects. |
101 | 167k | // This includes instructions that could write to memory, and loads that are |
102 | 167k | // marked volatile. |
103 | 167k | for (auto &I : L->blocks()) |
104 | 1.08M | if (203k any_of(*I, [](Instruction &I) 203k { return I.mayHaveSideEffects(); }1.08M )) |
105 | 136k | return false; |
106 | 30.8k | return true; |
107 | 30.8k | } |
108 | | |
109 | | /// This function returns true if there is no viable path from the |
110 | | /// entry block to the header of \p L. Right now, it only does |
111 | | /// a local search to save compile time. |
112 | 257k | static bool isLoopNeverExecuted(Loop *L) { |
113 | 257k | using namespace PatternMatch; |
114 | 257k | |
115 | 257k | auto *Preheader = L->getLoopPreheader(); |
116 | 257k | // TODO: We can relax this constraint, since we just need a loop |
117 | 257k | // predecessor. |
118 | 257k | assert(Preheader && "Needs preheader!"); |
119 | 257k | |
120 | 257k | if (Preheader == &Preheader->getParent()->getEntryBlock()) |
121 | 14.9k | return false; |
122 | 243k | // All predecessors of the preheader should have a constant conditional |
123 | 243k | // branch, with the loop's preheader as not-taken. |
124 | 243k | for (auto *Pred: predecessors(Preheader)) 243k { |
125 | 243k | BasicBlock *Taken, *NotTaken; |
126 | 243k | ConstantInt *Cond; |
127 | 243k | if (!match(Pred->getTerminator(), |
128 | 243k | m_Br(m_ConstantInt(Cond), Taken, NotTaken))) |
129 | 242k | return false; |
130 | 281 | if (281 !Cond->getZExtValue()281 ) |
131 | 107 | std::swap(Taken, NotTaken); |
132 | 281 | if (Taken == Preheader) |
133 | 230 | return false; |
134 | 45 | } |
135 | 243k | assert(!pred_empty(Preheader) && |
136 | 45 | "Preheader should have predecessors at this point!"); |
137 | 45 | // All the predecessors have the loop preheader as not-taken target. |
138 | 45 | return true; |
139 | 45 | } |
140 | | |
141 | | /// Remove a loop if it is dead. |
142 | | /// |
143 | | /// A loop is considered dead if it does not impact the observable behavior of |
144 | | /// the program other than finite running time. This never removes a loop that |
145 | | /// might be infinite (unless it is never executed), as doing so could change |
146 | | /// the halting/non-halting nature of a program. |
147 | | /// |
148 | | /// This entire process relies pretty heavily on LoopSimplify form and LCSSA in |
149 | | /// order to make various safety checks work. |
150 | | /// |
151 | | /// \returns true if any changes were made. This may mutate the loop even if it |
152 | | /// is unable to delete it due to hoisting trivially loop invariant |
153 | | /// instructions out of the loop. |
154 | | static LoopDeletionResult deleteLoopIfDead(Loop *L, DominatorTree &DT, |
155 | 363k | ScalarEvolution &SE, LoopInfo &LI) { |
156 | 363k | assert(L->isLCSSAForm(DT) && "Expected LCSSA!"); |
157 | 363k | |
158 | 363k | // We can only remove the loop if there is a preheader that we can branch from |
159 | 363k | // after removing it. Also, if LoopSimplify form is not available, stay out |
160 | 363k | // of trouble. |
161 | 363k | BasicBlock *Preheader = L->getLoopPreheader(); |
162 | 363k | if (!Preheader || 363k !L->hasDedicatedExits()363k ) { |
163 | 4 | DEBUG(dbgs() |
164 | 4 | << "Deletion requires Loop with preheader and dedicated exits.\n"); |
165 | 4 | return LoopDeletionResult::Unmodified; |
166 | 4 | } |
167 | 363k | // We can't remove loops that contain subloops. If the subloops were dead, |
168 | 363k | // they would already have been removed in earlier executions of this pass. |
169 | 363k | if (363k L->begin() != L->end()363k ) { |
170 | 60.3k | DEBUG(dbgs() << "Loop contains subloops.\n"); |
171 | 60.3k | return LoopDeletionResult::Unmodified; |
172 | 60.3k | } |
173 | 303k | |
174 | 303k | |
175 | 303k | BasicBlock *ExitBlock = L->getUniqueExitBlock(); |
176 | 303k | |
177 | 303k | if (ExitBlock && 303k isLoopNeverExecuted(L)257k ) { |
178 | 45 | DEBUG(dbgs() << "Loop is proven to never execute, delete it!"); |
179 | 45 | // Set incoming value to undef for phi nodes in the exit block. |
180 | 45 | BasicBlock::iterator BI = ExitBlock->begin(); |
181 | 50 | while (PHINode *P50 = dyn_cast<PHINode>(BI)) { |
182 | 18 | for (unsigned i = 0; i < P->getNumIncomingValues()18 ; i++13 ) |
183 | 13 | P->setIncomingValue(i, UndefValue::get(P->getType())); |
184 | 5 | BI++; |
185 | 5 | } |
186 | 45 | deleteDeadLoop(L, DT, SE, LI); |
187 | 45 | ++NumDeleted; |
188 | 45 | return LoopDeletionResult::Deleted; |
189 | 45 | } |
190 | 303k | |
191 | 303k | // The remaining checks below are for a loop being dead because all statements |
192 | 303k | // in the loop are invariant. |
193 | 303k | SmallVector<BasicBlock *, 4> ExitingBlocks; |
194 | 303k | L->getExitingBlocks(ExitingBlocks); |
195 | 303k | |
196 | 303k | // We require that the loop only have a single exit block. Otherwise, we'd |
197 | 303k | // be in the situation of needing to be able to solve statically which exit |
198 | 303k | // block will be branched to, or trying to preserve the branching logic in |
199 | 303k | // a loop invariant manner. |
200 | 303k | if (!ExitBlock303k ) { |
201 | 45.4k | DEBUG(dbgs() << "Deletion requires single exit block\n"); |
202 | 45.4k | return LoopDeletionResult::Unmodified; |
203 | 45.4k | } |
204 | 257k | // Finally, we have to check that the loop really is dead. |
205 | 257k | bool Changed = false; |
206 | 257k | if (!isLoopDead(L, SE, ExitingBlocks, ExitBlock, Changed, Preheader)257k ) { |
207 | 227k | DEBUG(dbgs() << "Loop is not invariant, cannot delete.\n"); |
208 | 3 | return Changed ? LoopDeletionResult::Modified |
209 | 227k | : LoopDeletionResult::Unmodified; |
210 | 227k | } |
211 | 30.8k | |
212 | 30.8k | // Don't remove loops for which we can't solve the trip count. |
213 | 30.8k | // They could be infinite, in which case we'd be changing program behavior. |
214 | 30.8k | const SCEV *S = SE.getMaxBackedgeTakenCount(L); |
215 | 30.8k | if (isa<SCEVCouldNotCompute>(S)30.8k ) { |
216 | 222 | DEBUG(dbgs() << "Could not compute SCEV MaxBackedgeTakenCount.\n"); |
217 | 0 | return Changed ? LoopDeletionResult::Modified |
218 | 222 | : LoopDeletionResult::Unmodified; |
219 | 222 | } |
220 | 30.6k | |
221 | 30.6k | DEBUG30.6k (dbgs() << "Loop is invariant, delete it!"); |
222 | 30.6k | deleteDeadLoop(L, DT, SE, LI); |
223 | 30.6k | ++NumDeleted; |
224 | 30.6k | |
225 | 30.6k | return LoopDeletionResult::Deleted; |
226 | 30.6k | } |
227 | | |
228 | | static void deleteDeadLoop(Loop *L, DominatorTree &DT, ScalarEvolution &SE, |
229 | 30.6k | LoopInfo &LI) { |
230 | 30.6k | assert(L->isLCSSAForm(DT) && "Expected LCSSA!"); |
231 | 30.6k | auto *Preheader = L->getLoopPreheader(); |
232 | 30.6k | assert(Preheader && "Preheader should exist!"); |
233 | 30.6k | |
234 | 30.6k | // Now that we know the removal is safe, remove the loop by changing the |
235 | 30.6k | // branch from the preheader to go to the single exit block. |
236 | 30.6k | // |
237 | 30.6k | // Because we're deleting a large chunk of code at once, the sequence in which |
238 | 30.6k | // we remove things is very important to avoid invalidation issues. |
239 | 30.6k | |
240 | 30.6k | // Tell ScalarEvolution that the loop is deleted. Do this before |
241 | 30.6k | // deleting the loop so that ScalarEvolution can look at the loop |
242 | 30.6k | // to determine what it needs to clean up. |
243 | 30.6k | SE.forgetLoop(L); |
244 | 30.6k | |
245 | 30.6k | auto *ExitBlock = L->getUniqueExitBlock(); |
246 | 30.6k | assert(ExitBlock && "Should have a unique exit block!"); |
247 | 30.6k | assert(L->hasDedicatedExits() && "Loop should have dedicated exits!"); |
248 | 30.6k | |
249 | 30.6k | auto *OldBr = dyn_cast<BranchInst>(Preheader->getTerminator()); |
250 | 30.6k | assert(OldBr && "Preheader must end with a branch"); |
251 | 30.6k | assert(OldBr->isUnconditional() && "Preheader must have a single successor"); |
252 | 30.6k | // Connect the preheader to the exit block. Keep the old edge to the header |
253 | 30.6k | // around to perform the dominator tree update in two separate steps |
254 | 30.6k | // -- #1 insertion of the edge preheader -> exit and #2 deletion of the edge |
255 | 30.6k | // preheader -> header. |
256 | 30.6k | // |
257 | 30.6k | // |
258 | 30.6k | // 0. Preheader 1. Preheader 2. Preheader |
259 | 30.6k | // | | | | |
260 | 30.6k | // V | V | |
261 | 30.6k | // Header <--\ | Header <--\ | Header <--\ |
262 | 30.6k | // | | | | | | | | | | | |
263 | 30.6k | // | V | | | V | | | V | |
264 | 30.6k | // | Body --/ | | Body --/ | | Body --/ |
265 | 30.6k | // V V V V V |
266 | 30.6k | // Exit Exit Exit |
267 | 30.6k | // |
268 | 30.6k | // By doing this is two separate steps we can perform the dominator tree |
269 | 30.6k | // update without using the batch update API. |
270 | 30.6k | // |
271 | 30.6k | // Even when the loop is never executed, we cannot remove the edge from the |
272 | 30.6k | // source block to the exit block. Consider the case where the unexecuted loop |
273 | 30.6k | // branches back to an outer loop. If we deleted the loop and removed the edge |
274 | 30.6k | // coming to this inner loop, this will break the outer loop structure (by |
275 | 30.6k | // deleting the backedge of the outer loop). If the outer loop is indeed a |
276 | 30.6k | // non-loop, it will be deleted in a future iteration of loop deletion pass. |
277 | 30.6k | IRBuilder<> Builder(OldBr); |
278 | 30.6k | Builder.CreateCondBr(Builder.getFalse(), L->getHeader(), ExitBlock); |
279 | 30.6k | // Remove the old branch. The conditional branch becomes a new terminator. |
280 | 30.6k | OldBr->eraseFromParent(); |
281 | 30.6k | |
282 | 30.6k | // Update the dominator tree by informing it about the new edge from the |
283 | 30.6k | // preheader to the exit. |
284 | 30.6k | DT.insertEdge(Preheader, ExitBlock); |
285 | 30.6k | |
286 | 30.6k | // Rewrite phis in the exit block to get their inputs from the Preheader |
287 | 30.6k | // instead of the exiting block. |
288 | 30.6k | BasicBlock::iterator BI = ExitBlock->begin(); |
289 | 30.7k | while (PHINode *P30.7k = dyn_cast<PHINode>(BI)) { |
290 | 53 | // Set the zero'th element of Phi to be from the preheader and remove all |
291 | 53 | // other incoming values. Given the loop has dedicated exits, all other |
292 | 53 | // incoming values must be from the exiting blocks. |
293 | 53 | int PredIndex = 0; |
294 | 53 | P->setIncomingBlock(PredIndex, Preheader); |
295 | 53 | // Removes all incoming values from all other exiting blocks (including |
296 | 53 | // duplicate values from an exiting block). |
297 | 53 | // Nuke all entries except the zero'th entry which is the preheader entry. |
298 | 53 | // NOTE! We need to remove Incoming Values in the reverse order as done |
299 | 53 | // below, to keep the indices valid for deletion (removeIncomingValues |
300 | 53 | // updates getNumIncomingValues and shifts all values down into the operand |
301 | 53 | // being deleted). |
302 | 66 | for (unsigned i = 0, e = P->getNumIncomingValues() - 1; i != e66 ; ++i13 ) |
303 | 13 | P->removeIncomingValue(e-i, false); |
304 | 53 | |
305 | 53 | assert((P->getNumIncomingValues() == 1 && |
306 | 53 | P->getIncomingBlock(PredIndex) == Preheader) && |
307 | 53 | "Should have exactly one value and that's from the preheader!"); |
308 | 53 | ++BI; |
309 | 53 | } |
310 | 30.6k | |
311 | 30.6k | // Disconnect the loop body by branching directly to its exit. |
312 | 30.6k | Builder.SetInsertPoint(Preheader->getTerminator()); |
313 | 30.6k | Builder.CreateBr(ExitBlock); |
314 | 30.6k | // Remove the old branch. |
315 | 30.6k | Preheader->getTerminator()->eraseFromParent(); |
316 | 30.6k | |
317 | 30.6k | // Inform the dominator tree about the removed edge. |
318 | 30.6k | DT.deleteEdge(Preheader, L->getHeader()); |
319 | 30.6k | |
320 | 30.6k | // Remove the block from the reference counting scheme, so that we can |
321 | 30.6k | // delete it freely later. |
322 | 30.6k | for (auto *Block : L->blocks()) |
323 | 34.0k | Block->dropAllReferences(); |
324 | 30.6k | |
325 | 30.6k | // Erase the instructions and the blocks without having to worry |
326 | 30.6k | // about ordering because we already dropped the references. |
327 | 30.6k | // NOTE: This iteration is safe because erasing the block does not remove its |
328 | 30.6k | // entry from the loop's block list. We do that in the next section. |
329 | 30.6k | for (Loop::block_iterator LI = L->block_begin(), LE = L->block_end(); |
330 | 64.6k | LI != LE64.6k ; ++LI34.0k ) |
331 | 34.0k | (*LI)->eraseFromParent(); |
332 | 30.6k | |
333 | 30.6k | // Finally, the blocks from loopinfo. This has to happen late because |
334 | 30.6k | // otherwise our loop iterators won't work. |
335 | 30.6k | |
336 | 30.6k | SmallPtrSet<BasicBlock *, 8> blocks; |
337 | 30.6k | blocks.insert(L->block_begin(), L->block_end()); |
338 | 30.6k | for (BasicBlock *BB : blocks) |
339 | 34.0k | LI.removeBlock(BB); |
340 | 30.6k | |
341 | 30.6k | // The last step is to update LoopInfo now that we've eliminated this loop. |
342 | 30.6k | LI.erase(L); |
343 | 30.6k | } |
344 | | |
345 | | PreservedAnalyses LoopDeletionPass::run(Loop &L, LoopAnalysisManager &AM, |
346 | | LoopStandardAnalysisResults &AR, |
347 | 43 | LPMUpdater &Updater) { |
348 | 43 | |
349 | 43 | DEBUG(dbgs() << "Analyzing Loop for deletion: "); |
350 | 43 | DEBUG(L.dump()); |
351 | 43 | std::string LoopName = L.getName(); |
352 | 43 | auto Result = deleteLoopIfDead(&L, AR.DT, AR.SE, AR.LI); |
353 | 43 | if (Result == LoopDeletionResult::Unmodified) |
354 | 37 | return PreservedAnalyses::all(); |
355 | 6 | |
356 | 6 | if (6 Result == LoopDeletionResult::Deleted6 ) |
357 | 6 | Updater.markLoopAsDeleted(L, LoopName); |
358 | 43 | |
359 | 43 | return getLoopPassPreservedAnalyses(); |
360 | 43 | } |
361 | | |
362 | | namespace { |
363 | | class LoopDeletionLegacyPass : public LoopPass { |
364 | | public: |
365 | | static char ID; // Pass ID, replacement for typeid |
366 | 17.4k | LoopDeletionLegacyPass() : LoopPass(ID) { |
367 | 17.4k | initializeLoopDeletionLegacyPassPass(*PassRegistry::getPassRegistry()); |
368 | 17.4k | } |
369 | | |
370 | | // Possibly eliminate loop L if it is dead. |
371 | | bool runOnLoop(Loop *L, LPPassManager &) override; |
372 | | |
373 | 17.4k | void getAnalysisUsage(AnalysisUsage &AU) const override { |
374 | 17.4k | getLoopAnalysisUsage(AU); |
375 | 17.4k | } |
376 | | }; |
377 | | } |
378 | | |
379 | | char LoopDeletionLegacyPass::ID = 0; |
380 | 41.8k | INITIALIZE_PASS_BEGIN41.8k (LoopDeletionLegacyPass, "loop-deletion",
|
381 | 41.8k | "Delete dead loops", false, false) |
382 | 41.8k | INITIALIZE_PASS_DEPENDENCY(LoopPass) |
383 | 41.8k | INITIALIZE_PASS_END(LoopDeletionLegacyPass, "loop-deletion", |
384 | | "Delete dead loops", false, false) |
385 | | |
386 | 17.4k | Pass *llvm::createLoopDeletionPass() { return new LoopDeletionLegacyPass(); } |
387 | | |
388 | 363k | bool LoopDeletionLegacyPass::runOnLoop(Loop *L, LPPassManager &LPM) { |
389 | 363k | if (skipLoop(L)) |
390 | 15 | return false; |
391 | 363k | DominatorTree &DT = getAnalysis<DominatorTreeWrapperPass>().getDomTree(); |
392 | 363k | ScalarEvolution &SE = getAnalysis<ScalarEvolutionWrapperPass>().getSE(); |
393 | 363k | LoopInfo &LI = getAnalysis<LoopInfoWrapperPass>().getLoopInfo(); |
394 | 363k | |
395 | 363k | DEBUG(dbgs() << "Analyzing Loop for deletion: "); |
396 | 363k | DEBUG(L->dump()); |
397 | 363k | |
398 | 363k | LoopDeletionResult Result = deleteLoopIfDead(L, DT, SE, LI); |
399 | 363k | |
400 | 363k | if (Result == LoopDeletionResult::Deleted) |
401 | 30.6k | LPM.markLoopAsDeleted(*L); |
402 | 363k | |
403 | 363k | return Result != LoopDeletionResult::Unmodified; |
404 | 363k | } |