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
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 /// 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.
36 static bool checkLoopsStructure(const Loop &OuterLoop, const Loop &InnerLoop,
37 ScalarEvolution &SE);
38
39 //===----------------------------------------------------------------------===//
40 // LoopNest implementation
41 //
42
LoopNest(Loop & Root,ScalarEvolution & SE)43 LoopNest::LoopNest(Loop &Root, ScalarEvolution &SE)
44 : MaxPerfectDepth(getMaxPerfectDepth(Root, SE)) {
45 append_range(Loops, breadth_first(&Root));
46 }
47
getLoopNest(Loop & Root,ScalarEvolution & SE)48 std::unique_ptr<LoopNest> LoopNest::getLoopNest(Loop &Root,
49 ScalarEvolution &SE) {
50 return std::make_unique<LoopNest>(Root, SE);
51 }
52
getOuterLoopLatchCmp(const Loop & OuterLoop)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());
59 assert(BI && BI->isConditional() &&
60 "Expecting loop latch terminator to be a branch instruction");
61
62 CmpInst *OuterLoopLatchCmp = dyn_cast<CmpInst>(BI->getCondition());
63 DEBUG_WITH_TYPE(
64 VerboseDebug, if (OuterLoopLatchCmp) {
65 dbgs() << "Outer loop latch compare instruction: " << *OuterLoopLatchCmp
66 << "\n";
67 });
68 return OuterLoopLatchCmp;
69 }
70
getInnerLoopGuardCmp(const Loop & InnerLoop)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
checkSafeInstruction(const Instruction & I,const CmpInst * InnerLoopGuardCmp,const CmpInst * OuterLoopLatchCmp,Optional<Loop::LoopBounds> OuterLoopLB)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 // The only binary instruction allowed is the outer loop step instruction,
95 // the only comparison instructions allowed are the inner loop guard
96 // compare instruction and the outer loop latch compare instruction.
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
arePerfectlyNested(const Loop & OuterLoop,const Loop & InnerLoop,ScalarEvolution & SE)104 bool LoopNest::arePerfectlyNested(const Loop &OuterLoop, const Loop &InnerLoop,
105 ScalarEvolution &SE) {
106 return (analyzeLoopNestForPerfectNest(OuterLoop, InnerLoop, SE) ==
107 PerfectLoopNest);
108 }
109
analyzeLoopNestForPerfectNest(const Loop & OuterLoop,const Loop & InnerLoop,ScalarEvolution & SE)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 // Determine whether the loops structure satisfies the following requirements:
120 // - the inner loop should be the outer loop's only child
121 // - the outer loop header should 'flow' into the inner loop preheader
122 // or jump around the inner loop to the outer loop latch
123 // - if the inner loop latch exits the inner loop, it should 'flow' into
124 // the outer loop latch.
125 if (!checkLoopsStructure(OuterLoop, InnerLoop, SE)) {
126 LLVM_DEBUG(dbgs() << "Not perfectly nested: invalid loop structure.\n");
127 return InvalidLoopStructure;
128 }
129
130 // Bail out if we cannot retrieve the outer loop bounds.
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 // Determine whether instructions in a basic block are one of:
142 // - the inner loop guard comparison
143 // - the outer loop latch comparison
144 // - the outer loop induction variable increment
145 // - a phi node, a cast or a branch
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 // Check the code surrounding the inner loop for instructions that are deemed
161 // unsafe.
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
getInterveningInstructions(const Loop & OuterLoop,const Loop & InnerLoop,ScalarEvolution & SE)182 LoopNest::InstrVectorTy LoopNest::getInterveningInstructions(
183 const Loop &OuterLoop, const Loop &InnerLoop, ScalarEvolution &SE) {
184 InstrVectorTy Instr;
185 switch (analyzeLoopNestForPerfectNest(OuterLoop, InnerLoop, SE)) {
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;
203 }
204
205 // Identify the outer loop latch comparison instruction.
206 auto OuterLoopLB = OuterLoop.getBounds(SE);
207
208 CmpInst *OuterLoopLatchCmp = getOuterLoopLatchCmp(OuterLoop);
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 // Check the code surrounding the inner loop for instructions that are deemed
225 // unsafe.
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>
getPerfectLoops(ScalarEvolution & SE) const242 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
getMaxPerfectDepth(const Loop & Root,ScalarEvolution & SE)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
skipEmptyBlockUntil(const BasicBlock * From,const BasicBlock * End,bool CheckUniquePred)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 // Visited is used to avoid running into an infinite loop.
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
checkLoopsStructure(const Loop & OuterLoop,const Loop & InnerLoop,ScalarEvolution & SE)316 static bool checkLoopsStructure(const Loop &OuterLoop, const Loop &InnerLoop,
317 ScalarEvolution &SE) {
318 // The inner loop must be the only outer loop's child.
319 if ((OuterLoop.getSubLoops().size() != 1) ||
320 (InnerLoop.getParentLoop() != &OuterLoop))
321 return false;
322
323 // We expect loops in normal form which have a preheader, header, latch...
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 // We expect rotated loops. The inner loop should have a single exit block.
334 if (OuterLoop.getExitingBlock() != OuterLoopLatch ||
335 InnerLoop.getExitingBlock() != InnerLoopLatch || !InnerLoopExit)
336 return false;
337
338 // Returns whether the block `ExitBlock` contains at least one LCSSA Phi node.
339 auto ContainsLCSSAPhi = [](const BasicBlock &ExitBlock) {
340 return any_of(ExitBlock.phis(), [](const PHINode &PN) {
341 return PN.getNumIncomingValues() == 1;
342 });
343 };
344
345 // Returns whether the block `BB` qualifies for being an extra Phi block. The
346 // extra Phi block is the additional block inserted after the exit block of an
347 // "guarded" inner loop which contains "only" Phi nodes corresponding to the
348 // LCSSA Phi nodes in the exit block.
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 // Ensure the only branch that may exist between the loops is the inner loop
361 // guard.
362 if (OuterLoopHeader != InnerLoopPreHeader) {
363 const BasicBlock &SingleSucc =
364 LoopNest::skipEmptyBlockUntil(OuterLoopHeader, InnerLoopPreHeader);
365
366 // no conditional branch present
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 // The successors of the inner loop guard should be the inner loop
376 // preheader or the outer loop latch possibly through empty blocks.
377 for (const BasicBlock *Succ : BI->successors()) {
378 const BasicBlock *PotentialInnerPreHeader = Succ;
379 const BasicBlock *PotentialOuterLatch = Succ;
380
381 // Ensure the inner loop guard successor is empty before skipping
382 // blocks.
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 // If `InnerLoopExit` contains LCSSA Phi instructions, additional block
396 // may be inserted before the `OuterLoopLatch` to which `BI` jumps. The
397 // loops are still considered perfectly nested if the extra block only
398 // contains Phi instructions from InnerLoopExit and OuterLoopHeader.
399 if (InnerLoopExitContainsLCSSA && IsExtraPhiBlock(*Succ) &&
400 Succ->getSingleSuccessor() == OuterLoopLatch) {
401 // Points to the extra block so that we can reference it later in the
402 // final check. We can also conclude that the inner loop is
403 // guarded and there exists LCSSA Phi node in the exit block later if
404 // we see a non-null `ExtraPhiBlock`.
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 // Ensure the inner loop exit block lead to the outer loop latch possibly
420 // through empty blocks.
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
operator <<(raw_ostream & OS,const LoopNest & LN)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 // LoopNestPrinterPass implementation
456 //
457
run(Loop & L,LoopAnalysisManager & AM,LoopStandardAnalysisResults & AR,LPMUpdater & U)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 }
466