[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

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

llvm/lib/Transforms/Scalar/SimpleLoopUnswitch.cpp

2600

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

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

2600

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

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

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

179

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

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

llvm/lib/Transforms/Scalar/LoopFlatten.cpp

320

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

320

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 ↗

(On Diff #315417)

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

llvm/lib/Transforms/Scalar/LoopUnrollPass.cpp

531

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/CodeMetrics.h

 // the Inliner and other passes decide whether to duplicate its contents.
 //
 //===----------------------------------------------------------------------===//
 
 #ifndef LLVM_ANALYSIS_CODEMETRICS_H
 #define LLVM_ANALYSIS_CODEMETRICS_H
 
 #include "llvm/ADT/DenseMap.h"
+#include "llvm/Analysis/InstructionCost.h"
 
 namespace llvm {
 class AssumptionCache;
 class BasicBlock;
 class Loop;
 class Function;
 template <class T> class SmallPtrSetImpl;
 class TargetTransformInfo;
struct CodeMetrics {
 
   /// True if this function contains a call to a convergent function.
   bool convergent = false;
 
   /// True if this function calls alloca (in the C sense).
   bool usesDynamicAlloca = false;
 
   /// Number of instructions in the analyzed blocks.
-  unsigned NumInsts = false;
+  InstructionCost NumInsts = 0;
 
   /// Number of analyzed blocks.
   unsigned NumBlocks = false;
 
   /// Keeps track of basic block code size estimates.
-  DenseMap<const BasicBlock *, unsigned> NumBBInsts;
+  DenseMap<const BasicBlock *, InstructionCost> NumBBInsts;
 
   /// Keep track of the number of calls to 'big' functions.
   unsigned NumCalls = false;
 
   /// The number of calls to internal functions with a single caller.
   ///
   /// These are likely targets for future inlining, likely exposed by
   /// interleaved devirtualization.

llvm/include/llvm/Analysis/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/include/llvm/Analysis/TargetTransformInfo.h

case TCK_Latency:
       break;
     case TCK_CodeSize:
     case TCK_SizeAndLatency:
       Cost = getUserCost(I, kind);
       break;
     default:
       llvm_unreachable("Unknown instruction cost kind");
     }
-    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->value_op_begin(),
                                            U->value_op_end());
     return getUserCost(U, Operands, CostKind);
   }
 
   /// Return true if branch divergence exists.
   ///
   /// Branch divergence has a significantly negative impact on GPU performance

 
   /// @}
 
   /// @}
 
 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;
virtual bool useReductionIntrinsic(unsigned Opcode, Type *Ty,
                                      ReductionFlags) const = 0;
   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 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);
+    InstructionCost Cost = Impl.getUserCost(U, Operands, CostKind);
+    if (Cost == -1)
+      Cost.setInvalid();
+    return Cost;
   }
   bool hasBranchDivergence() override { return Impl.hasBranchDivergence(); }
   bool useGPUDivergenceAnalysis() override {
     return Impl.useGPUDivergenceAnalysis();
   }
   bool isSourceOfDivergence(const Value *V) override {
     return Impl.isSourceOfDivergence(V);
   }
public:
   unsigned getGISelRematGlobalCost() const override {
     return Impl.getGISelRematGlobalCost();
   }
 
   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/Transforms/Utils/LoopRotationUtils.h

 /// perform loop latch simplication as well if the flag RotationOnly
 /// is false. The flag Threshold represents the size threshold of the loop
 /// header. If the loop header's size exceeds the threshold, the loop rotation
 /// will give up. The flag IsUtilMode controls the heuristic used in the
 /// LoopRotation. If it is true, the profitability heuristic will be ignored.
 bool LoopRotation(Loop *L, LoopInfo *LI, const TargetTransformInfo *TTI,
                   AssumptionCache *AC, DominatorTree *DT, ScalarEvolution *SE,
                   MemorySSAUpdater *MSSAU, const SimplifyQuery &SQ,
-                  bool RotationOnly, unsigned Threshold, bool IsUtilMode);
+                  bool RotationOnly, int Threshold, bool IsUtilMode);
 
 } // namespace llvm
 
 #endif

llvm/lib/Analysis/CodeMetrics.cpp

 }
 
 /// Fill in the current structure with information gleaned from the specified
 /// block.
 void CodeMetrics::analyzeBasicBlock(const BasicBlock *BB,
                                     const TargetTransformInfo &TTI,
                                     const SmallPtrSetImpl<const Value*> &EphValues) {
   ++NumBlocks;
-  unsigned NumInstsBeforeThisBB = NumInsts;
+  InstructionCost NumInstsBeforeThisBB = NumInsts;
   for (const Instruction &I : *BB) {
     // Skip ephemeral values.
     if (EphValues.count(&I))
       continue;
 
     // Special handling for calls.
     if (const auto *Call = dyn_cast<CallBase>(&I)) {
       if (const Function *F = Call->getCalledFunction()) {
if (const InvokeInst *InvI = dyn_cast<InvokeInst>(&I))
         notDuplicatable = true;
 
     NumInsts += TTI.getUserCost(&I, TargetTransformInfo::TCK_CodeSize);
   }
 
   if (isa<ReturnInst>(BB->getTerminator()))
     ++NumRets;
 
+  notDuplicatable |= !NumInsts.isValid();
+
   // 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 {

 bool TargetTransformInfo::shouldExpandReduction(const IntrinsicInst *II) const {
   return TTIImpl->shouldExpandReduction(II);
 }
 
 unsigned TargetTransformInfo::getGISelRematGlobalCost() const {
   return TTIImpl->getGISelRematGlobalCost();
 }
 
-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/PowerPC/PPCTargetTransformInfo.cpp

bool PPCTTIImpl::isHardwareLoopProfitable(Loop *L, ScalarEvolution &SE,
   unsigned ConstTripCount = SE.getSmallConstantTripCount(L);
   if (ConstTripCount && ConstTripCount < SmallCTRLoopThreshold) {
     SmallPtrSet<const Value *, 32> EphValues;
     CodeMetrics::collectEphemeralValues(L, &AC, EphValues);
     CodeMetrics Metrics;
     for (BasicBlock *BB : L->blocks())
       Metrics.analyzeBasicBlock(BB, *this, EphValues);
     // 6 is an approximate latency for the mtctr instruction.
-    if (Metrics.NumInsts <= (6 * SchedModel.getIssueWidth()))
+    if (!Metrics.NumInsts.isValid() ||
+        Metrics.NumInsts <= (6 * SchedModel.getIssueWidth()))
       return false;
   }
 
   // We don't want to spill/restore the counter register, and so we don't
   // want to use the counter register if the loop contains calls.
   SmallPtrSet<const Value *, 4> Visited;
   for (Loop::block_iterator I = L->block_begin(), IE = L->block_end();
        I != IE; ++I)

llvm/lib/Transforms/Scalar/LoopDataPrefetch.cpp

for (auto &I : *BB) {
             HasCall = true;
         } else { // indirect call.
           HasCall = true;
         }
       }
     }
     Metrics.analyzeBasicBlock(BB, *TTI, EphValues);
   }
-  unsigned LoopSize = Metrics.NumInsts;
+  if (!Metrics.NumInsts.isValid())
+    return MadeChange;
+
+  unsigned LoopSize = *(Metrics.NumInsts.getValue());
   if (!LoopSize)
     LoopSize = 1;
 
   unsigned ItersAhead = getPrefetchDistance() / LoopSize;
   if (!ItersAhead)
     ItersAhead = 1;
 
   if (ItersAhead > getMaxPrefetchIterationsAhead())

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) {
+  if (!RepeatedInstrCost.isValid() ||
+      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;
+  InstructionCost RolledDynamicCost = 0;
 
   // We track the simplification of each instruction in each iteration. We use
   // this to recursively merge costs into the unrolled cost on-demand so that
   // we don't count the cost of any dead code. This is essentially a map from
   // <instruction, int> to <bool, bool>, but stored as a densely packed struct.
   DenseSet<UnrolledInstState, UnrolledInstStateKeyInfo> InstCostMap;
 
   // A small worklist used to accumulate cost of instructions from each
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;
 
         // 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())),
+           unsigned(*(RolledDynamicCost.getValue()))}};
 }
 
 /// 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;
   for (BasicBlock *BB : L->blocks())
     Metrics.analyzeBasicBlock(BB, TTI, EphValues);
   NumCalls = Metrics.NumInlineCandidates;
   NotDuplicatable = Metrics.notDuplicatable;
   Convergent = Metrics.convergent;
 
-  unsigned LoopSize = Metrics.NumInsts;
+  if (!Metrics.NumInsts.isValid()) {
+    NotDuplicatable = true;
+    // Similar to the code below, we shouldn't allow an estimate of zero even
+    // though we're marking the loop as not duplicatable.
+    return BEInsns + 1;
+  }
+
+  unsigned LoopSize = *(Metrics.NumInsts.getValue());
 
   // Don't allow an estimate of size zero.  This would allows unrolling of loops
   // with huge iteration counts, which is a compile time problem even if it's
   // not a problem for code quality. Also, the code using this size may assume
   // that each loop has at least three instructions (likely a conditional
   // branch, a comparison feeding that branch, and some kind of loop increment
   // feeding that comparison instruction).
   LoopSize = std::max(LoopSize, BEInsns + 1);

llvm/lib/Transforms/Scalar/LoopUnswitch.cpp

if (Inserted) {
     // FIXME: This is overly conservative because it does not take into
     // consideration code simplification opportunities and code that can
     // be shared by the resultant unswitched loops.
     CodeMetrics Metrics;
     for (Loop::block_iterator I = L->block_begin(), E = L->block_end(); I != E;
          ++I)
       Metrics.analyzeBasicBlock(*I, TTI, EphValues);
 
-    Props.SizeEstimation = Metrics.NumInsts;
+    if (auto NumInsts = Metrics.NumInsts.getValue())
+      Props.SizeEstimation = *NumInsts;
+    else
+      Props.SizeEstimation = std::numeric_limits<unsigned>::max();
     Props.CanBeUnswitchedCount = MaxSize / (Props.SizeEstimation);
     Props.WasUnswitchedCount = 0;
     MaxSize -= Props.SizeEstimation * Props.CanBeUnswitchedCount;
 
     if (Metrics.notDuplicatable) {
       LLVM_DEBUG(dbgs() << "NOT unswitching loop %" << L->getHeader()->getName()
                         << ", contents cannot be "
                         << "duplicated!\n");

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) {
+          if (!SpecCost.isValid() || 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/LoopRotationUtils.cpp

 static cl::opt<bool>
     MultiRotate("loop-rotate-multi", cl::init(false), cl::Hidden,
                 cl::desc("Allow loop rotation multiple times in order to reach "
                          "a better latch exit"));
 
 namespace {
 /// A simple loop rotation transformation.
 class LoopRotate {
-  const unsigned MaxHeaderSize;
+  const int MaxHeaderSize;
   LoopInfo *LI;
   const TargetTransformInfo *TTI;
   AssumptionCache *AC;
   DominatorTree *DT;
   ScalarEvolution *SE;
   MemorySSAUpdater *MSSAU;
   const SimplifyQuery &SQ;
   bool RotationOnly;
   bool IsUtilMode;
 
 public:
-  LoopRotate(unsigned MaxHeaderSize, LoopInfo *LI,
-             const TargetTransformInfo *TTI, AssumptionCache *AC,
-             DominatorTree *DT, ScalarEvolution *SE, MemorySSAUpdater *MSSAU,
-             const SimplifyQuery &SQ, bool RotationOnly, bool IsUtilMode)
+  LoopRotate(int MaxHeaderSize, LoopInfo *LI, const TargetTransformInfo *TTI,
+             AssumptionCache *AC, DominatorTree *DT, ScalarEvolution *SE,
+             MemorySSAUpdater *MSSAU, const SimplifyQuery &SQ,
+             bool RotationOnly, bool IsUtilMode)
       : MaxHeaderSize(MaxHeaderSize), LI(LI), TTI(TTI), AC(AC), DT(DT), SE(SE),
         MSSAU(MSSAU), SQ(SQ), RotationOnly(RotationOnly),
         IsUtilMode(IsUtilMode) {}
   bool processLoop(Loop *L);
 
 private:
   bool rotateLoop(Loop *L, bool SimplifiedLatch);
   bool simplifyLoopLatch(Loop *L);

 }
 
 
 /// The utility to convert a loop into a loop with bottom test.
 bool llvm::LoopRotation(Loop *L, LoopInfo *LI, const TargetTransformInfo *TTI,
                         AssumptionCache *AC, DominatorTree *DT,
                         ScalarEvolution *SE, MemorySSAUpdater *MSSAU,
                         const SimplifyQuery &SQ, bool RotationOnly = true,
-                        unsigned Threshold = unsigned(-1),
-                        bool IsUtilMode = true) {
+                        int Threshold = INT_MAX, bool IsUtilMode = true) {
   LoopRotate LR(Threshold, LI, TTI, AC, DT, SE, MSSAU, SQ, RotationOnly,
                 IsUtilMode);
   return LR.processLoop(L);
 }

llvm/lib/Transforms/Utils/SimplifyCFG.cpp

if (MSSAU)
     if (auto *MPhi = MSSAU->getMemorySSA()->getMemoryAccess(Succ))
       MPhi->addIncoming(MPhi->getIncomingValueForBlock(ExistPred), NewPred);
 }
 
 /// 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,
+static InstructionCost ComputeSpeculationCost(const User *I,
                                               const TargetTransformInfo &TTI) {
   assert(isSafeToSpeculativelyExecute(I) &&
          "Instruction is not safe to speculatively execute!");
   return TTI.getUserCost(I, TargetTransformInfo::TCK_SizeAndLatency);
 }
 
 /// 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
if (AggressiveInsts.count(I))
     return true;
 
   // Okay, it looks like the instruction IS in the "condition".  Check to
   // see if it's a cheap instruction to unconditionally compute, and if it
   // only uses stuff defined outside of the condition.  If so, hoist it out.
   if (!isSafeToSpeculativelyExecute(I))
     return false;
 
-  BudgetRemaining -= ComputeSpeculationCost(I, TTI);
+  InstructionCost SpecCost = ComputeSpeculationCost(I, TTI);
+  // If we cannot determine the cost then we cannot determine if we have
+  // exceeded the budget or not, so let's be conservative here.
+  if (!SpecCost.isValid())
+    BudgetRemaining = -1;
+  else
+    BudgetRemaining -= *(SpecCost.getValue());
 
   // Allow exactly one instruction to be speculated regardless of its cost
   // (as long as it is safe to do so).
   // This is intended to flatten the CFG even if the instruction is a division
   // or other expensive operation. The speculation of an expensive instruction
   // is expected to be undone in CodeGenPrepare if the speculation has not
   // enabled further IR optimizations.
   if (BudgetRemaining < 0 &&
for (PHINode &PN : EndBB->phis()) {
     ConstantExpr *OrigCE = dyn_cast<ConstantExpr>(OrigV);
     ConstantExpr *ThenCE = dyn_cast<ConstantExpr>(ThenV);
     if (!OrigCE && !ThenCE)
       continue; // Known safe and cheap.
 
     if ((ThenCE && !isSafeToSpeculativelyExecute(ThenCE)) ||
         (OrigCE && !isSafeToSpeculativelyExecute(OrigCE)))
       return false;
-    unsigned OrigCost = OrigCE ? ComputeSpeculationCost(OrigCE, TTI) : 0;
-    unsigned ThenCost = ThenCE ? ComputeSpeculationCost(ThenCE, TTI) : 0;
+    InstructionCost OrigCost = OrigCE ? ComputeSpeculationCost(OrigCE, TTI) : 0;
+    InstructionCost ThenCost = ThenCE ? ComputeSpeculationCost(ThenCE, TTI) : 0;
     unsigned MaxCost =
         2 * PHINodeFoldingThreshold * TargetTransformInfo::TCC_Basic;
-    if (OrigCost + ThenCost > MaxCost)
+    if (!OrigCost.isValid() || !ThenCost.isValid() ||
+        (OrigCost + ThenCost) > MaxCost)
       return false;
 
     // Account for the cost of an unfolded ConstantExpr which could end up
     // getting expanded into Instructions.
     // FIXME: This doesn't account for how many operations are combined in the
     // constant expression.
     ++SpeculatedInstructions;
     if (SpeculatedInstructions > 1)
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);
+      if (UserCost.isValid())
+        BudgetRemaining -= *(UserCost.getValue());
+      else
+        BudgetRemaining = -1;
       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;
   };

llvm/unittests/Transforms/Utils/LoopRotationUtilsTest.cpp

deopt.exit:
   TargetTransformInfo TTI(M->getDataLayout());
   TargetLibraryInfoImpl TLII;
   TargetLibraryInfo TLI(TLII);
   ScalarEvolution SE(*F, TLI, AC, DT, LI);
   SimplifyQuery SQ(M->getDataLayout());
 
   Loop *L = *LI.begin();
 
-  bool ret = LoopRotation(L, &LI, &TTI,
-                          &AC, &DT,
-                          &SE, nullptr,
-                          SQ, true, -1, false);
+  bool ret = LoopRotation(L, &LI, &TTI, &AC, &DT, &SE, nullptr, SQ, true,
+                          INT_MAX, false);
   EXPECT_TRUE(ret);
 }
 
 /// Checking a special case of multi-deopt exit loop that can not perform
 /// required amount of rotations due to the desired header containing
 /// non-duplicatable code.
 /// Similar to MultiDeoptExit test this one should do at least one rotation and
 /// pass no matter what loop rotation settings are.
deopt.exit:
   TargetTransformInfo TTI(M->getDataLayout());
   TargetLibraryInfoImpl TLII;
   TargetLibraryInfo TLI(TLII);
   ScalarEvolution SE(*F, TLI, AC, DT, LI);
   SimplifyQuery SQ(M->getDataLayout());
 
   Loop *L = *LI.begin();
 
-  bool ret = LoopRotation(L, &LI, &TTI,
-                          &AC, &DT,
-                          &SE, nullptr,
-                          SQ, true, -1, false);
+  bool ret = LoopRotation(L, &LI, &TTI, &AC, &DT, &SE, nullptr, SQ, true,
+                          INT_MAX, false);
   /// LoopRotation should properly report "true" as we still perform the first rotation
   /// so we do change the IR.
   EXPECT_TRUE(ret);
 }