Bug Summary

File:llvm/lib/Transforms/Scalar/LoopDeletion.cpp
Warning:line 77, 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 -clear-ast-before-backend -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 -ffp-contract=on -fno-rounding-math -mconstructor-aliases -funwind-tables=2 -target-cpu x86-64 -tune-cpu generic -debugger-tuning=gdb -ffunction-sections -fdata-sections -fcoverage-compilation-dir=/build/llvm-toolchain-snapshot-14~++20220126101029+f487a76430a0/build-llvm -resource-dir /usr/lib/llvm-14/lib/clang/14.0.0 -D _DEBUG -D _GNU_SOURCE -D __STDC_CONSTANT_MACROS -D __STDC_FORMAT_MACROS -D __STDC_LIMIT_MACROS -I lib/Transforms/Scalar -I /build/llvm-toolchain-snapshot-14~++20220126101029+f487a76430a0/llvm/lib/Transforms/Scalar -I include -I /build/llvm-toolchain-snapshot-14~++20220126101029+f487a76430a0/llvm/include -D _FORTIFY_SOURCE=2 -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-14/lib/clang/14.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 -fmacro-prefix-map=/build/llvm-toolchain-snapshot-14~++20220126101029+f487a76430a0/build-llvm=build-llvm -fmacro-prefix-map=/build/llvm-toolchain-snapshot-14~++20220126101029+f487a76430a0/= -fcoverage-prefix-map=/build/llvm-toolchain-snapshot-14~++20220126101029+f487a76430a0/build-llvm=build-llvm -fcoverage-prefix-map=/build/llvm-toolchain-snapshot-14~++20220126101029+f487a76430a0/= -O3 -Wno-unused-command-line-argument -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-14~++20220126101029+f487a76430a0/build-llvm -fdebug-prefix-map=/build/llvm-toolchain-snapshot-14~++20220126101029+f487a76430a0/build-llvm=build-llvm -fdebug-prefix-map=/build/llvm-toolchain-snapshot-14~++20220126101029+f487a76430a0/= -ferror-limit 19 -fvisibility-inlines-hidden -stack-protector 2 -fgnuc-version=4.2.1 -fcolor-diagnostics -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-2022-01-26-233846-219801-1 -x c++ /build/llvm-toolchain-snapshot-14~++20220126101029+f487a76430a0/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"}
;
39STATISTIC(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
42static 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
47enum class LoopDeletionResult {
48 Unmodified,
49 Modified,
50 Deleted,
51};
52
53static 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.
65static 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()) {
16
Assuming the condition is true
17
Taking true branch
77 for (PHINode &P : ExitBlock->phis()) {
18
Called C++ object pointer is null
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.
150static 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
179static Value *
180getValueOnFirstIteration(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.
219static 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.
401static LoopDeletionResult
402breakBackedgeIfNotTaken(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.
439static 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__))
;
5
Assuming the condition is true
6
'?' condition is true
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()) {
7
Assuming 'Preheader' is non-null
8
Assuming the condition is false
9
Taking false branch
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();
10
'ExitBlock' initialized here
457
458 if (ExitBlock && isLoopNeverExecuted(L)) {
11
Assuming 'ExitBlock' is null
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
11.1
'ExitBlock' is null
&& !L->hasNoExitBlocks()) {
12
Assuming the condition is false
13
Taking false branch
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)) {
14
Passing null pointer value via 4th parameter 'ExitBlock'
15
Calling 'isLoopDead'
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
512PreservedAnalyses 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)
;
1
Assuming 'DebugFlag' is false
517 LLVM_DEBUG(L.dump())do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("loop-delete")) { L.dump(); } } while (false)
;
2
Loop condition is false. Exiting loop
3
Loop condition is false. Exiting loop
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);
4
Calling 'deleteLoopIfDead'
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
544namespace {
545class LoopDeletionLegacyPass : public LoopPass {
546public:
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
562char LoopDeletionLegacyPass::ID = 0;
563INITIALIZE_PASS_BEGIN(LoopDeletionLegacyPass, "loop-deletion",static void *initializeLoopDeletionLegacyPassPassOnce(PassRegistry
&Registry) {
564 "Delete dead loops", false, false)static void *initializeLoopDeletionLegacyPassPassOnce(PassRegistry
&Registry) {
565INITIALIZE_PASS_DEPENDENCY(LoopPass)initializeLoopPassPass(Registry);
566INITIALIZE_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
569Pass *llvm::createLoopDeletionPass() { return new LoopDeletionLegacyPass(); }
570
571bool 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}