[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

214

I'd prefer them as separate asserts.

223

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

226

[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

223

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

223

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/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"
 
 using namespace llvm;
 
 #define DEBUG_TYPE "loopnest"
 #ifndef NDEBUG
 static const char *VerboseDebug = DEBUG_TYPE "-verbose";
 #endif
 
 /// Determine whether the loops structure violates basic requirements for
while (SubLoops->size() == 1) {
     CurrentLoop = InnerLoop;
     SubLoops = &CurrentLoop->getSubLoops();
     ++CurrentDepth;
   }
 
   return CurrentDepth;
 }
 
+/// 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) {
+  assert((From != nullptr && End != nullptr) && "Expecting valid arguments");
+
+  if (From == End || !From->getSingleSuccessor())
+    return *From;
+
+  auto isEmpty = [](const BasicBlock *BB) {
+    return (BB->getInstList().size() == 1);
+  };
+
+  SmallPtrSet<const BasicBlock *, 4> Visited;
+  const BasicBlock *BB = From->getSingleSuccessor();
+  const BasicBlock *PredBB = BB;
+  while (BB && BB != End && isEmpty(BB) && Visited.count(BB) == 0) {
+    Visited.insert(BB);
+    PredBB = BB;
+    BB = BB->getSingleSuccessor();
+  }
+
+  return (BB == End) ? *End : *PredBB;
+}
+
 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...
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.
       for (const BasicBlock *Succ : BI->successors()) {
         if (Succ == InnerLoopPreHeader)
           continue;
         if (Succ == 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/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 %perf_nest_2D_3_loop_j, label %inc_i
+
+perf_nest_2D_3_loop_j:
+  %j = phi i64 [ 0, %singleSucc ], [ %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.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) {