Page MenuHomePhabricator

[SCEVExpander] Migrate costAndCollectOperands to use InstructionCost.
ClosedPublic

Authored by sdesmalen on Nov 27 2020, 10:06 AM.

Details

Summary

This patch changes costAndCollectOperands to use InstructionCost for
accumulated cost values.

isHighCostExpansion will return true if the cost is too high or invalid.

Diff Detail

Event Timeline

sdesmalen created this revision.Nov 27 2020, 10:06 AM
Herald added a project: Restricted Project. · View Herald TranscriptNov 27 2020, 10:06 AM
Herald added a subscriber: hiraditya. · View Herald Transcript
sdesmalen requested review of this revision.Nov 27 2020, 10:06 AM
sdesmalen updated this revision to Diff 310203.Dec 8 2020, 7:36 AM
llvm/include/llvm/Transforms/Utils/ScalarEvolutionExpander.h
250

Maybe put this assertion before the loop? Is there any reason to check the Cost if BudgetRemaining.isValid() is not valid?
Or maybe you can remove this assert from here, because if we check isHighCostExpansionHelper this test is done in line 2346.

llvm/lib/Transforms/Utils/ScalarEvolutionExpander.cpp
2188

Why you did not changed Cost to be InstructionCost?

I think this is conflating use-cases.
I'm not sure the entire InstructionCost should be used as a variable to track full/remaining cost over a several instructions.
Perhaps there should be a[nother] abstraction for that?

I think this is conflating use-cases.
I'm not sure the entire InstructionCost should be used as a variable to track full/remaining cost over a several instructions.
Perhaps there should be a[nother] abstraction for that?

Really, we were already doing this; we just didn't have a special cost type. We could leave the cost as an integer, but then the code would just become way more verbose (unwrapping every InstructionCost after computing them). Using the metaphor of money, a cost is a quantity of money. I think it's reasonable to subtract money from a budget. I suppose we could accumulate a running cost, and compare it with the budget that remains an integer, but that would just introduce another variable for (IMO) no good reason.

sdesmalen updated this revision to Diff 315138.Jan 7 2021, 7:50 AM
  • Simplified *BudgetRemaining.getValue() < 0 to BudgetRemaining < 0.
  • Changed int Cost; to InstructionCost Cost.
  • Rebased patch.

I think this is conflating use-cases.
I'm not sure the entire InstructionCost should be used as a variable to track full/remaining cost over a several instructions.
Perhaps there should be a[nother] abstraction for that?

Really, we were already doing this; we just didn't have a special cost type. We could leave the cost as an integer, but then the code would just become way more verbose (unwrapping every InstructionCost after computing them). Using the metaphor of money, a cost is a quantity of money. I think it's reasonable to subtract money from a budget. I suppose we could accumulate a running cost, and compare it with the budget that remains an integer, but that would just introduce another variable for (IMO) no good reason.

Like @ctetreau I don't see why the algorithm shouldn't be using InstructionCost. The class has enough capabilities that any invalid state now propagates quite naturally without too big changes (InstructionCost behaves mostly like a scalar int that carries extra state).
I've simplified the use of *BudgetRemaining.getValue() < 0 to BudgetRemaining < 0, which hopefully makes the patch more palatable?

llvm/include/llvm/Transforms/Utils/ScalarEvolutionExpander.h
250

Or maybe you can remove this assert from here, because if we check isHighCostExpansionHelper this test is done in line 2346.

That's true, but the assert here is only to verify the code/values are sane.

llvm/lib/Transforms/Utils/ScalarEvolutionExpander.cpp
2188

Good catch!

RKSimon added inline comments.Jan 14 2021, 9:55 AM
llvm/include/llvm/Transforms/Utils/ScalarEvolutionExpander.h
20

the headers need sorting - clang-format this

sdesmalen updated this revision to Diff 317282.Jan 18 2021, 1:35 AM
  • Reordered includes.
  • Changed two more variables to be of type InstructionCost instead of int.
sdesmalen marked an inline comment as done.Jan 18 2021, 1:35 AM
sdesmalen added inline comments.
llvm/include/llvm/Transforms/Utils/ScalarEvolutionExpander.h
20

Fixed, thanks for pointing out!

CarolineConcatto accepted this revision.Jan 18 2021, 6:42 AM

It look to me now.

This revision is now accepted and ready to land.Jan 18 2021, 6:42 AM
lebedev.ri added inline comments.Jan 18 2021, 8:02 AM
llvm/lib/Transforms/Utils/ScalarEvolutionExpander.cpp
2328–2329

What happens without the isValid() check?

sdesmalen marked an inline comment as done.Jan 18 2021, 8:09 AM
sdesmalen added inline comments.
llvm/lib/Transforms/Utils/ScalarEvolutionExpander.cpp
2328–2329

Without the isValid() check it defaults to the total ordering for InstructionCost where all valid costs < Invalid.
This means that BudgetRemaining < 0 would evaluate to false, where instead we want to return true from this function to signal this is a high cost expansion.

lebedev.ri added inline comments.Jan 18 2021, 8:23 AM
llvm/lib/Transforms/Utils/ScalarEvolutionExpander.cpp
2328–2329

Uh oh.

So if every single check now needs to not be forgotten to be prefixed with isValid(),
doesn't that imply that the default is wrong, and it should be Invalid < all valid costs instead?
I'm guessing not, because i guess 0 > BudgetRemaining will then break.

So alternatively, why not at least make it easy to detect this issue,
and instead assert within the InstructionCost that costs must be valid to do such comparison?

sdesmalen added inline comments.Jan 19 2021, 1:20 AM
llvm/lib/Transforms/Utils/ScalarEvolutionExpander.cpp
2328–2329

In D91174 @ctetreau argued in favour of having a total ordering over asserting that the costs must be valid (https://reviews.llvm.org/D91174#2422681).

Probably the most prominent use-case where an InstructionCost is used in comparisons is:

if (CostX < CostY)
  // replace with X

Here the total-ordering is desirable, i.e. if CostX is invalid, don't replace with X. Otherwise, replace if CostX is smaller than CostY or CostY is invalid. We want to avoid having to rewrite these cases to:

if ((CostX.isValid() && !CostY.isValid()) ||
     (CostX.isValid() && CostY.isValid() && CostX < Cost))
  // replace with X

// All cases would need to be covered if CostX < CostY would *assert*
// they most both be valid.

I think that in this particular case - working with cost as a budget - there is extra confusion because the code is comparing directly with a constant, which makes it easy to forget that this is not a 'normal' comparison, but is in fact a comparison between InstructionCosts which has total ordering semantics.

What I could do is:

  • Mark InstructionCost::operator<(int) operator as delete, so that the above statement no longer compiles. This means only comparisons between InstructionCosts are supported.
  • Add a new method bool InstructionCost::isNegativeValue() which returns true if the value is Valid and less than 0.
  • Update this patch to use isNegativeValue() instead.

Would that be a suitable solution?

sdesmalen updated this revision to Diff 318949.Jan 25 2021, 4:06 AM
sdesmalen edited the summary of this revision. (Show Details)

Changed patch to use a new InstructionBudget class.

I have come to the realisation that an abstraction around InstructionCost specific for budgeting is actually quite useful.

@lebedev.ri are you happy with these changes?

llvm/lib/Transforms/Utils/ScalarEvolutionExpander.cpp
2328–2329

Last week I've been working to update multiple passes and interfaces to work on InstructionCost, and I found that for most, if not all, other cases where InstructionCost is used the total ordering is sufficient and sufficiently clear. Therefore I don't think my above suggestion makes sense, so please ignore it.

lebedev.ri accepted this revision.Jan 25 2021, 4:49 AM

I guess this is as good as we'll get for the first approximation.
Thanks.

I guess this is as good as we'll get for the first approximation.
Thanks.

Thanks for your feedback!

ctetreau added inline comments.Jan 25 2021, 9:53 AM
llvm/include/llvm/Support/InstructionCost.h
238 ↗(On Diff #318949)

I think this new class is uneccesary. Can't we just write 0 > Cost for any case where we would use Cost.isExceeded()?

ctetreau requested changes to this revision.Jan 25 2021, 9:58 AM

I'd like you to reconsider adding InstructionBudget. I think this new class is just trying to paper over people's misunderstanding of how InstructionCost works. This wouldn't be a huge issue, except now we're going to have to add a million redundant operator definitions to it ("why can't I multiply budgets?") so it's going to become a maintenance burden.

This revision now requires changes to proceed.Jan 25 2021, 9:58 AM

Then please fix the InstrouctionCost comparison operators to do the right thing to avoid most of the changes in this diff in the first place.

Then please fix the InstrouctionCost comparison operators to do the right thing to avoid most of the changes in this diff in the first place.

InstructionCost does do the right thing. InstructionCost is isomorphic to Optional<int>, except in 99% of cases, you want an invalid cost to be considered greater than any other cost. Does int do the wrong thing because std::numeric_limits<int>::max() + 1 < std::numeric_limits<int>::max()?

I don't think that Cost < 0 || Cost.isInvalid() is an unreasonable change to request. Especially considering all the other code that uses InstructionCost that is written much more naturally due to the total ordering. An isExceeded() free function can be added to this file to ensure it's done correctly.

llvm/include/llvm/Support/InstructionCost.h
238 ↗(On Diff #318949)

I guess this doesn't work either. You have to do the isInvalid() call

lebedev.ri requested changes to this revision.Jan 25 2021, 10:21 AM

Guess this is stuck, then.

ctetreau added inline comments.Jan 25 2021, 10:24 AM
llvm/include/llvm/Support/InstructionCost.h
238 ↗(On Diff #318949)

Things that are logically "budgets" can be initialized with negative numbers, and have costs added to them, rather than subtracted. Then Cost > 0 can be used and will work correctly.

sdesmalen updated this revision to Diff 319105.Jan 25 2021, 1:40 PM

An attempt to meet in the middle:

  • No need for InstructionBudget class.
  • No need for any changes to return BudgetRemaining < 0 in isHighCostExpansionHelper.

Instead, the check for BudgetRemaining.isValid() is now done at the end in isHighCostExpansion. If the helper function found the budget has exceeded, or if the resulting budget has been invalidated, the expansion is considered high cost.

Is this a step in the right direction?

An attempt to meet in the middle:

  • No need for InstructionBudget class.
  • No need for any changes to return BudgetRemaining < 0 in isHighCostExpansionHelper.

Instead, the check for BudgetRemaining.isValid() is now done at the end in isHighCostExpansion. If the helper function found the budget has exceeded, or if the resulting budget has been invalidated, the expansion is considered high cost.

Is this a step in the right direction?

Won't we now not stop as soon as the budget is invalidated?
Perhaps if InstructionCost::operator< can't be fixed, it needs to be ripped out.
I'm sorry, i don't have useful feedback other than "the new abstraction is bad".

Won't we now not stop as soon as the budget is invalidated?
Perhaps if InstructionCost::operator< can't be fixed, it needs to be ripped out.
I'm sorry, i don't have useful feedback other than "the new abstraction is bad".

I agree that it's strictly worse in that the early return is not triggered if anything returns an invalid cost. I disagree that InstructionCost::operator< needs to be fixed or that "the new abstraction is bad".

The new abstraction has a well-defined semantics that is useful in the common case of deciding which of two costs is preferable. Throughout the codebase, we decide if thingA should be done over thingB by asking if the cost of thingA is less than the cost of thingB. If one of those things has an invalid cost, then it makes sense to consider the thing with a valid cost as less than it. If they are both invalid, then it doesn't really matter which one we pick.

I'm curious: what's the objection to having the budget be a negative number, and adding costs instead of subtracting? We could also accumulate costs in a separate variable and compare Cost < Budget, which will also do the right thing in the face of an invalid cost infecting the running total. In this case, Budget doesn't even need to be an InstructionCost.

Won't we now not stop as soon as the budget is invalidated?

That should be no different than before, isHighCostExpansionHelper is not recursive. The function that calls it, isHighCostExpansion, will still stop immediately when the cost is invalidated.

Perhaps if InstructionCost::operator< can't be fixed, it needs to be ripped out.
I'm sorry, i don't have useful feedback other than "the new abstraction is bad".

The part of the new abstraction that I believe may require more thought is the signedness of InstructionCost. If Cost would be unsigned, the code is already expected to deal with wrapping values due to underflow and InstructionCost::operator< would work as expected. There would be no need to add additional checks for validity. Another possibility would be to return Invalid when there is an underflow, because if there is a negative cost at any point this is probably a bug. That would still mean changing the compare "Budget < 0" in this file, but there are other ways to write it such as @ctetreau's suggests.

Is this something to consider changing at some point?

I'm curious: what's the objection to having the budget be a negative number, and adding costs instead of subtracting?

Personally I find this a bit counter-intuitive, because a budget is always a positive value that is subtracted from.

We could also accumulate costs in a separate variable and compare Cost < Budget, which will also do the right thing in the face of an invalid cost infecting the running total. In this case, Budget doesn't even need to be an InstructionCost.

Yes, I quite like that suggestion.

sdesmalen updated this revision to Diff 319297.Jan 26 2021, 8:03 AM
sdesmalen edited the summary of this revision. (Show Details)
  • Refactored patch to use incrementing Cost value, to be compared with Budget.

There probably isn't much I can do in this patch to take away all @lebedev.ri 's concerns regarding the comparison operators, but hopefully this patch is now written in such a way that it is clear and acceptable to everyone. I'd be happy to follow this up with possible changes to the nature of InstructionCost itself, like I suggested earlier, if that is helpful.

Aside from the change to the assert, this version looks good to me.

llvm/include/llvm/Transforms/Utils/ScalarEvolutionExpander.h
241–251

If the scale factor to the budget changes, then this assert will be wrong. If TCC_Basic is not 1, then the assert is already wrong.

Fixed issue with assert, now uses ScaledBudget.

sdesmalen marked an inline comment as done.Jan 27 2021, 12:33 PM

Hi @lebedev.ri, when we introduced InstructionCost, we left open the possibility of changing the class based on new insights on how costs are used in TargetTransformInfo and IR passes.

In this patch you pointed out a valid concern. It is indeed unexpected to need to have to check isValid() when wanting to know if a budget has gone negative after subtracting a cost, because even though InstructionCost is signed, subtracting Invalid currently results in Invalid, not -Invalid.

I had a chat with @ctetreau offline about changing InstructionCost by making the cost unsigned (i.e. a cost can only ever be positive), or possibly restricting the class's operators that it can only ever be incrementing, so that sorting Invalid after a valid cost value would no longer be strange/unexpected. I think this would address your fundamental concerns with the abstraction. There is some investigation required on what exactly the right solution would be, but I'd be happy to follow this up separately.

For the use-case in this patch (SCEVExpander), I think we now have a suitable solution that makes sense and is future proof for whatever changes we may make to InstructionCost. If you have no strong objections to the current approach (separate Cost and Budget variables), are you happy to accept the patch so that we can move this forward?

ctetreau accepted this revision.Feb 3 2021, 8:49 AM

This version LGTM

lebedev.ri resigned from this revision.Feb 13 2021, 2:10 AM

I wasn't reachable since 02.02.2021, ~back now.

Let me just complain about the interface next time i use it an obviously fall into it's traps.

This revision is now accepted and ready to land.Feb 13 2021, 2:10 AM