Page MenuHomePhabricator

[Support] Introduce a new InstructionCost class
ClosedPublic

Authored by david-arm on Nov 10 2020, 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

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
22 ↗(On Diff #307278)

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.Nov 24 2020, 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.Nov 24 2020, 9:02 AM
  • Added tests for value extraction.
sdesmalen accepted this revision.Nov 25 2020, 3:31 AM

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

llvm/include/llvm/Analysis/InstructionCost.h
64 ↗(On Diff #306616)

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.Nov 25 2020, 3:48 AM
fhahn added inline comments.
llvm/include/llvm/Analysis/InstructionCost.h
64 ↗(On Diff #306616)

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?

66 ↗(On Diff #307534)

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.Nov 25 2020, 4:02 AM
llvm/include/llvm/Analysis/InstructionCost.h
64 ↗(On Diff #306616)

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.Nov 25 2020, 4:20 AM
llvm/include/llvm/Analysis/InstructionCost.h
64 ↗(On Diff #306616)

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.Nov 25 2020, 5:32 AM
llvm/include/llvm/Analysis/InstructionCost.h
64 ↗(On Diff #306616)

[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.EditedNov 25 2020, 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.Nov 25 2020, 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
28 ↗(On Diff #307629)

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

224–236 ↗(On Diff #307629)

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.Nov 26 2020, 12:41 AM
llvm/include/llvm/Analysis/InstructionCost.h
28 ↗(On Diff #307629)

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.Nov 26 2020, 2:34 AM
llvm/include/llvm/Analysis/InstructionCost.h
224–236 ↗(On Diff #307629)

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.Nov 26 2020, 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.Dec 1 2020, 8:43 AM
llvm/include/llvm/Analysis/InstructionCost.h
57 ↗(On Diff #307870)

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 added inline comments.Dec 2 2020, 6:31 AM
llvm/include/llvm/Analysis/InstructionCost.h
57 ↗(On Diff #307870)

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 added inline comments.Dec 3 2020, 5:40 AM
llvm/include/llvm/Analysis/InstructionCost.h
57 ↗(On Diff #307870)

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 marked 18 inline comments as done.Dec 8 2020, 6:04 AM

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
57 ↗(On Diff #307870)

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 updated this revision to Diff 310210.Dec 8 2020, 7:50 AM
david-arm marked an inline comment as done.
david-arm retitled this revision from [Analysis] Introduce a new InstructionCost class to [Support] Introduce a new InstructionCost class.
  • 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 updated this revision to Diff 310216.Dec 8 2020, 7:55 AM
  • Fixed typo in InstructionCost.h - replaced LLVM_ANALYSIS_INSTRUCTIONCOST_H with LLVM_SUPPORT_INSTRUCTIONCOST_H

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
41

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

david-arm updated this revision to Diff 310454.Dec 9 2020, 1:34 AM
  • Added increment and decrement operator tests.
david-arm marked an inline comment as done.Dec 9 2020, 1:34 AM
david-arm added inline comments.
llvm/unittests/Support/InstructionCostTest.cpp
41

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

RKSimon added inline comments.
llvm/include/llvm/Analysis/TargetTransformInfo.h
24

clang-format this (sorting)

llvm/include/llvm/IR/DiagnosticInfo.h
42

(sorting)

llvm/lib/IR/DiagnosticInfo.cpp
19

(sorting)

llvm/lib/Transforms/Vectorize/LoopVectorize.cpp
7195–7200

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

ctetreau added inline comments.Dec 9 2020, 11:52 AM
llvm/lib/Transforms/Vectorize/LoopVectorize.cpp
7195–7200

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
50

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 added inline comments.Dec 9 2020, 11:54 AM
llvm/lib/Transforms/Vectorize/LoopVectorize.cpp
7195–7200

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 marked an inline comment as done.Dec 10 2020, 12:52 AM
david-arm added inline comments.
llvm/lib/Transforms/Vectorize/LoopVectorize.cpp
7195–7200

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 updated this revision to Diff 310796.Dec 10 2020, 1:29 AM
  • Fixed sorting issues with InstructionCost header + class declaration.
  • Added assert that ExtractValue cost is valid in LoopVectorize.cpp.
  • Added additional tests to InstructionCostTests.cpp
david-arm marked 6 inline comments as done.Dec 10 2020, 1:30 AM

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

llvm/lib/Transforms/Vectorize/SLPVectorizer.cpp
3797–3808

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

david-arm updated this revision to Diff 310880.Dec 10 2020, 7:02 AM
david-arm marked an inline comment as done.
RKSimon accepted this revision.Dec 10 2020, 8:22 AM

LGTM - cheers

This revision was automatically updated to reflect the committed changes.