Page MenuHomePhabricator

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

Authored by fhahn on Jul 31 2020, 2:38 PM.

Details

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

Diff Detail

Event Timeline

fhahn created this revision.Jul 31 2020, 2:38 PM
Herald added a project: Restricted Project. · View Herald TranscriptJul 31 2020, 2:38 PM
Herald added a subscriber: hiraditya. · View Herald Transcript
fhahn requested review of this revision.Jul 31 2020, 2:38 PM
nikic added a subscriber: nikic.Jul 31 2020, 2:47 PM
lebedev.ri edited the summary of this revision. (Show Details)Jul 31 2020, 11:09 PM
lebedev.ri retitled this revision from [SCEV] If Start >= RHS, simplify (Start smin RHS) to RHS for trip counts. to [SCEV] If Start >= RHS, simplify (Start smin RHS) to RHS for trip counts (PR46924, PR46939).Jul 31 2020, 11:12 PM
lebedev.ri edited the summary of this revision. (Show Details)

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

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 accepted this revision.Aug 2 2020, 10:09 PM

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.

This revision is now accepted and ready to land.Aug 2 2020, 10:09 PM
fhahn added a comment.Aug 3 2020, 8:26 AM

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.

This revision was landed with ongoing or failed builds.Aug 3 2020, 9:31 AM
This revision was automatically updated to reflect the committed changes.
nikic added a comment.Aug 3 2020, 12:38 PM

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 added a comment.Aug 3 2020, 1:12 PM

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.