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