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 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() 58 << "' and '" << InnerLoop.getName() 59 << "' are perfectly nested.\n"); 60 61 // Determine whether the loops structure satisfies the following requirements: 62 // - the inner loop should be the outer loop's only child 63 // - the outer loop header should 'flow' into the inner loop preheader 64 // or jump around the inner loop to the outer loop latch 65 // - if the inner loop latch exits the inner loop, it should 'flow' into 66 // the outer loop latch. 67 if (!checkLoopsStructure(OuterLoop, InnerLoop, SE)) { 68 LLVM_DEBUG(dbgs() << "Not perfectly nested: invalid loop structure.\n"); 69 return false; 70 } 71 72 // Bail out if we cannot retrieve the outer loop bounds. 73 auto OuterLoopLB = OuterLoop.getBounds(SE); 74 if (OuterLoopLB == None) { 75 LLVM_DEBUG(dbgs() << "Cannot compute loop bounds of OuterLoop: " 76 << OuterLoop << "\n";); 77 return false; 78 } 79 80 // Identify the outer loop latch comparison instruction. 81 const BasicBlock *Latch = OuterLoop.getLoopLatch(); 82 assert(Latch && "Expecting a valid loop latch"); 83 const BranchInst *BI = dyn_cast<BranchInst>(Latch->getTerminator()); 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()); 88 DEBUG_WITH_TYPE( 89 VerboseDebug, if (OuterLoopLatchCmp) { 90 dbgs() << "Outer loop latch compare instruction: " << *OuterLoopLatchCmp 91 << "\n"; 92 }); 93 94 // Identify the inner loop guard instruction. 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 // Determine whether instructions in a basic block are one of: 106 // - the inner loop guard comparison 107 // - the outer loop latch comparison 108 // - the outer loop induction variable increment 109 // - a phi node, a cast or a branch 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 // The only binary instruction allowed is the outer loop step instruction, 123 // the only comparison instructions allowed are the inner loop guard 124 // compare instruction and the outer loop latch compare instruction. 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 // Check the code surrounding the inner loop for instructions that are deemed 139 // unsafe. 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)) { 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 assert(From && "Expecting valid From"); 211 assert(End && "Expecting valid End"); 212 213 if (From == End || !From->getSingleSuccessor()) 214 return *From; 215 216 auto IsEmpty = [](const BasicBlock *BB) { 217 return (BB->getInstList().size() == 1); 218 }; 219 220 // Visited is used to avoid running into an infinite loop. 221 SmallPtrSet<const BasicBlock *, 4> Visited; 222 const BasicBlock *BB = From->getSingleSuccessor(); 223 const BasicBlock *PredBB = BB; 224 while (BB && BB != End && IsEmpty(BB) && !Visited.count(BB)) { 225 Visited.insert(BB); 226 PredBB = BB; 227 BB = BB->getSingleSuccessor(); 228 } 229 230 return (BB == End) ? *End : *PredBB; 231 } 232 233 static bool checkLoopsStructure(const Loop &OuterLoop, const Loop &InnerLoop, 234 ScalarEvolution &SE) { 235 // The inner loop must be the only outer loop's child. 236 if ((OuterLoop.getSubLoops().size() != 1) || 237 (InnerLoop.getParentLoop() != &OuterLoop)) 238 return false; 239 240 // We expect loops in normal form which have a preheader, header, latch... 241 if (!OuterLoop.isLoopSimplifyForm() || !InnerLoop.isLoopSimplifyForm()) 242 return false; 243 244 const BasicBlock *OuterLoopHeader = OuterLoop.getHeader(); 245 const BasicBlock *OuterLoopLatch = OuterLoop.getLoopLatch(); 246 const BasicBlock *InnerLoopPreHeader = InnerLoop.getLoopPreheader(); 247 const BasicBlock *InnerLoopLatch = InnerLoop.getLoopLatch(); 248 const BasicBlock *InnerLoopExit = InnerLoop.getExitBlock(); 249 250 // We expect rotated loops. The inner loop should have a single exit block. 251 if (OuterLoop.getExitingBlock() != OuterLoopLatch || 252 InnerLoop.getExitingBlock() != InnerLoopLatch || !InnerLoopExit) 253 return false; 254 255 // Returns whether the block `ExitBlock` contains at least one LCSSA Phi node. 256 auto ContainsLCSSAPhi = [](const BasicBlock &ExitBlock) { 257 return any_of(ExitBlock.phis(), [](const PHINode &PN) { 258 return PN.getNumIncomingValues() == 1; 259 }); 260 }; 261 262 // Returns whether the block `BB` qualifies for being an extra Phi block. The 263 // extra Phi block is the additional block inserted after the exit block of an 264 // "guarded" inner loop which contains "only" Phi nodes corresponding to the 265 // LCSSA Phi nodes in the exit block. 266 auto IsExtraPhiBlock = [&](const BasicBlock &BB) { 267 return BB.getFirstNonPHI() == BB.getTerminator() && 268 all_of(BB.phis(), [&](const PHINode &PN) { 269 return all_of(PN.blocks(), [&](const BasicBlock *IncomingBlock) { 270 return IncomingBlock == InnerLoopExit || 271 IncomingBlock == OuterLoopHeader; 272 }); 273 }); 274 }; 275 276 const BasicBlock *ExtraPhiBlock = nullptr; 277 // Ensure the only branch that may exist between the loops is the inner loop 278 // guard. 279 if (OuterLoopHeader != InnerLoopPreHeader) { 280 const BasicBlock &SingleSucc = 281 LoopNest::skipEmptyBlockUntil(OuterLoopHeader, InnerLoopPreHeader); 282 283 // no conditional branch present 284 if (&SingleSucc != InnerLoopPreHeader) { 285 const BranchInst *BI = dyn_cast<BranchInst>(SingleSucc.getTerminator()); 286 287 if (!BI || BI != InnerLoop.getLoopGuardBranch()) 288 return false; 289 290 bool InnerLoopExitContainsLCSSA = ContainsLCSSAPhi(*InnerLoopExit); 291 292 // The successors of the inner loop guard should be the inner loop 293 // preheader or the outer loop latch possibly through empty blocks. 294 for (const BasicBlock *Succ : BI->successors()) { 295 const BasicBlock *PotentialInnerPreHeader = Succ; 296 const BasicBlock *PotentialOuterLatch = Succ; 297 298 // Ensure the inner loop guard successor is empty before skipping 299 // blocks. 300 if (Succ->getInstList().size() == 1) { 301 PotentialInnerPreHeader = 302 &LoopNest::skipEmptyBlockUntil(Succ, InnerLoopPreHeader); 303 PotentialOuterLatch = 304 &LoopNest::skipEmptyBlockUntil(Succ, OuterLoopLatch); 305 } 306 307 if (PotentialInnerPreHeader == InnerLoopPreHeader) 308 continue; 309 if (PotentialOuterLatch == OuterLoopLatch) 310 continue; 311 312 // If `InnerLoopExit` contains LCSSA Phi instructions, additional block 313 // may be inserted before the `OuterLoopLatch` to which `BI` jumps. The 314 // loops are still considered perfectly nested if the extra block only 315 // contains Phi instructions from InnerLoopExit and OuterLoopHeader. 316 if (InnerLoopExitContainsLCSSA && IsExtraPhiBlock(*Succ) && 317 Succ->getSingleSuccessor() == OuterLoopLatch) { 318 // Points to the extra block so that we can reference it later in the 319 // final check. We can also conclude that the inner loop is 320 // guarded and there exists LCSSA Phi node in the exit block later if 321 // we see a non-null `ExtraPhiBlock`. 322 ExtraPhiBlock = Succ; 323 continue; 324 } 325 326 DEBUG_WITH_TYPE(VerboseDebug, { 327 dbgs() << "Inner loop guard successor " << Succ->getName() 328 << " doesn't lead to inner loop preheader or " 329 "outer loop latch.\n"; 330 }); 331 return false; 332 } 333 } 334 } 335 336 // Ensure the inner loop exit block lead to the outer loop latch possibly 337 // through empty blocks. 338 const BasicBlock &SuccInner = 339 LoopNest::skipEmptyBlockUntil(InnerLoop.getExitBlock(), OuterLoopLatch); 340 if (&SuccInner != OuterLoopLatch && &SuccInner != ExtraPhiBlock) { 341 DEBUG_WITH_TYPE( 342 VerboseDebug, 343 dbgs() << "Inner loop exit block " << *InnerLoopExit 344 << " does not directly lead to the outer loop latch.\n";); 345 return false; 346 } 347 348 return true; 349 } 350 351 AnalysisKey LoopNestAnalysis::Key; 352 353 raw_ostream &llvm::operator<<(raw_ostream &OS, const LoopNest &LN) { 354 OS << "IsPerfect="; 355 if (LN.getMaxPerfectDepth() == LN.getNestDepth()) 356 OS << "true"; 357 else 358 OS << "false"; 359 OS << ", Depth=" << LN.getNestDepth(); 360 OS << ", OutermostLoop: " << LN.getOutermostLoop().getName(); 361 OS << ", Loops: ( "; 362 for (const Loop *L : LN.getLoops()) 363 OS << L->getName() << " "; 364 OS << ")"; 365 366 return OS; 367 } 368 369 //===----------------------------------------------------------------------===// 370 // LoopNestPrinterPass implementation 371 // 372 373 PreservedAnalyses LoopNestPrinterPass::run(Loop &L, LoopAnalysisManager &AM, 374 LoopStandardAnalysisResults &AR, 375 LPMUpdater &U) { 376 if (auto LN = LoopNest::getLoopNest(L, AR.SE)) 377 OS << *LN << "\n"; 378 379 return PreservedAnalyses::all(); 380 } 381