This is an archive of the discontinued LLVM Phabricator instance.

[SCEV] SCEVExpander::isHighCostExpansionHelper(): cost-model plain UDiv
ClosedPublic

Authored by lebedev.ri on Jan 30 2020, 9:30 AM.

Details

Summary

If we don't believe this UDiv is actually a LShr in disguise, things are much worse.
First, we try to see if this UDiv actually originates from user code,
by looking for S + 1, and if found considering this UDiv to be free.
But otherwise, we always considered this UDiv to be high-cost.

However that is no longer the case with TTI-driven cost model:
our default budget is 4, which matches the default cost of UDiv,
so now we allow a single UDiv to not be counted as high-cost.

While that is the case, it is evident this is actually a regression
due to the fact that cost-modelling is incomplete - we did not account
for the add, mul costs yet. That is being addressed in D73728.

Cost-modelling for UDiv also seems pretty straight-forward:
subtract cost of the UDiv itself, and recurse into both the LHS and RHS.

Diff Detail

Event Timeline

lebedev.ri created this revision.Jan 30 2020, 9:30 AM
lebedev.ri edited the summary of this revision. (Show Details)Jan 31 2020, 5:09 AM
mkazantsev added inline comments.Feb 18 2020, 10:59 PM
llvm/test/Transforms/IndVarSimplify/exit_value_test2.ll
24

Why do we need this change if it starts generating worse code?

lebedev.ri marked an inline comment as done.Feb 19 2020, 1:19 AM

@mkazantsev thank you for taking a look!
Please see inline reply :)

llvm/test/Transforms/IndVarSimplify/exit_value_test2.ll
24

We need this change because the goal of this patchset is to move
the *entirety* of SCEVExpander::isHighCostExpansionHelper()
to TTI cost-modelling. Entirety as in everything.

Also, please do see the patch's description:

While that is the case, it is evident this is actually a regression
due to the fact that cost-modelling is incomplete - we did not account
for the add, mul costs yet. That is being addressed in D73728.

Ping @reames / @mkazantsev
Please do indicate if there is any way i can help move this process along.
Thanks

mkazantsev accepted this revision.Feb 24 2020, 9:12 PM

LGTM

llvm/test/Transforms/IndVarSimplify/exit_value_test2.ll
24

Ok it seems the next patch fixes it back. Thanks. :)

This revision is now accepted and ready to land.Feb 24 2020, 9:12 PM
lebedev.ri marked 2 inline comments as done.Feb 25 2020, 9:41 AM

LGTM

Thank you for the review!

Rebased, NFC.