[Support] Introduce a new InstructionCost class

[david-arm]

Summary

This is the first in a series of patches that attempts to migrate
existing cost instructions to return a new InstructionCost class
in place of a simple integer. This new class is intended to be
as light-weight and simple as possible, with a full range of
arithmetic and comparison operators that largely mirror the same
sets of operations on basic types, such as integers. The main
advantage to using an InstructionCost is that it can encode a
particular cost state in addition to a value. The initial
implementation only has two states - Normal and Invalid - but these
could be expanded over time if necessary. An invalid state can
be used to represent an unknown cost or an instruction that is
prohibitively expensive.

This patch adds the new class and changes the getInstructionCost
interface to return the new class. Other cost functions, such as
getUserCost, etc., will be migrated in future patches as I believe
this to be less disruptive. One benefit of this new class is that
it provides a way to unify many of the magic costs in the codebase
where the cost is set to a deliberately high number to prevent
optimisations taking place, e.g. vectorization. It also provides
a route to represent the extremely high, and unknown, cost of
scalarization of scalable vectors, which is not currently supported.

[ctetreau]

This is pretty much there, just a few nits and it will be good to go.

llvm/include/llvm/Analysis/InstructionCost.h

35

Since CostType is exposed through the public interface, it should be public.

NIT: prefer using to typedef

41–44

NIT: I think it'd be clearer if we just checked that the state was invalid, especially since there are currently only two enumerants for it.

[ctetreau]

Looks good to me

[sdesmalen]

llvm/include/llvm/Analysis/InstructionCost.h

65

Sorry for the late comment, I only just noticed this.

I don't think it makes sense to simply return CostType, because if the value is Invalid, then Value is garbage.
From what I can tell, the options are to either:

1. assert(isValid() && "Can't return value if it is invalid"). If the assert fails, the caller needs to be modified to check the validity of the InstructionCost before continuing its calculation.
2. Return Optional<CostType> to make it clear to the caller that the value _may_ not be valid.

Without having seen all the places that would need to use getValue, my preference would probably be 2, because it is more explicit that the Invalid state needs to be considered, whereas for 1, it may false give the impression that you can simply query the value without first checking it's validity.

Any thoughts?

[david-arm]

llvm/include/llvm/Analysis/InstructionCost.h

65

My personal preference would be for an assert, since I kind of thought the design was always that users should only call getValue() after checking for validity anyway. However, I didn't document this above getValue(), which I should do regardless of which choice we make. My concern with returning Optional is that users may be confused about how they are supposed to check for validity and we'll see people doing this:

if (Cost.getValue() != None)

BudgetRemaining -= *Cost.getValue()

instead of using the state-checking interfaces that we provided, i.e.

if (Cost.isValid())

BudgetRemaining -= Cost.getValue();

[sdesmalen]

llvm/include/llvm/Analysis/InstructionCost.h

65

The issue is that people won't necessarily read the documentation, so making it part of the interface seems like the better choice.

Also, at the moment CostState only has two states. If there is ever the need to add IsUnknown, then both Unknown and Invalid would not return a value, meaning that isInvalid and Optional<>::None would no longer be equivalent.

You could probably write the example above as:

if (auto C = Cost.getValue())
  BudgetRemaining -= *C;

[ctetreau]

llvm/include/llvm/Analysis/InstructionCost.h

65

I think an assert is fine. This InstructionCost is basically isomorphic to Optional<CostType> anyways, so requiring the user to convert to Optional, then get the maybe-value is a redundant conversion IMO.

[ctetreau]

I'm likely to be out of the office most of this week, so once the assert is in, feel free to merge without waiting for my approval (assuming Sander is satisfied)

[ctetreau]

I suppose I'm fine with Optional<CostType> for the purpose of future-proofing. Users should be doing arithmetic on InstructionCost anyways, so there shouldn't be a ton of conversions. Maybe we can just provide operator* instead of making the user write *(C.getCost()).

[david-arm]

In D91174#2411632, @ctetreau wrote:

I'm likely to be out of the office most of this week, so once the assert is in, feel free to merge without waiting for my approval (assuming Sander is satisfied)

Hi @ctetreau thanks for the quick reply! I think you marked the patch as "Request changes" - does that mean if I make changes and you're out of office we can't merge the patch? Just not sure how it works if @sdesmalen accepts while you're still blocking?

[david-arm]

llvm/include/llvm/Analysis/InstructionCost.h

65

I'm happy to go with the Optional route, but the class does already provide an interface that is future-proof, i.e. @vkmr requested I add the "isValid()" interface, which serves the identical purpose, i.e.

if (Cost.isValid())

BudgetRemaining -= *(Cost.getValue())

I personally prefer users querying the state, but I guess that's personal preference. I agree having the Optional value forces callers to think about validity.

[david-arm]

• Changed getValue() to return an Optional<CostType>

[ctetreau]

I marked it "needs changes" to rescind my acceptance due to Sander's issue. However, I'm fine with this (aside from the test I requested), so feel free to merge it once the test is added and Sander is satisfied.

llvm/unittests/Analysis/InstructionCostTest.cpp

23

please add a test that a valid cost returns a value, and an invalid cost retruns a none.

[ctetreau]

I don't know if having that red x next to my name causes phabricator to be difficult. If so, I apologize.

[ctetreau]

I'll go ahead an approve the patch for now to clear the "red x" next to my name. Please add the test before merging though.

[david-arm]

• Added tests for value extraction.

[sdesmalen]

Thanks for the changes. The patch looks good to me now.

llvm/include/llvm/Analysis/InstructionCost.h

65

Thanks for adding the interface. You're right that at the moment there are two ways to query the same thing, but they are conceptually different. Otherwise, CostState would have been a bool instead of an enum and we could remove the isValid in favour of having getValue return an Optional. This allows for adding new states in the future without necessarily changing the places where InstructionCost is used.

llvm/lib/Analysis/CostModel.cpp

107

nit: Cost.isValid() ?

Or now that you've added Optional, you can write:

if (Optional<int> Cost = TTI->getInstructionCost(&Inst, CostKind))
  OS << "Cost Model: Found an estimated cost of " << *Cost;
else
  OS << "Cost Model: Unknown cost";

[fhahn]

llvm/include/llvm/Analysis/InstructionCost.h

65

It seems like the comment of this function needs to be updated now, because the current version still mentions the user can/should use the isValid interface?

I think for readers it would be good to describe what this function returns and when it returns none. And then follow with the notes about using it sparingly.

Thanks for adding the interface. You're right that at the moment there are two ways to query the same thing, but they are conceptually different. Otherwise, CostState would have been a bool instead of an enum and we could remove the isValid in favour of having getValue return an Optional

Is the plan for getValue to return anything for any of the new states or will it only ever return the value for Valid states?

67

Is there a reason this function comment and others isn't a doxygen comment? (///) I am not sure if the comments will be used for the auto-generated docs with just //.

[sdesmalen]

llvm/include/llvm/Analysis/InstructionCost.h

65

Is the plan for getValue to return anything for any of the new states or will it only ever return the value for Valid states?

The latter. The other possible state I can think of is 'Unknown', which would be similar to Invalid in that it doesn't have an actual value. It may be that Invalid can be used to represent it, and that distinguishing this state will never be necessary, but this implementation leaves that possibility open.

[fhahn]

llvm/include/llvm/Analysis/InstructionCost.h

65

The latter. The other possible state I can think of is 'Unknown', which would be similar to Invalid in that it doesn't have an actual value. It may be that Invalid can be used to represent it, and that distinguishing this state will never be necessary, but this implementation leaves that possibility open.

Ok thanks, that makes sense! I just had another though about returning Optional. If getValue only ever returns not-none when the state is valid, then is the Optional needed? Couldn't we get the same thing by checking isValid in the caller, rather than in getState and have assert(isValid()) in getState?

if (S.isValid())
  Foo += S.getState();

[sdesmalen]

llvm/include/llvm/Analysis/InstructionCost.h

65

[Assuming you mean s/getState/getValue/ ?]

If you read back the previous comments, you'll see that this was discussed.

The reason for Optional is because calling getValue might otherwise assert. This is not directly obvious when using this class, the only way to know that getValue() might assert is by reading the documentation of InstructionCost and getValue. By making that part of the interface, the caller will know it has to cope with the possibility of the value not being known, and modify the code accordingly.

Perhaps the isValid and isInvalid methods are only creating unnecessary confusion, and perhaps we should remove those in favour of some getCostState() function that returns the enum value, so that the user can check why the value is not known (Invalid or Unknown or ...).

[david-arm]

I think the main reason for having isValid (or something like that) was because it sometimes made control flow easier and there are places in the codebase today where all we want to do is assert that something is valid. I guess the alternative to calling isValid is something like:

assert(Cost.getValue().hasValue() && "Cost is invalid!");
return Cost;

or if we had a new getCostState() it would look like:

assert(Cost.getCostState() == InstructionCost::Valid && "Cost is invalid!");
return Cost;

which does work, but feels a bit less user-friendly. However, I do think that perhaps getting rid of isInvalid might make sense and introducing a getCostState() function. Perhaps I've missed something - any thoughts?

[david-arm]

OK, so it is possible to check for validity just using getValue() by writing code such as:

assert(Cost.getValue() && "Cost is invalid");
return Cost;

but, and perhaps this is just me, I find it a bit confusing as at first glance reading such code it seems like we're comparing a value with 0. I personally prefer using isValid() as a readable way of writing such code, but as a second option we could add a boolean operator, i.e.

assert(Cost && "Cost is invalid");
return Cost;

in a similar way to how other classes have done this.

[david-arm]

• Removed isInvalid() in favour of getState() that is more future-proof.
• Converted comments to use three slashes!

[nhaehnle]

(comparison being a total ordering)
/// This avoids having to add asserts the comparison operators that the states
/// are valid and users can test for validity of the cost explicitly.

Counterpoint: The asserts cost nothing in a release build, and for software maintainability, having the asserts once in the comparison operator is better than having them at every callsite. Users of this class will forget to put them there.

Worse, users may end up relying on the total ordering behavior, which seems like a bad idea to me: what does comparing 5 to Invalid mean? It might be tempting for users to use Invalid as a stand-in for Infinite (as suggested on llvm-dev), but Invalid does not behave arithmetically like one would except Infinite to behave. (For example, I would expect int(0) * InstructionCost(Infinite) == InstructionCost(0).)

llvm/include/llvm/Analysis/InstructionCost.h

29

I'd argue that this should be unsigned. Are there places where instructions have negative costs?

225–237

Dimensional analysis suggests that this particular overload of operator* should not exist. Instead, we should have (unsigned, InstructionCost) and (InstructionCost, unsigned) overloads. By dimensional analysis I mean that we should think of InstructionCost as having an implicit unit, such as ns or nJ or whatever. Multiplying two InstructionCosts would give us square seconds or square joules, which is nonsensical.

Similarly, the return type of this particular overload of operator/ should just be unsigned.

Similar logic applies for the assignment operators.

[david-arm]

llvm/include/llvm/Analysis/InstructionCost.h

29

I think in some places in the codebase there are comments saying that they explicitly chose signed integers for costs because they had complex arithmetic where the cost could go negative and I felt it wasn't quite right to restrict the type to being unsigned. Examples of where the signedness matters are transforms/optimisations where they have a budgeted cost and they decrement this budget by individual instruction costs to the point where the budget goes negative. At this point the optimisation bails out. When I wrote this class I thought that having signed integers for a cost type would help to avoid rewriting such algorithms to use unsigned budgets. Examples of such cases can be found in:

lib/Transforms/Utils/ScalarEvolutionExpander.cpp
lib/Transforms/Utils/SimplifyCFG.cpp

I guess it's also worth mentioning that this new InstructionCost is not intended to be fixed down in this patch. I imagine it's a process of evolution and over time as we use the InstructionCost class more to migrate more of the codebase we'll get a better feeling for what's needed and improve it as we go along.

[sdesmalen]

In D91174#2417172, @nhaehnle wrote:

(comparison being a total ordering)
/// This avoids having to add asserts the comparison operators that the states
/// are valid and users can test for validity of the cost explicitly.

Counterpoint: The asserts cost nothing in a release build, and for software maintainability, having the asserts once in the comparison operator is better than having them at every callsite. Users of this class will forget to put them there.

Worse, users may end up relying on the total ordering behavior, which seems like a bad idea to me: what does comparing 5 to Invalid mean? It might be tempting for users to use Invalid as a stand-in for Infinite (as suggested on llvm-dev), but Invalid does not behave arithmetically like one would except Infinite to behave. (For example, I would expect int(0) * InstructionCost(Infinite) == InstructionCost(0).)

For TypeSize we came across a similar issue, where we eventually decided to remove the overloaded comparison operators altogether.

Having an assert in TypeSize::operator< that verifies the scalable flag of two TypeSize objects matches might cause a crash in an assert-build. And because this is used for total orderings in sets/maps, we were concerned this would lead to spurious failures, especially because most LLVM code is still written with fixed width vectors in mind. Instead, we settled on using named methods if the operators were not mathematically correct, e.g. isKnownLT, isKnownGT. This function does what it says on the box, returns whether it knows that one object is less than (or greater then) the other. If it cannot determine it, it returns false.

For InstructionCost, we can take a similar approach:

• Remove all overloaded comparison operators [1]
• Add two new interfaces: CostType getValueOr(CostType Other) and CostType getValueOrMax() so that it can be left to the users of this code to interpret the 'Invalid' state and substitute it with a desired value for the comparison, e.g. X.getValueOrMax() < Y.getValueOrMax()

[1] we could possibly opt to keep only operator< for total ordering used in maps/sets, and document its behaviour as using getValueOrMax.

[david-arm]

llvm/include/llvm/Analysis/InstructionCost.h

225–237

Fundamentally the InstructionCost is really just a wrapper for an integer with an additional state attached. We're multiplying two integers, i.e. just the same as builtin operator*(int,int). The only difference between a traditional integer operator* and the InstructionCost variant is that we are propagating a state - see the propagateState() function.

We also tried to avoid complexities of modelling it too much like an FP value by talking about 'infinity' (which leads to the question as to what 0 * Infinity means). Instead, this class is more simple and pragmatic, which turns out to be sufficient for all uses of this class. If one of the values in an expression is Invalid, the resulting expression is Invalid as well.

[paulwalker-arm]

I agree with @david-arm because this unsigned->class conversion has a different rational than TypeSize. Here we want to have the ability to allow natural maths when computing a cost but also be able to reflect the state where the cost is special, one example of which is "the cost is meaningless", rather than trying to second guess the callers intention and say "just returning a big number in the hope the user does what we need".

When it comes to comparisons, you're asking the question for a reason so whilst we can and probably should ensure that the unnatural states have an order (presumably sitting at the end of the "return a high number" range) it's my believe that performing such comparisons without ever querying the cost's status (which could just be an assert in some cases) is likely a source of error.

I also wonder how much of the interface is here temporarily for pragmatic reasons. operator*=(InstructionCount&) is a good example of this. Is there a real use case for such an interface or is it just a temporary measure until uses can be refactored at which point it can be removed.

[david-arm]

• Fixed shared library build issue due to InstructionCost::print living in llvm/lib/Analysis. I've moved this to a new file - llvm/lib/Support/InstructionCost.cpp - which resolves dependency issues.

[ctetreau]

I personally feel very strongly that we should define a total ordering here as is currently being done. @nhaehnle says that this behaves like nan, and that this is bad, and that it runs the risk of users relying on this total ordering. I disagree with all three of these concerns.

1. It behaves like nan - This is false because we have a documented total ordering, and floats only have a partial ordering with respect to nan.

float a = [something that returns nan];
float b = [something that returns a different nan];

// ignoring epsilon issues for the purposes of demonstration

if (a < b) {
  // unreachable
} else if (a > b) {
  // also unreachable
} else if (a == b) {
  // also unreachable
} else if (a != b) {
  // also unreachable
} else {
  llvm_unreachable("we shouldn't be able to get here, but we do");
}

auto a = InstructionCost::getInvalid(1);
auto b = InstructionCost::getInvalid(2);

if (a < b) {
  // we will always hit this branch
} else if (a > b) {
  // also unreachable
} else if (a == b) {
  // also unreachable
} else if (a != b) {
  // also unreachable
} else {
  llvm_unreachable("actually unreachable");
}

2. "behaving like nan" is undesirable - Float with nan and this InstructionCost are basically the same as llvm::Optional<float or InstructionCost>. Unfortunately, working with optionals in C++ is kind of annoying due to a lack of nice language features like pattern matching or anything resembling do blocks in Haskell. To work around this, we add arithmetic operators and relations that let the user just treat two InstructionCost objects as plain numbers. The user will be forced to handle the invalid case when they call getValue(), so there's no risk of "NaN getting in your matrix and causing the screen to go black."

3. having a total ordering runs the risk of users accidentally relying on it - This isn't a "risk", it's a feature. I requested a huge comment describing how the total ordering works, this makes it a guarantee provided by the class that it will continue to work this way. Unit tests have been added to ensure that it works this way. It is explicitly intended that users will use it this way.

To address some other issues raised in the thread:

• InstructionCost's relations don't behave correctly with respect to infinities. While this is true, I don't think that this is an issue. An invalid cost is not an "infinite cost". If you think about what an "infinite cost" even means, it means "a thing that is always the most costly thing to do". Why would you want such a thing? As mentioned in the commit message, it's typically used to prevent some optimization from happening. The hope is that if you assign a cost that's high enough, the system will never choose to do this thing. Really, the user isn't doing math with infinity, they are trying to set a cost to invalid. Additionally, this thing is basically a pair of bool and int. int doesn't actually have an inifinity, it has INT_MAX, and int doesn't have correct arithmetic with respect to "infinity". If we want to change the arithmetic operators to detect integer overflow, and to saturate at INT_MIN and INT_MAX, I would be ok with that. InstructionCost(INT_MAX) + InstructionCost(INT_MAX) == InstructionCost(INT_MAX) // true. I think this is reasonable but it also needs to be documented.

• @sdesmalen mentioned similar issues encountered in TypeSize. I don't think this is really the same sort of scenario. TypeSize represents a polynomial, but InstructionCost is basically just a scalar value. We want to provide the usual arithmetic operators and relations, and there exists a sensible total ordering. TypeSize does not have a sensible total ordering because it contains an unknown variable.

[ctetreau]

llvm/include/llvm/Analysis/InstructionCost.h

58

Feature request: Please add ctors and getters such that you can implicitly convert from various numeric types and Optionals. See D92178 for motivation for this. Locally, I added:

template <typename ConvertsToCostTypeT>
InstructionCost(const ConvertsToCostTypeT& Val) : Value(Val), State(Valid) {}

template <typename ConvertsToCostTypeT>
InstructionCost(const Optional<ConvertsToCostTypeT>& Val) {
  if (Val) {
    Value = *Val;
    State = Valid;
  }
  else
    State = Invalid;
}

static InstructionCost getInvalid() {
  return getInvalid(0);
}

template <typename ConvertsToCostTypeT>
static InstructionCost getInvalid(const ConvertsToCostTypeT& Val) {
  InstructionCost Tmp(Val);
  Tmp.setInvalid();
  return Tmp;
}

[david-arm]

llvm/include/llvm/Analysis/InstructionCost.h

58

I think this request seems sensible to me, although this code does fail debug builds for me due to ambiguous operator<< overloads. I think I can work around this with an explicit getter, i.e.

template <typename T>
InstructionCost getValid(const T &Val) { ... }

[ctetreau]

llvm/include/llvm/Analysis/InstructionCost.h

58

Only make this change if it's easy and doesn't negatively impact the ergonomics of using the class. Alternatively, you could add constructors for float and/or double instead of having the templated constructors.

I think the combinatorial explosion of having ctors for int, float, Optional<int>, Optional<float> probably wouldn't be too bad.

[david-arm]

Hi all, thanks everyone for all the reviews so far! I hope I've addressed everyone's comments with either code changes or giving clear enough reasons for the motivation behind certain aspects of the new class. Given it's been accepted by two people, @ctetreau and @sdesmalen, I'd like to merge the patch this week if that's ok? I'll wait until Friday to merge in case there are any strong objections.

llvm/include/llvm/Analysis/InstructionCost.h

58

Hi @ctetreau, I think it's simpler if I leave the patch as it is now if that's ok? I just thought that if we want to add new constructors then perhaps it's best to do it as part of the vectoriser work, where we move to using InstructionCost. It makes it a bit more obvious then why we're doing it.

[david-arm]

• Fixed a build issue whilst rebasing.
• Moved InstructionCost.h from Analysis to Support inline with the .cpp file. The original reason for moving was to satisfy the various dependencies between shared libraries.

[david-arm]

• Fixed typo in InstructionCost.h - replaced LLVM_ANALYSIS_INSTRUCTIONCOST_H with LLVM_SUPPORT_INSTRUCTIONCOST_H

[ctetreau]

I think this is pretty much fine. Please add the increment and decrement tests and this looks good to me.

llvm/unittests/Support/InstructionCostTest.cpp

40 ↗

(On Diff #310216)

should add tests for the increments and decrements. Would also confirm or deny my issue with the postfix increments.

[david-arm]

• Added increment and decrement operator tests.

[david-arm]

llvm/unittests/Support/InstructionCostTest.cpp

40 ↗

(On Diff #310216)

I added new increment, decrement tests below and they seem to work. Thanks!

[RKSimon]

llvm/include/llvm/Analysis/TargetTransformInfo.h

24

clang-format this (sorting)

llvm/include/llvm/IR/DiagnosticInfo.h

41

(sorting)

llvm/lib/IR/DiagnosticInfo.cpp

19

(sorting)

llvm/lib/Transforms/Vectorize/LoopVectorize.cpp

7167 ↗

(On Diff #310454)

Is it a good idea to always "dereference" optionals like this?

[ctetreau]

llvm/lib/Transforms/Vectorize/LoopVectorize.cpp

7167 ↗

(On Diff #310454)

In principle, "no". However, my assumption is that this function will eventually be changed to return InstructionCost. For now, all we can do is assert that it's valid.

a nice assert would be nice, but Optional::operator* does assert that there's a value, so a debugger will break in a useful location if this code ever tries to unwrap a none

llvm/unittests/Support/InstructionCostTest.cpp

49 ↗

(On Diff #310454)

The next line should be EXPECT_EQ(VThree, 5);, and vice versa for the postfix decrement. As it stands, somebody could break the behavior that postfix increment and decrement actually modify the value and these tests would still pass.

[ctetreau]

llvm/lib/Transforms/Vectorize/LoopVectorize.cpp

7167 ↗

(On Diff #310454)

I suppose maybe we ought to be setting a good example with the introduction of this new type. If it always unconditionally dereferences the Optional from day one, monkey-see-monkey-do will ensure that this is done everywhere.

I think adding an actual assert, optionally a FIXME would be good enough.

[david-arm]

llvm/lib/Transforms/Vectorize/LoopVectorize.cpp

7167 ↗

(On Diff #310454)

Hi @RKSimon, yeah I already have another patch (D92178) that changes this function to return a InstructionCost class so this dereference will disappear. That patch needs a bit more work after review comments and also needs rebasing to pick this up. However, sure for now I can add an assert if that helps! It's kind of like swings and roundabouts - checking in lots of smaller patches to migrate to using InstructionCost makes it easier for reviewers and easier to pin point any potential post-commit build failures. However, as a consequence it also means that interim measures like the dereference are needed sometimes.

[david-arm]

• Fixed sorting issues with InstructionCost header + class declaration.
• Added assert that ExtractValue cost is valid in LoopVectorize.cpp.
• Added additional tests to InstructionCostTests.cpp

[ctetreau]

Please add the asserts in SLPVectorizer, and then this looks good to me.

llvm/lib/Transforms/Vectorize/SLPVectorizer.cpp

3749–3760

NIT: If we're adding an assert in LoopVectorize, then these three getValues should also get asserts.

[RKSimon]

LGTM - cheers

llvm/include/llvm/Analysis/InstructionCost.h

+//===- InstructionCost.h ----------------------------------------*- C++ -*-===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+/// \file
+/// This file defines an InstructionCost class that is used when calculating
+/// the cost of an instruction, or a group of instructions. In addition to a
+/// numeric value representing the cost the class also contains a state that
+/// can be used to encode particular properties, i.e. a cost being invalid or
+/// unknown.
+///
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_ANALYSIS_INSTRUCTIONCOST_H
+#define LLVM_ANALYSIS_INSTRUCTIONCOST_H
+
+#include "llvm/Support/raw_ostream.h"
+
+namespace llvm {
+
+template <typename T>
+class GenericCost {
+private:
+
+  // These states can currently be used to indicate whether a cost is valid or
+  // invalid. Examples of an invalid cost might be where the cost is
+  // prohibitively expensive and the user wants to prevent certain
+  // optimizations being performed. Or perhaps the cost is simply unknown
+  // because the operation makes no sense in certain circumstances. These states
+  // can be expanded in future to support other cases if necessary.
+  typedef enum {
+    Normal = 0,
+    Invalid
+  } CostState;
+
+private:
+
+  T Value;
+  CostState State;
+
+public:
+
+  GenericCost() = default;
+
+  GenericCost(T Val) :
+    Value(Val), State(Normal) {}
+
+  static GenericCost getInvalid(T Val = 0) {
+    GenericCost Tmp(Val);
+    Tmp.setInvalid();
+    return Tmp;
+  }
+
+  bool isInvalid() const { return State == Invalid; }
+
+  void setInvalid() { State = Invalid; }
+
+  // This function is intended to be used as sparingly as possible, since the
+  // class provides the full range of operator support required for arithmetic
+  // and comparisons.
+  T getValue() const {
+    return Value;
+  }
+
+  // There are cases where it is necessary to convert an integer cost to a
+  // another cost type, for example the vectorizer does cost analysis using
+  // floating point values.
+  template <typename T2>
+  void convertTo(GenericCost<T2> &Other) const {
+    Other.Value = T2(Value);
+    Other.State = State;
+  }
+
+  // For all of the arithmetic operators provided here any non-normal state is
+  // perpetuated and cannot be removed. Once a cost becomes invalid it stays
+  // invalid, and it also inherits any invalid state from the RHS. Regardless
+  // of the state, arithmetic and comparisons work on the actual values in the
+  // same way as they would on a basic type, such as integer.
+
+  GenericCost &operator+=(const GenericCost &RHS) {
+    if (RHS.isInvalid())
+      setInvalid();
+    Value += RHS.Value;
+    return *this;
+  }
+
+  template <typename RT>
+  GenericCost &operator+=(const RT RHS) {
+    GenericCost<T> RHS2(RHS);
+    *this += RHS2;
+    return *this;
+  }
+
+  GenericCost &operator-=(const GenericCost &RHS) {
+    if (RHS.isInvalid())
+      setInvalid();
+    Value -= RHS.Value;
+    return *this;
+  }
+
+  template <typename RT>
+  GenericCost &operator-=(const RT RHS) {
+    GenericCost<T> RHS2(RHS);
+    *this -= RHS2;
+    return *this;
+  }
+
+  GenericCost &operator*=(const GenericCost &RHS) {
+    if (RHS.isInvalid())
+      setInvalid();
+    Value *= RHS.Value;
+    return *this;
+  }
+
+  GenericCost &operator*=(const T RHS) {
+    GenericCost<T> RHS2(RHS);
+    *this *= RHS2;
+    return *this;
+  }
+
+  GenericCost &operator/=(const GenericCost &RHS) {
+    if (RHS.isInvalid())
+      setInvalid();
+    Value /= RHS.Value;
+    return *this;
+  }
+
+  GenericCost &operator/=(const T RHS) {
+    GenericCost<T> RHS2(RHS);
+    *this /= RHS2;
+    return *this;
+  }
+
+  GenericCost &operator++() {
+    *this += 1;
+    return *this;
+  }
+
+  GenericCost operator++(int) {
+    GenericCost Copy = *this;
+    ++*this;
+    return Copy;
+  }
+
+  GenericCost &operator--() {
+    *this -= 1;
+    return *this;
+  }
+
+  GenericCost operator--(int) {
+    GenericCost Copy = *this;
+    --*this;
+    return Copy;
+  }
+
+  bool operator==(const GenericCost &RHS) const {
+    return Value == RHS.Value;
+  }
+
+  bool operator==(const T RHS) const {
+    return Value == RHS;
+  }
+
+  bool operator!=(const GenericCost &RHS) const {
+    return !(*this == RHS);
+  }
+
+  bool operator!=(const T RHS) const {
+    return !(*this == RHS);
+  }
+
+  bool operator<(const GenericCost &RHS) const {
+    return Value < RHS.Value;
+  }
+
+  bool operator>(const GenericCost &RHS) const {
+    return RHS < *this;
+  }
+
+  bool operator<=(const GenericCost &RHS) const {
+    return !(RHS < *this);
+  }
+
+  bool operator>=(const GenericCost &RHS) const {
+    return !(*this < RHS);
+  }
+
+  bool operator<(const T RHS) const {
+    return Value < RHS;
+  }
+
+  bool operator<=(const T RHS) const {
+    return Value <= RHS;
+  }
+
+  bool operator>(const T RHS) const {
+    return Value > RHS;
+  }
+
+  bool operator>=(const T RHS) const {
+    return Value >= RHS;
+  }
+
+  static GenericCost min(GenericCost LHS, GenericCost RHS) {
+    return LHS.Value < RHS.Value ? LHS : RHS;
+  }
+
+  static GenericCost max(GenericCost LHS, GenericCost RHS) {
+    return LHS.Value > RHS.Value ? LHS : RHS;
+  }
+
+  void print(raw_ostream &OS) const {
+    if (isInvalid())
+      OS << "Invalid";
+    else
+      OS << Value;
+  }
+};
+
+template <typename LT, typename RT>
+inline bool operator==(const LT LHS, const GenericCost<RT> &RHS) {
+  return RHS == LHS;
+}
+
+template <typename LT, typename RT>
+inline bool operator!=(const LT LHS, const GenericCost<RT> &RHS) {
+  return RHS != LHS;
+}
+
+template <typename T>
+inline GenericCost<T> operator+(const GenericCost<T> &LHS, const GenericCost<T> &RHS) {
+  GenericCost<T> LHS2(LHS);
+  LHS2 += RHS;
+  return LHS2;
+}
+
+template <typename T>
+inline GenericCost<T> operator-(const GenericCost<T> &LHS, const GenericCost<T> &RHS) {
+  GenericCost<T> LHS2(LHS);
+  LHS2 -= RHS;
+  return LHS2;
+}
+
+template <typename T>
+inline GenericCost<T> operator*(const GenericCost<T> &LHS, const GenericCost<T> &RHS) {
+  GenericCost<T> LHS2(LHS);
+  LHS2 *= RHS;
+  return LHS2;
+}
+
+template <typename T>
+inline GenericCost<T> operator/(const GenericCost<T> &LHS, const GenericCost<T> &RHS) {
+  GenericCost<T> LHS2(LHS);
+  LHS2 /= RHS;
+  return LHS2;
+}
+
+template <typename LT, typename RT>
+inline GenericCost<LT> operator+(const GenericCost<LT> &LHS, const RT RHS) {
+  GenericCost<LT> RHS2(RHS);
+  return LHS + RHS2;
+}
+
+template <typename LT, typename RT>
+inline GenericCost<LT> operator-(const GenericCost<LT> &LHS, const RT RHS) {
+  GenericCost<LT> RHS2(RHS);
+  return LHS - RHS2;
+}
+
+template <typename LT, typename RT>
+inline GenericCost<LT> operator*(const GenericCost<LT> &LHS, const RT RHS) {
+  GenericCost<LT> RHS2(RHS);
+  return LHS * RHS2;
+}
+
+template <typename LT, typename RT>
+inline GenericCost<LT> operator/(const GenericCost<LT> &LHS, const RT RHS) {
+  GenericCost<LT> RHS2(RHS);
+  return LHS / RHS2;
+}
+
+template <typename LT, typename RT>
+inline GenericCost<RT> operator+(const LT LHS, const GenericCost<RT> &RHS) {
+  GenericCost<RT> LHS2(LHS);
+  return LHS2 + RHS;
+}
+
+template <typename LT, typename RT>
+inline GenericCost<RT> operator-(const LT LHS, const GenericCost<RT> &RHS) {
+  GenericCost<RT> LHS2(LHS);
+  return LHS2 - RHS;
+}
+
+template <typename LT, typename RT>
+inline GenericCost<RT> operator*(const LT LHS, const GenericCost<RT> &RHS) {
+  GenericCost<RT> LHS2(LHS);
+  return LHS2 * RHS;
+}
+
+template <typename LT, typename RT>
+inline GenericCost<RT> operator/(const LT LHS, const GenericCost<RT> &RHS) {
+  GenericCost<RT> LHS2(LHS);
+  return LHS2 / RHS;
+}
+
+template <typename T>
+inline raw_ostream &operator<<(raw_ostream &OS, const GenericCost<T> &V) {
+  V.print(OS);
+  return OS;
+}
+
+using InstructionCost = GenericCost<int>;
+
+} // namespace llvm
+
+#endif

llvm/include/llvm/Analysis/TargetTransformInfo.h

 /// This file defines #2, which is the interface that IR-level transformations
 /// use for querying the codegen.
 ///
 //===----------------------------------------------------------------------===//
 
 #ifndef LLVM_ANALYSIS_TARGETTRANSFORMINFO_H
 #define LLVM_ANALYSIS_TARGETTRANSFORMINFO_H
 
+#include "llvm/Analysis/InstructionCost.h"
 #include "llvm/IR/InstrTypes.h"
 #include "llvm/IR/Operator.h"
 #include "llvm/IR/PassManager.h"
 #include "llvm/Pass.h"
 #include "llvm/Support/AtomicOrdering.h"
 #include "llvm/Support/DataTypes.h"
 #include <functional>
 
public:
 
   /// Query the cost of a specified instruction.
   ///
   /// Clients should use this interface to query the cost of an existing
   /// instruction. The instruction must have a valid parent (basic block).
   ///
   /// Note, this method does not cache the cost calculation and it
   /// can be expensive in some cases.
-  int getInstructionCost(const Instruction *I, enum TargetCostKind kind) const {
+  InstructionCost getInstructionCost(const Instruction *I,
+                                     enum TargetCostKind kind) const {
+    InstructionCost Cost;
     switch (kind) {
     case TCK_RecipThroughput:
-      return getInstructionThroughput(I);
-
+      Cost = getInstructionThroughput(I);
+      break;
     case TCK_Latency:
-      return getInstructionLatency(I);
-
+      Cost = getInstructionLatency(I);
+      break;
     case TCK_CodeSize:
     case TCK_SizeAndLatency:
-      return getUserCost(I, kind);
-    }
+      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
   /// enumeration because it is expected that the cost of one IR instruction
   /// may have a multiplicative factor to it or otherwise won't fit directly

llvm/include/llvm/IR/DiagnosticInfo.h

 
 // Forward declarations.
 class DiagnosticPrinter;
 class Function;
 class Instruction;
 class LLVMContext;
 class Module;
 class SMDiagnostic;
+template <typename T> class GenericCost;
+using InstructionCost = GenericCost<int>;
 
 /// Defines the different supported severity of a diagnostic.
 enum DiagnosticSeverity : char {
   DS_Error,
   DS_Warning,
   DS_Remark,
   // A note attaches additional information to one of the previous diagnostic
   // types.
struct Argument {
     Argument(StringRef Key, long N);
     Argument(StringRef Key, long long N);
     Argument(StringRef Key, unsigned N);
     Argument(StringRef Key, unsigned long N);
     Argument(StringRef Key, unsigned long long N);
     Argument(StringRef Key, ElementCount EC);
     Argument(StringRef Key, bool B) : Key(Key), Val(B ? "true" : "false") {}
     Argument(StringRef Key, DebugLoc dl);
+    Argument(StringRef Key, InstructionCost C);
   };
 
   /// \p PassName is the name of the pass emitting this diagnostic. \p
   /// RemarkName is a textual identifier for the remark (single-word,
   /// camel-case). \p Fn is the function where the diagnostic is being emitted.
   /// \p Loc is the location information to use in the diagnostic. If line table
   /// information is available, the diagnostic will include the source code
   /// location.

llvm/lib/Analysis/CostModel.cpp

CostModelAnalysis() : FunctionPass(ID), F(nullptr), TTI(nullptr) {
       initializeCostModelAnalysisPass(
         *PassRegistry::getPassRegistry());
     }
 
     /// Returns the expected cost of the instruction.
     /// Returns -1 if the cost is unknown.
     /// Note, this method does not cache the cost calculation and it
     /// can be expensive in some cases.
-    unsigned getInstructionCost(const Instruction *I) const {
+    InstructionCost getInstructionCost(const Instruction *I) const {
       return TTI->getInstructionCost(I, TargetTransformInfo::TCK_RecipThroughput);
     }
 
   private:
     void getAnalysisUsage(AnalysisUsage &AU) const override;
     bool runOnFunction(Function &F) override;
     void print(raw_ostream &OS, const Module*) const override;
 

 }
 
 void CostModelAnalysis::print(raw_ostream &OS, const Module*) const {
   if (!F)
     return;
 
   for (BasicBlock &B : *F) {
     for (Instruction &Inst : B) {
-      unsigned Cost = TTI->getInstructionCost(&Inst, CostKind);
-      if (Cost != (unsigned)-1)
+      InstructionCost Cost = TTI->getInstructionCost(&Inst, CostKind);
+      if (!Cost.isInvalid())
         OS << "Cost Model: Found an estimated cost of " << Cost;
       else
         OS << "Cost Model: Unknown cost";
 
       OS << " for instruction: " << Inst << "\n";
     }
   }
 }

llvm/lib/CodeGen/InterleavedLoadCombinePass.cpp

bool InterleavedLoadCombineImpl::combine(std::list<VectorInfo> &InterleavedLoad,
   // Test if the offset is computed
   if (!InsertionPoint)
     return false;
 
   std::set<LoadInst *> LIs;
   std::set<Instruction *> Is;
   std::set<Instruction *> SVIs;
 
-  unsigned InterleavedCost;
-  unsigned InstructionCost = 0;
+  InstructionCost InterleavedCost;
+  InstructionCost InstructionCost = 0;
 
   // Get the interleave factor
   unsigned Factor = InterleavedLoad.size();
 
   // Merge all input sets used in analysis
   for (auto &VI : InterleavedLoad) {
     // Generate a set of all load instructions to be combined
     LIs.insert(VI.LIs.begin(), VI.LIs.end());
for (auto &I : Is) {
     // If there are users outside the set to be eliminated, we abort the
     // transformation. No gain can be expected.
     for (auto *U : I->users()) {
       if (Is.find(dyn_cast<Instruction>(U)) == Is.end())
         return false;
     }
   }
 
+  // We need to have a valid cost in order to proceed.
+  if (InstructionCost.isInvalid())
+    return false;
+
   // We know that all LoadInst are within the same BB. This guarantees that
   // either everything or nothing is loaded.
   LoadInst *First = findFirstLoad(LIs);
 
   // To be safe that the loads can be combined, iterate over all loads and test
   // that the corresponding defining access dominates first LI. This guarantees
   // that there are no aliasing stores in between the loads.
   auto FMA = MSSA.getMemoryAccess(First);

llvm/lib/IR/DiagnosticInfo.cpp

 // Diagnostics reporting is still done as part of the LLVMContext.
 //===----------------------------------------------------------------------===//
 
 #include "llvm/IR/DiagnosticInfo.h"
 #include "LLVMContextImpl.h"
 #include "llvm/ADT/StringExtras.h"
 #include "llvm/ADT/Twine.h"
 #include "llvm/ADT/iterator_range.h"
+#include "llvm/Analysis/InstructionCost.h"
 #include "llvm/IR/BasicBlock.h"
 #include "llvm/IR/Constants.h"
 #include "llvm/IR/DebugInfoMetadata.h"
 #include "llvm/IR/DerivedTypes.h"
 #include "llvm/IR/DiagnosticPrinter.h"
 #include "llvm/IR/Function.h"
 #include "llvm/IR/GlobalValue.h"
 #include "llvm/IR/Instruction.h"

 
 DiagnosticInfoOptimizationBase::Argument::Argument(StringRef Key,
                                                    ElementCount EC)
     : Key(std::string(Key)) {
   raw_string_ostream OS(Val);
   EC.print(OS);
 }
 
+DiagnosticInfoOptimizationBase::Argument::Argument(StringRef Key,
+                                                   InstructionCost C)
+    : Key(std::string(Key)) {
+  raw_string_ostream OS(Val);
+  C.print(OS);
+}
+
 DiagnosticInfoOptimizationBase::Argument::Argument(StringRef Key, DebugLoc Loc)
     : Key(std::string(Key)), Loc(Loc) {
   if (Loc) {
     Val = (Loc->getFilename() + ":" + Twine(Loc.getLine()) + ":" +
            Twine(Loc.getCol())).str();
   } else {
     Val = "<UNKNOWN LOCATION>";
   }

llvm/lib/Transforms/IPO/HotColdSplitting.cpp

if (F.hasFnAttribute(Attribute::SanitizeAddress) ||
       F.hasFnAttribute(Attribute::SanitizeThread) ||
       F.hasFnAttribute(Attribute::SanitizeMemory))
     return false;
 
   return true;
 }
 
 /// Get the benefit score of outlining \p Region.
-static int getOutliningBenefit(ArrayRef<BasicBlock *> Region,
+static InstructionCost getOutliningBenefit(ArrayRef<BasicBlock *> Region,
                                            TargetTransformInfo &TTI) {
   // Sum up the code size costs of non-terminator instructions. Tight coupling
   // with \ref getOutliningPenalty is needed to model the costs of terminators.
-  int Benefit = 0;
+  InstructionCost Benefit = 0;
   for (BasicBlock *BB : Region)
     for (Instruction &I : BB->instructionsWithoutDebug())
       if (&I != BB->getTerminator())
         Benefit +=
             TTI.getInstructionCost(&I, TargetTransformInfo::TCK_CodeSize);
 
   return Benefit;
 }
CodeExtractor CE(Region, &DT, /* AggregateArgs */ false, /* BFI */ nullptr,
                    /* BPI */ nullptr, AC, /* AllowVarArgs */ false,
                    /* AllowAlloca */ false,
                    /* Suffix */ "cold." + std::to_string(Count));
 
   // Perform a simple cost/benefit analysis to decide whether or not to permit
   // splitting.
   SetVector<Value *> Inputs, Outputs, Sinks;
   CE.findInputsOutputs(Inputs, Outputs, Sinks);
-  int OutliningBenefit = getOutliningBenefit(Region, TTI);
+  InstructionCost OutliningBenefit = getOutliningBenefit(Region, TTI);
   int OutliningPenalty =
       getOutliningPenalty(Region, Inputs.size(), Outputs.size());
   LLVM_DEBUG(dbgs() << "Split profitability: benefit = " << OutliningBenefit
                     << ", penalty = " << OutliningPenalty << "\n");
-  if (OutliningBenefit <= OutliningPenalty)
+  if (OutliningBenefit.isInvalid() || OutliningBenefit <= OutliningPenalty)
     return nullptr;
 
   Function *OrigF = Region[0]->getParent();
   if (Function *OutF = CE.extractCodeRegion(CEAC)) {
     User *U = *OutF->user_begin();
     CallInst *CI = cast<CallInst>(U);
     NumColdRegionsOutlined++;
     if (TTI.useColdCCForColdCall(*OutF)) {

llvm/lib/Transforms/Scalar/CallSiteSplitting.cpp

static bool canSplitCallSite(CallBase &CB, TargetTransformInfo &TTI) {
   // BasicBlock::isEHPad as well.
   if (!CallSiteBB->canSplitPredecessors() || CallSiteBB->isEHPad())
     return false;
 
   // Allow splitting a call-site only when the CodeSize cost of the
   // instructions before the call is less then DuplicationThreshold. The
   // instructions before the call will be duplicated in the split blocks and
   // corresponding uses will be updated.
-  unsigned Cost = 0;
+  InstructionCost Cost = 0;
   for (auto &InstBeforeCall :
        llvm::make_range(CallSiteBB->begin(), CB.getIterator())) {
     Cost += TTI.getInstructionCost(&InstBeforeCall,
                                    TargetTransformInfo::TCK_CodeSize);
-    if (Cost >= DuplicationThreshold)
+    if (Cost.isInvalid() || Cost >= DuplicationThreshold)
       return false;
   }
 
   return true;
 }
 
 static Instruction *cloneInstForMustTail(Instruction *I, Instruction *Before,
                                          Value *V) {

llvm/lib/Transforms/Vectorize/SLPVectorizer.cpp

case Instruction::ShuffleVector: {
                Instruction::isBinaryOp(E->getAltOpcode())) ||
               (Instruction::isCast(E->getOpcode()) &&
                Instruction::isCast(E->getAltOpcode()))) &&
              "Invalid Shuffle Vector Operand");
       int ScalarCost = 0;
       if (NeedToShuffleReuses) {
         for (unsigned Idx : E->ReuseShuffleIndices) {
           Instruction *I = cast<Instruction>(VL[Idx]);
-          ReuseShuffleCost -= TTI->getInstructionCost(I, CostKind);
+          ReuseShuffleCost -= TTI->getInstructionCost(I, CostKind).getValue();
         }
         for (Value *V : VL) {
           Instruction *I = cast<Instruction>(V);
-          ReuseShuffleCost += TTI->getInstructionCost(I, CostKind);
+          ReuseShuffleCost += TTI->getInstructionCost(I, CostKind).getValue();
         }
       }
       for (Value *V : VL) {
         Instruction *I = cast<Instruction>(V);
         assert(E->isOpcodeOrAlt(I) && "Unexpected main/alternate opcode");
-        ScalarCost += TTI->getInstructionCost(I, CostKind);
+        ScalarCost += TTI->getInstructionCost(I, CostKind).getValue();
       }
       // VecCost is equal to sum of the cost of creating 2 vectors
       // and the cost of creating shuffle.
       int VecCost = 0;
       if (Instruction::isBinaryOp(E->getOpcode())) {
         VecCost = TTI->getArithmeticInstrCost(E->getOpcode(), VecTy, CostKind);
         VecCost += TTI->getArithmeticInstrCost(E->getAltOpcode(), VecTy,
                                                CostKind);
       } else {
         Type *Src0SclTy = E->getMainOp()->getOperand(0)->getType();

llvm/unittests/Analysis/CMakeLists.txt

add_llvm_unittest_with_input_files(AnalysisTests
   CFGTest.cpp
   CGSCCPassManagerTest.cpp
   ConstraintSystemTest.cpp
   DDGTest.cpp
   DivergenceAnalysisTest.cpp
   DomTreeUpdaterTest.cpp
   GlobalsModRefTest.cpp
   FunctionPropertiesAnalysisTest.cpp
+  InstructionCostTest.cpp
   IRSimilarityIdentifierTest.cpp
   IVDescriptorsTest.cpp
   LazyCallGraphTest.cpp
   LoadsTest.cpp
   LoopInfoTest.cpp
   LoopNestTest.cpp
   MemoryBuiltinsTest.cpp
   MemorySSATest.cpp

llvm/unittests/Analysis/InstructionCostTest.cpp

+//===- InstructionCostTest.cpp - InstructionCost tests --------------------===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+
+#include "llvm/Analysis/InstructionCost.h"
+#include "gtest/gtest.h"
+
+using namespace llvm;
+
+namespace {
+
+struct CostTest : public testing::Test {
+  CostTest() {}
+};
+
+
+} // namespace
+
+TEST_F(CostTest, Operators) {
+  InstructionCost Cost1 = 3;
+  InstructionCost Cost2 = -2;
+  InstructionCost Cost3 = 6;
+  InstructionCost Cost4 = InstructionCost::getInvalid(3);
+  InstructionCost TmpCost;
+
+  EXPECT_NE(Cost1, Cost2);
+  EXPECT_GT(Cost1, Cost2);
+  EXPECT_EQ(Cost1, Cost4);
+  EXPECT_EQ(Cost1 - Cost2, 5);
+  EXPECT_EQ(Cost1 * Cost2, -6);
+  EXPECT_EQ(Cost3 / Cost1, 2);
+
+  EXPECT_TRUE(Cost4.isInvalid());
+
+  TmpCost = Cost1 + Cost4;
+  EXPECT_TRUE(TmpCost.isInvalid());
+
+  TmpCost = Cost1 * Cost4;
+  EXPECT_TRUE(TmpCost.isInvalid());
+
+  EXPECT_EQ(InstructionCost::min(Cost1, Cost2), -2);
+  EXPECT_EQ(InstructionCost::max(Cost1, Cost3), 6);
+}