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