This is an archive of the discontinued LLVM Phabricator instance.

[SCCP] Use ranges for predicate info conditions.
ClosedPublic

Authored by fhahn on Mar 23 2020, 7:23 AM.

Details

Summary

This patch updates the code that deals with conditions from predicate
info to make use of constant ranges.

For ssa_copy instructions inserted by PredicateInfo, we have 2 ranges:

  1. The range of the original value.
  2. The range imposed by the linked condition.
  1. is known, 2. can be determined using makeAllowedICmpRegion. The

intersection of those ranges is the range for the copy.

With this patch, we get a nice increase in the number of instructions
eliminated by both SCCP and IPSCCP for some benchmarks:

For MultiSource, SPEC2000 & SPEC2006:

Tests: 237
Same hash: 170 (filtered out)
Remaining: 67
Metric: sccp.NumInstRemoved
Program base patch diff
test-suite...Source/Benchmarks/sim/sim.test 10.00 71.00 610.0%
test-suite...CFP2000/177.mesa/177.mesa.test 361.00 1626.00 350.4%
test-suite...encode/alacconvert-encode.test 141.00 602.00 327.0%
test-suite...decode/alacconvert-decode.test 141.00 602.00 327.0%
test-suite...CI_Purple/SMG2000/smg2000.test 1639.00 4093.00 149.7%
test-suite...peg2/mpeg2dec/mpeg2decode.test 75.00 163.00 117.3%
test-suite...T2006/401.bzip2/401.bzip2.test 358.00 513.00 43.3%
test-suite...rks/FreeBench/pifft/pifft.test 11.00 15.00 36.4%
test-suite...langs-C/unix-tbl/unix-tbl.test 4.00 5.00 25.0%
test-suite...lications/sqlite3/sqlite3.test 541.00 667.00 23.3%
test-suite.../CINT2000/254.gap/254.gap.test 243.00 299.00 23.0%
test-suite...ks/Prolangs-C/agrep/agrep.test 25.00 29.00 16.0%
test-suite...marks/7zip/7zip-benchmark.test 1135.00 1304.00 14.9%
test-suite...lications/ClamAV/clamscan.test 1105.00 1268.00 14.8%
test-suite...urce/Applications/lua/lua.test 398.00 436.00 9.5%

Metric: sccp.IPNumInstRemoved
Program base patch diff
test-suite...C/CFP2000/179.art/179.art.test 1.00 3.00 200.0%
test-suite...006/447.dealII/447.dealII.test 429.00 1056.00 146.2%
test-suite...nch/fourinarow/fourinarow.test 3.00 7.00 133.3%
test-suite...CI_Purple/SMG2000/smg2000.test 818.00 1748.00 113.7%
test-suite...ks/McCat/04-bisect/bisect.test 3.00 5.00 66.7%
test-suite...CFP2000/177.mesa/177.mesa.test 165.00 255.00 54.5%
test-suite...ediabench/gsm/toast/toast.test 18.00 27.00 50.0%
test-suite...telecomm-gsm/telecomm-gsm.test 18.00 27.00 50.0%
test-suite...ks/Prolangs-C/agrep/agrep.test 24.00 35.00 45.8%
test-suite...TimberWolfMC/timberwolfmc.test 43.00 62.00 44.2%
test-suite...encode/alacconvert-encode.test 46.00 66.00 43.5%
test-suite...decode/alacconvert-decode.test 46.00 66.00 43.5%
test-suite...langs-C/unix-tbl/unix-tbl.test 12.00 17.00 41.7%
test-suite...peg2/mpeg2dec/mpeg2decode.test 31.00 41.00 32.3%
test-suite.../CINT2000/254.gap/254.gap.test 117.00 154.00 31.6%

Diff Detail

Event Timeline

fhahn created this revision.Mar 23 2020, 7:23 AM
Herald added a project: Restricted Project. · View Herald TranscriptMar 23 2020, 7:23 AM
Herald added a subscriber: hiraditya. · View Herald Transcript

(Lint has a couple formatting suggestions.)

llvm/lib/Transforms/Scalar/SCCP.cpp
1247–1248

"If the original value is a constant we cannot do better" is technically not true; in theory, if we prove a contradiction, the ssa.copy is unreachable. But unlikely to matter in practice, I guess.

1264

Do we want to try to handle the case where we have a constant expression of integer type?

fhahn updated this revision to Diff 252318.Mar 24 2020, 7:38 AM

Use range information only of either operand is a constant range, instead of for all integer types and drop special case preserving original constant.

fhahn updated this revision to Diff 252319.Mar 24 2020, 7:40 AM

clang-format

fhahn marked 2 inline comments as done.Mar 24 2020, 7:46 AM
fhahn added inline comments.
llvm/lib/Transforms/Scalar/SCCP.cpp
1247–1248

Agreed, the special case here was not really necessary. I've removed it. Intersecting the constant ranges below should give the same result in practice. I've added a test case with a contradiction (f11_contradiction). I think in those cases, the contradicting compare will get folded to false, and we never branch to the block with the contradiction.

1264

Ah yes, I've change it to use ranges only if either operand is a constant range.

I've added a test with a compare of 2 constant ranges. Currently this just swaps the known values and is not too helpful in that case (f14_constexpr2).

Also, would it be legal to fold something like i1 icmp eq (i32 ptrtoint (i32* @B to i32), i32 ptrtoint (i32* @B to i32) to true? If it is, it looks like ConstantExpr currently misses that fold.

Harbormaster completed remote builds in B50254: Diff 252319.
efriedma added inline comments.Mar 24 2020, 10:51 AM
llvm/lib/Transforms/Scalar/SCCP.cpp
1264

I think the order of the conditions might be backwards? Consider if OriginalVal is a ConstantRange, and CondVal is a Constant.


I briefly tried the following, and it seems to fold (just passing it to "opt -S"):

@B = global i32 0
@C = global i1 icmp eq (i32 ptrtoint (i32* @B to i32), i32 ptrtoint (i32* @B to i32))

efriedma accepted this revision.Mar 24 2020, 10:54 AM

LGTM

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

Err, actually, hmm... in general, there's sort a conflict here between Constant and ConstantRange here; in more complicated cases, you could end up accidentally landing on overdefined by merging a Constant and a ConstantRange.

I guess it's unlikely to matter very much in practice; constant expressions are relatively rare.

This revision is now accepted and ready to land.Mar 24 2020, 10:54 AM
fhahn marked an inline comment as done.Mar 24 2020, 12:55 PM

Thank you very much Eli!

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

Yes I think potentially are cases involving constant ranges where we might go to overdefined using ranges unnecessarily. Maybe it would be best to try both and chose the better result, although it sometimes is not clear if a larger constant range or a constant Expr is better for further analysis. I think it would be interesting to follow up on that in future patches.

efriedma requested changes to this revision.Mar 24 2020, 1:29 PM

Hang on, is this actually safe?

If we compute a predicate based on a possibly-undef value, and branch based on that, does the predicate actually mean anything?

This revision now requires changes to proceed.Mar 24 2020, 1:29 PM
fhahn updated this revision to Diff 252683.Mar 25 2020, 3:01 PM

Hang on, is this actually safe?

If we compute a predicate based on a possibly-undef value, and branch based on that, does the predicate actually mean anything?

There are 2 cases IIUC that may be undef: the value we derive a bound for and the bound. I think in terms of the bound value, we should be safe, as we will go to overdefined for ranges that are merged with undef and effectively remove the information from the bound.

I think for now it should be safe as well if the value we derive the bound for may be undef, because the only place we actually use range information for simplification is at compares and there we always replace an icmp with a constant.

And I am not sure if it would be safe in general to replace a value with a different value based on range info in any case. E.g. consider

define void @foo(i32 %a) {
entry:
  %bc.1 = icmp ult i32 %a, 15
  br i1 %bc.1, label %true, label %false

true:
  %f.1 = icmp eq i32 %a, 128
  call void @use(i1 %f.1)

  %p.127 = and i32 %a, 15
  call void @use.i32(i32 %p.127)
  ret void

false:
  ret void
}

We can use the range info in the above to remove %f.1, but we cannot use it to remove the %p.127 = and...., as %a could be undef. CVP currently gets this wrong, besides other things. If we want to remove the and, we would need to insert an extra freeze I think.

Does that make sense?

fhahn added a comment.Mar 25 2020, 3:03 PM

I also added a set of additional test cases with various combinations of undef in https://reviews.llvm.org/rG081efa7dd084

They are also part of the current diff: llvm/test/Transforms/SCCP/conditions-ranges-with-undef.ll

If I'm understanding correctly, you're saying that SCCP doesn't care about the difference between constantrange and a hypothetical constantrangefromundef, therefore it's fine if the value is actually undef? I guess that's reasonable. But it would be more clear if we represented it explicitly in the lattice.

If I'm understanding correctly, you're saying that SCCP doesn't care about the difference between constantrange and a hypothetical constantrangefromundef, therefore it's fine if the value is actually undef? I guess that's reasonable.

Yep that should be the case.

But it would be more clear if we represented it explicitly in the lattice.

Agreed. I think we should be able to convert singlecrfromundef to something like constantrangeincludingundef. The regular constantrange would mean it is guaranteed to not include undef (would only be able to come from things like phis with all incoming values constants != undef). We can use information from such ranges to replace values with other values (like the and removal). All other ranges should be constantrangeincludingundef, e.g. the and example with a constant and an arbitrary value or the information inferred from bounds. Let me prepare a patch.

fhahn added a comment.Mar 27 2020, 8:48 AM

If I'm understanding correctly, you're saying that SCCP doesn't care about the difference between constantrange and a hypothetical constantrangefromundef, therefore it's fine if the value is actually undef? I guess that's reasonable. But it would be more clear if we represented it explicitly in the lattice.

I've put up D76931. It is based on the assumption that we have to assume arbitrary values like function arguments may be undef. I did not find that spelled out anywhere explicitly, so I might be wrong there.

nikic added a subscriber: nikic.Mar 27 2020, 1:43 PM
fhahn updated this revision to Diff 254185.Apr 1 2020, 6:58 AM

Rebased after adding constantrange_including_undef to ValueLattice.

I think we can create ranges that do not include undef from branch conditions given the recent clarification to the langref. I update the code to make that explicit and added a comment on the reasoning behind it.

Code looks fine.

I'm a little concerned that the recent clarification in LangRef doesn't actually match the code at the moment, so this could end up exposing an issue with some other transform. (grep for Attribute::SanitizeMemory.)

fhahn added a comment.Apr 1 2020, 2:09 PM

Code looks fine.

I'm a little concerned that the recent clarification in LangRef doesn't actually match the code at the moment, so this could end up exposing an issue with some other transform. (grep for Attribute::SanitizeMemory.)

I assume you are referring to code in other passes, right? I think we probably have code assuming both the new behaviour and the old one and we somehow have to consolidate the code base. Probably best to discuss that at the langref change/llvm-Dev?

Yes, code in other passes, particularly SimplifyCFG.

ekatz added a subscriber: ekatz.Apr 5 2020, 1:45 PM
fhahn updated this revision to Diff 255195.Apr 5 2020, 1:50 PM

Yes, code in other passes, particularly SimplifyCFG.

Thanks, I think I know what you mean now!

Making branch on undef UB kind of trades of making it easier to assume ranges (without undef) from branch conditions, but it makes it harder to introduce branches that where not there before, as it may introduce undef. This seems tricky. As you pointed out, the sanitizer attribute has some early exits for cases that might introduce branches on poison (but in most contexts that could also be undef). I'll raise it in D76973. It's probably best to discuss it there and maybe extend to llvm-dev.

Regardless of the outcome, I think the patch should be fine either way: only whether the range based on the condition can include undef or not is impacted by the outcome of that discussion. As ranges are only used to simplify conditions (which should be fine either way), switching to include undef for the new ranges by default should not have any functional impact on the current transformations.

I've updated the code to mark new ranges as potentially including undef. That should be the conservative choice and correct even if branch on undef is not UB. I've also added a TODO to flip the default once more other parts of the optimizer respect 'branch on undef is UB'.

Do you think this is conservative enough to get this in, even with the open questions remaining around 'branch on undef is UB'?

efriedma accepted this revision.Apr 6 2020, 2:24 PM

That seems fine, yes. LGTM

This revision is now accepted and ready to land.Apr 6 2020, 2:24 PM
This revision was automatically updated to reflect the committed changes.