llvm/lib/Analysis/LoopNestAnalysis.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-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
  19 using namespace llvm;
  20
  21 #define DEBUG_TYPE "loopnest"
  22 #ifndef NDEBUG
  23 static 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.
  35 static bool checkLoopsStructure(const Loop &OuterLoop, const Loop &InnerLoop,
  36                                 ScalarEvolution &SE);
  37
  38 //===----------------------------------------------------------------------===//
  39 // LoopNest implementation
  40 //
  41
  42 LoopNest::LoopNest(Loop &Root, ScalarEvolution &SE)
  43     : MaxPerfectDepth(getMaxPerfectDepth(Root, SE)) {
  44   append_range(Loops, breadth_first(&Root));
  45 }
  46
  47 std::unique_ptr<LoopNest> LoopNest::getLoopNest(Loop &Root,
  48                                                 ScalarEvolution &SE) {
  49   return std::make_unique<LoopNest>(Root, SE);
  50 }
  51
  52 static 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: " << *OuterLoopLatchCmp
  65                << "\n";
  66       });
  67   return OuterLoopLatchCmp;
  68 }
  69
  70 static 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: " << *InnerLoopGuardCmp
  79                << "\n";
  80       });
  81   return InnerLoopGuardCmp;
  82 }
  83
  84 static 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 guard
  95   // 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
 103 bool LoopNest::arePerfectlyNested(const Loop &OuterLoop, const Loop &InnerLoop,
 104                                   ScalarEvolution &SE) {
 105   return (analyzeLoopNestForPerfectNest(OuterLoop, InnerLoop, SE) ==
 106           PerfectLoopNest);
 107 }
 108
 109 LoopNest::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 child
 120   //  - the outer loop header should 'flow' into the inner loop preheader
 121   //    or jump around the inner loop to the outer loop latch
 122   //  - if the inner loop latch exits the inner loop, it should 'flow' into
 123   //    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 comparison
 142   //  - the outer loop latch comparison
 143   //  - the outer loop induction variable increment
 144   //  - a phi node, a cast or a branch
 145   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:" << BB
 152                  << "is unsafe.\n";
 153         });
 154       }
 155       return IsSafeInstr;
 156     });
 157   };
 158
 159   // Check the code surrounding the inner loop for instructions that are deemed
 160   // 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
 181 LoopNest::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:" << BB
 217                  << "is unsafe.\n";
 218         });
 219       }
 220     }
 221   };
 222
 223   // Check the code surrounding the inner loop for instructions that are deemed
 224   // 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
 240 SmallVector<LoopVectorTy, 4>
 241 LoopNest::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
 261 unsigned 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
 288 const 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
 315 static 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. The
 345   // extra Phi block is the additional block inserted after the exit block of an
 346   // "guarded" inner loop which contains "only" Phi nodes corresponding to the
 347   // LCSSA Phi nodes in the exit block.
 348   auto IsExtraPhiBlock = [&](const BasicBlock &BB) {
 349     return BB.getFirstNonPHI() == 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 loop
 360   // guard.
 361   if (OuterLoopHeader != InnerLoopPreHeader) {
 362     const BasicBlock &SingleSucc =
 363         LoopNest::skipEmptyBlockUntil(OuterLoopHeader, InnerLoopPreHeader);
 364
 365     // no conditional branch present
 366     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 loop
 375       // 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 skipping
 381         // 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 block
 395         // may be inserted before the `OuterLoopLatch` to which `BI` jumps. The
 396         // loops are still considered perfectly nested if the extra block only
 397         // 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 the
 401           // final check. We can also conclude that the inner loop is
 402           // guarded and there exists LCSSA Phi node in the exit block later if
 403           // 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 possibly
 419   // 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 " << *InnerLoopExit
 428                << " does not directly lead to the outer loop latch.\n";);
 429     return false;
 430   }
 431
 432   return true;
 433 }
 434
 435 AnalysisKey LoopNestAnalysis::Key;
 436
 437 raw_ostream &llvm::operator<<(raw_ostream &OS, const LoopNest &LN) {
 438   OS << "IsPerfect=";
 439   if (LN.getMaxPerfectDepth() == LN.getNestDepth())
 440     OS << "true";
 441   else
 442     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 implementation
 455 //
 456
 457 PreservedAnalyses 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 }