Bug Summary

File:src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/lib/Analysis/LoopInfo.cpp
Warning:line 239, column 47
Called C++ object pointer is null

Annotated Source Code

Press '?' to see keyboard shortcuts

clang -cc1 -cc1 -triple amd64-unknown-openbsd7.0 -analyze -disable-free -disable-llvm-verifier -discard-value-names -main-file-name LoopInfo.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 -mrelocation-model static -mframe-pointer=all -relaxed-aliasing -fno-rounding-math -mconstructor-aliases -munwind-tables -target-cpu x86-64 -tune-cpu generic -debugger-tuning=gdb -fcoverage-compilation-dir=/usr/src/gnu/usr.bin/clang/libLLVM/obj -resource-dir /usr/local/lib/clang/13.0.0 -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/Transforms -I /usr/src/gnu/usr.bin/clang/libLLVM/obj/../include/llvm/AMDGPU -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/lib/Target/AMDGPU -I /usr/src/gnu/usr.bin/clang/libLLVM/obj/../include/llvm/AMDGPU -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/lib/Target/AMDGPU -I /usr/src/gnu/usr.bin/clang/libLLVM/obj/../include/llvm/AMDGPU -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/lib/Target/AMDGPU -I /usr/src/gnu/usr.bin/clang/libLLVM/obj/../include/llvm/AMDGPU -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/lib/Target/AMDGPU -I /usr/src/gnu/usr.bin/clang/libLLVM/obj/../include/llvm/AMDGPU -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/lib/Target/AMDGPU -I /usr/src/gnu/usr.bin/clang/libLLVM/obj/../include/llvm/AMDGPU -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/lib/Target/AMDGPU -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/Analysis -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/ASMParser -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/BinaryFormat -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/Bitcode -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/Bitcode -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/Bitstream -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/Transforms -I /include/llvm/CodeGen -I /include/llvm/CodeGen/PBQP -I /usr/src/gnu/usr.bin/clang/libLLVM/obj/../include/llvm/IR -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/IR -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/Transforms -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/Transforms/Coroutines -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/ProfileData/Coverage -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/DebugInfo/CodeView -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/DebugInfo/DWARF -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/DebugInfo -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/DebugInfo/MSF -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/DebugInfo/PDB -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/Demangle -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/ExecutionEngine -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/ExecutionEngine/JITLink -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/ExecutionEngine/Orc -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/Frontend -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/Frontend/OpenACC -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/Frontend -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/Frontend/OpenMP -I /include/llvm/CodeGen/GlobalISel -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/IRReader -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/Transforms -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/Transforms/InstCombine -I /usr/src/gnu/usr.bin/clang/libLLVM/obj/../include/llvm/Transforms/InstCombine -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/Transforms -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/LTO -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/Linker -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/MC -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/MC/MCParser -I /include/llvm/CodeGen/MIRParser -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/Transforms -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/Object -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/Option -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/Passes -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/ -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/ProfileData -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/Transforms -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/Transforms/Scalar -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/ADT -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/Support -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/DebugInfo/Symbolize -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/Target -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/Transforms -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/Transforms/Utils -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/Transforms -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/Transforms/Vectorize -I /usr/src/gnu/usr.bin/clang/libLLVM/obj/../include/llvm/X86 -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/lib/Target/X86 -I /usr/src/gnu/usr.bin/clang/libLLVM/obj/../include/llvm/X86 -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/lib/Target/X86 -I /usr/src/gnu/usr.bin/clang/libLLVM/obj/../include/llvm/X86 -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/lib/Target/X86 -I /usr/src/gnu/usr.bin/clang/libLLVM/obj/../include/llvm/X86 -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/lib/Target/X86 -I /usr/src/gnu/usr.bin/clang/libLLVM/obj/../include/llvm/X86 -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/lib/Target/X86 -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/Transforms -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/Transforms/IPO -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include -I /usr/src/gnu/usr.bin/clang/libLLVM/../include -I /usr/src/gnu/usr.bin/clang/libLLVM/obj -I /usr/src/gnu/usr.bin/clang/libLLVM/obj/../include -D NDEBUG -D __STDC_LIMIT_MACROS -D __STDC_CONSTANT_MACROS -D __STDC_FORMAT_MACROS -D LLVM_PREFIX="/usr" -internal-isystem /usr/include/c++/v1 -internal-isystem /usr/local/lib/clang/13.0.0/include -internal-externc-isystem /usr/include -O2 -Wno-unused-parameter -Wwrite-strings -Wno-missing-field-initializers -Wno-long-long -Wno-comment -std=c++14 -fdeprecated-macro -fdebug-compilation-dir=/usr/src/gnu/usr.bin/clang/libLLVM/obj -ferror-limit 19 -fvisibility-inlines-hidden -fwrapv -stack-protector 2 -fno-rtti -fgnuc-version=4.2.1 -vectorize-loops -vectorize-slp -fno-builtin-malloc -fno-builtin-calloc -fno-builtin-realloc -fno-builtin-valloc -fno-builtin-free -fno-builtin-strdup -fno-builtin-strndup -analyzer-output=html -faddrsig -D__GCC_HAVE_DWARF2_CFI_ASM=1 -o /home/ben/Projects/vmm/scan-build/2022-01-12-194120-40624-1 -x c++ /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/lib/Analysis/LoopInfo.cpp
1//===- LoopInfo.cpp - Natural Loop Calculator -----------------------------===//
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 defines the LoopInfo class that is used to identify natural loops
10// and determine the loop depth of various nodes of the CFG. Note that the
11// loops identified may actually be several natural loops that share the same
12// header node... not just a single natural loop.
13//
14//===----------------------------------------------------------------------===//
15
16#include "llvm/Analysis/LoopInfo.h"
17#include "llvm/ADT/DepthFirstIterator.h"
18#include "llvm/ADT/ScopeExit.h"
19#include "llvm/ADT/SmallPtrSet.h"
20#include "llvm/Analysis/IVDescriptors.h"
21#include "llvm/Analysis/LoopInfoImpl.h"
22#include "llvm/Analysis/LoopIterator.h"
23#include "llvm/Analysis/LoopNestAnalysis.h"
24#include "llvm/Analysis/MemorySSA.h"
25#include "llvm/Analysis/MemorySSAUpdater.h"
26#include "llvm/Analysis/ScalarEvolutionExpressions.h"
27#include "llvm/Analysis/ValueTracking.h"
28#include "llvm/Config/llvm-config.h"
29#include "llvm/IR/CFG.h"
30#include "llvm/IR/Constants.h"
31#include "llvm/IR/DebugLoc.h"
32#include "llvm/IR/Dominators.h"
33#include "llvm/IR/IRPrintingPasses.h"
34#include "llvm/IR/Instructions.h"
35#include "llvm/IR/LLVMContext.h"
36#include "llvm/IR/Metadata.h"
37#include "llvm/IR/PassManager.h"
38#include "llvm/IR/PrintPasses.h"
39#include "llvm/InitializePasses.h"
40#include "llvm/Support/CommandLine.h"
41#include "llvm/Support/Debug.h"
42#include "llvm/Support/raw_ostream.h"
43#include <algorithm>
44using namespace llvm;
45
46// Explicitly instantiate methods in LoopInfoImpl.h for IR-level Loops.
47template class llvm::LoopBase<BasicBlock, Loop>;
48template class llvm::LoopInfoBase<BasicBlock, Loop>;
49
50// Always verify loopinfo if expensive checking is enabled.
51#ifdef EXPENSIVE_CHECKS
52bool llvm::VerifyLoopInfo = true;
53#else
54bool llvm::VerifyLoopInfo = false;
55#endif
56static cl::opt<bool, true>
57 VerifyLoopInfoX("verify-loop-info", cl::location(VerifyLoopInfo),
58 cl::Hidden, cl::desc("Verify loop info (time consuming)"));
59
60//===----------------------------------------------------------------------===//
61// Loop implementation
62//
63
64bool Loop::isLoopInvariant(const Value *V) const {
65 if (const Instruction *I = dyn_cast<Instruction>(V))
66 return !contains(I);
67 return true; // All non-instructions are loop invariant
68}
69
70bool Loop::hasLoopInvariantOperands(const Instruction *I) const {
71 return all_of(I->operands(), [this](Value *V) { return isLoopInvariant(V); });
72}
73
74bool Loop::makeLoopInvariant(Value *V, bool &Changed, Instruction *InsertPt,
75 MemorySSAUpdater *MSSAU) const {
76 if (Instruction *I = dyn_cast<Instruction>(V))
77 return makeLoopInvariant(I, Changed, InsertPt, MSSAU);
78 return true; // All non-instructions are loop-invariant.
79}
80
81bool Loop::makeLoopInvariant(Instruction *I, bool &Changed,
82 Instruction *InsertPt,
83 MemorySSAUpdater *MSSAU) const {
84 // Test if the value is already loop-invariant.
85 if (isLoopInvariant(I))
86 return true;
87 if (!isSafeToSpeculativelyExecute(I))
88 return false;
89 if (I->mayReadFromMemory())
90 return false;
91 // EH block instructions are immobile.
92 if (I->isEHPad())
93 return false;
94 // Determine the insertion point, unless one was given.
95 if (!InsertPt) {
96 BasicBlock *Preheader = getLoopPreheader();
97 // Without a preheader, hoisting is not feasible.
98 if (!Preheader)
99 return false;
100 InsertPt = Preheader->getTerminator();
101 }
102 // Don't hoist instructions with loop-variant operands.
103 for (Value *Operand : I->operands())
104 if (!makeLoopInvariant(Operand, Changed, InsertPt, MSSAU))
105 return false;
106
107 // Hoist.
108 I->moveBefore(InsertPt);
109 if (MSSAU)
110 if (auto *MUD = MSSAU->getMemorySSA()->getMemoryAccess(I))
111 MSSAU->moveToPlace(MUD, InsertPt->getParent(),
112 MemorySSA::BeforeTerminator);
113
114 // There is possibility of hoisting this instruction above some arbitrary
115 // condition. Any metadata defined on it can be control dependent on this
116 // condition. Conservatively strip it here so that we don't give any wrong
117 // information to the optimizer.
118 I->dropUnknownNonDebugMetadata();
119
120 Changed = true;
121 return true;
122}
123
124bool Loop::getIncomingAndBackEdge(BasicBlock *&Incoming,
125 BasicBlock *&Backedge) const {
126 BasicBlock *H = getHeader();
127
128 Incoming = nullptr;
129 Backedge = nullptr;
130 pred_iterator PI = pred_begin(H);
131 assert(PI != pred_end(H) && "Loop must have at least one backedge!")((void)0);
132 Backedge = *PI++;
133 if (PI == pred_end(H))
134 return false; // dead loop
135 Incoming = *PI++;
136 if (PI != pred_end(H))
137 return false; // multiple backedges?
138
139 if (contains(Incoming)) {
140 if (contains(Backedge))
141 return false;
142 std::swap(Incoming, Backedge);
143 } else if (!contains(Backedge))
144 return false;
145
146 assert(Incoming && Backedge && "expected non-null incoming and backedges")((void)0);
147 return true;
148}
149
150PHINode *Loop::getCanonicalInductionVariable() const {
151 BasicBlock *H = getHeader();
152
153 BasicBlock *Incoming = nullptr, *Backedge = nullptr;
154 if (!getIncomingAndBackEdge(Incoming, Backedge))
155 return nullptr;
156
157 // Loop over all of the PHI nodes, looking for a canonical indvar.
158 for (BasicBlock::iterator I = H->begin(); isa<PHINode>(I); ++I) {
159 PHINode *PN = cast<PHINode>(I);
160 if (ConstantInt *CI =
161 dyn_cast<ConstantInt>(PN->getIncomingValueForBlock(Incoming)))
162 if (CI->isZero())
163 if (Instruction *Inc =
164 dyn_cast<Instruction>(PN->getIncomingValueForBlock(Backedge)))
165 if (Inc->getOpcode() == Instruction::Add && Inc->getOperand(0) == PN)
166 if (ConstantInt *CI = dyn_cast<ConstantInt>(Inc->getOperand(1)))
167 if (CI->isOne())
168 return PN;
169 }
170 return nullptr;
171}
172
173/// Get the latch condition instruction.
174ICmpInst *Loop::getLatchCmpInst() const {
175 if (BasicBlock *Latch = getLoopLatch())
176 if (BranchInst *BI = dyn_cast_or_null<BranchInst>(Latch->getTerminator()))
177 if (BI->isConditional())
178 return dyn_cast<ICmpInst>(BI->getCondition());
179
180 return nullptr;
181}
182
183/// Return the final value of the loop induction variable if found.
184static Value *findFinalIVValue(const Loop &L, const PHINode &IndVar,
185 const Instruction &StepInst) {
186 ICmpInst *LatchCmpInst = L.getLatchCmpInst();
187 if (!LatchCmpInst)
188 return nullptr;
189
190 Value *Op0 = LatchCmpInst->getOperand(0);
191 Value *Op1 = LatchCmpInst->getOperand(1);
192 if (Op0 == &IndVar || Op0 == &StepInst)
193 return Op1;
194
195 if (Op1 == &IndVar || Op1 == &StepInst)
196 return Op0;
197
198 return nullptr;
199}
200
201Optional<Loop::LoopBounds> Loop::LoopBounds::getBounds(const Loop &L,
202 PHINode &IndVar,
203 ScalarEvolution &SE) {
204 InductionDescriptor IndDesc;
205 if (!InductionDescriptor::isInductionPHI(&IndVar, &L, &SE, IndDesc))
206 return None;
207
208 Value *InitialIVValue = IndDesc.getStartValue();
209 Instruction *StepInst = IndDesc.getInductionBinOp();
210 if (!InitialIVValue || !StepInst)
211 return None;
212
213 const SCEV *Step = IndDesc.getStep();
214 Value *StepInstOp1 = StepInst->getOperand(1);
215 Value *StepInstOp0 = StepInst->getOperand(0);
216 Value *StepValue = nullptr;
217 if (SE.getSCEV(StepInstOp1) == Step)
218 StepValue = StepInstOp1;
219 else if (SE.getSCEV(StepInstOp0) == Step)
220 StepValue = StepInstOp0;
221
222 Value *FinalIVValue = findFinalIVValue(L, IndVar, *StepInst);
223 if (!FinalIVValue)
224 return None;
225
226 return LoopBounds(L, *InitialIVValue, *StepInst, StepValue, *FinalIVValue,
227 SE);
228}
229
230using Direction = Loop::LoopBounds::Direction;
231
232ICmpInst::Predicate Loop::LoopBounds::getCanonicalPredicate() const {
233 BasicBlock *Latch = L.getLoopLatch();
234 assert(Latch && "Expecting valid latch")((void)0);
235
236 BranchInst *BI = dyn_cast_or_null<BranchInst>(Latch->getTerminator());
1
Assuming null pointer is passed into cast
2
'BI' initialized to a null pointer value
237 assert(BI && BI->isConditional() && "Expecting conditional latch branch")((void)0);
238
239 ICmpInst *LatchCmpInst = dyn_cast<ICmpInst>(BI->getCondition());
3
Called C++ object pointer is null
240 assert(LatchCmpInst &&((void)0)
241 "Expecting the latch compare instruction to be a CmpInst")((void)0);
242
243 // Need to inverse the predicate when first successor is not the loop
244 // header
245 ICmpInst::Predicate Pred = (BI->getSuccessor(0) == L.getHeader())
246 ? LatchCmpInst->getPredicate()
247 : LatchCmpInst->getInversePredicate();
248
249 if (LatchCmpInst->getOperand(0) == &getFinalIVValue())
250 Pred = ICmpInst::getSwappedPredicate(Pred);
251
252 // Need to flip strictness of the predicate when the latch compare instruction
253 // is not using StepInst
254 if (LatchCmpInst->getOperand(0) == &getStepInst() ||
255 LatchCmpInst->getOperand(1) == &getStepInst())
256 return Pred;
257
258 // Cannot flip strictness of NE and EQ
259 if (Pred != ICmpInst::ICMP_NE && Pred != ICmpInst::ICMP_EQ)
260 return ICmpInst::getFlippedStrictnessPredicate(Pred);
261
262 Direction D = getDirection();
263 if (D == Direction::Increasing)
264 return ICmpInst::ICMP_SLT;
265
266 if (D == Direction::Decreasing)
267 return ICmpInst::ICMP_SGT;
268
269 // If cannot determine the direction, then unable to find the canonical
270 // predicate
271 return ICmpInst::BAD_ICMP_PREDICATE;
272}
273
274Direction Loop::LoopBounds::getDirection() const {
275 if (const SCEVAddRecExpr *StepAddRecExpr =
276 dyn_cast<SCEVAddRecExpr>(SE.getSCEV(&getStepInst())))
277 if (const SCEV *StepRecur = StepAddRecExpr->getStepRecurrence(SE)) {
278 if (SE.isKnownPositive(StepRecur))
279 return Direction::Increasing;
280 if (SE.isKnownNegative(StepRecur))
281 return Direction::Decreasing;
282 }
283
284 return Direction::Unknown;
285}
286
287Optional<Loop::LoopBounds> Loop::getBounds(ScalarEvolution &SE) const {
288 if (PHINode *IndVar = getInductionVariable(SE))
289 return LoopBounds::getBounds(*this, *IndVar, SE);
290
291 return None;
292}
293
294PHINode *Loop::getInductionVariable(ScalarEvolution &SE) const {
295 if (!isLoopSimplifyForm())
296 return nullptr;
297
298 BasicBlock *Header = getHeader();
299 assert(Header && "Expected a valid loop header")((void)0);
300 ICmpInst *CmpInst = getLatchCmpInst();
301 if (!CmpInst)
302 return nullptr;
303
304 Instruction *LatchCmpOp0 = dyn_cast<Instruction>(CmpInst->getOperand(0));
305 Instruction *LatchCmpOp1 = dyn_cast<Instruction>(CmpInst->getOperand(1));
306
307 for (PHINode &IndVar : Header->phis()) {
308 InductionDescriptor IndDesc;
309 if (!InductionDescriptor::isInductionPHI(&IndVar, this, &SE, IndDesc))
310 continue;
311
312 Instruction *StepInst = IndDesc.getInductionBinOp();
313
314 // case 1:
315 // IndVar = phi[{InitialValue, preheader}, {StepInst, latch}]
316 // StepInst = IndVar + step
317 // cmp = StepInst < FinalValue
318 if (StepInst == LatchCmpOp0 || StepInst == LatchCmpOp1)
319 return &IndVar;
320
321 // case 2:
322 // IndVar = phi[{InitialValue, preheader}, {StepInst, latch}]
323 // StepInst = IndVar + step
324 // cmp = IndVar < FinalValue
325 if (&IndVar == LatchCmpOp0 || &IndVar == LatchCmpOp1)
326 return &IndVar;
327 }
328
329 return nullptr;
330}
331
332bool Loop::getInductionDescriptor(ScalarEvolution &SE,
333 InductionDescriptor &IndDesc) const {
334 if (PHINode *IndVar = getInductionVariable(SE))
335 return InductionDescriptor::isInductionPHI(IndVar, this, &SE, IndDesc);
336
337 return false;
338}
339
340bool Loop::isAuxiliaryInductionVariable(PHINode &AuxIndVar,
341 ScalarEvolution &SE) const {
342 // Located in the loop header
343 BasicBlock *Header = getHeader();
344 if (AuxIndVar.getParent() != Header)
345 return false;
346
347 // No uses outside of the loop
348 for (User *U : AuxIndVar.users())
349 if (const Instruction *I = dyn_cast<Instruction>(U))
350 if (!contains(I))
351 return false;
352
353 InductionDescriptor IndDesc;
354 if (!InductionDescriptor::isInductionPHI(&AuxIndVar, this, &SE, IndDesc))
355 return false;
356
357 // The step instruction opcode should be add or sub.
358 if (IndDesc.getInductionOpcode() != Instruction::Add &&
359 IndDesc.getInductionOpcode() != Instruction::Sub)
360 return false;
361
362 // Incremented by a loop invariant step for each loop iteration
363 return SE.isLoopInvariant(IndDesc.getStep(), this);
364}
365
366BranchInst *Loop::getLoopGuardBranch() const {
367 if (!isLoopSimplifyForm())
368 return nullptr;
369
370 BasicBlock *Preheader = getLoopPreheader();
371 assert(Preheader && getLoopLatch() &&((void)0)
372 "Expecting a loop with valid preheader and latch")((void)0);
373
374 // Loop should be in rotate form.
375 if (!isRotatedForm())
376 return nullptr;
377
378 // Disallow loops with more than one unique exit block, as we do not verify
379 // that GuardOtherSucc post dominates all exit blocks.
380 BasicBlock *ExitFromLatch = getUniqueExitBlock();
381 if (!ExitFromLatch)
382 return nullptr;
383
384 BasicBlock *GuardBB = Preheader->getUniquePredecessor();
385 if (!GuardBB)
386 return nullptr;
387
388 assert(GuardBB->getTerminator() && "Expecting valid guard terminator")((void)0);
389
390 BranchInst *GuardBI = dyn_cast<BranchInst>(GuardBB->getTerminator());
391 if (!GuardBI || GuardBI->isUnconditional())
392 return nullptr;
393
394 BasicBlock *GuardOtherSucc = (GuardBI->getSuccessor(0) == Preheader)
395 ? GuardBI->getSuccessor(1)
396 : GuardBI->getSuccessor(0);
397
398 // Check if ExitFromLatch (or any BasicBlock which is an empty unique
399 // successor of ExitFromLatch) is equal to GuardOtherSucc. If
400 // skipEmptyBlockUntil returns GuardOtherSucc, then the guard branch for the
401 // loop is GuardBI (return GuardBI), otherwise return nullptr.
402 if (&LoopNest::skipEmptyBlockUntil(ExitFromLatch, GuardOtherSucc,
403 /*CheckUniquePred=*/true) ==
404 GuardOtherSucc)
405 return GuardBI;
406 else
407 return nullptr;
408}
409
410bool Loop::isCanonical(ScalarEvolution &SE) const {
411 InductionDescriptor IndDesc;
412 if (!getInductionDescriptor(SE, IndDesc))
413 return false;
414
415 ConstantInt *Init = dyn_cast_or_null<ConstantInt>(IndDesc.getStartValue());
416 if (!Init || !Init->isZero())
417 return false;
418
419 if (IndDesc.getInductionOpcode() != Instruction::Add)
420 return false;
421
422 ConstantInt *Step = IndDesc.getConstIntStepValue();
423 if (!Step || !Step->isOne())
424 return false;
425
426 return true;
427}
428
429// Check that 'BB' doesn't have any uses outside of the 'L'
430static bool isBlockInLCSSAForm(const Loop &L, const BasicBlock &BB,
431 const DominatorTree &DT) {
432 for (const Instruction &I : BB) {
433 // Tokens can't be used in PHI nodes and live-out tokens prevent loop
434 // optimizations, so for the purposes of considered LCSSA form, we
435 // can ignore them.
436 if (I.getType()->isTokenTy())
437 continue;
438
439 for (const Use &U : I.uses()) {
440 const Instruction *UI = cast<Instruction>(U.getUser());
441 const BasicBlock *UserBB = UI->getParent();
442
443 // For practical purposes, we consider that the use in a PHI
444 // occurs in the respective predecessor block. For more info,
445 // see the `phi` doc in LangRef and the LCSSA doc.
446 if (const PHINode *P = dyn_cast<PHINode>(UI))
447 UserBB = P->getIncomingBlock(U);
448
449 // Check the current block, as a fast-path, before checking whether
450 // the use is anywhere in the loop. Most values are used in the same
451 // block they are defined in. Also, blocks not reachable from the
452 // entry are special; uses in them don't need to go through PHIs.
453 if (UserBB != &BB && !L.contains(UserBB) &&
454 DT.isReachableFromEntry(UserBB))
455 return false;
456 }
457 }
458 return true;
459}
460
461bool Loop::isLCSSAForm(const DominatorTree &DT) const {
462 // For each block we check that it doesn't have any uses outside of this loop.
463 return all_of(this->blocks(), [&](const BasicBlock *BB) {
464 return isBlockInLCSSAForm(*this, *BB, DT);
465 });
466}
467
468bool Loop::isRecursivelyLCSSAForm(const DominatorTree &DT,
469 const LoopInfo &LI) const {
470 // For each block we check that it doesn't have any uses outside of its
471 // innermost loop. This process will transitively guarantee that the current
472 // loop and all of the nested loops are in LCSSA form.
473 return all_of(this->blocks(), [&](const BasicBlock *BB) {
474 return isBlockInLCSSAForm(*LI.getLoopFor(BB), *BB, DT);
475 });
476}
477
478bool Loop::isLoopSimplifyForm() const {
479 // Normal-form loops have a preheader, a single backedge, and all of their
480 // exits have all their predecessors inside the loop.
481 return getLoopPreheader() && getLoopLatch() && hasDedicatedExits();
482}
483
484// Routines that reform the loop CFG and split edges often fail on indirectbr.
485bool Loop::isSafeToClone() const {
486 // Return false if any loop blocks contain indirectbrs, or there are any calls
487 // to noduplicate functions.
488 // FIXME: it should be ok to clone CallBrInst's if we correctly update the
489 // operand list to reflect the newly cloned labels.
490 for (BasicBlock *BB : this->blocks()) {
491 if (isa<IndirectBrInst>(BB->getTerminator()) ||
492 isa<CallBrInst>(BB->getTerminator()))
493 return false;
494
495 for (Instruction &I : *BB)
496 if (auto *CB = dyn_cast<CallBase>(&I))
497 if (CB->cannotDuplicate())
498 return false;
499 }
500 return true;
501}
502
503MDNode *Loop::getLoopID() const {
504 MDNode *LoopID = nullptr;
505
506 // Go through the latch blocks and check the terminator for the metadata.
507 SmallVector<BasicBlock *, 4> LatchesBlocks;
508 getLoopLatches(LatchesBlocks);
509 for (BasicBlock *BB : LatchesBlocks) {
510 Instruction *TI = BB->getTerminator();
511 MDNode *MD = TI->getMetadata(LLVMContext::MD_loop);
512
513 if (!MD)
514 return nullptr;
515
516 if (!LoopID)
517 LoopID = MD;
518 else if (MD != LoopID)
519 return nullptr;
520 }
521 if (!LoopID || LoopID->getNumOperands() == 0 ||
522 LoopID->getOperand(0) != LoopID)
523 return nullptr;
524 return LoopID;
525}
526
527void Loop::setLoopID(MDNode *LoopID) const {
528 assert((!LoopID || LoopID->getNumOperands() > 0) &&((void)0)
529 "Loop ID needs at least one operand")((void)0);
530 assert((!LoopID || LoopID->getOperand(0) == LoopID) &&((void)0)
531 "Loop ID should refer to itself")((void)0);
532
533 SmallVector<BasicBlock *, 4> LoopLatches;
534 getLoopLatches(LoopLatches);
535 for (BasicBlock *BB : LoopLatches)
536 BB->getTerminator()->setMetadata(LLVMContext::MD_loop, LoopID);
537}
538
539void Loop::setLoopAlreadyUnrolled() {
540 LLVMContext &Context = getHeader()->getContext();
541
542 MDNode *DisableUnrollMD =
543 MDNode::get(Context, MDString::get(Context, "llvm.loop.unroll.disable"));
544 MDNode *LoopID = getLoopID();
545 MDNode *NewLoopID = makePostTransformationMetadata(
546 Context, LoopID, {"llvm.loop.unroll."}, {DisableUnrollMD});
547 setLoopID(NewLoopID);
548}
549
550void Loop::setLoopMustProgress() {
551 LLVMContext &Context = getHeader()->getContext();
552
553 MDNode *MustProgress = findOptionMDForLoop(this, "llvm.loop.mustprogress");
554
555 if (MustProgress)
556 return;
557
558 MDNode *MustProgressMD =
559 MDNode::get(Context, MDString::get(Context, "llvm.loop.mustprogress"));
560 MDNode *LoopID = getLoopID();
561 MDNode *NewLoopID =
562 makePostTransformationMetadata(Context, LoopID, {}, {MustProgressMD});
563 setLoopID(NewLoopID);
564}
565
566bool Loop::isAnnotatedParallel() const {
567 MDNode *DesiredLoopIdMetadata = getLoopID();
568
569 if (!DesiredLoopIdMetadata)
570 return false;
571
572 MDNode *ParallelAccesses =
573 findOptionMDForLoop(this, "llvm.loop.parallel_accesses");
574 SmallPtrSet<MDNode *, 4>
575 ParallelAccessGroups; // For scalable 'contains' check.
576 if (ParallelAccesses) {
577 for (const MDOperand &MD : drop_begin(ParallelAccesses->operands())) {
578 MDNode *AccGroup = cast<MDNode>(MD.get());
579 assert(isValidAsAccessGroup(AccGroup) &&((void)0)
580 "List item must be an access group")((void)0);
581 ParallelAccessGroups.insert(AccGroup);
582 }
583 }
584
585 // The loop branch contains the parallel loop metadata. In order to ensure
586 // that any parallel-loop-unaware optimization pass hasn't added loop-carried
587 // dependencies (thus converted the loop back to a sequential loop), check
588 // that all the memory instructions in the loop belong to an access group that
589 // is parallel to this loop.
590 for (BasicBlock *BB : this->blocks()) {
591 for (Instruction &I : *BB) {
592 if (!I.mayReadOrWriteMemory())
593 continue;
594
595 if (MDNode *AccessGroup = I.getMetadata(LLVMContext::MD_access_group)) {
596 auto ContainsAccessGroup = [&ParallelAccessGroups](MDNode *AG) -> bool {
597 if (AG->getNumOperands() == 0) {
598 assert(isValidAsAccessGroup(AG) && "Item must be an access group")((void)0);
599 return ParallelAccessGroups.count(AG);
600 }
601
602 for (const MDOperand &AccessListItem : AG->operands()) {
603 MDNode *AccGroup = cast<MDNode>(AccessListItem.get());
604 assert(isValidAsAccessGroup(AccGroup) &&((void)0)
605 "List item must be an access group")((void)0);
606 if (ParallelAccessGroups.count(AccGroup))
607 return true;
608 }
609 return false;
610 };
611
612 if (ContainsAccessGroup(AccessGroup))
613 continue;
614 }
615
616 // The memory instruction can refer to the loop identifier metadata
617 // directly or indirectly through another list metadata (in case of
618 // nested parallel loops). The loop identifier metadata refers to
619 // itself so we can check both cases with the same routine.
620 MDNode *LoopIdMD =
621 I.getMetadata(LLVMContext::MD_mem_parallel_loop_access);
622
623 if (!LoopIdMD)
624 return false;
625
626 if (!llvm::is_contained(LoopIdMD->operands(), DesiredLoopIdMetadata))
627 return false;
628 }
629 }
630 return true;
631}
632
633DebugLoc Loop::getStartLoc() const { return getLocRange().getStart(); }
634
635Loop::LocRange Loop::getLocRange() const {
636 // If we have a debug location in the loop ID, then use it.
637 if (MDNode *LoopID = getLoopID()) {
638 DebugLoc Start;
639 // We use the first DebugLoc in the header as the start location of the loop
640 // and if there is a second DebugLoc in the header we use it as end location
641 // of the loop.
642 for (unsigned i = 1, ie = LoopID->getNumOperands(); i < ie; ++i) {
643 if (DILocation *L = dyn_cast<DILocation>(LoopID->getOperand(i))) {
644 if (!Start)
645 Start = DebugLoc(L);
646 else
647 return LocRange(Start, DebugLoc(L));
648 }
649 }
650
651 if (Start)
652 return LocRange(Start);
653 }
654
655 // Try the pre-header first.
656 if (BasicBlock *PHeadBB = getLoopPreheader())
657 if (DebugLoc DL = PHeadBB->getTerminator()->getDebugLoc())
658 return LocRange(DL);
659
660 // If we have no pre-header or there are no instructions with debug
661 // info in it, try the header.
662 if (BasicBlock *HeadBB = getHeader())
663 return LocRange(HeadBB->getTerminator()->getDebugLoc());
664
665 return LocRange();
666}
667
668#if !defined(NDEBUG1) || defined(LLVM_ENABLE_DUMP)
669LLVM_DUMP_METHOD__attribute__((noinline)) void Loop::dump() const { print(dbgs()); }
670
671LLVM_DUMP_METHOD__attribute__((noinline)) void Loop::dumpVerbose() const {
672 print(dbgs(), /*Verbose=*/true);
673}
674#endif
675
676//===----------------------------------------------------------------------===//
677// UnloopUpdater implementation
678//
679
680namespace {
681/// Find the new parent loop for all blocks within the "unloop" whose last
682/// backedges has just been removed.
683class UnloopUpdater {
684 Loop &Unloop;
685 LoopInfo *LI;
686
687 LoopBlocksDFS DFS;
688
689 // Map unloop's immediate subloops to their nearest reachable parents. Nested
690 // loops within these subloops will not change parents. However, an immediate
691 // subloop's new parent will be the nearest loop reachable from either its own
692 // exits *or* any of its nested loop's exits.
693 DenseMap<Loop *, Loop *> SubloopParents;
694
695 // Flag the presence of an irreducible backedge whose destination is a block
696 // directly contained by the original unloop.
697 bool FoundIB;
698
699public:
700 UnloopUpdater(Loop *UL, LoopInfo *LInfo)
701 : Unloop(*UL), LI(LInfo), DFS(UL), FoundIB(false) {}
702
703 void updateBlockParents();
704
705 void removeBlocksFromAncestors();
706
707 void updateSubloopParents();
708
709protected:
710 Loop *getNearestLoop(BasicBlock *BB, Loop *BBLoop);
711};
712} // end anonymous namespace
713
714/// Update the parent loop for all blocks that are directly contained within the
715/// original "unloop".
716void UnloopUpdater::updateBlockParents() {
717 if (Unloop.getNumBlocks()) {
718 // Perform a post order CFG traversal of all blocks within this loop,
719 // propagating the nearest loop from successors to predecessors.
720 LoopBlocksTraversal Traversal(DFS, LI);
721 for (BasicBlock *POI : Traversal) {
722
723 Loop *L = LI->getLoopFor(POI);
724 Loop *NL = getNearestLoop(POI, L);
725
726 if (NL != L) {
727 // For reducible loops, NL is now an ancestor of Unloop.
728 assert((NL != &Unloop && (!NL || NL->contains(&Unloop))) &&((void)0)
729 "uninitialized successor")((void)0);
730 LI->changeLoopFor(POI, NL);
731 } else {
732 // Or the current block is part of a subloop, in which case its parent
733 // is unchanged.
734 assert((FoundIB || Unloop.contains(L)) && "uninitialized successor")((void)0);
735 }
736 }
737 }
738 // Each irreducible loop within the unloop induces a round of iteration using
739 // the DFS result cached by Traversal.
740 bool Changed = FoundIB;
741 for (unsigned NIters = 0; Changed; ++NIters) {
742 assert(NIters < Unloop.getNumBlocks() && "runaway iterative algorithm")((void)0);
743
744 // Iterate over the postorder list of blocks, propagating the nearest loop
745 // from successors to predecessors as before.
746 Changed = false;
747 for (LoopBlocksDFS::POIterator POI = DFS.beginPostorder(),
748 POE = DFS.endPostorder();
749 POI != POE; ++POI) {
750
751 Loop *L = LI->getLoopFor(*POI);
752 Loop *NL = getNearestLoop(*POI, L);
753 if (NL != L) {
754 assert(NL != &Unloop && (!NL || NL->contains(&Unloop)) &&((void)0)
755 "uninitialized successor")((void)0);
756 LI->changeLoopFor(*POI, NL);
757 Changed = true;
758 }
759 }
760 }
761}
762
763/// Remove unloop's blocks from all ancestors below their new parents.
764void UnloopUpdater::removeBlocksFromAncestors() {
765 // Remove all unloop's blocks (including those in nested subloops) from
766 // ancestors below the new parent loop.
767 for (BasicBlock *BB : Unloop.blocks()) {
768 Loop *OuterParent = LI->getLoopFor(BB);
769 if (Unloop.contains(OuterParent)) {
770 while (OuterParent->getParentLoop() != &Unloop)
771 OuterParent = OuterParent->getParentLoop();
772 OuterParent = SubloopParents[OuterParent];
773 }
774 // Remove blocks from former Ancestors except Unloop itself which will be
775 // deleted.
776 for (Loop *OldParent = Unloop.getParentLoop(); OldParent != OuterParent;
777 OldParent = OldParent->getParentLoop()) {
778 assert(OldParent && "new loop is not an ancestor of the original")((void)0);
779 OldParent->removeBlockFromLoop(BB);
780 }
781 }
782}
783
784/// Update the parent loop for all subloops directly nested within unloop.
785void UnloopUpdater::updateSubloopParents() {
786 while (!Unloop.isInnermost()) {
787 Loop *Subloop = *std::prev(Unloop.end());
788 Unloop.removeChildLoop(std::prev(Unloop.end()));
789
790 assert(SubloopParents.count(Subloop) && "DFS failed to visit subloop")((void)0);
791 if (Loop *Parent = SubloopParents[Subloop])
792 Parent->addChildLoop(Subloop);
793 else
794 LI->addTopLevelLoop(Subloop);
795 }
796}
797
798/// Return the nearest parent loop among this block's successors. If a successor
799/// is a subloop header, consider its parent to be the nearest parent of the
800/// subloop's exits.
801///
802/// For subloop blocks, simply update SubloopParents and return NULL.
803Loop *UnloopUpdater::getNearestLoop(BasicBlock *BB, Loop *BBLoop) {
804
805 // Initially for blocks directly contained by Unloop, NearLoop == Unloop and
806 // is considered uninitialized.
807 Loop *NearLoop = BBLoop;
808
809 Loop *Subloop = nullptr;
810 if (NearLoop != &Unloop && Unloop.contains(NearLoop)) {
811 Subloop = NearLoop;
812 // Find the subloop ancestor that is directly contained within Unloop.
813 while (Subloop->getParentLoop() != &Unloop) {
814 Subloop = Subloop->getParentLoop();
815 assert(Subloop && "subloop is not an ancestor of the original loop")((void)0);
816 }
817 // Get the current nearest parent of the Subloop exits, initially Unloop.
818 NearLoop = SubloopParents.insert({Subloop, &Unloop}).first->second;
819 }
820
821 succ_iterator I = succ_begin(BB), E = succ_end(BB);
822 if (I == E) {
823 assert(!Subloop && "subloop blocks must have a successor")((void)0);
824 NearLoop = nullptr; // unloop blocks may now exit the function.
825 }
826 for (; I != E; ++I) {
827 if (*I == BB)
828 continue; // self loops are uninteresting
829
830 Loop *L = LI->getLoopFor(*I);
831 if (L == &Unloop) {
832 // This successor has not been processed. This path must lead to an
833 // irreducible backedge.
834 assert((FoundIB || !DFS.hasPostorder(*I)) && "should have seen IB")((void)0);
835 FoundIB = true;
836 }
837 if (L != &Unloop && Unloop.contains(L)) {
838 // Successor is in a subloop.
839 if (Subloop)
840 continue; // Branching within subloops. Ignore it.
841
842 // BB branches from the original into a subloop header.
843 assert(L->getParentLoop() == &Unloop && "cannot skip into nested loops")((void)0);
844
845 // Get the current nearest parent of the Subloop's exits.
846 L = SubloopParents[L];
847 // L could be Unloop if the only exit was an irreducible backedge.
848 }
849 if (L == &Unloop) {
850 continue;
851 }
852 // Handle critical edges from Unloop into a sibling loop.
853 if (L && !L->contains(&Unloop)) {
854 L = L->getParentLoop();
855 }
856 // Remember the nearest parent loop among successors or subloop exits.
857 if (NearLoop == &Unloop || !NearLoop || NearLoop->contains(L))
858 NearLoop = L;
859 }
860 if (Subloop) {
861 SubloopParents[Subloop] = NearLoop;
862 return BBLoop;
863 }
864 return NearLoop;
865}
866
867LoopInfo::LoopInfo(const DomTreeBase<BasicBlock> &DomTree) { analyze(DomTree); }
868
869bool LoopInfo::invalidate(Function &F, const PreservedAnalyses &PA,
870 FunctionAnalysisManager::Invalidator &) {
871 // Check whether the analysis, all analyses on functions, or the function's
872 // CFG have been preserved.
873 auto PAC = PA.getChecker<LoopAnalysis>();
874 return !(PAC.preserved() || PAC.preservedSet<AllAnalysesOn<Function>>() ||
875 PAC.preservedSet<CFGAnalyses>());
876}
877
878void LoopInfo::erase(Loop *Unloop) {
879 assert(!Unloop->isInvalid() && "Loop has already been erased!")((void)0);
880
881 auto InvalidateOnExit = make_scope_exit([&]() { destroy(Unloop); });
882
883 // First handle the special case of no parent loop to simplify the algorithm.
884 if (Unloop->isOutermost()) {
885 // Since BBLoop had no parent, Unloop blocks are no longer in a loop.
886 for (BasicBlock *BB : Unloop->blocks()) {
887 // Don't reparent blocks in subloops.
888 if (getLoopFor(BB) != Unloop)
889 continue;
890
891 // Blocks no longer have a parent but are still referenced by Unloop until
892 // the Unloop object is deleted.
893 changeLoopFor(BB, nullptr);
894 }
895
896 // Remove the loop from the top-level LoopInfo object.
897 for (iterator I = begin();; ++I) {
898 assert(I != end() && "Couldn't find loop")((void)0);
899 if (*I == Unloop) {
900 removeLoop(I);
901 break;
902 }
903 }
904
905 // Move all of the subloops to the top-level.
906 while (!Unloop->isInnermost())
907 addTopLevelLoop(Unloop->removeChildLoop(std::prev(Unloop->end())));
908
909 return;
910 }
911
912 // Update the parent loop for all blocks within the loop. Blocks within
913 // subloops will not change parents.
914 UnloopUpdater Updater(Unloop, this);
915 Updater.updateBlockParents();
916
917 // Remove blocks from former ancestor loops.
918 Updater.removeBlocksFromAncestors();
919
920 // Add direct subloops as children in their new parent loop.
921 Updater.updateSubloopParents();
922
923 // Remove unloop from its parent loop.
924 Loop *ParentLoop = Unloop->getParentLoop();
925 for (Loop::iterator I = ParentLoop->begin();; ++I) {
926 assert(I != ParentLoop->end() && "Couldn't find loop")((void)0);
927 if (*I == Unloop) {
928 ParentLoop->removeChildLoop(I);
929 break;
930 }
931 }
932}
933
934bool
935LoopInfo::wouldBeOutOfLoopUseRequiringLCSSA(const Value *V,
936 const BasicBlock *ExitBB) const {
937 if (V->getType()->isTokenTy())
938 // We can't form PHIs of token type, so the definition of LCSSA excludes
939 // values of that type.
940 return false;
941
942 const Instruction *I = dyn_cast<Instruction>(V);
943 if (!I)
944 return false;
945 const Loop *L = getLoopFor(I->getParent());
946 if (!L)
947 return false;
948 if (L->contains(ExitBB))
949 // Could be an exit bb of a subloop and contained in defining loop
950 return false;
951
952 // We found a (new) out-of-loop use location, for a value defined in-loop.
953 // (Note that because of LCSSA, we don't have to account for values defined
954 // in sibling loops. Such values will have LCSSA phis of their own in the
955 // common parent loop.)
956 return true;
957}
958
959AnalysisKey LoopAnalysis::Key;
960
961LoopInfo LoopAnalysis::run(Function &F, FunctionAnalysisManager &AM) {
962 // FIXME: Currently we create a LoopInfo from scratch for every function.
963 // This may prove to be too wasteful due to deallocating and re-allocating
964 // memory each time for the underlying map and vector datastructures. At some
965 // point it may prove worthwhile to use a freelist and recycle LoopInfo
966 // objects. I don't want to add that kind of complexity until the scope of
967 // the problem is better understood.
968 LoopInfo LI;
969 LI.analyze(AM.getResult<DominatorTreeAnalysis>(F));
970 return LI;
971}
972
973PreservedAnalyses LoopPrinterPass::run(Function &F,
974 FunctionAnalysisManager &AM) {
975 AM.getResult<LoopAnalysis>(F).print(OS);
976 return PreservedAnalyses::all();
977}
978
979void llvm::printLoop(Loop &L, raw_ostream &OS, const std::string &Banner) {
980
981 if (forcePrintModuleIR()) {
982 // handling -print-module-scope
983 OS << Banner << " (loop: ";
984 L.getHeader()->printAsOperand(OS, false);
985 OS << ")\n";
986
987 // printing whole module
988 OS << *L.getHeader()->getModule();
989 return;
990 }
991
992 OS << Banner;
993
994 auto *PreHeader = L.getLoopPreheader();
995 if (PreHeader) {
996 OS << "\n; Preheader:";
997 PreHeader->print(OS);
998 OS << "\n; Loop:";
999 }
1000
1001 for (auto *Block : L.blocks())
1002 if (Block)
1003 Block->print(OS);
1004 else
1005 OS << "Printing <null> block";
1006
1007 SmallVector<BasicBlock *, 8> ExitBlocks;
1008 L.getExitBlocks(ExitBlocks);
1009 if (!ExitBlocks.empty()) {
1010 OS << "\n; Exit blocks";
1011 for (auto *Block : ExitBlocks)
1012 if (Block)
1013 Block->print(OS);
1014 else
1015 OS << "Printing <null> block";
1016 }
1017}
1018
1019MDNode *llvm::findOptionMDForLoopID(MDNode *LoopID, StringRef Name) {
1020 // No loop metadata node, no loop properties.
1021 if (!LoopID)
1022 return nullptr;
1023
1024 // First operand should refer to the metadata node itself, for legacy reasons.
1025 assert(LoopID->getNumOperands() > 0 && "requires at least one operand")((void)0);
1026 assert(LoopID->getOperand(0) == LoopID && "invalid loop id")((void)0);
1027
1028 // Iterate over the metdata node operands and look for MDString metadata.
1029 for (unsigned i = 1, e = LoopID->getNumOperands(); i < e; ++i) {
1030 MDNode *MD = dyn_cast<MDNode>(LoopID->getOperand(i));
1031 if (!MD || MD->getNumOperands() < 1)
1032 continue;
1033 MDString *S = dyn_cast<MDString>(MD->getOperand(0));
1034 if (!S)
1035 continue;
1036 // Return the operand node if MDString holds expected metadata.
1037 if (Name.equals(S->getString()))
1038 return MD;
1039 }
1040
1041 // Loop property not found.
1042 return nullptr;
1043}
1044
1045MDNode *llvm::findOptionMDForLoop(const Loop *TheLoop, StringRef Name) {
1046 return findOptionMDForLoopID(TheLoop->getLoopID(), Name);
1047}
1048
1049/// Find string metadata for loop
1050///
1051/// If it has a value (e.g. {"llvm.distribute", 1} return the value as an
1052/// operand or null otherwise. If the string metadata is not found return
1053/// Optional's not-a-value.
1054Optional<const MDOperand *> llvm::findStringMetadataForLoop(const Loop *TheLoop,
1055 StringRef Name) {
1056 MDNode *MD = findOptionMDForLoop(TheLoop, Name);
1057 if (!MD)
1058 return None;
1059 switch (MD->getNumOperands()) {
1060 case 1:
1061 return nullptr;
1062 case 2:
1063 return &MD->getOperand(1);
1064 default:
1065 llvm_unreachable("loop metadata has 0 or 1 operand")__builtin_unreachable();
1066 }
1067}
1068
1069Optional<bool> llvm::getOptionalBoolLoopAttribute(const Loop *TheLoop,
1070 StringRef Name) {
1071 MDNode *MD = findOptionMDForLoop(TheLoop, Name);
1072 if (!MD)
1073 return None;
1074 switch (MD->getNumOperands()) {
1075 case 1:
1076 // When the value is absent it is interpreted as 'attribute set'.
1077 return true;
1078 case 2:
1079 if (ConstantInt *IntMD =
1080 mdconst::extract_or_null<ConstantInt>(MD->getOperand(1).get()))
1081 return IntMD->getZExtValue();
1082 return true;
1083 }
1084 llvm_unreachable("unexpected number of options")__builtin_unreachable();
1085}
1086
1087bool llvm::getBooleanLoopAttribute(const Loop *TheLoop, StringRef Name) {
1088 return getOptionalBoolLoopAttribute(TheLoop, Name).getValueOr(false);
1089}
1090
1091llvm::Optional<int> llvm::getOptionalIntLoopAttribute(const Loop *TheLoop,
1092 StringRef Name) {
1093 const MDOperand *AttrMD =
1094 findStringMetadataForLoop(TheLoop, Name).getValueOr(nullptr);
1095 if (!AttrMD)
1096 return None;
1097
1098 ConstantInt *IntMD = mdconst::extract_or_null<ConstantInt>(AttrMD->get());
1099 if (!IntMD)
1100 return None;
1101
1102 return IntMD->getSExtValue();
1103}
1104
1105static const char *LLVMLoopMustProgress = "llvm.loop.mustprogress";
1106
1107bool llvm::hasMustProgress(const Loop *L) {
1108 return getBooleanLoopAttribute(L, LLVMLoopMustProgress);
1109}
1110
1111bool llvm::isMustProgress(const Loop *L) {
1112 return L->getHeader()->getParent()->mustProgress() || hasMustProgress(L);
1113}
1114
1115bool llvm::isValidAsAccessGroup(MDNode *Node) {
1116 return Node->getNumOperands() == 0 && Node->isDistinct();
1117}
1118
1119MDNode *llvm::makePostTransformationMetadata(LLVMContext &Context,
1120 MDNode *OrigLoopID,
1121 ArrayRef<StringRef> RemovePrefixes,
1122 ArrayRef<MDNode *> AddAttrs) {
1123 // First remove any existing loop metadata related to this transformation.
1124 SmallVector<Metadata *, 4> MDs;
1125
1126 // Reserve first location for self reference to the LoopID metadata node.
1127 MDs.push_back(nullptr);
1128
1129 // Remove metadata for the transformation that has been applied or that became
1130 // outdated.
1131 if (OrigLoopID) {
1132 for (unsigned i = 1, ie = OrigLoopID->getNumOperands(); i < ie; ++i) {
1133 bool IsVectorMetadata = false;
1134 Metadata *Op = OrigLoopID->getOperand(i);
1135 if (MDNode *MD = dyn_cast<MDNode>(Op)) {
1136 const MDString *S = dyn_cast<MDString>(MD->getOperand(0));
1137 if (S)
1138 IsVectorMetadata =
1139 llvm::any_of(RemovePrefixes, [S](StringRef Prefix) -> bool {
1140 return S->getString().startswith(Prefix);
1141 });
1142 }
1143 if (!IsVectorMetadata)
1144 MDs.push_back(Op);
1145 }
1146 }
1147
1148 // Add metadata to avoid reapplying a transformation, such as
1149 // llvm.loop.unroll.disable and llvm.loop.isvectorized.
1150 MDs.append(AddAttrs.begin(), AddAttrs.end());
1151
1152 MDNode *NewLoopID = MDNode::getDistinct(Context, MDs);
1153 // Replace the temporary node with a self-reference.
1154 NewLoopID->replaceOperandWith(0, NewLoopID);
1155 return NewLoopID;
1156}
1157
1158//===----------------------------------------------------------------------===//
1159// LoopInfo implementation
1160//
1161
1162LoopInfoWrapperPass::LoopInfoWrapperPass() : FunctionPass(ID) {
1163 initializeLoopInfoWrapperPassPass(*PassRegistry::getPassRegistry());
1164}
1165
1166char LoopInfoWrapperPass::ID = 0;
1167INITIALIZE_PASS_BEGIN(LoopInfoWrapperPass, "loops", "Natural Loop Information",static void *initializeLoopInfoWrapperPassPassOnce(PassRegistry
&Registry) {
1168 true, true)static void *initializeLoopInfoWrapperPassPassOnce(PassRegistry
&Registry) {
1169INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)initializeDominatorTreeWrapperPassPass(Registry);
1170INITIALIZE_PASS_END(LoopInfoWrapperPass, "loops", "Natural Loop Information",PassInfo *PI = new PassInfo( "Natural Loop Information", "loops"
, &LoopInfoWrapperPass::ID, PassInfo::NormalCtor_t(callDefaultCtor
<LoopInfoWrapperPass>), true, true); Registry.registerPass
(*PI, true); return PI; } static llvm::once_flag InitializeLoopInfoWrapperPassPassFlag
; void llvm::initializeLoopInfoWrapperPassPass(PassRegistry &
Registry) { llvm::call_once(InitializeLoopInfoWrapperPassPassFlag
, initializeLoopInfoWrapperPassPassOnce, std::ref(Registry));
}
1171 true, true)PassInfo *PI = new PassInfo( "Natural Loop Information", "loops"
, &LoopInfoWrapperPass::ID, PassInfo::NormalCtor_t(callDefaultCtor
<LoopInfoWrapperPass>), true, true); Registry.registerPass
(*PI, true); return PI; } static llvm::once_flag InitializeLoopInfoWrapperPassPassFlag
; void llvm::initializeLoopInfoWrapperPassPass(PassRegistry &
Registry) { llvm::call_once(InitializeLoopInfoWrapperPassPassFlag
, initializeLoopInfoWrapperPassPassOnce, std::ref(Registry));
}
1172
1173bool LoopInfoWrapperPass::runOnFunction(Function &) {
1174 releaseMemory();
1175 LI.analyze(getAnalysis<DominatorTreeWrapperPass>().getDomTree());
1176 return false;
1177}
1178
1179void LoopInfoWrapperPass::verifyAnalysis() const {
1180 // LoopInfoWrapperPass is a FunctionPass, but verifying every loop in the
1181 // function each time verifyAnalysis is called is very expensive. The
1182 // -verify-loop-info option can enable this. In order to perform some
1183 // checking by default, LoopPass has been taught to call verifyLoop manually
1184 // during loop pass sequences.
1185 if (VerifyLoopInfo) {
1186 auto &DT = getAnalysis<DominatorTreeWrapperPass>().getDomTree();
1187 LI.verify(DT);
1188 }
1189}
1190
1191void LoopInfoWrapperPass::getAnalysisUsage(AnalysisUsage &AU) const {
1192 AU.setPreservesAll();
1193 AU.addRequiredTransitive<DominatorTreeWrapperPass>();
1194}
1195
1196void LoopInfoWrapperPass::print(raw_ostream &OS, const Module *) const {
1197 LI.print(OS);
1198}
1199
1200PreservedAnalyses LoopVerifierPass::run(Function &F,
1201 FunctionAnalysisManager &AM) {
1202 LoopInfo &LI = AM.getResult<LoopAnalysis>(F);
1203 auto &DT = AM.getResult<DominatorTreeAnalysis>(F);
1204 LI.verify(DT);
1205 return PreservedAnalyses::all();
1206}
1207
1208//===----------------------------------------------------------------------===//
1209// LoopBlocksDFS implementation
1210//
1211
1212/// Traverse the loop blocks and store the DFS result.
1213/// Useful for clients that just want the final DFS result and don't need to
1214/// visit blocks during the initial traversal.
1215void LoopBlocksDFS::perform(LoopInfo *LI) {
1216 LoopBlocksTraversal Traversal(*this, LI);
1217 for (LoopBlocksTraversal::POTIterator POI = Traversal.begin(),
1218 POE = Traversal.end();
1219 POI != POE; ++POI)
1220 ;
1221}