[SCEVExpander] Migrate costAndCollectOperands to use InstructionCost.

[sdesmalen]

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.

[CarolineConcatto]

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?

[lebedev.ri]

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?

[ctetreau]

In D92238#2452418, @lebedev.ri wrote:

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]

• Simplified *BudgetRemaining.getValue() < 0 to BudgetRemaining < 0.
• Changed int Cost; to InstructionCost Cost.
• Rebased patch.

[sdesmalen]

In D92238#2480072, @ctetreau wrote:

In D92238#2452418, @lebedev.ri wrote:

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!

[sdesmalen]

Gentle ping

[RKSimon]

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

20

the headers need sorting - clang-format this

[sdesmalen]

• Reordered includes.
• Changed two more variables to be of type InstructionCost instead of int.

[sdesmalen]

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

20

Fixed, thanks for pointing out!

[CarolineConcatto]

It look to me now.

[lebedev.ri]

llvm/lib/Transforms/Utils/ScalarEvolutionExpander.cpp

2348–2349

What happens without the isValid() check?

[sdesmalen]

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]

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]

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?