LoopNest Analysis expansion to return instructions that prevent a Loop Nest from being perfect

[madanial]

Summary

Expand LoopNestAnalysis to return the full list of instructions that cause a loop nest to be imperfect. This is useful for other passes to know if they should continue for in the inner loops.
Added New function getInterveningInstructions
that returns a small vector with the instructions that prevent a loop for being perfect. Also added a couple of helper functions to reduce code duplication.

[Whitney]

llvm/include/llvm/Analysis/LoopNestAnalysis.h

37

Why is this needed?

llvm/lib/Analysis/LoopNestAnalysis.cpp

53

clang-format the lines you changed.

92

no braces needed for single statement block,

107

return (analyzeLoopNestForPerfectNest(OuterLoop,InnerLoop,SE) == PerfectLoopNest);

152

Variable name starts with uppercase.

[madanial]

Addressing review comments and clang-format

[Whitney]

llvm/include/llvm/Analysis/LoopNestAnalysis.h

55

from being Perfect => from being perfect.

[madanial]

This comment was removed by madanial.

[madanial]

Addressed latest comment

llvm/include/llvm/Analysis/LoopNestAnalysis.h

 
 #include "llvm/ADT/STLExtras.h"
 #include "llvm/Analysis/LoopAnalysisManager.h"
 #include "llvm/Analysis/LoopInfo.h"
 
 namespace llvm {
 
 using LoopVectorTy = SmallVector<Loop *, 8>;
+
 class LPMUpdater;
 
 /// This class represents a loop nest and can be used to query its properties.
 class LoopNest {
 public:
+  using InstrVectorTy = SmallVector<const Instruction *>;
+
   /// Construct a loop nest rooted by loop \p Root.
   LoopNest(Loop &Root, ScalarEvolution &SE);
 
   LoopNest() = delete;
 
   /// Construct a LoopNest object.
   static std::unique_ptr<LoopNest> getLoopNest(Loop &Root, ScalarEvolution &SE);
 
   /// Return true if the given loops \p OuterLoop and \p InnerLoop are
   /// perfectly nested with respect to each other, and false otherwise.
   /// Example:
   /// \code
   ///   for(i)
   ///     for(j)
   ///       for(k)
   /// \endcode
   /// arePerfectlyNested(loop_i, loop_j, SE) would return true.
   /// arePerfectlyNested(loop_j, loop_k, SE) would return true.
   /// arePerfectlyNested(loop_i, loop_k, SE) would return false.
   static bool arePerfectlyNested(const Loop &OuterLoop, const Loop &InnerLoop,
                                  ScalarEvolution &SE);
 
+  /// Return a vector of instructions that prevent the LoopNest given
+  /// by loops \p OuterLoop and \p InnerLoop from being perfect.
+  static InstrVectorTy getInterveningInstructions(const Loop &OuterLoop,
+                                                  const Loop &InnerLoop,
+                                                  ScalarEvolution &SE);
+
   /// Return the maximum nesting depth of the loop nest rooted by loop \p Root.
   /// For example given the loop nest:
   /// \code
   ///   for(i)     // loop at level 1 and Root of the nest
   ///     for(j)   // loop at level 2
   ///       <code>
   ///       for(k) // loop at level 3
   /// \endcode
Function *getParent() const {
     return Loops.front()->getHeader()->getParent();
   }
 
   StringRef getName() const { return Loops.front()->getName(); }
 
 protected:
   const unsigned MaxPerfectDepth; // maximum perfect nesting depth level.
   LoopVectorTy Loops; // the loops in the nest (in breadth first order).
+
+private:
+  enum LoopNestEnum {
+    PerfectLoopNest,
+    ImperfectLoopNest,
+    InvalidLoopStructure,
+    OuterLoopLowerBoundUnknown
+  };
+  static LoopNestEnum analyzeLoopNestForPerfectNest(const Loop &OuterLoop,
+                                                    const Loop &InnerLoop,
+                                                    ScalarEvolution &SE);
 };
 
 raw_ostream &operator<<(raw_ostream &, const LoopNest &);
 
 /// This analysis provides information for a loop nest. The analysis runs on
 /// demand and can be initiated via AM.getResult<LoopNestAnalysis>.
 class LoopNestAnalysis : public AnalysisInfoMixin<LoopNestAnalysis> {
   friend AnalysisInfoMixin<LoopNestAnalysis>;

llvm/lib/Analysis/LoopNestAnalysis.cpp

LoopNest::LoopNest(Loop &Root, ScalarEvolution &SE)
   append_range(Loops, breadth_first(&Root));
 }
 
 std::unique_ptr<LoopNest> LoopNest::getLoopNest(Loop &Root,
                                                 ScalarEvolution &SE) {
   return std::make_unique<LoopNest>(Root, SE);
 }
 
+static CmpInst *getOuterLoopLatchCmp(const Loop &OuterLoop) {
+
+  const BasicBlock *Latch = OuterLoop.getLoopLatch();
+  assert(Latch && "Expecting a valid loop latch");
+
+  const BranchInst *BI = dyn_cast<BranchInst>(Latch->getTerminator());
+  assert(BI && BI->isConditional() &&
+         "Expecting loop latch terminator to be a branch instruction");
+
+  CmpInst *OuterLoopLatchCmp = dyn_cast<CmpInst>(BI->getCondition());
+  DEBUG_WITH_TYPE(
+      VerboseDebug, if (OuterLoopLatchCmp) {
+        dbgs() << "Outer loop latch compare instruction: " << *OuterLoopLatchCmp
+               << "\n";
+      });
+  return OuterLoopLatchCmp;
+}
+
+static CmpInst *getInnerLoopGuardCmp(const Loop &InnerLoop) {
+
+  BranchInst *InnerGuard = InnerLoop.getLoopGuardBranch();
+  CmpInst *InnerLoopGuardCmp =
+      (InnerGuard) ? dyn_cast<CmpInst>(InnerGuard->getCondition()) : nullptr;
+
+  DEBUG_WITH_TYPE(
+      VerboseDebug, if (InnerLoopGuardCmp) {
+        dbgs() << "Inner loop guard compare instruction: " << *InnerLoopGuardCmp
+               << "\n";
+      });
+  return InnerLoopGuardCmp;
+}
+
+static bool checkSafeInstruction(const Instruction &I,
+                                 const CmpInst *InnerLoopGuardCmp,
+                                 const CmpInst *OuterLoopLatchCmp,
+                                 Optional<Loop::LoopBounds> OuterLoopLB) {
+
+  bool IsAllowed =
+      isSafeToSpeculativelyExecute(&I) || isa<PHINode>(I) || isa<BranchInst>(I);
+  if (!IsAllowed)
+    return false;
+  // The only binary instruction allowed is the outer loop step instruction,
+  // the only comparison instructions allowed are the inner loop guard
+  // compare instruction and the outer loop latch compare instruction.
+  if ((isa<BinaryOperator>(I) && &I != &OuterLoopLB->getStepInst()) ||
+      (isa<CmpInst>(I) && &I != OuterLoopLatchCmp && &I != InnerLoopGuardCmp)) {
+    return false;
+  }
+  return true;
+}
+
 bool LoopNest::arePerfectlyNested(const Loop &OuterLoop, const Loop &InnerLoop,
                                   ScalarEvolution &SE) {
+  return (analyzeLoopNestForPerfectNest(OuterLoop, InnerLoop, SE) ==
+          PerfectLoopNest);
+}
+
+LoopNest::LoopNestEnum LoopNest::analyzeLoopNestForPerfectNest(
+    const Loop &OuterLoop, const Loop &InnerLoop, ScalarEvolution &SE) {
+
   assert(!OuterLoop.isInnermost() && "Outer loop should have subloops");
   assert(!InnerLoop.isOutermost() && "Inner loop should have a parent");
   LLVM_DEBUG(dbgs() << "Checking whether loop '" << OuterLoop.getName()
                     << "' and '" << InnerLoop.getName()
                     << "' are perfectly nested.\n");
 
   // Determine whether the loops structure satisfies the following requirements:
   //  - the inner loop should be the outer loop's only child
   //  - the outer loop header should 'flow' into the inner loop preheader
   //    or jump around the inner loop to the outer loop latch
   //  - if the inner loop latch exits the inner loop, it should 'flow' into
   //    the outer loop latch.
   if (!checkLoopsStructure(OuterLoop, InnerLoop, SE)) {
     LLVM_DEBUG(dbgs() << "Not perfectly nested: invalid loop structure.\n");
-    return false;
+    return InvalidLoopStructure;
   }
 
   // Bail out if we cannot retrieve the outer loop bounds.
   auto OuterLoopLB = OuterLoop.getBounds(SE);
   if (OuterLoopLB == None) {
     LLVM_DEBUG(dbgs() << "Cannot compute loop bounds of OuterLoop: "
                       << OuterLoop << "\n";);
-    return false;
+    return OuterLoopLowerBoundUnknown;
   }
 
-  // Identify the outer loop latch comparison instruction.
-  const BasicBlock *Latch = OuterLoop.getLoopLatch();
-  assert(Latch && "Expecting a valid loop latch");
-  const BranchInst *BI = dyn_cast<BranchInst>(Latch->getTerminator());
-  assert(BI && BI->isConditional() &&
-         "Expecting loop latch terminator to be a branch instruction");
-
-  const CmpInst *OuterLoopLatchCmp = dyn_cast<CmpInst>(BI->getCondition());
-  DEBUG_WITH_TYPE(
-      VerboseDebug, if (OuterLoopLatchCmp) {
-        dbgs() << "Outer loop latch compare instruction: " << *OuterLoopLatchCmp
-               << "\n";
-      });
-
-  // Identify the inner loop guard instruction.
-  BranchInst *InnerGuard = InnerLoop.getLoopGuardBranch();
-  const CmpInst *InnerLoopGuardCmp =
-      (InnerGuard) ? dyn_cast<CmpInst>(InnerGuard->getCondition()) : nullptr;
-
-  DEBUG_WITH_TYPE(
-      VerboseDebug, if (InnerLoopGuardCmp) {
-        dbgs() << "Inner loop guard compare instruction: " << *InnerLoopGuardCmp
-               << "\n";
-      });
+  CmpInst *OuterLoopLatchCmp = getOuterLoopLatchCmp(OuterLoop);
+  CmpInst *InnerLoopGuardCmp = getInnerLoopGuardCmp(InnerLoop);
 
   // Determine whether instructions in a basic block are one of:
   //  - the inner loop guard comparison
   //  - the outer loop latch comparison
   //  - the outer loop induction variable increment
   //  - a phi node, a cast or a branch
   auto containsOnlySafeInstructions = [&](const BasicBlock &BB) {
     return llvm::all_of(BB, [&](const Instruction &I) {
-      bool isAllowed = isSafeToSpeculativelyExecute(&I) || isa<PHINode>(I) ||
-                       isa<BranchInst>(I);
-      if (!isAllowed) {
-        DEBUG_WITH_TYPE(VerboseDebug, {
-          dbgs() << "Instruction: " << I << "\nin basic block: " << BB
-                 << " is considered unsafe.\n";
-        });
-        return false;
-      }
-
-      // The only binary instruction allowed is the outer loop step instruction,
-      // the only comparison instructions allowed are the inner loop guard
-      // compare instruction and the outer loop latch compare instruction.
-      if ((isa<BinaryOperator>(I) && &I != &OuterLoopLB->getStepInst()) ||
-          (isa<CmpInst>(I) && &I != OuterLoopLatchCmp &&
-           &I != InnerLoopGuardCmp)) {
+      bool IsSafeInstr = checkSafeInstruction(I, InnerLoopGuardCmp,
+                                              OuterLoopLatchCmp, OuterLoopLB);
+      if (IsSafeInstr) {
         DEBUG_WITH_TYPE(VerboseDebug, {
           dbgs() << "Instruction: " << I << "\nin basic block:" << BB
                  << "is unsafe.\n";
         });
-        return false;
       }
-      return true;
+      return IsSafeInstr;
     });
   };
 
   // Check the code surrounding the inner loop for instructions that are deemed
   // unsafe.
   const BasicBlock *OuterLoopHeader = OuterLoop.getHeader();
   const BasicBlock *OuterLoopLatch = OuterLoop.getLoopLatch();
   const BasicBlock *InnerLoopPreHeader = InnerLoop.getLoopPreheader();
 
   if (!containsOnlySafeInstructions(*OuterLoopHeader) ||
       !containsOnlySafeInstructions(*OuterLoopLatch) ||
       (InnerLoopPreHeader != OuterLoopHeader &&
        !containsOnlySafeInstructions(*InnerLoopPreHeader)) ||
       !containsOnlySafeInstructions(*InnerLoop.getExitBlock())) {
     LLVM_DEBUG(dbgs() << "Not perfectly nested: code surrounding inner loop is "
                          "unsafe\n";);
-    return false;
+    return ImperfectLoopNest;
   }
 
   LLVM_DEBUG(dbgs() << "Loop '" << OuterLoop.getName() << "' and '"
                     << InnerLoop.getName() << "' are perfectly nested.\n");
 
-  return true;
+  return PerfectLoopNest;
+}
+
+LoopNest::InstrVectorTy LoopNest::getInterveningInstructions(
+    const Loop &OuterLoop, const Loop &InnerLoop, ScalarEvolution &SE) {
+  InstrVectorTy Instr;
+  switch (analyzeLoopNestForPerfectNest(OuterLoop, InnerLoop, SE)) {
+  case PerfectLoopNest:
+    LLVM_DEBUG(dbgs() << "The loop Nest is Perfect, returning empty "
+                         "instruction vector. \n";);
+    return Instr;
+
+  case InvalidLoopStructure:
+    LLVM_DEBUG(dbgs() << "Not perfectly nested: invalid loop structure. "
+                         "Instruction vector is empty.\n";);
+    return Instr;
+
+  case OuterLoopLowerBoundUnknown:
+    LLVM_DEBUG(dbgs() << "Cannot compute loop bounds of OuterLoop: "
+                      << OuterLoop << "\nInstruction vector is empty.\n";);
+    return Instr;
+
+  case ImperfectLoopNest:
+    break;
+  }
+
+  // Identify the outer loop latch comparison instruction.
+  auto OuterLoopLB = OuterLoop.getBounds(SE);
+
+  CmpInst *OuterLoopLatchCmp = getOuterLoopLatchCmp(OuterLoop);
+  CmpInst *InnerLoopGuardCmp = getInnerLoopGuardCmp(InnerLoop);
+
+  auto GetUnsafeInstructions = [&](const BasicBlock &BB) {
+    for (const Instruction &I : BB) {
+      if (!checkSafeInstruction(I, InnerLoopGuardCmp, OuterLoopLatchCmp,
+                                OuterLoopLB)) {
+        Instr.push_back(&I);
+        DEBUG_WITH_TYPE(VerboseDebug, {
+          dbgs() << "Instruction: " << I << "\nin basic block:" << BB
+                 << "is unsafe.\n";
+        });
+      }
+    }
+  };
+
+  // Check the code surrounding the inner loop for instructions that are deemed
+  // unsafe.
+  const BasicBlock *OuterLoopHeader = OuterLoop.getHeader();
+  const BasicBlock *OuterLoopLatch = OuterLoop.getLoopLatch();
+  const BasicBlock *InnerLoopPreHeader = InnerLoop.getLoopPreheader();
+  const BasicBlock *InnerLoopExitBlock = InnerLoop.getExitBlock();
+
+  GetUnsafeInstructions(*OuterLoopHeader);
+  GetUnsafeInstructions(*OuterLoopLatch);
+  GetUnsafeInstructions(*InnerLoopExitBlock);
+
+  if (InnerLoopPreHeader != OuterLoopHeader) {
+    GetUnsafeInstructions(*InnerLoopPreHeader);
+  }
+  return Instr;
 }
 
 SmallVector<LoopVectorTy, 4>
 LoopNest::getPerfectLoops(ScalarEvolution &SE) const {
   SmallVector<LoopVectorTy, 4> LV;
   LoopVectorTy PerfectNest;
 
   for (Loop *L : depth_first(const_cast<Loop *>(Loops.front()))) {

llvm/unittests/Analysis/LoopNestTest.cpp

 }
 
 static std::unique_ptr<Module> makeLLVMModule(LLVMContext &Context,
                                               const char *ModuleStr) {
   SMDiagnostic Err;
   return parseAssemblyString(ModuleStr, Err, Context);
 }
 
+static Instruction *getInstructionByName(Function &F, StringRef Name) {
+  for (BasicBlock &BB : F)
+    for (Instruction &I : BB)
+      if (I.getName() == Name)
+        return &I;
+  llvm_unreachable("Expected to find instruction!");
+}
+
 TEST(LoopNestTest, PerfectLoopNest) {
   const char *ModuleStr =
     "target datalayout = \"e-m:o-i64:64-f80:128-n8:16:32:64-S128\"\n"
     "define void @foo(i64 signext %nx, i64 signext %ny) {\n"
     "entry:\n"
     "  br label %for.outer\n"
     "for.outer:\n"
     "  %i = phi i64 [ 0, %entry ], [ %inc13, %for.outer.latch ]\n"
runTest(*M, "foo", [&](Function &F, LoopInfo &LI, ScalarEvolution &SE) {
     // Ensure the loop nest is recognized as perfect in its entirety.
     const SmallVector<LoopVectorTy, 4> &PLV = LN.getPerfectLoops(SE);
     EXPECT_EQ(PLV.size(), 1ull);
     EXPECT_EQ(PLV.front().size(), 2ull);
 
     // Ensure the nest depth and perfect nest depth are computed correctly.
     EXPECT_EQ(LN.getNestDepth(), 2u);
     EXPECT_EQ(LN.getMaxPerfectDepth(), 2u);
+
+    EXPECT_TRUE(LN.getInterveningInstructions(OL, *IL, SE).empty());
   });
 }
 
 TEST(LoopNestTest, ImperfectLoopNest) {
   const char *ModuleStr =
       "target datalayout = \"e-m:o-i64:64-f80:128-n8:16:32:64-S128\"\n"
       "define void @foo(i32 signext %nx, i32 signext %ny, i32 signext %nk) {\n"
       "entry:\n"
runTest(*M, "foo", [&](Function &F, LoopInfo &LI, ScalarEvolution &SE) {
     const SmallVector<LoopVectorTy, 4> &PLV = LN.getPerfectLoops(SE);
     EXPECT_EQ(PLV.size(), 2ull);
     EXPECT_EQ(PLV.front().size(), 2ull);
     EXPECT_EQ(PLV.back().size(), 1ull);
 
     // Ensure the nest depth and perfect nest depth are computed correctly.
     EXPECT_EQ(LN.getNestDepth(), 3u);
     EXPECT_EQ(LN.getMaxPerfectDepth(), 2u);
+
+    EXPECT_TRUE(LN.getInterveningInstructions(OL, *IL, SE).empty());
   });
 }
 
+TEST(LoopNestTest, InterveningInstrLoopNest) {
+  const char *ModuleStr =
+      "target datalayout = \"e-m:o-i64:64-f80:128-n8:16:32:64-S128\"\n"
+      "define void @foo(i64 signext %nx, i64 signext %ny, i32* noalias %A, i32 "
+      "%op0, i32 %op1){\n"
+      "entry:\n"
+      "  br label %for.outer\n"
+      "for.outer:\n"
+      "  %i = phi i64 [ 0, %entry ], [ %inc13, %for.outer.latch ]\n"
+      "  %cmp21 = icmp slt i64 0, %ny\n"
+      "  call void @outerheader()\n"
+      "  br i1 %cmp21, label %for.inner.preheader, label %for.outer.latch\n"
+      "for.inner.preheader:\n"
+      "  %varr = getelementptr inbounds i32, i32* %A, i64 5\n"
+      "  store i32 5, i32* %varr, align 4\n"
+      "  call void @innerpreheader()\n"
+      "  br label %for.inner\n"
+      "for.inner:\n"
+      "  %j = phi i64 [ 0, %for.inner.preheader ], [ %inc, %for.inner.latch ]\n"
+      "  br label %for.inner.latch\n"
+      "for.inner.latch:\n"
+      "  %inc = add nsw i64 %j, 1\n"
+      "  %cmp2 = icmp slt i64 %inc, %ny\n"
+      "  br i1 %cmp2, label %for.inner, label %for.inner.exit\n"
+      "for.inner.exit:\n"
+      "  %varr1 = getelementptr inbounds i32, i32* %A, i64 5\n"
+      "  call void @innerexit()\n"
+      "  br label %for.outer.latch\n"
+      "for.outer.latch:\n"
+      "  %inc13 = add nsw i64 %i, 1\n"
+      "  call void @outerlatch()\n"
+      "  %cmp = icmp slt i64 %inc13, %nx\n"
+      "  br i1 %cmp, label %for.outer, label %for.outer.exit\n"
+      "for.outer.exit:\n"
+      "  br label %for.end\n"
+      "for.end:\n"
+      "  ret void\n"
+      "}\n"
+      "declare void @innerpreheader()\n"
+      "declare void @outerheader()\n"
+      "declare void @outerlatch()\n"
+      "declare void @innerexit()\n";
+
+  LLVMContext Context;
+  std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleStr);
+
+  runTest(*M, "foo", [&](Function &F, LoopInfo &LI, ScalarEvolution &SE) {
+    Function::iterator FI = F.begin();
+    // Skip the first basic block (entry), get to the outer loop header.
+    BasicBlock *Header = &*(++FI);
+    assert(Header->getName() == "for.outer");
+    Loop *L = LI.getLoopFor(Header);
+    EXPECT_NE(L, nullptr);
+
+    LoopNest LN(*L, SE);
+    EXPECT_TRUE(LN.areAllLoopsSimplifyForm());
+
+    // Ensure that we can identify the outermost loop in the nest.
+    const Loop &OL = LN.getOutermostLoop();
+    EXPECT_EQ(OL.getName(), "for.outer");
+
+    // Ensure that we can identify the innermost loop in the nest.
+    const Loop *IL = LN.getInnermostLoop();
+    EXPECT_NE(IL, nullptr);
+    EXPECT_EQ(IL->getName(), "for.inner");
+
+    // Ensure the loop nest is recognized as having 2 loops.
+    const ArrayRef<Loop *> Loops = LN.getLoops();
+    EXPECT_EQ(Loops.size(), 2ull);
+
+    // Ensure the loop nest is not recognized as perfect in its entirety.
+    const SmallVector<LoopVectorTy, 4> &PLV = LN.getPerfectLoops(SE);
+    EXPECT_EQ(PLV.size(), 2ull);
+    EXPECT_EQ(PLV.front().size(), 1ull);
+    EXPECT_EQ(PLV.back().size(), 1ull);
+
+    // Ensure the nest depth and perfect nest depth are computed correctly.
+    EXPECT_EQ(LN.getNestDepth(), 2u);
+    EXPECT_EQ(LN.getMaxPerfectDepth(), 1u);
+
+    // Ensure enclosed instructions are recognized
+    const LoopNest::InstrVectorTy InstrV =
+        LN.getInterveningInstructions(OL, *IL, SE);
+    EXPECT_EQ(InstrV.size(), 5u);
+
+    Instruction *SI = getInstructionByName(F, "varr")->getNextNode();
+    Instruction *CI = SI->getNextNode();
+    Instruction *OLH =
+        getInstructionByName(F, "i")->getNextNode()->getNextNode();
+    Instruction *OLL = getInstructionByName(F, "inc13")->getNextNode();
+    Instruction *IE = getInstructionByName(F, "varr1")->getNextNode();
+
+    EXPECT_EQ(InstrV.front(), OLH);
+    EXPECT_EQ(InstrV[1], OLL);
+    EXPECT_EQ(InstrV[2], IE);
+    EXPECT_EQ(InstrV[3], SI);
+    EXPECT_EQ(InstrV.back(), CI);
+  });
+}