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/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 }