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 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/LoopNestAnalysis.cpp
1 | |
2 | |
3 | |
4 | |
5 | |
6 | |
7 | |
8 | |
9 | |
10 | |
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 | |
20 | using namespace llvm; |
21 | |
22 | #define DEBUG_TYPE "loopnest" |
23 | #ifndef NDEBUG |
24 | static const char *VerboseDebug = DEBUG_TYPE "-verbose"; |
25 | #endif |
26 | |
27 | |
28 | |
29 | |
30 | |
31 | |
32 | |
33 | |
34 | |
35 | |
36 | static bool checkLoopsStructure(const Loop &OuterLoop, const Loop &InnerLoop, |
37 | ScalarEvolution &SE); |
38 | |
39 | |
40 | |
41 | |
42 | |
43 | LoopNest::LoopNest(Loop &Root, ScalarEvolution &SE) |
44 | : MaxPerfectDepth(getMaxPerfectDepth(Root, SE)) { |
45 | append_range(Loops, breadth_first(&Root)); |
46 | } |
47 | |
48 | std::unique_ptr<LoopNest> LoopNest::getLoopNest(Loop &Root, |
49 | ScalarEvolution &SE) { |
50 | return std::make_unique<LoopNest>(Root, SE); |
51 | } |
52 | |
53 | bool LoopNest::arePerfectlyNested(const Loop &OuterLoop, const Loop &InnerLoop, |
54 | ScalarEvolution &SE) { |
55 | assert(!OuterLoop.isInnermost() && "Outer loop should have subloops"); |
56 | assert(!InnerLoop.isOutermost() && "Inner loop should have a parent"); |
57 | LLVM_DEBUG(dbgs() << "Checking whether loop '" << OuterLoop.getName() |
| 4 | | Loop condition is false. Exiting loop | |
|
58 | << "' and '" << InnerLoop.getName() |
59 | << "' are perfectly nested.\n"); |
60 | |
61 | |
62 | |
63 | |
64 | |
65 | |
66 | |
67 | if (!checkLoopsStructure(OuterLoop, InnerLoop, SE)) { |
| 5 | | Calling 'checkLoopsStructure' | |
|
| 21 | | Returning from 'checkLoopsStructure' | |
|
| |
68 | LLVM_DEBUG(dbgs() << "Not perfectly nested: invalid loop structure.\n"); |
69 | return false; |
70 | } |
71 | |
72 | |
73 | auto OuterLoopLB = OuterLoop.getBounds(SE); |
74 | if (OuterLoopLB == None) { |
| 23 | | Calling 'operator==<llvm::Loop::LoopBounds>' | |
|
| 26 | | Returning from 'operator==<llvm::Loop::LoopBounds>' | |
|
| |
75 | LLVM_DEBUG(dbgs() << "Cannot compute loop bounds of OuterLoop: " |
76 | << OuterLoop << "\n";); |
77 | return false; |
78 | } |
79 | |
80 | |
81 | const BasicBlock *Latch = OuterLoop.getLoopLatch(); |
82 | assert(Latch && "Expecting a valid loop latch"); |
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() && |
85 | "Expecting loop latch terminator to be a branch instruction"); |
86 | |
87 | const CmpInst *OuterLoopLatchCmp = dyn_cast<CmpInst>(BI->getCondition()); |
| 30 | | Called C++ object pointer is null |
|
88 | DEBUG_WITH_TYPE( |
89 | VerboseDebug, if (OuterLoopLatchCmp) { |
90 | dbgs() << "Outer loop latch compare instruction: " << *OuterLoopLatchCmp |
91 | << "\n"; |
92 | }); |
93 | |
94 | |
95 | BranchInst *InnerGuard = InnerLoop.getLoopGuardBranch(); |
96 | const CmpInst *InnerLoopGuardCmp = |
97 | (InnerGuard) ? dyn_cast<CmpInst>(InnerGuard->getCondition()) : nullptr; |
98 | |
99 | DEBUG_WITH_TYPE( |
100 | VerboseDebug, if (InnerLoopGuardCmp) { |
101 | dbgs() << "Inner loop guard compare instruction: " << *InnerLoopGuardCmp |
102 | << "\n"; |
103 | }); |
104 | |
105 | |
106 | |
107 | |
108 | |
109 | |
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, { |
116 | dbgs() << "Instruction: " << I << "\nin basic block: " << BB |
117 | << " is considered unsafe.\n"; |
118 | }); |
119 | return false; |
120 | } |
121 | |
122 | |
123 | |
124 | |
125 | if ((isa<BinaryOperator>(I) && &I != &OuterLoopLB->getStepInst()) || |
126 | (isa<CmpInst>(I) && &I != OuterLoopLatchCmp && |
127 | &I != InnerLoopGuardCmp)) { |
128 | DEBUG_WITH_TYPE(VerboseDebug, { |
129 | dbgs() << "Instruction: " << I << "\nin basic block:" << BB |
130 | << "is unsafe.\n"; |
131 | }); |
132 | return false; |
133 | } |
134 | return true; |
135 | }); |
136 | }; |
137 | |
138 | |
139 | |
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 " |
150 | "unsafe\n";); |
151 | return false; |
152 | } |
153 | |
154 | LLVM_DEBUG(dbgs() << "Loop '" << OuterLoop.getName() << "' and '" |
155 | << InnerLoop.getName() << "' are perfectly nested.\n"); |
156 | |
157 | return true; |
158 | } |
159 | |
160 | SmallVector<LoopVectorTy, 4> |
161 | LoopNest::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()) |
| |
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 | |
181 | unsigned LoopNest::getMaxPerfectDepth(const Loop &Root, ScalarEvolution &SE) { |
182 | LLVM_DEBUG(dbgs() << "Get maximum perfect depth of loop nest rooted by loop '" |
183 | << Root.getName() << "'\n"); |
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({ |
193 | dbgs() << "Not a perfect nest: loop '" << CurrentLoop->getName() |
194 | << "' is not perfectly nested with loop '" |
195 | << InnerLoop->getName() << "'\n"; |
196 | }); |
197 | break; |
198 | } |
199 | |
200 | CurrentLoop = InnerLoop; |
201 | SubLoops = &CurrentLoop->getSubLoops(); |
202 | ++CurrentDepth; |
203 | } |
204 | |
205 | return CurrentDepth; |
206 | } |
207 | |
208 | const BasicBlock &LoopNest::skipEmptyBlockUntil(const BasicBlock *From, |
209 | const BasicBlock *End, |
210 | bool CheckUniquePred) { |
211 | assert(From && "Expecting valid From"); |
212 | assert(End && "Expecting valid End"); |
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 | |
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 | |
235 | static bool checkLoopsStructure(const Loop &OuterLoop, const Loop &InnerLoop, |
236 | ScalarEvolution &SE) { |
237 | |
238 | if ((OuterLoop.getSubLoops().size() != 1) || |
| 6 | | Assuming the condition is false | |
|
| |
239 | (InnerLoop.getParentLoop() != &OuterLoop)) |
| 7 | | Assuming the condition is false | |
|
240 | return false; |
241 | |
242 | |
243 | if (!OuterLoop.isLoopSimplifyForm() || !InnerLoop.isLoopSimplifyForm()) |
| 9 | | Assuming the condition is false | |
|
| 10 | | Assuming the condition is false | |
|
| |
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 | |
253 | if (OuterLoop.getExitingBlock() != OuterLoopLatch || |
| 12 | | Assuming the condition is false | |
|
| |
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 | |
258 | auto ContainsLCSSAPhi = [](const BasicBlock &ExitBlock) { |
259 | return any_of(ExitBlock.phis(), [](const PHINode &PN) { |
260 | return PN.getNumIncomingValues() == 1; |
261 | }); |
262 | }; |
263 | |
264 | |
265 | |
266 | |
267 | |
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 | |
280 | |
281 | if (OuterLoopHeader != InnerLoopPreHeader) { |
| 16 | | Assuming 'OuterLoopHeader' is equal to 'InnerLoopPreHeader' | |
|
| |
282 | const BasicBlock &SingleSucc = |
283 | LoopNest::skipEmptyBlockUntil(OuterLoopHeader, InnerLoopPreHeader); |
284 | |
285 | |
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 | |
295 | |
296 | for (const BasicBlock *Succ : BI->successors()) { |
297 | const BasicBlock *PotentialInnerPreHeader = Succ; |
298 | const BasicBlock *PotentialOuterLatch = Succ; |
299 | |
300 | |
301 | |
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 | |
315 | |
316 | |
317 | |
318 | if (InnerLoopExitContainsLCSSA && IsExtraPhiBlock(*Succ) && |
319 | Succ->getSingleSuccessor() == OuterLoopLatch) { |
320 | |
321 | |
322 | |
323 | |
324 | ExtraPhiBlock = Succ; |
325 | continue; |
326 | } |
327 | |
328 | DEBUG_WITH_TYPE(VerboseDebug, { |
329 | dbgs() << "Inner loop guard successor " << Succ->getName() |
330 | << " doesn't lead to inner loop preheader or " |
331 | "outer loop latch.\n"; |
332 | }); |
333 | return false; |
334 | } |
335 | } |
336 | } |
337 | |
338 | |
339 | |
340 | if ((!ExtraPhiBlock || |
| |
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( |
346 | VerboseDebug, |
347 | dbgs() << "Inner loop exit block " << *InnerLoopExit |
348 | << " does not directly lead to the outer loop latch.\n";); |
349 | return false; |
350 | } |
351 | |
352 | return true; |
| 20 | | Returning the value 1, which participates in a condition later | |
|
353 | } |
354 | |
355 | AnalysisKey LoopNestAnalysis::Key; |
356 | |
357 | raw_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 | |
375 | |
376 | |
377 | PreservedAnalyses 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 | } |
1 | |
2 | |
3 | |
4 | |
5 | |
6 | |
7 | |
8 | |
9 | |
10 | |
11 | |
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 | |
28 | namespace llvm { |
29 | |
30 | class raw_ostream; |
31 | |
32 | namespace optional_detail { |
33 | |
34 | |
35 | |
36 | |
37 | |
38 | |
39 | |
40 | |
41 | |
42 | |
43 | |
44 | |
45 | |
46 | |
47 | |
48 | |
49 | |
50 | |
51 | |
52 | |
53 | template <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))> |
59 | class OptionalStorage { |
60 | union { |
61 | char empty; |
62 | T value; |
63 | }; |
64 | bool hasVal; |
65 | |
66 | public: |
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); |
97 | return value; |
98 | } |
99 | constexpr T const &getValue() const LLVM_LVALUE_FUNCTION noexcept { |
100 | assert(hasVal); |
101 | return value; |
102 | } |
103 | #if LLVM_HAS_RVALUE_REFERENCE_THIS |
104 | T &&getValue() && noexcept { |
105 | assert(hasVal); |
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 | |
164 | template <typename T> class OptionalStorage<T, true> { |
165 | union { |
166 | char empty; |
167 | T value; |
168 | }; |
169 | bool hasVal = false; |
170 | |
171 | public: |
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); |
197 | return value; |
198 | } |
199 | constexpr T const &getValue() const LLVM_LVALUE_FUNCTION noexcept { |
200 | assert(hasVal); |
201 | return value; |
202 | } |
203 | #if LLVM_HAS_RVALUE_REFERENCE_THIS |
204 | T &&getValue() && noexcept { |
205 | assert(hasVal); |
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 | } |
237 | |
238 | template <typename T> class Optional { |
239 | optional_detail::OptionalStorage<T> Storage; |
240 | |
241 | public: |
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 | |
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 | |
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_THIS |
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 | |
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 | |
328 | template <class T> llvm::hash_code hash_value(const Optional<T> &O) { |
329 | return O ? hash_combine(true, *O) : hash_value(false); |
330 | } |
331 | |
332 | template <typename T, typename U> |
333 | constexpr 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 | |
339 | template <typename T, typename U> |
340 | constexpr bool operator!=(const Optional<T> &X, const Optional<U> &Y) { |
341 | return !(X == Y); |
342 | } |
343 | |
344 | template <typename T, typename U> |
345 | constexpr 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 | |
351 | template <typename T, typename U> |
352 | constexpr bool operator<=(const Optional<T> &X, const Optional<U> &Y) { |
353 | return !(Y < X); |
354 | } |
355 | |
356 | template <typename T, typename U> |
357 | constexpr bool operator>(const Optional<T> &X, const Optional<U> &Y) { |
358 | return Y < X; |
359 | } |
360 | |
361 | template <typename T, typename U> |
362 | constexpr bool operator>=(const Optional<T> &X, const Optional<U> &Y) { |
363 | return !(X < Y); |
364 | } |
365 | |
366 | template <typename T> |
367 | constexpr 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 | |
371 | template <typename T> |
372 | constexpr bool operator==(NoneType, const Optional<T> &X) { |
373 | return X == None; |
374 | } |
375 | |
376 | template <typename T> |
377 | constexpr bool operator!=(const Optional<T> &X, NoneType) { |
378 | return !(X == None); |
379 | } |
380 | |
381 | template <typename T> |
382 | constexpr bool operator!=(NoneType, const Optional<T> &X) { |
383 | return X != None; |
384 | } |
385 | |
386 | template <typename T> constexpr bool operator<(const Optional<T> &, NoneType) { |
387 | return false; |
388 | } |
389 | |
390 | template <typename T> constexpr bool operator<(NoneType, const Optional<T> &X) { |
391 | return X.hasValue(); |
392 | } |
393 | |
394 | template <typename T> |
395 | constexpr bool operator<=(const Optional<T> &X, NoneType) { |
396 | return !(None < X); |
397 | } |
398 | |
399 | template <typename T> |
400 | constexpr bool operator<=(NoneType, const Optional<T> &X) { |
401 | return !(X < None); |
402 | } |
403 | |
404 | template <typename T> constexpr bool operator>(const Optional<T> &X, NoneType) { |
405 | return None < X; |
406 | } |
407 | |
408 | template <typename T> constexpr bool operator>(NoneType, const Optional<T> &X) { |
409 | return X < None; |
410 | } |
411 | |
412 | template <typename T> |
413 | constexpr bool operator>=(const Optional<T> &X, NoneType) { |
414 | return None <= X; |
415 | } |
416 | |
417 | template <typename T> |
418 | constexpr bool operator>=(NoneType, const Optional<T> &X) { |
419 | return X <= None; |
420 | } |
421 | |
422 | template <typename T> |
423 | constexpr bool operator==(const Optional<T> &X, const T &Y) { |
424 | return X && *X == Y; |
425 | } |
426 | |
427 | template <typename T> |
428 | constexpr bool operator==(const T &X, const Optional<T> &Y) { |
429 | return Y && X == *Y; |
430 | } |
431 | |
432 | template <typename T> |
433 | constexpr bool operator!=(const Optional<T> &X, const T &Y) { |
434 | return !(X == Y); |
435 | } |
436 | |
437 | template <typename T> |
438 | constexpr bool operator!=(const T &X, const Optional<T> &Y) { |
439 | return !(X == Y); |
440 | } |
441 | |
442 | template <typename T> |
443 | constexpr bool operator<(const Optional<T> &X, const T &Y) { |
444 | return !X || *X < Y; |
445 | } |
446 | |
447 | template <typename T> |
448 | constexpr bool operator<(const T &X, const Optional<T> &Y) { |
449 | return Y && X < *Y; |
450 | } |
451 | |
452 | template <typename T> |
453 | constexpr bool operator<=(const Optional<T> &X, const T &Y) { |
454 | return !(Y < X); |
455 | } |
456 | |
457 | template <typename T> |
458 | constexpr bool operator<=(const T &X, const Optional<T> &Y) { |
459 | return !(Y < X); |
460 | } |
461 | |
462 | template <typename T> |
463 | constexpr bool operator>(const Optional<T> &X, const T &Y) { |
464 | return Y < X; |
465 | } |
466 | |
467 | template <typename T> |
468 | constexpr bool operator>(const T &X, const Optional<T> &Y) { |
469 | return Y < X; |
470 | } |
471 | |
472 | template <typename T> |
473 | constexpr bool operator>=(const Optional<T> &X, const T &Y) { |
474 | return !(X < Y); |
475 | } |
476 | |
477 | template <typename T> |
478 | constexpr bool operator>=(const T &X, const Optional<T> &Y) { |
479 | return !(X < Y); |
480 | } |
481 | |
482 | raw_ostream &operator<<(raw_ostream &OS, NoneType); |
483 | |
484 | template <typename T, typename = decltype(std::declval<raw_ostream &>() |
485 | << std::declval<const T &>())> |
486 | raw_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 | } |
495 | |
496 | #endif // LLVM_ADT_OPTIONAL_H |