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 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()); 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 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 // 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 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 // 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 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> 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 // 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 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 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 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