[IndVars] Remove exiting conditions that are trivially true/false

[mkazantsev]

Summary

When removing exiting loop conditions, we only consider checks for
which we know the exact exit count. We could also eliminate checks for
which the condition is always true/false.

[reames]

Max, I think this is probably handled by the existing optimizeLoopExits if the exit counts for the condition are computable. (i.e. you're probably looking at a gap in exit count computation)

[mkazantsev]

Thanks for a clue Philip, you are kind of right, but I don't think we can fix exit count computation. Here's the motivating example:

define i32 @test_01(i32* %p) {
entry:
  %len = load i32, i32* %p, align 4, !range !0
  br label %loop

loop:                                             ; preds = %backedge, %entry
  %iv = phi i32 [ %len, %entry ], [ %iv.next, %backedge ]
  %iv.next = add nsw i32 %iv, -1
  %rc = icmp slt i32 %iv.next, %len
  br i1 %rc, label %backedge, label %fail

backedge:                                         ; preds = %loop
  %loop.cond = icmp ne i32 %iv, 0
  br i1 %loop.cond, label %loop, label %exit

fail:                                             ; preds = %loop
  ret i32 -1

exit:                                             ; preds = %backedge
  ret i32 0
}

The block loop just never exits (if we leave this check alone then the loop is infinite). So formally, we do not know the exit count for this block. The only thing we can do is we can try to prove that, no matter what this exit count is, it is greater than max backedge taken count. This may work.

[mkazantsev]

Reframing the solution with accordance with @reames 's comment, starting from the most trivial cases and moving towards more complex ones.

[mkazantsev]

Rebased (no spam in test checks update).

[lebedev.ri]

This looks about reasonable to me, but i don't feel confident reviewing this.

llvm/lib/Transforms/Scalar/IndVarSimplify.cpp

2348–2352

Should this just be return SE->isKnownPredicate(Pred, LHSS, RHSS);,
or are there some other changes planned?

2386–2387

// Likewise, the loop latch must be dominated by the exiting BB.

[mkazantsev]

Internal testing revealed bugs, look weird, investigating.

llvm/lib/Transforms/Scalar/IndVarSimplify.cpp

2348–2352

Other changes planned on top, see dependent patch.

[mkazantsev]

llvm/lib/Transforms/Scalar/IndVarSimplify.cpp

2342

Should invert if false succ is the loop block.

[mkazantsev]

Addressed comments, fixed bug with non-loop true successor, added corresponding test.

[mkazantsev]

Ping.

[mkazantsev]

Some refactoring & renaming.

[lebedev.ri]

This seems fine to me, but might be good for someone else to take a look too.

[reames]

LGTM. Nice restructure.

An idea for another way to approach this would be to add ability to SCEV to prove an exit is infinite directly. That might be useful in other places. We could consider either a new function isExitCountInfinite or a new SCEVInfinite node.

Just to be clear, this is now brainstorming, not a review comment in the sense that I expect you to act on it. :)

llvm/lib/Transforms/Scalar/IndVarSimplify.cpp

2438

Minor, pull out the cast into a variable please.

[nikic]

What is the relationship between this code and SimplifyIndvar::eliminateIVComparison()? Is this basically the same thing, just for icmps against something other than the IV itself?

If I'm understanding this correctly, this optimization doesn't really seem to be related to loop exits and could apply to any icmp in the loop. Looking at it in terms of a loop exit seems to make the logic more complicated (e.g. the double inversion of the predicate).

[reames]

In D87344#2298471, @nikic wrote:

What is the relationship between this code and SimplifyIndvar::eliminateIVComparison()? Is this basically the same thing, just for icmps against something other than the IV itself?

If I'm understanding this correctly, this optimization doesn't really seem to be related to loop exits and could apply to any icmp in the loop. Looking at it in terms of a loop exit seems to make the logic more complicated (e.g. the double inversion of the predicate).

If we want to generally handle icmps involving SCEVs which were not either uses of IVs (directly) or loop exits, I agree this code would be good to pull out and use.

The catch is the the IV logic only visits a small subset of icmps. If you have any form of complicated expression feeding the icmp, it gives up without every reaching it.

I'll note that I think it's seriously worth considering whether we want a transform which just visits all icmps in a loop and tries to eliminate them, but that's a broader task than this patch. :)

[nikic]

In D87344#2298584, @reames wrote:

If we want to generally handle icmps involving SCEVs which were not either uses of IVs (directly) or loop exits, I agree this code would be good to pull out and use.

The catch is the the IV logic only visits a small subset of icmps. If you have any form of complicated expression feeding the icmp, it gives up without every reaching it.

I'll note that I think it's seriously worth considering whether we want a transform which just visits all icmps in a loop and tries to eliminate them, but that's a broader task than this patch. :)

Okay, thanks for the clarification!

llvm/lib/Transforms/Scalar/IndVarSimplify.cpp

2368–2369

Nit: The mention of analyzeable exits here is stale now.

2402–2404

And here as well. Now we know because we explicitly checked dominance, not because the exits are analyzable.

[mkazantsev]

llvm/lib/Transforms/Scalar/IndVarSimplify.cpp

2368–2369

Well, they are kind of still analyzable. We just do not know exact exit count for them, but it does not mean we know absolutely nothing.

llvm/lib/Transforms/Scalar/IndVarSimplify.cpp

while (I != Preheader->begin()) {
     ToMove->moveBefore(*ExitBlock, InsertPt);
     if (Done) break;
     InsertPt = ToMove->getIterator();
   }
 
   return MadeAnyChanges;
 }
 
+// Returns true if the condition of \p BI being checked is invariant and can be
+// proved to be trivially true.
+static bool isTrivialCond(const Loop *L, BranchInst *BI, ScalarEvolution *SE,
+                          bool ProvingLoopExit) {
+  ICmpInst::Predicate Pred;
+  Value *LHS, *RHS;
+  using namespace PatternMatch;
+  BasicBlock *TrueSucc, *FalseSucc;
+  if (!match(BI, m_Br(m_ICmp(Pred, m_Value(LHS), m_Value(RHS)),
+                      m_BasicBlock(TrueSucc), m_BasicBlock(FalseSucc))))
+    return false;
+
+  assert((L->contains(TrueSucc) != L->contains(FalseSucc)) &&
+         "Not a loop exit!");
+
+  // 'LHS pred RHS' should now mean that we stay in loop.
+  if (L->contains(FalseSucc))
+    Pred = CmpInst::getInversePredicate(Pred);
+
+  // If we are proving loop exit, invert the predicate.
+  if (ProvingLoopExit)
+    Pred = CmpInst::getInversePredicate(Pred);
+
+  const SCEV *LHSS = SE->getSCEVAtScope(LHS, L);
+  const SCEV *RHSS = SE->getSCEVAtScope(RHS, L);
+  // Can we prove it to be trivially true?
+  if (SE->isKnownPredicate(Pred, LHSS, RHSS))
+    return true;
+
+  return false;
+}
+
 bool IndVarSimplify::optimizeLoopExits(Loop *L, SCEVExpander &Rewriter) {
   SmallVector<BasicBlock*, 16> ExitingBlocks;
   L->getExitingBlocks(ExitingBlocks);
 
-  // Remove all exits which aren't both rewriteable and analyzeable.
+  // Remove all exits which aren't both rewriteable and execute on every
+  // iteration.
   auto NewEnd = llvm::remove_if(ExitingBlocks, [&](BasicBlock *ExitingBB) {
     // If our exitting block exits multiple loops, we can only rewrite the
     // innermost one.  Otherwise, we're changing how many times the innermost
     // loop runs before it exits.
     if (LI->getLoopFor(ExitingBB) != L)
       return true;
 
     // Can't rewrite non-branch yet.
     BranchInst *BI = dyn_cast<BranchInst>(ExitingBB->getTerminator());
     if (!BI)
       return true;
 
     // If already constant, nothing to do.
     if (isa<Constant>(BI->getCondition()))
       return true;
 
-    const SCEV *ExitCount = SE->getExitCount(L, ExitingBB);
-    if (isa<SCEVCouldNotCompute>(ExitCount))
+    // Likewise, the loop latch must be dominated by the exiting BB.
+    if (!DT->dominates(ExitingBB, L->getLoopLatch()))
       return true;
+
     return false;
   });
   ExitingBlocks.erase(NewEnd, ExitingBlocks.end());
 
   if (ExitingBlocks.empty())
     return false;
 
   // Get a symbolic upper bound on the loop backedge taken count.
   const SCEV *MaxExitCount = SE->computeMaxBackedgeTakenCount(L);
   if (isa<SCEVCouldNotCompute>(MaxExitCount))
     return false;
 
-  // Visit our exit blocks in order of dominance.  We know from the fact that
-  // all exits (left) are analyzeable that the must be a total dominance order
-  // between them as each must dominate the latch.  The visit order only
-  // matters for the provably equal case.
+  // Visit our exit blocks in order of dominance. We know from the fact that
+  // all exits must dominate the latch, so there is a total dominance order
+  // between them.
   llvm::sort(ExitingBlocks,
              [&](BasicBlock *A, BasicBlock *B) {
                // std::sort sorts in ascending order, so we want the inverse of
                // the normal dominance relation.
                if (A == B) return false;
                if (DT->properlyDominates(A, B)) return true;
                if (DT->properlyDominates(B, A)) return false;
                llvm_unreachable("expected total dominance order!");
auto FoldExit = [&](BasicBlock *ExitingBB, bool IsTaken) {
     if (OldCond->use_empty())
       DeadInsts.emplace_back(OldCond);
   };
 
   bool Changed = false;
   SmallSet<const SCEV*, 8> DominatingExitCounts;
   for (BasicBlock *ExitingBB : ExitingBlocks) {
     const SCEV *ExitCount = SE->getExitCount(L, ExitingBB);
-    assert(!isa<SCEVCouldNotCompute>(ExitCount) && "checked above");
+    if (isa<SCEVCouldNotCompute>(ExitCount)) {
+      // Okay, we do not know the exit count here. Can we at least prove that it
+      // will remain the same within iteration space?
+      auto *BI = cast<BranchInst>(ExitingBB->getTerminator());
+      if (isTrivialCond(L, BI, SE, false)) {
+        FoldExit(ExitingBB, false);
+        Changed = true;
+      }
+      if (isTrivialCond(L, BI, SE, true)) {
+        FoldExit(ExitingBB, true);
+        Changed = true;
+      }
+      continue;
+    }
 
     // If we know we'd exit on the first iteration, rewrite the exit to
     // reflect this.  This does not imply the loop must exit through this
     // exit; there may be an earlier one taken on the first iteration.
     // TODO: Given we know the backedge can't be taken, we should go ahead
     // and break it.  Or at least, kill all the header phis and simplify.
     if (ExitCount->isZero()) {
       FoldExit(ExitingBB, true);

llvm/test/Transforms/IndVarSimplify/eliminate-comparison.ll

 ; Indvars should not turn the second loop into an infinite one.
 
 
 define i32 @func_11() nounwind uwtable {
 ; CHECK-LABEL: @func_11(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    br label [[FORCOND:%.*]]
 ; CHECK:       forcond:
-; CHECK-NEXT:    [[__KEY6_0:%.*]] = phi i32 [ 2, [[ENTRY:%.*]] ], [ [[TMP37:%.*]], [[NOASSERT:%.*]] ]
-; CHECK-NEXT:    [[EXITCOND1:%.*]] = icmp ne i32 [[__KEY6_0]], 10
-; CHECK-NEXT:    br i1 [[EXITCOND1]], label [[NOASSERT]], label [[FORCOND38_PREHEADER:%.*]]
+; CHECK-NEXT:    br i1 false, label [[NOASSERT:%.*]], label [[FORCOND38_PREHEADER:%.*]]
 ; CHECK:       forcond38.preheader:
 ; CHECK-NEXT:    br label [[FORCOND38:%.*]]
 ; CHECK:       noassert:
-; CHECK-NEXT:    [[TMP13:%.*]] = sdiv i32 -32768, [[__KEY6_0]]
-; CHECK-NEXT:    [[TMP2936:%.*]] = shl i32 [[TMP13]], 24
-; CHECK-NEXT:    [[SEXT23:%.*]] = shl i32 [[TMP13]], 24
-; CHECK-NEXT:    [[TMP32:%.*]] = icmp eq i32 [[TMP2936]], [[SEXT23]]
-; CHECK-NEXT:    [[TMP37]] = add nuw nsw i32 [[__KEY6_0]], 1
-; CHECK-NEXT:    br i1 [[TMP32]], label [[FORCOND]], label [[ASSERT33:%.*]]
+; CHECK-NEXT:    br i1 true, label [[FORCOND]], label [[ASSERT33:%.*]]
 ; CHECK:       assert33:
 ; CHECK-NEXT:    tail call void @llvm.trap()
 ; CHECK-NEXT:    unreachable
 ; CHECK:       forcond38:
-; CHECK-NEXT:    [[__KEY8_0:%.*]] = phi i32 [ [[TMP81:%.*]], [[NOASSERT68:%.*]] ], [ 2, [[FORCOND38_PREHEADER]] ]
-; CHECK-NEXT:    [[EXITCOND:%.*]] = icmp ne i32 [[__KEY8_0]], 10
-; CHECK-NEXT:    br i1 [[EXITCOND]], label [[NOASSERT68]], label [[UNROLLEDEND:%.*]]
+; CHECK-NEXT:    br i1 false, label [[NOASSERT68:%.*]], label [[UNROLLEDEND:%.*]]
 ; CHECK:       noassert68:
-; CHECK-NEXT:    [[TMP57:%.*]] = sdiv i32 -32768, [[__KEY8_0]]
-; CHECK-NEXT:    [[SEXT34:%.*]] = shl i32 [[TMP57]], 16
-; CHECK-NEXT:    [[SEXT21:%.*]] = shl i32 [[TMP57]], 16
-; CHECK-NEXT:    [[TMP76:%.*]] = icmp eq i32 [[SEXT34]], [[SEXT21]]
-; CHECK-NEXT:    [[TMP81]] = add nuw nsw i32 [[__KEY8_0]], 1
-; CHECK-NEXT:    br i1 [[TMP76]], label [[FORCOND38]], label [[ASSERT77:%.*]]
+; CHECK-NEXT:    br i1 true, label [[FORCOND38]], label [[ASSERT77:%.*]]
 ; CHECK:       assert77:
 ; CHECK-NEXT:    tail call void @llvm.trap()
 ; CHECK-NEXT:    unreachable
 ; CHECK:       unrolledend:
 ; CHECK-NEXT:    ret i32 0
 ;
 entry:
   br label %forcond

 assert77:                                         ; preds = %noassert68
   tail call void @llvm.trap()
   unreachable
 
 unrolledend:                                      ; preds = %forcond38
   ret i32 0
 }
 
+define i32 @func_11_flipped() nounwind uwtable {
+; CHECK-LABEL: @func_11_flipped(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    br label [[FORCOND:%.*]]
+; CHECK:       forcond:
+; CHECK-NEXT:    br i1 true, label [[FORCOND38_PREHEADER:%.*]], label [[NOASSERT:%.*]]
+; CHECK:       forcond38.preheader:
+; CHECK-NEXT:    br label [[FORCOND38:%.*]]
+; CHECK:       noassert:
+; CHECK-NEXT:    br i1 true, label [[FORCOND]], label [[ASSERT33:%.*]]
+; CHECK:       assert33:
+; CHECK-NEXT:    tail call void @llvm.trap()
+; CHECK-NEXT:    unreachable
+; CHECK:       forcond38:
+; CHECK-NEXT:    br i1 false, label [[NOASSERT68:%.*]], label [[UNROLLEDEND:%.*]]
+; CHECK:       noassert68:
+; CHECK-NEXT:    br i1 true, label [[FORCOND38]], label [[ASSERT77:%.*]]
+; CHECK:       assert77:
+; CHECK-NEXT:    tail call void @llvm.trap()
+; CHECK-NEXT:    unreachable
+; CHECK:       unrolledend:
+; CHECK-NEXT:    ret i32 0
+;
+entry:
+  br label %forcond
+
+forcond:                                          ; preds = %noassert, %entry
+  %__key6.0 = phi i32 [ 2, %entry ], [ %tmp37, %noassert ]
+  %tmp5 = icmp sge i32 %__key6.0, 10
+  br i1 %tmp5, label %forcond38.preheader, label %noassert
+
+forcond38.preheader:                              ; preds = %forcond
+  br label %forcond38
+
+noassert:                                         ; preds = %forbody
+  %tmp13 = sdiv i32 -32768, %__key6.0
+  %tmp2936 = shl i32 %tmp13, 24
+  %sext23 = shl i32 %tmp13, 24
+  %tmp32 = icmp eq i32 %tmp2936, %sext23
+  %tmp37 = add i32 %__key6.0, 1
+  br i1 %tmp32, label %forcond, label %assert33
+
+assert33:                                         ; preds = %noassert
+  tail call void @llvm.trap()
+  unreachable
+
+forcond38:                                        ; preds = %noassert68, %forcond38.preheader
+  %__key8.0 = phi i32 [ %tmp81, %noassert68 ], [ 2, %forcond38.preheader ]
+  %tmp46 = icmp slt i32 %__key8.0, 10
+  br i1 %tmp46, label %noassert68, label %unrolledend
+
+noassert68:                                       ; preds = %forbody39
+  %tmp57 = sdiv i32 -32768, %__key8.0
+  %sext34 = shl i32 %tmp57, 16
+  %sext21 = shl i32 %tmp57, 16
+  %tmp76 = icmp eq i32 %sext34, %sext21
+  %tmp81 = add i32 %__key8.0, 1
+  br i1 %tmp76, label %forcond38, label %assert77
+
+assert77:                                         ; preds = %noassert68
+  tail call void @llvm.trap()
+  unreachable
+
+unrolledend:                                      ; preds = %forcond38
+  ret i32 0
+}
+
 declare void @llvm.trap() noreturn nounwind
 
 ; In this case the second loop only has a single iteration, fold the header away
 define i32 @func_12() nounwind uwtable {
 ; CHECK-LABEL: @func_12(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    br label [[FORCOND:%.*]]
 ; CHECK:       forcond:
-; CHECK-NEXT:    [[__KEY6_0:%.*]] = phi i32 [ 2, [[ENTRY:%.*]] ], [ [[TMP37:%.*]], [[NOASSERT:%.*]] ]
-; CHECK-NEXT:    [[EXITCOND:%.*]] = icmp ne i32 [[__KEY6_0]], 10
-; CHECK-NEXT:    br i1 [[EXITCOND]], label [[NOASSERT]], label [[FORCOND38_PREHEADER:%.*]]
+; CHECK-NEXT:    br i1 false, label [[NOASSERT:%.*]], label [[FORCOND38_PREHEADER:%.*]]
 ; CHECK:       forcond38.preheader:
 ; CHECK-NEXT:    br label [[FORCOND38:%.*]]
 ; CHECK:       noassert:
-; CHECK-NEXT:    [[TMP13:%.*]] = sdiv i32 -32768, [[__KEY6_0]]
-; CHECK-NEXT:    [[TMP2936:%.*]] = shl i32 [[TMP13]], 24
-; CHECK-NEXT:    [[SEXT23:%.*]] = shl i32 [[TMP13]], 24
-; CHECK-NEXT:    [[TMP32:%.*]] = icmp eq i32 [[TMP2936]], [[SEXT23]]
-; CHECK-NEXT:    [[TMP37]] = add nuw nsw i32 [[__KEY6_0]], 1
-; CHECK-NEXT:    br i1 [[TMP32]], label [[FORCOND]], label [[ASSERT33:%.*]]
+; CHECK-NEXT:    br i1 true, label [[FORCOND]], label [[ASSERT33:%.*]]
 ; CHECK:       assert33:
 ; CHECK-NEXT:    tail call void @llvm.trap()
 ; CHECK-NEXT:    unreachable
 ; CHECK:       forcond38:
 ; CHECK-NEXT:    br i1 true, label [[NOASSERT68:%.*]], label [[UNROLLEDEND:%.*]]
 ; CHECK:       noassert68:
 ; CHECK-NEXT:    br i1 false, label [[FORCOND38]], label [[ASSERT77:%.*]]
 ; CHECK:       assert77: