Page MenuHomePhabricator

[Analysis] Introduce a new InstructionCost class
AcceptedPublic

Authored by david-arm on Tue, Nov 10, 8:42 AM.

Details

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.

Diff Detail

Event Timeline

There are a very large number of changes, so older changes are hidden. Show Older Changes
nikic added a subscriber: nikic.Tue, Nov 10, 9:30 AM
nikic added inline comments.
llvm/include/llvm/Analysis/InstructionCost.h
43

Please make "invalid" a special value (like -1) instead.

Overall, this seems reasonable to me.

llvm/include/llvm/Analysis/InstructionCost.h
2

I think it's a bit strange that the new header is named InstructionCost.h, but all but 1 line of it is dedicated to defining a class called GenericCost. I feel like this header should be renamed GenericCost.h, and be put somewhere more central. (perhaps under llvm/Support). The using InstructionCost = GenericCost<int> should probably be moved out of this file. Perhaps TargetTransformInfo.h or CostModel.h?

36

BIKESHED: If you ask a person on the street what the opposite of "invalid" is, they probably won't answer "normal"

60

should we have a setValid function? I'm thinking cases like x / 0 being invalid, select (I would imagine) having max(lhs, rhs) cost, but select(true, lhs, x / 0) being valid, having the cost of the lhs.

(this is just an example. I'm sure select(true, ..., ...) doesn't naively do a max)

160

The comparators should do something with isValid(). I feel like this is going to be a source of bugs. I see three things you could do:

  • assert: I'm not in love with this option. I think it's reasonable to ask {7, Invalid} == {7, Valid}
  • define a total ordering: This is my preference. I think forall x, y. {x, Invalid} > {y, Valid} is good, because conceptually, an invalid cost has infinite cost.
  • document a partial ordering: "nobody likes NaN semantics"
208–214

These should check isValid() (not necessary if you define a total ordering)

ctetreau added inline comments.Tue, Nov 10, 10:11 AM
llvm/include/llvm/Analysis/InstructionCost.h
35

please use enum class. Assigning values is unneccesary in this case because it won't magically coerce to an int.

Thanks @david-arm for working on this. It all looks quite sensible to me.

One thing I wondered when looking at this patch is if the templating for the cost type is really necessary, or would it be sufficient to always use int64_t as the cost type?
That might simplify the implementation a bit and would remove a level of indirection (i.e. using InstructionCost = GenericCost<unsigned>)

david-arm added inline comments.Fri, Nov 13, 3:39 AM
llvm/include/llvm/Analysis/InstructionCost.h
43

Hi @nikic , do you mean remove the CostState and use a set of special values to define any possible state such as invalid? The reason I chose not to do this was for two reasons:

  1. If we ever want to support an additional state in future then it means another special value, e.g. -2. I thought it was better to avoid having a list of special values and simply encode the state separately.
  2. There are plenty of examples in the codebase where costs can go negative, for example when calculating the cost budget remaining for some loop optimisations or in the SLPVectorizer. In such cases you could hit a value of -1 accidentally during normal operation and it would then be treated as invalid.

Does anyone else have any thoughts about this?

david-arm updated this revision to Diff 305097.Fri, Nov 13, 4:28 AM
  • Changed comparison operators to explicitly treat invalid as infinitely expensive and return the appropriate result.
  • Added setValid() function.
  • Changed enum states to Valid and Invalid.
  • Removed template from the InstructionCost class and defaulted to 'int'. I think 32 bits is enough for costs, since everywhere in the codebase uses int or unsigned. However, the cost type can be easily changed since I made it a typedef. Not having the template meant I could also simplify the list of operators.
  • Changed lib/Transforms/Scalar/CallSiteSplitting.cpp so that we no longer explicitly check isInvalid() before comparing with DuplicationThreshold. This is because the ">=" operator now takes the invalid state into account.
david-arm marked 7 inline comments as done.Fri, Nov 13, 4:29 AM
ctetreau added inline comments.Fri, Nov 13, 10:20 AM
llvm/include/llvm/Analysis/InstructionCost.h
43

I think this approach is error-prone. Additionally, it's not extensible. Maybe we want to add scalable costs in the future? The way you have it defined now, it's a straightforward extension. If you have "invalid" just be a special case cost, then we have to repeat this whole exercise.

I feel strongly that your approach is preferable.

62
81–85

I feel like this comment is unnecessarily scary. I believe that the intuition that you have formed is:

CostType evaluateCostState(CostState c) {
   if (c == Valid)
      return 0;
   return std::numeric_limits<CostType>::max()
}

CostType evaluateCost(InstructionCost c) {
   return c.Value + evaluateCostState(c.State);
}

As you've noted, this falls apart for subtraction.

I think the intuition should be more like how floating point numbers work wrt NaN. For l + r, where l and r are floats, the user just assumes they do math like normal. NaN is just a cancer value that can contaminate a float if you do something bad. The user typically does not expect to be able to recover from NaN, they just make sure they don't have it at some point. Similarly, we expect users of InstructionCost to just do math with costs as if they were a regular scalar value. If they ask for the cost of something that should never be done, they get an invalid cost. For all arithmetic operators op, l op r is invalid for all l and r. At some point, the user will inspect a cost and see if it's valid, and make a choice based on this info.

The only different here is that unlike floats with NaNs, we have a useful total ordering. In this case, it's a lexicographical ordering, where Invalid > Valid and State is checked before Value.

158

Maybe it would be good to document the ordering and motivation for it?

161

is false < true actually defined by the C++ standard? (I don't know offhand)

llvm/include/llvm/Analysis/TargetTransformInfo.h
257–260

Why is this being done? Did the code not handle -1 correctly before?

llvm/unittests/Analysis/InstructionCostTest.cpp
24–29

I would prefer that these costs have descriptive names. It's much more obvious why EXPECT_GT(VThree, VNegTwo) is true than EXPECT_GT(Cost1, Cost2)

david-arm added inline comments.Tue, Nov 17, 2:35 AM
llvm/include/llvm/Analysis/TargetTransformInfo.h
257–260

So this patch doesn't change the getUserCost interface - that will be done in a later patch. getUserCost returns -1 for invalid costs, or costs that it cannot determine. This matches up with our new Invalid state in InstructionCost so as a temporary measure I've added the check here. A later patch will remove this "if (Cost == -1)" code and ensure that getUserCost returns a proper Invalid Cost.

david-arm updated this revision to Diff 306107.Wed, Nov 18, 7:55 AM
  • Added comments explaining the reason for the behaviour used in the comparison operators.
  • Removed the comment above operator-.
  • Added private propagateState() function, which is more generic and will support more than state. It uses the same lexicographical ordering as the comparisons.
  • Updated the tests to use more readable variable names.

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.

david-arm updated this revision to Diff 306616.Fri, Nov 20, 1:25 AM
david-arm marked 2 inline comments as done.
ctetreau accepted this revision.Fri, Nov 20, 9:46 AM

Looks good to me

This revision is now accepted and ready to land.Fri, Nov 20, 9:46 AM
sdesmalen added inline comments.Mon, Nov 23, 7:32 AM
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 added inline comments.Mon, Nov 23, 8:14 AM
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 added inline comments.Mon, Nov 23, 8:46 AM
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 requested changes to this revision.Mon, Nov 23, 8:46 AM
ctetreau added inline comments.
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.

This revision now requires changes to proceed.Mon, Nov 23, 8:46 AM

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)

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()).

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 added a subscriber: vkmr.Tue, Nov 24, 1:20 AM
david-arm added inline comments.
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 updated this revision to Diff 307278.Tue, Nov 24, 1:29 AM
  • Changed getValue() to return an Optional<CostType>

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.

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

ctetreau accepted this revision.Tue, Nov 24, 9:02 AM

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.

This revision is now accepted and ready to land.Tue, Nov 24, 9:02 AM
  • Added tests for value extraction.
sdesmalen accepted this revision.Wed, Nov 25, 3:31 AM

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
106

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 added a subscriber: fhahn.Wed, Nov 25, 3:48 AM
fhahn added inline comments.
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 added inline comments.Wed, Nov 25, 4:02 AM
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 added inline comments.Wed, Nov 25, 4:20 AM
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 added inline comments.Wed, Nov 25, 5:32 AM
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 ...).

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?

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 updated this revision to Diff 307629.EditedWed, Nov 25, 8:58 AM
  • Removed isInvalid() in favour of getState() that is more future-proof.
  • Converted comments to use three slashes!
david-arm marked 2 inline comments as done.Wed, Nov 25, 8:59 AM
(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 added inline comments.Thu, Nov 26, 12:41 AM
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.

(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 added inline comments.Thu, Nov 26, 2:34 AM
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.

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 updated this revision to Diff 307870.Thu, Nov 26, 7:56 AM
  • 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.

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");
}
  1. "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."
  1. 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 added inline comments.Tue, Dec 1, 8:43 AM
llvm/include/llvm/Analysis/InstructionCost.h
57

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;
}