[SCEV] Improve AddRecs' range computation

[aleksandr.popov]

Summary

Apply loop guards to AddRec's start in range computation for
non-self-wrapping AddRecs

[mkazantsev]

llvm/lib/Analysis/ScalarEvolution.cpp

6736

Do we also need getRangeViaFactoring?

[mkazantsev]

llvm/lib/Analysis/ScalarEvolution.cpp

6711

Refactor with moving const Loop *L = AddRec->getLoop(); earlier?

llvm/test/Analysis/ScalarEvolution/decrementing_addrecs.ll

21

Remove FIXME's

[nikic]

This is too expensive in terms of compile-time: http://llvm-compile-time-tracker.com/compare.php?from=712dfec1781db8aa92782b98cac5517db548b7f9&to=2a04edbcecc77f3d80597662a4ba19f521874d62&stat=instructions:u You're probably forcing an extra invalidation cycle here or something.

I'm also not sure whether the overall approach really makes sense. We shouldn't really get more information from the exit value than we already get from the addrec and the BE count. From what I can tell based on the test changes, the primary benefit here seems to be that we now take into account guard information on the addrec start value -- so a possible alternative would be to apply guards to the start value when calculating addrec ranges, or something along those lines?

[mkazantsev]

Yeah. Why exactly getRangeForAffineAR could not infer the same facts? Maybe it's doing something over-conservative? I think we could do more in terms of symbolic computations and not range computations in there.

[aleksandr.popov]

@nikic Thanks for the advice, I've applied loop guards to the AddRec's start value in the getRangeForAffineNoSelfWrappingAR and now symbolic computations work for the example from decrementing_addrecs.ll

[mkazantsev]

llvm/test/Analysis/ScalarEvolution/decrementing_addrecs.ll

2–3

Let's have 2 run commands - with and without expensive checks, to highlight the difference.

[mkazantsev]

Code change LG, I'll update this test with two different run commands to see what change comes from expensive sharpening and what from your patch.

Also please wait for Nikita to take a look.

[mkazantsev]

LG, but let's wait few days in case if anyone else has concerns/objections.

It would also be great if we could find a way to do it w/o expensive sharpening. There are usually several ways to achieving the same effect.

@aleksandr.popov during this chill period, could you please try to construct a test that shows benefit from your patch w/o expensive sharpening?

[nikic]

In D147557#4250538, @mkazantsev wrote:

LG, but let's wait few days in case if anyone else has concerns/objections.

It would also be great if we could find a way to do it w/o expensive sharpening. There are usually several ways to achieving the same effect.

@aleksandr.popov during this chill period, could you please try to construct a test that shows benefit from your patch w/o expensive sharpening?

The changed code is only used by expensive sharpening, so no :)

I tried applying loop guards to other places like getRangeForAffineAR() as well, but this again had very bad compile-time impact: https://llvm-compile-time-tracker.com/compare.php?from=2caaec65c04ea7d0e9568b7895b7a46d6100cb75&to=87d1063758a038ffa7a0e358dc97c16ef6297aa3&stat=instructions:u Here's the corresponding diff: https://github.com/llvm/llvm-project/commit/87d1063758a038ffa7a0e358dc97c16ef6297aa3 I was hoping that doing this is pretty cheap, but apparently it isn't.

[mkazantsev]

Ah ok, since it's only in expensive sharpening, then it should be fine.

Nikita, what's overall impact of expensive range sharpening together with this patch? It's sad for me that it is switched off by default. I'll maybe need to investigate why exactly it's so expensive and fix it.

[nikic]

In D147557#4255027, @mkazantsev wrote:

Nikita, what's overall impact of expensive range sharpening together with this patch? It's sad for me that it is switched off by default. I'll maybe need to investigate why exactly it's so expensive and fix it.

Here are the compile-time results for just flipping the flag to true: http://llvm-compile-time-tracker.com/compare.php?from=b8917ac62ad49a0ce6de026c086599fc5fa35566&to=f0c3b441b6b01bb09c28c8608c5904d1910cd6d1&stat=instructions:u

llvm/lib/Analysis/ScalarEvolution.cpp

if (AddRec->hasNoSignedWrap()) {
                                        getSignedRangeMax(AddRec->getStart()) +
                                            1),
             RangeType);
     }
 
     // TODO: non-affine addrec
     if (AddRec->isAffine()) {
       const SCEV *MaxBECount =
           getConstantMaxBackedgeTakenCount(AddRec->getLoop());
       if (!isa<SCEVCouldNotCompute>(MaxBECount) &&
           getTypeSizeInBits(MaxBECount->getType()) <= BitWidth) {
         auto RangeFromAffine = getRangeForAffineAR(
             AddRec->getStart(), AddRec->getStepRecurrence(*this), MaxBECount,
             BitWidth);
         ConservativeResult =
             ConservativeResult.intersectWith(RangeFromAffine, RangeType);
 
         auto RangeFromFactoring = getRangeViaFactoring(
             AddRec->getStart(), AddRec->getStepRecurrence(*this), MaxBECount,
             BitWidth);
         ConservativeResult =
             ConservativeResult.intersectWith(RangeFromFactoring, RangeType);
       }
 
       // Now try symbolic BE count and more powerful methods.
       if (UseExpensiveRangeSharpening) {
         const SCEV *SymbolicMaxBECount =
             getSymbolicMaxBackedgeTakenCount(AddRec->getLoop());
         if (!isa<SCEVCouldNotCompute>(SymbolicMaxBECount) &&
             getTypeSizeInBits(MaxBECount->getType()) <= BitWidth &&
             AddRec->hasNoSelfWrap()) {
           auto RangeFromAffineNew = getRangeForAffineNoSelfWrappingAR(
               AddRec, SymbolicMaxBECount, BitWidth, SignHint);
           ConservativeResult =
               ConservativeResult.intersectWith(RangeFromAffineNew, RangeType);
         }
       }
     }
 
     return setRange(AddRec, SignHint, std::move(ConservativeResult));
   }
   case scUMaxExpr:
ConstantRange ScalarEvolution::getRangeForAffineNoSelfWrappingAR(
   //
   // Case 1:   RangeMin    ...    Start V1 ... VN End ...           RangeMax;
   // Case 2:   RangeMin Vk ... V1 Start    ...    End Vn ... Vk + 1 RangeMax;
   //
   // No self wrap flag guarantees that the intermediate values cannot be BOTH
   // outside and inside the range [Min(Start, End), Max(Start, End)]. Using that
   // knowledge, let's try to prove that we are dealing with Case 1. It is so if
   // Start <= End and step is positive, or Start >= End and step is negative.
-  const SCEV *Start = AddRec->getStart();
+  const SCEV *Start = applyLoopGuards(AddRec->getStart(), AddRec->getLoop());
   ConstantRange StartRange = getRangeRef(Start, SignHint);
   ConstantRange EndRange = getRangeRef(End, SignHint);
   ConstantRange RangeBetween = StartRange.unionWith(EndRange);
   // If they already cover full iteration space, we will know nothing useful
   // even if we prove what we want to prove.
   if (RangeBetween.isFullSet())
     return RangeBetween;
   // Only deal with ranges that do not wrap (i.e. RangeMin < RangeMax).

llvm/test/Analysis/ScalarEvolution/decrementing_addrecs.ll

 ; NOTE: Assertions have been autogenerated by utils/update_analyze_test_checks.py UTC_ARGS: --version 2
 ; RUN: opt -disable-output "-passes=print<scalar-evolution>" < %s 2>&1 | FileCheck %s --check-prefix=DEFAULT
 ; RUN: opt -disable-output "-passes=print<scalar-evolution>" -scalar-evolution-use-expensive-range-sharpening < %s 2>&1 | FileCheck %s  --check-prefix=EXPENSIVE_SHARPENING
 
 ; This test exercises the following scenario:
 ; given: n > 0
 ; for (i = 0, j = n - 1; i < n; i++, j--) {
 ;   a = n - i;
 ;   b = (n - 1) - i;
 ;   c = 2147483647 - 1;
 ; }
 ;
 ; Note that value ranges of 'i' and 'j' are the same, just inverted. It means that
 ; they have same ranges and same no-wrap properties. 'b' is just an alternative
 ; way to compute the same value as 'j'. 'a' is effectively 'j + 1' and 'c' is a
 ; a positive value. All involved addrecs for 'i', 'j', 'a', 'b', 'c' should have
 ; no-sign-wrap flag.
 ;
 ;        i's AddRec is expected to be proven no-sign-wrap
 ;        j's AddRec is expected to be proven no-sign-wrap
 ; FIXME: a's AddRec is expected to be no-sign-wrap
 ;        b's AddRec is expected to be no-sign-wrap
 ; FIXME: c's AddRec is expected to be no-sign-wrap
 ;        i is expected to be non-negative
 ;        j is expected to be non-negative
-; FIXME: a is expected to be positive
-; FIXME: b is expected to be non-negative
+;        a is expected to be positive
+;        b is expected to be non-negative
 ;        c is expected to be positive
 define i32 @test_step_1_flags(i32 %n) {
 ; DEFAULT-LABEL: 'test_step_1_flags'
 ; DEFAULT-NEXT:  Classifying expressions for: @test_step_1_flags
 ; DEFAULT-NEXT:    %n.minus.1 = sub nsw i32 %n, 1
 ; DEFAULT-NEXT:    --> (-1 + %n) U: full-set S: full-set
 ; DEFAULT-NEXT:    %i = phi i32 [ 0, %entry ], [ %i.next, %loop ]
 ; DEFAULT-NEXT:    --> {0,+,1}<nuw><nsw><%loop> U: [0,2147483647) S: [0,2147483647) Exits: (-1 + %n) LoopDispositions: { %loop: Computable }

 ;
 ; EXPENSIVE_SHARPENING-LABEL: 'test_step_1_flags'
 ; EXPENSIVE_SHARPENING-NEXT:  Classifying expressions for: @test_step_1_flags
 ; EXPENSIVE_SHARPENING-NEXT:    %n.minus.1 = sub nsw i32 %n, 1
 ; EXPENSIVE_SHARPENING-NEXT:    --> (-1 + %n) U: full-set S: full-set
 ; EXPENSIVE_SHARPENING-NEXT:    %i = phi i32 [ 0, %entry ], [ %i.next, %loop ]
 ; EXPENSIVE_SHARPENING-NEXT:    --> {0,+,1}<nuw><nsw><%loop> U: [0,2147483647) S: [0,2147483647) Exits: (-1 + %n) LoopDispositions: { %loop: Computable }
 ; EXPENSIVE_SHARPENING-NEXT:    %j = phi i32 [ %n.minus.1, %entry ], [ %j.next, %loop ]
-; EXPENSIVE_SHARPENING-NEXT:    --> {(-1 + %n),+,-1}<nsw><%loop> U: full-set S: full-set Exits: 0 LoopDispositions: { %loop: Computable }
+; EXPENSIVE_SHARPENING-NEXT:    --> {(-1 + %n),+,-1}<nsw><%loop> U: [0,2147483647) S: [0,2147483647) Exits: 0 LoopDispositions: { %loop: Computable }
 ; EXPENSIVE_SHARPENING-NEXT:    %a = sub i32 %n, %i
-; EXPENSIVE_SHARPENING-NEXT:    --> {%n,+,-1}<nw><%loop> U: full-set S: full-set Exits: 1 LoopDispositions: { %loop: Computable }
+; EXPENSIVE_SHARPENING-NEXT:    --> {%n,+,-1}<nw><%loop> U: [1,-2147483648) S: [1,-2147483648) Exits: 1 LoopDispositions: { %loop: Computable }
 ; EXPENSIVE_SHARPENING-NEXT:    %b = sub i32 %n.minus.1, %i
-; EXPENSIVE_SHARPENING-NEXT:    --> {(-1 + %n),+,-1}<nsw><%loop> U: full-set S: full-set Exits: 0 LoopDispositions: { %loop: Computable }
+; EXPENSIVE_SHARPENING-NEXT:    --> {(-1 + %n),+,-1}<nsw><%loop> U: [0,2147483647) S: [0,2147483647) Exits: 0 LoopDispositions: { %loop: Computable }
 ; EXPENSIVE_SHARPENING-NEXT:    %c = sub i32 2147483647, %i
 ; EXPENSIVE_SHARPENING-NEXT:    --> {2147483647,+,-1}<nw><%loop> U: [1,-2147483648) S: [1,-2147483648) Exits: (-2147483648 + (-1 * %n)) LoopDispositions: { %loop: Computable }
 ; EXPENSIVE_SHARPENING-NEXT:    %i.next = add nuw nsw i32 %i, 1
 ; EXPENSIVE_SHARPENING-NEXT:    --> {1,+,1}<nuw><nsw><%loop> U: [1,-2147483648) S: [1,-2147483648) Exits: %n LoopDispositions: { %loop: Computable }
 ; EXPENSIVE_SHARPENING-NEXT:    %j.next = add nsw i32 %j, -1
-; EXPENSIVE_SHARPENING-NEXT:    --> {(-2 + %n),+,-1}<nw><%loop> U: full-set S: full-set Exits: -1 LoopDispositions: { %loop: Computable }
+; EXPENSIVE_SHARPENING-NEXT:    --> {(-2 + %n),+,-1}<nsw><%loop> U: full-set S: [-1,2147483646) Exits: -1 LoopDispositions: { %loop: Computable }
 ; EXPENSIVE_SHARPENING-NEXT:  Determining loop execution counts for: @test_step_1_flags
 ; EXPENSIVE_SHARPENING-NEXT:  Loop %loop: backedge-taken count is (-1 + %n)
 ; EXPENSIVE_SHARPENING-NEXT:  Loop %loop: constant max backedge-taken count is 2147483646
 ; EXPENSIVE_SHARPENING-NEXT:  Loop %loop: symbolic max backedge-taken count is (-1 + %n)
 ; EXPENSIVE_SHARPENING-NEXT:  Loop %loop: Predicated backedge-taken count is (-1 + %n)
 ; EXPENSIVE_SHARPENING-NEXT:   Predicates:
 ; EXPENSIVE_SHARPENING:       Loop %loop: Trip multiple is 1
 ;