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.
Details
Diff Detail
Event Timeline
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? | |
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?
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.
- Simplified *BudgetRemaining.getValue() < 0 to BudgetRemaining < 0.
- Changed int Cost; to InstructionCost Cost.
- Rebased patch.
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 |
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! |
llvm/include/llvm/Transforms/Utils/ScalarEvolutionExpander.h | ||
---|---|---|
20 | the headers need sorting - clang-format this |
- Reordered includes.
- Changed two more variables to be of type InstructionCost instead of int.
llvm/include/llvm/Transforms/Utils/ScalarEvolutionExpander.h | ||
---|---|---|
20 | Fixed, thanks for pointing out! |
llvm/lib/Transforms/Utils/ScalarEvolutionExpander.cpp | ||
---|---|---|
2348–2349 | What happens without the isValid() check? |
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. |
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(), So alternatively, why not at least make it easy to detect this issue, |
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:
Would that be a suitable solution? |