[SCEV] SCEVExpander::isHighCostExpansionHelper(): begin cost modelling - model cast cost

[lebedev.ri]

Summary

This is not a NFC, although it does not change any of the existing tests.
I'm not really sure if we should have specific tests for the cost modelling itself.

This is the first patch that actually makes SCEVExpander::isHighCostExpansionHelper()
account for the cost of the SCEV expression, and consider the budget available,
by modelling cast expressions.

I believe the logic itself is "pretty obviously correct" - from budget,
we need to subtract the cost of the cast expression from inner type Op->getType()
to the S->getType() type, and recurse into the expression we are casting.

[xbolva00]

llvm/include/llvm/Analysis/ScalarEvolutionExpander.h

177

Budget

[mkazantsev]

llvm/include/llvm/Analysis/ScalarEvolutionExpander.h

176–177

evaluate -> evaluated?

194

You already check this inside the helper, why do it twice?

llvm/lib/Analysis/ScalarEvolutionExpander.cpp

2160

Does it really need to be opcode, or we can pass SCEVType to getOperationCost?

[lebedev.ri]

llvm/lib/Analysis/ScalarEvolutionExpander.cpp

2160

TargetTransformInfo::getOperationCost() has no such SCEVType overload.
it can only be called with either opcode or preexisting existing IR instruction.

[lebedev.ri]

Addressed review notes.

[lebedev.ri]

Ping @mkazantsev / @reames
Thanks

[lebedev.ri]

Ping @reames / @mkazantsev
Thanks

[mkazantsev]

LGTM

[lebedev.ri]

In D73716#1881997, @mkazantsev wrote:

LGTM

Thank you for the review!

[lebedev.ri]

Rebased, NFC.

llvm/include/llvm/Analysis/ScalarEvolutionExpander.h

#endif
     /// places within the same BasicBlock can do so.
     void clear() {
       InsertedExpressions.clear();
       InsertedValues.clear();
       InsertedPostIncValues.clear();
       ChainedPhis.clear();
     }
 
-    /// Return true for expressions that may incur non-trivial cost to evaluate
-    /// at runtime.
+    /// Return true for expressions that can't be evaluated at runtime
+    /// within given \b Budget.
     ///
     /// At is an optional parameter which specifies point in code where user is
     /// going to expand this expression. Sometimes this knowledge can lead to a
     /// more accurate cost estimation.
     bool isHighCostExpansion(const SCEV *Expr, Loop *L, unsigned Budget,
                              const TargetTransformInfo *TTI,
                              const Instruction *At = nullptr) {
       assert(TTI && "This function requires TTI to be provided.");
       if (!TTI)      // In assert-less builds, avoid crashing
         return true; // by always claiming to be high-cost.
       SmallPtrSet<const SCEV *, 8> Processed;
       int BudgetRemaining = Budget * TargetTransformInfo::TCC_Basic;
       return isHighCostExpansionHelper(Expr, L, At, BudgetRemaining, *TTI,
                                        Processed);
     }
 
     /// This method returns the canonical induction variable of the specified
     /// type for the specified loop (inserting one if there is none).  A
     /// canonical induction variable starts at zero and steps by one on each
     /// iteration.
     PHINode *getOrInsertCanonicalInductionVariable(const Loop *L, Type *Ty);
 
     /// Return the induction variable increment's IV operand.
     Instruction *getIVIncOperand(Instruction *IncV, Instruction *InsertPos,
                                  bool allowScale);

llvm/lib/Analysis/ScalarEvolutionExpander.cpp

SCEVExpander::getRelatedExistingExpansion(const SCEV *S, const Instruction *At,
 
   // Can not find suitable value.
   return None;
 }
 
 bool SCEVExpander::isHighCostExpansionHelper(
     const SCEV *S, Loop *L, const Instruction *At, int &BudgetRemaining,
     const TargetTransformInfo &TTI, SmallPtrSetImpl<const SCEV *> &Processed) {
+  if (BudgetRemaining < 0)
+    return true; // Already run out of budget, give up.
+
   // Was the cost of expansion of this expression already accounted for?
   if (!Processed.insert(S).second)
     return false; // We have already accounted for this expression.
 
   // If we can find an existing value for this scev available at the point "At"
   // then consider the expression cheap.
   if (At && getRelatedExistingExpansion(S, At, L))
     return false; // Consider the expression to be free.
 
   switch (S->getSCEVType()) {
   case scUnknown:
   case scConstant:
     return false; // Assume to be zero-cost.
   }
 
-  // Zero/One operand expressions
+  if (auto *CastExpr = dyn_cast<SCEVCastExpr>(S)) {
+    unsigned Opcode;
     switch (S->getSCEVType()) {
     case scTruncate:
-    return isHighCostExpansionHelper(cast<SCEVTruncateExpr>(S)->getOperand(), L,
-                                     At, BudgetRemaining, TTI, Processed);
+      Opcode = Instruction::Trunc;
+      break;
     case scZeroExtend:
-    return isHighCostExpansionHelper(cast<SCEVZeroExtendExpr>(S)->getOperand(),
-                                     L, At, BudgetRemaining, TTI, Processed);
+      Opcode = Instruction::ZExt;
+      break;
     case scSignExtend:
-    return isHighCostExpansionHelper(cast<SCEVSignExtendExpr>(S)->getOperand(),
-                                     L, At, BudgetRemaining, TTI, Processed);
+      Opcode = Instruction::SExt;
+      break;
+    default:
+      llvm_unreachable("There are no other cast types.");
+    }
+    const SCEV *Op = CastExpr->getOperand();
+    BudgetRemaining -=
+        TTI.getOperationCost(Opcode, S->getType(), Op->getType());
+    return isHighCostExpansionHelper(Op, L, At, BudgetRemaining, TTI,
+                                     Processed);
   }
 
 
   if (auto *UDivExpr = dyn_cast<SCEVUDivExpr>(S)) {
     // If the divisor is a power of two and the SCEV type fits in a native
     // integer (and the LHS not expensive), consider the division cheap
     // irrespective of whether it occurs in the user code since it can be
     // lowered into a right shift.