[Support] Migrate more high level cost functions to using InstructionCost

[david-arm]

Summary

This patch changes the following TargetTransformInfo and BasicTTIIMpl
interfaces to return a InstructionCost class:

getUserCost
getInstructionLatency
getInstructionThroughput

As a result of changing getUserCost I have also had to fix up various
places where it is called. In places where it's obvious that we should
never encounter an invalid cost I have added an assert and dereferenced
the value. In other places where trivial I have simply added isValid()
checks and bailed out of an optimisation.

See this patch for the introduction of the type: https://reviews.llvm.org/D91174
See this thread for context: http://lists.llvm.org/pipermail/llvm-dev/2020-November/146408.html

[david-arm]

• Rebased off parent patch.
• Changed calls to isInvalid to !isValid instead, since I feel this is more future-proof in case additional states are added to the InstructionCost class.

[david-arm]

• After some private discussions with @paulwalker-arm I think that we shouldn't rely upon the comparison operators treating invalid costs as infinite. Instead it's better to explicitly check for validity before comparing.

[CarolineConcatto]

Thank you @david-arm for the patch.
It helps to understand a bit more how to use the new class InstructionCost in D91174
I hope you don't mind but I have a couple of questions.

llvm/lib/Transforms/Scalar/LoopUnswitch.cpp

306 ↗

(On Diff #308020)

This assumes that Metrics.NumInsts.getValue(), should we check if Metrics.NumInsts.isValid()?

llvm/lib/Transforms/Scalar/SimpleLoopUnswitch.cpp

2602

Why we do not use InstructionCost in this function when computing the Instruction costs?
You've only replaced in one place, but not others.

llvm/lib/Transforms/Scalar/SpeculateAroundPHIs.cpp

506

The behaviour of SpecCost invalid is the same if SpecCost is lower than CostSaving?
Should LLVM_DEBUG inform that the costs are invalid?

[david-arm]

llvm/lib/Transforms/Scalar/LoopUnswitch.cpp

306 ↗

(On Diff #308020)

Yeah I could have used isValid() here too, but getValue() returns an Optional<int>, which cannot be used directly anyway. I thought it was cleaner to write it this way and only reference Metric.NumInsts once. The alternative would be to write:

if (Metrics.NumInsts.isValid())

Props.SizeEstimation = *(Metrics.NumInsts.getValue());

else

Props.SizeEstimation = std::numeric_limits<unsigned>::max();

Both ways of writing are functionally correct though! I've tended to use isValid() in places where we don't need to extract the value, i.e. for asserts, before doing comparisons or to bail out early from an optimisation.

llvm/lib/Transforms/Scalar/SimpleLoopUnswitch.cpp

2602

This patch only changes code that's relevant to TTI.getUserCost(), etc and I've tried to avoid making the patch too large by only changing the places that absolutely had to use InstructionCost. The code below had existing asserts that the instruction cost is valid, so I thought I could do the same thing. If the InstructionCost is valid that means we can safely extract the value from InstructionCost and store as an integer in BBCostMap. It may be that at some point in the future we will encounter invalid costs, but I thought it was best not to try to guess what might happen and just wait to see if it's really a problem or not.

llvm/lib/Transforms/Scalar/SpeculateAroundPHIs.cpp

506

The InstructionCost has an operator<< that prints out "Invalid" if the cost is invalid so the debug would look like this:

" Not profitable, speculation cost: ...\n"
" Cost savings: ...\n"
" SpecCost: Invalid\n"

I just thought that was probably enough for the user to figure out something had gone wrong that's all.

[paulwalker-arm]

llvm/lib/Transforms/Scalar/LoopUnswitch.cpp

306 ↗

(On Diff #308020)

For the case where the number of instructions is unknown why not treat this as a reason not to unswitch the loop rather than than trying to second guess how Props.SizeEstimation will be used when determining a sensible value to set it to? You could even add an LLVM_DEBUG to report when this happens.

I think this will be a general comment of my for any such code where we want to support not knowing the cost of something or more specifically when the cost is invalid and thus unusable.

[david-arm]

llvm/lib/Transforms/Scalar/LoopUnswitch.cpp

306 ↗

(On Diff #308020)

Sure, I completely agree with you. My problem here is that I simply didn't know what value to set it to when invalid. It has to be set to something and I wasn't trying to second guess here - I was just trying to ensure it had some sort of obvious, debuggable value, rather than random data. The flag "Metrics.notDuplicatable" will be set to true when invalid and you'll see this is checked below, however I couldn't be sure that Props wouldn't still be checked even if notDuplicatable is true. The Props structure goes into a LoopsProperties map that is kept around for later - it's not thrown away if not duplicatable.

[sdesmalen]

llvm/lib/Analysis/CodeMetrics.cpp

182

If the basic-block contains an instruction that would have an Invalid codesize-cost, that means it can't be expanded and having such an instruction in the block is an error. So you can just dereference TTI.getUserCost(...) here directly (which will fail when the cost is invalid). That also removes the need for a lot of the other changes.

llvm/lib/Transforms/Scalar/LoopDataPrefetch.cpp

303 ↗

(On Diff #308020)

nit: the extra parenthesis are not required, e.g. unsigned LoopSize = *Metrics.NumInsts.getValue();

llvm/lib/Transforms/Scalar/LoopFlatten.cpp

324

The same holds true here (that you can just dereference RepeatedInstrCost) because the cost should never be Invalid.

[david-arm]

llvm/lib/Transforms/Scalar/LoopFlatten.cpp

324

Hi @sdesmalen, I wasn't sure if that was the case here because we're iterating through blocks in the FlattenInfo structure that the caller created. I wondered if there was a possibility someone might have created some new instructions or modified existing ones and it seemed trivial to add a check here.

[david-arm]

• Following discussions on D94069, I've removed unnecessary checks for isValid when comparing costs.

[ctetreau]

llvm/include/llvm/Analysis/TargetTransformInfoImpl.h

1017

Where are all of these "return -1"'s handled?

llvm/lib/Transforms/Scalar/LoopUnrollPass.cpp

533

I think this is a functional change. Before it returned a non-None garbage value, and now it returns None. Is there a test that can be written for this?

llvm/include/llvm/Analysis/TargetTransformInfo.h

InstructionCost getInstructionCost(const Instruction *I,
     case TCK_Latency:
       Cost = getInstructionLatency(I);
       break;
     case TCK_CodeSize:
     case TCK_SizeAndLatency:
       Cost = getUserCost(I, kind);
       break;
     }
-    if (Cost == -1)
-      Cost.setInvalid();
     return Cost;
   }
 
   /// Underlying constants for 'cost' values in this interface.
   ///
   /// Many APIs in this interface return a cost. This enum defines the
   /// fundamental values that should be used to interpret (and produce) those
   /// costs. The costs are returned as an int rather than a member of this
public:
   /// \p Operands is a list of operands which can be a result of transformations
   /// of the current operands. The number of the operands on the list must equal
   /// to the number of the current operands the IR user has. Their order on the
   /// list must be the same as the order of the current operands the IR user
   /// has.
   ///
   /// The returned cost is defined in terms of \c TargetCostConstants, see its
   /// comments for a detailed explanation of the cost values.
-  int getUserCost(const User *U, ArrayRef<const Value *> Operands,
+  InstructionCost getUserCost(const User *U, ArrayRef<const Value *> Operands,
                               TargetCostKind CostKind) const;
 
   /// This is a helper function which calls the two-argument getUserCost
   /// with \p Operands which are the current operands U has.
-  int getUserCost(const User *U, TargetCostKind CostKind) const {
+  InstructionCost getUserCost(const User *U, TargetCostKind CostKind) const {
     SmallVector<const Value *, 4> Operands(U->operand_values());
     return getUserCost(U, Operands, CostKind);
   }
 
   /// Return true if branch divergence exists.
   ///
   /// Branch divergence has a significantly negative impact on GPU performance
   /// when threads in the same wavefront take different paths due to conditional

 
   /// @}
 
   /// @}
 
 private:
   /// Estimate the latency of specified instruction.
   /// Returns 1 as the default value.
-  int getInstructionLatency(const Instruction *I) const;
+  InstructionCost getInstructionLatency(const Instruction *I) const;
 
   /// Returns the expected throughput cost of the instruction.
   /// Returns -1 if the cost is unknown.
-  int getInstructionThroughput(const Instruction *I) const;
+  InstructionCost getInstructionThroughput(const Instruction *I) const;
 
   /// The abstract base class used to type erase specific TTI
   /// implementations.
   class Concept;
 
   /// The template model for the base class which wraps a concrete
   /// implementation in a type erased interface.
   template <typename T> class Model;
virtual int getGEPCost(Type *PointeeType, const Value *Ptr,
                          TTI::TargetCostKind CostKind) = 0;
   virtual unsigned getInliningThresholdMultiplier() = 0;
   virtual int getInlinerVectorBonusPercent() = 0;
   virtual int getMemcpyCost(const Instruction *I) = 0;
   virtual unsigned
   getEstimatedNumberOfCaseClusters(const SwitchInst &SI, unsigned &JTSize,
                                    ProfileSummaryInfo *PSI,
                                    BlockFrequencyInfo *BFI) = 0;
-  virtual int getUserCost(const User *U, ArrayRef<const Value *> Operands,
+  virtual InstructionCost getUserCost(const User *U,
+                                      ArrayRef<const Value *> Operands,
                                       TargetCostKind CostKind) = 0;
   virtual bool hasBranchDivergence() = 0;
   virtual bool useGPUDivergenceAnalysis() = 0;
   virtual bool isSourceOfDivergence(const Value *V) = 0;
   virtual bool isAlwaysUniform(const Value *V) = 0;
   virtual unsigned getFlatAddressSpace() = 0;
   virtual bool collectFlatAddressOperands(SmallVectorImpl<int> &OpIndexes,
                                           Intrinsic::ID IID) const = 0;
   virtual bool isNoopAddrSpaceCast(unsigned FromAS, unsigned ToAS) const = 0;
public:
   virtual bool preferInLoopReduction(unsigned Opcode, Type *Ty,
                                      ReductionFlags) const = 0;
   virtual bool preferPredicatedReductionSelect(unsigned Opcode, Type *Ty,
                                                ReductionFlags) const = 0;
   virtual bool shouldExpandReduction(const IntrinsicInst *II) const = 0;
   virtual unsigned getGISelRematGlobalCost() const = 0;
   virtual bool supportsScalableVectors() const = 0;
   virtual bool hasActiveVectorLength() const = 0;
-  virtual int getInstructionLatency(const Instruction *I) = 0;
+  virtual InstructionCost getInstructionLatency(const Instruction *I) = 0;
 };
 
 template <typename T>
 class TargetTransformInfo::Model final : public TargetTransformInfo::Concept {
   T Impl;
 
 public:
   Model(T Impl) : Impl(std::move(Impl)) {}
unsigned getInliningThresholdMultiplier() override {
     return Impl.getInliningThresholdMultiplier();
   }
   int getInlinerVectorBonusPercent() override {
     return Impl.getInlinerVectorBonusPercent();
   }
   int getMemcpyCost(const Instruction *I) override {
     return Impl.getMemcpyCost(I);
   }
-  int getUserCost(const User *U, ArrayRef<const Value *> Operands,
+  InstructionCost getUserCost(const User *U, ArrayRef<const Value *> Operands,
                               TargetCostKind CostKind) override {
     return Impl.getUserCost(U, Operands, CostKind);
   }
   bool hasBranchDivergence() override { return Impl.hasBranchDivergence(); }
   bool useGPUDivergenceAnalysis() override {
     return Impl.useGPUDivergenceAnalysis();
   }
   bool isSourceOfDivergence(const Value *V) override {
     return Impl.isSourceOfDivergence(V);
public:
   bool supportsScalableVectors() const override {
     return Impl.supportsScalableVectors();
   }
 
   bool hasActiveVectorLength() const override {
     return Impl.hasActiveVectorLength();
   }
 
-  int getInstructionLatency(const Instruction *I) override {
+  InstructionCost getInstructionLatency(const Instruction *I) override {
     return Impl.getInstructionLatency(I);
   }
 };
 
 template <typename T>
 TargetTransformInfo::TargetTransformInfo(T Impl)
     : TTIImpl(new Model<T>(Impl)) {}
 

llvm/include/llvm/Analysis/TargetTransformInfoImpl.h

int getGEPCost(Type *PointeeType, const Value *Ptr,
     if (static_cast<T *>(this)->isLegalAddressingMode(
             TargetType, const_cast<GlobalValue *>(BaseGV),
             BaseOffset.sextOrTrunc(64).getSExtValue(), HasBaseReg, Scale,
             Ptr->getType()->getPointerAddressSpace()))
       return TTI::TCC_Free;
     return TTI::TCC_Basic;
   }
 
-  int getUserCost(const User *U, ArrayRef<const Value *> Operands,
+  InstructionCost getUserCost(const User *U, ArrayRef<const Value *> Operands,
                               TTI::TargetCostKind CostKind) {
     auto *TargetTTI = static_cast<T *>(this);
     // Handle non-intrinsic calls, invokes, and callbr.
     // FIXME: Unlikely to be true for anything but CodeSize.
     auto *CB = dyn_cast<CallBase>(U);
     if (CB && !isa<IntrinsicInst>(U)) {
       if (const Function *F = CB->getCalledFunction()) {
         if (!TargetTTI->isLoweredToCall(F))
           return TTI::TCC_Basic; // Give a basic cost if it will be lowered
case Instruction::ShuffleVector: {
       auto *VecSrcTy = cast<VectorType>(U->getOperand(0)->getType());
 
       // TODO: Identify and add costs for insert subvector, etc.
       int SubIndex;
       if (Shuffle->isExtractSubvectorMask(SubIndex))
         return TargetTTI->getShuffleCost(TTI::SK_ExtractSubvector, VecSrcTy,
                                          SubIndex, VecTy);
       else if (Shuffle->changesLength())
-        return CostKind == TTI::TCK_RecipThroughput ? -1 : 1;
+        return CostKind == TTI::TCK_RecipThroughput
+                   ? InstructionCost::getInvalid()
+                   : 1;
       else if (Shuffle->isIdentity())
         return 0;
       else if (Shuffle->isReverse())
         return TargetTTI->getShuffleCost(TTI::SK_Reverse, VecTy, 0, nullptr);
       else if (Shuffle->isSelect())
         return TargetTTI->getShuffleCost(TTI::SK_Select, VecTy, 0, nullptr);
       else if (Shuffle->isTranspose())
         return TargetTTI->getShuffleCost(TTI::SK_Transpose, VecTy, 0, nullptr);
case Instruction::ExtractElement: {
       return TargetTTI->getVectorInstrCost(Opcode, U->getOperand(0)->getType(),
                                            Idx);
     }
     }
     // By default, just classify everything as 'basic'.
     return TTI::TCC_Basic;
   }
 
-  int getInstructionLatency(const Instruction *I) {
+  InstructionCost getInstructionLatency(const Instruction *I) {
     SmallVector<const Value *, 4> Operands(I->operand_values());
     if (getUserCost(I, Operands, TTI::TCK_Latency) == TTI::TCC_Free)
       return 0;
 
     if (isa<LoadInst>(I))
       return 4;
 
     Type *DstTy = I->getType();

llvm/include/llvm/CodeGen/BasicTTIImpl.h

Optional<Value *> simplifyDemandedVectorEltsIntrinsic(
       APInt &UndefElts2, APInt &UndefElts3,
       std::function<void(Instruction *, unsigned, APInt, APInt &)>
           SimplifyAndSetOp) {
     return BaseT::simplifyDemandedVectorEltsIntrinsic(
         IC, II, DemandedElts, UndefElts, UndefElts2, UndefElts3,
         SimplifyAndSetOp);
   }
 
-  int getInstructionLatency(const Instruction *I) {
+  InstructionCost getInstructionLatency(const Instruction *I) {
     if (isa<LoadInst>(I))
       return getST()->getSchedModel().DefaultLoadLatency;
 
     return BaseT::getInstructionLatency(I);
   }
 
   virtual Optional<unsigned>
   getCacheSize(TargetTransformInfo::CacheLevel Level) const {

llvm/include/llvm/Support/InstructionCost.h

public:
 
   static InstructionCost max(InstructionCost LHS, InstructionCost RHS) {
     return LHS > RHS ? LHS : RHS;
   }
 
   void print(raw_ostream &OS) const;
 };
 
+inline bool operator==(const InstructionCost::CostType LHS,
+                       const InstructionCost &RHS) {
+  return RHS == LHS;
+}
+
+inline bool operator!=(const InstructionCost::CostType LHS,
+                       const InstructionCost &RHS) {
+  return RHS != LHS;
+}
+
 inline InstructionCost operator+(const InstructionCost &LHS,
                                  const InstructionCost &RHS) {
   InstructionCost LHS2(LHS);
   LHS2 += RHS;
   return LHS2;
 }
 
 inline InstructionCost operator-(const InstructionCost &LHS,

llvm/lib/Analysis/CodeMetrics.cpp

if (const CallInst *CI = dyn_cast<CallInst>(&I)) {
       if (CI->isConvergent())
         convergent = true;
     }
 
     if (const InvokeInst *InvI = dyn_cast<InvokeInst>(&I))
       if (InvI->cannotDuplicate())
         notDuplicatable = true;
 
-    NumInsts += TTI.getUserCost(&I, TargetTransformInfo::TCK_CodeSize);
+    InstructionCost Cost =
+        TTI.getUserCost(&I, TargetTransformInfo::TCK_CodeSize);
+    assert(Cost.isValid() && "Unexpected invalid cost");
+    NumInsts += *Cost.getValue();
   }
 
   if (isa<ReturnInst>(BB->getTerminator()))
     ++NumRets;
 
   // We never want to inline functions that contain an indirectbr.  This is
   // incorrect because all the blockaddress's (in static global initializers
   // for example) would be referring to the original function, and this indirect
   // jump would jump from the inlined copy of the function into the original
   // function which is extremely undefined behavior.
   // FIXME: This logic isn't really right; we can safely inline functions
   // with indirectbr's as long as no other function or global references the
   // blockaddress of a block within the current function.  And as a QOI issue,
   // if someone is using a blockaddress without an indirectbr, and that
   // reference somehow ends up in another function or global, we probably
   // don't want to inline this function.
   notDuplicatable |= isa<IndirectBrInst>(BB->getTerminator());
 
   // Remember NumInsts for this BB.
   NumBBInsts[BB] = NumInsts - NumInstsBeforeThisBB;
 }

llvm/lib/Analysis/TargetTransformInfo.cpp

 }
 
 unsigned TargetTransformInfo::getEstimatedNumberOfCaseClusters(
     const SwitchInst &SI, unsigned &JTSize, ProfileSummaryInfo *PSI,
     BlockFrequencyInfo *BFI) const {
   return TTIImpl->getEstimatedNumberOfCaseClusters(SI, JTSize, PSI, BFI);
 }
 
-int TargetTransformInfo::getUserCost(const User *U,
-                                     ArrayRef<const Value *> Operands,
-                                     enum TargetCostKind CostKind) const {
-  int Cost = TTIImpl->getUserCost(U, Operands, CostKind);
-  assert((CostKind == TTI::TCK_RecipThroughput || Cost >= 0) &&
-         "TTI should not produce negative costs!");
+InstructionCost
+TargetTransformInfo::getUserCost(const User *U,
+  InstructionCost Cost = TTIImpl->getUserCost(U, Operands, CostKind);
+  assert((CostKind == TTI::TCK_RecipThroughput || Cost.isValid()) &&
+         "TTI should not produce invalid costs!");
   return Cost;
 }
 
 bool TargetTransformInfo::hasBranchDivergence() const {
   return TTIImpl->hasBranchDivergence();
 }
 
 bool TargetTransformInfo::useGPUDivergenceAnalysis() const {

 unsigned TargetTransformInfo::getGISelRematGlobalCost() const {
   return TTIImpl->getGISelRematGlobalCost();
 }
 
 bool TargetTransformInfo::supportsScalableVectors() const {
   return TTIImpl->supportsScalableVectors();
 }
 
-int TargetTransformInfo::getInstructionLatency(const Instruction *I) const {
+InstructionCost
+TargetTransformInfo::getInstructionLatency(const Instruction *I) const {
   return TTIImpl->getInstructionLatency(I);
 }
 
 static bool matchPairwiseShuffleMask(ShuffleVectorInst *SI, bool IsLeft,
                                      unsigned Level) {
   // We don't need a shuffle if we just want to have element 0 in position 0 of
   // the vector.
   if (!SI && Level == 0 && IsLeft)
TTI::matchVectorReduction(const ExtractElementInst *Root, unsigned &Opcode,
   if (RdxKind != TTI::ReductionKind::RK_None) {
     IsPairwise = false;
     return RdxKind;
   }
   IsPairwise = true;
   return matchPairwiseReduction(Root, Opcode, Ty);
 }
 
-int TargetTransformInfo::getInstructionThroughput(const Instruction *I) const {
+InstructionCost
+TargetTransformInfo::getInstructionThroughput(const Instruction *I) const {
   TTI::TargetCostKind CostKind = TTI::TCK_RecipThroughput;
 
   switch (I->getOpcode()) {
   case Instruction::GetElementPtr:
   case Instruction::Ret:
   case Instruction::PHI:
   case Instruction::Br:
   case Instruction::Add:
TargetTransformInfo::getInstructionThroughput(const Instruction *I) const {
   case Instruction::ExtractElement:
   case Instruction::InsertElement:
   case Instruction::ExtractValue:
   case Instruction::ShuffleVector:
   case Instruction::Call:
     return getUserCost(I, CostKind);
   default:
     // We don't have any information on this instruction.
-    return -1;
+    return InstructionCost::getInvalid();
   }
 }
 
 TargetTransformInfo::Concept::~Concept() {}
 
 TargetIRAnalysis::TargetIRAnalysis() : TTICallback(&getDefaultTTI) {}
 
 TargetIRAnalysis::TargetIRAnalysis(

llvm/lib/Target/ARM/ARMTargetTransformInfo.cpp

for (auto &I : *BB) {
         if (const Function *F = cast<CallBase>(I).getCalledFunction()) {
           if (!isLoweredToCall(F))
             continue;
         }
         return;
       }
 
       SmallVector<const Value*, 4> Operands(I.operand_values());
-      Cost +=
+      InstructionCost UserCost =
           getUserCost(&I, Operands, TargetTransformInfo::TCK_SizeAndLatency);
+      assert(UserCost.isValid() && "Found invalid user cost");
+      Cost += *UserCost.getValue();
     }
   }
 
   LLVM_DEBUG(dbgs() << "Cost of loop: " << Cost << "\n");
 
   UP.Partial = true;
   UP.Runtime = true;
   UP.UpperBound = true;

llvm/lib/Target/Hexagon/HexagonTargetTransformInfo.h

unsigned getCFInstrCost(unsigned Opcode, TTI::TargetCostKind CostKind) {
     return 1;
   }
 
   bool isLegalMaskedStore(Type *DataType, Align Alignment);
   bool isLegalMaskedLoad(Type *DataType, Align Alignment);
 
   /// @}
 
-  int getUserCost(const User *U, ArrayRef<const Value *> Operands,
+  InstructionCost getUserCost(const User *U, ArrayRef<const Value *> Operands,
                               TTI::TargetCostKind CostKind);
 
   // Hexagon specific decision to generate a lookup table.
   bool shouldBuildLookupTables() const;
 };
 
 } // end namespace llvm
 #endif // LLVM_LIB_TARGET_HEXAGON_HEXAGONTARGETTRANSFORMINFO_H

llvm/lib/Target/Hexagon/HexagonTargetTransformInfo.cpp

 unsigned HexagonTTIImpl::getPrefetchDistance() const {
   return ST.getL1PrefetchDistance();
 }
 
 unsigned HexagonTTIImpl::getCacheLineSize() const {
   return ST.getL1CacheLineSize();
 }
 
-int
-HexagonTTIImpl::getUserCost(const User *U,
+InstructionCost HexagonTTIImpl::getUserCost(const User *U,
                                             ArrayRef<const Value *> Operands,
                                             TTI::TargetCostKind CostKind) {
   auto isCastFoldedIntoLoad = [this](const CastInst *CI) -> bool {
     if (!CI->isIntegerCast())
       return false;
     // Only extensions from an integer type shorter than 32-bit to i32
     // can be folded into the load.
     const DataLayout &DL = getDataLayout();
     unsigned SBW = DL.getTypeSizeInBits(CI->getSrcTy());
     unsigned DBW = DL.getTypeSizeInBits(CI->getDestTy());

llvm/lib/Target/PowerPC/PPCTargetTransformInfo.h

int getIntImmCost(const APInt &Imm, Type *Ty,
                     TTI::TargetCostKind CostKind);
 
   int getIntImmCostInst(unsigned Opcode, unsigned Idx, const APInt &Imm,
                         Type *Ty, TTI::TargetCostKind CostKind,
                         Instruction *Inst = nullptr);
   int getIntImmCostIntrin(Intrinsic::ID IID, unsigned Idx, const APInt &Imm,
                           Type *Ty, TTI::TargetCostKind CostKind);
 
-  unsigned getUserCost(const User *U, ArrayRef<const Value *> Operands,
+  InstructionCost getUserCost(const User *U, ArrayRef<const Value *> Operands,
                               TTI::TargetCostKind CostKind);
 
   TTI::PopcntSupportKind getPopcntSupport(unsigned TyWidth);
   bool isHardwareLoopProfitable(Loop *L, ScalarEvolution &SE,
                                 AssumptionCache &AC,
                                 TargetLibraryInfo *LibInfo,
                                 HardwareLoopInfo &HWLoopInfo);
   bool canSaveCmp(Loop *L, BranchInst **BI, ScalarEvolution *SE, LoopInfo *LI,
                   DominatorTree *DT, AssumptionCache *AC,

llvm/lib/Target/PowerPC/PPCTargetTransformInfo.cpp

if (Idx == ImmIdx && Imm.getBitWidth() <= 64) {
 
     if (ShiftedFree && (Imm.getZExtValue() & 0xFFFF) == 0)
       return TTI::TCC_Free;
   }
 
   return PPCTTIImpl::getIntImmCost(Imm, Ty, CostKind);
 }
 
-unsigned
-PPCTTIImpl::getUserCost(const User *U, ArrayRef<const Value *> Operands,
+InstructionCost PPCTTIImpl::getUserCost(const User *U,
+                                        ArrayRef<const Value *> Operands,
                                         TTI::TargetCostKind CostKind) {
   // We already implement getCastInstrCost and getMemoryOpCost where we perform
   // the vector adjustment there.
   if (isa<CastInst>(U) || isa<LoadInst>(U) || isa<StoreInst>(U))
     return BaseT::getUserCost(U, Operands, CostKind);
 
   if (U->getType()->isVectorTy()) {
     // Instructions that need to be split should cost more.
     std::pair<int, MVT> LT = TLI->getTypeLegalizationCost(DL, U->getType());

llvm/lib/Transforms/Scalar/LoopFlatten.cpp

 checkOuterLoopInsts(struct FlattenInfo &FI,
                     SmallPtrSetImpl<Instruction *> &IterationInstructions,
                     const TargetTransformInfo *TTI) {
   // Check for instructions in the outer but not inner loop. If any of these
   // have side-effects then this transformation is not legal, and if there is
   // a significant amount of code here which can't be optimised out that it's
   // not profitable (as these instructions would get executed for each
   // iteration of the inner loop).
-  unsigned RepeatedInstrCost = 0;
+  InstructionCost RepeatedInstrCost = 0;
   for (auto *B : FI.OuterLoop->getBlocks()) {
     if (FI.InnerLoop->contains(B))
       continue;
 
     for (auto &I : *B) {
       if (!isa<PHINode>(&I) && !I.isTerminator() &&
           !isSafeToSpeculativelyExecute(&I)) {
         LLVM_DEBUG(dbgs() << "Cannot flatten because instruction may have "
for (auto &I : *B) {
       if (Br && Br->isUnconditional() &&
           Br->getSuccessor(0) == FI.InnerLoop->getHeader())
         continue;
       // Multiplies of the outer iteration variable and inner iteration
       // count will be optimised out.
       if (match(&I, m_c_Mul(m_Specific(FI.OuterInductionPHI),
                             m_Specific(FI.InnerLimit))))
         continue;
-      int Cost = TTI->getUserCost(&I, TargetTransformInfo::TCK_SizeAndLatency);
+      InstructionCost Cost =
+          TTI->getUserCost(&I, TargetTransformInfo::TCK_SizeAndLatency);
       LLVM_DEBUG(dbgs() << "Cost " << Cost << ": "; I.dump());
       RepeatedInstrCost += Cost;
     }
   }
 
   LLVM_DEBUG(dbgs() << "Cost of instructions that will be repeated: "
                     << RepeatedInstrCost << "\n");
   // Bail out if flattening the loops would cause instructions in the outer
   // loop but not in the inner loop to be executed extra times.
   if (RepeatedInstrCost > RepeatedInstructionThreshold) {
     LLVM_DEBUG(dbgs() << "checkOuterLoopInsts: not profitable, bailing.\n");
     return false;
   }
 
   LLVM_DEBUG(dbgs() << "checkOuterLoopInsts: OK\n");
   return true;
 }
 

llvm/lib/Transforms/Scalar/LoopUnrollPass.cpp

static Optional<EstimatedUnrollCost> analyzeLoopUnrollCost(
 
   SmallSetVector<BasicBlock *, 16> BBWorklist;
   SmallSetVector<std::pair<BasicBlock *, BasicBlock *>, 4> ExitWorklist;
   DenseMap<Value *, Constant *> SimplifiedValues;
   SmallVector<std::pair<Value *, Constant *>, 4> SimplifiedInputValues;
 
   // The estimated cost of the unrolled form of the loop. We try to estimate
   // this by simplifying as much as we can while computing the estimate.
-  unsigned UnrolledCost = 0;
+  InstructionCost UnrolledCost = 0;
 
   // We also track the estimated dynamic (that is, actually executed) cost in
   // the rolled form. This helps identify cases when the savings from unrolling
   // aren't just exposing dead control flows, but actual reduced dynamic
   // instructions due to the simplifications which we expect to occur after
   // unrolling.
   unsigned RolledDynamicCost = 0;
 
for (unsigned Idx = 0; Idx != BBWorklist.size(); ++Idx) {
       for (Instruction &I : *BB) {
         // These won't get into the final code - don't even try calculating the
         // cost for them.
         if (isa<DbgInfoIntrinsic>(I) || EphValues.count(&I))
           continue;
 
         // Track this instruction's expected baseline cost when executing the
         // rolled loop form.
-        RolledDynamicCost += TTI.getUserCost(&I, CostKind);
+        InstructionCost InsnCost = TTI.getUserCost(&I, CostKind);
+        if (!InsnCost.isValid()) {
+          LLVM_DEBUG(dbgs() << "  Encountered invalid baseline cost.\n");
+          return None;
+        }
+        RolledDynamicCost += *InsnCost.getValue();
 
         // Visit the instruction to analyze its loop cost after unrolling,
         // and if the visitor returns true, mark the instruction as free after
         // unrolling and continue.
         bool IsFree = Analyzer.visit(I);
         bool Inserted = InstCostMap.insert({&I, (int)Iteration,
                                            (unsigned)IsFree,
                                            /*IsCounted*/ false}).second;
for (Instruction &I : *ExitBB) {
         if (L->contains(OpI))
           AddCostRecursively(*OpI, TripCount - 1);
     }
   }
 
   LLVM_DEBUG(dbgs() << "Analysis finished:\n"
                     << "UnrolledCost: " << UnrolledCost << ", "
                     << "RolledDynamicCost: " << RolledDynamicCost << "\n");
-  return {{UnrolledCost, RolledDynamicCost}};
+  return {{unsigned(*UnrolledCost.getValue()), RolledDynamicCost}};
 }
 
 /// ApproximateLoopSize - Approximate the size of the loop.
 unsigned llvm::ApproximateLoopSize(
     const Loop *L, unsigned &NumCalls, bool &NotDuplicatable, bool &Convergent,
     const TargetTransformInfo &TTI,
     const SmallPtrSetImpl<const Value *> &EphValues, unsigned BEInsns) {
   CodeMetrics Metrics;

llvm/lib/Transforms/Scalar/SimpleLoopUnswitch.cpp

static int CalculateUnswitchCostMultiplier(
   LLVM_DEBUG(dbgs() << "  Computed multiplier  " << CostMultiplier
                     << " (siblings " << SiblingsMultiplier << " * clones "
                     << (1 << ClonesPower) << ")"
                     << " for unswitch candidate: " << TI << "\n");
   return CostMultiplier;
 }
 
 static bool
 unswitchBestCondition(Loop &L, DominatorTree &DT, LoopInfo &LI,
                       AssumptionCache &AC, TargetTransformInfo &TTI,
                       function_ref<void(bool, ArrayRef<Loop *>)> UnswitchCB,
                       ScalarEvolution *SE, MemorySSAUpdater *MSSAU) {
   // Collect all invariant conditions within this loop (as opposed to an inner
   // loop which would be handled when visiting that inner loop).
   SmallVector<std::pair<Instruction *, TinyPtrVector<Value *>>, 4>
       UnswitchCandidates;
 
unswitchBestCondition(Loop &L, DominatorTree &DT, LoopInfo &LI,
   // FIXME: We might be able to safely handle some of these in non-duplicated
   // regions.
   TargetTransformInfo::TargetCostKind CostKind =
       L.getHeader()->getParent()->hasMinSize()
       ? TargetTransformInfo::TCK_CodeSize
       : TargetTransformInfo::TCK_SizeAndLatency;
   int LoopCost = 0;
   for (auto *BB : L.blocks()) {
-    int Cost = 0;
+    InstructionCost Cost = 0;
     for (auto &I : *BB) {
       if (EphValues.count(&I))
         continue;
 
       if (I.getType()->isTokenTy() && I.isUsedOutsideOfBlock(BB))
         return false;
       if (auto *CB = dyn_cast<CallBase>(&I))
         if (CB->isConvergent() || CB->cannotDuplicate())
           return false;
 
       Cost += TTI.getUserCost(&I, CostKind);
     }
-    assert(Cost >= 0 && "Must not have negative costs!");
-    LoopCost += Cost;
+    assert(Cost.isValid() && "Must have valid costs!");
+    LoopCost += *Cost.getValue();
     assert(LoopCost >= 0 && "Must not have negative loop costs!");
-    BBCostMap[BB] = Cost;
+    BBCostMap[BB] = *Cost.getValue();
   }
   LLVM_DEBUG(dbgs() << "  Total loop cost: " << LoopCost << "\n");
 
   // Now we find the best candidate by searching for the one with the following
   // properties in order:
   //
   // 1) An unswitching cost below the threshold
   // 2) The smallest number of duplicated unswitch candidates (to avoid

llvm/lib/Transforms/Scalar/SpeculateAroundPHIs.cpp

for (auto *PN : PNs) {
     for (auto *UI : UserSet)
       UserToPNMap.insert({UI, {}}).first->second.push_back(PN);
     UserSet.clear();
   }
 
   // Now do a DFS across the operand graph of the users, computing cost as we
   // go and when all costs for a given PHI are known, checking that PHI for
   // profitability.
-  SmallDenseMap<Instruction *, int, 16> SpecCostMap;
+  SmallDenseMap<Instruction *, InstructionCost, 16> SpecCostMap;
   visitPHIUsersAndDepsInPostOrder(
       PNs,
       /*IsVisited*/
       [&](Instruction *I) {
         // We consider anything that isn't potentially speculated to be
         // "visited" as it is already handled. Similarly, anything that *is*
         // potentially speculated but for which we have an entry in our cost
         // map, we're done.
         return !PotentialSpecSet.count(I) || SpecCostMap.count(I);
       },
       /*Visit*/
       [&](Instruction *I) {
         // We've fully visited the operands, so sum their cost with this node
         // and update the cost map.
-        int Cost = TTI.TCC_Free;
+        InstructionCost Cost = TTI.TCC_Free;
         for (Value *OpV : I->operand_values())
           if (auto *OpI = dyn_cast<Instruction>(OpV)) {
             auto CostMapIt = SpecCostMap.find(OpI);
             if (CostMapIt != SpecCostMap.end())
               Cost += CostMapIt->second;
           }
         Cost += TTI.getUserCost(I, TargetTransformInfo::TCK_SizeAndLatency);
         bool Inserted = SpecCostMap.insert({I, Cost}).second;
visitPHIUsersAndDepsInPostOrder(
               --PNUserCount;
               return PNUserCount != 0;
             });
 
         // FIXME: Rather than one at a time, we should sum the savings as the
         // cost will be completely shared.
         SmallVector<Instruction *, 16> SpecWorklist;
         for (auto *PN : llvm::make_range(UserPNsSplitIt, UserPNs.end())) {
-          int SpecCost = TTI.TCC_Free;
+          InstructionCost SpecCost = TTI.TCC_Free;
           for (Use &U : PN->uses())
             SpecCost +=
                 SpecCostMap.find(cast<Instruction>(U.getUser()))->second;
           SpecCost *= (NumPreds - 1);
           // When the user count of a PHI node hits zero, we should check its
           // profitability. If profitable, we should mark it for speculation
           // and zero out the cost of everything it depends on.
           int CostSavings = CostSavingsMap.find(PN)->second;
           if (SpecCost > CostSavings) {
             LLVM_DEBUG(dbgs() << "  Not profitable, speculation cost: " << *PN
                               << "\n"
                                  "    Cost savings:     "
                               << CostSavings
                               << "\n"
                                  "    Speculation cost: "
                               << SpecCost << "\n");
             continue;

llvm/lib/Transforms/Scalar/SpeculativeExecution.cpp

if (Succ1.size() == 1) // equivalent to if-then
       return considerHoistingFromTo(Succ0, B);
     if (Succ0.size() == 1) // equivalent to if-else
       return considerHoistingFromTo(Succ1, B);
   }
 
   return false;
 }
 
-static unsigned ComputeSpeculationCost(const Instruction *I,
+static InstructionCost ComputeSpeculationCost(const Instruction *I,
                                               const TargetTransformInfo &TTI) {
   switch (Operator::getOpcode(I)) {
     case Instruction::GetElementPtr:
     case Instruction::Add:
     case Instruction::Mul:
     case Instruction::And:
     case Instruction::Or:
     case Instruction::Select:
     case Instruction::Shl:
switch (Operator::getOpcode(I)) {
     case Instruction::ExtractElement:
     case Instruction::InsertElement:
     case Instruction::ShuffleVector:
     case Instruction::ExtractValue:
     case Instruction::InsertValue:
       return TTI.getUserCost(I, TargetTransformInfo::TCK_SizeAndLatency);
 
     default:
-      return UINT_MAX; // Disallow anything not explicitly listed.
+      return InstructionCost::getInvalid(); // Disallow anything not explicitly
+                                            // listed.
   }
 }
 
 bool SpeculativeExecutionPass::considerHoistingFromTo(
     BasicBlock &FromBlock, BasicBlock &ToBlock) {
   SmallPtrSet<const Instruction *, 8> NotHoisted;
   const auto AllPrecedingUsesFromBlockHoisted = [&NotHoisted](const User *U) {
     // Debug variable has special operand to check it's not hoisted.
for (const Value *V : U->operand_values()) {
       if (const Instruction *I = dyn_cast<Instruction>(V)) {
         if (NotHoisted.count(I) > 0)
           return false;
       }
     }
     return true;
   };
 
-  unsigned TotalSpeculationCost = 0;
+  InstructionCost TotalSpeculationCost = 0;
   unsigned NotHoistedInstCount = 0;
   for (const auto &I : FromBlock) {
-    const unsigned Cost = ComputeSpeculationCost(&I, *TTI);
-    if (Cost != UINT_MAX && isSafeToSpeculativelyExecute(&I) &&
+    const InstructionCost Cost = ComputeSpeculationCost(&I, *TTI);
+    if (Cost.isValid() && isSafeToSpeculativelyExecute(&I) &&
         AllPrecedingUsesFromBlockHoisted(&I)) {
       TotalSpeculationCost += Cost;
       if (TotalSpeculationCost > SpecExecMaxSpeculationCost)
         return false;  // too much to hoist
     } else {
       // Debug info instrinsics should not be counted for threshold.
       if (!isa<DbgInfoIntrinsic>(I))
         NotHoistedInstCount++;

llvm/lib/Transforms/Utils/SimplifyCFG.cpp

 /// Compute an abstract "cost" of speculating the given instruction,
 /// which is assumed to be safe to speculate. TCC_Free means cheap,
 /// TCC_Basic means less cheap, and TCC_Expensive means prohibitively
 /// expensive.
 static unsigned ComputeSpeculationCost(const User *I,
                                        const TargetTransformInfo &TTI) {
   assert(isSafeToSpeculativelyExecute(I) &&
          "Instruction is not safe to speculatively execute!");
-  return TTI.getUserCost(I, TargetTransformInfo::TCK_SizeAndLatency);
+  InstructionCost Cost =
+      TTI.getUserCost(I, TargetTransformInfo::TCK_SizeAndLatency);
+  assert(Cost.isValid() && "Unexpected invalid user cost");
+  return *Cost.getValue();
 }
 
 /// If we have a merge point of an "if condition" as accepted above,
 /// return true if the specified value dominates the block.  We
 /// don't handle the true generality of domination here, just a special case
 /// which works well enough for us.
 ///
 /// If AggressiveInsts is non-null, and if V does not dominate BB, we check to
for (auto &I : BB->instructionsWithoutDebug()) {
       if (auto *S = dyn_cast<StoreInst>(&I))
         if (llvm::find(FreeStores, S))
           continue;
       // Else, we have a white-list of instructions that we are ak speculating.
       if (!isa<BinaryOperator>(I) && !isa<GetElementPtrInst>(I))
         return false; // Not in white-list - not worthwhile folding.
       // And finally, if this is a non-free instruction that we are okay
       // speculating, ensure that we consider the speculation budget.
-      BudgetRemaining -= TTI.getUserCost(&I, TargetTransformInfo::TCK_SizeAndLatency);
+      InstructionCost UserCost =
+          TTI.getUserCost(&I, TargetTransformInfo::TCK_SizeAndLatency);
+      assert(UserCost.isValid() && "Unexpected invalid user cost");
+      BudgetRemaining -= *UserCost.getValue();
       if (BudgetRemaining < 0)
         return false; // Eagerly refuse to fold as soon as we're out of budget.
     }
     assert(BudgetRemaining >= 0 &&
            "When we run out of budget we will eagerly return from within the "
            "per-instruction loop.");
     return true;
   };