[SCEV] SCEVExpander::isHighCostExpansionHelper(): cost-model plain UDiv

Summary:
If we don't believe this UDiv is actually a LShr in disguise, things are much worse.
First, we try to see if this UDiv actually originates from user code,
by looking for `S + 1`, and if found considering this UDiv to be free.
But otherwise, we always considered this UDiv to be high-cost.

However that is no longer the case with TTI-driven cost model:
our default budget is 4, which matches the default cost of UDiv,
so now we allow a single UDiv to not be counted as high-cost.

While that is the case, it is evident this is actually a regression
due to the fact that cost-modelling is incomplete - we did not account
for the `add`, `mul` costs yet. That is being addressed in D73728.

Cost-modelling for UDiv also seems pretty straight-forward:
subtract cost of the UDiv itself, and recurse into both the LHS and RHS.

Reviewers: reames, mkazantsev, wmi, sanjoy

Reviewed By: mkazantsev

Subscribers: hiraditya, llvm-commits

Tags: #llvm

Differential Revision: https://reviews.llvm.org/D73722

1 files changed, 19 insertions, 12 deletions

diff --git a/llvm/lib/Analysis/ScalarEvolutionExpander.cpp b/llvm/lib/Analysis/ScalarEvolutionExpander.cpp
index 73f70d4..abfb784 100644
--- a/llvm/lib/Analysis/ScalarEvolutionExpander.cpp
+++ b/llvm/lib/Analysis/ScalarEvolutionExpander.cpp
@@ -2196,20 +2196,27 @@ bool SCEVExpander::isHighCostExpansionHelper(
     // 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.
+    // simple searching, we need to account for it's cost.
+
     BasicBlock *ExitingBB = L->getExitingBlock();
-    if (!ExitingBB)
-      return true;
+    if (At || ExitingBB) {
+      if (!At)
+        At = &ExitingBB->back();
+
+      // At the beginning of this function we already tried to find existing
+      // value for plain 'S'. Now try to lookup 'S + 1' since it is common
+      // pattern involving division. This is just a simple search heuristic.
+      if (getRelatedExistingExpansion(
+              SE.getAddExpr(S, SE.getConstant(S->getType(), 1)), At, L))
+        return false; // Consider it to be free.
+    }
 
-    // At the beginning of this function we already tried to find existing value
-    // for plain 'S'. Now try to lookup 'S + 1' since it is common pattern
-    // involving division. This is just a simple search heuristic.
-    if (!At)
-      At = &ExitingBB->back();
-    if (!getRelatedExistingExpansion(
-            SE.getAddExpr(S, SE.getConstant(S->getType(), 1)), At, L))
-      return true;
+    // Need to count the cost of this UDiv.
+    BudgetRemaining -= TTI.getOperationCost(Instruction::UDiv, S->getType());
+    return isHighCostExpansionHelper(UDivExpr->getLHS(), L, At, BudgetRemaining,
+                                     TTI, Processed) ||
+           isHighCostExpansionHelper(UDivExpr->getRHS(), L, At, BudgetRemaining,
+                                     TTI, Processed);
   }
 
   // HowManyLessThans uses a Max expression whenever the loop is not guarded by