[IndVars] Use isLoopBackedgeGuardedByCond for last iteration check

[mkazantsev]

Summary

Use more context to prove contextual facts about the last iteration. It is
only executed when the backedge is taken, so we can use isLoopBackedgeGuardedByCond
to make this check.

[mkazantsev]

Marking "planned changes" until dependencies are merged.

[skatkov]

llvm/lib/Analysis/ScalarEvolution.cpp

9642

The only concern I have: whether isLoopBackedgeGuardedByCond always produces better result than isKnownPredicateAt.

[mkazantsev]

llvm/lib/Analysis/ScalarEvolution.cpp

9642

I ran 4077 fuzzer-generated test with assert that whenever the new condition is false, the old condition is also false. Theoretically, this might happen. But it's just a reason to make isLoopBackedgeGuardedByCond smarter.

[skatkov]

llvm/lib/Analysis/ScalarEvolution.cpp

9642

I hope no one test failed :)

[mkazantsev]

Yes, I ran 4077 fuzz tests checking this assumption, and it seems better in every case there. There can theoretically be cases where isLoopBackedgeGuardedBy is weaker, but it's only the reason to improve it.

[mkazantsev]

Eeek. I found a test where isKnownPredicateAt is more powerful. Need to use both then.

[mkazantsev]

Actually, it only means that isLoopBackedgeGuardedByCond should directly call isKnownPredicateAt(Latch->getTerminator()) as the last resort. I will follow-up with this improvement adding relevant test.

llvm/lib/Analysis/ScalarEvolution.cpp

if (!AR || AR->getLoop() != L)
     return None;
 
   if (!getMonotonicPredicateType(AR, Pred, MaxIter, Context))
     return None;
 
   // Value of IV on suggested last iteration.
   const SCEV *Last = AR->evaluateAtIteration(MaxIter, *this);
   // Does it still meet the requirement?
-  if (!isKnownPredicateAt(Pred, Last, RHS, Context))
+  if (!isLoopBackedgeGuardedByCond(L, Pred, Last, RHS))
     return None;
 
   // Everything is fine.
   return ScalarEvolution::LoopInvariantPredicate(Pred, AR->getStart(), RHS);
 }
 
 bool ScalarEvolution::isKnownPredicateViaConstantRanges(
     ICmpInst::Predicate Pred, const SCEV *LHS, const SCEV *RHS) {

llvm/test/Transforms/IndVarSimplify/predicated_ranges.ll

 fail:
   unreachable
 }
 
 define void @test_can_predicate_simple_unsigned_different_start(i32 %start, i32* %p, i32* %arr) {
 ; CHECK-LABEL: @test_can_predicate_simple_unsigned_different_start(
 ; CHECK-NEXT:  preheader:
 ; CHECK-NEXT:    [[LEN:%.*]] = load i32, i32* [[P:%.*]], align 4
+; CHECK-NEXT:    [[TMP0:%.*]] = add i32 [[START:%.*]], -1
 ; CHECK-NEXT:    br label [[LOOP:%.*]]
 ; CHECK:       loop:
-; CHECK-NEXT:    [[IV:%.*]] = phi i32 [ [[START:%.*]], [[PREHEADER:%.*]] ], [ [[IV_NEXT:%.*]], [[BACKEDGE:%.*]] ]
+; CHECK-NEXT:    [[IV:%.*]] = phi i32 [ [[START]], [[PREHEADER:%.*]] ], [ [[IV_NEXT:%.*]], [[BACKEDGE:%.*]] ]
 ; CHECK-NEXT:    [[ZERO_COND:%.*]] = icmp eq i32 [[IV]], 0
 ; CHECK-NEXT:    br i1 [[ZERO_COND]], label [[EXIT:%.*]], label [[RANGE_CHECK_BLOCK:%.*]]
 ; CHECK:       range_check_block:
 ; CHECK-NEXT:    [[IV_NEXT]] = sub i32 [[IV]], 1
-; CHECK-NEXT:    [[RANGE_CHECK:%.*]] = icmp ult i32 [[IV_NEXT]], [[LEN]]
-; CHECK-NEXT:    br i1 [[RANGE_CHECK]], label [[BACKEDGE]], label [[FAIL:%.*]]
+; CHECK-NEXT:    [[RANGE_CHECK1:%.*]] = icmp ult i32 [[TMP0]], [[LEN]]
+; CHECK-NEXT:    br i1 [[RANGE_CHECK1]], label [[BACKEDGE]], label [[FAIL:%.*]]
 ; CHECK:       backedge:
 ; CHECK-NEXT:    [[EL_PTR:%.*]] = getelementptr i32, i32* [[P]], i32 [[IV]]
 ; CHECK-NEXT:    [[EL:%.*]] = load i32, i32* [[EL_PTR]], align 4
 ; CHECK-NEXT:    [[LOOP_COND:%.*]] = icmp eq i32 [[EL]], 0
 ; CHECK-NEXT:    br i1 [[LOOP_COND]], label [[LOOP]], label [[EXIT]]
 ; CHECK:       exit:
 ; CHECK-NEXT:    ret void
 ; CHECK:       fail:

 fail:
   unreachable
 }
 
 define void @test_can_predicate_simple_unsigned_inverted_different_start(i32 %start, i32* %p, i32* %arr) {
 ; CHECK-LABEL: @test_can_predicate_simple_unsigned_inverted_different_start(
 ; CHECK-NEXT:  preheader:
 ; CHECK-NEXT:    [[LEN:%.*]] = load i32, i32* [[P:%.*]], align 4
+; CHECK-NEXT:    [[TMP0:%.*]] = add i32 [[START:%.*]], -1
 ; CHECK-NEXT:    br label [[LOOP:%.*]]
 ; CHECK:       loop:
-; CHECK-NEXT:    [[IV:%.*]] = phi i32 [ [[START:%.*]], [[PREHEADER:%.*]] ], [ [[IV_NEXT:%.*]], [[BACKEDGE:%.*]] ]
+; CHECK-NEXT:    [[IV:%.*]] = phi i32 [ [[START]], [[PREHEADER:%.*]] ], [ [[IV_NEXT:%.*]], [[BACKEDGE:%.*]] ]
 ; CHECK-NEXT:    [[ZERO_COND:%.*]] = icmp eq i32 [[IV]], 0
 ; CHECK-NEXT:    br i1 [[ZERO_COND]], label [[EXIT:%.*]], label [[RANGE_CHECK_BLOCK:%.*]]
 ; CHECK:       range_check_block:
 ; CHECK-NEXT:    [[IV_NEXT]] = sub i32 [[IV]], 1
-; CHECK-NEXT:    [[RANGE_CHECK:%.*]] = icmp uge i32 [[IV_NEXT]], [[LEN]]
-; CHECK-NEXT:    br i1 [[RANGE_CHECK]], label [[FAIL:%.*]], label [[BACKEDGE]]
+; CHECK-NEXT:    [[RANGE_CHECK1:%.*]] = icmp uge i32 [[TMP0]], [[LEN]]
+; CHECK-NEXT:    br i1 [[RANGE_CHECK1]], label [[FAIL:%.*]], label [[BACKEDGE]]
 ; CHECK:       backedge:
 ; CHECK-NEXT:    [[EL_PTR:%.*]] = getelementptr i32, i32* [[P]], i32 [[IV]]
 ; CHECK-NEXT:    [[EL:%.*]] = load i32, i32* [[EL_PTR]], align 4
 ; CHECK-NEXT:    [[LOOP_COND:%.*]] = icmp eq i32 [[EL]], 0
 ; CHECK-NEXT:    br i1 [[LOOP_COND]], label [[LOOP]], label [[EXIT]]
 ; CHECK:       exit:
 ; CHECK-NEXT:    ret void
 ; CHECK:       fail: