[CostModel] Return an invalid cost for memory ops with unsupported types

[kmclaughlin]

Summary

Fixes getTypeConversion to return TypeScalarizeScalableVector when a scalable vector
type cannot be legalized by widening/splitting. When this is the method of legalization
found, getTypeLegalizationCost will return an Invalid cost.

The getMemoryOpCost, getMaskedMemoryOpCost & getGatherScatterOpCost functions already call
getTypeLegalizationCost and will now also return an Invalid cost for unsupported types.

[david-arm]

llvm/include/llvm/Analysis/TargetTransformInfo.h

2261 ↗

(On Diff #345496)

nit: Could you clean up the clang-format warnings?

llvm/lib/CodeGen/TargetLoweringBase.cpp

1019–1020

Hi @kmclaughlin is it possible to add a test for this? For example, just another test for <vscale x 1 x i128>.

[kmclaughlin]

• Changed one of the tests in sve-illegal-types.ll to use <vscale x 1 x i128>
• Ran clang-format

llvm/lib/CodeGen/TargetLoweringBase.cpp

1019–1020

Hi @david-arm, I've changed the @store_nxvi128 test to use vscale x 1 x i128

[david-arm]

LGTM! Thanks for adding the test!

llvm/lib/Target/AArch64/AArch64TargetTransformInfo.cpp

1291

nit: I think because we bail out at the start of the function if it's not a scalable vector we can actually just do:

VectorType *VTy = cast<ScalableVectorType>(Src);
if (!isLegalToVectorizeElementType(...))

This is also true for getGatherScatterOpCost

[sdesmalen]

llvm/include/llvm/Analysis/TargetTransformInfo.h

1324 ↗

(On Diff #345863)

Does it ever make sense to call this function with VectorIsScalable=false given that fixed-width vectors can fall back on scalarization?
If not, should this then become: isElementTypeLegalForScalableVector(Type *Ty) ?

llvm/lib/Target/AArch64/AArch64TargetTransformInfo.cpp

1644–1650

nit:

if (!VectorIsScalable)
  return true;
return Ty->isIntegerTy(1) || isLegalElementTypeForSVE(Ty);

[david-arm]

llvm/include/llvm/Analysis/TargetTransformInfo.h

1324 ↗

(On Diff #345863)

I wonder if there may be a possibility in future where a scalable vector supports something that a fixed width one doesn't, e.g. not related specifically to scalarisation?

[sdesmalen]

llvm/include/llvm/Analysis/TargetTransformInfo.h

1324 ↗

(On Diff #345863)

But then I imagine it would still be legal to vectorize, because fixed-width can fall back on scalarization. It would then be up to the cost-model to say which one is more profitable.

[kmclaughlin]

• Renamed isLegalToVectorizeElementType to isElementTypeLegalForScalableVector as suggested by @sdesmalen and stopped passing VectorIsScalable, as we are never calling this function when this is false.

[david-arm]

LGTM! Looks like you've addressed all the review comments!

[sdesmalen]

Hi @kmclaughlin, I'm requesting changes to this patch because after a closer look I believe we can/should rely on the CodeGenerator's information on how to legalize a vector type in order to know how to cost it. The [AArch64]TargetTransformInfo::get*MemoryCost implementations actually already do this. For example, a <vscale x 8 x i32> for SVE will need splitting into 2 x <vscale x 4 x i32>, and so the operation cost would be 2 x the cost of a memory operation on a legal type. For scalable vector types that need scalarization, we know the cost is Invalid, because the code-generator is unable to handle these types. In practice, this requires:

• Fixing getTypeConversion to return TypeScalarizeScalableVector when a scalable vector type cannot be legalized by widening/splitting.
• Returning an Invalid cost from getTypeLegalizationCost when the method of legalization is TypeScalarizeScalableVector.
• In the AArch64TTI methods that return the cost of memory operations, we already call getTypeLegalizationCost, so all that needs doing is returning Invalid.

The method isElementTypeLegalForScalableVector is more something to add in D102253 where it is called by the LV before it has picked a VF, to know if there is any VF which can handle these types. If so, then it must be possible to legalize the types by splitting or widening and so the CostModel must be able to cost them.

llvm/lib/CodeGen/TargetLoweringBase.cpp

1019–1020

This comment will become redundant when you address my other comment, but I found that when removing this change, the tests still passed because the calls to isElementTypeLegalForScalableVector return before calling the getTypeLegalizationCost code (which ends up in this function).

[kmclaughlin]

• Removed isElementTypeLegalForScalableVector from this patch
• Changed getTypeConversion to return TypeScalarizeScalableVector if a scalable type cannot be legalized by widening/splitting.
• Return an Invalid cost from getMemoryOpCost, getMaskedMemoryOpCost & getGatherScatterOpCost if the cost returned by getTypeLegalizationCost is Invalid

[dfukalov]

llvm/lib/CodeGen/TargetLoweringBase.cpp

1848–1850

My observation was that here less destructive for test is to just Cost.setInvalid() instead of return 'empty' invalid value. So the function continues to return the same numeric value but with invalid flag. It will create less impact on the current flow.

Most of operations with InstructionCost are not aware of invalid flag. I guess it might be be next separated step to stop loop here and just return invalid value and then gather all side effects of 'changed' cost numeric value.

Btw my D102915, D103407 and D103406 are preparation to return invalid cost flag from the function and to reduce impact of the change.

[kmclaughlin]

• Changed getTypeConversion to only set the cost to Invalid for TypeScalarizeScalableVector
• Removed a failing test in AArch64SelectionDAGTest.cpp testing the "Cannot legalize this vector" assert, which has been removed.
• Removed the CHECK-NO-MAX-VSCALE RUN line from scalable-vf-hint.ll. This line used the -force-target-supports-scalable-vectors=true flag but did not enable +sve, resulting in an Invalid cost being returning in getRegUsage.

[kmclaughlin]

llvm/lib/CodeGen/TargetLoweringBase.cpp

1848–1850

Hi @dfukalov, thanks for the suggestion. I have updated this to instead set the cost to Invalid where the kind is TypeScalarizeScalableVector for now.

[sdesmalen]

llvm/lib/CodeGen/TargetLoweringBase.cpp

1848–1850

The value of Invalid is irrelevant when the Invalid flag is set. In fact, retrieving the value is not possible since InstructionCost::getValue() returns an llvm::Optional. Because there is nothing the code below can do to change the invalid cost to a valid cost, there's no reason not to break out of the loop early by returning std::make_pair(InstructionCost::getInvalid(), ..).

llvm/lib/Target/AArch64/AArch64TargetTransformInfo.cpp

1291

nit: I'd prefer for this to be written as:

if (!LT.first.isValid())
  return InstructionCost::getInvalid();
return LT.first * 2;

so it's a little more explicit that Invalid is returned.

llvm/test/Analysis/CostModel/AArch64/sve-illegal-types.ll

4

Can you structure these tests a bit more so that we check the code in TargetLoweringBase for each of the types:

nxv1i128
nxv2i128
nxv1f128
nxv2f128

using e.g. load, and then testing all the other load/store operations (store, masked.load, masked.store) with only nxv1i128.

You can also merge all the instructions into the same function, because for invoking the cost-model, it doesn't actually matter how the result values are used.

llvm/test/Transforms/LoopVectorize/AArch64/scalable-vf-hint.ll

5

Is it necessary to pipe the output to a temporary file and use a different check-prefix?

[dfukalov]

llvm/lib/CodeGen/TargetLoweringBase.cpp

1848–1850

Actually almost all operations on InstructionCost ignore invalid flag at the moment. I don't insist, just suggested to split the changes to smaller steps to reduce future side effects of a commit.

[sdesmalen]

llvm/lib/CodeGen/TargetLoweringBase.cpp

1848–1850

Perhaps I misunderstand your concern, do you mean that if InstructionCost has a value like "10" but the value has been set to 'Invalid', that the original code which called getTypeLegalizationCost will continue to operate on the value "10"? That's not really how InstructionCost works, once the value is Invalid, it will never become Valid. i.e. Invalid * 2 is still Invalid. It's also not possible to retrieve the original value "10", because InstructionCost::getValue() returns an Optional, which if the cost is Invalid, will be None.

So even if most operations on InstructionCost are not aware of the Invalid flag, they mostly just continue propagating "invalid", and this will eventually bubble up to top-level call where it needs to do somethign with the value (e.g. by calling 'getValue()''). These instances should already be able to deal with Invalid, and if it does cause a crash, then this is something we'll need to fix.

At the moment though, the only case where this patch may have an impact are with scalable vectors in combination with illegal vectors. This combination is still very experimental, so if this does end up breaking anything it just highlights something that needs fixing.

[dfukalov]

llvm/lib/CodeGen/TargetLoweringBase.cpp

1848–1850

There are a lot of places where logic is based on comparison of InstructionCost with an integer or at least between two costs. In D103406 I experimented and renamed getValue() - it's used in a few dozens places.
It seems all other code (like comparisons and arithmetic operations) still ignore invalid flag. It will be next, I guess painful, step to check invalid (and assert?) at least in comparison with integers.

As an illustration of the impact, you can check test report of the previous patch version. I don't know how many regressions will be in cases not covered with tests.

Again, I don't insist, but it seems to me if a cost model change with unpredicted regressions can be splitted to smaller patches - it would be better to split it.

[sdesmalen]

llvm/lib/CodeGen/TargetLoweringBase.cpp

1848–1850

There are a lot of places where logic is based on comparison of InstructionCost with an integer or at least between two costs. In D103406 I experimented and renamed getValue() - it's used in a few dozens places.
It seems all other code (like comparisons and arithmetic operations) still ignore invalid flag. It will be next, I guess painful, step to check invalid (and assert?) at least in comparison with integers.

InstructionCost has overloaded comparison- and arithmetic operators. The comparison operators check the Invalid flag. e.g. for some auto X = InstructionCost::(42).setInvalid();, then (X == 42) <=> false. See the implementation here: https://github.com/llvm/llvm-project/blob/d480f968ad8b56d3ee4a6b6df5532d485b0ad01e/llvm/include/llvm/Support/InstructionCost.h#L169 .

The arithmetic operators propagate the Invalid flag, so that X.isValid() == (X * 2).isValid().

As an illustration of the impact, you can check test report of the previous patch version. I don't know how many regressions will be in cases not covered with tests.

@kmclaughlin explained to me off-list that these tests needed fixing in the previous revision of the patch, and so with the current patch the tests should still pass when changing the code back to return InstructionCost::getInvalid().

Thanks for raising these concerns, it's good to check we're not missing anything. But I hope the above explains why it should be safe to return getInvalid() directly.

[kmclaughlin]

• Changed getTypeConversion back to return an invalid cost for TypeScalarizeScalableVector.
• Added tests for loads of nxv1i128, nxv2i128, nxv1f128 & nxv2f128 to sve-illegal-types.ll & grouped the instructions into fewer functions.
• Moved a failing test from test/Transforms/VectorCombine/X86/extract-cmp-binop.ll. This test uses scalable vectors and will fail in X86TTIImpl::getVectorInstrCost with the changes in this patch.

[kmclaughlin]

llvm/test/Transforms/LoopVectorize/AArch64/scalable-vf-hint.ll

5

I tried changing all CHECK-NO-MAX-VSCALEs to CHECK-NO-SVE, but this caused the test to fail. I think something like this is needed so that @test_no_sve and @test_no_max_vscale can have CHECK lines for both the output from -loop-vectorize and -pass-remarks-analysis=loop-vectorize.
I could instead add another RUN line, similar to the other tests which use the CHECK & CHECK-DBG prefixes?

[sdesmalen]

Just one final request about one of the tests, but otherwise the patch looks good to me.

llvm/unittests/CodeGen/AArch64SelectionDAGTest.cpp

576

Instead of removing the test, can you instead check that the TypeAction is ScalarizeScalableVector?

[kmclaughlin]

• Added a test to AArch64SelectionDAGTest.cpp which checks that getTypeAction returns TypeScalarizeScalableVector for an illegal type

[dfukalov]

llvm/lib/CodeGen/TargetLoweringBase.cpp

1848–1850

InstructionCost has overloaded comparison- and arithmetic operators. The comparison operators check the Invalid flag. e.g. for some auto X = InstructionCost::(42).setInvalid();, then (X == 42) <=> false.

Yes. But at the same time for some auto X = InstructionCost::(42).setInvalid(); we have funny X > 142 <=> true, since it finally calls InstructionCost(142).operator<(X) that has if (State != RHS.State) return State < RHS.State; at the start. I guess there are a lot of places with "cost > threshold" comparisons.
It seems we need to fix InstructionCost comparisons (and other operations?) before the change or we'll get side effects.

Actually I thought any operation with invalid cost should cause assert at some point in beautiful future. Am I right it was intended?

[sdesmalen]

llvm/lib/CodeGen/TargetLoweringBase.cpp

1848–1850

Yes. But at the same time for some auto X = InstructionCost::(42).setInvalid(); we have funny X > 142 <=> true, since it finally calls InstructionCost(142).operator<(X) that has if (State != RHS.State) return State < RHS.State; at the start. I guess there are a lot of places with "cost > threshold" comparisons.

That's actually a feature, not a bug :) We basically had the option of always asserting that both costs need to be valid (which would lead to lots of extra code to always guarantee this by checking X.isValid() && Y.isValid() in lots of places before being able to compare the two costs. The other option was to have a documented total ordering where Invalid is considered 'infinitely expensive' when compared with any other costs. This is useful, because in most places the comparison is there to check if the cost of "some operation" is an improvement over the cost of some other operation. And an Invalid cost can never be an improvement to a valid cost.

It seems we need to fix InstructionCost comparisons (and other operations?) before the change or we'll get side effects.

Most places have already been fixed in the passes that use InstructionCost. Perhaps there are some cases we've missed, but hopefully these show up easily enough in our testing. I expect most of these cases are actually gaps in our cost-model for scalable vectors, which is currently the only reason we ever return Invalid. For fixed-width vectors or anything else, we should always have valid costs.

[sdesmalen]

LGTM, thanks @kmclaughlin

llvm/unittests/CodeGen/AArch64SelectionDAGTest.cpp

577

nit: ElementCount::getScalable(1) is a bit more readable.

579

nit: It's better to test the result explicitly, i.e.:

EXPECT_EQ(getTypeToTransformTo(VT) == MVT::f128);