[SCEV] SCEVExpander::isHighCostExpansionHelper(): cost-model UDiv by power-of-two...
authorRoman Lebedev <lebedev.ri@gmail.com>
Tue, 25 Feb 2020 18:51:22 +0000 (21:51 +0300)
committerRoman Lebedev <lebedev.ri@gmail.com>
Tue, 25 Feb 2020 20:05:58 +0000 (23:05 +0300)
commitb8793f0dabc974aec74ce09362d8790d77c6acba
treefc73c801270aa15e69acd80679aa042e340ec4d7
parentf90973f48645d1d1799d7bdb81cd6873e3a8ab71
[SCEV] SCEVExpander::isHighCostExpansionHelper(): cost-model UDiv by power-of-two as LShr

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

Reviewers: reames, mkazantsev, wmi, sanjoy

Reviewed By: mkazantsev

Subscribers: hiraditya, llvm-commits

Tags: #llvm

Differential Revision: https://reviews.llvm.org/D73718
llvm/lib/Analysis/ScalarEvolutionExpander.cpp