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