[SCEV] ] If RHS >= Start, simplify (Start smax RHS) to RHS for trip counts.

[fhahn]

Summary

This is the max version of D85046.

This change causes binary changes in 44 out of 237 benchmarks (out of
MultiSource/SPEC2000/SPEC2006)

[lebedev.ri]

Looks good to me.

[lebedev.ri]

I feel like this is pretty identical to the D85046, so lgtm modulo some possible generalization.

llvm/lib/Analysis/ScalarEvolution.cpp

ScalarEvolution::howManyLessThans(const SCEV *LHS, const SCEV *RHS,
   // expression (max(End,Start)-Start)/Stride to describe the backedge count,
   // as if the backedge is taken at least once max(End,Start) is End and so the
   // result is as above, and if not max(End,Start) is Start so we get a backedge
   // count of zero.
   const SCEV *BECount;
   if (isLoopEntryGuardedByCond(L, Cond, getMinusSCEV(Start, Stride), RHS))
     BECount = BECountIfBackedgeTaken;
   else {
+    // If we know that RHS >= Start in the context of loop, then we know that
+    // max(RHS, Start) = RHS at this point.
+    if (isLoopEntryGuardedByCond(
+            L, IsSigned ? ICmpInst::ICMP_SGE : ICmpInst::ICMP_UGE, RHS, Start))
+      End = RHS;
+    else
       End = IsSigned ? getSMaxExpr(RHS, Start) : getUMaxExpr(RHS, Start);
     BECount = computeBECount(getMinusSCEV(End, Start), Stride, false);
   }
 
   const SCEV *MaxBECount;
   bool MaxOrZero = false;
   if (isa<SCEVConstant>(BECount))
     MaxBECount = BECount;
   else if (isa<SCEVConstant>(BECountIfBackedgeTaken)) {

llvm/test/Analysis/ScalarEvolution/smin-smax-folds.ll

for.cond.cleanup:
   ret void
 }
 
 ; The information from the loop guard can be used to simplify the trip count expression.
 define void @smax_simplify_with_guard(i32 %start, i32 %n) {
 ; CHECK-LABEL:  'smax_simplify_with_guard'
 ; CHECK-NEXT:  Classifying expressions for: @smax_simplify_with_guard
 ; CHECK-NEXT:    %k.0.i26 = phi i32 [ %start, %loop.ph ], [ %inc.i, %loop ]
-; CHECK-NEXT:    -->  {%start,+,1}<nsw><%loop> U: full-set S: full-set      Exits: (%start smax %n)     LoopDispositions: { %loop: Computable }
+; CHECK-NEXT:    -->  {%start,+,1}<nsw><%loop> U: full-set S: full-set      Exits: %n     LoopDispositions: { %loop: Computable }
 ; CHECK-NEXT:    %inc.i = add nsw i32 %k.0.i26, 1
-; CHECK-NEXT:    -->  {(1 + %start),+,1}<nw><%loop> U: full-set S: full-set     Exits: (1 + (%start smax %n))       LoopDispositions: { %loop: Computable }
+; CHECK-NEXT:    -->  {(1 + %start),+,1}<nw><%loop> U: full-set S: full-set     Exits: (1 + %n)       LoopDispositions: { %loop: Computable }
 ; CHECK-NEXT:  Determining loop execution counts for: @smax_simplify_with_guard
-; CHECK-NEXT:  Loop %loop: backedge-taken count is ((-1 * %start) + (%start smax %n))
+; CHECK-NEXT:  Loop %loop: backedge-taken count is ((-1 * %start) + %n)
 ; CHECK-NEXT:  Loop %loop: max backedge-taken count is -1
-; CHECK-NEXT:  Loop %loop: Predicated backedge-taken count is ((-1 * %start) + (%start smax %n))
+; CHECK-NEXT:  Loop %loop: Predicated backedge-taken count is ((-1 * %start) +  %n)
 ; CHECK-NEXT:   Predicates:
 ; CHECK:       Loop %loop: Trip multiple is 1
 entry:
   %guard = icmp sge i32 %n, %start
   br i1 %guard, label %loop.ph, label %exit
 
 loop.ph:
   br label %loop