Bug Summary

File:src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/lib/Analysis/LoopNestAnalysis.cpp
Warning:line 87, column 56
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 LoopNestAnalysis.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 pic -pic-level 1 -fhalf-no-semantic-interposition -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" -D PIC -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 -D_RET_PROTECTOR -ret-protector -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/LoopNestAnalysis.cpp

/usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/lib/Analysis/LoopNestAnalysis.cpp

→
1//===- LoopNestAnalysis.cpp - Loop Nest Analysis --------------------------==//
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/// \file
10/// The implementation for the loop nest analysis.
11///
12//===----------------------------------------------------------------------===//
13
14#include "llvm/Analysis/LoopNestAnalysis.h"
15#include "llvm/ADT/BreadthFirstIterator.h"
16#include "llvm/ADT/Statistic.h"
17#include "llvm/Analysis/PostDominators.h"
18#include "llvm/Analysis/ValueTracking.h"
19
20using namespace llvm;
21
22#define DEBUG_TYPE"loopnest" "loopnest"
23#ifndef NDEBUG1
24static const char *VerboseDebug = DEBUG_TYPE"loopnest" "-verbose";
25#endif
26
27/// Determine whether the loops structure violates basic requirements for
28/// perfect nesting:
29/// - the inner loop should be the outer loop's only child
30/// - the outer loop header should 'flow' into the inner loop preheader
31/// or jump around the inner loop to the outer loop latch
32/// - if the inner loop latch exits the inner loop, it should 'flow' into
33/// the outer loop latch.
34/// Returns true if the loop structure satisfies the basic requirements and
35/// false otherwise.
36static bool checkLoopsStructure(const Loop &OuterLoop, const Loop &InnerLoop,
37 ScalarEvolution &SE);
38
39//===----------------------------------------------------------------------===//
40// LoopNest implementation
41//
42
43LoopNest::LoopNest(Loop &Root, ScalarEvolution &SE)
44 : MaxPerfectDepth(getMaxPerfectDepth(Root, SE)) {
45 append_range(Loops, breadth_first(&Root));
46}
47
48std::unique_ptr<LoopNest> LoopNest::getLoopNest(Loop &Root,
49 ScalarEvolution &SE) {
50 return std::make_unique<LoopNest>(Root, SE);
51}
52
53bool LoopNest::arePerfectlyNested(const Loop &OuterLoop, const Loop &InnerLoop,
54 ScalarEvolution &SE) {
55 assert(!OuterLoop.isInnermost() && "Outer loop should have subloops")((void)0);
56 assert(!InnerLoop.isOutermost() && "Inner loop should have a parent")((void)0);
57 LLVM_DEBUG(dbgs() << "Checking whether loop '" << OuterLoop.getName()do { } while (false)
4
←
Loop condition is false. Exiting loop
→
58 << "' and '" << InnerLoop.getName()do { } while (false)
59 << "' are perfectly nested.\n")do { } while (false);
60
61 // Determine whether the loops structure satisfies the following requirements:
62 // - the inner loop should be the outer loop's only child
63 // - the outer loop header should 'flow' into the inner loop preheader
64 // or jump around the inner loop to the outer loop latch
65 // - if the inner loop latch exits the inner loop, it should 'flow' into
66 // the outer loop latch.
67 if (!checkLoopsStructure(OuterLoop, InnerLoop, SE)) {
5
←
Calling 'checkLoopsStructure'
→
21
←
Returning from 'checkLoopsStructure'
→
22
←
Taking false branch
→
68 LLVM_DEBUG(dbgs() << "Not perfectly nested: invalid loop structure.\n")do { } while (false);
69 return false;
70 }
71
72 // Bail out if we cannot retrieve the outer loop bounds.
73 auto OuterLoopLB = OuterLoop.getBounds(SE);
74 if (OuterLoopLB == None) {
23
←
Calling 'operator==<llvm::Loop::LoopBounds>'
→
26
←
Returning from 'operator==<llvm::Loop::LoopBounds>'
→
27
←
Taking false branch
→
75 LLVM_DEBUG(dbgs() << "Cannot compute loop bounds of OuterLoop: "do { } while (false)
76 << OuterLoop << "\n";)do { } while (false);
77 return false;
78 }
79
80 // Identify the outer loop latch comparison instruction.
81 const BasicBlock *Latch = OuterLoop.getLoopLatch();
82 assert(Latch && "Expecting a valid loop latch")((void)0);
83 const BranchInst *BI = dyn_cast<BranchInst>(Latch->getTerminator());
28
←
Assuming the object is not a 'BranchInst'
→
29
←
'BI' initialized to a null pointer value
→
84 assert(BI && BI->isConditional() &&((void)0)
85 "Expecting loop latch terminator to be a branch instruction")((void)0);
86
87 const CmpInst *OuterLoopLatchCmp = dyn_cast<CmpInst>(BI->getCondition());
30
←
Called C++ object pointer is null
88 DEBUG_WITH_TYPE(do { } while (false)
89 VerboseDebug, if (OuterLoopLatchCmp) {do { } while (false)
90 dbgs() << "Outer loop latch compare instruction: " << *OuterLoopLatchCmpdo { } while (false)
91 << "\n";do { } while (false)
92 })do { } while (false);
93
94 // Identify the inner loop guard instruction.
95 BranchInst *InnerGuard = InnerLoop.getLoopGuardBranch();
96 const CmpInst *InnerLoopGuardCmp =
97 (InnerGuard) ? dyn_cast<CmpInst>(InnerGuard->getCondition()) : nullptr;
98
99 DEBUG_WITH_TYPE(do { } while (false)
100 VerboseDebug, if (InnerLoopGuardCmp) {do { } while (false)
101 dbgs() << "Inner loop guard compare instruction: " << *InnerLoopGuardCmpdo { } while (false)
102 << "\n";do { } while (false)
103 })do { } while (false);
104
105 // Determine whether instructions in a basic block are one of:
106 // - the inner loop guard comparison
107 // - the outer loop latch comparison
108 // - the outer loop induction variable increment
109 // - a phi node, a cast or a branch
110 auto containsOnlySafeInstructions = [&](const BasicBlock &BB) {
111 return llvm::all_of(BB, [&](const Instruction &I) {
112 bool isAllowed = isSafeToSpeculativelyExecute(&I) || isa<PHINode>(I) ||
113 isa<BranchInst>(I);
114 if (!isAllowed) {
115 DEBUG_WITH_TYPE(VerboseDebug, {do { } while (false)
116 dbgs() << "Instruction: " << I << "\nin basic block: " << BBdo { } while (false)
117 << " is considered unsafe.\n";do { } while (false)
118 })do { } while (false);
119 return false;
120 }
121
122 // The only binary instruction allowed is the outer loop step instruction,
123 // the only comparison instructions allowed are the inner loop guard
124 // compare instruction and the outer loop latch compare instruction.
125 if ((isa<BinaryOperator>(I) && &I != &OuterLoopLB->getStepInst()) ||
126 (isa<CmpInst>(I) && &I != OuterLoopLatchCmp &&
127 &I != InnerLoopGuardCmp)) {
128 DEBUG_WITH_TYPE(VerboseDebug, {do { } while (false)
129 dbgs() << "Instruction: " << I << "\nin basic block:" << BBdo { } while (false)
130 << "is unsafe.\n";do { } while (false)
131 })do { } while (false);
132 return false;
133 }
134 return true;
135 });
136 };
137
138 // Check the code surrounding the inner loop for instructions that are deemed
139 // unsafe.
140 const BasicBlock *OuterLoopHeader = OuterLoop.getHeader();
141 const BasicBlock *OuterLoopLatch = OuterLoop.getLoopLatch();
142 const BasicBlock *InnerLoopPreHeader = InnerLoop.getLoopPreheader();
143
144 if (!containsOnlySafeInstructions(*OuterLoopHeader) ||
145 !containsOnlySafeInstructions(*OuterLoopLatch) ||
146 (InnerLoopPreHeader != OuterLoopHeader &&
147 !containsOnlySafeInstructions(*InnerLoopPreHeader)) ||
148 !containsOnlySafeInstructions(*InnerLoop.getExitBlock())) {
149 LLVM_DEBUG(dbgs() << "Not perfectly nested: code surrounding inner loop is "do { } while (false)
150 "unsafe\n";)do { } while (false);
151 return false;
152 }
153
154 LLVM_DEBUG(dbgs() << "Loop '" << OuterLoop.getName() << "' and '"do { } while (false)
155 << InnerLoop.getName() << "' are perfectly nested.\n")do { } while (false);
156
157 return true;
158}
159
160SmallVector<LoopVectorTy, 4>
161LoopNest::getPerfectLoops(ScalarEvolution &SE) const {
162 SmallVector<LoopVectorTy, 4> LV;
163 LoopVectorTy PerfectNest;
164
165 for (Loop *L : depth_first(const_cast<Loop *>(Loops.front()))) {
166 if (PerfectNest.empty())
1
Taking false branch
→
167 PerfectNest.push_back(L);
168
169 auto &SubLoops = L->getSubLoops();
170 if (SubLoops.size() == 1 && arePerfectlyNested(*L, *SubLoops.front(), SE)) {
2
←
Assuming the condition is true
→
3
←
Calling 'LoopNest::arePerfectlyNested'
→
171 PerfectNest.push_back(SubLoops.front());
172 } else {
173 LV.push_back(PerfectNest);
174 PerfectNest.clear();
175 }
176 }
177
178 return LV;
179}
180
181unsigned LoopNest::getMaxPerfectDepth(const Loop &Root, ScalarEvolution &SE) {
182 LLVM_DEBUG(dbgs() << "Get maximum perfect depth of loop nest rooted by loop '"do { } while (false)
183 << Root.getName() << "'\n")do { } while (false);
184
185 const Loop *CurrentLoop = &Root;
186 const auto *SubLoops = &CurrentLoop->getSubLoops();
187 unsigned CurrentDepth = 1;
188
189 while (SubLoops->size() == 1) {
190 const Loop *InnerLoop = SubLoops->front();
191 if (!arePerfectlyNested(*CurrentLoop, *InnerLoop, SE)) {
192 LLVM_DEBUG({do { } while (false)
193 dbgs() << "Not a perfect nest: loop '" << CurrentLoop->getName()do { } while (false)
194 << "' is not perfectly nested with loop '"do { } while (false)
195 << InnerLoop->getName() << "'\n";do { } while (false)
196 })do { } while (false);
197 break;
198 }
199
200 CurrentLoop = InnerLoop;
201 SubLoops = &CurrentLoop->getSubLoops();
202 ++CurrentDepth;
203 }
204
205 return CurrentDepth;
206}
207
208const BasicBlock &LoopNest::skipEmptyBlockUntil(const BasicBlock *From,
209 const BasicBlock *End,
210 bool CheckUniquePred) {
211 assert(From && "Expecting valid From")((void)0);
212 assert(End && "Expecting valid End")((void)0);
213
214 if (From == End || !From->getUniqueSuccessor())
215 return *From;
216
217 auto IsEmpty = [](const BasicBlock *BB) {
218 return (BB->getInstList().size() == 1);
219 };
220
221 // Visited is used to avoid running into an infinite loop.
222 SmallPtrSet<const BasicBlock *, 4> Visited;
223 const BasicBlock *BB = From->getUniqueSuccessor();
224 const BasicBlock *PredBB = From;
225 while (BB && BB != End && IsEmpty(BB) && !Visited.count(BB) &&
226 (!CheckUniquePred || BB->getUniquePredecessor())) {
227 Visited.insert(BB);
228 PredBB = BB;
229 BB = BB->getUniqueSuccessor();
230 }
231
232 return (BB == End) ? *End : *PredBB;
233}
234
235static bool checkLoopsStructure(const Loop &OuterLoop, const Loop &InnerLoop,
236 ScalarEvolution &SE) {
237 // The inner loop must be the only outer loop's child.
238 if ((OuterLoop.getSubLoops().size() != 1) ||
6
←
Assuming the condition is false
→
8
←
Taking false branch
→
239 (InnerLoop.getParentLoop() != &OuterLoop))
7
←
Assuming the condition is false
→
240 return false;
241
242 // We expect loops in normal form which have a preheader, header, latch...
243 if (!OuterLoop.isLoopSimplifyForm() || !InnerLoop.isLoopSimplifyForm())
9
←
Assuming the condition is false
→
10
←
Assuming the condition is false
→
11
←
Taking false branch
→
244 return false;
245
246 const BasicBlock *OuterLoopHeader = OuterLoop.getHeader();
247 const BasicBlock *OuterLoopLatch = OuterLoop.getLoopLatch();
248 const BasicBlock *InnerLoopPreHeader = InnerLoop.getLoopPreheader();
249 const BasicBlock *InnerLoopLatch = InnerLoop.getLoopLatch();
250 const BasicBlock *InnerLoopExit = InnerLoop.getExitBlock();
251
252 // We expect rotated loops. The inner loop should have a single exit block.
253 if (OuterLoop.getExitingBlock() != OuterLoopLatch ||
12
←
Assuming the condition is false
→
15
←
Taking false branch
→
254 InnerLoop.getExitingBlock() != InnerLoopLatch || !InnerLoopExit)
13
←
Assuming the condition is false
→
14
←
Assuming 'InnerLoopExit' is non-null, which participates in a condition later
→
255 return false;
256
257 // Returns whether the block `ExitBlock` contains at least one LCSSA Phi node.
258 auto ContainsLCSSAPhi = [](const BasicBlock &ExitBlock) {
259 return any_of(ExitBlock.phis(), [](const PHINode &PN) {
260 return PN.getNumIncomingValues() == 1;
261 });
262 };
263
264 // Returns whether the block `BB` qualifies for being an extra Phi block. The
265 // extra Phi block is the additional block inserted after the exit block of an
266 // "guarded" inner loop which contains "only" Phi nodes corresponding to the
267 // LCSSA Phi nodes in the exit block.
268 auto IsExtraPhiBlock = [&](const BasicBlock &BB) {
269 return BB.getFirstNonPHI() == BB.getTerminator() &&
270 all_of(BB.phis(), [&](const PHINode &PN) {
271 return all_of(PN.blocks(), [&](const BasicBlock *IncomingBlock) {
272 return IncomingBlock == InnerLoopExit ||
273 IncomingBlock == OuterLoopHeader;
274 });
275 });
276 };
277
278 const BasicBlock *ExtraPhiBlock = nullptr;
279 // Ensure the only branch that may exist between the loops is the inner loop
280 // guard.
281 if (OuterLoopHeader != InnerLoopPreHeader) {
16
←
Assuming 'OuterLoopHeader' is equal to 'InnerLoopPreHeader'
→
17
←
Taking false branch
→
282 const BasicBlock &SingleSucc =
283 LoopNest::skipEmptyBlockUntil(OuterLoopHeader, InnerLoopPreHeader);
284
285 // no conditional branch present
286 if (&SingleSucc != InnerLoopPreHeader) {
287 const BranchInst *BI = dyn_cast<BranchInst>(SingleSucc.getTerminator());
288
289 if (!BI || BI != InnerLoop.getLoopGuardBranch())
290 return false;
291
292 bool InnerLoopExitContainsLCSSA = ContainsLCSSAPhi(*InnerLoopExit);
293
294 // The successors of the inner loop guard should be the inner loop
295 // preheader or the outer loop latch possibly through empty blocks.
296 for (const BasicBlock *Succ : BI->successors()) {
297 const BasicBlock *PotentialInnerPreHeader = Succ;
298 const BasicBlock *PotentialOuterLatch = Succ;
299
300 // Ensure the inner loop guard successor is empty before skipping
301 // blocks.
302 if (Succ->getInstList().size() == 1) {
303 PotentialInnerPreHeader =
304 &LoopNest::skipEmptyBlockUntil(Succ, InnerLoopPreHeader);
305 PotentialOuterLatch =
306 &LoopNest::skipEmptyBlockUntil(Succ, OuterLoopLatch);
307 }
308
309 if (PotentialInnerPreHeader == InnerLoopPreHeader)
310 continue;
311 if (PotentialOuterLatch == OuterLoopLatch)
312 continue;
313
314 // If `InnerLoopExit` contains LCSSA Phi instructions, additional block
315 // may be inserted before the `OuterLoopLatch` to which `BI` jumps. The
316 // loops are still considered perfectly nested if the extra block only
317 // contains Phi instructions from InnerLoopExit and OuterLoopHeader.
318 if (InnerLoopExitContainsLCSSA && IsExtraPhiBlock(*Succ) &&
319 Succ->getSingleSuccessor() == OuterLoopLatch) {
320 // Points to the extra block so that we can reference it later in the
321 // final check. We can also conclude that the inner loop is
322 // guarded and there exists LCSSA Phi node in the exit block later if
323 // we see a non-null `ExtraPhiBlock`.
324 ExtraPhiBlock = Succ;
325 continue;
326 }
327
328 DEBUG_WITH_TYPE(VerboseDebug, {do { } while (false)
329 dbgs() << "Inner loop guard successor " << Succ->getName()do { } while (false)
330 << " doesn't lead to inner loop preheader or "do { } while (false)
331 "outer loop latch.\n";do { } while (false)
332 })do { } while (false);
333 return false;
334 }
335 }
336 }
337
338 // Ensure the inner loop exit block lead to the outer loop latch possibly
339 // through empty blocks.
340 if ((!ExtraPhiBlock
17.1
'ExtraPhiBlock' is null
17.1
'ExtraPhiBlock' is null
 ||
19
←
Taking false branch
→
341 &LoopNest::skipEmptyBlockUntil(InnerLoop.getExitBlock(),
342 ExtraPhiBlock) != ExtraPhiBlock) &&
343 (&LoopNest::skipEmptyBlockUntil(InnerLoop.getExitBlock(),
18
←
Assuming the condition is false
→
344 OuterLoopLatch) != OuterLoopLatch)) {
345 DEBUG_WITH_TYPE(do { } while (false)
346 VerboseDebug,do { } while (false)
347 dbgs() << "Inner loop exit block " << *InnerLoopExitdo { } while (false)
348 << " does not directly lead to the outer loop latch.\n";)do { } while (false);
349 return false;
350 }
351
352 return true;
20
←
Returning the value 1, which participates in a condition later
→
353}
354
355AnalysisKey LoopNestAnalysis::Key;
356
357raw_ostream &llvm::operator<<(raw_ostream &OS, const LoopNest &LN) {
358 OS << "IsPerfect=";
359 if (LN.getMaxPerfectDepth() == LN.getNestDepth())
360 OS << "true";
361 else
362 OS << "false";
363 OS << ", Depth=" << LN.getNestDepth();
364 OS << ", OutermostLoop: " << LN.getOutermostLoop().getName();
365 OS << ", Loops: ( ";
366 for (const Loop *L : LN.getLoops())
367 OS << L->getName() << " ";
368 OS << ")";
369
370 return OS;
371}
372
373//===----------------------------------------------------------------------===//
374// LoopNestPrinterPass implementation
375//
376
377PreservedAnalyses LoopNestPrinterPass::run(Loop &L, LoopAnalysisManager &AM,
378 LoopStandardAnalysisResults &AR,
379 LPMUpdater &U) {
380 if (auto LN = LoopNest::getLoopNest(L, AR.SE))
381 OS << *LN << "\n";
382
383 return PreservedAnalyses::all();
384}
←

/usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/ADT/Optional.h

1//===- Optional.h - Simple variant for passing optional values --*- C++ -*-===//
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 provides Optional, a template class modeled in the spirit of
10// OCaml's 'opt' variant. The idea is to strongly type whether or not
11// a value can be optional.
12//
13//===----------------------------------------------------------------------===//
14
15#ifndef LLVM_ADT_OPTIONAL_H
16#define LLVM_ADT_OPTIONAL_H
17
18#include "llvm/ADT/Hashing.h"
19#include "llvm/ADT/None.h"
20#include "llvm/ADT/STLForwardCompat.h"
21#include "llvm/Support/Compiler.h"
22#include "llvm/Support/type_traits.h"
23#include <cassert>
24#include <memory>
25#include <new>
26#include <utility>
27
28namespace llvm {
29
30class raw_ostream;
31
32namespace optional_detail {
33
34/// Storage for any type.
35//
36// The specialization condition intentionally uses
37// llvm::is_trivially_copy_constructible instead of
38// std::is_trivially_copy_constructible. GCC versions prior to 7.4 may
39// instantiate the copy constructor of `T` when
40// std::is_trivially_copy_constructible is instantiated. This causes
41// compilation to fail if we query the trivially copy constructible property of
42// a class which is not copy constructible.
43//
44// The current implementation of OptionalStorage insists that in order to use
45// the trivial specialization, the value_type must be trivially copy
46// constructible and trivially copy assignable due to =default implementations
47// of the copy/move constructor/assignment. It does not follow that this is
48// necessarily the case std::is_trivially_copyable is true (hence the expanded
49// specialization condition).
50//
51// The move constructible / assignable conditions emulate the remaining behavior
52// of std::is_trivially_copyable.
53template <typename T, bool = (llvm::is_trivially_copy_constructible<T>::value &&
54 std::is_trivially_copy_assignable<T>::value &&
55 (std::is_trivially_move_constructible<T>::value ||
56 !std::is_move_constructible<T>::value) &&
57 (std::is_trivially_move_assignable<T>::value ||
58 !std::is_move_assignable<T>::value))>
59class OptionalStorage {
60 union {
61 char empty;
62 T value;
63 };
64 bool hasVal;
65
66public:
67 ~OptionalStorage() { reset(); }
68
69 constexpr OptionalStorage() noexcept : empty(), hasVal(false) {}
70
71 constexpr OptionalStorage(OptionalStorage const &other) : OptionalStorage() {
72 if (other.hasValue()) {
73 emplace(other.value);
74 }
75 }
76 constexpr OptionalStorage(OptionalStorage &&other) : OptionalStorage() {
77 if (other.hasValue()) {
78 emplace(std::move(other.value));
79 }
80 }
81
82 template <class... Args>
83 constexpr explicit OptionalStorage(in_place_t, Args &&... args)
84 : value(std::forward<Args>(args)...), hasVal(true) {}
85
86 void reset() noexcept {
87 if (hasVal) {
88 value.~T();
89 hasVal = false;
90 }
91 }
92
93 constexpr bool hasValue() const noexcept { return hasVal; }
94
95 T &getValue() LLVM_LVALUE_FUNCTION& noexcept {
96 assert(hasVal)((void)0);
97 return value;
98 }
99 constexpr T const &getValue() const LLVM_LVALUE_FUNCTION& noexcept {
100 assert(hasVal)((void)0);
101 return value;
102 }
103#if LLVM_HAS_RVALUE_REFERENCE_THIS1
104 T &&getValue() && noexcept {
105 assert(hasVal)((void)0);
106 return std::move(value);
107 }
108#endif
109
110 template <class... Args> void emplace(Args &&... args) {
111 reset();
112 ::new ((void *)std::addressof(value)) T(std::forward<Args>(args)...);
113 hasVal = true;
114 }
115
116 OptionalStorage &operator=(T const &y) {
117 if (hasValue()) {
118 value = y;
119 } else {
120 ::new ((void *)std::addressof(value)) T(y);
121 hasVal = true;
122 }
123 return *this;
124 }
125 OptionalStorage &operator=(T &&y) {
126 if (hasValue()) {
127 value = std::move(y);
128 } else {
129 ::new ((void *)std::addressof(value)) T(std::move(y));
130 hasVal = true;
131 }
132 return *this;
133 }
134
135 OptionalStorage &operator=(OptionalStorage const &other) {
136 if (other.hasValue()) {
137 if (hasValue()) {
138 value = other.value;
139 } else {
140 ::new ((void *)std::addressof(value)) T(other.value);
141 hasVal = true;
142 }
143 } else {
144 reset();
145 }
146 return *this;
147 }
148
149 OptionalStorage &operator=(OptionalStorage &&other) {
150 if (other.hasValue()) {
151 if (hasValue()) {
152 value = std::move(other.value);
153 } else {
154 ::new ((void *)std::addressof(value)) T(std::move(other.value));
155 hasVal = true;
156 }
157 } else {
158 reset();
159 }
160 return *this;
161 }
162};
163
164template <typename T> class OptionalStorage<T, true> {
165 union {
166 char empty;
167 T value;
168 };
169 bool hasVal = false;
170
171public:
172 ~OptionalStorage() = default;
173
174 constexpr OptionalStorage() noexcept : empty{} {}
175
176 constexpr OptionalStorage(OptionalStorage const &other) = default;
177 constexpr OptionalStorage(OptionalStorage &&other) = default;
178
179 OptionalStorage &operator=(OptionalStorage const &other) = default;
180 OptionalStorage &operator=(OptionalStorage &&other) = default;
181
182 template <class... Args>
183 constexpr explicit OptionalStorage(in_place_t, Args &&... args)
184 : value(std::forward<Args>(args)...), hasVal(true) {}
185
186 void reset() noexcept {
187 if (hasVal) {
188 value.~T();
189 hasVal = false;
190 }
191 }
192
193 constexpr bool hasValue() const noexcept { return hasVal; }
194
195 T &getValue() LLVM_LVALUE_FUNCTION& noexcept {
196 assert(hasVal)((void)0);
197 return value;
198 }
199 constexpr T const &getValue() const LLVM_LVALUE_FUNCTION& noexcept {
200 assert(hasVal)((void)0);
201 return value;
202 }
203#if LLVM_HAS_RVALUE_REFERENCE_THIS1
204 T &&getValue() && noexcept {
205 assert(hasVal)((void)0);
206 return std::move(value);
207 }
208#endif
209
210 template <class... Args> void emplace(Args &&... args) {
211 reset();
212 ::new ((void *)std::addressof(value)) T(std::forward<Args>(args)...);
213 hasVal = true;
214 }
215
216 OptionalStorage &operator=(T const &y) {
217 if (hasValue()) {
218 value = y;
219 } else {
220 ::new ((void *)std::addressof(value)) T(y);
221 hasVal = true;
222 }
223 return *this;
224 }
225 OptionalStorage &operator=(T &&y) {
226 if (hasValue()) {
227 value = std::move(y);
228 } else {
229 ::new ((void *)std::addressof(value)) T(std::move(y));
230 hasVal = true;
231 }
232 return *this;
233 }
234};
235
236} // namespace optional_detail
237
238template <typename T> class Optional {
239 optional_detail::OptionalStorage<T> Storage;
240
241public:
242 using value_type = T;
243
244 constexpr Optional() {}
245 constexpr Optional(NoneType) {}
246
247 constexpr Optional(const T &y) : Storage(in_place, y) {}
248 constexpr Optional(const Optional &O) = default;
249
250 constexpr Optional(T &&y) : Storage(in_place, std::move(y)) {}
251 constexpr Optional(Optional &&O) = default;
252
253 template <typename... ArgTypes>
254 constexpr Optional(in_place_t, ArgTypes &&...Args)
255 : Storage(in_place, std::forward<ArgTypes>(Args)...) {}
256
257 Optional &operator=(T &&y) {
258 Storage = std::move(y);
259 return *this;
260 }
261 Optional &operator=(Optional &&O) = default;
262
263 /// Create a new object by constructing it in place with the given arguments.
264 template <typename... ArgTypes> void emplace(ArgTypes &&... Args) {
265 Storage.emplace(std::forward<ArgTypes>(Args)...);
266 }
267
268 static constexpr Optional create(const T *y) {
269 return y ? Optional(*y) : Optional();
270 }
271
272 Optional &operator=(const T &y) {
273 Storage = y;
274 return *this;
275 }
276 Optional &operator=(const Optional &O) = default;
277
278 void reset() { Storage.reset(); }
279
280 constexpr const T *getPointer() const { return &Storage.getValue(); }
281 T *getPointer() { return &Storage.getValue(); }
282 constexpr const T &getValue() const LLVM_LVALUE_FUNCTION& {
283 return Storage.getValue();
284 }
285 T &getValue() LLVM_LVALUE_FUNCTION& { return Storage.getValue(); }
286
287 constexpr explicit operator bool() const { return hasValue(); }
288 constexpr bool hasValue() const { return Storage.hasValue(); }
289 constexpr const T *operator->() const { return getPointer(); }
290 T *operator->() { return getPointer(); }
291 constexpr const T &operator*() const LLVM_LVALUE_FUNCTION& {
292 return getValue();
293 }
294 T &operator*() LLVM_LVALUE_FUNCTION& { return getValue(); }
295
296 template <typename U>
297 constexpr T getValueOr(U &&value) const LLVM_LVALUE_FUNCTION& {
298 return hasValue() ? getValue() : std::forward<U>(value);
299 }
300
301 /// Apply a function to the value if present; otherwise return None.
302 template <class Function>
303 auto map(const Function &F) const LLVM_LVALUE_FUNCTION&
304 -> Optional<decltype(F(getValue()))> {
305 if (*this) return F(getValue());
306 return None;
307 }
308
309#if LLVM_HAS_RVALUE_REFERENCE_THIS1
310 T &&getValue() && { return std::move(Storage.getValue()); }
311 T &&operator*() && { return std::move(Storage.getValue()); }
312
313 template <typename U>
314 T getValueOr(U &&value) && {
315 return hasValue() ? std::move(getValue()) : std::forward<U>(value);
316 }
317
318 /// Apply a function to the value if present; otherwise return None.
319 template <class Function>
320 auto map(const Function &F) &&
321 -> Optional<decltype(F(std::move(*this).getValue()))> {
322 if (*this) return F(std::move(*this).getValue());
323 return None;
324 }
325#endif
326};
327
328template <class T> llvm::hash_code hash_value(const Optional<T> &O) {
329 return O ? hash_combine(true, *O) : hash_value(false);
330}
331
332template <typename T, typename U>
333constexpr bool operator==(const Optional<T> &X, const Optional<U> &Y) {
334 if (X && Y)
335 return *X == *Y;
336 return X.hasValue() == Y.hasValue();
337}
338
339template <typename T, typename U>
340constexpr bool operator!=(const Optional<T> &X, const Optional<U> &Y) {
341 return !(X == Y);
342}
343
344template <typename T, typename U>
345constexpr bool operator<(const Optional<T> &X, const Optional<U> &Y) {
346 if (X && Y)
347 return *X < *Y;
348 return X.hasValue() < Y.hasValue();
349}
350
351template <typename T, typename U>
352constexpr bool operator<=(const Optional<T> &X, const Optional<U> &Y) {
353 return !(Y < X);
354}
355
356template <typename T, typename U>
357constexpr bool operator>(const Optional<T> &X, const Optional<U> &Y) {
358 return Y < X;
359}
360
361template <typename T, typename U>
362constexpr bool operator>=(const Optional<T> &X, const Optional<U> &Y) {
363 return !(X < Y);
364}
365
366template <typename T>
367constexpr bool operator==(const Optional<T> &X, NoneType) {
368 return !X;
24
←
Assuming the condition is false
→
25
←
Returning zero, which participates in a condition later
→
369}
370
371template <typename T>
372constexpr bool operator==(NoneType, const Optional<T> &X) {
373 return X == None;
374}
375
376template <typename T>
377constexpr bool operator!=(const Optional<T> &X, NoneType) {
378 return !(X == None);
379}
380
381template <typename T>
382constexpr bool operator!=(NoneType, const Optional<T> &X) {
383 return X != None;
384}
385
386template <typename T> constexpr bool operator<(const Optional<T> &, NoneType) {
387 return false;
388}
389
390template <typename T> constexpr bool operator<(NoneType, const Optional<T> &X) {
391 return X.hasValue();
392}
393
394template <typename T>
395constexpr bool operator<=(const Optional<T> &X, NoneType) {
396 return !(None < X);
397}
398
399template <typename T>
400constexpr bool operator<=(NoneType, const Optional<T> &X) {
401 return !(X < None);
402}
403
404template <typename T> constexpr bool operator>(const Optional<T> &X, NoneType) {
405 return None < X;
406}
407
408template <typename T> constexpr bool operator>(NoneType, const Optional<T> &X) {
409 return X < None;
410}
411
412template <typename T>
413constexpr bool operator>=(const Optional<T> &X, NoneType) {
414 return None <= X;
415}
416
417template <typename T>
418constexpr bool operator>=(NoneType, const Optional<T> &X) {
419 return X <= None;
420}
421
422template <typename T>
423constexpr bool operator==(const Optional<T> &X, const T &Y) {
424 return X && *X == Y;
425}
426
427template <typename T>
428constexpr bool operator==(const T &X, const Optional<T> &Y) {
429 return Y && X == *Y;
430}
431
432template <typename T>
433constexpr bool operator!=(const Optional<T> &X, const T &Y) {
434 return !(X == Y);
435}
436
437template <typename T>
438constexpr bool operator!=(const T &X, const Optional<T> &Y) {
439 return !(X == Y);
440}
441
442template <typename T>
443constexpr bool operator<(const Optional<T> &X, const T &Y) {
444 return !X || *X < Y;
445}
446
447template <typename T>
448constexpr bool operator<(const T &X, const Optional<T> &Y) {
449 return Y && X < *Y;
450}
451
452template <typename T>
453constexpr bool operator<=(const Optional<T> &X, const T &Y) {
454 return !(Y < X);
455}
456
457template <typename T>
458constexpr bool operator<=(const T &X, const Optional<T> &Y) {
459 return !(Y < X);
460}
461
462template <typename T>
463constexpr bool operator>(const Optional<T> &X, const T &Y) {
464 return Y < X;
465}
466
467template <typename T>
468constexpr bool operator>(const T &X, const Optional<T> &Y) {
469 return Y < X;
470}
471
472template <typename T>
473constexpr bool operator>=(const Optional<T> &X, const T &Y) {
474 return !(X < Y);
475}
476
477template <typename T>
478constexpr bool operator>=(const T &X, const Optional<T> &Y) {
479 return !(X < Y);
480}
481
482raw_ostream &operator<<(raw_ostream &OS, NoneType);
483
484template <typename T, typename = decltype(std::declval<raw_ostream &>()
485 << std::declval<const T &>())>
486raw_ostream &operator<<(raw_ostream &OS, const Optional<T> &O) {
487 if (O)
488 OS << *O;
489 else
490 OS << None;
491 return OS;
492}
493
494} // end namespace llvm
495
496#endif // LLVM_ADT_OPTIONAL_H