This is an archive of the discontinued LLVM Phabricator instance.

[IPSCCP] Use ValueLatticeElement instead of LatticeVal (NFCI)
ClosedPublic

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, as first step to enable integer range support.

This patch does not make use of constant ranges for additional operations
and the only difference for now is that integer constants are represented by
single element ranges. To preserve the existing behavior, the following helpers
are used

  • isConstant(LV): returns true when LV is either a constant or a constant range with a single element. This should return true in the same cases where LV.isConstant() returned true previously.
  • getConstant(LV): returns a constant if LV is either a constant or a constant range with a single element. This should return a constant in the same cases as LV.getConstant() previously.
  • getConstantInt(LV): same as getConstant, but additionally casted to ConstantInt.

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.Aug 2 2019, 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?

fhahn updated this revision to Diff 235029.Dec 21 2019, 2:40 PM

Rebase and reduce diff as much as possible.

Unit tests: pass. 61088 tests passed, 0 failed and 728 were skipped.

clang-tidy: fail. Please fix clang-tidy findings.

clang-format: fail. Please format your changes with clang-format by running git-clang-format HEAD^ or applying this patch.

Build artifacts: diff.json, clang-tidy.txt, clang-format.patch, CMakeCache.txt, console-log.txt, test-results.xml

fhahn updated this revision to Diff 235423.Dec 27 2019, 8:16 AM

ping :)

I finally found some time to rebase this and I also tried to reduce the diff as far as possible!

This patch now just replaces SCCP's LatticeVal with ValueLatticeElement, without making additional use of constant ranges (besides for function arguments) just yet. As follow-up, I'll add patches making use of range information for various kinds of instructions. This patch itself should be a NFC (compiling test-suite & SPEC produces equal binaries with and without this change for -O3) and uses the following helpers to preserve the current behavior when constant ranges are used for integers:

  • isConstant(LV): returns true when LV is either a constant or a constant range with a single element. This should return true in the same cases where LV.isConstant() returned true previously.
  • getConstant(LV): returns a constant if LV is either a constant or a constant range with a single element. This should return a constant in the same cases as LV.getConstant() previously.
  • getConstantInt(LV): same as getConstant, but additionally casted to ConstantInt.

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've moved the widening to mergeInValue. This guarantees we set/extend a range at most once and go to overdefined otherwise. That should cover all loops. The one exception is when merging function argument values, but that should be fine, because the concrete argument value ranges can only extended at most once.

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

The updated patches break things down much better I think and allow it to more carefully review the changes. I don't think there's an impact on ResolveUndefsIn at the moment, although begin more powerful might expose additional issues. But I think we could look at the issues as they appear.

fhahn retitled this revision from [IPSCCP] Add general integer range support. to [IPSCCP] Use ValueLatticeElement instead of LatticeVal (NFCI).Dec 27 2019, 8:19 AM
fhahn edited the summary of this revision. (Show Details)

Unit tests: fail. 61129 tests passed, 3 failed and 728 were skipped.

failed: Clang.SemaOpenCL/numbered-address-space.cl
failed: libc++.std/thread/thread_mutex/thread_mutex_requirements/thread_timedmutex_requirements/thread_timedmutex_class/lock.pass.cpp
failed: lld.COFF/fixed.test

clang-tidy: fail. Please fix clang-tidy findings.

clang-format: pass.

Build artifacts: diff.json, clang-tidy.txt, clang-format.patch, CMakeCache.txt, console-log.txt, test-results.xml

fhahn added a comment.Jan 14 2020, 1:06 PM

ping. Eli, do you think the updated approach makes more sense?

I'm skeptical of the way this stack is handling forcedconstant... but probably makes more sense to discuss on D61314.

llvm/include/llvm/Analysis/ValueLattice.h
250 ↗(On Diff #235423)

This is just a drive-by fix?

llvm/lib/Transforms/Scalar/SCCP.cpp
333–334

Is the IV.isConstant() here actually useful? Don't we always resolve constant integers to a ConstantRange?

401

This probably could be refined to handle cases that aren't actually loops, but probably fine as a first shot.

708

The point of "!isUnknownOrConstant()" instead of isOverdefined() is to exclude constant ranges? If that's right, could you use a positive name like "isOverdefinedOrConstantRange"?

fhahn updated this revision to Diff 239748.Jan 22 2020, 5:50 PM
fhahn marked 5 inline comments as done.

Address Eli's comments:

  • change name of isUnknownOrConstant to isOverdefined
  • simplify getConstantInt.
fhahn added a comment.Jan 22 2020, 5:51 PM

ping

llvm/include/llvm/Analysis/ValueLattice.h
250 ↗(On Diff #235423)

Yes, I moved that out to D73240

llvm/lib/Transforms/Scalar/SCCP.cpp
333–334

Is the IV.isConstant() here actually useful?

Not really, the check is not required, as getConstant() already handles that already.

Don't we always resolve constant integers to a ConstantRange?

I *think* I encountered some cases with integer constant expressions that do not resolve to a concrete integer (e.g. involving ptrtoint).

401

Agreed, I am planning on improving that as another follow-up, once the series of changes in in, so we have a better chance to spot issues through testing.

708

It excludes constant ranges with more than a single element and should cover exactly the same cases as the original LatticeVal::isOverdefined. I've changed the name to isOverdefined and also updated the comments for the helper functions.

fhahn added a comment.Jan 22 2020, 5:53 PM

ping

^ that was a stale comment that got accidentally submitted, when I just wanted to submit the responses to the inline comments. Sorry about that.

Unit tests: unknown.

clang-tidy: unknown.

clang-format: unknown.

Build artifacts: diff.json, console-log.txt

This revision is now accepted and ready to land.Feb 11 2020, 2:23 PM

Thanks Eli! I'll try to land this at the end of next week, unless there are any regressions due to D61314.

fhahn added a comment.Mar 11 2020, 3:39 PM

Given the progress with the ValueLatticeElement improvements with respect to dealing with undef and ranges and due to the fact that the problems only become practical issues with the follow up patches, do you think it is fine to land this initial change in the following days?

Sure, I'm fine with landing this first.

fhahn updated this revision to Diff 249892.Mar 12 2020, 4:21 AM

Rebased

This revision was automatically updated to reflect the committed changes.