File: | 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 { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("loop-delete")) { dbgs() << "Could not compute SCEV MaxBackedgeTakenCount and was " "not required to make progress.\n"; } } while (false) | |||
136 | 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) | |||
137 | "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); | |||
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!")(static_cast <bool> (Preheader && "Needs preheader!" ) ? void (0) : __assert_fail ("Preheader && \"Needs preheader!\"" , "/build/llvm-toolchain-snapshot-14~++20210828111110+16086d47c0d0/llvm/lib/Transforms/Scalar/LoopDeletion.cpp" , 154, __extension__ __PRETTY_FUNCTION__)); | |||
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) &&(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!\"" , "/build/llvm-toolchain-snapshot-14~++20210828111110+16086d47c0d0/llvm/lib/Transforms/Scalar/LoopDeletion.cpp" , 172, __extension__ __PRETTY_FUNCTION__)) | |||
172 | "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!\"" , "/build/llvm-toolchain-snapshot-14~++20210828111110+16086d47c0d0/llvm/lib/Transforms/Scalar/LoopDeletion.cpp" , 172, __extension__ __PRETTY_FUNCTION__)); | |||
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!")(static_cast <bool> (LiveBlocks.count(From) && "Must be live!" ) ? void (0) : __assert_fail ("LiveBlocks.count(From) && \"Must be live!\"" , "/build/llvm-toolchain-snapshot-14~++20210828111110+16086d47c0d0/llvm/lib/Transforms/Scalar/LoopDeletion.cpp" , 235, __extension__ __PRETTY_FUNCTION__)); | |||
236 | 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?\"" , "/build/llvm-toolchain-snapshot-14~++20210828111110+16086d47c0d0/llvm/lib/Transforms/Scalar/LoopDeletion.cpp" , 237, __extension__ __PRETTY_FUNCTION__)) | |||
237 | "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?\"" , "/build/llvm-toolchain-snapshot-14~++20210828111110+16086d47c0d0/llvm/lib/Transforms/Scalar/LoopDeletion.cpp" , 237, __extension__ __PRETTY_FUNCTION__)); | |||
238 | 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!\"" , "/build/llvm-toolchain-snapshot-14~++20210828111110+16086d47c0d0/llvm/lib/Transforms/Scalar/LoopDeletion.cpp" , 239, __extension__ __PRETTY_FUNCTION__)) | |||
239 | "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!\"" , "/build/llvm-toolchain-snapshot-14~++20210828111110+16086d47c0d0/llvm/lib/Transforms/Scalar/LoopDeletion.cpp" , 239, __extension__ __PRETTY_FUNCTION__)); | |||
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?")(static_cast <bool> (HasLivePreds && "No live predecessors?" ) ? void (0) : __assert_fail ("HasLivePreds && \"No live predecessors?\"" , "/build/llvm-toolchain-snapshot-14~++20210828111110+16086d47c0d0/llvm/lib/Transforms/Scalar/LoopDeletion.cpp" , 273, __extension__ __PRETTY_FUNCTION__)); | |||
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!")(static_cast <bool> (L->isLCSSAForm(DT) && "Expected LCSSA!" ) ? void (0) : __assert_fail ("L->isLCSSAForm(DT) && \"Expected LCSSA!\"" , "/build/llvm-toolchain-snapshot-14~++20210828111110+16086d47c0d0/llvm/lib/Transforms/Scalar/LoopDeletion.cpp" , 391, __extension__ __PRETTY_FUNCTION__)); | |||
392 | ||||
393 | if (!L->getLoopLatch()) | |||
394 | return LoopDeletionResult::Unmodified; | |||
395 | ||||
396 | auto *BTCMax = SE.getConstantMaxBackedgeTakenCount(L); | |||
397 | if (!BTCMax->isZero()) { | |||
398 | auto *BTC = SE.getBackedgeTakenCount(L); | |||
399 | if (!BTC->isZero()) { | |||
400 | if (!isa<SCEVCouldNotCompute>(BTC) && SE.isKnownNonZero(BTC)) | |||
401 | return LoopDeletionResult::Unmodified; | |||
402 | if (!canProveExitOnFirstIteration(L, DT, LI)) | |||
403 | return LoopDeletionResult::Unmodified; | |||
404 | } | |||
405 | } | |||
406 | ||||
407 | breakLoopBackedge(L, DT, SE, LI, MSSA); | |||
408 | return LoopDeletionResult::Deleted; | |||
409 | } | |||
410 | ||||
411 | /// Remove a loop if it is dead. | |||
412 | /// | |||
413 | /// A loop is considered dead either if it does not impact the observable | |||
414 | /// behavior of the program other than finite running time, or if it is | |||
415 | /// required to make progress by an attribute such as 'mustprogress' or | |||
416 | /// 'llvm.loop.mustprogress' and does not make any. This may remove | |||
417 | /// infinite loops that have been required to make progress. | |||
418 | /// | |||
419 | /// This entire process relies pretty heavily on LoopSimplify form and LCSSA in | |||
420 | /// order to make various safety checks work. | |||
421 | /// | |||
422 | /// \returns true if any changes were made. This may mutate the loop even if it | |||
423 | /// is unable to delete it due to hoisting trivially loop invariant | |||
424 | /// instructions out of the loop. | |||
425 | static LoopDeletionResult deleteLoopIfDead(Loop *L, DominatorTree &DT, | |||
426 | ScalarEvolution &SE, LoopInfo &LI, | |||
427 | MemorySSA *MSSA, | |||
428 | OptimizationRemarkEmitter &ORE) { | |||
429 | assert(L->isLCSSAForm(DT) && "Expected LCSSA!")(static_cast <bool> (L->isLCSSAForm(DT) && "Expected LCSSA!" ) ? void (0) : __assert_fail ("L->isLCSSAForm(DT) && \"Expected LCSSA!\"" , "/build/llvm-toolchain-snapshot-14~++20210828111110+16086d47c0d0/llvm/lib/Transforms/Scalar/LoopDeletion.cpp" , 429, __extension__ __PRETTY_FUNCTION__)); | |||
430 | ||||
431 | // We can only remove the loop if there is a preheader that we can branch from | |||
432 | // after removing it. Also, if LoopSimplify form is not available, stay out | |||
433 | // of trouble. | |||
434 | BasicBlock *Preheader = L->getLoopPreheader(); | |||
435 | if (!Preheader || !L->hasDedicatedExits()) { | |||
436 | LLVM_DEBUG(do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("loop-delete")) { dbgs() << "Deletion requires Loop with preheader and dedicated exits.\n" ; } } while (false) | |||
437 | dbgs()do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("loop-delete")) { dbgs() << "Deletion requires Loop with preheader and dedicated exits.\n" ; } } while (false) | |||
438 | << "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); | |||
439 | return LoopDeletionResult::Unmodified; | |||
440 | } | |||
441 | ||||
442 | BasicBlock *ExitBlock = L->getUniqueExitBlock(); | |||
443 | ||||
444 | if (ExitBlock && isLoopNeverExecuted(L)) { | |||
445 | 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); | |||
446 | // We need to forget the loop before setting the incoming values of the exit | |||
447 | // phis to undef, so we properly invalidate the SCEV expressions for those | |||
448 | // phis. | |||
449 | SE.forgetLoop(L); | |||
450 | // Set incoming value to undef for phi nodes in the exit block. | |||
451 | for (PHINode &P : ExitBlock->phis()) { | |||
452 | std::fill(P.incoming_values().begin(), P.incoming_values().end(), | |||
453 | UndefValue::get(P.getType())); | |||
454 | } | |||
455 | ORE.emit([&]() { | |||
456 | return OptimizationRemark(DEBUG_TYPE"loop-delete", "NeverExecutes", L->getStartLoc(), | |||
457 | L->getHeader()) | |||
458 | << "Loop deleted because it never executes"; | |||
459 | }); | |||
460 | deleteDeadLoop(L, &DT, &SE, &LI, MSSA); | |||
461 | ++NumDeleted; | |||
462 | return LoopDeletionResult::Deleted; | |||
463 | } | |||
464 | ||||
465 | // The remaining checks below are for a loop being dead because all statements | |||
466 | // in the loop are invariant. | |||
467 | SmallVector<BasicBlock *, 4> ExitingBlocks; | |||
468 | L->getExitingBlocks(ExitingBlocks); | |||
469 | ||||
470 | // We require that the loop has at most one exit block. Otherwise, we'd be in | |||
471 | // the situation of needing to be able to solve statically which exit block | |||
472 | // will be branched to, or trying to preserve the branching logic in a loop | |||
473 | // invariant manner. | |||
474 | if (!ExitBlock
| |||
475 | 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); | |||
476 | return LoopDeletionResult::Unmodified; | |||
477 | } | |||
478 | // Finally, we have to check that the loop really is dead. | |||
479 | bool Changed = false; | |||
480 | if (!isLoopDead(L, SE, ExitingBlocks, ExitBlock, Changed, Preheader, LI)) { | |||
481 | 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); | |||
482 | return Changed ? LoopDeletionResult::Modified | |||
483 | : LoopDeletionResult::Unmodified; | |||
484 | } | |||
485 | ||||
486 | LLVM_DEBUG(dbgs() << "Loop is invariant, delete it!")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("loop-delete")) { dbgs() << "Loop is invariant, delete it!" ; } } while (false); | |||
487 | ORE.emit([&]() { | |||
488 | return OptimizationRemark(DEBUG_TYPE"loop-delete", "Invariant", L->getStartLoc(), | |||
489 | L->getHeader()) | |||
490 | << "Loop deleted because it is invariant"; | |||
491 | }); | |||
492 | deleteDeadLoop(L, &DT, &SE, &LI, MSSA); | |||
493 | ++NumDeleted; | |||
494 | ||||
495 | return LoopDeletionResult::Deleted; | |||
496 | } | |||
497 | ||||
498 | PreservedAnalyses LoopDeletionPass::run(Loop &L, LoopAnalysisManager &AM, | |||
499 | LoopStandardAnalysisResults &AR, | |||
500 | LPMUpdater &Updater) { | |||
501 | ||||
502 | LLVM_DEBUG(dbgs() << "Analyzing Loop for deletion: ")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("loop-delete")) { dbgs() << "Analyzing Loop for deletion: " ; } } while (false); | |||
| ||||
503 | LLVM_DEBUG(L.dump())do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("loop-delete")) { L.dump(); } } while (false); | |||
504 | std::string LoopName = std::string(L.getName()); | |||
505 | // For the new PM, we can't use OptimizationRemarkEmitter as an analysis | |||
506 | // pass. Function analyses need to be preserved across loop transformations | |||
507 | // but ORE cannot be preserved (see comment before the pass definition). | |||
508 | OptimizationRemarkEmitter ORE(L.getHeader()->getParent()); | |||
509 | auto Result = deleteLoopIfDead(&L, AR.DT, AR.SE, AR.LI, AR.MSSA, ORE); | |||
510 | ||||
511 | // If we can prove the backedge isn't taken, just break it and be done. This | |||
512 | // leaves the loop structure in place which means it can handle dispatching | |||
513 | // to the right exit based on whatever loop invariant structure remains. | |||
514 | if (Result != LoopDeletionResult::Deleted) | |||
515 | Result = merge(Result, breakBackedgeIfNotTaken(&L, AR.DT, AR.SE, AR.LI, | |||
516 | AR.MSSA, ORE)); | |||
517 | ||||
518 | if (Result == LoopDeletionResult::Unmodified) | |||
519 | return PreservedAnalyses::all(); | |||
520 | ||||
521 | if (Result == LoopDeletionResult::Deleted) | |||
522 | Updater.markLoopAsDeleted(L, LoopName); | |||
523 | ||||
524 | auto PA = getLoopPassPreservedAnalyses(); | |||
525 | if (AR.MSSA) | |||
526 | PA.preserve<MemorySSAAnalysis>(); | |||
527 | return PA; | |||
528 | } | |||
529 | ||||
530 | namespace { | |||
531 | class LoopDeletionLegacyPass : public LoopPass { | |||
532 | public: | |||
533 | static char ID; // Pass ID, replacement for typeid | |||
534 | LoopDeletionLegacyPass() : LoopPass(ID) { | |||
535 | initializeLoopDeletionLegacyPassPass(*PassRegistry::getPassRegistry()); | |||
536 | } | |||
537 | ||||
538 | // Possibly eliminate loop L if it is dead. | |||
539 | bool runOnLoop(Loop *L, LPPassManager &) override; | |||
540 | ||||
541 | void getAnalysisUsage(AnalysisUsage &AU) const override { | |||
542 | AU.addPreserved<MemorySSAWrapperPass>(); | |||
543 | getLoopAnalysisUsage(AU); | |||
544 | } | |||
545 | }; | |||
546 | } | |||
547 | ||||
548 | char LoopDeletionLegacyPass::ID = 0; | |||
549 | INITIALIZE_PASS_BEGIN(LoopDeletionLegacyPass, "loop-deletion",static void *initializeLoopDeletionLegacyPassPassOnce(PassRegistry &Registry) { | |||
550 | "Delete dead loops", false, false)static void *initializeLoopDeletionLegacyPassPassOnce(PassRegistry &Registry) { | |||
551 | INITIALIZE_PASS_DEPENDENCY(LoopPass)initializeLoopPassPass(Registry); | |||
552 | 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 )); } | |||
553 | "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 )); } | |||
554 | ||||
555 | Pass *llvm::createLoopDeletionPass() { return new LoopDeletionLegacyPass(); } | |||
556 | ||||
557 | bool LoopDeletionLegacyPass::runOnLoop(Loop *L, LPPassManager &LPM) { | |||
558 | if (skipLoop(L)) | |||
559 | return false; | |||
560 | DominatorTree &DT = getAnalysis<DominatorTreeWrapperPass>().getDomTree(); | |||
561 | ScalarEvolution &SE = getAnalysis<ScalarEvolutionWrapperPass>().getSE(); | |||
562 | LoopInfo &LI = getAnalysis<LoopInfoWrapperPass>().getLoopInfo(); | |||
563 | auto *MSSAAnalysis = getAnalysisIfAvailable<MemorySSAWrapperPass>(); | |||
564 | MemorySSA *MSSA = nullptr; | |||
565 | if (MSSAAnalysis) | |||
566 | MSSA = &MSSAAnalysis->getMSSA(); | |||
567 | // For the old PM, we can't use OptimizationRemarkEmitter as an analysis | |||
568 | // pass. Function analyses need to be preserved across loop transformations | |||
569 | // but ORE cannot be preserved (see comment before the pass definition). | |||
570 | OptimizationRemarkEmitter ORE(L->getHeader()->getParent()); | |||
571 | ||||
572 | LLVM_DEBUG(dbgs() << "Analyzing Loop for deletion: ")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("loop-delete")) { dbgs() << "Analyzing Loop for deletion: " ; } } while (false); | |||
573 | LLVM_DEBUG(L->dump())do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("loop-delete")) { L->dump(); } } while (false); | |||
574 | ||||
575 | LoopDeletionResult Result = deleteLoopIfDead(L, DT, SE, LI, MSSA, ORE); | |||
576 | ||||
577 | // If we can prove the backedge isn't taken, just break it and be done. This | |||
578 | // leaves the loop structure in place which means it can handle dispatching | |||
579 | // to the right exit based on whatever loop invariant structure remains. | |||
580 | if (Result != LoopDeletionResult::Deleted) | |||
581 | Result = merge(Result, breakBackedgeIfNotTaken(L, DT, SE, LI, MSSA, ORE)); | |||
582 | ||||
583 | if (Result == LoopDeletionResult::Deleted) | |||
584 | LPM.markLoopAsDeleted(*L); | |||
585 | ||||
586 | return Result != LoopDeletionResult::Unmodified; | |||
587 | } |