[LoopNest] Consider loop nest with inner loop guard using outer loop induction variable to be perfect

[Whitney]

Summary

This patch allow more conditional branches to be considered as loop guard, and so more loop nests can be considered perfect.

[Whitney]

llvm/test/Analysis/LoopNestAnalysis/imperfectnest.ll

428

This test case should be considered as imperfect, as the user branch is not the inner loop guard.

[bmahjour]

llvm/lib/Analysis/LoopInfo.cpp

409

apart from checking that the control flow can be simplified, we also need to check to make sure that the chain of BBs don't contain unsafe instructions (or at least check that they are empty).

llvm/test/Analysis/LoopNestAnalysis/imperfectnest.ll

428

the user branch is behaving as a guard so we can allow it per the current definition of a loop guard.

[sidbav]

Ensure the chain of BBs are empty blocks.

[bmahjour]

llvm/lib/Analysis/LoopInfo.cpp

402

[nit] this comment needs to be reworded to be more clear.

405

AFAICS skipEmptyBlockUntil doesn't check that the unique successor blocks have unique predecessors. Don't we need to check for that too?

[Whitney]

llvm/lib/Analysis/LoopInfo.cpp

405

I thought about that too, but it seems to be questionable...

if (cond)
  goto label;
if (0 < N) {
  for (int i = 0; i < N; ++i) {...}
label:  
}

Should we consider if (0 < N) to be a loop guard? It actually guarded the loop, but it is not a single entry single exit region.

If we decided to check for unique predecessor, it may make sense to do it in skipEmptyBlockUntil.

[bmahjour]

llvm/lib/Analysis/LoopInfo.cpp

405

I think we should keep the control-flow cases that are considered "guard-like" fairly simple (otherwise transforms will be faced with too many canonical forms to have to deal with). I'd say we do not consider if (0 < N) in the example above as a loop guard, given that label: is also being guarded by that condition.

There may be legitimate use cases for the current semantics of skipEmptyBlockUntil, so I think we should create another version of that function (or pass a flag to it) to additionally check for existence of unique predecessors. Then we could use that version of the function here to decide whether the control flow structure should be considered a guard. @sidbav could you please do that?

[sidbav]

Modify skipEmptyBlockUntil to also consider unique predecessors.

[sidbav]

llvm/lib/Analysis/LoopInfo.cpp

405

Yes, I intended on adding adding it, but I ran into LIT test issues so I did not put those changes in the patch.... Just took another look at it, and I realized I made a mistake in the initial implementation. It is working now.

[Whitney]

llvm/include/llvm/Analysis/LoopNestAnalysis.h

65

Please update the description.

llvm/lib/Analysis/LoopInfo.cpp

405

@sidbav Can you please add a unit test in llvm/unittests/Analysis/LoopInfoTest.cpp for a test case like

if (cond)
  goto label;
if (0 < N) {
  for (int i = 0; i < N; ++i) {...}
label:  
}

where the branch if (0 < N) should be not a guard.

[bmahjour]

llvm/include/llvm/Analysis/LoopNestAnalysis.h

68

[nit] rename UniquePred -> CheckUniquePred.

llvm/lib/Analysis/LoopInfo.cpp

407

[nit] rename UniquePred -> CheckUniquePred.

llvm/lib/Analysis/LoopNestAnalysis.cpp

210

[nit] rename UniquePred -> CheckUniquePred.

[sidbav]

address review comments

[sidbav]

The previous Solution to bug was more of a hack rather than a fix. This patch actually resolves the bug

[bmahjour]

I think this changes the semantics for the cases that we used to handle before. For example wouldn't this require the exit successors to be empty? If so I think lcssa phis can prevent us from detecting guards. We need to test for those cases as well.

[Whitney]

In D94717#2730582, @bmahjour wrote:

I think this changes the semantics for the cases that we used to handle before. For example wouldn't this require the exit successors to be empty? If so I think lcssa phis can prevent us from detecting guards. We need to test for those cases as well.

LCSSA phis should be in the loop exit block, not exit successors.

[bmahjour]

In D94717#2730948, @Whitney wrote:

In D94717#2730582, @bmahjour wrote:

I think this changes the semantics for the cases that we used to handle before. For example wouldn't this require the exit successors to be empty? If so I think lcssa phis can prevent us from detecting guards. We need to test for those cases as well.

LCSSA phis should be in the loop exit block, not exit successors.

int foo(char * restrict aa, int N) {
  int sum = 0;
  for (int i = 0; i < N; i++) {
    sum += aa[i];
  }
  return sum;
}

The corresponding IR would be:

define dso_local signext i32 @foo(i8* noalias %aa, i32 signext %N) #0 {
entry:
  %cmp1 = icmp sgt i32 %N, 0
  br i1 %cmp1, label %for.body.preheader, label %for.end

for.body.preheader:                               ; preds = %entry
  %wide.trip.count = zext i32 %N to i64
  br label %for.body

for.body:                                         ; preds = %for.body.preheader, %for.body
  %indvars.iv = phi i64 [ 0, %for.body.preheader ], [ %indvars.iv.next, %for.body ]
  %sum.02 = phi i32 [ %add, %for.body ], [ 0, %for.body.preheader ]
  %arrayidx = getelementptr inbounds i8, i8* %aa, i64 %indvars.iv
  %0 = load i8, i8* %arrayidx, align 1, !tbaa !2
  %conv = zext i8 %0 to i32
  %add = add nuw nsw i32 %sum.02, %conv
  %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1
  %exitcond = icmp ne i64 %indvars.iv.next, %wide.trip.count
  br i1 %exitcond, label %for.body, label %for.end.loopexit, !llvm.loop !5

for.end.loopexit:                                 ; preds = %for.body
  %add.lcssa = phi i32 [ %add, %for.body ]
  br label %for.end

for.end:                                          ; preds = %for.end.loopexit, %entry
  %sum.0.lcssa = phi i32 [ 0, %entry ], [ %add.lcssa, %for.end.loopexit ]
  ret i32 %sum.0.lcssa
}

As you can see for.end is not empty and so this loop's guard won't be detected!

[Whitney]

As you can see for.end is not empty and so this loop's guard won't be detected!

From looking at skipEmptyBlockUntil, End is not require to be empty, so skipEmptyBlockUntil(for.end.loopexit, for.end) would return for.end.

llvm/lib/Analysis/LoopInfo.cpp

384–386

These 3 lines can be removed.

llvm/lib/Analysis/LoopNestAnalysis.cpp

224

Should change this to const BasicBlock *PredBB = From;

[bmahjour]

In D94717#2737167, @Whitney wrote:

As you can see for.end is not empty and so this loop's guard won't be detected!

From looking at skipEmptyBlockUntil, End is not require to be empty, so skipEmptyBlockUntil(for.end.loopexit, for.end) would return for.end.

True, although you can have another bb in between that has code, and then we won't be able to detect the guard. I don't think we would want to limit our ability to detect a guard when there is code in the epilogue. There is also the question of what "code" is considered neutral. Perhaps we need a way to distinguish between guards that are "dedicated" and those that are not.

[Whitney]

Addressed review comments.

[bmahjour]

So if I understand correctly, we still allow code in the exit block and the other target of the guard branch like before, so this is purely an improvement over what we had before. Although, as I said before I think we should allow non-empty blocks as well, but that can come as future extensions.

llvm/include/llvm/Analysis/LoopNestAnalysis.h

66

[nit] has an unique -> has a unique

[Whitney]

In D94717#2740268, @bmahjour wrote:

So if I understand correctly, we still allow code in the exit block and the other target of the guard branch like before, so this is purely an improvement over what we had before. Although, as I said before I think we should allow non-empty blocks as well, but that can come as future extensions.

Yes, our understanding are the same.

[Whitney]

Addressed review comment, and fixed a bug in detecting perfect nest using skipEmptyBlockUntil.

[sidbav]

LGTM

llvm/include/llvm/Analysis/LoopNestAnalysis.h

public:
   ///       <code>
   ///       for(k) // loop at level 3
   /// \endcode
   /// getMaxPerfectDepth(Loop_i) would return 2.
   static unsigned getMaxPerfectDepth(const Loop &Root, ScalarEvolution &SE);
 
   /// 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.
   static const BasicBlock &skipEmptyBlockUntil(const BasicBlock *From,
-                                               const BasicBlock *End);
+                                               const BasicBlock *End,
+                                               bool UniquePred = false);
 
   /// Return the outermost loop in the loop nest.
   Loop &getOutermostLoop() const { return *Loops.front(); }
 
   /// Return the innermost loop in the loop nest if the nest has only one
   /// innermost loop, and a nullptr otherwise.
   /// Note: the innermost loop returned is not necessarily perfectly nested.
   Loop *getInnermostLoop() const {

llvm/lib/Analysis/LoopInfo.cpp

 
 #include "llvm/Analysis/LoopInfo.h"
 #include "llvm/ADT/DepthFirstIterator.h"
 #include "llvm/ADT/ScopeExit.h"
 #include "llvm/ADT/SmallPtrSet.h"
 #include "llvm/Analysis/IVDescriptors.h"
 #include "llvm/Analysis/LoopInfoImpl.h"
 #include "llvm/Analysis/LoopIterator.h"
+#include "llvm/Analysis/LoopNestAnalysis.h"
 #include "llvm/Analysis/MemorySSA.h"
 #include "llvm/Analysis/MemorySSAUpdater.h"
 #include "llvm/Analysis/ScalarEvolutionExpressions.h"
 #include "llvm/Analysis/ValueTracking.h"
 #include "llvm/Config/llvm-config.h"
 #include "llvm/IR/CFG.h"
 #include "llvm/IR/Constants.h"
 #include "llvm/IR/DebugLoc.h"
if (!isRotatedForm())
     return nullptr;
 
   // Disallow loops with more than one unique exit block, as we do not verify
   // that GuardOtherSucc post dominates all exit blocks.
   BasicBlock *ExitFromLatch = getUniqueExitBlock();
   if (!ExitFromLatch)
     return nullptr;
 
   BasicBlock *ExitFromLatchSucc = ExitFromLatch->getUniqueSuccessor();
   if (!ExitFromLatchSucc)
     return nullptr;
 
   BasicBlock *GuardBB = Preheader->getUniquePredecessor();
   if (!GuardBB)
     return nullptr;
 
   assert(GuardBB->getTerminator() && "Expecting valid guard terminator");
 
   BranchInst *GuardBI = dyn_cast<BranchInst>(GuardBB->getTerminator());
   if (!GuardBI || GuardBI->isUnconditional())
     return nullptr;
 
   BasicBlock *GuardOtherSucc = (GuardBI->getSuccessor(0) == Preheader)
                                    ? GuardBI->getSuccessor(1)
                                    : GuardBI->getSuccessor(0);
-  return (GuardOtherSucc == ExitFromLatchSucc) ? GuardBI : nullptr;
+
+  // Check if ExitFromLatchSucc (or any BasicBlock which is an empty unique
+  // successor of ExitFromLatchSucc) is equal to GuardOtherSucc. If
+  // skipEmptyBlockUntil returns GuardOtherSucc, then the guard branch for the
+  // loop is GuardBI (return GuardBI), otherwise return nullptr.
+  if (&LoopNest::skipEmptyBlockUntil(ExitFromLatchSucc, GuardOtherSucc,
+                                     /*UniquePred=*/true) == GuardOtherSucc)
+    return GuardBI;
+  else
+    return nullptr;
 }
 
 bool Loop::isCanonical(ScalarEvolution &SE) const {
   InductionDescriptor IndDesc;
   if (!getInductionDescriptor(SE, IndDesc))
     return false;
 
   ConstantInt *Init = dyn_cast_or_null<ConstantInt>(IndDesc.getStartValue());

llvm/lib/Analysis/LoopNestAnalysis.cpp

while (SubLoops->size() == 1) {
     SubLoops = &CurrentLoop->getSubLoops();
     ++CurrentDepth;
   }
 
   return CurrentDepth;
 }
 
 const BasicBlock &LoopNest::skipEmptyBlockUntil(const BasicBlock *From,
-                                                const BasicBlock *End) {
+                                                const BasicBlock *End,
+                                                bool UniquePred) {
   assert(From && "Expecting valid From");
   assert(End && "Expecting valid End");
 
   if (From == End || !From->getUniqueSuccessor())
     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->getUniqueSuccessor();
   const BasicBlock *PredBB = BB;
-  while (BB && BB != End && IsEmpty(BB) && !Visited.count(BB)) {
+  while (BB && BB != End && IsEmpty(BB) && !Visited.count(BB) &&
+         (!UniquePred || BB->getUniquePredecessor())) {
     Visited.insert(BB);
     PredBB = BB;
     BB = BB->getUniqueSuccessor();
   }
 
   return (BB == End) ? *End : *PredBB;
 }
 

llvm/test/Analysis/LoopNestAnalysis/imperfectnest.ll

for.inc11:
   br i1 %cmp, label %imperf_nest_5_loop_i, label %for.cond.for.end13_crit_edge
 
 for.cond.for.end13_crit_edge:
   br label %for.end13
 
 for.end13:                   
   ret void
 }
-
-; Test an imperfect loop nest of the form:
-;   for (int i = 0; i < nx; ++i)
-;     if (i > 5) { // user branch
-;       for (int j = 1; j <= 5; j+=2)
-;         y[j][i] = x[i][j] + j;
-;     }
-
-define void @imperf_nest_6(i32** %y, i32** %x, i32 signext %nx, i32 signext %ny) {
-;    CHECK-LABEL: IsPerfect=false, Depth=2, OutermostLoop: imperf_nest_6_loop_i, Loops: ( imperf_nest_6_loop_i imperf_nest_6_loop_j )
-entry:
-  %cmp2 = icmp slt i32 0, %nx
-  br i1 %cmp2, label %imperf_nest_6_loop_i.lr.ph, label %for.end13
-
-imperf_nest_6_loop_i.lr.ph:
-  br label %imperf_nest_6_loop_i
-
-imperf_nest_6_loop_i:      
-  %i.0 = phi i32 [ 0, %imperf_nest_6_loop_i.lr.ph ], [ %inc12, %for.inc11 ]
-  %cmp1 = icmp sgt i32 %i.0, 5
-  br i1 %cmp1, label %imperf_nest_6_loop_j.lr.ph, label %if.end
-
-imperf_nest_6_loop_j.lr.ph:
-  br label %imperf_nest_6_loop_j
-
-imperf_nest_6_loop_j:      
-  %j.0 = phi i32 [ 1, %imperf_nest_6_loop_j.lr.ph ], [ %inc, %for.inc ]
-  %idxprom = sext i32 %i.0 to i64
-  %arrayidx = getelementptr inbounds i32*, i32** %x, i64 %idxprom
-  %0 = load i32*, i32** %arrayidx, align 8
-  %idxprom5 = sext i32 %j.0 to i64
-  %arrayidx6 = getelementptr inbounds i32, i32* %0, i64 %idxprom5
-  %1 = load i32, i32* %arrayidx6, align 4
-  %add = add nsw i32 %1, %j.0
-  %idxprom7 = sext i32 %j.0 to i64
-  %arrayidx8 = getelementptr inbounds i32*, i32** %y, i64 %idxprom7
-  %2 = load i32*, i32** %arrayidx8, align 8
-  %idxprom9 = sext i32 %i.0 to i64
-  %arrayidx10 = getelementptr inbounds i32, i32* %2, i64 %idxprom9
-  store i32 %add, i32* %arrayidx10, align 4
-  br label %for.inc
-
-for.inc:
-  %inc = add nsw i32 %j.0, 2
-  %cmp3 = icmp sle i32 %inc, 5
-  br i1 %cmp3, label %imperf_nest_6_loop_j, label %for.cond2.for.end_crit_edge
-
-for.cond2.for.end_crit_edge:
-  br label %for.end
-
-for.end:                    
-  br label %if.end
-
-if.end:                     
-  br label %for.inc11
-
-for.inc11:                  
-  %inc12 = add nsw i32 %i.0, 1
-  %cmp = icmp slt i32 %inc12, %nx
-  br i1 %cmp, label %imperf_nest_6_loop_i, label %for.cond.for.end13_crit_edge
-
-for.cond.for.end13_crit_edge:
-  br label %for.end13
-
-for.end13:                   
-  ret void
-}

llvm/test/Analysis/LoopNestAnalysis/perfectnest.ll

 for.cond.for.end7_crit_edge:
   %split7 = phi i32 [ %x.addr.1.lcssa, %for.inc5 ]
   br label %for.end7
 
 for.end7:
   %x.addr.0.lcssa = phi i32 [ %split7, %for.cond.for.end7_crit_edge ], [ %x, %entry ]
   ret i32 %x.addr.0.lcssa
 }
+
+; Test a perfect loop nest of the form:
+;   for (int i = 0; i < nx; ++i)
+;     if (i < ny) { // guard branch for the j-loop
+;       for (int j=i; j < ny; j+=1)
+;         y[j][i] = x[i][j] + j;
+;     }
+define double @perf_nest_guard_branch(i32** %y, i32** %x, i32 signext %nx, i32 signext %ny) {
+; CHECK-LABEL: IsPerfect=true, Depth=1, OutermostLoop: test6Loop2, Loops: ( test6Loop2 )
+; CHECK-LABEL: IsPerfect=true, Depth=2, OutermostLoop: test6Loop1, Loops: ( test6Loop1 test6Loop2 )
+entry:
+  %cmp2 = icmp slt i32 0, %nx
+  br i1 %cmp2, label %test6Loop1.lr.ph, label %for.end13
+
+test6Loop1.lr.ph:                                   ; preds = %entry
+  br label %test6Loop1
+
+test6Loop1:                                         ; preds = %test6Loop1.lr.ph, %for.inc11
+  %i.0 = phi i32 [ 0, %test6Loop1.lr.ph ], [ %inc12, %for.inc11 ]
+  %cmp1 = icmp slt i32 %i.0, %ny
+  br i1 %cmp1, label %test6Loop2.lr.ph, label %if.end
+
+test6Loop2.lr.ph:                                  ; preds = %if.then
+  br label %test6Loop2
+
+test6Loop2:                                        ; preds = %test6Loop2.lr.ph, %for.inc
+  %j.0 = phi i32 [ %i.0, %test6Loop2.lr.ph ], [ %inc, %for.inc ]
+  %idxprom = sext i32 %i.0 to i64
+  %arrayidx = getelementptr inbounds i32*, i32** %x, i64 %idxprom
+  %0 = load i32*, i32** %arrayidx, align 8
+  %idxprom5 = sext i32 %j.0 to i64
+  %arrayidx6 = getelementptr inbounds i32, i32* %0, i64 %idxprom5
+  %1 = load i32, i32* %arrayidx6, align 4
+  %add = add nsw i32 %1, %j.0
+  %idxprom7 = sext i32 %j.0 to i64
+  %arrayidx8 = getelementptr inbounds i32*, i32** %y, i64 %idxprom7
+  %2 = load i32*, i32** %arrayidx8, align 8
+  %idxprom9 = sext i32 %i.0 to i64
+  %arrayidx10 = getelementptr inbounds i32, i32* %2, i64 %idxprom9
+  store i32 %add, i32* %arrayidx10, align 4
+  br label %for.inc
+
+for.inc:                                          ; preds = %test6Loop2
+  %inc = add nsw i32 %j.0, 1
+  %cmp3 = icmp slt i32 %inc, %ny
+  br i1 %cmp3, label %test6Loop2, label %for.cond2.for.end_crit_edge
+
+for.cond2.for.end_crit_edge:                      ; preds = %for.inc
+  br label %for.end
+
+for.end:                                          ; preds = %for.cond2.for.end_crit_edge, %if.then
+  br label %if.end
+
+if.end:                                           ; preds = %for.end, %test6Loop1
+  br label %for.inc11
+
+for.inc11:                                        ; preds = %if.end
+  %inc12 = add nsw i32 %i.0, 1
+  %cmp = icmp slt i32 %inc12, %nx
+  br i1 %cmp, label %test6Loop1, label %for.cond.for.end13_crit_edge
+
+for.cond.for.end13_crit_edge:                     ; preds = %for.inc11
+  br label %for.end13
+
+for.end13:                                        ; preds = %for.cond.for.end13_crit_edge, %entry
+  %arrayidx14 = getelementptr inbounds i32*, i32** %y, i64 0
+  %3 = load i32*, i32** %arrayidx14, align 8
+  %arrayidx15 = getelementptr inbounds i32, i32* %3, i64 0
+  %4 = load i32, i32* %arrayidx15, align 4
+  %conv = sitofp i32 %4 to double
+  ret double %conv
+}
+
+; Test a perfect loop nest of the form:
+;   for (int i = 0; i < nx; ++i)
+;     if (i < ny) { // guard branch for the j-loop
+;       for (int j=i; j < ny; j+=1)
+;         y[j][i] = x[i][j] + j;
+;     }
+
+define double @test6(i32** %y, i32** %x, i32 signext %nx, i32 signext %ny) {
+; CHECK-LABEL: IsPerfect=true, Depth=1, OutermostLoop: test6Loop2, Loops: ( test6Loop2 )
+; CHECK-LABEL: IsPerfect=true, Depth=2, OutermostLoop: test6Loop1, Loops: ( test6Loop1 test6Loop2 )
+entry:
+  %cmp2 = icmp slt i32 0, %nx
+  br i1 %cmp2, label %test6Loop1.lr.ph, label %for.end13
+
+test6Loop1.lr.ph:                                   ; preds = %entry
+  br label %test6Loop1
+
+test6Loop1:                                         ; preds = %test6Loop1.lr.ph, %for.inc11
+  %i.0 = phi i32 [ 0, %test6Loop1.lr.ph ], [ %inc12, %for.inc11 ]
+  %cmp1 = icmp slt i32 %i.0, %ny
+  br i1 %cmp1, label %test6Loop2.lr.ph, label %if.end
+
+test6Loop2.lr.ph:                                  ; preds = %if.then
+  br label %test6Loop2
+
+test6Loop2:                                        ; preds = %test6Loop2.lr.ph, %for.inc
+  %j.0 = phi i32 [ %i.0, %test6Loop2.lr.ph ], [ %inc, %for.inc ]
+  %idxprom = sext i32 %i.0 to i64
+  %arrayidx = getelementptr inbounds i32*, i32** %x, i64 %idxprom
+  %0 = load i32*, i32** %arrayidx, align 8
+  %idxprom5 = sext i32 %j.0 to i64
+  %arrayidx6 = getelementptr inbounds i32, i32* %0, i64 %idxprom5
+  %1 = load i32, i32* %arrayidx6, align 4
+  %add = add nsw i32 %1, %j.0
+  %idxprom7 = sext i32 %j.0 to i64
+  %arrayidx8 = getelementptr inbounds i32*, i32** %y, i64 %idxprom7
+  %2 = load i32*, i32** %arrayidx8, align 8
+  %idxprom9 = sext i32 %i.0 to i64
+  %arrayidx10 = getelementptr inbounds i32, i32* %2, i64 %idxprom9
+  store i32 %add, i32* %arrayidx10, align 4
+  br label %for.inc
+
+for.inc:                                          ; preds = %test6Loop2
+  %inc = add nsw i32 %j.0, 1
+  %cmp3 = icmp slt i32 %inc, %ny
+  br i1 %cmp3, label %test6Loop2, label %for.cond2.for.end_crit_edge
+
+for.cond2.for.end_crit_edge:                      ; preds = %for.inc
+  br label %for.end
+
+for.end:                                          ; preds = %for.cond2.for.end_crit_edge, %if.then
+  br label %if.end
+
+if.end:                                           ; preds = %for.end, %test6Loop1
+  br label %for.inc11
+
+for.inc11:                                        ; preds = %if.end
+  %inc12 = add nsw i32 %i.0, 1
+  %cmp = icmp slt i32 %inc12, %nx
+  br i1 %cmp, label %test6Loop1, label %for.cond.for.end13_crit_edge
+
+for.cond.for.end13_crit_edge:                     ; preds = %for.inc11
+  br label %for.end13
+
+for.end13:                                        ; preds = %for.cond.for.end13_crit_edge, %entry
+  %arrayidx14 = getelementptr inbounds i32*, i32** %y, i64 0
+  %3 = load i32*, i32** %arrayidx14, align 8
+  %arrayidx15 = getelementptr inbounds i32, i32* %3, i64 0
+  %4 = load i32, i32* %arrayidx15, align 4
+  %conv = sitofp i32 %4 to double
+  ret double %conv
+}