clang -cc1 -cc1 -triple x86_64-pc-linux-gnu -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 -analyzer-config-compatibility-mode=true -mrelocation-model pic -pic-level 2 -mframe-pointer=none -fmath-errno -fno-rounding-math -mconstructor-aliases -munwind-tables -target-cpu x86-64 -tune-cpu generic -debugger-tuning=gdb -ffunction-sections -fdata-sections -fcoverage-compilation-dir=/build/llvm-toolchain-snapshot-14~++20210903100615+fd66b44ec19e/build-llvm/lib/Analysis -resource-dir /usr/lib/llvm-14/lib/clang/14.0.0 -D _GNU_SOURCE -D __STDC_CONSTANT_MACROS -D __STDC_FORMAT_MACROS -D __STDC_LIMIT_MACROS -I /build/llvm-toolchain-snapshot-14~++20210903100615+fd66b44ec19e/build-llvm/lib/Analysis -I /build/llvm-toolchain-snapshot-14~++20210903100615+fd66b44ec19e/llvm/lib/Analysis -I /build/llvm-toolchain-snapshot-14~++20210903100615+fd66b44ec19e/build-llvm/include -I /build/llvm-toolchain-snapshot-14~++20210903100615+fd66b44ec19e/llvm/include -D NDEBUG -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/10/../../../../include/c++/10 -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/10/../../../../include/x86_64-linux-gnu/c++/10 -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/10/../../../../include/c++/10/backward -internal-isystem /usr/lib/llvm-14/lib/clang/14.0.0/include -internal-isystem /usr/local/include -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/10/../../../../x86_64-linux-gnu/include -internal-externc-isystem /usr/include/x86_64-linux-gnu -internal-externc-isystem /include -internal-externc-isystem /usr/include -O2 -Wno-unused-parameter -Wwrite-strings -Wno-missing-field-initializers -Wno-long-long -Wno-maybe-uninitialized -Wno-class-memaccess -Wno-redundant-move -Wno-pessimizing-move -Wno-noexcept-type -Wno-comment -std=c++14 -fdeprecated-macro -fdebug-compilation-dir=/build/llvm-toolchain-snapshot-14~++20210903100615+fd66b44ec19e/build-llvm/lib/Analysis -fdebug-prefix-map=/build/llvm-toolchain-snapshot-14~++20210903100615+fd66b44ec19e=. -ferror-limit 19 -fvisibility-inlines-hidden -stack-protector 2 -fgnuc-version=4.2.1 -vectorize-loops -vectorize-slp -analyzer-output=html -analyzer-config stable-report-filename=true -faddrsig -D__GCC_HAVE_DWARF2_CFI_ASM=1 -o /tmp/scan-build-2021-09-04-040900-46481-1 -x c++ /build/llvm-toolchain-snapshot-14~++20210903100615+fd66b44ec19e/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 | static CmpInst *getOuterLoopLatchCmp(const Loop &OuterLoop) { |
54 | |
55 | const BasicBlock *Latch = OuterLoop.getLoopLatch(); |
56 | assert(Latch && "Expecting a valid loop latch"); |
57 | |
58 | const BranchInst *BI = dyn_cast<BranchInst>(Latch->getTerminator()); |
| 4 | | Assuming the object is not a 'BranchInst' | |
|
| 5 | | 'BI' initialized to a null pointer value | |
|
59 | assert(BI && BI->isConditional() && |
60 | "Expecting loop latch terminator to be a branch instruction"); |
61 | |
62 | CmpInst *OuterLoopLatchCmp = dyn_cast<CmpInst>(BI->getCondition()); |
| 6 | | Called C++ object pointer is null |
|
63 | DEBUG_WITH_TYPE( |
64 | VerboseDebug, if (OuterLoopLatchCmp) { |
65 | dbgs() << "Outer loop latch compare instruction: " << *OuterLoopLatchCmp |
66 | << "\n"; |
67 | }); |
68 | return OuterLoopLatchCmp; |
69 | } |
70 | |
71 | static CmpInst *getInnerLoopGuardCmp(const Loop &InnerLoop) { |
72 | |
73 | BranchInst *InnerGuard = InnerLoop.getLoopGuardBranch(); |
74 | CmpInst *InnerLoopGuardCmp = |
75 | (InnerGuard) ? dyn_cast<CmpInst>(InnerGuard->getCondition()) : nullptr; |
76 | |
77 | DEBUG_WITH_TYPE( |
78 | VerboseDebug, if (InnerLoopGuardCmp) { |
79 | dbgs() << "Inner loop guard compare instruction: " << *InnerLoopGuardCmp |
80 | << "\n"; |
81 | }); |
82 | return InnerLoopGuardCmp; |
83 | } |
84 | |
85 | static bool checkSafeInstruction(const Instruction &I, |
86 | const CmpInst *InnerLoopGuardCmp, |
87 | const CmpInst *OuterLoopLatchCmp, |
88 | Optional<Loop::LoopBounds> OuterLoopLB) { |
89 | |
90 | bool IsAllowed = |
91 | isSafeToSpeculativelyExecute(&I) || isa<PHINode>(I) || isa<BranchInst>(I); |
92 | if (!IsAllowed) |
93 | return false; |
94 | |
95 | |
96 | |
97 | if ((isa<BinaryOperator>(I) && &I != &OuterLoopLB->getStepInst()) || |
98 | (isa<CmpInst>(I) && &I != OuterLoopLatchCmp && &I != InnerLoopGuardCmp)) { |
99 | return false; |
100 | } |
101 | return true; |
102 | } |
103 | |
104 | bool LoopNest::arePerfectlyNested(const Loop &OuterLoop, const Loop &InnerLoop, |
105 | ScalarEvolution &SE) { |
106 | return (analyzeLoopNestForPerfectNest(OuterLoop, InnerLoop, SE) == |
107 | PerfectLoopNest); |
108 | } |
109 | |
110 | LoopNest::LoopNestEnum LoopNest::analyzeLoopNestForPerfectNest( |
111 | const Loop &OuterLoop, const Loop &InnerLoop, ScalarEvolution &SE) { |
112 | |
113 | assert(!OuterLoop.isInnermost() && "Outer loop should have subloops"); |
114 | assert(!InnerLoop.isOutermost() && "Inner loop should have a parent"); |
115 | LLVM_DEBUG(dbgs() << "Checking whether loop '" << OuterLoop.getName() |
116 | << "' and '" << InnerLoop.getName() |
117 | << "' are perfectly nested.\n"); |
118 | |
119 | |
120 | |
121 | |
122 | |
123 | |
124 | |
125 | if (!checkLoopsStructure(OuterLoop, InnerLoop, SE)) { |
126 | LLVM_DEBUG(dbgs() << "Not perfectly nested: invalid loop structure.\n"); |
127 | return InvalidLoopStructure; |
128 | } |
129 | |
130 | |
131 | auto OuterLoopLB = OuterLoop.getBounds(SE); |
132 | if (OuterLoopLB == None) { |
133 | LLVM_DEBUG(dbgs() << "Cannot compute loop bounds of OuterLoop: " |
134 | << OuterLoop << "\n";); |
135 | return OuterLoopLowerBoundUnknown; |
136 | } |
137 | |
138 | CmpInst *OuterLoopLatchCmp = getOuterLoopLatchCmp(OuterLoop); |
139 | CmpInst *InnerLoopGuardCmp = getInnerLoopGuardCmp(InnerLoop); |
140 | |
141 | |
142 | |
143 | |
144 | |
145 | |
146 | auto containsOnlySafeInstructions = [&](const BasicBlock &BB) { |
147 | return llvm::all_of(BB, [&](const Instruction &I) { |
148 | bool IsSafeInstr = checkSafeInstruction(I, InnerLoopGuardCmp, |
149 | OuterLoopLatchCmp, OuterLoopLB); |
150 | if (IsSafeInstr) { |
151 | DEBUG_WITH_TYPE(VerboseDebug, { |
152 | dbgs() << "Instruction: " << I << "\nin basic block:" << BB |
153 | << "is unsafe.\n"; |
154 | }); |
155 | } |
156 | return IsSafeInstr; |
157 | }); |
158 | }; |
159 | |
160 | |
161 | |
162 | const BasicBlock *OuterLoopHeader = OuterLoop.getHeader(); |
163 | const BasicBlock *OuterLoopLatch = OuterLoop.getLoopLatch(); |
164 | const BasicBlock *InnerLoopPreHeader = InnerLoop.getLoopPreheader(); |
165 | |
166 | if (!containsOnlySafeInstructions(*OuterLoopHeader) || |
167 | !containsOnlySafeInstructions(*OuterLoopLatch) || |
168 | (InnerLoopPreHeader != OuterLoopHeader && |
169 | !containsOnlySafeInstructions(*InnerLoopPreHeader)) || |
170 | !containsOnlySafeInstructions(*InnerLoop.getExitBlock())) { |
171 | LLVM_DEBUG(dbgs() << "Not perfectly nested: code surrounding inner loop is " |
172 | "unsafe\n";); |
173 | return ImperfectLoopNest; |
174 | } |
175 | |
176 | LLVM_DEBUG(dbgs() << "Loop '" << OuterLoop.getName() << "' and '" |
177 | << InnerLoop.getName() << "' are perfectly nested.\n"); |
178 | |
179 | return PerfectLoopNest; |
180 | } |
181 | |
182 | LoopNest::InstrVectorTy LoopNest::getInterveningInstructions( |
183 | const Loop &OuterLoop, const Loop &InnerLoop, ScalarEvolution &SE) { |
184 | InstrVectorTy Instr; |
185 | switch (analyzeLoopNestForPerfectNest(OuterLoop, InnerLoop, SE)) { |
| 1 | Control jumps to 'case ImperfectLoopNest:' at line 201 | |
|
186 | case PerfectLoopNest: |
187 | LLVM_DEBUG(dbgs() << "The loop Nest is Perfect, returning empty " |
188 | "instruction vector. \n";); |
189 | return Instr; |
190 | |
191 | case InvalidLoopStructure: |
192 | LLVM_DEBUG(dbgs() << "Not perfectly nested: invalid loop structure. " |
193 | "Instruction vector is empty.\n";); |
194 | return Instr; |
195 | |
196 | case OuterLoopLowerBoundUnknown: |
197 | LLVM_DEBUG(dbgs() << "Cannot compute loop bounds of OuterLoop: " |
198 | << OuterLoop << "\nInstruction vector is empty.\n";); |
199 | return Instr; |
200 | |
201 | case ImperfectLoopNest: |
202 | break; |
| 2 | | Execution continues on line 206 | |
|
203 | } |
204 | |
205 | |
206 | auto OuterLoopLB = OuterLoop.getBounds(SE); |
207 | |
208 | CmpInst *OuterLoopLatchCmp = getOuterLoopLatchCmp(OuterLoop); |
| 3 | | Calling 'getOuterLoopLatchCmp' | |
|
209 | CmpInst *InnerLoopGuardCmp = getInnerLoopGuardCmp(InnerLoop); |
210 | |
211 | auto GetUnsafeInstructions = [&](const BasicBlock &BB) { |
212 | for (const Instruction &I : BB) { |
213 | if (!checkSafeInstruction(I, InnerLoopGuardCmp, OuterLoopLatchCmp, |
214 | OuterLoopLB)) { |
215 | Instr.push_back(&I); |
216 | DEBUG_WITH_TYPE(VerboseDebug, { |
217 | dbgs() << "Instruction: " << I << "\nin basic block:" << BB |
218 | << "is unsafe.\n"; |
219 | }); |
220 | } |
221 | } |
222 | }; |
223 | |
224 | |
225 | |
226 | const BasicBlock *OuterLoopHeader = OuterLoop.getHeader(); |
227 | const BasicBlock *OuterLoopLatch = OuterLoop.getLoopLatch(); |
228 | const BasicBlock *InnerLoopPreHeader = InnerLoop.getLoopPreheader(); |
229 | const BasicBlock *InnerLoopExitBlock = InnerLoop.getExitBlock(); |
230 | |
231 | GetUnsafeInstructions(*OuterLoopHeader); |
232 | GetUnsafeInstructions(*OuterLoopLatch); |
233 | GetUnsafeInstructions(*InnerLoopExitBlock); |
234 | |
235 | if (InnerLoopPreHeader != OuterLoopHeader) { |
236 | GetUnsafeInstructions(*InnerLoopPreHeader); |
237 | } |
238 | return Instr; |
239 | } |
240 | |
241 | SmallVector<LoopVectorTy, 4> |
242 | LoopNest::getPerfectLoops(ScalarEvolution &SE) const { |
243 | SmallVector<LoopVectorTy, 4> LV; |
244 | LoopVectorTy PerfectNest; |
245 | |
246 | for (Loop *L : depth_first(const_cast<Loop *>(Loops.front()))) { |
247 | if (PerfectNest.empty()) |
248 | PerfectNest.push_back(L); |
249 | |
250 | auto &SubLoops = L->getSubLoops(); |
251 | if (SubLoops.size() == 1 && arePerfectlyNested(*L, *SubLoops.front(), SE)) { |
252 | PerfectNest.push_back(SubLoops.front()); |
253 | } else { |
254 | LV.push_back(PerfectNest); |
255 | PerfectNest.clear(); |
256 | } |
257 | } |
258 | |
259 | return LV; |
260 | } |
261 | |
262 | unsigned LoopNest::getMaxPerfectDepth(const Loop &Root, ScalarEvolution &SE) { |
263 | LLVM_DEBUG(dbgs() << "Get maximum perfect depth of loop nest rooted by loop '" |
264 | << Root.getName() << "'\n"); |
265 | |
266 | const Loop *CurrentLoop = &Root; |
267 | const auto *SubLoops = &CurrentLoop->getSubLoops(); |
268 | unsigned CurrentDepth = 1; |
269 | |
270 | while (SubLoops->size() == 1) { |
271 | const Loop *InnerLoop = SubLoops->front(); |
272 | if (!arePerfectlyNested(*CurrentLoop, *InnerLoop, SE)) { |
273 | LLVM_DEBUG({ |
274 | dbgs() << "Not a perfect nest: loop '" << CurrentLoop->getName() |
275 | << "' is not perfectly nested with loop '" |
276 | << InnerLoop->getName() << "'\n"; |
277 | }); |
278 | break; |
279 | } |
280 | |
281 | CurrentLoop = InnerLoop; |
282 | SubLoops = &CurrentLoop->getSubLoops(); |
283 | ++CurrentDepth; |
284 | } |
285 | |
286 | return CurrentDepth; |
287 | } |
288 | |
289 | const BasicBlock &LoopNest::skipEmptyBlockUntil(const BasicBlock *From, |
290 | const BasicBlock *End, |
291 | bool CheckUniquePred) { |
292 | assert(From && "Expecting valid From"); |
293 | assert(End && "Expecting valid End"); |
294 | |
295 | if (From == End || !From->getUniqueSuccessor()) |
296 | return *From; |
297 | |
298 | auto IsEmpty = [](const BasicBlock *BB) { |
299 | return (BB->getInstList().size() == 1); |
300 | }; |
301 | |
302 | |
303 | SmallPtrSet<const BasicBlock *, 4> Visited; |
304 | const BasicBlock *BB = From->getUniqueSuccessor(); |
305 | const BasicBlock *PredBB = From; |
306 | while (BB && BB != End && IsEmpty(BB) && !Visited.count(BB) && |
307 | (!CheckUniquePred || BB->getUniquePredecessor())) { |
308 | Visited.insert(BB); |
309 | PredBB = BB; |
310 | BB = BB->getUniqueSuccessor(); |
311 | } |
312 | |
313 | return (BB == End) ? *End : *PredBB; |
314 | } |
315 | |
316 | static bool checkLoopsStructure(const Loop &OuterLoop, const Loop &InnerLoop, |
317 | ScalarEvolution &SE) { |
318 | |
319 | if ((OuterLoop.getSubLoops().size() != 1) || |
320 | (InnerLoop.getParentLoop() != &OuterLoop)) |
321 | return false; |
322 | |
323 | |
324 | if (!OuterLoop.isLoopSimplifyForm() || !InnerLoop.isLoopSimplifyForm()) |
325 | return false; |
326 | |
327 | const BasicBlock *OuterLoopHeader = OuterLoop.getHeader(); |
328 | const BasicBlock *OuterLoopLatch = OuterLoop.getLoopLatch(); |
329 | const BasicBlock *InnerLoopPreHeader = InnerLoop.getLoopPreheader(); |
330 | const BasicBlock *InnerLoopLatch = InnerLoop.getLoopLatch(); |
331 | const BasicBlock *InnerLoopExit = InnerLoop.getExitBlock(); |
332 | |
333 | |
334 | if (OuterLoop.getExitingBlock() != OuterLoopLatch || |
335 | InnerLoop.getExitingBlock() != InnerLoopLatch || !InnerLoopExit) |
336 | return false; |
337 | |
338 | |
339 | auto ContainsLCSSAPhi = [](const BasicBlock &ExitBlock) { |
340 | return any_of(ExitBlock.phis(), [](const PHINode &PN) { |
341 | return PN.getNumIncomingValues() == 1; |
342 | }); |
343 | }; |
344 | |
345 | |
346 | |
347 | |
348 | |
349 | auto IsExtraPhiBlock = [&](const BasicBlock &BB) { |
350 | return BB.getFirstNonPHI() == BB.getTerminator() && |
351 | all_of(BB.phis(), [&](const PHINode &PN) { |
352 | return all_of(PN.blocks(), [&](const BasicBlock *IncomingBlock) { |
353 | return IncomingBlock == InnerLoopExit || |
354 | IncomingBlock == OuterLoopHeader; |
355 | }); |
356 | }); |
357 | }; |
358 | |
359 | const BasicBlock *ExtraPhiBlock = nullptr; |
360 | |
361 | |
362 | if (OuterLoopHeader != InnerLoopPreHeader) { |
363 | const BasicBlock &SingleSucc = |
364 | LoopNest::skipEmptyBlockUntil(OuterLoopHeader, InnerLoopPreHeader); |
365 | |
366 | |
367 | if (&SingleSucc != InnerLoopPreHeader) { |
368 | const BranchInst *BI = dyn_cast<BranchInst>(SingleSucc.getTerminator()); |
369 | |
370 | if (!BI || BI != InnerLoop.getLoopGuardBranch()) |
371 | return false; |
372 | |
373 | bool InnerLoopExitContainsLCSSA = ContainsLCSSAPhi(*InnerLoopExit); |
374 | |
375 | |
376 | |
377 | for (const BasicBlock *Succ : BI->successors()) { |
378 | const BasicBlock *PotentialInnerPreHeader = Succ; |
379 | const BasicBlock *PotentialOuterLatch = Succ; |
380 | |
381 | |
382 | |
383 | if (Succ->getInstList().size() == 1) { |
384 | PotentialInnerPreHeader = |
385 | &LoopNest::skipEmptyBlockUntil(Succ, InnerLoopPreHeader); |
386 | PotentialOuterLatch = |
387 | &LoopNest::skipEmptyBlockUntil(Succ, OuterLoopLatch); |
388 | } |
389 | |
390 | if (PotentialInnerPreHeader == InnerLoopPreHeader) |
391 | continue; |
392 | if (PotentialOuterLatch == OuterLoopLatch) |
393 | continue; |
394 | |
395 | |
396 | |
397 | |
398 | |
399 | if (InnerLoopExitContainsLCSSA && IsExtraPhiBlock(*Succ) && |
400 | Succ->getSingleSuccessor() == OuterLoopLatch) { |
401 | |
402 | |
403 | |
404 | |
405 | ExtraPhiBlock = Succ; |
406 | continue; |
407 | } |
408 | |
409 | DEBUG_WITH_TYPE(VerboseDebug, { |
410 | dbgs() << "Inner loop guard successor " << Succ->getName() |
411 | << " doesn't lead to inner loop preheader or " |
412 | "outer loop latch.\n"; |
413 | }); |
414 | return false; |
415 | } |
416 | } |
417 | } |
418 | |
419 | |
420 | |
421 | if ((!ExtraPhiBlock || |
422 | &LoopNest::skipEmptyBlockUntil(InnerLoop.getExitBlock(), |
423 | ExtraPhiBlock) != ExtraPhiBlock) && |
424 | (&LoopNest::skipEmptyBlockUntil(InnerLoop.getExitBlock(), |
425 | OuterLoopLatch) != OuterLoopLatch)) { |
426 | DEBUG_WITH_TYPE( |
427 | VerboseDebug, |
428 | dbgs() << "Inner loop exit block " << *InnerLoopExit |
429 | << " does not directly lead to the outer loop latch.\n";); |
430 | return false; |
431 | } |
432 | |
433 | return true; |
434 | } |
435 | |
436 | AnalysisKey LoopNestAnalysis::Key; |
437 | |
438 | raw_ostream &llvm::operator<<(raw_ostream &OS, const LoopNest &LN) { |
439 | OS << "IsPerfect="; |
440 | if (LN.getMaxPerfectDepth() == LN.getNestDepth()) |
441 | OS << "true"; |
442 | else |
443 | OS << "false"; |
444 | OS << ", Depth=" << LN.getNestDepth(); |
445 | OS << ", OutermostLoop: " << LN.getOutermostLoop().getName(); |
446 | OS << ", Loops: ( "; |
447 | for (const Loop *L : LN.getLoops()) |
448 | OS << L->getName() << " "; |
449 | OS << ")"; |
450 | |
451 | return OS; |
452 | } |
453 | |
454 | |
455 | |
456 | |
457 | |
458 | PreservedAnalyses LoopNestPrinterPass::run(Loop &L, LoopAnalysisManager &AM, |
459 | LoopStandardAnalysisResults &AR, |
460 | LPMUpdater &U) { |
461 | if (auto LN = LoopNest::getLoopNest(L, AR.SE)) |
462 | OS << *LN << "\n"; |
463 | |
464 | return PreservedAnalyses::all(); |
465 | } |