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

[lebedev.ri]

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.

[lebedev.ri]

Rebased.

[lebedev.ri]

Ping @mkazantsev / @reames
Thanks

[lebedev.ri]

Ping @reames / @mkazantsev
Thanks

[mkazantsev]

llvm/test/Transforms/IndVarSimplify/exit_value_test2.ll

24

Why do we need this change if it starts generating worse code?

[lebedev.ri]

@mkazantsev thank you for taking a look!
Please see inline reply :)

llvm/test/Transforms/IndVarSimplify/exit_value_test2.ll

24

We need this change because the goal of this patchset is to move
the *entirety* of SCEVExpander::isHighCostExpansionHelper()
to TTI cost-modelling. Entirety as in everything.

Also, please do see the patch's description:

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.

[lebedev.ri]

Ping @reames / @mkazantsev
Please do indicate if there is any way i can help move this process along.
Thanks

[mkazantsev]

LGTM

llvm/test/Transforms/IndVarSimplify/exit_value_test2.ll

24

Ok it seems the next patch fixes it back. Thanks. :)

[lebedev.ri]

In D73722#1890683, @mkazantsev wrote:

LGTM

Thank you for the review!

[lebedev.ri]

Rebased, NFC.

llvm/lib/Analysis/ScalarEvolutionExpander.cpp

if (auto *SC = dyn_cast<SCEVConstant>(UDivExpr->getRHS())) {
         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)
-      return true;
+    // simple searching, we need to account for it's cost.
 
-    // 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.
+    BasicBlock *ExitingBB = L->getExitingBlock();
+    if (At || ExitingBB) {
       if (!At)
         At = &ExitingBB->back();
-    if (!getRelatedExistingExpansion(
+
+      // 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 true;
+        return false; // Consider it to be free.
+    }
+
+    // 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
   // the exit condition.
   if (isa<SCEVMinMaxExpr>(S))
     return true;
 
   // Recurse past nary expressions, which commonly occur in the

llvm/test/Transforms/IndVarSimplify/exit_value_test2.ll

 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[A:%.*]] = alloca i32, align 4
 ; CHECK-NEXT:    [[T:%.*]] = bitcast i32* [[A]] to i8*
 ; CHECK-NEXT:    call void @llvm.lifetime.start.p0i8(i64 4, i8* [[T]])
 ; CHECK-NEXT:    store i32 -1640531527, i32* [[A]], align 4
 ; CHECK-NEXT:    [[CMP8:%.*]] = icmp ugt i32 [[LEN:%.*]], 11
 ; CHECK-NEXT:    br i1 [[CMP8]], label [[WHILE_BODY_LR_PH:%.*]], label [[WHILE_END:%.*]]
 ; CHECK:       while.body.lr.ph:
+; CHECK-NEXT:    [[TMP0:%.*]] = add i32 [[LEN]], -12
+; CHECK-NEXT:    [[TMP1:%.*]] = udiv i32 [[TMP0]], 12
+; CHECK-NEXT:    [[TMP2:%.*]] = mul i32 [[TMP1]], 12
 ; CHECK-NEXT:    br label [[WHILE_BODY:%.*]]
 ; CHECK:       while.body:
 ; CHECK-NEXT:    [[KEYLEN_010:%.*]] = phi i32 [ [[LEN]], [[WHILE_BODY_LR_PH]] ], [ [[SUB:%.*]], [[WHILE_BODY]] ]
 ; CHECK-NEXT:    [[S_ADDR_09:%.*]] = phi i8* [ [[S:%.*]], [[WHILE_BODY_LR_PH]] ], [ [[ADD_PTR:%.*]], [[WHILE_BODY]] ]
 ; CHECK-NEXT:    [[T1:%.*]] = bitcast i8* [[S_ADDR_09]] to i32*
 ; CHECK-NEXT:    [[T2:%.*]] = load i32, i32* [[T1]], align 4
 ; CHECK-NEXT:    [[SHL_I:%.*]] = shl i32 [[T2]], 1
 ; CHECK-NEXT:    [[AND_I:%.*]] = and i32 [[SHL_I]], 16843008
 ; CHECK-NEXT:    [[T3:%.*]] = load i32, i32* [[A]], align 4
 ; CHECK-NEXT:    [[SUB_I:%.*]] = add i32 [[T3]], [[T2]]
 ; CHECK-NEXT:    [[ADD:%.*]] = sub i32 [[SUB_I]], [[AND_I]]
 ; CHECK-NEXT:    store i32 [[ADD]], i32* [[A]], align 4
 ; CHECK-NEXT:    [[ADD_PTR]] = getelementptr inbounds i8, i8* [[S_ADDR_09]], i64 12
 ; CHECK-NEXT:    [[SUB]] = add i32 [[KEYLEN_010]], -12
 ; CHECK-NEXT:    [[CMP:%.*]] = icmp ugt i32 [[SUB]], 11
 ; CHECK-NEXT:    br i1 [[CMP]], label [[WHILE_BODY]], label [[WHILE_COND_WHILE_END_CRIT_EDGE:%.*]]
 ; CHECK:       while.cond.while.end_crit_edge:
-; CHECK-NEXT:    [[SUB_LCSSA:%.*]] = phi i32 [ [[SUB]], [[WHILE_BODY]] ]
+; CHECK-NEXT:    [[TMP3:%.*]] = sub i32 [[TMP0]], [[TMP2]]
 ; CHECK-NEXT:    br label [[WHILE_END]]
 ; CHECK:       while.end:
-; CHECK-NEXT:    [[KEYLEN_0_LCSSA:%.*]] = phi i32 [ [[SUB_LCSSA]], [[WHILE_COND_WHILE_END_CRIT_EDGE]] ], [ [[LEN]], [[ENTRY:%.*]] ]
+; CHECK-NEXT:    [[KEYLEN_0_LCSSA:%.*]] = phi i32 [ [[TMP3]], [[WHILE_COND_WHILE_END_CRIT_EDGE]] ], [ [[LEN]], [[ENTRY:%.*]] ]
 ; CHECK-NEXT:    call void @_Z3mixRjj(i32* dereferenceable(4) [[A]], i32 [[KEYLEN_0_LCSSA]])
 ; CHECK-NEXT:    [[T4:%.*]] = load i32, i32* [[A]], align 4
 ; CHECK-NEXT:    call void @llvm.lifetime.end.p0i8(i64 4, i8* [[T]])
 ; CHECK-NEXT:    ret i32 [[T4]]
 ;
 entry:
   %a = alloca i32, align 4
   %t = bitcast i32* %a to i8*