Page MenuHomePhabricator

[SCEV] SCEVExpander::isHighCostExpansionHelper(): cost-model UDiv by power-of-two as LShr
ClosedPublic

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

Details

Summary

Like with casts, we need to subtract the cost of lshr instruction
from budget, and recurse into LHS operand.
Seems "pretty obviously correct" to me?

To be noted, there is a number of other shortcuts we could cost-model:

  • ... + (-1 * ...) -> ... - ... <- likely very frequent case
  • x - (rem x, power-of-2), which is currently (x udiv power-of-2) * power-of-2 -> x & -log2(power-of-2)
  • rem x, power-of-2, which is currently x - ((x udiv power-of-2) * power-of-2) -> x & log2(power-of-2)-1
  • ... * power-of-2 -> ... << log2(power-of-2) <- likely not very beneficial

Diff Detail

Event Timeline

lebedev.ri created this revision.Jan 30 2020, 8:47 AM

To be noted, there is a number of other shortcuts we could cost-model:

  • ... + (-1 * ...) -> ... - ... <- likely very frequent case
  • rem x, power-of-2, which is currently x - ((x udiv y) * y) -> x & log2(power-of-2)-1
  • x - (rem x, power-of-2), which is currently (x udiv y) * y -> x & -log2(power-of-2)
  • ... * power-of-2 -> ... << log2(power-of-2) <- likely not very beneficial
lebedev.ri edited the summary of this revision. (Show Details)Jan 31 2020, 7:26 AM
lebedev.ri edited the summary of this revision. (Show Details)Jan 31 2020, 8:04 AM
mkazantsev accepted this revision.Feb 18 2020, 10:57 PM

Not sure what are cost implications of that, but fine.

This revision is now accepted and ready to land.Feb 18 2020, 10:57 PM

Not sure what are cost implications of that, but fine.

Thank you for the review!

Rebased, NFC.

This revision was automatically updated to reflect the committed changes.