[SCEVExpander] NFCI: Change Cost type in costAndCollectOperands from int -> unsigned.

[sdesmalen]

Summary

This patch intends to be a non-functional change. It changes the
type of BudgetRemaining and Cost in costAndCollectOperands from 'int' to
'unsigned' so that the algorithm checks beforehand whether the resulting
budget is going to be exceeded or invalidated, rather than relying on
BudgetRemaining to end up < 0.

This refactoring is a preparation for InstructionCost added in D91174, which
has an Invalid state. By checking the 'invalidated' case early, InstructionCost
can be a drop-in replacement for unsigned when D91174 lands.

[lebedev.ri]

I don't like this.
I intentionally made this change from unsigned to signed back in D67318,
and then followed the same pattern when re-writing isHighCostExpansionHelper(),
because using signed is that much more easy to catch budget overrun
as opposed to basically ensuring that each subtraction doesn't cause an overflow
(or failing to do that, and having an infinite budget)

[CarolineConcatto]

llvm/lib/Transforms/Utils/ScalarEvolutionExpander.cpp

2345

Should we not add the test SubtractFromBudget(BudgetRemaining, Cost);
here too?
Because removing the test (BudgetRemaining<0) from here it may change the code path, and something that in the past could return true, now may return false because of the two tests below.

[sdesmalen]

In D92237#2420530, @lebedev.ri wrote:

I don't like this.
I intentionally made this change from unsigned to signed back in D67318,
and then followed the same pattern when re-writing isHighCostExpansionHelper(),
because using signed is that much more easy to catch budget overrun
as opposed to basically ensuring that each subtraction doesn't cause an overflow
(or failing to do that, and having an infinite budget)

Fair enough, I didn't realise it had already been changed before. I thought it would be useful to rewrite it in anticipation of the InstructionCost class, but I've rewritten that patch now (D92238).

llvm/include/llvm/Transforms/Utils/ScalarEvolutionExpander.h

bool isHighCostExpansion(const SCEV *Expr, Loop *L, unsigned Budget,
                            const TargetTransformInfo *TTI,
                            const Instruction *At) {
     assert(TTI && "This function requires TTI to be provided.");
     assert(At && "This function requires At instruction to be provided.");
     if (!TTI)      // In assert-less builds, avoid crashing
       return true; // by always claiming to be high-cost.
     SmallVector<SCEVOperand, 8> Worklist;
     SmallPtrSet<const SCEV *, 8> Processed;
-    int BudgetRemaining = Budget * TargetTransformInfo::TCC_Basic;
+    unsigned BudgetRemaining = Budget * TargetTransformInfo::TCC_Basic;
     Worklist.emplace_back(-1, -1, Expr);
     while (!Worklist.empty()) {
       const SCEVOperand WorkItem = Worklist.pop_back_val();
       if (isHighCostExpansionHelper(WorkItem, L, *At, BudgetRemaining,
                                     *TTI, Processed, Worklist))
         return true;
     }
     assert(BudgetRemaining >= 0 && "Should have returned from inner loop.");
private:
 
   /// Insert code to directly compute the specified SCEV expression into the
   /// program. The code is inserted into the specified block. If \p
   /// Root is true, this indicates that \p SH is the top-level expression to
   /// expand passed from an external client call.
   Value *expandCodeForImpl(const SCEV *SH, Type *Ty, Instruction *I, bool Root);
 
   /// Recursive helper function for isHighCostExpansion.
   bool isHighCostExpansionHelper(
     const SCEVOperand &WorkItem, Loop *L, const Instruction &At,
-    int &BudgetRemaining, const TargetTransformInfo &TTI,
+    unsigned &BudgetRemaining, const TargetTransformInfo &TTI,
     SmallPtrSetImpl<const SCEV *> &Processed,
     SmallVectorImpl<SCEVOperand> &Worklist);
 
   /// Insert the specified binary operator, doing a small amount of work to
   /// avoid inserting an obviously redundant operation, and hoisting to an
   /// outer loop when the opportunity is there and it is safe.
   Value *InsertBinop(Instruction::BinaryOps Opcode, Value *LHS, Value *RHS,
                      SCEV::NoWrapFlags Flags, bool IsSafeToHoist);

llvm/lib/Transforms/Utils/ScalarEvolutionExpander.cpp

SCEVExpander::getRelatedExistingExpansion(const SCEV *S, const Instruction *At,
 
   // There is potential to make this significantly smarter, but this simple
   // heuristic already gets some interesting cases.
 
   // Can not find suitable value.
   return None;
 }
 
-template<typename T> static int costAndCollectOperands(
+template<typename T> static unsigned costAndCollectOperands(
   const SCEVOperand &WorkItem, const TargetTransformInfo &TTI,
   TargetTransformInfo::TargetCostKind CostKind,
   SmallVectorImpl<SCEVOperand> &Worklist) {
 
   const T *S = cast<T>(WorkItem.S);
   int Cost = 0;
   // Object to help map SCEV operands to expanded IR instructions.
   struct OperationIndices {
for (auto SCEVOp : enumerate(S->operands())) {
       Worklist.emplace_back(CostOp.Opcode, OpIdx, SCEVOp.value());
     }
   }
   return Cost;
 }
 
 bool SCEVExpander::isHighCostExpansionHelper(
     const SCEVOperand &WorkItem, Loop *L, const Instruction &At,
-    int &BudgetRemaining, const TargetTransformInfo &TTI,
+    unsigned &BudgetRemaining, const TargetTransformInfo &TTI,
     SmallPtrSetImpl<const SCEV *> &Processed,
     SmallVectorImpl<SCEVOperand> &Worklist) {
-  if (BudgetRemaining < 0)
-    return true; // Already run out of budget, give up.
-
   const SCEV *S = WorkItem.S;
   // Was the cost of expansion of this expression already accounted for?
   if (!isa<SCEVConstant>(S) && !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 (getRelatedExistingExpansion(S, &At, L))
     return false; // Consider the expression to be free.
 
   TargetTransformInfo::TargetCostKind CostKind =
       L->getHeader()->getParent()->hasMinSize()
           ? TargetTransformInfo::TCK_CodeSize
           : TargetTransformInfo::TCK_RecipThroughput;
 
+  // Convenience function to subtract from budget. Returns 'true'
+  // if the budget would be exceeded.
+  auto SubtractFromBudget = [](unsigned &BudgetRemaining,
+                               const unsigned &Cost) -> bool {
+    if (Cost > BudgetRemaining)
+      return true;
+
+    BudgetRemaining -= Cost;
+    return false;
+  };
+
   switch (S->getSCEVType()) {
   case scCouldNotCompute:
     llvm_unreachable("Attempt to use a SCEVCouldNotCompute object!");
   case scUnknown:
     // Assume to be zero-cost.
     return false;
   case scConstant: {
     // Only evalulate the costs of constants when optimizing for size.
     if (CostKind != TargetTransformInfo::TCK_CodeSize)
       return 0;
     const APInt &Imm = cast<SCEVConstant>(S)->getAPInt();
     Type *Ty = S->getType();
-    BudgetRemaining -= TTI.getIntImmCostInst(
+    unsigned Cost = TTI.getIntImmCostInst(
         WorkItem.ParentOpcode, WorkItem.OperandIdx, Imm, Ty, CostKind);
-    return BudgetRemaining < 0;
+    return SubtractFromBudget(BudgetRemaining, Cost);
   }
   case scTruncate:
   case scPtrToInt:
   case scZeroExtend:
   case scSignExtend: {
-    int Cost =
+    unsigned Cost =
         costAndCollectOperands<SCEVCastExpr>(WorkItem, TTI, CostKind, Worklist);
-    BudgetRemaining -= Cost;
-    return false; // Will answer upon next entry into this function.
+    return SubtractFromBudget(BudgetRemaining, Cost);
   }
   case scUDivExpr: {
     // 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, 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.
     if (getRelatedExistingExpansion(
             SE.getAddExpr(S, SE.getConstant(S->getType(), 1)), &At, L))
       return false; // Consider it to be free.
 
-    int Cost =
+    unsigned Cost =
         costAndCollectOperands<SCEVUDivExpr>(WorkItem, TTI, CostKind, Worklist);
-    // Need to count the cost of this UDiv.
-    BudgetRemaining -= Cost;
-    return false; // Will answer upon next entry into this function.
+    return SubtractFromBudget(BudgetRemaining, Cost);
   }
   case scAddExpr:
   case scMulExpr:
   case scUMaxExpr:
   case scSMaxExpr:
   case scUMinExpr:
   case scSMinExpr: {
     assert(cast<SCEVNAryExpr>(S)->getNumOperands() > 1 &&
            "Nary expr should have more than 1 operand.");
     // The simple nary expr will require one less op (or pair of ops)
     // than the number of it's terms.
-    int Cost =
+    unsigned Cost =
         costAndCollectOperands<SCEVNAryExpr>(WorkItem, TTI, CostKind, Worklist);
-    BudgetRemaining -= Cost;
-    return BudgetRemaining < 0;
+    return SubtractFromBudget(BudgetRemaining, Cost);
   }
   case scAddRecExpr: {
     assert(cast<SCEVAddRecExpr>(S)->getNumOperands() >= 2 &&
            "Polynomial should be at least linear");
-    BudgetRemaining -= costAndCollectOperands<SCEVAddRecExpr>(
+    unsigned Cost = costAndCollectOperands<SCEVAddRecExpr>(
         WorkItem, TTI, CostKind, Worklist);
-    return BudgetRemaining < 0;
+    return SubtractFromBudget(BudgetRemaining, Cost);
   }
   }
   llvm_unreachable("Unknown SCEV kind!");
 }
 
 Value *SCEVExpander::expandCodeForPredicate(const SCEVPredicate *Pred,
                                             Instruction *IP) {
   assert(IP);