[SCEV] SCEVExpander::isHighCostExpansionHelper(): cost-model add/mul

[lebedev.ri]

Summary

While this resolves the regression from D73722 in llvm/test/Transforms/IndVarSimplify/exit_value_test2.ll,
this now regresses llvm/test/Transforms/IndVarSimplify/elim-extend.ll @nestedIV test,
we no longer can perform that expansion within default budget of 4, but require budget of 6.
That regression is being addressed by D73777.

The basic idea here is simple.

Op0,  Op1, Op2 ...
 |     |    |
 \--+--/    |
    |       |
    \---+---/

I.e. given N operands, we will have N-1 operations,
so we have to add cost of an add (mul) for every Op processed,
except the first one, plus we need to recurse into *every* Op.

I'm guessing there's already canonicalization that ensures we won't
have 1 operand in scMulExpr, and no 0 in scAddExpr/scMulExpr.

[lebedev.ri]

NFC, fixup diff.

[lebedev.ri]

Rebased.

[lebedev.ri]

Ping @mkazantsev / @reames
Thanks

[lebedev.ri]

Ping @reames / @mkazantsev
Thanks

[lebedev.ri]

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

[mkazantsev]

LGTM

llvm/lib/Analysis/ScalarEvolutionExpander.cpp

2247

Just a suggestion, feel free to ignore: break if BudgetRemaining goes below zero in the loop to save time processing really huge SCEVs with many operands.

[mkazantsev]

llvm/lib/Analysis/ScalarEvolutionExpander.cpp

2247

Or actually nvm, I guess it should be handled inside the helper.

[mkazantsev]

llvm/lib/Analysis/ScalarEvolutionExpander.cpp

2238

This is a very rough approximation for Mul, because of Bin Pow algorithm used in Expander. See https://github.com/llvm-mirror/llvm/blob/master/lib/Analysis/ScalarEvolutionExpander.cpp#L781. You might want to factor it in in the future, but what you did is fine for the 1st step. Please add a TODO for that.

[lebedev.ri]

In D73728#1890687, @mkazantsev wrote:

LGTM

Thank you for the review!

llvm/lib/Analysis/ScalarEvolutionExpander.cpp

2238

Aha, good point. I will add a TODO.

2247

Indeed, the idea is that it will be handled by isHighCostExpansionHelper().

[lebedev.ri]

Rebased, added TODO.

llvm/lib/Analysis/ScalarEvolutionExpander.cpp

if (auto *UDivExpr = dyn_cast<SCEVUDivExpr>(S)) {
     // 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);
   }
 
+  if (S->getSCEVType() == scAddExpr || S->getSCEVType() == scMulExpr) {
+    const SCEVNAryExpr *NAry = dyn_cast<SCEVNAryExpr>(S);
+
+    unsigned Opcode;
+    switch (S->getSCEVType()) {
+    case scAddExpr:
+      Opcode = Instruction::Add;
+      break;
+    case scMulExpr:
+      Opcode = Instruction::Mul;
+      break;
+    default:
+      llvm_unreachable("There are no other variants here.");
+    }
+
+    Type *OpType = NAry->getType();
+    int PairCost = TTI.getOperationCost(Opcode, OpType);
+    // TODO: this is a very pessimistic cost modelling for Mul,
+    // because of Bin Pow algorithm actually used by the expander,
+    // see SCEVExpander::visitMulExpr(), ExpandOpBinPowN().
+
+    assert(NAry->getNumOperands() > 1 &&
+           "Nary expr should have more than 1 operand.");
+    for (const SCEV *Op : NAry->operands()) {
+      if (isHighCostExpansionHelper(Op, L, At, BudgetRemaining, TTI, Processed))
+        return true;
+      if (Op == *NAry->op_begin())
+        continue;
+      BudgetRemaining -= PairCost;
+    }
+
+    return BudgetRemaining < 0;
+  }
+
   // 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
   // BackedgeTakenCount. They may already exist in program code, and if not,
   // they are not too expensive rematerialize.

llvm/test/Transforms/IndVarSimplify/elim-extend.ll

 ; CHECK-NEXT:    br label [[INNERLOOP:%.*]]
 ; CHECK:       innerloop:
 ; CHECK-NEXT:    [[INDVARS_IV:%.*]] = phi i64 [ [[TMP3]], [[INNERLOOP_PREHEADER]] ], [ [[INDVARS_IV_NEXT:%.*]], [[INNERLOOP]] ]
 ; CHECK-NEXT:    [[INDVARS_IV_NEXT]] = add nsw i64 [[INDVARS_IV]], 1
 ; CHECK-NEXT:    [[ADR2:%.*]] = getelementptr i8, i8* [[ADDRESS]], i64 [[INDVARS_IV]]
 ; CHECK-NEXT:    store i8 0, i8* [[ADR2]]
 ; CHECK-NEXT:    [[ADR3:%.*]] = getelementptr i8, i8* [[ADDRESS]], i64 [[INDVARS_IV_NEXT]]
 ; CHECK-NEXT:    store i8 0, i8* [[ADR3]]
-; CHECK-NEXT:    [[EXITCOND:%.*]] = icmp ne i64 [[INDVARS_IV_NEXT]], [[TMP0]]
-; CHECK-NEXT:    br i1 [[EXITCOND]], label [[INNERLOOP]], label [[INNEREXIT:%.*]]
+; CHECK-NEXT:    [[INNERCMP:%.*]] = icmp sgt i64 [[TMP0]], [[INDVARS_IV_NEXT]]
+; CHECK-NEXT:    br i1 [[INNERCMP]], label [[INNERLOOP]], label [[INNEREXIT:%.*]]
 ; CHECK:       innerexit:
 ; CHECK-NEXT:    [[INNERCOUNT_LCSSA_WIDE:%.*]] = phi i64 [ [[INDVARS_IV_NEXT]], [[INNERLOOP]] ]
 ; CHECK-NEXT:    [[TMP4:%.*]] = trunc i64 [[INNERCOUNT_LCSSA_WIDE]] to i32
 ; CHECK-NEXT:    br label [[OUTERMERGE]]
 ; CHECK:       outermerge:
 ; CHECK-NEXT:    [[INNERCOUNT_MERGE]] = phi i32 [ [[TMP4]], [[INNEREXIT]] ], [ [[INNERCOUNT]], [[INNERPREHEADER]] ]
 ; CHECK-NEXT:    [[ADR4:%.*]] = getelementptr i8, i8* [[ADDRESS]], i64 [[INDVARS_IV1]]
 ; CHECK-NEXT:    store i8 0, i8* [[ADR4]]

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:    [[TMP3:%.*]] = sub i32 [[TMP0]], [[TMP2]]
+; CHECK-NEXT:    [[SUB_LCSSA:%.*]] = phi i32 [ [[SUB]], [[WHILE_BODY]] ]
 ; CHECK-NEXT:    br label [[WHILE_END]]
 ; CHECK:       while.end:
-; CHECK-NEXT:    [[KEYLEN_0_LCSSA:%.*]] = phi i32 [ [[TMP3]], [[WHILE_COND_WHILE_END_CRIT_EDGE]] ], [ [[LEN]], [[ENTRY:%.*]] ]
+; CHECK-NEXT:    [[KEYLEN_0_LCSSA:%.*]] = phi i32 [ [[SUB_LCSSA]], [[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*