Page MenuHomePhabricator

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

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

Details

Summary

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.
Thanks

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

LGTM

llvm/lib/Analysis/ScalarEvolutionExpander.cpp
2247

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
llvm/lib/Analysis/ScalarEvolutionExpander.cpp
2247

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

mkazantsev added inline comments.Feb 24 2020, 9:33 PM
llvm/lib/Analysis/ScalarEvolutionExpander.cpp
2238

This is a very rough approximation for Mul, because of Bin Pow algorithm used in Expander. See https://github.com/llvm-mirror/llvm/blob/master/lib/Analysis/ScalarEvolutionExpander.cpp#L781. 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

LGTM

Thank you for the review!

llvm/lib/Analysis/ScalarEvolutionExpander.cpp
2238

Aha, good point. I will add a TODO.

2247

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

lebedev.ri marked 2 inline comments as done.

Rebased, added TODO.