[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

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; PR23538
 ; RUN: opt < %s -indvars -loop-deletion -S | FileCheck %s
 
 ; Check IndVarSimplify should not replace exit value because or else
 ; udiv will be introduced by expand and the cost will be high.
 
 declare void @_Z3mixRjj(i32* dereferenceable(4), i32)
 declare void @llvm.lifetime.start.p0i8(i64, i8* nocapture)
 declare void @llvm.lifetime.end.p0i8(i64, i8* nocapture)
 
 define i32 @_Z3fooPKcjj(i8* nocapture readonly %s, i32 %len, i32 %c) {
 ; CHECK-LABEL: @_Z3fooPKcjj(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[A:%.*]] = alloca i32, align 4
-; CHECK-NEXT:    [[TMP:%.*]] = bitcast i32* [[A]] to i8*
-; CHECK-NEXT:    call void @llvm.lifetime.start.p0i8(i64 4, i8* [[TMP]])
+; 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:    [[TMP1:%.*]] = bitcast i8* [[S_ADDR_09]] to i32*
-; CHECK-NEXT:    [[TMP2:%.*]] = load i32, i32* [[TMP1]], align 4
-; CHECK-NEXT:    [[SHL_I:%.*]] = shl i32 [[TMP2]], 1
+; 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:    [[TMP3:%.*]] = load i32, i32* [[A]], align 4
-; CHECK-NEXT:    [[SUB_I:%.*]] = add i32 [[TMP3]], [[TMP2]]
+; 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:    [[TMP4:%.*]] = load i32, i32* [[A]], align 4
-; CHECK-NEXT:    call void @llvm.lifetime.end.p0i8(i64 4, i8* [[TMP]])
-; CHECK-NEXT:    ret i32 [[TMP4]]
+; 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
-  %tmp = bitcast i32* %a to i8*
-  call void @llvm.lifetime.start.p0i8(i64 4, i8* %tmp)
+  %t = bitcast i32* %a to i8*
+  call void @llvm.lifetime.start.p0i8(i64 4, i8* %t)
   store i32 -1640531527, i32* %a, align 4
   %cmp8 = icmp ugt i32 %len, 11
   br i1 %cmp8, label %while.body.lr.ph, label %while.end
 
 while.body.lr.ph:                                 ; preds = %entry
   br label %while.body
 
 while.body:                                       ; preds = %while.body, %while.body.lr.ph
   %keylen.010 = phi i32 [ %len, %while.body.lr.ph ], [ %sub, %while.body ]
   %s.addr.09 = phi i8* [ %s, %while.body.lr.ph ], [ %add.ptr, %while.body ]
-  %tmp1 = bitcast i8* %s.addr.09 to i32*
-  %tmp2 = load i32, i32* %tmp1, align 4
-  %shl.i = shl i32 %tmp2, 1
+  %t1 = bitcast i8* %s.addr.09 to i32*
+  %t2 = load i32, i32* %t1, align 4
+  %shl.i = shl i32 %t2, 1
   %and.i = and i32 %shl.i, 16843008
-  %tmp3 = load i32, i32* %a, align 4
-  %sub.i = add i32 %tmp3, %tmp2
+  %t3 = load i32, i32* %a, align 4
+  %sub.i = add i32 %t3, %t2
   %add = sub i32 %sub.i, %and.i
   store i32 %add, i32* %a, align 4
   %add.ptr = getelementptr inbounds i8, i8* %s.addr.09, i64 12
   %sub = add i32 %keylen.010, -12
   %cmp = icmp ugt i32 %sub, 11
   br i1 %cmp, label %while.body, label %while.cond.while.end_crit_edge
 
 while.cond.while.end_crit_edge:                   ; preds = %while.body
   %sub.lcssa = phi i32 [ %sub, %while.body ]
   br label %while.end
 
 while.end:                                        ; preds = %while.cond.while.end_crit_edge, %entry
   %keylen.0.lcssa = phi i32 [ %sub.lcssa, %while.cond.while.end_crit_edge ], [ %len, %entry ]
   call void @_Z3mixRjj(i32* dereferenceable(4) %a, i32 %keylen.0.lcssa)
-  %tmp4 = load i32, i32* %a, align 4
-  call void @llvm.lifetime.end.p0i8(i64 4, i8* %tmp)
-  ret i32 %tmp4
+  %t4 = load i32, i32* %a, align 4
+  call void @llvm.lifetime.end.p0i8(i64 4, i8* %t)
+  ret i32 %t4
 }
 
 define i32 @zero_backedge_count_test(i32 %unknown_init, i32* %unknown_mem) {
 ; CHECK-LABEL: @zero_backedge_count_test(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    br label [[LOOP:%.*]]
 ; CHECK:       loop:
 ; CHECK-NEXT:    [[UNKNOWN_NEXT:%.*]] = load volatile i32, i32* [[UNKNOWN_MEM:%.*]]