Index: llvm/include/llvm/Transforms/Utils/ScalarEvolutionExpander.h
===================================================================
--- llvm/include/llvm/Transforms/Utils/ScalarEvolutionExpander.h
+++ llvm/include/llvm/Transforms/Utils/ScalarEvolutionExpander.h
@@ -235,7 +235,7 @@
       return true; // by always claiming to be high-cost.
     SmallVector<SCEVOperand, 8> Worklist;
     SmallPtrSet<const SCEV *, 8> Processed;
-    unsigned BudgetRemaining = Budget * TargetTransformInfo::TCC_Basic;
+    InstructionCost BudgetRemaining(Budget * TargetTransformInfo::TCC_Basic);
     Worklist.emplace_back(-1, -1, Expr);
     while (!Worklist.empty()) {
       const SCEVOperand WorkItem = Worklist.pop_back_val();
@@ -243,7 +243,9 @@
                                     *TTI, Processed, Worklist))
         return true;
     }
-    assert(BudgetRemaining >= 0 && "Should have returned from inner loop.");
+    assert(BudgetRemaining.isValid() && "Expected a valid cost");
+    assert(*BudgetRemaining.getValue() >= 0 &&
+           "Should have returned from inner loop.");
     return false;
   }
 
@@ -409,7 +411,7 @@
   /// Recursive helper function for isHighCostExpansion.
   bool isHighCostExpansionHelper(
     const SCEVOperand &WorkItem, Loop *L, const Instruction &At,
-    unsigned &BudgetRemaining, const TargetTransformInfo &TTI,
+    InstructionCost &BudgetRemaining, const TargetTransformInfo &TTI,
     SmallPtrSetImpl<const SCEV *> &Processed,
     SmallVectorImpl<SCEVOperand> &Worklist);
 
Index: llvm/lib/Transforms/Utils/ScalarEvolutionExpander.cpp
===================================================================
--- llvm/lib/Transforms/Utils/ScalarEvolutionExpander.cpp
+++ llvm/lib/Transforms/Utils/ScalarEvolutionExpander.cpp
@@ -15,6 +15,7 @@
 #include "llvm/Transforms/Utils/ScalarEvolutionExpander.h"
 #include "llvm/ADT/STLExtras.h"
 #include "llvm/ADT/SmallSet.h"
+#include "llvm/Analysis/InstructionCost.h"
 #include "llvm/Analysis/InstructionSimplify.h"
 #include "llvm/Analysis/LoopInfo.h"
 #include "llvm/Analysis/TargetTransformInfo.h"
@@ -2199,7 +2200,7 @@
   return None;
 }
 
-template<typename T> static unsigned costAndCollectOperands(
+template<typename T> static InstructionCost costAndCollectOperands(
   const SCEVOperand &WorkItem, const TargetTransformInfo &TTI,
   TargetTransformInfo::TargetCostKind CostKind,
   SmallVectorImpl<SCEVOperand> &Worklist) {
@@ -2340,7 +2341,7 @@
 
 bool SCEVExpander::isHighCostExpansionHelper(
     const SCEVOperand &WorkItem, Loop *L, const Instruction &At,
-    unsigned &BudgetRemaining, const TargetTransformInfo &TTI,
+    InstructionCost &BudgetRemaining, const TargetTransformInfo &TTI,
     SmallPtrSetImpl<const SCEV *> &Processed,
     SmallVectorImpl<SCEVOperand> &Worklist) {
   const SCEV *S = WorkItem.S;
@@ -2359,10 +2360,11 @@
           : 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)
+  // if the budget would be exceeded or if Cost is not a valid
+  // cost.
+  auto SubtractFromBudget = [](InstructionCost &BudgetRemaining,
+                               const InstructionCost &Cost) -> bool {
+    if (!Cost.isValid() || *Cost.getValue() > *BudgetRemaining.getValue())
       return true;
 
     BudgetRemaining -= Cost;
@@ -2381,7 +2383,7 @@
       return 0;
     const APInt &Imm = cast<SCEVConstant>(S)->getAPInt();
     Type *Ty = S->getType();
-    unsigned Cost = TTI.getIntImmCostInst(
+    InstructionCost Cost = TTI.getIntImmCostInst(
         WorkItem.ParentOpcode, WorkItem.OperandIdx, Imm, Ty, CostKind);
     return SubtractFromBudget(BudgetRemaining, Cost);
   }
@@ -2389,7 +2391,7 @@
   case scPtrToInt:
   case scZeroExtend:
   case scSignExtend: {
-    unsigned Cost =
+    InstructionCost Cost =
         costAndCollectOperands<SCEVCastExpr>(WorkItem, TTI, CostKind, Worklist);
     return SubtractFromBudget(BudgetRemaining, Cost);
   }
@@ -2406,7 +2408,7 @@
             SE.getAddExpr(S, SE.getConstant(S->getType(), 1)), &At, L))
       return false; // Consider it to be free.
 
-    unsigned Cost =
+    InstructionCost Cost =
         costAndCollectOperands<SCEVUDivExpr>(WorkItem, TTI, CostKind, Worklist);
     return SubtractFromBudget(BudgetRemaining, Cost);
   }
@@ -2420,14 +2422,14 @@
            "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.
-    unsigned Cost =
+    InstructionCost Cost =
         costAndCollectOperands<SCEVNAryExpr>(WorkItem, TTI, CostKind, Worklist);
     return SubtractFromBudget(BudgetRemaining, Cost);
   }
   case scAddRecExpr: {
     assert(cast<SCEVAddRecExpr>(S)->getNumOperands() >= 2 &&
            "Polynomial should be at least linear");
-    unsigned Cost = costAndCollectOperands<SCEVAddRecExpr>(
+    InstructionCost Cost = costAndCollectOperands<SCEVAddRecExpr>(
         WorkItem, TTI, CostKind, Worklist);
     return SubtractFromBudget(BudgetRemaining, Cost);
   }