File: | src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/lib/Transforms/Scalar/LoopDeletion.cpp |
Warning: | line 75, column 23 Called C++ object pointer is null |
Press '?' to see keyboard shortcuts
Keyboard shortcuts:
1 | //===- LoopDeletion.cpp - Dead Loop Deletion Pass ---------------===// | |||
2 | // | |||
3 | // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. | |||
4 | // See https://llvm.org/LICENSE.txt for license information. | |||
5 | // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception | |||
6 | // | |||
7 | //===----------------------------------------------------------------------===// | |||
8 | // | |||
9 | // This file implements the Dead Loop Deletion Pass. This pass is responsible | |||
10 | // for eliminating loops with non-infinite computable trip counts that have no | |||
11 | // side effects or volatile instructions, and do not contribute to the | |||
12 | // computation of the function's return value. | |||
13 | // | |||
14 | //===----------------------------------------------------------------------===// | |||
15 | ||||
16 | #include "llvm/Transforms/Scalar/LoopDeletion.h" | |||
17 | #include "llvm/ADT/SmallVector.h" | |||
18 | #include "llvm/ADT/Statistic.h" | |||
19 | #include "llvm/Analysis/CFG.h" | |||
20 | #include "llvm/Analysis/GlobalsModRef.h" | |||
21 | #include "llvm/Analysis/InstructionSimplify.h" | |||
22 | #include "llvm/Analysis/LoopIterator.h" | |||
23 | #include "llvm/Analysis/LoopPass.h" | |||
24 | #include "llvm/Analysis/MemorySSA.h" | |||
25 | #include "llvm/Analysis/OptimizationRemarkEmitter.h" | |||
26 | #include "llvm/IR/Dominators.h" | |||
27 | ||||
28 | #include "llvm/IR/PatternMatch.h" | |||
29 | #include "llvm/InitializePasses.h" | |||
30 | #include "llvm/Transforms/Scalar.h" | |||
31 | #include "llvm/Transforms/Scalar/LoopPassManager.h" | |||
32 | #include "llvm/Transforms/Utils/LoopUtils.h" | |||
33 | ||||
34 | using namespace llvm; | |||
35 | ||||
36 | #define DEBUG_TYPE"loop-delete" "loop-delete" | |||
37 | ||||
38 | STATISTIC(NumDeleted, "Number of loops deleted")static llvm::Statistic NumDeleted = {"loop-delete", "NumDeleted" , "Number of loops deleted"}; | |||
39 | ||||
40 | static cl::opt<bool> EnableSymbolicExecution( | |||
41 | "loop-deletion-enable-symbolic-execution", cl::Hidden, cl::init(true), | |||
42 | cl::desc("Break backedge through symbolic execution of 1st iteration " | |||
43 | "attempting to prove that the backedge is never taken")); | |||
44 | ||||
45 | enum class LoopDeletionResult { | |||
46 | Unmodified, | |||
47 | Modified, | |||
48 | Deleted, | |||
49 | }; | |||
50 | ||||
51 | static LoopDeletionResult merge(LoopDeletionResult A, LoopDeletionResult B) { | |||
52 | if (A == LoopDeletionResult::Deleted || B == LoopDeletionResult::Deleted) | |||
53 | return LoopDeletionResult::Deleted; | |||
54 | if (A == LoopDeletionResult::Modified || B == LoopDeletionResult::Modified) | |||
55 | return LoopDeletionResult::Modified; | |||
56 | return LoopDeletionResult::Unmodified; | |||
57 | } | |||
58 | ||||
59 | /// Determines if a loop is dead. | |||
60 | /// | |||
61 | /// This assumes that we've already checked for unique exit and exiting blocks, | |||
62 | /// and that the code is in LCSSA form. | |||
63 | static bool isLoopDead(Loop *L, ScalarEvolution &SE, | |||
64 | SmallVectorImpl<BasicBlock *> &ExitingBlocks, | |||
65 | BasicBlock *ExitBlock, bool &Changed, | |||
66 | BasicBlock *Preheader, LoopInfo &LI) { | |||
67 | // Make sure that all PHI entries coming from the loop are loop invariant. | |||
68 | // Because the code is in LCSSA form, any values used outside of the loop | |||
69 | // must pass through a PHI in the exit block, meaning that this check is | |||
70 | // sufficient to guarantee that no loop-variant values are used outside | |||
71 | // of the loop. | |||
72 | bool AllEntriesInvariant = true; | |||
73 | bool AllOutgoingValuesSame = true; | |||
74 | if (!L->hasNoExitBlocks()) { | |||
75 | for (PHINode &P : ExitBlock->phis()) { | |||
| ||||
76 | Value *incoming = P.getIncomingValueForBlock(ExitingBlocks[0]); | |||
77 | ||||
78 | // Make sure all exiting blocks produce the same incoming value for the | |||
79 | // block. If there are different incoming values for different exiting | |||
80 | // blocks, then it is impossible to statically determine which value | |||
81 | // should be used. | |||
82 | AllOutgoingValuesSame = | |||
83 | all_of(makeArrayRef(ExitingBlocks).slice(1), [&](BasicBlock *BB) { | |||
84 | return incoming == P.getIncomingValueForBlock(BB); | |||
85 | }); | |||
86 | ||||
87 | if (!AllOutgoingValuesSame) | |||
88 | break; | |||
89 | ||||
90 | if (Instruction *I = dyn_cast<Instruction>(incoming)) | |||
91 | if (!L->makeLoopInvariant(I, Changed, Preheader->getTerminator())) { | |||
92 | AllEntriesInvariant = false; | |||
93 | break; | |||
94 | } | |||
95 | } | |||
96 | } | |||
97 | ||||
98 | if (Changed) | |||
99 | SE.forgetLoopDispositions(L); | |||
100 | ||||
101 | if (!AllEntriesInvariant || !AllOutgoingValuesSame) | |||
102 | return false; | |||
103 | ||||
104 | // Make sure that no instructions in the block have potential side-effects. | |||
105 | // This includes instructions that could write to memory, and loads that are | |||
106 | // marked volatile. | |||
107 | for (auto &I : L->blocks()) | |||
108 | if (any_of(*I, [](Instruction &I) { | |||
109 | return I.mayHaveSideEffects() && !I.isDroppable(); | |||
110 | })) | |||
111 | return false; | |||
112 | ||||
113 | // The loop or any of its sub-loops looping infinitely is legal. The loop can | |||
114 | // only be considered dead if either | |||
115 | // a. the function is mustprogress. | |||
116 | // b. all (sub-)loops are mustprogress or have a known trip-count. | |||
117 | if (L->getHeader()->getParent()->mustProgress()) | |||
118 | return true; | |||
119 | ||||
120 | LoopBlocksRPO RPOT(L); | |||
121 | RPOT.perform(&LI); | |||
122 | // If the loop contains an irreducible cycle, it may loop infinitely. | |||
123 | if (containsIrreducibleCFG<const BasicBlock *>(RPOT, LI)) | |||
124 | return false; | |||
125 | ||||
126 | SmallVector<Loop *, 8> WorkList; | |||
127 | WorkList.push_back(L); | |||
128 | while (!WorkList.empty()) { | |||
129 | Loop *Current = WorkList.pop_back_val(); | |||
130 | if (hasMustProgress(Current)) | |||
131 | continue; | |||
132 | ||||
133 | const SCEV *S = SE.getConstantMaxBackedgeTakenCount(Current); | |||
134 | if (isa<SCEVCouldNotCompute>(S)) { | |||
135 | LLVM_DEBUG(do { } while (false) | |||
136 | dbgs() << "Could not compute SCEV MaxBackedgeTakenCount and was "do { } while (false) | |||
137 | "not required to make progress.\n")do { } while (false); | |||
138 | return false; | |||
139 | } | |||
140 | WorkList.append(Current->begin(), Current->end()); | |||
141 | } | |||
142 | return true; | |||
143 | } | |||
144 | ||||
145 | /// This function returns true if there is no viable path from the | |||
146 | /// entry block to the header of \p L. Right now, it only does | |||
147 | /// a local search to save compile time. | |||
148 | static bool isLoopNeverExecuted(Loop *L) { | |||
149 | using namespace PatternMatch; | |||
150 | ||||
151 | auto *Preheader = L->getLoopPreheader(); | |||
152 | // TODO: We can relax this constraint, since we just need a loop | |||
153 | // predecessor. | |||
154 | assert(Preheader && "Needs preheader!")((void)0); | |||
155 | ||||
156 | if (Preheader->isEntryBlock()) | |||
157 | return false; | |||
158 | // All predecessors of the preheader should have a constant conditional | |||
159 | // branch, with the loop's preheader as not-taken. | |||
160 | for (auto *Pred: predecessors(Preheader)) { | |||
161 | BasicBlock *Taken, *NotTaken; | |||
162 | ConstantInt *Cond; | |||
163 | if (!match(Pred->getTerminator(), | |||
164 | m_Br(m_ConstantInt(Cond), Taken, NotTaken))) | |||
165 | return false; | |||
166 | if (!Cond->getZExtValue()) | |||
167 | std::swap(Taken, NotTaken); | |||
168 | if (Taken == Preheader) | |||
169 | return false; | |||
170 | } | |||
171 | assert(!pred_empty(Preheader) &&((void)0) | |||
172 | "Preheader should have predecessors at this point!")((void)0); | |||
173 | // All the predecessors have the loop preheader as not-taken target. | |||
174 | return true; | |||
175 | } | |||
176 | ||||
177 | static Value * | |||
178 | getValueOnFirstIteration(Value *V, DenseMap<Value *, Value *> &FirstIterValue, | |||
179 | const SimplifyQuery &SQ) { | |||
180 | // Quick hack: do not flood cache with non-instruction values. | |||
181 | if (!isa<Instruction>(V)) | |||
182 | return V; | |||
183 | // Do we already know cached result? | |||
184 | auto Existing = FirstIterValue.find(V); | |||
185 | if (Existing != FirstIterValue.end()) | |||
186 | return Existing->second; | |||
187 | Value *FirstIterV = nullptr; | |||
188 | if (auto *BO = dyn_cast<BinaryOperator>(V)) { | |||
189 | Value *LHS = | |||
190 | getValueOnFirstIteration(BO->getOperand(0), FirstIterValue, SQ); | |||
191 | Value *RHS = | |||
192 | getValueOnFirstIteration(BO->getOperand(1), FirstIterValue, SQ); | |||
193 | FirstIterV = SimplifyBinOp(BO->getOpcode(), LHS, RHS, SQ); | |||
194 | } | |||
195 | if (!FirstIterV) | |||
196 | FirstIterV = V; | |||
197 | FirstIterValue[V] = FirstIterV; | |||
198 | return FirstIterV; | |||
199 | } | |||
200 | ||||
201 | // Try to prove that one of conditions that dominates the latch must exit on 1st | |||
202 | // iteration. | |||
203 | static bool canProveExitOnFirstIteration(Loop *L, DominatorTree &DT, | |||
204 | LoopInfo &LI) { | |||
205 | // Disabled by option. | |||
206 | if (!EnableSymbolicExecution) | |||
207 | return false; | |||
208 | ||||
209 | BasicBlock *Predecessor = L->getLoopPredecessor(); | |||
210 | BasicBlock *Latch = L->getLoopLatch(); | |||
211 | ||||
212 | if (!Predecessor || !Latch) | |||
213 | return false; | |||
214 | ||||
215 | LoopBlocksRPO RPOT(L); | |||
216 | RPOT.perform(&LI); | |||
217 | ||||
218 | // For the optimization to be correct, we need RPOT to have a property that | |||
219 | // each block is processed after all its predecessors, which may only be | |||
220 | // violated for headers of the current loop and all nested loops. Irreducible | |||
221 | // CFG provides multiple ways to break this assumption, so we do not want to | |||
222 | // deal with it. | |||
223 | if (containsIrreducibleCFG<const BasicBlock *>(RPOT, LI)) | |||
224 | return false; | |||
225 | ||||
226 | BasicBlock *Header = L->getHeader(); | |||
227 | // Blocks that are reachable on the 1st iteration. | |||
228 | SmallPtrSet<BasicBlock *, 4> LiveBlocks; | |||
229 | // Edges that are reachable on the 1st iteration. | |||
230 | DenseSet<BasicBlockEdge> LiveEdges; | |||
231 | LiveBlocks.insert(Header); | |||
232 | ||||
233 | SmallPtrSet<BasicBlock *, 4> Visited; | |||
234 | auto MarkLiveEdge = [&](BasicBlock *From, BasicBlock *To) { | |||
235 | assert(LiveBlocks.count(From) && "Must be live!")((void)0); | |||
236 | assert((LI.isLoopHeader(To) || !Visited.count(To)) &&((void)0) | |||
237 | "Only canonical backedges are allowed. Irreducible CFG?")((void)0); | |||
238 | assert((LiveBlocks.count(To) || !Visited.count(To)) &&((void)0) | |||
239 | "We already discarded this block as dead!")((void)0); | |||
240 | LiveBlocks.insert(To); | |||
241 | LiveEdges.insert({ From, To }); | |||
242 | }; | |||
243 | ||||
244 | auto MarkAllSuccessorsLive = [&](BasicBlock *BB) { | |||
245 | for (auto *Succ : successors(BB)) | |||
246 | MarkLiveEdge(BB, Succ); | |||
247 | }; | |||
248 | ||||
249 | // Check if there is only one value coming from all live predecessor blocks. | |||
250 | // Note that because we iterate in RPOT, we have already visited all its | |||
251 | // (non-latch) predecessors. | |||
252 | auto GetSoleInputOnFirstIteration = [&](PHINode & PN)->Value * { | |||
253 | BasicBlock *BB = PN.getParent(); | |||
254 | bool HasLivePreds = false; | |||
255 | (void)HasLivePreds; | |||
256 | if (BB == Header) | |||
257 | return PN.getIncomingValueForBlock(Predecessor); | |||
258 | Value *OnlyInput = nullptr; | |||
259 | for (auto *Pred : predecessors(BB)) | |||
260 | if (LiveEdges.count({ Pred, BB })) { | |||
261 | HasLivePreds = true; | |||
262 | Value *Incoming = PN.getIncomingValueForBlock(Pred); | |||
263 | // Skip undefs. If they are present, we can assume they are equal to | |||
264 | // the non-undef input. | |||
265 | if (isa<UndefValue>(Incoming)) | |||
266 | continue; | |||
267 | // Two inputs. | |||
268 | if (OnlyInput && OnlyInput != Incoming) | |||
269 | return nullptr; | |||
270 | OnlyInput = Incoming; | |||
271 | } | |||
272 | ||||
273 | assert(HasLivePreds && "No live predecessors?")((void)0); | |||
274 | // If all incoming live value were undefs, return undef. | |||
275 | return OnlyInput ? OnlyInput : UndefValue::get(PN.getType()); | |||
276 | }; | |||
277 | DenseMap<Value *, Value *> FirstIterValue; | |||
278 | ||||
279 | // Use the following algorithm to prove we never take the latch on the 1st | |||
280 | // iteration: | |||
281 | // 1. Traverse in topological order, so that whenever we visit a block, all | |||
282 | // its predecessors are already visited. | |||
283 | // 2. If we can prove that the block may have only 1 predecessor on the 1st | |||
284 | // iteration, map all its phis onto input from this predecessor. | |||
285 | // 3a. If we can prove which successor of out block is taken on the 1st | |||
286 | // iteration, mark this successor live. | |||
287 | // 3b. If we cannot prove it, conservatively assume that all successors are | |||
288 | // live. | |||
289 | auto &DL = Header->getModule()->getDataLayout(); | |||
290 | const SimplifyQuery SQ(DL); | |||
291 | for (auto *BB : RPOT) { | |||
292 | Visited.insert(BB); | |||
293 | ||||
294 | // This block is not reachable on the 1st iterations. | |||
295 | if (!LiveBlocks.count(BB)) | |||
296 | continue; | |||
297 | ||||
298 | // Skip inner loops. | |||
299 | if (LI.getLoopFor(BB) != L) { | |||
300 | MarkAllSuccessorsLive(BB); | |||
301 | continue; | |||
302 | } | |||
303 | ||||
304 | // If Phi has only one input from all live input blocks, use it. | |||
305 | for (auto &PN : BB->phis()) { | |||
306 | if (!PN.getType()->isIntegerTy()) | |||
307 | continue; | |||
308 | auto *Incoming = GetSoleInputOnFirstIteration(PN); | |||
309 | if (Incoming && DT.dominates(Incoming, BB->getTerminator())) { | |||
310 | Value *FirstIterV = | |||
311 | getValueOnFirstIteration(Incoming, FirstIterValue, SQ); | |||
312 | FirstIterValue[&PN] = FirstIterV; | |||
313 | } | |||
314 | } | |||
315 | ||||
316 | using namespace PatternMatch; | |||
317 | ICmpInst::Predicate Pred; | |||
318 | Value *LHS, *RHS; | |||
319 | BasicBlock *IfTrue, *IfFalse; | |||
320 | auto *Term = BB->getTerminator(); | |||
321 | if (match(Term, m_Br(m_ICmp(Pred, m_Value(LHS), m_Value(RHS)), | |||
322 | m_BasicBlock(IfTrue), m_BasicBlock(IfFalse)))) { | |||
323 | if (!LHS->getType()->isIntegerTy()) { | |||
324 | MarkAllSuccessorsLive(BB); | |||
325 | continue; | |||
326 | } | |||
327 | ||||
328 | // Can we prove constant true or false for this condition? | |||
329 | LHS = getValueOnFirstIteration(LHS, FirstIterValue, SQ); | |||
330 | RHS = getValueOnFirstIteration(RHS, FirstIterValue, SQ); | |||
331 | auto *KnownCondition = SimplifyICmpInst(Pred, LHS, RHS, SQ); | |||
332 | if (!KnownCondition) { | |||
333 | // Failed to simplify. | |||
334 | MarkAllSuccessorsLive(BB); | |||
335 | continue; | |||
336 | } | |||
337 | if (isa<UndefValue>(KnownCondition)) { | |||
338 | // TODO: According to langref, branching by undef is undefined behavior. | |||
339 | // It means that, theoretically, we should be able to just continue | |||
340 | // without marking any successors as live. However, we are not certain | |||
341 | // how correct our compiler is at handling such cases. So we are being | |||
342 | // very conservative here. | |||
343 | // | |||
344 | // If there is a non-loop successor, always assume this branch leaves the | |||
345 | // loop. Otherwise, arbitrarily take IfTrue. | |||
346 | // | |||
347 | // Once we are certain that branching by undef is handled correctly by | |||
348 | // other transforms, we should not mark any successors live here. | |||
349 | if (L->contains(IfTrue) && L->contains(IfFalse)) | |||
350 | MarkLiveEdge(BB, IfTrue); | |||
351 | continue; | |||
352 | } | |||
353 | auto *ConstCondition = dyn_cast<ConstantInt>(KnownCondition); | |||
354 | if (!ConstCondition) { | |||
355 | // Non-constant condition, cannot analyze any further. | |||
356 | MarkAllSuccessorsLive(BB); | |||
357 | continue; | |||
358 | } | |||
359 | if (ConstCondition->isAllOnesValue()) | |||
360 | MarkLiveEdge(BB, IfTrue); | |||
361 | else | |||
362 | MarkLiveEdge(BB, IfFalse); | |||
363 | } else if (SwitchInst *SI = dyn_cast<SwitchInst>(Term)) { | |||
364 | auto *SwitchValue = SI->getCondition(); | |||
365 | auto *SwitchValueOnFirstIter = | |||
366 | getValueOnFirstIteration(SwitchValue, FirstIterValue, SQ); | |||
367 | auto *ConstSwitchValue = dyn_cast<ConstantInt>(SwitchValueOnFirstIter); | |||
368 | if (!ConstSwitchValue) { | |||
369 | MarkAllSuccessorsLive(BB); | |||
370 | continue; | |||
371 | } | |||
372 | auto CaseIterator = SI->findCaseValue(ConstSwitchValue); | |||
373 | MarkLiveEdge(BB, CaseIterator->getCaseSuccessor()); | |||
374 | } else { | |||
375 | MarkAllSuccessorsLive(BB); | |||
376 | continue; | |||
377 | } | |||
378 | } | |||
379 | ||||
380 | // We can break the latch if it wasn't live. | |||
381 | return !LiveEdges.count({ Latch, Header }); | |||
382 | } | |||
383 | ||||
384 | /// If we can prove the backedge is untaken, remove it. This destroys the | |||
385 | /// loop, but leaves the (now trivially loop invariant) control flow and | |||
386 | /// side effects (if any) in place. | |||
387 | static LoopDeletionResult | |||
388 | breakBackedgeIfNotTaken(Loop *L, DominatorTree &DT, ScalarEvolution &SE, | |||
389 | LoopInfo &LI, MemorySSA *MSSA, | |||
390 | OptimizationRemarkEmitter &ORE) { | |||
391 | assert(L->isLCSSAForm(DT) && "Expected LCSSA!")((void)0); | |||
392 | ||||
393 | if (!L->getLoopLatch()) | |||
394 | return LoopDeletionResult::Unmodified; | |||
395 | ||||
396 | auto *BTC = SE.getBackedgeTakenCount(L); | |||
397 | if (!isa<SCEVCouldNotCompute>(BTC) && SE.isKnownNonZero(BTC)) | |||
398 | return LoopDeletionResult::Unmodified; | |||
399 | if (!BTC->isZero() && !canProveExitOnFirstIteration(L, DT, LI)) | |||
400 | return LoopDeletionResult::Unmodified; | |||
401 | ||||
402 | breakLoopBackedge(L, DT, SE, LI, MSSA); | |||
403 | return LoopDeletionResult::Deleted; | |||
404 | } | |||
405 | ||||
406 | /// Remove a loop if it is dead. | |||
407 | /// | |||
408 | /// A loop is considered dead either if it does not impact the observable | |||
409 | /// behavior of the program other than finite running time, or if it is | |||
410 | /// required to make progress by an attribute such as 'mustprogress' or | |||
411 | /// 'llvm.loop.mustprogress' and does not make any. This may remove | |||
412 | /// infinite loops that have been required to make progress. | |||
413 | /// | |||
414 | /// This entire process relies pretty heavily on LoopSimplify form and LCSSA in | |||
415 | /// order to make various safety checks work. | |||
416 | /// | |||
417 | /// \returns true if any changes were made. This may mutate the loop even if it | |||
418 | /// is unable to delete it due to hoisting trivially loop invariant | |||
419 | /// instructions out of the loop. | |||
420 | static LoopDeletionResult deleteLoopIfDead(Loop *L, DominatorTree &DT, | |||
421 | ScalarEvolution &SE, LoopInfo &LI, | |||
422 | MemorySSA *MSSA, | |||
423 | OptimizationRemarkEmitter &ORE) { | |||
424 | assert(L->isLCSSAForm(DT) && "Expected LCSSA!")((void)0); | |||
425 | ||||
426 | // We can only remove the loop if there is a preheader that we can branch from | |||
427 | // after removing it. Also, if LoopSimplify form is not available, stay out | |||
428 | // of trouble. | |||
429 | BasicBlock *Preheader = L->getLoopPreheader(); | |||
430 | if (!Preheader || !L->hasDedicatedExits()) { | |||
431 | LLVM_DEBUG(do { } while (false) | |||
432 | dbgs()do { } while (false) | |||
433 | << "Deletion requires Loop with preheader and dedicated exits.\n")do { } while (false); | |||
434 | return LoopDeletionResult::Unmodified; | |||
435 | } | |||
436 | ||||
437 | BasicBlock *ExitBlock = L->getUniqueExitBlock(); | |||
438 | ||||
439 | if (ExitBlock && isLoopNeverExecuted(L)) { | |||
440 | LLVM_DEBUG(dbgs() << "Loop is proven to never execute, delete it!")do { } while (false); | |||
441 | // We need to forget the loop before setting the incoming values of the exit | |||
442 | // phis to undef, so we properly invalidate the SCEV expressions for those | |||
443 | // phis. | |||
444 | SE.forgetLoop(L); | |||
445 | // Set incoming value to undef for phi nodes in the exit block. | |||
446 | for (PHINode &P : ExitBlock->phis()) { | |||
447 | std::fill(P.incoming_values().begin(), P.incoming_values().end(), | |||
448 | UndefValue::get(P.getType())); | |||
449 | } | |||
450 | ORE.emit([&]() { | |||
451 | return OptimizationRemark(DEBUG_TYPE"loop-delete", "NeverExecutes", L->getStartLoc(), | |||
452 | L->getHeader()) | |||
453 | << "Loop deleted because it never executes"; | |||
454 | }); | |||
455 | deleteDeadLoop(L, &DT, &SE, &LI, MSSA); | |||
456 | ++NumDeleted; | |||
457 | return LoopDeletionResult::Deleted; | |||
458 | } | |||
459 | ||||
460 | // The remaining checks below are for a loop being dead because all statements | |||
461 | // in the loop are invariant. | |||
462 | SmallVector<BasicBlock *, 4> ExitingBlocks; | |||
463 | L->getExitingBlocks(ExitingBlocks); | |||
464 | ||||
465 | // We require that the loop has at most one exit block. Otherwise, we'd be in | |||
466 | // the situation of needing to be able to solve statically which exit block | |||
467 | // will be branched to, or trying to preserve the branching logic in a loop | |||
468 | // invariant manner. | |||
469 | if (!ExitBlock
| |||
470 | LLVM_DEBUG(dbgs() << "Deletion requires at most one exit block.\n")do { } while (false); | |||
471 | return LoopDeletionResult::Unmodified; | |||
472 | } | |||
473 | // Finally, we have to check that the loop really is dead. | |||
474 | bool Changed = false; | |||
475 | if (!isLoopDead(L, SE, ExitingBlocks, ExitBlock, Changed, Preheader, LI)) { | |||
476 | LLVM_DEBUG(dbgs() << "Loop is not invariant, cannot delete.\n")do { } while (false); | |||
477 | return Changed ? LoopDeletionResult::Modified | |||
478 | : LoopDeletionResult::Unmodified; | |||
479 | } | |||
480 | ||||
481 | LLVM_DEBUG(dbgs() << "Loop is invariant, delete it!")do { } while (false); | |||
482 | ORE.emit([&]() { | |||
483 | return OptimizationRemark(DEBUG_TYPE"loop-delete", "Invariant", L->getStartLoc(), | |||
484 | L->getHeader()) | |||
485 | << "Loop deleted because it is invariant"; | |||
486 | }); | |||
487 | deleteDeadLoop(L, &DT, &SE, &LI, MSSA); | |||
488 | ++NumDeleted; | |||
489 | ||||
490 | return LoopDeletionResult::Deleted; | |||
491 | } | |||
492 | ||||
493 | PreservedAnalyses LoopDeletionPass::run(Loop &L, LoopAnalysisManager &AM, | |||
494 | LoopStandardAnalysisResults &AR, | |||
495 | LPMUpdater &Updater) { | |||
496 | ||||
497 | LLVM_DEBUG(dbgs() << "Analyzing Loop for deletion: ")do { } while (false); | |||
| ||||
498 | LLVM_DEBUG(L.dump())do { } while (false); | |||
499 | std::string LoopName = std::string(L.getName()); | |||
500 | // For the new PM, we can't use OptimizationRemarkEmitter as an analysis | |||
501 | // pass. Function analyses need to be preserved across loop transformations | |||
502 | // but ORE cannot be preserved (see comment before the pass definition). | |||
503 | OptimizationRemarkEmitter ORE(L.getHeader()->getParent()); | |||
504 | auto Result = deleteLoopIfDead(&L, AR.DT, AR.SE, AR.LI, AR.MSSA, ORE); | |||
505 | ||||
506 | // If we can prove the backedge isn't taken, just break it and be done. This | |||
507 | // leaves the loop structure in place which means it can handle dispatching | |||
508 | // to the right exit based on whatever loop invariant structure remains. | |||
509 | if (Result != LoopDeletionResult::Deleted) | |||
510 | Result = merge(Result, breakBackedgeIfNotTaken(&L, AR.DT, AR.SE, AR.LI, | |||
511 | AR.MSSA, ORE)); | |||
512 | ||||
513 | if (Result == LoopDeletionResult::Unmodified) | |||
514 | return PreservedAnalyses::all(); | |||
515 | ||||
516 | if (Result == LoopDeletionResult::Deleted) | |||
517 | Updater.markLoopAsDeleted(L, LoopName); | |||
518 | ||||
519 | auto PA = getLoopPassPreservedAnalyses(); | |||
520 | if (AR.MSSA) | |||
521 | PA.preserve<MemorySSAAnalysis>(); | |||
522 | return PA; | |||
523 | } | |||
524 | ||||
525 | namespace { | |||
526 | class LoopDeletionLegacyPass : public LoopPass { | |||
527 | public: | |||
528 | static char ID; // Pass ID, replacement for typeid | |||
529 | LoopDeletionLegacyPass() : LoopPass(ID) { | |||
530 | initializeLoopDeletionLegacyPassPass(*PassRegistry::getPassRegistry()); | |||
531 | } | |||
532 | ||||
533 | // Possibly eliminate loop L if it is dead. | |||
534 | bool runOnLoop(Loop *L, LPPassManager &) override; | |||
535 | ||||
536 | void getAnalysisUsage(AnalysisUsage &AU) const override { | |||
537 | AU.addPreserved<MemorySSAWrapperPass>(); | |||
538 | getLoopAnalysisUsage(AU); | |||
539 | } | |||
540 | }; | |||
541 | } | |||
542 | ||||
543 | char LoopDeletionLegacyPass::ID = 0; | |||
544 | INITIALIZE_PASS_BEGIN(LoopDeletionLegacyPass, "loop-deletion",static void *initializeLoopDeletionLegacyPassPassOnce(PassRegistry &Registry) { | |||
545 | "Delete dead loops", false, false)static void *initializeLoopDeletionLegacyPassPassOnce(PassRegistry &Registry) { | |||
546 | INITIALIZE_PASS_DEPENDENCY(LoopPass)initializeLoopPassPass(Registry); | |||
547 | INITIALIZE_PASS_END(LoopDeletionLegacyPass, "loop-deletion",PassInfo *PI = new PassInfo( "Delete dead loops", "loop-deletion" , &LoopDeletionLegacyPass::ID, PassInfo::NormalCtor_t(callDefaultCtor <LoopDeletionLegacyPass>), false, false); Registry.registerPass (*PI, true); return PI; } static llvm::once_flag InitializeLoopDeletionLegacyPassPassFlag ; void llvm::initializeLoopDeletionLegacyPassPass(PassRegistry &Registry) { llvm::call_once(InitializeLoopDeletionLegacyPassPassFlag , initializeLoopDeletionLegacyPassPassOnce, std::ref(Registry )); } | |||
548 | "Delete dead loops", false, false)PassInfo *PI = new PassInfo( "Delete dead loops", "loop-deletion" , &LoopDeletionLegacyPass::ID, PassInfo::NormalCtor_t(callDefaultCtor <LoopDeletionLegacyPass>), false, false); Registry.registerPass (*PI, true); return PI; } static llvm::once_flag InitializeLoopDeletionLegacyPassPassFlag ; void llvm::initializeLoopDeletionLegacyPassPass(PassRegistry &Registry) { llvm::call_once(InitializeLoopDeletionLegacyPassPassFlag , initializeLoopDeletionLegacyPassPassOnce, std::ref(Registry )); } | |||
549 | ||||
550 | Pass *llvm::createLoopDeletionPass() { return new LoopDeletionLegacyPass(); } | |||
551 | ||||
552 | bool LoopDeletionLegacyPass::runOnLoop(Loop *L, LPPassManager &LPM) { | |||
553 | if (skipLoop(L)) | |||
554 | return false; | |||
555 | DominatorTree &DT = getAnalysis<DominatorTreeWrapperPass>().getDomTree(); | |||
556 | ScalarEvolution &SE = getAnalysis<ScalarEvolutionWrapperPass>().getSE(); | |||
557 | LoopInfo &LI = getAnalysis<LoopInfoWrapperPass>().getLoopInfo(); | |||
558 | auto *MSSAAnalysis = getAnalysisIfAvailable<MemorySSAWrapperPass>(); | |||
559 | MemorySSA *MSSA = nullptr; | |||
560 | if (MSSAAnalysis) | |||
561 | MSSA = &MSSAAnalysis->getMSSA(); | |||
562 | // For the old PM, we can't use OptimizationRemarkEmitter as an analysis | |||
563 | // pass. Function analyses need to be preserved across loop transformations | |||
564 | // but ORE cannot be preserved (see comment before the pass definition). | |||
565 | OptimizationRemarkEmitter ORE(L->getHeader()->getParent()); | |||
566 | ||||
567 | LLVM_DEBUG(dbgs() << "Analyzing Loop for deletion: ")do { } while (false); | |||
568 | LLVM_DEBUG(L->dump())do { } while (false); | |||
569 | ||||
570 | LoopDeletionResult Result = deleteLoopIfDead(L, DT, SE, LI, MSSA, ORE); | |||
571 | ||||
572 | // If we can prove the backedge isn't taken, just break it and be done. This | |||
573 | // leaves the loop structure in place which means it can handle dispatching | |||
574 | // to the right exit based on whatever loop invariant structure remains. | |||
575 | if (Result != LoopDeletionResult::Deleted) | |||
576 | Result = merge(Result, breakBackedgeIfNotTaken(L, DT, SE, LI, MSSA, ORE)); | |||
577 | ||||
578 | if (Result == LoopDeletionResult::Deleted) | |||
579 | LPM.markLoopAsDeleted(*L); | |||
580 | ||||
581 | return Result != LoopDeletionResult::Unmodified; | |||
582 | } |