[SCEV] Compute ranges for lshr recurrences

[reames]

Summary

Straight forward extension to the recently added infrastructure which was pioneered with shl.

@reviewers - I always have trouble with wrapping arithmetic, so please sanity check my usage of ranges and reasoning.

[reames]

llvm/test/Analysis/ScalarEvolution/shift-recurrences.ll

664

The choice of the inverted range here looks odd. I dug into this a bit, and am suspecting a generic bug in the preferred range mechanism in ConstantRange. The key point is that we're making a heuristic driven chosen between two possible ranges, and we simply happen to pick the other one after this patch.

[mkazantsev]

I couldn't find tests for the following scenarios:

• Saturated ashr for positive & negative start;
• Zero shift value (for any operation & start);
• Start/end value not being power of 2 (power of 2 - 1). I am a bit worried that the boundaries of the ranges are always powers of 2, and no test shows that the rounding is correct.

(I don't claim there is none, but I could not find them in this test file :) )
Could you please point out on them (if they exist) or add them?

llvm/lib/Analysis/ScalarEvolution.cpp

5732

Any tests for two first cases?

[reames]

Need to add additional tests (or pointers to them), but also intentionally stalling this until issues with handling of unreachable code in the underlying infrastructure are resolved and nothing new pops up for a few days.

llvm/test/Analysis/ScalarEvolution/shift-recurrences.ll

664

Dug into this further, and it's not a bug in the code, it was a bug in my understanding. The broad point about it being a legal choice for the answer still holds though.

[reames]

In D99687#2668491, @mkazantsev wrote:

I couldn't find tests for the following scenarios:

• Saturated ashr for positive & negative start;

test_ashr_tc_positive and test_ashr_tc_negative - not that 128 is INT_MIN for i8

• Zero shift value (for any operation & start);

added as test_lshr_zero_shift and test_ashr_zero_shift

• Start/end value not being power of 2 (power of 2 - 1). I am a bit worried that the boundaries of the ranges are always powers of 2, and no test shows that the rounding is correct.

Added as test_lshr_power_of_2_start, test_lshr_arbitrary_start, and test_lshr_start_power_of_2_plus_one

[reames]

Rebase over requested tests, and narrow initial scope to lshr only. Will return to ashr once this lands.

[mkazantsev]

Thanks, LGTM!

llvm/lib/Analysis/ScalarEvolution.cpp

if (!L->contains(BO->getParent()))
     // There doesn't appear to be an obvious fix, so for the moment bailout
     // until the caller issue can be fixed.  PR49566 tracks the bug.
     return CR;
 
   // TODO: Extend to other opcodes such as ashr, mul, and div
   switch (BO->getOpcode()) {
   default:
     return CR;
+  case Instruction::LShr:
   case Instruction::Shl:
     break;
   };
 
   if (BO->getOperand(0) != P)
     // TODO: Handle the power function forms some day.
     return CR;
 
getRangeForUnknownRecurrence(const SCEVUnknown *U) {
   bool Overflow = false;
   auto TotalShift = MaxShiftAmt.umul_ov(TCAP, Overflow);
   if (Overflow)
     return CR;
 
   switch (BO->getOpcode()) {
   default:
     llvm_unreachable("filtered out above");
+  case Instruction::LShr: {
+    // For each lshr, three cases:
+    //   shift = 0 => unchanged value
+    //   saturation => 0
+    //   other => a smaller positive number
+    // Thus, the low end of the unsigned range is the last value produced.
+    auto KnownEnd = KnownBits::lshr(KnownStart,
+                                    KnownBits::makeConstant(TotalShift));
+    auto R = ConstantRange::getNonEmpty(KnownEnd.getMinValue(),
+                                        KnownStart.getMaxValue() + 1);
+    CR = CR.intersectWith(R);
+    break;
+  }
   case Instruction::Shl: {
     // Iff no bits are shifted out, value increases on every shift.
     auto KnownEnd = KnownBits::shl(KnownStart,
                                    KnownBits::makeConstant(TotalShift));
     if (TotalShift.ult(KnownStart.countMinLeadingZeros()))
       CR = CR.intersectWith(ConstantRange(KnownStart.getMinValue(),
                                           KnownEnd.getMaxValue() + 1));
     break;

llvm/test/Analysis/ScalarEvolution/shift-recurrences.ll

 }
 
 define void @test_lshr_tc_positive() {
 ; CHECK-LABEL: 'test_lshr_tc_positive'
 ; CHECK-NEXT:  Classifying expressions for: @test_lshr_tc_positive
 ; CHECK-NEXT:    %iv = phi i64 [ 0, %entry ], [ %iv.next, %loop ]
 ; CHECK-NEXT:    --> {0,+,1}<%loop> U: [0,5) S: [0,5) Exits: 4 LoopDispositions: { %loop: Computable }
 ; CHECK-NEXT:    %iv.lshr = phi i64 [ 1023, %entry ], [ %iv.lshr.next, %loop ]
-; CHECK-NEXT:    --> %iv.lshr U: [0,1024) S: [0,1024) Exits: 63 LoopDispositions: { %loop: Variant }
+; CHECK-NEXT:    --> %iv.lshr U: [63,1024) S: [63,1024) Exits: 63 LoopDispositions: { %loop: Variant }
 ; CHECK-NEXT:    %iv.next = add i64 %iv, 1
 ; CHECK-NEXT:    --> {1,+,1}<%loop> U: [1,6) S: [1,6) Exits: 5 LoopDispositions: { %loop: Computable }
 ; CHECK-NEXT:    %iv.lshr.next = lshr i64 %iv.lshr, 1
-; CHECK-NEXT:    --> (%iv.lshr /u 2) U: [0,512) S: [0,512) Exits: 31 LoopDispositions: { %loop: Variant }
+; CHECK-NEXT:    --> (%iv.lshr /u 2) U: [31,512) S: [31,512) Exits: 31 LoopDispositions: { %loop: Variant }
 ; CHECK-NEXT:  Determining loop execution counts for: @test_lshr_tc_positive
 ; CHECK-NEXT:  Loop %loop: backedge-taken count is 4
 ; CHECK-NEXT:  Loop %loop: max backedge-taken count is 4
 ; CHECK-NEXT:  Loop %loop: Predicated backedge-taken count is 4
 ; CHECK-NEXT:   Predicates:
 ; CHECK:       Loop %loop: Trip multiple is 5
 ;
 entry:

 }
 
 define void @test_lshr_tc_negative() {
 ; CHECK-LABEL: 'test_lshr_tc_negative'
 ; CHECK-NEXT:  Classifying expressions for: @test_lshr_tc_negative
 ; CHECK-NEXT:    %iv = phi i64 [ 0, %entry ], [ %iv.next, %loop ]
 ; CHECK-NEXT:    --> {0,+,1}<%loop> U: [0,5) S: [0,5) Exits: 4 LoopDispositions: { %loop: Computable }
 ; CHECK-NEXT:    %iv.lshr = phi i8 [ -1, %entry ], [ %iv.lshr.next, %loop ]
-; CHECK-NEXT:    --> %iv.lshr U: [-1,-128) S: [-1,-128) Exits: 15 LoopDispositions: { %loop: Variant }
+; CHECK-NEXT:    --> %iv.lshr U: [15,0) S: [-1,-128) Exits: 15 LoopDispositions: { %loop: Variant }
 ; CHECK-NEXT:    %iv.next = add i64 %iv, 1
 ; CHECK-NEXT:    --> {1,+,1}<%loop> U: [1,6) S: [1,6) Exits: 5 LoopDispositions: { %loop: Computable }
 ; CHECK-NEXT:    %iv.lshr.next = lshr i8 %iv.lshr, 1
-; CHECK-NEXT:    --> (%iv.lshr /u 2) U: [0,-128) S: [0,-128) Exits: 7 LoopDispositions: { %loop: Variant }
+; CHECK-NEXT:    --> (%iv.lshr /u 2) U: [7,-128) S: [7,-128) Exits: 7 LoopDispositions: { %loop: Variant }
 ; CHECK-NEXT:  Determining loop execution counts for: @test_lshr_tc_negative
 ; CHECK-NEXT:  Loop %loop: backedge-taken count is 4
 ; CHECK-NEXT:  Loop %loop: max backedge-taken count is 4
 ; CHECK-NEXT:  Loop %loop: Predicated backedge-taken count is 4
 ; CHECK-NEXT:   Predicates:
 ; CHECK:       Loop %loop: Trip multiple is 5
 ;
 entry:

 }
 
 define void @test_lshr_zero_shift() {
 ; CHECK-LABEL: 'test_lshr_zero_shift'
 ; CHECK-NEXT:  Classifying expressions for: @test_lshr_zero_shift
 ; CHECK-NEXT:    %iv = phi i64 [ 0, %entry ], [ %iv.next, %loop ]
 ; CHECK-NEXT:    --> {0,+,1}<%loop> U: [0,5) S: [0,5) Exits: 4 LoopDispositions: { %loop: Computable }
 ; CHECK-NEXT:    %iv.lshr = phi i64 [ 1023, %entry ], [ %iv.lshr.next, %loop ]
-; CHECK-NEXT:    --> %iv.lshr U: [0,1024) S: [0,1024) Exits: 1023 LoopDispositions: { %loop: Variant }
+; CHECK-NEXT:    --> %iv.lshr U: [1023,1024) S: [1023,1024) Exits: 1023 LoopDispositions: { %loop: Variant }
 ; CHECK-NEXT:    %iv.next = add i64 %iv, 1
 ; CHECK-NEXT:    --> {1,+,1}<%loop> U: [1,6) S: [1,6) Exits: 5 LoopDispositions: { %loop: Computable }
 ; CHECK-NEXT:    %iv.lshr.next = lshr i64 %iv.lshr, 0
-; CHECK-NEXT:    --> %iv.lshr U: [0,1024) S: [0,1024) Exits: 1023 LoopDispositions: { %loop: Variant }
+; CHECK-NEXT:    --> %iv.lshr U: [1023,1024) S: [1023,1024) Exits: 1023 LoopDispositions: { %loop: Variant }
 ; CHECK-NEXT:  Determining loop execution counts for: @test_lshr_zero_shift
 ; CHECK-NEXT:  Loop %loop: backedge-taken count is 4
 ; CHECK-NEXT:  Loop %loop: max backedge-taken count is 4
 ; CHECK-NEXT:  Loop %loop: Predicated backedge-taken count is 4
 ; CHECK-NEXT:   Predicates:
 ; CHECK:       Loop %loop: Trip multiple is 5
 ;
 entry:

 
 
 define void @test_lshr_power_of_2_start() {
 ; CHECK-LABEL: 'test_lshr_power_of_2_start'
 ; CHECK-NEXT:  Classifying expressions for: @test_lshr_power_of_2_start
 ; CHECK-NEXT:    %iv = phi i64 [ 0, %entry ], [ %iv.next, %loop ]
 ; CHECK-NEXT:    --> {0,+,1}<%loop> U: [0,5) S: [0,5) Exits: 4 LoopDispositions: { %loop: Computable }
 ; CHECK-NEXT:    %iv.lshr = phi i64 [ 1024, %entry ], [ %iv.lshr.next, %loop ]
-; CHECK-NEXT:    --> %iv.lshr U: [0,1025) S: [0,1025) Exits: 4 LoopDispositions: { %loop: Variant }
+; CHECK-NEXT:    --> %iv.lshr U: [4,1025) S: [4,1025) Exits: 4 LoopDispositions: { %loop: Variant }
 ; CHECK-NEXT:    %iv.next = add i64 %iv, 1
 ; CHECK-NEXT:    --> {1,+,1}<%loop> U: [1,6) S: [1,6) Exits: 5 LoopDispositions: { %loop: Computable }
 ; CHECK-NEXT:    %iv.lshr.next = lshr i64 %iv.lshr, 2
-; CHECK-NEXT:    --> (%iv.lshr /u 4) U: [0,512) S: [0,512) Exits: 1 LoopDispositions: { %loop: Variant }
+; CHECK-NEXT:    --> (%iv.lshr /u 4) U: [1,257) S: [1,257) Exits: 1 LoopDispositions: { %loop: Variant }
 ; CHECK-NEXT:  Determining loop execution counts for: @test_lshr_power_of_2_start
 ; CHECK-NEXT:  Loop %loop: backedge-taken count is 4
 ; CHECK-NEXT:  Loop %loop: max backedge-taken count is 4
 ; CHECK-NEXT:  Loop %loop: Predicated backedge-taken count is 4
 ; CHECK-NEXT:   Predicates:
 ; CHECK:       Loop %loop: Trip multiple is 5
 ;
 entry:

 
 ; Starting value is chosen not to be near power of 2
 define void @test_lshr_arbitrary_start() {
 ; CHECK-LABEL: 'test_lshr_arbitrary_start'
 ; CHECK-NEXT:  Classifying expressions for: @test_lshr_arbitrary_start
 ; CHECK-NEXT:    %iv = phi i64 [ 0, %entry ], [ %iv.next, %loop ]
 ; CHECK-NEXT:    --> {0,+,1}<%loop> U: [0,5) S: [0,5) Exits: 4 LoopDispositions: { %loop: Computable }
 ; CHECK-NEXT:    %iv.lshr = phi i64 [ 957, %entry ], [ %iv.lshr.next, %loop ]
-; CHECK-NEXT:    --> %iv.lshr U: [0,958) S: [0,958) Exits: 3 LoopDispositions: { %loop: Variant }
+; CHECK-NEXT:    --> %iv.lshr U: [3,958) S: [3,958) Exits: 3 LoopDispositions: { %loop: Variant }
 ; CHECK-NEXT:    %iv.next = add i64 %iv, 1
 ; CHECK-NEXT:    --> {1,+,1}<%loop> U: [1,6) S: [1,6) Exits: 5 LoopDispositions: { %loop: Computable }
 ; CHECK-NEXT:    %iv.lshr.next = lshr i64 %iv.lshr, 2
-; CHECK-NEXT:    --> (%iv.lshr /u 4) U: [0,256) S: [0,256) Exits: 0 LoopDispositions: { %loop: Variant }
+; CHECK-NEXT:    --> (%iv.lshr /u 4) U: [0,240) S: [0,240) Exits: 0 LoopDispositions: { %loop: Variant }
 ; CHECK-NEXT:  Determining loop execution counts for: @test_lshr_arbitrary_start
 ; CHECK-NEXT:  Loop %loop: backedge-taken count is 4
 ; CHECK-NEXT:  Loop %loop: max backedge-taken count is 4
 ; CHECK-NEXT:  Loop %loop: Predicated backedge-taken count is 4
 ; CHECK-NEXT:   Predicates:
 ; CHECK:       Loop %loop: Trip multiple is 5
 ;
 entry:

 }
 
 define void @test_lshr_start_power_of_2_plus_one() {
 ; CHECK-LABEL: 'test_lshr_start_power_of_2_plus_one'
 ; CHECK-NEXT:  Classifying expressions for: @test_lshr_start_power_of_2_plus_one
 ; CHECK-NEXT:    %iv = phi i64 [ 0, %entry ], [ %iv.next, %loop ]
 ; CHECK-NEXT:    --> {0,+,1}<%loop> U: [0,5) S: [0,5) Exits: 4 LoopDispositions: { %loop: Computable }
 ; CHECK-NEXT:    %iv.lshr = phi i64 [ 1025, %entry ], [ %iv.lshr.next, %loop ]
-; CHECK-NEXT:    --> %iv.lshr U: [0,1026) S: [0,1026) Exits: 4 LoopDispositions: { %loop: Variant }
+; CHECK-NEXT:    --> %iv.lshr U: [4,1026) S: [4,1026) Exits: 4 LoopDispositions: { %loop: Variant }
 ; CHECK-NEXT:    %iv.next = add i64 %iv, 1
 ; CHECK-NEXT:    --> {1,+,1}<%loop> U: [1,6) S: [1,6) Exits: 5 LoopDispositions: { %loop: Computable }
 ; CHECK-NEXT:    %iv.lshr.next = lshr i64 %iv.lshr, 2
-; CHECK-NEXT:    --> (%iv.lshr /u 4) U: [0,512) S: [0,512) Exits: 1 LoopDispositions: { %loop: Variant }
+; CHECK-NEXT:    --> (%iv.lshr /u 4) U: [1,257) S: [1,257) Exits: 1 LoopDispositions: { %loop: Variant }
 ; CHECK-NEXT:  Determining loop execution counts for: @test_lshr_start_power_of_2_plus_one
 ; CHECK-NEXT:  Loop %loop: backedge-taken count is 4
 ; CHECK-NEXT:  Loop %loop: max backedge-taken count is 4
 ; CHECK-NEXT:  Loop %loop: Predicated backedge-taken count is 4
 ; CHECK-NEXT:   Predicates:
 ; CHECK:       Loop %loop: Trip multiple is 5
 ;
 entry: