[SCEV] If Start >= RHS, simplify (Start smin RHS) to RHS for trip counts (PR46924, PR46939)

[fhahn]

Summary

In some cases, it seems like we can get rid of unnecessary s/umins by
using information from the loop guards (unless I am missing something).

One place where this seems to be helpful in practice is when computing
loop trip counts. This patch just changes howManyGreaterThans for now.
Note that this requires a loop for which we can check 'is guarded'.

On SPEC2000/SPEC2006/MultiSource, there are some notable changes for
some programs in the number of loops unrolled and trip counts computed.

Same hash: 179 (filtered out)
Remaining: 58
Metric: scalar-evolution.NumTripCountsComputed

Program                                        base    patch   diff
 test-suite...langs-C/compiler/compiler.test    25.00   31.00  24.0%
 test-suite.../Applications/SPASS/SPASS.test   2020.00 2323.00 15.0%
 test-suite...langs-C/allroots/allroots.test    29.00   32.00  10.3%
 test-suite.../Prolangs-C/loader/loader.test    17.00   18.00   5.9%
 test-suite...fice-ispell/office-ispell.test   253.00  265.00   4.7%
 test-suite...006/450.soplex/450.soplex.test   3552.00 3692.00  3.9%
 test-suite...chmarks/MallocBench/gs/gs.test   453.00  470.00   3.8%
 test-suite...ngs-C/assembler/assembler.test    29.00   30.00   3.4%
 test-suite.../Benchmarks/Ptrdist/bc/bc.test   263.00  270.00   2.7%
 test-suite...rks/FreeBench/pifft/pifft.test   722.00  741.00   2.6%
 test-suite...count/automotive-bitcount.test    41.00   42.00   2.4%
 test-suite...0/253.perlbmk/253.perlbmk.test   1417.00 1451.00  2.4%
 test-suite...000/197.parser/197.parser.test   387.00  396.00   2.3%
 test-suite...lications/sqlite3/sqlite3.test   1168.00 1189.00  1.8%
 test-suite...000/255.vortex/255.vortex.test   173.00  176.00   1.7%

Metric: loop-unroll.NumUnrolled

Program                                        base   patch  diff
 test-suite...langs-C/compiler/compiler.test     1.00   3.00 200.0%
 test-suite.../Applications/SPASS/SPASS.test   134.00 234.00 74.6%
 test-suite...count/automotive-bitcount.test     3.00   4.00 33.3%
 test-suite.../Prolangs-C/loader/loader.test     3.00   4.00 33.3%
 test-suite...langs-C/allroots/allroots.test     3.00   4.00 33.3%
 test-suite...Source/Benchmarks/sim/sim.test    10.00  12.00 20.0%
 test-suite...fice-ispell/office-ispell.test    21.00  25.00 19.0%
 test-suite.../Benchmarks/Ptrdist/bc/bc.test    32.00  38.00 18.8%
 test-suite...006/450.soplex/450.soplex.test   300.00 352.00 17.3%
 test-suite...rks/FreeBench/pifft/pifft.test    60.00  69.00 15.0%
 test-suite...chmarks/MallocBench/gs/gs.test    57.00  63.00 10.5%
 test-suite...ngs-C/assembler/assembler.test    10.00  11.00 10.0%
 test-suite...0/253.perlbmk/253.perlbmk.test   145.00 157.00  8.3%
 test-suite...000/197.parser/197.parser.test    43.00  46.00  7.0%
 test-suite...TimberWolfMC/timberwolfmc.test   205.00 214.00  4.4%
 Geomean difference                                           7.6%

Fixes https://bugs.llvm.org/show_bug.cgi?id=46939
Mostly(?) fixes https://bugs.llvm.org/show_bug.cgi?id=46924

[lebedev.ri]

LGTM, that looks like a better/more general fix indeed.

[mkazantsev]

Seems that SCEV simplification is unable to exploit this fact when computing minimum. I think the right place to fix this is inside getMinExpr.

llvm/lib/Analysis/ScalarEvolution.cpp

10636

If loop is guarded by condition Start >= RHS, then getMinExpr(RHS, Start) should be able to simplify to RHS. Seems that we are missing some simplifications in there. Can we improve the simplification instead of manually handling this particular case here?

[mkazantsev]

LGTM. Good catch! Need to think about API to make this more generic.

llvm/lib/Analysis/ScalarEvolution.cpp

10633

Please add comment like

// If we know that Start >= RHS in the context of loop, then we know that min(RHS, Start) = RHS
// at this point.

10636

Oh, I see what happens. We only know this fact in this point, and getMinExpr has no mechanism to figure out in which context it happens. Then it makes sense.

Maybe in the future we will want to have something like "get<SCEVType>Expr(Ops, Context)" for such cases. But here the fix seems crystal clear, so it should be fine.

[fhahn]

Thanks for taking a look! I'll add the comment as suggested in the commit. I'm more than happy to collaborate/brainstorm/work on a way to get context-specific version of SCEV expressions as follow-up.

llvm/lib/Analysis/ScalarEvolution.cpp

10636

Oh, I see what happens. We only know this fact in this point, and getMinExpr has no mechanism to figure out in which context it happens. Then it makes sense.

Yep, that's specifically in the context of the loop where this information is available. I added the comment you suggested above, this should make this much clearer.

Maybe in the future we will want to have something like "get<SCEVType>Expr(Ops, Context)" for such cases. But here the fix seems crystal clear, so it should be fine.

Something like that would indeed be quite useful in some cases I think. IIRC getting an expression for a specific context could also help with retaining wrapping flags in some cases. I would be more than happy to collaborate/work on a more general solution.

[nikic]

For the record, this was a 1% compile-time regression on SPASS (https://llvm-compile-time-tracker.com/compare.php?from=7ba82a7320df82d07d3d5679bce89b14526b536c&to=ee1c12708a4519361729205168dedb2b61bc2638&stat=instructions). This seems to be caused due to a 2.3% increase in code size (https://llvm-compile-time-tracker.com/compare.php?from=7ba82a7320df82d07d3d5679bce89b14526b536c&to=ee1c12708a4519361729205168dedb2b61bc2638&stat=size-text), with some of the files getting 20-30% larger. Not particularly unexpected for this kind of change though.

[fhahn]

In D85046#2191535, @nikic wrote:

For the record, this was a 1% compile-time regression on SPASS (https://llvm-compile-time-tracker.com/compare.php?from=7ba82a7320df82d07d3d5679bce89b14526b536c&to=ee1c12708a4519361729205168dedb2b61bc2638&stat=instructions). This seems to be caused due to a 2.3% increase in code size (https://llvm-compile-time-tracker.com/compare.php?from=7ba82a7320df82d07d3d5679bce89b14526b536c&to=ee1c12708a4519361729205168dedb2b61bc2638&stat=size-text), with some of the files getting 20-30% larger. Not particularly unexpected for this kind of change though.

After this change ~100 more loops are unrolled in SPASS, which likely causes the increase.

llvm/lib/Analysis/ScalarEvolution.cpp

ScalarEvolution::howManyGreaterThans(const SCEV *LHS, const SCEV *RHS,
   if (!Stride->isOne() && doesIVOverflowOnGT(RHS, Stride, IsSigned, NoWrap))
     return getCouldNotCompute();
 
   ICmpInst::Predicate Cond = IsSigned ? ICmpInst::ICMP_SGT
                                       : ICmpInst::ICMP_UGT;
 
   const SCEV *Start = IV->getStart();
   const SCEV *End = RHS;
-  if (!isLoopEntryGuardedByCond(L, Cond, getAddExpr(Start, Stride), RHS))
+  if (!isLoopEntryGuardedByCond(L, Cond, getAddExpr(Start, Stride), RHS)) {
+    // If we know that Start >= RHS in the context of loop, then we know that
+    // min(RHS, Start) = RHS at this point.
+    if (isLoopEntryGuardedByCond(
+            L, IsSigned ? ICmpInst::ICMP_SGE : ICmpInst::ICMP_UGE, Start, RHS))
+      End = RHS;
+    else
       End = IsSigned ? getSMinExpr(RHS, Start) : getUMinExpr(RHS, Start);
+  }
 
   const SCEV *BECount = computeBECount(getMinusSCEV(Start, End), Stride, false);
 
   APInt MaxStart = IsSigned ? getSignedRangeMax(Start)
                             : getUnsignedRangeMax(Start);
 
   APInt MinStride = IsSigned ? getSignedRangeMin(Stride)
                              : getUnsignedRangeMin(Stride);

llvm/test/Analysis/ScalarEvolution/pr46939-trip-count-count-down.ll

 ; RUN: opt -analyze -scalar-evolution %s 2>&1 | FileCheck %s
 
 declare void @iteration()
 
 define void @reverse_loop(i32 %n) {
 ; CHECK-LABEL: 'reverse_loop'
 ; CHECK-NEXT:  Classifying expressions for: @reverse_loop
 ; CHECK-NEXT:    %i.011 = phi i32 [ %n, %for.body.lr.ph ], [ %dec, %for.body ]
-; CHECK-NEXT:    --> {%n,+,-1}<nsw><%for.body> U: full-set S: full-set Exits: (0 smin %n) LoopDispositions: { %for.body: Computable }
+; CHECK-NEXT:    --> {%n,+,-1}<nsw><%for.body> U: full-set S: full-set Exits: 0 LoopDispositions: { %for.body: Computable }
 ; CHECK-NEXT:    %dec = add nsw i32 %i.011, -1
-; CHECK-NEXT:    --> {(-1 + %n),+,-1}<nw><%for.body> U: full-set S: full-set Exits: (-1 + (0 smin %n)) LoopDispositions: { %for.body: Computable }
+; CHECK-NEXT:    --> {(-1 + %n),+,-1}<nw><%for.body> U: full-set S: full-set Exits: -1 LoopDispositions: { %for.body: Computable }
 ; CHECK-NEXT:  Determining loop execution counts for: @reverse_loop
-; CHECK-NEXT:  Loop %for.body: backedge-taken count is ((-1 * (0 smin %n)) + %n)
+; CHECK-NEXT:  Loop %for.body: backedge-taken count is %n
 ; CHECK-NEXT:  Loop %for.body: max backedge-taken count is 2147483647
-; CHECK-NEXT:  Loop %for.body: Predicated backedge-taken count is ((-1 * (0 smin %n)) + %n)
+; CHECK-NEXT:  Loop %for.body: Predicated backedge-taken count is %n
 ; CHECK-NEXT:   Predicates:
 ; CHECK:       Loop %for.body: Trip multiple is 1
 ;
 entry:
   %cmp10 = icmp sgt i32 %n, -1
   br i1 %cmp10, label %for.body.lr.ph, label %for.cond.cleanup
 
 for.body.lr.ph:

llvm/test/Transforms/HardwareLoops/scalar-while.ll

while.end:
   ret void
 }
 
 ; CHECK-GUARD-LABEL: while_gte
 ; CHECK-GUARD: entry:
 ; CHECK-GUARD:   br i1 %cmp4, label %while.end, label %while.body.preheader
 ; CHECK-GUARD: while.body.preheader:
 ; CHECK-GUARD:   [[ADD:%[^ ]+]] = add i32 %i, 1
-; CHECK-GUARD:   [[SEL:%[^ ]+]] = icmp slt i32 %N, %i
-; CHECK-GUARD:   [[MIN:%[^ ]+]] = select i1 [[SEL]], i32 %N, i32 %i
-; CHECK-GUARD:   [[COUNT:%[^ ]+]] = sub i32 [[ADD]], [[MIN]]
+; CHECK-GUARD:   [[COUNT:%[^ ]+]] = sub i32 [[ADD]], %N
 ; CHECK-GUARD:   call void @llvm.set.loop.iterations.i32(i32 [[COUNT]])
 ; CHECK-GUARD:   br label %while.body
 
 ; CHECK-LABEL: while_gte
 ; CHECK: while.body.preheader:
 ; CHECK: [[ADD:%[^ ]+]] = add i32 %i, 1
-; CHECK: [[SEL:%[^ ]+]] = icmp slt i32 %N, %i
-; CHECK: [[MIN:%[^ ]+]] = select i1 [[SEL]], i32 %N, i32 %i
-; CHECK: [[COUNT:%[^ ]+]] = sub i32 [[ADD]], [[MIN]]
+; CHECK: [[COUNT:%[^ ]+]] = sub i32 [[ADD]], %N
 ; CHECK: call void @llvm.set.loop.iterations.i32(i32 [[COUNT]])
 ; CHECK: br label %while.body
 
 ; CHECK-REGDEC: [[REM:%[^ ]+]] = phi i32 [ [[COUNT]], %while.body.preheader ], [ [[LOOP_DEC:%[^ ]+]], %while.body ]
 ; CHECK-REGDEC: [[LOOP_DEC]] = call i32 @llvm.loop.decrement.reg.i32(i32 [[REM]], i32 1)
 ; CHECK-REGDEC: [[CMP:%[^ ]+]] = icmp ne i32 [[LOOP_DEC]], 0
 ; CHECK-REGDEC: br i1 [[CMP]], label %while.body, label %while.end