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

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`.

Reviewers: reames, mkazantsev, wmi, sanjoy

Reviewed By: mkazantsev

Subscribers: hiraditya, llvm-commits

Tags: #llvm

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

1 files changed, 34 insertions, 0 deletions

diff --git a/llvm/lib/Analysis/ScalarEvolutionExpander.cpp b/llvm/lib/Analysis/ScalarEvolutionExpander.cpp
index abfb784..30634f7 100644
--- a/llvm/lib/Analysis/ScalarEvolutionExpander.cpp
+++ b/llvm/lib/Analysis/ScalarEvolutionExpander.cpp
@@ -2219,6 +2219,40 @@ bool SCEVExpander::isHighCostExpansionHelper(
                                      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))