[LoopNest] Allow empty basic blocks without loops

[Whitney]

Summary

Allow loop nests with empty basic blocks without loops in different levels as perfect.

[Meinersbur]

Alternatively, we could rely on SimplifyCFG to remote such empty BBs?

Would we want to allow such empty blocks between outer header and inner preheader as well?

llvm/lib/Analysis/LoopNestAnalysis.cpp

215

I'd prefer them as separate asserts.

224

To clarify: the Visited set is used to detect an infinite loop?

227

[Whitney]

• Addressed review comments
• Moved skipEmptyBlockUntil to BasicBlockUtils, because it is not specific to loop nest.

[Whitney]

Alternatively, we could rely on SimplifyCFG to remote such empty BBs?

SimplifyCFG could be used to fold empty blocks, but we may want to know if the loop nest is perfect in between SimplifyCFG invocations.
And there are times where we intentionally have empty blocks, e.g. dedicated exits.

Would we want to allow such empty blocks between outer header and inner preheader as well?

It is being allowed in this patch,

if (OuterLoopHeader != InnerLoopPreHeader) {
  const BasicBlock &SingleSucc =
      skipEmptyBlockUntil(OuterLoopHeader, InnerLoopPreHeader);

  // no conditional branch present
  if (&SingleSucc != InnerLoopPreHeader) {

llvm/lib/Analysis/LoopNestAnalysis.cpp

224

Yes, to avoid running into an infinite loop.

[Whitney]

Allow empty blocks between inner loop guard successor to inner loop preheader or inner loop guard successor the outer loop latch.

[Whitney]

ping

[Meinersbur]

LGTM

llvm/lib/Analysis/LoopNestAnalysis.cpp

224

Could you add a comment to clarify?

[Whitney]

Added comment to clarify Visited.

[Whitney]

Reverted, due to http://lab.llvm.org:8011/#/builders/112/builds/2681

[Whitney]

Fix BUILD_SHARED_LIBS build failure.

[dblaikie]

llvm/lib/Analysis/LoopNestAnalysis.cpp

19

While not, I think, technically impossible - this is a rather "interesting" dependency to add. (generally Analysis can't depend on Transforms, because Transforms depend on Analysis - though Transforms/Utils doesn't depend on Transforms, so we can have the diamond of Analysis depends on Transforms and Transforms and Analysis depend on Transforms/Utils)

But this is missing the CMakeLists.txt update to indicate that Analysis depends on TransformUtils.

While the dependency is technically possible, I think it might be better to revert this patch (& later ones in the series) before having a broader discussion (possibly on llvm-dev) about this new dependency due to its subtlety. Perhaps some utilities should move to Analysis or an Analysis/Utils, or an IR/Utils instead of living in Transforms/Utils, if they aren't actually doing transformations?

[Meinersbur]

llvm/lib/Analysis/LoopNestAnalysis.cpp

19

I think this header is not needed anymore. It was included for skipEmptyBlockUntil, but this function has been moved to Analysis/LoopNestAnalysis.h because of the BUILD_SHARED_LIBS build failure which resultet from the layering violation you are referring to.

@Whitney Can you remove this #include in trunk/main?

[Whitney]

llvm/lib/Analysis/LoopNestAnalysis.cpp

19

opps, this include is no longer needed, I just forgot to remove it.
Thanks for pointing it out.

[Whitney]

llvm/lib/Analysis/LoopNestAnalysis.cpp

19

@Meinersbur Yes, you beat me to it.

llvm/include/llvm/Analysis/LoopNestAnalysis.h

public:
   unsigned getMaxPerfectDepth() const { return MaxPerfectDepth; }
 
   /// Return true if all loops in the loop nest are in simplify form.
   bool areAllLoopsSimplifyForm() const {
     return llvm::all_of(Loops,
                         [](const Loop *L) { return L->isLoopSimplifyForm(); });
   }
 
+  /// Return true if all loops in the loop nest are in rotated form.
+  bool areAllLoopsRotatedForm() const {
+    return std::all_of(Loops.begin(), Loops.end(),
+                       [](const Loop *L) { return L->isRotatedForm(); });
+  }
+
   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).
 };
 
 raw_ostream &operator<<(raw_ostream &, const LoopNest &);

llvm/include/llvm/Transforms/Utils/BasicBlockUtils.h

 }
 
 /// Loop over all of the edges in the CFG, breaking critical edges as they are
 /// found. Returns the number of broken edges.
 unsigned SplitAllCriticalEdges(Function &F,
                                const CriticalEdgeSplittingOptions &Options =
                                    CriticalEdgeSplittingOptions());
 
+/// Recursivelly traverse all empty 'single successor' basic blocks of \p From
+/// (if there are any). Return the last basic block found or \p End if it was
+/// reached during the search.
+const BasicBlock &skipEmptyBlockUntil(const BasicBlock *From,
+                                      const BasicBlock *End);
+
 /// Split the edge connecting the specified blocks, and return the newly created
 /// basic block between \p From and \p To.
 BasicBlock *SplitEdge(BasicBlock *From, BasicBlock *To,
                       DominatorTree *DT = nullptr, LoopInfo *LI = nullptr,
                       MemorySSAUpdater *MSSAU = nullptr);
 
 /// Split the specified block at the specified instruction.
 ///

llvm/lib/Analysis/LoopNestAnalysis.cpp

 ///
 //===----------------------------------------------------------------------===//
 
 #include "llvm/Analysis/LoopNestAnalysis.h"
 #include "llvm/ADT/BreadthFirstIterator.h"
 #include "llvm/ADT/Statistic.h"
 #include "llvm/Analysis/PostDominators.h"
 #include "llvm/Analysis/ValueTracking.h"
+#include "llvm/Transforms/Utils/BasicBlockUtils.h"
 
 using namespace llvm;
 
 #define DEBUG_TYPE "loopnest"
 #ifndef NDEBUG
 static const char *VerboseDebug = DEBUG_TYPE "-verbose";
 #endif
 
unsigned LoopNest::getMaxPerfectDepth(const Loop &Root, ScalarEvolution &SE) {
   return CurrentDepth;
 }
 
 static bool checkLoopsStructure(const Loop &OuterLoop, const Loop &InnerLoop,
                                 ScalarEvolution &SE) {
   // The inner loop must be the only outer loop's child.
   if ((OuterLoop.getSubLoops().size() != 1) ||
       (InnerLoop.getParentLoop() != &OuterLoop))
     return false;
 
   // We expect loops in normal form which have a preheader, header, latch...
   if (!OuterLoop.isLoopSimplifyForm() || !InnerLoop.isLoopSimplifyForm())
     return false;
 
   const BasicBlock *OuterLoopHeader = OuterLoop.getHeader();
   const BasicBlock *OuterLoopLatch = OuterLoop.getLoopLatch();
   const BasicBlock *InnerLoopPreHeader = InnerLoop.getLoopPreheader();
   const BasicBlock *InnerLoopLatch = InnerLoop.getLoopLatch();
   const BasicBlock *InnerLoopExit = InnerLoop.getExitBlock();
 
   // We expect rotated loops. The inner loop should have a single exit block.
   if (OuterLoop.getExitingBlock() != OuterLoopLatch ||
       InnerLoop.getExitingBlock() != InnerLoopLatch || !InnerLoopExit)
     return false;
 
   // Returns whether the block `ExitBlock` contains at least one LCSSA Phi node.
   auto ContainsLCSSAPhi = [](const BasicBlock &ExitBlock) {
     return any_of(ExitBlock.phis(), [](const PHINode &PN) {
       return PN.getNumIncomingValues() == 1;
return BB.getFirstNonPHI() == BB.getTerminator() &&
              });
            });
   };
 
   const BasicBlock *ExtraPhiBlock = nullptr;
   // Ensure the only branch that may exist between the loops is the inner loop
   // guard.
   if (OuterLoopHeader != InnerLoopPreHeader) {
-    const BranchInst *BI =
-        dyn_cast<BranchInst>(OuterLoopHeader->getTerminator());
+    const BasicBlock &SingleSucc =
+        skipEmptyBlockUntil(OuterLoopHeader, InnerLoopPreHeader);
+
+    // no conditional branch present
+    if (&SingleSucc != InnerLoopPreHeader) {
+      const BranchInst *BI = dyn_cast<BranchInst>(SingleSucc.getTerminator());
 
       if (!BI || BI != InnerLoop.getLoopGuardBranch())
         return false;
 
       bool InnerLoopExitContainsLCSSA = ContainsLCSSAPhi(*InnerLoopExit);
 
       // The successors of the inner loop guard should be the inner loop
-    // preheader and the outer loop latch.
+      // preheader or the outer loop latch possibly through empty blocks.
       for (const BasicBlock *Succ : BI->successors()) {
-      if (Succ == InnerLoopPreHeader)
+        const BasicBlock *PotentialInnerPreHeader = Succ;
+        const BasicBlock *PotentialOuterLatch = Succ;
+
+        // Ensure the inner loop guard successor is empty before skipping
+        // blocks.
+        if (Succ->getInstList().size() == 1) {
+          PotentialInnerPreHeader =
+              &skipEmptyBlockUntil(Succ, InnerLoopPreHeader);
+          PotentialOuterLatch = &skipEmptyBlockUntil(Succ, OuterLoopLatch);
+        }
+
+        if (PotentialInnerPreHeader == InnerLoopPreHeader)
           continue;
-      if (Succ == OuterLoopLatch)
+        if (PotentialOuterLatch == OuterLoopLatch)
           continue;
 
         // If `InnerLoopExit` contains LCSSA Phi instructions, additional block
         // may be inserted before the `OuterLoopLatch` to which `BI` jumps. The
         // loops are still considered perfectly nested if the extra block only
         // contains Phi instructions from InnerLoopExit and OuterLoopHeader.
         if (InnerLoopExitContainsLCSSA && IsExtraPhiBlock(*Succ) &&
             Succ->getSingleSuccessor() == OuterLoopLatch) {
           // Points to the extra block so that we can reference it later in the
           // final check. We can also conclude that the inner loop is
-        // guarded and there exists LCSSA Phi node in the exit block later if we
-        // see a non-null `ExtraPhiBlock`.
+          // guarded and there exists LCSSA Phi node in the exit block later if
+          // we see a non-null `ExtraPhiBlock`.
           ExtraPhiBlock = Succ;
           continue;
         }
 
         DEBUG_WITH_TYPE(VerboseDebug, {
           dbgs() << "Inner loop guard successor " << Succ->getName()
                  << " doesn't lead to inner loop preheader or "
                     "outer loop latch.\n";
         });
         return false;
       }
     }
+  }
 
-  // Ensure the inner loop exit block leads to the outer loop latch.
-  const BasicBlock *SuccInner = InnerLoopExit->getSingleSuccessor();
-  if (!SuccInner ||
-      (SuccInner != OuterLoopLatch && SuccInner != ExtraPhiBlock)) {
+  // Ensure the inner loop exit block lead to the outer loop latch possibly
+  // through empty blocks.
+  const BasicBlock &SuccInner =
+      skipEmptyBlockUntil(InnerLoop.getExitBlock(), OuterLoopLatch);
+  if (&SuccInner != OuterLoopLatch && &SuccInner != ExtraPhiBlock) {
     DEBUG_WITH_TYPE(
         VerboseDebug,
         dbgs() << "Inner loop exit block " << *InnerLoopExit
                << " does not directly lead to the outer loop latch.\n";);
     return false;
   }
 
   return true;

llvm/lib/Transforms/Utils/BasicBlockUtils.cpp

void llvm::ReplaceInstWithInst(BasicBlock::InstListType &BIL,
   BI = New;
 }
 
 void llvm::ReplaceInstWithInst(Instruction *From, Instruction *To) {
   BasicBlock::iterator BI(From);
   ReplaceInstWithInst(From->getParent()->getInstList(), BI, To);
 }
 
+const BasicBlock &llvm::skipEmptyBlockUntil(const BasicBlock *From,
+                                            const BasicBlock *End) {
+  assert(From && "Expecting valid From");
+  assert(End && "Expecting valid End");
+
+  if (From == End || !From->getSingleSuccessor())
+    return *From;
+
+  auto IsEmpty = [](const BasicBlock *BB) {
+    return (BB->getInstList().size() == 1);
+  };
+
+  // Visited is used to avoid running into an infinite loop.
+  SmallPtrSet<const BasicBlock *, 4> Visited;
+  const BasicBlock *BB = From->getSingleSuccessor();
+  const BasicBlock *PredBB = BB;
+  while (BB && BB != End && IsEmpty(BB) && !Visited.count(BB)) {
+    Visited.insert(BB);
+    PredBB = BB;
+    BB = BB->getSingleSuccessor();
+  }
+
+  return (BB == End) ? *End : *PredBB;
+}
+
 BasicBlock *llvm::SplitEdge(BasicBlock *BB, BasicBlock *Succ, DominatorTree *DT,
                             LoopInfo *LI, MemorySSAUpdater *MSSAU) {
   unsigned SuccNum = GetSuccessorNumber(BB, Succ);
 
   // If this is a critical edge, let SplitCriticalEdge do it.
   Instruction *LatchTerm = BB->getTerminator();
   if (SplitCriticalEdge(
           LatchTerm, SuccNum,

llvm/test/Analysis/LoopNestAnalysis/perfectnest.ll

inc_i:
   %inc13 = add nsw i64 %i, 1
   %cmp = icmp slt i64 %inc13, 100
   br i1 %cmp, label %perf_nest_2D_2_loop_i, label %perf_nest_2D_2_loop_i_end
 
 perf_nest_2D_2_loop_i_end:
   ret void
 }
 
+define void @perf_nest_2D_3(i32** %y, i32** %x, i64 signext %nx, i64 signext %ny) {
+; CHECK-LABEL: IsPerfect=true, Depth=1, OutermostLoop: perf_nest_2D_3_loop_j, Loops: ( perf_nest_2D_3_loop_j )
+; CHECK-LABEL: IsPerfect=true, Depth=2, OutermostLoop: perf_nest_2D_3_loop_i, Loops: ( perf_nest_2D_3_loop_i perf_nest_2D_3_loop_j )
+entry:
+  br label %perf_nest_2D_3_loop_i
+
+perf_nest_2D_3_loop_i:
+  %i = phi i64 [ 0, %entry ], [ %inc13, %inc_i ]
+  %cmp21 = icmp slt i64 0, %ny
+  br label %singleSucc
+
+singleSucc:
+  br i1 %cmp21, label %preheader.j, label %for.end
+
+preheader.j:
+  br label %perf_nest_2D_3_loop_j
+
+perf_nest_2D_3_loop_j:
+  %j = phi i64 [ 0, %preheader.j ], [ %inc, %inc_j ]
+  %arrayidx = getelementptr inbounds i32*, i32** %x, i64 %j
+  %0 = load i32*, i32** %arrayidx, align 8
+  %arrayidx6 = getelementptr inbounds i32, i32* %0, i64 %j
+  %1 = load i32, i32* %arrayidx6, align 4
+  %arrayidx8 = getelementptr inbounds i32*, i32** %y, i64 %j
+  %2 = load i32*, i32** %arrayidx8, align 8
+  %arrayidx11 = getelementptr inbounds i32, i32* %2, i64 %i
+  store i32 %1, i32* %arrayidx11, align 4
+  br label %inc_j
+
+inc_j:
+  %inc = add nsw i64 %j, 1
+  %cmp2 = icmp slt i64 %inc, %ny
+  br i1 %cmp2, label %perf_nest_2D_3_loop_j, label %for.exit
+
+for.exit:
+  br label %for.end
+
+for.end:
+  br label %inc_i
+
+inc_i:
+  %inc13 = add nsw i64 %i, 1
+  %cmp = icmp slt i64 %inc13, %nx
+  br i1 %cmp, label %perf_nest_2D_3_loop_i, label %perf_nest_2D_3_loop_i_end
+
+perf_nest_2D_3_loop_i_end:
+  ret void
+}
+
 ; Test a perfect 3-dim loop nest of the form:
 ;   for (i=0; i<nx; ++i)
 ;     for (j=0; j<ny; ++j)
 ;       for (k=0; j<nk; ++k)
 ;          y[j][j][k] = x[i][j][k];
 ;
 
 define void @perf_nest_3D_1(i32*** %y, i32*** %x, i32 signext %nx, i32 signext %ny, i32 signext %nk) {