[SCEV] Apply guards to max with non-unitary steps.

[fhahn]

Summary

We already apply loop-guards when computing the maximum with unitary
steps. This extends the code to also do so when dealing with non-unitary
steps.

This allows us to infer a tighter maximum in some cases.

[nikic]

llvm/lib/Analysis/ScalarEvolution.cpp

9269

Is there any particular reason to believe that this assertion can't be hit? The unit step case takes the minimum and has a test for this (@guard_pessimizes_analysis). Or is the assert here so we can find a test case?

On a related note, I wonder if we shouldn't be limiting the guard insertion to comparisons against constants. That case should be non-pessimizing, and at least none of the existing tests benefit from non-constant guards.

[fhahn]

Add test where applying guards pessimizes range (96c1fa2a041d), replace assert with conditional assignment.

[fhahn]

llvm/lib/Analysis/ScalarEvolution.cpp

9269

Is there any particular reason to believe that this assertion can't be hit? The unit step case takes the minimum and has a test for this (@guard_pessimizes_analysis). Or is the assert here so we can find a test case?

I was overly optimistic. But I added a variant of @guard_pessimizes_analysis that would trigger the assert. Replaced that with a conditional assignment.

On a related note, I wonder if we shouldn't be limiting the guard insertion to comparisons against constants. That case should be non-pessimizing, and at least none of the existing tests benefit from non-constant guards.

I think in theory rewriting with non-constants could also help in some cases, but probably not in practice at the moment. I'm planning to look into that separately, possible to also help with pessimizing results after applying guards.

[nikic]

LGTM

llvm/lib/Analysis/ScalarEvolution.cpp

9269

On a related note, I wonder if we shouldn't be limiting the guard insertion to comparisons against constants. That case should be non-pessimizing, and at least none of the existing tests benefit from non-constant guards.

I think in theory rewriting with non-constants could also help in some cases, but probably not in practice at the moment. I'm planning to look into that separately, possible to also help with pessimizing results after applying guards.

To avoid pessimization, we could do something like this: For LHS ule RHS rewrite to umin(LHS, getUnsignedRangeMax(RHS)) rather than umin(LHS, RHS). Though I suspect that for practical purposes, just limiting to constants would be fine.

9272

Max = getConstant(APIntOps::umin(MaxInt, BaseMaxInt)) maybe?

llvm/lib/Analysis/ScalarEvolution.cpp

ScalarEvolution::howFarToZero(const SCEV *V, const Loop *L, bool ControlsExit,
   // is true) and the addition is no-wrap we can use unsigned divide to
   // compute the backedge count.  In this case, the step may not divide the
   // distance, but we don't care because if the condition is "missed" the loop
   // will have undefined behavior due to wrapping.
   if (ControlsExit && AddRec->hasNoSelfWrap() &&
       loopHasNoAbnormalExits(AddRec->getLoop())) {
     const SCEV *Exact =
         getUDivExpr(Distance, CountDown ? getNegativeSCEV(Step) : Step);
-    const SCEV *Max =
-        Exact == getCouldNotCompute()
-            ? Exact
-            : getConstant(getUnsignedRangeMax(Exact));
+    const SCEV *Max = getCouldNotCompute();
+    if (Exact != getCouldNotCompute()) {
+      APInt MaxInt = getUnsignedRangeMax(applyLoopGuards(Exact, L));
+      APInt BaseMaxInt = getUnsignedRangeMax(Exact);
+      if (BaseMaxInt.ult(MaxInt))
+        Max = getConstant(BaseMaxInt);
+      else
+        Max = getConstant(MaxInt);
+    }
     return ExitLimit(Exact, Max, false, Predicates);
   }
 
   // Solve the general equation.
   const SCEV *E = SolveLinEquationWithOverflow(StepC->getAPInt(),
                                                getNegativeSCEV(Start), *this);
   const SCEV *M = E == getCouldNotCompute()
                       ? E

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

 exit:
   ret void
 }
 
 define void @test_guard_ule_12_step2(i32* nocapture %a, i64 %N) {
 ; CHECK-LABEL: 'test_guard_ule_12_step2'
 ; CHECK-NEXT:  Classifying expressions for: @test_guard_ule_12_step2
 ; CHECK-NEXT:    %iv = phi i64 [ %iv.next, %loop ], [ 0, %entry ]
-; CHECK-NEXT:    --> {0,+,2}<nuw><nsw><%loop> U: [0,-9223372036854775808) S: [0,9223372036854775807) Exits: (2 * (%N /u 2))<nuw> LoopDispositions: { %loop: Computable }
+; CHECK-NEXT:    --> {0,+,2}<nuw><nsw><%loop> U: [0,13) S: [0,13) Exits: (2 * (%N /u 2))<nuw> LoopDispositions: { %loop: Computable }
 ; CHECK-NEXT:    %idx = getelementptr inbounds i32, i32* %a, i64 %iv
 ; CHECK-NEXT:    --> {%a,+,8}<nuw><%loop> U: full-set S: full-set Exits: ((8 * (%N /u 2)) + %a) LoopDispositions: { %loop: Computable }
 ; CHECK-NEXT:    %iv.next = add nuw nsw i64 %iv, 2
-; CHECK-NEXT:    --> {2,+,2}<nuw><%loop> U: [2,-1) S: [-9223372036854775808,9223372036854775807) Exits: (2 + (2 * (%N /u 2))<nuw>) LoopDispositions: { %loop: Computable }
+; CHECK-NEXT:    --> {2,+,2}<nuw><nsw><%loop> U: [2,15) S: [2,15) Exits: (2 + (2 * (%N /u 2))<nuw>) LoopDispositions: { %loop: Computable }
 ; CHECK-NEXT:  Determining loop execution counts for: @test_guard_ule_12_step2
 ; CHECK-NEXT:  Loop %loop: backedge-taken count is (%N /u 2)
-; CHECK-NEXT:  Loop %loop: max backedge-taken count is 9223372036854775807
+; CHECK-NEXT:  Loop %loop: max backedge-taken count is 6
 ; CHECK-NEXT:  Loop %loop: Predicated backedge-taken count is (%N /u 2)
 ; CHECK-NEXT:   Predicates:
 ; CHECK:       Loop %loop: Trip multiple is 1
 ;
 entry:
   %c.1 = icmp ule i64 %N, 12
   br i1 %c.1, label %loop, label %exit