Page MenuHomePhabricator

[CVP] Remove a masking operation if range information implies it's a noop
ClosedPublic

Authored by reames on Oct 10 2019, 9:40 AM.

Details

Summary

This is really a known bits style transformation, but known bits isn't context sensitive. The particular case which comes up happens to involve a range which allows range based reasoning to eliminate the mask pattern, so handle that case specifically in CVP.

InstCombine likes to generate the mask-by-low-bits pattern when widening an arithmetic expression which includes a zext in the middle.

Diff Detail

Event Timeline

reames created this revision.Oct 10 2019, 9:40 AM
Herald added a project: Restricted Project. · View Herald TranscriptOct 10 2019, 9:40 AM

I agree that instcombine likes that pattern, so it may make sense to deal with it.

lib/Transforms/Scalar/CorrelatedValuePropagation.cpp
65 ↗(On Diff #224390)

STATISTIC(NumAndMasks, "Number of constant low-bit-masking ands dropped");

715–716 ↗(On Diff #224390)

Do we want to query constanrange, or use getPredicateAt()?
Different folds here take different routes.
Should this be:

if (LVI->getPredicateAt(ICmpInst::ICMP_ULE, LHS, RHS, SDI) !=
    LazyValueInfo::True)
  return false;

? (i don't know)

720–721 ↗(On Diff #224390)

++NumAndMasks();

reames updated this revision to Diff 224423.Oct 10 2019, 12:30 PM

Add statistic, and update a couple other tests which should have been in initial patch.

reames marked 3 inline comments as done.Oct 10 2019, 12:32 PM
reames added inline comments.
lib/Transforms/Scalar/CorrelatedValuePropagation.cpp
715–716 ↗(On Diff #224390)

In this case, I think they're basically equivalent in practice for this case. The getPredicateAt form is slightly more powerful as it does predicate pushback through one layer of predecessors, but skipping that is slightly faster compile time wise.

Hm, having written that, I think I'll switch to the predicate form just for future proofing ad consistency. Update coming.

reames marked an inline comment as done.Oct 10 2019, 12:42 PM
reames added inline comments.
lib/Transforms/Scalar/CorrelatedValuePropagation.cpp
715–716 ↗(On Diff #224390)

Correction: the getPredicateAt form does predicate pushback, but is weaker on conditions which are implied by edge local facts. (i.e. I tried to switch and the results are strictly worse.) This is arguably an LVI bug - one I remember from past occurrences now - but not something I'm going to fix just for this issue.

nikic added inline comments.Oct 10 2019, 12:57 PM
lib/Transforms/Scalar/CorrelatedValuePropagation.cpp
713 ↗(On Diff #224423)

The limit to masks seems a bit stronger than strictly necessary: The range needs to be <= than the trailing ones in RHS. That is for 0b11001111, if the range is <= 0b00001111 that is sufficient. Not sure if this is worth handling.

715–716 ↗(On Diff #224390)

Right, this is a longstanding LVI limitation.

Thanks, this looks ok to me, but i'll leave final review to others.

lib/Transforms/Scalar/CorrelatedValuePropagation.cpp
713 ↗(On Diff #224423)

I'd say this is intentional to limit the number of ands we handle.

reames marked an inline comment as done.Oct 10 2019, 4:29 PM
reames added inline comments.
lib/Transforms/Scalar/CorrelatedValuePropagation.cpp
713 ↗(On Diff #224423)

It's definitely more restrictive than necessary. I decided the mask case (which is specifically what instcombine generates) was a reasonable case to break at.

I'm happy to generalize (slightly) but will definitely do so in a separate patch.

This revision was not accepted when it landed; it landed in state Needs Review.Oct 10 2019, 8:49 PM
This revision was automatically updated to reflect the committed changes.