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

[lebedev.ri]

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

[lebedev.ri]

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]

Rebased.

[lebedev.ri]

Ping @mkazantsev / @reames
Thanks

[lebedev.ri]

Ping @reames / @mkazantsev
Thanks

[mkazantsev]

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

[lebedev.ri]

In D73718#1882000, @mkazantsev wrote:

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

Thank you for the review!

[lebedev.ri]

Rebased, NFC.

llvm/lib/Analysis/ScalarEvolutionExpander.cpp

if (auto *CastExpr = dyn_cast<SCEVCastExpr>(S)) {
     BudgetRemaining -=
         TTI.getOperationCost(Opcode, S->getType(), Op->getType());
     return isHighCostExpansionHelper(Op, L, At, BudgetRemaining, TTI,
                                      Processed);
   }
 
 
   if (auto *UDivExpr = dyn_cast<SCEVUDivExpr>(S)) {
-    // If the divisor is a power of two and the SCEV type fits in a native
-    // integer (and the LHS not expensive), consider the division cheap
-    // irrespective of whether it occurs in the user code since it can be
-    // lowered into a right shift.
-    if (auto *SC = dyn_cast<SCEVConstant>(UDivExpr->getRHS()))
+    // If the divisor is a power of two count this as a logical right-shift.
+    if (auto *SC = dyn_cast<SCEVConstant>(UDivExpr->getRHS())) {
       if (SC->getAPInt().isPowerOf2()) {
-        if (isHighCostExpansionHelper(UDivExpr->getLHS(), L, At,
-                                      BudgetRemaining, TTI, Processed))
-          return true;
-        const DataLayout &DL =
-            L->getHeader()->getParent()->getParent()->getDataLayout();
-        unsigned Width = cast<IntegerType>(UDivExpr->getType())->getBitWidth();
-        return DL.isIllegalInteger(Width);
-      }
+        BudgetRemaining -=
+            TTI.getOperationCost(Instruction::LShr, S->getType());
+        // Note that we don't count the cost of RHS, because it is a constant,
+        // and we consider those to be free. But if that changes, we would need
+        // to log2() it first before calling isHighCostExpansionHelper().
+        return isHighCostExpansionHelper(UDivExpr->getLHS(), L, At,
+                                         BudgetRemaining, TTI, Processed);
+      }
 
     // UDivExpr is very likely a UDiv that ScalarEvolution's HowFarToZero or
     // HowManyLessThans produced to compute a precise expression, rather than a
     // UDiv from the user's code. If we can't find a UDiv in the code with some
     // simple searching, assume the former consider UDivExpr expensive to
     // compute.
     BasicBlock *ExitingBB = L->getExitingBlock();
     if (!ExitingBB)