[SCEV] Use fact that B >u 0 for A <u B in applyLoopGuards.

[fhahn]

Summary

If LHS <u RHS holds, RHS should be guaranteed to be > 0. By using
using 'umax(RHS, 1) -1' instead of 'RHS - 1' the results in
applyLoopGuards can be improved in some cases.

Note that the TODO for the tests mentioned the max BTC being 11, but
unless I am missing something 10 should be correct.

https://alive2.llvm.org/ce/z/44nP7F

[mkazantsev]

Will it still work if c1 and c2 are checked in the loop? To me it looks like there is some piece of logic is missing in isImpliedCondition.

[fhahn]

@mkazantsev wrote:
Will it still work if c1 and c2 are checked in the loop?

Do you mean RHS & LHS? I'm not sure if a check in the loop would help us restrict the trip count, are you thinking about any case in particular?

To me it looks like there is some piece of logic is missing in isImpliedCondition.

I don't think we use isImpliedCond after constructing the SCEV expression for the backedge taken count and we also do not use it (at least with context) during SCEV construction. The UMax here helps to determine that the RHS - 1 won't wrap around, which in terms allows simplifying the BTC in some cases.

[mkazantsev]

I was thinking of smth like

define void @test_chceks_in_loop(i32* nocapture %a, i64 %i, i64 %N) {
entry:
  br label loop

loop:
  %iv = phi i64 [ %iv.next, %loop.guarded.2 ], [ 0, %entry]
  %c.1 = icmp ult i64 %N, 12
  br i1 %c.1, label %loop.guarded.1, label %exit

loop.guarded.1:
  %c.2 = icmp ult i64 %i, %N
  br i1 %c.2, label %loop.guarded.2, label %exit

loop.guarded.2:
  %idx = getelementptr inbounds i32, i32* %a, i64 %iv
  store i32 1, i32* %idx, align 4
  %iv.next = add nuw nsw i64 %iv, 1
  %exitcond = icmp eq i64 %iv, %i
  br i1 %exitcond, label %exit, label %loop

exit:
  ret void
}

Normally I'd expect this checks would be hoisted/unswitched out, but if not, maybe it also makes sense to make it work.

llvm/lib/Analysis/ScalarEvolution.cpp

15065

I think there should be (maybe not such useful, but still) a symmetrical signed case with SINT_MIN+1 instead of 1.

[mkazantsev]

llvm/test/Analysis/ScalarEvolution/max-backedge-taken-count-guard-info.ll

397–398

I wonder, how come that AddRec is now proven to make just 1 iteration less, but BE taken count is reduced by 2? It's not necessarily a bug, but looks strange.

[mkazantsev]

Generally LGTM, but please think of examples I've provided, maybe there is a better solution.

[fhahn]

Rebased and fixed crash on pointer inductions.

In D126503#3544920, @mkazantsev wrote:

Generally LGTM, but please think of examples I've provided, maybe there is a better solution.

Hmm, I think we could adjust the point from which we collect the conditions if it is used to compute the BTC for a specific branch. I'd need to check the compile-time impact and if it helps in practive much, as those branches should be hoisted out of the loop, as you said.

[fhahn]

llvm/lib/Analysis/ScalarEvolution.cpp

15065

I'll investigate as follow-up.

llvm/test/Analysis/ScalarEvolution/max-backedge-taken-count-guard-info.ll

397–398

The loop is guarded by %N < %I and %I < %N which cannot both be true, so it should never execute.

The reason we adjust the count by 2 is because we do the following substitutions

i = min(i, N-1)
N = min(N, min(I, N-1) -1)

[nikic]

llvm/test/Analysis/ScalarEvolution/max-backedge-taken-count-guard-info.ll

310–311

Remove TODO?

[fhahn]

Remove fixed TODOs, thanks! I plan to land this soon.

llvm/lib/Analysis/ScalarEvolution.cpp

auto CollectCondition = [&](ICmpInst::Predicate Predicate, const SCEV *LHS,
 
     // Check whether LHS has already been rewritten. In that case we want to
     // chain further rewrites onto the already rewritten value.
     auto I = RewriteMap.find(LHS);
     const SCEV *RewrittenLHS = I != RewriteMap.end() ? I->second : LHS;
 
     const SCEV *RewrittenRHS = nullptr;
     switch (Predicate) {
-    case CmpInst::ICMP_ULT:
+    case CmpInst::ICMP_ULT: {
+      if (RHS->getType()->isPointerTy())
+        break;
+      const SCEV *One = getOne(RHS->getType());
       RewrittenRHS =
-          getUMinExpr(RewrittenLHS, getMinusSCEV(RHS, getOne(RHS->getType())));
+          getUMinExpr(RewrittenLHS, getMinusSCEV(getUMaxExpr(RHS, One), One));
       break;
+    }
     case CmpInst::ICMP_SLT:
       RewrittenRHS =
           getSMinExpr(RewrittenLHS, getMinusSCEV(RHS, getOne(RHS->getType())));
       break;
     case CmpInst::ICMP_ULE:
       RewrittenRHS = getUMinExpr(RewrittenLHS, RHS);
       break;
     case CmpInst::ICMP_SLE:
       RewrittenRHS = getSMinExpr(RewrittenLHS, RHS);
       break;
     case CmpInst::ICMP_UGT:

llvm/test/Analysis/ScalarEvolution/max-backedge-taken-count-guard-info.ll

loop:
   store i32 1, ptr %idx, align 4
   %iv.next = add nuw nsw i64 %iv, 1
   %exitcond = icmp eq i64 %iv, %i
   br i1 %exitcond, label %exit, label %loop
 
 exit:
   ret void
 }
 
-; TODO: Currently we miss getting the tightest constant max backedge-taken count (11).
 define void @test_multiple_var_guards_order1(ptr nocapture %a, i64 %i, i64 %N) {
 ; CHECK-LABEL: 'test_multiple_var_guards_order1'
 ; CHECK-NEXT:  Classifying expressions for: @test_multiple_var_guards_order1
 ; CHECK-NEXT:    %iv = phi i64 [ %iv.next, %loop ], [ 0, %guardbb ]
-; CHECK-NEXT:    --> {0,+,1}<nuw><nsw><%loop> U: [0,-9223372036854775808) S: [0,-9223372036854775808) Exits: %i LoopDispositions: { %loop: Computable }
+; CHECK-NEXT:    --> {0,+,1}<nuw><nsw><%loop> U: [0,11) S: [0,11) Exits: %i LoopDispositions: { %loop: Computable }
 ; CHECK-NEXT:    %idx = getelementptr inbounds i32, ptr %a, i64 %iv
 ; CHECK-NEXT:    --> {%a,+,4}<nuw><%loop> U: full-set S: full-set Exits: ((4 * %i) + %a) LoopDispositions: { %loop: Computable }
 ; CHECK-NEXT:    %iv.next = add nuw nsw i64 %iv, 1
-; CHECK-NEXT:    --> {1,+,1}<nuw><%loop> U: [1,0) S: [1,0) Exits: (1 + %i) LoopDispositions: { %loop: Computable }
+; CHECK-NEXT:    --> {1,+,1}<nuw><nsw><%loop> U: [1,12) S: [1,12) Exits: (1 + %i) LoopDispositions: { %loop: Computable }
 ; CHECK-NEXT:  Determining loop execution counts for: @test_multiple_var_guards_order1
 ; CHECK-NEXT:  Loop %loop: backedge-taken count is %i
-; CHECK-NEXT:  Loop %loop: constant max backedge-taken count is -1
+; CHECK-NEXT:  Loop %loop: constant max backedge-taken count is 10
 ; CHECK-NEXT:  Loop %loop: symbolic max backedge-taken count is %i
 ; CHECK-NEXT:  Loop %loop: Predicated backedge-taken count is %i
 ; CHECK-NEXT:   Predicates:
 ; CHECK:       Loop %loop: Trip multiple is 1
 ;
 entry:
   %c.1 = icmp ult i64 %N, 12
   br i1 %c.1, label %guardbb, label %exit
loop:
   %iv.next = add nuw nsw i64 %iv, 1
   %exitcond = icmp eq i64 %iv, %i
   br i1 %exitcond, label %exit, label %loop
 
 exit:
   ret void
 }
 
-; TODO: Currently we miss getting the tightest constant max backedge-taken count (11).
 define void @test_multiple_var_guards_order2(ptr nocapture %a, i64 %i, i64 %N) {
 ; CHECK-LABEL: 'test_multiple_var_guards_order2'
 ; CHECK-NEXT:  Classifying expressions for: @test_multiple_var_guards_order2
 ; CHECK-NEXT:    %iv = phi i64 [ %iv.next, %loop ], [ 0, %guardbb ]
-; CHECK-NEXT:    --> {0,+,1}<nuw><nsw><%loop> U: [0,-9223372036854775808) S: [0,-9223372036854775808) Exits: %i LoopDispositions: { %loop: Computable }
+; CHECK-NEXT:    --> {0,+,1}<nuw><nsw><%loop> U: [0,11) S: [0,11) Exits: %i LoopDispositions: { %loop: Computable }
 ; CHECK-NEXT:    %idx = getelementptr inbounds i32, ptr %a, i64 %iv
 ; CHECK-NEXT:    --> {%a,+,4}<nuw><%loop> U: full-set S: full-set Exits: ((4 * %i) + %a) LoopDispositions: { %loop: Computable }
 ; CHECK-NEXT:    %iv.next = add nuw nsw i64 %iv, 1
-; CHECK-NEXT:    --> {1,+,1}<nuw><%loop> U: [1,0) S: [1,0) Exits: (1 + %i) LoopDispositions: { %loop: Computable }
+; CHECK-NEXT:    --> {1,+,1}<nuw><nsw><%loop> U: [1,12) S: [1,12) Exits: (1 + %i) LoopDispositions: { %loop: Computable }
 ; CHECK-NEXT:  Determining loop execution counts for: @test_multiple_var_guards_order2
 ; CHECK-NEXT:  Loop %loop: backedge-taken count is %i
-; CHECK-NEXT:  Loop %loop: constant max backedge-taken count is -1
+; CHECK-NEXT:  Loop %loop: constant max backedge-taken count is 10
 ; CHECK-NEXT:  Loop %loop: symbolic max backedge-taken count is %i
 ; CHECK-NEXT:  Loop %loop: Predicated backedge-taken count is %i
 ; CHECK-NEXT:   Predicates:
 ; CHECK:       Loop %loop: Trip multiple is 1
 ;
 entry:
   %c.1 = icmp ult i64 %i, %N
   br i1 %c.1, label %guardbb, label %exit

 define void @test_multiple_var_guards_cycle(ptr nocapture %a, i64 %i, i64 %N) {
 ; CHECK-LABEL: 'test_multiple_var_guards_cycle'
 ; CHECK-NEXT:  Classifying expressions for: @test_multiple_var_guards_cycle
 ; CHECK-NEXT:    %iv = phi i64 [ %iv.next, %loop ], [ 0, %guardbb ]
 ; CHECK-NEXT:    --> {0,+,1}<nuw><nsw><%loop> U: [0,-9223372036854775808) S: [0,-9223372036854775808) Exits: %N LoopDispositions: { %loop: Computable }
 ; CHECK-NEXT:    %idx = getelementptr inbounds i32, ptr %a, i64 %iv
 ; CHECK-NEXT:    --> {%a,+,4}<nuw><%loop> U: full-set S: full-set Exits: ((4 * %N) + %a) LoopDispositions: { %loop: Computable }
 ; CHECK-NEXT:    %iv.next = add nuw nsw i64 %iv, 1
-; CHECK-NEXT:    --> {1,+,1}<nuw><%loop> U: [1,0) S: [1,0) Exits: (1 + %N) LoopDispositions: { %loop: Computable }
+; CHECK-NEXT:    --> {1,+,1}<nuw><%loop> U: [1,-1) S: [1,-1) Exits: (1 + %N) LoopDispositions: { %loop: Computable }
 ; CHECK-NEXT:  Determining loop execution counts for: @test_multiple_var_guards_cycle
 ; CHECK-NEXT:  Loop %loop: backedge-taken count is %N
-; CHECK-NEXT:  Loop %loop: constant max backedge-taken count is -1
+; CHECK-NEXT:  Loop %loop: constant max backedge-taken count is -3
 ; CHECK-NEXT:  Loop %loop: symbolic max backedge-taken count is %N
 ; CHECK-NEXT:  Loop %loop: Predicated backedge-taken count is %N
 ; CHECK-NEXT:   Predicates:
 ; CHECK:       Loop %loop: Trip multiple is 1
 ;
 entry:
   %c.1 = icmp ult i64 %N, %i
   br i1 %c.1, label %guardbb, label %exit