This is an archive of the discontinued LLVM Phabricator instance.

[SCCP] Turn sext into zext for positive ranges.
ClosedPublic

Authored by fhahn on Jun 12 2020, 12:13 PM.

Details

Summary

This patch updates SCCP/IPSCCP to use the computed range info to turn
sexts into zexts, if the value is known to be non-negative. We already
to a similar transform in CorrelatedValuePropagation, but it seems like
we can catch a lot of additional cases by doing it in SCCP/IPSCCP as
well.

The transform is limited to ranges that are known to not include undef.
For it to be effective, we have to flip the MayIncludeUndef flag when
constructing ranges from predicates. That should be in line with the
recent LangRef updates, but may expose problems in other passes not
expecting branches on undef to be UB. But it might be good to start
making more aggressive use of the LangRef update and fix issues
uncovered. Alternatively we could wait until the 11.0 release branch is
taken.

Without this patch, CorrelatedValuePropagation turns ~6400 sexts into
zexts on MultiSource, SPEC2000 & SPEC2006. With this patch, CVP
transforms around 4000, while IPSCCP transforms around 10000.

This change impacts 90 binaries (147 unchanged). One interesting impact
is that this leads to a few more loops getting vectorized, probably
because reasoning about zexts is easier than about sexts in SCEV & co:

Program base patch3 diff
test-suite...T2000/256.bzip2/256.bzip2.test 20.00 21.00 5.0%
test-suite...T2006/401.bzip2/401.bzip2.test 22.00 23.00 4.5%
test-suite...0.perlbench/400.perlbench.test 84.00 87.00 3.6%
test-suite.../CINT2000/176.gcc/176.gcc.test 90.00 93.00 3.3%
test-suite...lications/ClamAV/clamscan.test 91.00 92.00 1.1%
test-suite.../CINT2006/403.gcc/403.gcc.test 220.00 222.00 0.9%
test-suite...pplications/oggenc/oggenc.test 126.00 127.00 0.8%
test-suite...arks/mafft/pairlocalalign.test 319.00 321.00 0.6%
test-suite...marks/7zip/7zip-benchmark.test 374.00 375.00 0.3%

Diff Detail

Event Timeline

fhahn created this revision.Jun 12 2020, 12:13 PM
Herald added a project: Restricted Project. · View Herald TranscriptJun 12 2020, 12:13 PM
nikic added a subscriber: nikic.Jun 12 2020, 1:25 PM
fhahn updated this revision to Diff 271346.Jun 17 2020, 5:43 AM

Ping. Rebased after updates to tests.

efriedma added inline comments.Jun 17 2020, 12:59 PM
llvm/lib/Transforms/Scalar/SCCP.cpp
1311

I'm a little uncomfortable that flipping this from true to false impacted zero testcases...

I'm not sure how to judge exactly how risky it is to land this without fixes to various passes we know have issues. I'm particularly worried about loop unswitch, since we saw a real miscompile involving it in the past.

1635

Are we keeping around stale pointers in the Solver? That's technically UB, I think, even if the code works otherwise, and the compiler is unlikely to take advantage.

fhahn updated this revision to Diff 271857.Jun 18 2020, 3:13 PM

Strip change flipping MayIncludeUndef and add removeLatticeValueFor helper, to remove stale pointers from ValueState.

fhahn marked 2 inline comments as done.Jun 18 2020, 3:21 PM
fhahn added inline comments.
llvm/lib/Transforms/Scalar/SCCP.cpp
1311

I'm a little uncomfortable that flipping this from true to false impacted zero testcases...

I'm not sure how to judge exactly how risky it is to land this without fixes to various passes we know have issues. I'm particularly worried about loop unswitch, since we saw a real miscompile involving it in the past.

Yeah, it's probably best to wait at least until the next release. I'll mention it in https://bugs.llvm.org/show_bug.cgi?id=46144. For now, I removed the change to MayIncludeUndef. That limits the cases we can catch, but there still are some.

I think the reason for why there are no changes to other test cases is because we currently only use ranges to replace compares with constants. When replacing with a constant I think we concluded that it does not matter whether the ranges include undef or not.

When it comes to replacing with other instructions based on range info like in this patch, we need to check for undef I think.

1635

Yes it does currently. I don't think it would cause in problems in practice, but it is better to properly remove it. I've added a removeLatticeValueFor and used that. We don't remove the entries when removing other instructions, but I guess if we create new instructions we could in theory re-use existing pointers or something.

efriedma accepted this revision.Jun 18 2020, 4:50 PM

LGTM

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

I think the reason for why there are no changes to other test cases is because we currently only use ranges to replace compares with constants.

Oh, right.

1635

Reusing existing pointers would only be if we tried to query the solver for an instruction we created after the solver runs; I don't think we do that.

This revision is now accepted and ready to land.Jun 18 2020, 4:50 PM
This revision was automatically updated to reflect the committed changes.
fhahn marked an inline comment as done.Jun 19 2020, 11:09 AM

Thank you very much, Eli!

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

Yep. The latest version does clear them up now, so we don't have to worry about it in the future :)