[IndVars] Use symbolic max block exit count to handle the last iter

[mkazantsev]

Summary

Old logic: when loop symbolic max exit count matched *exact* block exit count,
assume that all subsequent blocks will do 1 iteration less.

New logic: when loop symbolic max exit count matched *symbolic max* block exit count,
assume that all subsequent blocks will do 1 iteration less.

The new logic is still legal and is more permissive in situations when exact
block exit count is not known.

[nikic]

The change looks fine, but I think the naming here is now a mess. We have ExitCount (the exact exit count of this exit), SymbolicMaxExitCount (the max exit count of this exit) and MaxExitCount (the max backedge taken count). I'd suggest to rename these variables as follows:

MaxExitCount -> MaxBECount
ExitCount -> ExactExitCount
SymbolicMaxExitCount -> MaxExitCount

Or keep including Symbolic if you think it adds value. (Preferably precommit the rename.)

[mkazantsev]

Rebased/renamed.

[nikic]

LG

llvm/lib/Transforms/Scalar/IndVarSimplify.cpp

1704–1705

As a followup, we should be able to use MaxExitCount here as well.

[mkazantsev]

llvm/lib/Transforms/Scalar/IndVarSimplify.cpp

1704–1705

Good catch, need to find a test on it.

[mkazantsev]

llvm/lib/Transforms/Scalar/IndVarSimplify.cpp

1704–1705

Thinking more of it, I don't think it's right. Imagine case:
exit 1: exact (unknown) is 2, symbolic max is x
exit 2: exact (unknown) is 0, symbolic max is x + 1<nuw>

Loop's symbolic max is x.

In this case we cannot eliminate the 2nd exit basing on fact that its maximum is more than some other maximum.

Unilke this, in my patch exit (in given block) earlier than proven max doesn't matter; logic with last iteration is only in the game when loop actually exits on max possible proven iteration (and therefore all subsequent exits don't execute).

llvm/lib/Transforms/Scalar/IndVarSimplify.cpp

#ifdef ASSERT
   }
 #endif
 
   bool Changed = false;
   bool SkipLastIter = false;
   SmallSet<const SCEV*, 8> DominatingExitCounts;
   for (BasicBlock *ExitingBB : ExitingBlocks) {
     const SCEV *ExitCount = SE->getExitCount(L, ExitingBB);
+    const SCEV *SymbolicMaxExitCount = SE->getExitCount(
+        L, ExitingBB, ScalarEvolution::ExitCountKind::SymbolicMaximum);
     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());
       auto OptimizeCond = [&](bool Inverted, bool SkipLastIter) {
         return optimizeLoopExitWithUnknownExitCount(
             L, BI, ExitingBB, MaxExitCount, Inverted, SkipLastIter, SE,
             Rewriter, DeadInsts);
if (isa<SCEVCouldNotCompute>(ExitCount)) {
       // hope that we will be able to prove triviality for at least one of
       // them. We can stop querying MaxExitCount for this case once SCEV
       // understands that (MaxExitCount - 1) will not overflow here.
       if (OptimizeCond(false, false) || OptimizeCond(true, false))
         Changed = true;
       else if (SkipLastIter)
         if (OptimizeCond(false, true) || OptimizeCond(true, true))
           Changed = true;
+      if (MaxExitCount == SymbolicMaxExitCount)
+        // If the loop has more than 1 iteration, all further checks will be
+        // executed 1 iteration less.
+        SkipLastIter = true;
       continue;
     }
 
-    if (MaxExitCount == ExitCount)
+    if (MaxExitCount == SymbolicMaxExitCount)
       // If the loop has more than 1 iteration, all further checks will be
       // executed 1 iteration less.
       SkipLastIter = true;
 
     // 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.
     // We know that the backedge can't be taken, so we replace all
for (BasicBlock *ExitingBB : ExitingBlocks) {
     Type *WiderType =
       SE->getWiderType(MaxExitCount->getType(), ExitCount->getType());
     ExitCount = SE->getNoopOrZeroExtend(ExitCount, WiderType);
     MaxExitCount = SE->getNoopOrZeroExtend(MaxExitCount, WiderType);
     assert(MaxExitCount->getType() == ExitCount->getType());
 
     // Can we prove that some other exit must be taken strictly before this
     // one?
     if (SE->isLoopEntryGuardedByCond(L, CmpInst::ICMP_ULT,
                                      MaxExitCount, ExitCount)) {
       foldExit(L, ExitingBB, false, DeadInsts);
       Changed = true;
       continue;
     }
 
     // As we run, keep track of which exit counts we've encountered.  If we
     // find a duplicate, we've found an exit which would have exited on the
     // exiting iteration, but (from the visit order) strictly follows another

llvm/test/Transforms/IndVarSimplify/turn-to-invariant.ll

 
 failed_1:
   ret i32 -1
 
 failed_2:
   ret i32 -2
 }
 
-
-; TODO: Simplified version 1 of test_litter_conditions.
 define i32 @test_litter_conditions_01(i32 %start, i32 %len) {
 ; CHECK-LABEL: @test_litter_conditions_01(
 ; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[TMP0:%.*]] = add i32 [[START:%.*]], -1
 ; CHECK-NEXT:    br label [[LOOP:%.*]]
 ; CHECK:       loop:
-; CHECK-NEXT:    [[IV:%.*]] = phi i32 [ [[START:%.*]], [[ENTRY:%.*]] ], [ [[IV_NEXT:%.*]], [[BACKEDGE:%.*]] ]
+; CHECK-NEXT:    [[IV:%.*]] = phi i32 [ [[START]], [[ENTRY:%.*]] ], [ [[IV_NEXT:%.*]], [[BACKEDGE:%.*]] ]
 ; CHECK-NEXT:    [[ZERO_CHECK:%.*]] = icmp ne i32 [[IV]], 0
 ; CHECK-NEXT:    [[FAKE_1:%.*]] = call i1 @cond()
 ; CHECK-NEXT:    [[AND_1:%.*]] = and i1 [[ZERO_CHECK]], [[FAKE_1]]
 ; CHECK-NEXT:    br i1 [[AND_1]], label [[RANGE_CHECK_BLOCK:%.*]], label [[FAILED_1:%.*]]
 ; CHECK:       range_check_block:
-; CHECK-NEXT:    [[IV_MINUS_1:%.*]] = add i32 [[IV]], -1
-; CHECK-NEXT:    [[RANGE_CHECK:%.*]] = icmp ult i32 [[IV_MINUS_1]], [[LEN:%.*]]
-; CHECK-NEXT:    br i1 [[RANGE_CHECK]], label [[BACKEDGE]], label [[FAILED_2:%.*]]
+; CHECK-NEXT:    [[RANGE_CHECK3:%.*]] = icmp ult i32 [[TMP0]], [[LEN:%.*]]
+; CHECK-NEXT:    br i1 [[RANGE_CHECK3]], label [[BACKEDGE]], label [[FAILED_2:%.*]]
 ; CHECK:       backedge:
 ; CHECK-NEXT:    [[IV_NEXT]] = add i32 [[IV]], -1
 ; CHECK-NEXT:    [[LOOP_COND:%.*]] = call i1 @cond()
 ; CHECK-NEXT:    br i1 [[LOOP_COND]], label [[DONE:%.*]], label [[LOOP]]
 ; CHECK:       done:
 ; CHECK-NEXT:    [[IV_LCSSA2:%.*]] = phi i32 [ [[IV]], [[BACKEDGE]] ]
 ; CHECK-NEXT:    ret i32 [[IV_LCSSA2]]
 ; CHECK:       failed_1: