Page MenuHomePhabricator

[SCEV][NFC] Check NoWrap flags before lexicographical comparison of SCEVs
ClosedPublic

Authored by mkazantsev on Nov 30 2017, 4:15 AM.

Details

Summary

Lexicographical comparison of SCEV trees is potentially expensive for big
expression trees. We can define ordering between them for AddRecs and
N-ary operations by SCEV NoWrap flags to make non-equality check
cheaper.

This change does not prevent grouping eqivalent SCEVs together and is
not supposed to have any meaningful impact on behavior of any transforms.

Diff Detail

Event Timeline

mkazantsev created this revision.Nov 30 2017, 4:15 AM
mkazantsev edited the summary of this revision. (Show Details)Nov 30 2017, 4:20 AM
sanjoy accepted this revision.Dec 5 2017, 8:43 PM

lgtm

This revision is now accepted and ready to land.Dec 5 2017, 8:43 PM
This revision was automatically updated to reflect the committed changes.
rtereshin added inline comments.
llvm/trunk/lib/Analysis/ScalarEvolution.cpp
699 ↗(On Diff #125704)

Hi everyone,

Unfortunately, wrapping flags are not a part of SCEV's identity (they do not participate in computing a hash value or in equality comparisons) and in fact they could be assigned after the fact w/o rebuilding a SCEV.

At least, last time I checked it was that way. Grep for const_cast's to see quite a few of example, AFAIR all for AddRec's.

So, if 2 expressions get built in 2 slightly different ways: one with flags set in the beginning, the other with the flags attached later on, we may end up with 2 expressions which are exactly the same but have their operands swapped in one of the commutative N-ary expressions, and at least one of them will have "sorted by complexity" invariant broken.

2 identical SCEV's won't compare equal by pointer comparison as they are supposed to.

I didn't verify this with an experiment yet, please correct me if I'm wrong.

Thanks,
Roman

mkazantsev added inline comments.Aug 16 2018, 11:38 PM
llvm/trunk/lib/Analysis/ScalarEvolution.cpp
699 ↗(On Diff #125704)

I think you are right, and it's a good reason to revert this patch. Please do so with checking in a test where it shows up. Good catch!

rtereshin added inline comments.Aug 27 2018, 2:49 PM
llvm/trunk/lib/Analysis/ScalarEvolution.cpp
699 ↗(On Diff #125704)

Done as requested.

The revert is currently a part of https://reviews.llvm.org/D51014 aiming to gain back the compile time improvements, I will update the diff so it does not include the revert a bit later.

Also, I wasn't able to actually see any compile time regression with the revert yet as I'm not sure what to benchmark exactly. One benchmark I'm trying builds very large SCEVs and spends the absolute majority of the time doing getSCEV, and that benchmark show near-noise difference in time spent in compareSCEVComplexity as well as in getSCEV between TOT with and without the revert.