Bug Summary

File:llvm/lib/Transforms/Scalar/LoopDeletion.cpp
Warning:line 75, column 23
Called C++ object pointer is null

Annotated Source Code

Press '?' to see keyboard shortcuts

clang -cc1 -cc1 -triple x86_64-pc-linux-gnu -analyze -disable-free -disable-llvm-verifier -discard-value-names -main-file-name LoopDeletion.cpp -analyzer-store=region -analyzer-opt-analyze-nested-blocks -analyzer-checker=core -analyzer-checker=apiModeling -analyzer-checker=unix -analyzer-checker=deadcode -analyzer-checker=cplusplus -analyzer-checker=security.insecureAPI.UncheckedReturn -analyzer-checker=security.insecureAPI.getpw -analyzer-checker=security.insecureAPI.gets -analyzer-checker=security.insecureAPI.mktemp -analyzer-checker=security.insecureAPI.mkstemp -analyzer-checker=security.insecureAPI.vfork -analyzer-checker=nullability.NullPassedToNonnull -analyzer-checker=nullability.NullReturnedFromNonnull -analyzer-output plist -w -setup-static-analyzer -analyzer-config-compatibility-mode=true -mrelocation-model pic -pic-level 2 -mframe-pointer=none -fmath-errno -fno-rounding-math -mconstructor-aliases -munwind-tables -target-cpu x86-64 -tune-cpu generic -debugger-tuning=gdb -ffunction-sections -fdata-sections -fcoverage-compilation-dir=/build/llvm-toolchain-snapshot-13~++20210726100616+dead50d4427c/build-llvm/lib/Transforms/Scalar -resource-dir /usr/lib/llvm-13/lib/clang/13.0.0 -D _DEBUG -D _GNU_SOURCE -D __STDC_CONSTANT_MACROS -D __STDC_FORMAT_MACROS -D __STDC_LIMIT_MACROS -I /build/llvm-toolchain-snapshot-13~++20210726100616+dead50d4427c/build-llvm/lib/Transforms/Scalar -I /build/llvm-toolchain-snapshot-13~++20210726100616+dead50d4427c/llvm/lib/Transforms/Scalar -I /build/llvm-toolchain-snapshot-13~++20210726100616+dead50d4427c/build-llvm/include -I /build/llvm-toolchain-snapshot-13~++20210726100616+dead50d4427c/llvm/include -D NDEBUG -U NDEBUG -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/10/../../../../include/c++/10 -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/10/../../../../include/x86_64-linux-gnu/c++/10 -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/10/../../../../include/c++/10/backward -internal-isystem /usr/lib/llvm-13/lib/clang/13.0.0/include -internal-isystem /usr/local/include -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/10/../../../../x86_64-linux-gnu/include -internal-externc-isystem /usr/include/x86_64-linux-gnu -internal-externc-isystem /include -internal-externc-isystem /usr/include -O2 -Wno-unused-parameter -Wwrite-strings -Wno-missing-field-initializers -Wno-long-long -Wno-maybe-uninitialized -Wno-class-memaccess -Wno-redundant-move -Wno-pessimizing-move -Wno-noexcept-type -Wno-comment -std=c++14 -fdeprecated-macro -fdebug-compilation-dir=/build/llvm-toolchain-snapshot-13~++20210726100616+dead50d4427c/build-llvm/lib/Transforms/Scalar -fdebug-prefix-map=/build/llvm-toolchain-snapshot-13~++20210726100616+dead50d4427c=. -ferror-limit 19 -fvisibility-inlines-hidden -stack-protector 2 -fgnuc-version=4.2.1 -vectorize-loops -vectorize-slp -analyzer-output=html -analyzer-config stable-report-filename=true -faddrsig -D__GCC_HAVE_DWARF2_CFI_ASM=1 -o /tmp/scan-build-2021-07-26-235520-9401-1 -x c++ /build/llvm-toolchain-snapshot-13~++20210726100616+dead50d4427c/llvm/lib/Transforms/Scalar/LoopDeletion.cpp
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
34using namespace llvm;
35
36#define DEBUG_TYPE"loop-delete" "loop-delete"
37
38STATISTIC(NumDeleted, "Number of loops deleted")static llvm::Statistic NumDeleted = {"loop-delete", "NumDeleted"
, "Number of loops deleted"};
39
40static 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
45enum class LoopDeletionResult {
46 Unmodified,
47 Modified,
48 Deleted,
49};
50
51static 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.
63static 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()) {
16
←
Assuming the condition is true
→
17
←
Taking true branch
→
75 for (PHINode &P : ExitBlock->phis()) {
18
←
Called C++ object pointer is null
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.
148static 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-13~++20210726100616+dead50d4427c/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-13~++20210726100616+dead50d4427c/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-13~++20210726100616+dead50d4427c/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
177static Value *
178getValueOnFirstIteration(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.
203static 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-13~++20210726100616+dead50d4427c/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-13~++20210726100616+dead50d4427c/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-13~++20210726100616+dead50d4427c/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-13~++20210726100616+dead50d4427c/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-13~++20210726100616+dead50d4427c/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-13~++20210726100616+dead50d4427c/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.
387static LoopDeletionResult
388breakBackedgeIfNotTaken(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-13~++20210726100616+dead50d4427c/llvm/lib/Transforms/Scalar/LoopDeletion.cpp"
, 391, __extension__ __PRETTY_FUNCTION__));
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.
420static LoopDeletionResult deleteLoopIfDead(Loop *L, DominatorTree &DT,
421 ScalarEvolution &SE, LoopInfo &LI,
422 MemorySSA *MSSA,
423 OptimizationRemarkEmitter &ORE) {
424 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-13~++20210726100616+dead50d4427c/llvm/lib/Transforms/Scalar/LoopDeletion.cpp"
, 424, __extension__ __PRETTY_FUNCTION__));
5
←
Assuming the condition is true
→
6
←
'?' condition is true
→
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()) {
7
←
Assuming 'Preheader' is non-null
→
8
←
Assuming the condition is false
→
9
←
Taking false branch
→
431 LLVM_DEBUG(do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("loop-delete")) { dbgs() << "Deletion requires Loop with preheader and dedicated exits.\n"
; } } while (false)
432 dbgs()do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("loop-delete")) { dbgs() << "Deletion requires Loop with preheader and dedicated exits.\n"
; } } while (false)
433 << "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);
434 return LoopDeletionResult::Unmodified;
435 }
436
437 BasicBlock *ExitBlock = L->getUniqueExitBlock();
10
←
'ExitBlock' initialized here
→
438
439 if (ExitBlock && isLoopNeverExecuted(L)) {
11
←
Assuming 'ExitBlock' is null
→
440 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);
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
11.1
'ExitBlock' is null
 && !L->hasNoExitBlocks()) {
12
←
Assuming the condition is false
→
13
←
Taking false branch
→
470 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);
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)) {
14
←
Passing null pointer value via 4th parameter 'ExitBlock'
→
15
←
Calling 'isLoopDead'
→
476 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);
477 return Changed ? LoopDeletionResult::Modified
478 : LoopDeletionResult::Unmodified;
479 }
480
481 LLVM_DEBUG(dbgs() << "Loop is invariant, delete it!")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("loop-delete")) { dbgs() << "Loop is invariant, delete it!"
; } } 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
493PreservedAnalyses LoopDeletionPass::run(Loop &L, LoopAnalysisManager &AM,
494 LoopStandardAnalysisResults &AR,
495 LPMUpdater &Updater) {
496
497 LLVM_DEBUG(dbgs() << "Analyzing Loop for deletion: ")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("loop-delete")) { dbgs() << "Analyzing Loop for deletion: "
; } } while (false);
1
Assuming 'DebugFlag' is false
→
2
←
Loop condition is false. Exiting loop
→
498 LLVM_DEBUG(L.dump())do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("loop-delete")) { L.dump(); } } while (false);
3
←
Loop condition is false. Exiting loop
→
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);
4
←
Calling 'deleteLoopIfDead'
→
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
525namespace {
526class LoopDeletionLegacyPass : public LoopPass {
527public:
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
543char LoopDeletionLegacyPass::ID = 0;
544INITIALIZE_PASS_BEGIN(LoopDeletionLegacyPass, "loop-deletion",static void *initializeLoopDeletionLegacyPassPassOnce(PassRegistry
&Registry) {
545 "Delete dead loops", false, false)static void *initializeLoopDeletionLegacyPassPassOnce(PassRegistry
&Registry) {
546INITIALIZE_PASS_DEPENDENCY(LoopPass)initializeLoopPassPass(Registry);
547INITIALIZE_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
550Pass *llvm::createLoopDeletionPass() { return new LoopDeletionLegacyPass(); }
551
552bool 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 { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("loop-delete")) { dbgs() << "Analyzing Loop for deletion: "
; } } while (false);
568 LLVM_DEBUG(L->dump())do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("loop-delete")) { L->dump(); } } 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}