Page MenuHomePhabricator

[SCEV] SCEVExpander::isHighCostExpansionHelper(): cost-model add/mul

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



While this resolves the regression from D73722 in llvm/test/Transforms/IndVarSimplify/exit_value_test2.ll,
this now regresses llvm/test/Transforms/IndVarSimplify/elim-extend.ll @nestedIV test,
we no longer can perform that expansion within default budget of 4, but require budget of 6.
That regression is being addressed by D73777.

The basic idea here is simple.

Op0,  Op1, Op2 ...
 |     |    |
 \--+--/    |
    |       |

I.e. given N operands, we will have N-1 operations,
so we have to add cost of an add (mul) for every Op processed,
except the first one, plus we need to recurse into *every* Op.

I'm guessing there's already canonicalization that ensures we won't
have 1 operand in scMulExpr, and no 0 in scAddExpr/scMulExpr.

Diff Detail

Event Timeline

lebedev.ri created this revision.Jan 30 2020, 10:34 AM

NFC, fixup diff.

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

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



Just a suggestion, feel free to ignore: break if BudgetRemaining goes below zero in the loop to save time processing really huge SCEVs with many operands.

This revision is now accepted and ready to land.Feb 24 2020, 9:16 PM
mkazantsev added inline comments.Feb 24 2020, 9:19 PM

Or actually nvm, I guess it should be handled inside the helper.

mkazantsev added inline comments.Feb 24 2020, 9:33 PM

This is a very rough approximation for Mul, because of Bin Pow algorithm used in Expander. See You might want to factor it in in the future, but what you did is fine for the 1st step. Please add a TODO for that.

lebedev.ri marked 5 inline comments as done.Feb 25 2020, 9:47 AM


Thank you for the review!


Aha, good point. I will add a TODO.


Indeed, the idea is that it will be handled by isHighCostExpansionHelper().

lebedev.ri marked 2 inline comments as done.

Rebased, added TODO.