Page MenuHomePhabricator

[SCEVExpander] Migrate costAndCollectOperands to use InstructionCost.
AcceptedPublic

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

Details

Summary

This patch changes the type of BudgetRemaining and Cost in
costAndCollectOperands from 'unsigned' to 'InstructionCost' so that it
can take into account an Invalid cost. isHighCostExpansion will return
true if the cost is invalid, but the patch is NFC until any of the cost
functions return a Invalid cost.

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
248

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
2208

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.Thu, Jan 7, 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
248

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
2208

Good catch!

RKSimon added inline comments.Thu, Jan 14, 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.Mon, Jan 18, 1:35 AM
  • Reordered includes.
  • Changed two more variables to be of type InstructionCost instead of int.
sdesmalen marked an inline comment as done.Mon, Jan 18, 1:35 AM
sdesmalen added inline comments.
llvm/include/llvm/Transforms/Utils/ScalarEvolutionExpander.h
20

Fixed, thanks for pointing out!

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

It look to me now.

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

What happens without the isValid() check?

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

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.Mon, Jan 18, 8:23 AM
llvm/lib/Transforms/Utils/ScalarEvolutionExpander.cpp
2348–2349

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.Tue, Jan 19, 1:20 AM
llvm/lib/Transforms/Utils/ScalarEvolutionExpander.cpp
2348–2349

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?