Page MenuHomePhabricator

[IPSCCP] Add general integer range support.
Needs ReviewPublic

Authored by fhahn on Apr 11 2019, 1:57 PM.

Details

Summary

This patch switches SCCP to use ValueLatticeElement for lattice values,
instead of the local LatticeVal, to enable integer range support.

Diff Detail

Event Timeline

fhahn created this revision.Apr 11 2019, 1:57 PM
Herald added a project: Restricted Project. · View Herald TranscriptApr 11 2019, 1:57 PM
Herald added a subscriber: hiraditya. · View Herald Transcript
fhahn marked an inline comment as done.Apr 11 2019, 2:04 PM

For now I would appreciate any high-level input, like is this the right place to do this or should we have a separate range propagation pass? I think we might be able to use this as a replacement for (parts) of CorrelatedValuePropagation, to avoid a few instances of recursively walking the IR.

Some initial statistics for -O3 -flto

Tests: 243
Same hash: 209 (filtered out)
Remaining: 34
Metric: sccp.IPNumInstRemoved

Program base range diff
test-suite...marks/SciMark2-C/scimark2.test 13.00 25.00 92.3%
test-suite...peg2/mpeg2dec/mpeg2decode.test 23.00 35.00 52.2%
test-suite...ngs-C/assembler/assembler.test 7.00 9.00 28.6%
test-suite...CFP2000/177.mesa/177.mesa.test 155.00 178.00 14.8%
test-suite...ks/Prolangs-C/agrep/agrep.test 24.00 27.00 12.5%
test-suite.../CINT2000/254.gap/254.gap.test 117.00 127.00 8.5%
test-suite...urce/Applications/lua/lua.test 260.00 273.00 5.0%
test-suite...ce/Benchmarks/PAQ8p/paq8p.test 87.00 91.00 4.6%
test-suite...langs-C/football/football.test 78.00 80.00 2.6%
test-suite...lications/sqlite3/sqlite3.test 471.00 483.00 2.5%
test-suite...5/124.m88ksim/124.m88ksim.test 163.00 167.00 2.5%
test-suite...lications/ClamAV/clamscan.test 839.00 857.00 2.1%
test-suite...CFP2006/433.milc/433.milc.test 197.00 201.00 2.0%
test-suite...nal/skidmarks10/skidmarks.test 504.00 513.00 1.8%
test-suite...0.perlbench/400.perlbench.test 1551.00 1578.00 1.7%
test-suite...arks/mafft/pairlocalalign.test 237.00 241.00 1.7%
test-suite...T2006/456.hmmer/456.hmmer.test 120.00 122.00 1.7%
test-suite.../CINT2000/176.gcc/176.gcc.test 978.00 994.00 1.6%
test-suite...0/253.perlbmk/253.perlbmk.test 937.00 950.00 1.4%
test-suite...T2006/445.gobmk/445.gobmk.test 1567.00 1588.00 1.3%
test-suite.../CINT95/134.perl/134.perl.test 86.00 87.00 1.2%
test-suite.../CINT2006/403.gcc/403.gcc.test 3625.00 3656.00 0.9%
test-suite...000/186.crafty/186.crafty.test 282.00 284.00 0.7%
test-suite.../Applications/SPASS/SPASS.test 2007.00 2020.00 0.6%
test-suite...3.xalancbmk/483.xalancbmk.test 3898.00 3915.00 0.4%
test-suite...T95/147.vortex/147.vortex.test 3770.00 3783.00 0.3%
test-suite...000/255.vortex/255.vortex.test 3771.00 3784.00 0.3%
test-suite :: External/Nurbs/nurbs.test 367.00 368.00 0.3%
test-suite...006/453.povray/453.povray.test 1616.00 1618.00 0.1%
test-suite...-typeset/consumer-typeset.test 3158.00 3161.00 0.1%
test-suite...ications/JM/lencod/lencod.test 8348.00 8354.00 0.1%

Tests: 243
Same hash: 209 (filtered out)
Remaining: 34
Metric: sccp.NumInstRemoved

Program base range diff
test-suite...peg2/mpeg2dec/mpeg2decode.test 75.00 164.00 118.7%
test-suite...urce/Applications/lua/lua.test 381.00 717.00 88.2%
test-suite...CFP2000/177.mesa/177.mesa.test 349.00 523.00 49.9%
test-suite...ks/Prolangs-C/agrep/agrep.test 25.00 29.00 16.0%
test-suite.../Applications/SPASS/SPASS.test 1913.00 2105.00 10.0%
test-suite...5/124.m88ksim/124.m88ksim.test 62.00 68.00 9.7%
test-suite...T2006/445.gobmk/445.gobmk.test 1067.00 1147.00 7.5%
test-suite...lications/ClamAV/clamscan.test 1046.00 1101.00 5.3%
test-suite.../CINT2000/176.gcc/176.gcc.test 2966.00 3068.00 3.4%
test-suite.../CINT2006/403.gcc/403.gcc.test 6985.00 7087.00 1.5%
test-suite...ications/JM/lencod/lencod.test 1253.00 1270.00 1.4%
test-suite...CFP2006/444.namd/444.namd.test 174.00 175.00 0.6%
test-suite...marks/7zip/7zip-benchmark.test 1078.00 1084.00 0.6%
test-suite...T95/147.vortex/147.vortex.test 5896.00 5920.00 0.4%
test-suite...000/255.vortex/255.vortex.test 5896.00 5920.00 0.4%
test-suite...3.xalancbmk/483.xalancbmk.test 2969.00 2981.00 0.4%
test-suite...006/453.povray/453.povray.test 590.00 592.00 0.3%
test-suite...6/464.h264ref/464.h264ref.test 2222.00 2228.00 0.3%
test-suite...nal/skidmarks10/skidmarks.test 1444.00 1447.00 0.2%
test-suite...0.perlbench/400.perlbench.test 1153.00 1155.00 0.2%
test-suite...arks/mafft/pairlocalalign.test 3360.00 3364.00 0.1%
test-suite...-typeset/consumer-typeset.test 2988.00 2990.00 0.1%

llvm/test/Transforms/SCCP/ipsccp-notnull.ll
66 ↗(On Diff #194752)

Will clean up the test case.

nikic added a subscriber: nikic.Apr 12 2019, 5:13 AM
fhahn updated this revision to Diff 197289.Apr 30 2019, 3:56 AM

Fix remaining issues, now passes LTO bootstrap of llvm/clang and the test-suite with various externals

xbolva00 added inline comments.
llvm/include/llvm/Analysis/ValueLattice.h
39 ↗(On Diff #197289)

Please add comment

fhahn updated this revision to Diff 197341.Apr 30 2019, 8:35 AM
fhahn marked an inline comment as done.

Remove ValueLattice changes from the diff.

fhahn added inline comments.Apr 30 2019, 8:42 AM
llvm/include/llvm/Analysis/ValueLattice.h
39 ↗(On Diff #197289)

The ValueLattice changes have been added by accident to this review, sorry! They are in D60581 and forcedconstant might get removed as part of this series.

davide added a comment.Jul 5 2019, 1:29 PM

Sorry for the long delay. I'm happy with this going in. @efriedma ?

Ping. @efriedma do you have any thoughts about the general direction of this patch?

ping. Eli, do you have any thoughts about the direction of the patch?

Sorry about the delayed response.

So currently, this is essentially a three-patch series; D60581, D60582, and D61314. D61314 proposes to get rid of "forced" constants, and use plain constants instead. I'm a little confused how that works; are you just getting rid of the assertion that a constant can't have two different values?

How do constant ranges work with loops? It seems like under a naive implementation, an induction variable would start a 0, then grow to 0-1, then grow to 0-2, etc., until it covers the full integer range. That clearly doesn't happen, since it would take forever, but I'm not sure I understand the limiting factor. There's a comment in visitBinaryOperator about this, but does that cover all possible loops?

I'm a little wary of adding complexity to the lattice given the issues we currently have reasoning about the semantics of "undef"/ResolveUndefsIn.

llvm/lib/Transforms/Scalar/SCCP.cpp
1867

Does this change actually have an effect? An unconditional branch should always flow to its successor.

2102

This assertion makes no sense.

fhahn added a comment.Fri, Aug 2, 11:57 AM

Sorry about the delayed response.

No worries, thank you very much for taking the time to take a look!

So currently, this is essentially a three-patch series; D60581, D60582, and D61314. D61314 proposes to get rid of "forced" constants, and use plain constants instead. I'm a little confused how that works; are you just getting rid of the assertion that a constant can't have two different values?

Sorry for not better organizing things. I wanted to make sure the overall direction makes sense (remove forcedconstant, use integer ranges) before re-arranging things. I'll rebase things and bring them in order and link them in Phab.

The idea here is to use the fact that integer constants are represented via a range, so they can have multiple values, and SCCP must take care of updating dependent instructions, if a range changes. This should allow us to get the same (or slightly more precise) behavior as forcedconstant: assume an arbitrary value and be sound when we later discover a different constant value for the same value.

When we used to assume a value through forcedconstant, we now just create a singleton integer range. Should we later discover a different constant value, instead of going to overdefined, we extend the range to include the new value and update the dependent instructions. I think for integer constants we can construct ranges for, that should work out fine.

For constants we cannot construct ranges for (e.g. floats or constants without specific integer value), we should still have the assertion (ValueLatticeElement should have the same assertions as the removed code from the ValueLattice in this file). Thinking about it again now, there might be some scenarios where we might hit it. It did not surface on a bootstrap build of LLVM with LTO, but I'll see if I can construct one.

How do constant ranges work with loops? It seems like under a naive implementation, an induction variable would start a 0, then grow to 0-1, then grow to 0-2, etc., until it covers the full integer range. That clearly doesn't happen, since it would take forever, but I'm not sure I understand the limiting factor. There's a comment in visitBinaryOperator about this, but does that cover all possible loops?

For operations where the original lattice value is a non-singleton range and the result of an operation is different (larger) range, we go to overdefined (around line 913). That should be the most conservative form of widening and should handle binary ops in loops, because we never extend a range more than once before going to overdefined. With might be able to use slightly more involved widening approaches later on.

We need this for all operators, I'll double check to make sure we do that for all operators.

I'm a little wary of adding complexity to the lattice given the issues we currently have reasoning about the semantics of "undef"/ResolveUndefsIn.

Understood, this change is quite disruptive. Is there anything in particular you are worried about/ anything I could do to sort out any issues there?