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-14~++20210926122410+d23fd8ae8906/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~++20210926122410+d23fd8ae8906/llvm/lib/Transforms/Scalar -I include -I /build/llvm-toolchain-snapshot-14~++20210926122410+d23fd8ae8906/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-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 -O2 -Wno-unused-command-line-argument -Wno-unknown-warning-option -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~++20210926122410+d23fd8ae8906/build-llvm -ferror-limit 19 -fvisibility-inlines-hidden -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-2021-09-26-234817-15343-1 -x c++ /build/llvm-toolchain-snapshot-14~++20210926122410+d23fd8ae8906/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-14~++20210926122410+d23fd8ae8906/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~++20210926122410+d23fd8ae8906/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~++20210926122410+d23fd8ae8906/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 } else if (auto *Cmp = dyn_cast<ICmpInst>(V)) {
195 Value *LHS =
196 getValueOnFirstIteration(Cmp->getOperand(0), FirstIterValue, SQ);
197 Value *RHS =
198 getValueOnFirstIteration(Cmp->getOperand(1), FirstIterValue, SQ);
199 FirstIterV = SimplifyICmpInst(Cmp->getPredicate(), LHS, RHS, SQ);
200 }
201 if (!FirstIterV)
202 FirstIterV = V;
203 FirstIterValue[V] = FirstIterV;
204 return FirstIterV;
205}
206
207// Try to prove that one of conditions that dominates the latch must exit on 1st
208// iteration.
209static bool canProveExitOnFirstIteration(Loop *L, DominatorTree &DT,
210 LoopInfo &LI) {
211 // Disabled by option.
212 if (!EnableSymbolicExecution)
213 return false;
214
215 BasicBlock *Predecessor = L->getLoopPredecessor();
216 BasicBlock *Latch = L->getLoopLatch();
217
218 if (!Predecessor || !Latch)
219 return false;
220
221 LoopBlocksRPO RPOT(L);
222 RPOT.perform(&LI);
223
224 // For the optimization to be correct, we need RPOT to have a property that
225 // each block is processed after all its predecessors, which may only be
226 // violated for headers of the current loop and all nested loops. Irreducible
227 // CFG provides multiple ways to break this assumption, so we do not want to
228 // deal with it.
229 if (containsIrreducibleCFG<const BasicBlock *>(RPOT, LI))
230 return false;
231
232 BasicBlock *Header = L->getHeader();
233 // Blocks that are reachable on the 1st iteration.
234 SmallPtrSet<BasicBlock *, 4> LiveBlocks;
235 // Edges that are reachable on the 1st iteration.
236 DenseSet<BasicBlockEdge> LiveEdges;
237 LiveBlocks.insert(Header);
238
239 SmallPtrSet<BasicBlock *, 4> Visited;
240 auto MarkLiveEdge = [&](BasicBlock *From, BasicBlock *To) {
241 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~++20210926122410+d23fd8ae8906/llvm/lib/Transforms/Scalar/LoopDeletion.cpp"
, 241, __extension__ __PRETTY_FUNCTION__))
;
242 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~++20210926122410+d23fd8ae8906/llvm/lib/Transforms/Scalar/LoopDeletion.cpp"
, 243, __extension__ __PRETTY_FUNCTION__))
243 "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~++20210926122410+d23fd8ae8906/llvm/lib/Transforms/Scalar/LoopDeletion.cpp"
, 243, __extension__ __PRETTY_FUNCTION__))
;
244 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~++20210926122410+d23fd8ae8906/llvm/lib/Transforms/Scalar/LoopDeletion.cpp"
, 245, __extension__ __PRETTY_FUNCTION__))
245 "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~++20210926122410+d23fd8ae8906/llvm/lib/Transforms/Scalar/LoopDeletion.cpp"
, 245, __extension__ __PRETTY_FUNCTION__))
;
246 LiveBlocks.insert(To);
247 LiveEdges.insert({ From, To });
248 };
249
250 auto MarkAllSuccessorsLive = [&](BasicBlock *BB) {
251 for (auto *Succ : successors(BB))
252 MarkLiveEdge(BB, Succ);
253 };
254
255 // Check if there is only one value coming from all live predecessor blocks.
256 // Note that because we iterate in RPOT, we have already visited all its
257 // (non-latch) predecessors.
258 auto GetSoleInputOnFirstIteration = [&](PHINode & PN)->Value * {
259 BasicBlock *BB = PN.getParent();
260 bool HasLivePreds = false;
261 (void)HasLivePreds;
262 if (BB == Header)
263 return PN.getIncomingValueForBlock(Predecessor);
264 Value *OnlyInput = nullptr;
265 for (auto *Pred : predecessors(BB))
266 if (LiveEdges.count({ Pred, BB })) {
267 HasLivePreds = true;
268 Value *Incoming = PN.getIncomingValueForBlock(Pred);
269 // Skip undefs. If they are present, we can assume they are equal to
270 // the non-undef input.
271 if (isa<UndefValue>(Incoming))
272 continue;
273 // Two inputs.
274 if (OnlyInput && OnlyInput != Incoming)
275 return nullptr;
276 OnlyInput = Incoming;
277 }
278
279 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~++20210926122410+d23fd8ae8906/llvm/lib/Transforms/Scalar/LoopDeletion.cpp"
, 279, __extension__ __PRETTY_FUNCTION__))
;
280 // If all incoming live value were undefs, return undef.
281 return OnlyInput ? OnlyInput : UndefValue::get(PN.getType());
282 };
283 DenseMap<Value *, Value *> FirstIterValue;
284
285 // Use the following algorithm to prove we never take the latch on the 1st
286 // iteration:
287 // 1. Traverse in topological order, so that whenever we visit a block, all
288 // its predecessors are already visited.
289 // 2. If we can prove that the block may have only 1 predecessor on the 1st
290 // iteration, map all its phis onto input from this predecessor.
291 // 3a. If we can prove which successor of out block is taken on the 1st
292 // iteration, mark this successor live.
293 // 3b. If we cannot prove it, conservatively assume that all successors are
294 // live.
295 auto &DL = Header->getModule()->getDataLayout();
296 const SimplifyQuery SQ(DL);
297 for (auto *BB : RPOT) {
298 Visited.insert(BB);
299
300 // This block is not reachable on the 1st iterations.
301 if (!LiveBlocks.count(BB))
302 continue;
303
304 // Skip inner loops.
305 if (LI.getLoopFor(BB) != L) {
306 MarkAllSuccessorsLive(BB);
307 continue;
308 }
309
310 // If Phi has only one input from all live input blocks, use it.
311 for (auto &PN : BB->phis()) {
312 if (!PN.getType()->isIntegerTy())
313 continue;
314 auto *Incoming = GetSoleInputOnFirstIteration(PN);
315 if (Incoming && DT.dominates(Incoming, BB->getTerminator())) {
316 Value *FirstIterV =
317 getValueOnFirstIteration(Incoming, FirstIterValue, SQ);
318 FirstIterValue[&PN] = FirstIterV;
319 }
320 }
321
322 using namespace PatternMatch;
323 Value *Cond;
324 BasicBlock *IfTrue, *IfFalse;
325 auto *Term = BB->getTerminator();
326 if (match(Term, m_Br(m_Value(Cond),
327 m_BasicBlock(IfTrue), m_BasicBlock(IfFalse)))) {
328 auto *ICmp = dyn_cast<ICmpInst>(Cond);
329 if (!ICmp || !ICmp->getType()->isIntegerTy()) {
330 MarkAllSuccessorsLive(BB);
331 continue;
332 }
333
334 // Can we prove constant true or false for this condition?
335 auto *KnownCondition = getValueOnFirstIteration(ICmp, FirstIterValue, SQ);
336 if (KnownCondition == ICmp) {
337 // Failed to simplify.
338 MarkAllSuccessorsLive(BB);
339 continue;
340 }
341 if (isa<UndefValue>(KnownCondition)) {
342 // TODO: According to langref, branching by undef is undefined behavior.
343 // It means that, theoretically, we should be able to just continue
344 // without marking any successors as live. However, we are not certain
345 // how correct our compiler is at handling such cases. So we are being
346 // very conservative here.
347 //
348 // If there is a non-loop successor, always assume this branch leaves the
349 // loop. Otherwise, arbitrarily take IfTrue.
350 //
351 // Once we are certain that branching by undef is handled correctly by
352 // other transforms, we should not mark any successors live here.
353 if (L->contains(IfTrue) && L->contains(IfFalse))
354 MarkLiveEdge(BB, IfTrue);
355 continue;
356 }
357 auto *ConstCondition = dyn_cast<ConstantInt>(KnownCondition);
358 if (!ConstCondition) {
359 // Non-constant condition, cannot analyze any further.
360 MarkAllSuccessorsLive(BB);
361 continue;
362 }
363 if (ConstCondition->isAllOnesValue())
364 MarkLiveEdge(BB, IfTrue);
365 else
366 MarkLiveEdge(BB, IfFalse);
367 } else if (SwitchInst *SI = dyn_cast<SwitchInst>(Term)) {
368 auto *SwitchValue = SI->getCondition();
369 auto *SwitchValueOnFirstIter =
370 getValueOnFirstIteration(SwitchValue, FirstIterValue, SQ);
371 auto *ConstSwitchValue = dyn_cast<ConstantInt>(SwitchValueOnFirstIter);
372 if (!ConstSwitchValue) {
373 MarkAllSuccessorsLive(BB);
374 continue;
375 }
376 auto CaseIterator = SI->findCaseValue(ConstSwitchValue);
377 MarkLiveEdge(BB, CaseIterator->getCaseSuccessor());
378 } else {
379 MarkAllSuccessorsLive(BB);
380 continue;
381 }
382 }
383
384 // We can break the latch if it wasn't live.
385 return !LiveEdges.count({ Latch, Header });
386}
387
388/// If we can prove the backedge is untaken, remove it. This destroys the
389/// loop, but leaves the (now trivially loop invariant) control flow and
390/// side effects (if any) in place.
391static LoopDeletionResult
392breakBackedgeIfNotTaken(Loop *L, DominatorTree &DT, ScalarEvolution &SE,
393 LoopInfo &LI, MemorySSA *MSSA,
394 OptimizationRemarkEmitter &ORE) {
395 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~++20210926122410+d23fd8ae8906/llvm/lib/Transforms/Scalar/LoopDeletion.cpp"
, 395, __extension__ __PRETTY_FUNCTION__))
;
396
397 if (!L->getLoopLatch())
398 return LoopDeletionResult::Unmodified;
399
400 auto *BTC = SE.getSymbolicMaxBackedgeTakenCount(L);
401 if (BTC->isZero()) {
402 // SCEV knows this backedge isn't taken!
403 breakLoopBackedge(L, DT, SE, LI, MSSA);
404 return LoopDeletionResult::Deleted;
405 }
406
407 // If SCEV leaves open the possibility of a zero trip count, see if
408 // symbolically evaluating the first iteration lets us prove the backedge
409 // unreachable.
410 if (isa<SCEVCouldNotCompute>(BTC) || !SE.isKnownNonZero(BTC))
411 if (canProveExitOnFirstIteration(L, DT, LI)) {
412 breakLoopBackedge(L, DT, SE, LI, MSSA);
413 return LoopDeletionResult::Deleted;
414 }
415
416 return LoopDeletionResult::Unmodified;
417}
418
419/// Remove a loop if it is dead.
420///
421/// A loop is considered dead either if it does not impact the observable
422/// behavior of the program other than finite running time, or if it is
423/// required to make progress by an attribute such as 'mustprogress' or
424/// 'llvm.loop.mustprogress' and does not make any. This may remove
425/// infinite loops that have been required to make progress.
426///
427/// This entire process relies pretty heavily on LoopSimplify form and LCSSA in
428/// order to make various safety checks work.
429///
430/// \returns true if any changes were made. This may mutate the loop even if it
431/// is unable to delete it due to hoisting trivially loop invariant
432/// instructions out of the loop.
433static LoopDeletionResult deleteLoopIfDead(Loop *L, DominatorTree &DT,
434 ScalarEvolution &SE, LoopInfo &LI,
435 MemorySSA *MSSA,
436 OptimizationRemarkEmitter &ORE) {
437 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~++20210926122410+d23fd8ae8906/llvm/lib/Transforms/Scalar/LoopDeletion.cpp"
, 437, __extension__ __PRETTY_FUNCTION__))
;
5
Assuming the condition is true
6
'?' condition is true
438
439 // We can only remove the loop if there is a preheader that we can branch from
440 // after removing it. Also, if LoopSimplify form is not available, stay out
441 // of trouble.
442 BasicBlock *Preheader = L->getLoopPreheader();
443 if (!Preheader || !L->hasDedicatedExits()) {
7
Assuming 'Preheader' is non-null
8
Assuming the condition is false
9
Taking false branch
444 LLVM_DEBUG(do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("loop-delete")) { dbgs() << "Deletion requires Loop with preheader and dedicated exits.\n"
; } } while (false)
445 dbgs()do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("loop-delete")) { dbgs() << "Deletion requires Loop with preheader and dedicated exits.\n"
; } } while (false)
446 << "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)
;
447 return LoopDeletionResult::Unmodified;
448 }
449
450 BasicBlock *ExitBlock = L->getUniqueExitBlock();
10
'ExitBlock' initialized here
451
452 if (ExitBlock && isLoopNeverExecuted(L)) {
11
Assuming 'ExitBlock' is null
453 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)
;
454 // We need to forget the loop before setting the incoming values of the exit
455 // phis to undef, so we properly invalidate the SCEV expressions for those
456 // phis.
457 SE.forgetLoop(L);
458 // Set incoming value to undef for phi nodes in the exit block.
459 for (PHINode &P : ExitBlock->phis()) {
460 std::fill(P.incoming_values().begin(), P.incoming_values().end(),
461 UndefValue::get(P.getType()));
462 }
463 ORE.emit([&]() {
464 return OptimizationRemark(DEBUG_TYPE"loop-delete", "NeverExecutes", L->getStartLoc(),
465 L->getHeader())
466 << "Loop deleted because it never executes";
467 });
468 deleteDeadLoop(L, &DT, &SE, &LI, MSSA);
469 ++NumDeleted;
470 return LoopDeletionResult::Deleted;
471 }
472
473 // The remaining checks below are for a loop being dead because all statements
474 // in the loop are invariant.
475 SmallVector<BasicBlock *, 4> ExitingBlocks;
476 L->getExitingBlocks(ExitingBlocks);
477
478 // We require that the loop has at most one exit block. Otherwise, we'd be in
479 // the situation of needing to be able to solve statically which exit block
480 // will be branched to, or trying to preserve the branching logic in a loop
481 // invariant manner.
482 if (!ExitBlock
11.1
'ExitBlock' is null
&& !L->hasNoExitBlocks()) {
12
Assuming the condition is false
13
Taking false branch
483 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)
;
484 return LoopDeletionResult::Unmodified;
485 }
486 // Finally, we have to check that the loop really is dead.
487 bool Changed = false;
488 if (!isLoopDead(L, SE, ExitingBlocks, ExitBlock, Changed, Preheader, LI)) {
14
Passing null pointer value via 4th parameter 'ExitBlock'
15
Calling 'isLoopDead'
489 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)
;
490 return Changed ? LoopDeletionResult::Modified
491 : LoopDeletionResult::Unmodified;
492 }
493
494 LLVM_DEBUG(dbgs() << "Loop is invariant, delete it!")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("loop-delete")) { dbgs() << "Loop is invariant, delete it!"
; } } while (false)
;
495 ORE.emit([&]() {
496 return OptimizationRemark(DEBUG_TYPE"loop-delete", "Invariant", L->getStartLoc(),
497 L->getHeader())
498 << "Loop deleted because it is invariant";
499 });
500 deleteDeadLoop(L, &DT, &SE, &LI, MSSA);
501 ++NumDeleted;
502
503 return LoopDeletionResult::Deleted;
504}
505
506PreservedAnalyses LoopDeletionPass::run(Loop &L, LoopAnalysisManager &AM,
507 LoopStandardAnalysisResults &AR,
508 LPMUpdater &Updater) {
509
510 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
511 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
512 std::string LoopName = std::string(L.getName());
513 // For the new PM, we can't use OptimizationRemarkEmitter as an analysis
514 // pass. Function analyses need to be preserved across loop transformations
515 // but ORE cannot be preserved (see comment before the pass definition).
516 OptimizationRemarkEmitter ORE(L.getHeader()->getParent());
517 auto Result = deleteLoopIfDead(&L, AR.DT, AR.SE, AR.LI, AR.MSSA, ORE);
4
Calling 'deleteLoopIfDead'
518
519 // If we can prove the backedge isn't taken, just break it and be done. This
520 // leaves the loop structure in place which means it can handle dispatching
521 // to the right exit based on whatever loop invariant structure remains.
522 if (Result != LoopDeletionResult::Deleted)
523 Result = merge(Result, breakBackedgeIfNotTaken(&L, AR.DT, AR.SE, AR.LI,
524 AR.MSSA, ORE));
525
526 if (Result == LoopDeletionResult::Unmodified)
527 return PreservedAnalyses::all();
528
529 if (Result == LoopDeletionResult::Deleted)
530 Updater.markLoopAsDeleted(L, LoopName);
531
532 auto PA = getLoopPassPreservedAnalyses();
533 if (AR.MSSA)
534 PA.preserve<MemorySSAAnalysis>();
535 return PA;
536}
537
538namespace {
539class LoopDeletionLegacyPass : public LoopPass {
540public:
541 static char ID; // Pass ID, replacement for typeid
542 LoopDeletionLegacyPass() : LoopPass(ID) {
543 initializeLoopDeletionLegacyPassPass(*PassRegistry::getPassRegistry());
544 }
545
546 // Possibly eliminate loop L if it is dead.
547 bool runOnLoop(Loop *L, LPPassManager &) override;
548
549 void getAnalysisUsage(AnalysisUsage &AU) const override {
550 AU.addPreserved<MemorySSAWrapperPass>();
551 getLoopAnalysisUsage(AU);
552 }
553};
554}
555
556char LoopDeletionLegacyPass::ID = 0;
557INITIALIZE_PASS_BEGIN(LoopDeletionLegacyPass, "loop-deletion",static void *initializeLoopDeletionLegacyPassPassOnce(PassRegistry
&Registry) {
558 "Delete dead loops", false, false)static void *initializeLoopDeletionLegacyPassPassOnce(PassRegistry
&Registry) {
559INITIALIZE_PASS_DEPENDENCY(LoopPass)initializeLoopPassPass(Registry);
560INITIALIZE_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
)); }
561 "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
)); }
562
563Pass *llvm::createLoopDeletionPass() { return new LoopDeletionLegacyPass(); }
564
565bool LoopDeletionLegacyPass::runOnLoop(Loop *L, LPPassManager &LPM) {
566 if (skipLoop(L))
567 return false;
568 DominatorTree &DT = getAnalysis<DominatorTreeWrapperPass>().getDomTree();
569 ScalarEvolution &SE = getAnalysis<ScalarEvolutionWrapperPass>().getSE();
570 LoopInfo &LI = getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
571 auto *MSSAAnalysis = getAnalysisIfAvailable<MemorySSAWrapperPass>();
572 MemorySSA *MSSA = nullptr;
573 if (MSSAAnalysis)
574 MSSA = &MSSAAnalysis->getMSSA();
575 // For the old PM, we can't use OptimizationRemarkEmitter as an analysis
576 // pass. Function analyses need to be preserved across loop transformations
577 // but ORE cannot be preserved (see comment before the pass definition).
578 OptimizationRemarkEmitter ORE(L->getHeader()->getParent());
579
580 LLVM_DEBUG(dbgs() << "Analyzing Loop for deletion: ")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("loop-delete")) { dbgs() << "Analyzing Loop for deletion: "
; } } while (false)
;
581 LLVM_DEBUG(L->dump())do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("loop-delete")) { L->dump(); } } while (false)
;
582
583 LoopDeletionResult Result = deleteLoopIfDead(L, DT, SE, LI, MSSA, ORE);
584
585 // If we can prove the backedge isn't taken, just break it and be done. This
586 // leaves the loop structure in place which means it can handle dispatching
587 // to the right exit based on whatever loop invariant structure remains.
588 if (Result != LoopDeletionResult::Deleted)
589 Result = merge(Result, breakBackedgeIfNotTaken(L, DT, SE, LI, MSSA, ORE));
590
591 if (Result == LoopDeletionResult::Deleted)
592 LPM.markLoopAsDeleted(*L);
593
594 return Result != LoopDeletionResult::Unmodified;
595}