llvm dev - Jul 2021 - LoopVectorizer: Should the cost-model be used for legalisation?

Hi,

Thanks for bringing this up!
> On Jun 10, 2021, at 21:50, Sander De Smalen <Sander.DeSmalen at
arm.com> wrote:
> 
> Hi,
> 
> Last year we added the InstructionCost class which adds the ability to
> represent that an operation cannot be costed, i.e. operations that cannot
> be expanded by the code-generator will have an invalid cost.
> 
> We started using this information in the Loop Vectorizer for scalable
> auto-vectorization. The LV has a legality- and a cost-model stage, which
are
> conceptually separate concepts with different purposes. But with the 
> introduction of having valid/invalid costs it's more inviting to use
the
> cost-model as 'legalisation', which leads us to the following
question:
> 
>   Should we be using the cost-model to do legalisation?
> 
> 'Legalisation' in this context means asking the question beforehand
if the
> code-generator can handle the IR emitted from the LV. Examples of
> operations that need such legalisation are predicated divides (at least
> until we can use the llvm.vp intrinsics), or intrinsic calls that have no
> scalable-vector equivalent. For fixed-width vectors this legalisation issue
> is mostly moot, since operations on fixed-width vectors can be scalarised.
> For scalable vectors this is neither supported nor feasible [1].
I think this is one of the key points. LoopVectorLegality at the moment is
mostly concerned whether the loop is not vectorizable due to conceptual issues
(not sure sure what the best term would be) preventing vectorization (like
unvectorizable dependences or FP constraints), not target specific instruction
legality constraints like whether there is a vector version of a given
instruction. It is also independent of any given concrete VF. IIUC this is also
not limited to predication, e.g. we also need to check whether intrinsic calls
are supported natively. Are there any others?

As you mentioned, predicated instructions that are not supported by a target can
be scalarized and predicated. Even for fixed vectors, this is quite expensive in
general, but it allows LoopVectorLegality to work mostly independently of other
target constraints and focus on general legality checks. IIUC conceptually
there’s nothing preventing us from scalarizing operations on scalable vectors in
a similar fashion, but it requires an explicit loop dependent on the vector
width at runtime and deciding the cost depends on an unknown (the target vector
width).

I don’t have any insight in hardware-specific costs for scalable vector
operations, so I can’t comment on any specifics there. I am wondering if the
following hypothetical scenario is feasible/realistic: consider a loop where all
operations expect one can be widened directly and a single operations needs
scalarizing. I would expect there to be a point where the number of widenable
operations gets large enough to offset the cost of emitting a loop to scalarize
the single operation needing predication. Granted, depending on the maximum
vector width of the hardware this number might be quite large, but I could
imagine a scenario where we want to optimize given a tighter upper bound on the
maximum vector width than allowed by the hardware spec. E.g. considering the an
upper bound of 256 for the vector width, we’d only need to execute 2 iterations
of such a loop on AArch64. It would also be interesting to get addition
perspective on the cost question from people familiar with other hardware
supporting scalable vectors.

As a side-note, there is a use of TTI in LVL, but it is rather problematic. At
the moment, LVL considers loops with non-temporal memory operations as
unvectorizable up-front, if the vector version for an arbitrary VF (in that case
2 was chosen) is illegal on the target. This has the unfortunate side effect
that using non-temporal stores flat out blocks vectorization if there’s no legal
non-temporal load/store for VF = 2, which can be very surprising to our users,
especially on AArch64 where a single element non-temporal memory operation may
not be legal to start with and non-temporal stores may be legal at higher VFs
(https://github.com/llvm/llvm-project/blob/main/llvm/lib/Transforms/Vectorize/LoopVectorizationLegality.cpp#L788
<https://github.com/llvm/llvm-project/blob/main/llvm/lib/Transforms/Vectorize/LoopVectorizationLegality.cpp#L788>).
It’s not a perfect example, illustrates one of the issues of bailing out too
early.
> This means there's the option to do one of two things:
> 
> 
> [Option 1]
> 
> Add checks to the LV legalisation to see if scalable-vectorisation is
> feasible. If so, assert the cost must be valid. Otherwise discard scalable
> VFs as possible candidates.
> * This has the benefit that the compiler can avoid
>   calculating/considering VPlans that we know cannot be costed.
> * Legalisation and cost-model keep each other in check. If something
>   cannot be costed then either the cost-model or legalisation was
>   incomplete.
> 
> 
> [Option 2]
> 
> Leave the question about legalisation to the CostModel, i.e. if the
> CostModel says that <operation> for `VF=vscale x N` is Invalid, then
avoid
> selecting that VF.
> * This has the benefit that we don't need to do work up-front to
>   discard scalable VFs, keeping the LV design simpler.
> * This makes gaps in the cost-model more difficult to spot.
> 
I think if we would support scalarization for scalable vectors via a loop, then
the cost of predicating any given instruction would not be invalid, just
possibly quite high (depending on the upper bound for the vector), right? So we
should  still be able to assert that each result != Invalid.
> Note that it's not useful to combine Option 1 and Option 2, because
having
> two ways to choose from takes away the need to do legalisation beforehand,
> and so that's basically a choice for Option 2.
> 
> Both approaches lead to the same end-result, but we currently have a few
> patches in flight that have taken Option 1, and this led to some questions
> about the approach from both Florian and David Green. So we're looking
to
> reach to a consensus and decision on what way to move forward.
I think one concern that came up during the discussion was that option 1 means
that we need to add multiple isLegalToXXX helpers to TTI, which need to be kept
in sync with the already existing cost functions. It also more closely couples
legality checks and cost-modeling. I’m not sure if/how much native predication
support will complicate things and there may be more places that need to be
taught about native predication support. I’m not saying this is a blocker, just
a trade-off to consider. Also, if we missed a case or add a new case that may
require scalarization we would need to update/add additional checks.

Cheers,
Florian


-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20210615/62bf3d39/attachment.html>

Hi Florian, Vineet,

Thanks both for your input!

From the comments here and from conversations off-list, it seems there is no
objection -and perhaps even a slight preference- to use the 'Invalid'
state of InstructionCost as a feature. That's probably also the easiest way
forward for now, since it avoids us adding all sorts of TTI methods for
legalisation that we may need to delete again later when we have a scalarization
mechanism for scalable VFs.

Assuming there is no further objection to this, we'll change our patches
that are currently on Phabricator to pursue this approach instead.

[just sharing my thoughts/understanding here]

*  Calculating a more accurate scalarization cost probably requires extending
`TTI::getScalarizationOverhead` with an extra operand to tell whether the pass
which calls the cost-function can create a scalarisation loop. If the flag is
false the cost would be Invalid, otherwise it could return some high-but-valid
cost. That's because the cost-model doesn't know whether a scalable loop
can/will be created.

*  Having a scalarization mechanism is orthogonal to the question how we
interpret Invalid costs, although it would significantly reduce the cases where
an Invalid cost occurs. If we could emit an opt-remark each time an Invalid cost
prevents vectorization, that would help identify any such cases.

* If we interpret Invalid as 'infinitely' expensive, we could remove the
calls to TTI->isLegalNTLoad/Store from LVL in favour of them having invalid
costs. Otherwise, we'd still need to fix/improve the case for the NT
loads/stores. We come across something similar for the VFDatabase, where for
some VFs a vectorised function may (not) be available, and so we'd otherwise
need to filter out + maintain a set/bitmask of feasible VFs.

> Florian Hahn wrote:
>> I don’t have any insight in hardware-specific costs for scalable vector
operations, so I can’t comment on any specifics there. I am wondering if the
following hypothetical scenario is feasible/realistic: consider a loop where all
operations expect one can be widened directly and a single operations needs
scalarizing. I would expect there to be a point where the number of widenable
operations gets large enough to offset the cost of emitting a loop to scalarize
the single operation needing predication. Granted, depending on the maximum
vector width of the hardware this number might be quite large, but I could
imagine a scenario where we want to optimize given a tighter upper bound on the
maximum vector width than allowed by the hardware spec. E.g. considering the an
upper bound of 256 for the vector width, we’d only need to execute 2 iterations
of such a loop on AArch64. It would also be interesting to get addition
perspective on the cost question from people familiar with other hardware
supporting scalable vectors.
You're right that there could be loops big enough for the scalarised
sub-loop to be negligible. Our experiments haven't really found any where
scalarisation was still beneficial, so this seems very much a corner-case. This
may be different for other architectures, although I expect that
extracting/inserting arbitrary elements from/to scalable vectors are likely to
be more expensive than for fixed-width vectors.

When we have knowledge about the bounds of vscale, we should indeed be able to
calculate a more accurate cost. The min_vscale/max_vscale IR attributes can be
used for this.
> Vineet Kumar wrote:
>>  Perhaps, the assertion we want in the legalizer is that if an
instruction is illegal then it cannot have a valid cost. A legal instruction
might still have an invalid/prohibitively expensive cost. This way we get a
model where the legalizer does a quick weed-out of illegal instructions and
cost-model can do a more fine-grained analysis.
I'm not sure if such an assert would add much value, because the cases we
try to guard against are the cases where the LV lets something through (Legal ==
true), but the code-generator can't handle them (Cost = invalid), since the
operations are considered legal unless explicitly stated otherwise.
>> When you say "at runtime no redundant work is being done",
does it mean that at the implementation level there might be some duplication of
logic?
Yes.
>> Looking at the code, the `InstructionCost` class does not yet model a
separate prohibitively-high-but-valid cost, right? IIRC, some places use a
hard-coded value to represent a high cost.
That's right. That would require saturation support in InstructionCost (i.e.
infinitely-expensive + 10 = (still) infinitely-expensive). This is something on
we haven't started on yet, but is on our wish-list.
>> Hmmm, to be honest I can't really imagine a concrete example here.
Just thinking out loud here, wondering if there be a case where a non-predicated
instruction is invalid but a VP version of it is valid, in which case the VPlan
can transform into using a VP version. May be a far-fetched example would be a
VP instruction with a fixed EVL that makes it feasible to compute its cost.
I think the other way around would be more problematic, because you could
generate a 'all true' predicate for the predicated instruction. When the
loop requires predication and there is only an unpredicated instruction
available, that might actually prevent vectorization. The VFDatabase case I
mentioned above would be such a case. If there are function calls in the scalar
loop and the VFDatabase has corresponding vector variants but only unpredicated
ones, then the predicated style of vectorization would lead to having an invalid
cost, whereas the unpredicated vector body would result in a valid cost.

Thanks,

Sander
> On 15 Jun 2021, at 12:48, Florian Hahn <florian_hahn at apple.com>
wrote:
> 
> Hi,
> 
> Thanks for bringing this up!
> 
>> On Jun 10, 2021, at 21:50, Sander De Smalen <Sander.DeSmalen at
arm.com> wrote:
>> 
>> Hi,
>> 
>> Last year we added the InstructionCost class which adds the ability to
>> represent that an operation cannot be costed, i.e. operations that
cannot
>> be expanded by the code-generator will have an invalid cost.
>> 
>> We started using this information in the Loop Vectorizer for scalable
>> auto-vectorization. The LV has a legality- and a cost-model stage,
which are
>> conceptually separate concepts with different purposes. But with the 
>> introduction of having valid/invalid costs it's more inviting to
use the
>> cost-model as 'legalisation', which leads us to the following
question:
>> 
>>   Should we be using the cost-model to do legalisation?
>> 
>> 'Legalisation' in this context means asking the question
beforehand if the
>> code-generator can handle the IR emitted from the LV. Examples of
>> operations that need such legalisation are predicated divides (at least
>> until we can use the llvm.vp intrinsics), or intrinsic calls that have
no
>> scalable-vector equivalent. For fixed-width vectors this legalisation
issue
>> is mostly moot, since operations on fixed-width vectors can be
scalarised.
>> For scalable vectors this is neither supported nor feasible [1].
> 
> I think this is one of the key points. LoopVectorLegality at the moment is
mostly concerned whether the loop is not vectorizable due to conceptual issues
(not sure sure what the best term would be) preventing vectorization (like
unvectorizable dependences or FP constraints), not target specific instruction
legality constraints like whether there is a vector version of a given
instruction. It is also independent of any given concrete VF. IIUC this is also
not limited to predication, e.g. we also need to check whether intrinsic calls
are supported natively. Are there any others?
> 
> As you mentioned, predicated instructions that are not supported by a
target can be scalarized and predicated. Even for fixed vectors, this is quite
expensive in general, but it allows LoopVectorLegality to work mostly
independently of other target constraints and focus on general legality checks.
IIUC conceptually there’s nothing preventing us from scalarizing operations on
scalable vectors in a similar fashion, but it requires an explicit loop
dependent on the vector width at runtime and deciding the cost depends on an
unknown (the target vector width).
> 
> I don’t have any insight in hardware-specific costs for scalable vector
operations, so I can’t comment on any specifics there. I am wondering if the
following hypothetical scenario is feasible/realistic: consider a loop where all
operations expect one can be widened directly and a single operations needs
scalarizing. I would expect there to be a point where the number of widenable
operations gets large enough to offset the cost of emitting a loop to scalarize
the single operation needing predication. Granted, depending on the maximum
vector width of the hardware this number might be quite large, but I could
imagine a scenario where we want to optimize given a tighter upper bound on the
maximum vector width than allowed by the hardware spec. E.g. considering the an
upper bound of 256 for the vector width, we’d only need to execute 2 iterations
of such a loop on AArch64. It would also be interesting to get addition
perspective on the cost question from people familiar with other hardware
supporting scalable vectors.
> 
> As a side-note, there is a use of TTI in LVL, but it is rather problematic.
At the moment, LVL considers loops with non-temporal memory operations as
unvectorizable up-front, if the vector version for an arbitrary VF (in that case
2 was chosen) is illegal on the target. This has the unfortunate side effect
that using non-temporal stores flat out blocks vectorization if there’s no legal
non-temporal load/store for VF = 2, which can be very surprising to our users,
especially on AArch64 where a single element non-temporal memory operation may
not be legal to start with and non-temporal stores may be legal at higher VFs
(https://github.com/llvm/llvm-project/blob/main/llvm/lib/Transforms/Vectorize/LoopVectorizationLegality.cpp#L788).
It’s not a perfect example, illustrates one of the issues of bailing out too
early.
> 
>> This means there's the option to do one of two things:
>> 
>> 
>> [Option 1]
>> 
>> Add checks to the LV legalisation to see if scalable-vectorisation is
>> feasible. If so, assert the cost must be valid. Otherwise discard
scalable
>> VFs as possible candidates.
>> * This has the benefit that the compiler can avoid
>>   calculating/considering VPlans that we know cannot be costed.
>> * Legalisation and cost-model keep each other in check. If something
>>   cannot be costed then either the cost-model or legalisation was
>>   incomplete.
>> 
>> 
>> [Option 2]
>> 
>> Leave the question about legalisation to the CostModel, i.e. if the
>> CostModel says that <operation> for `VF=vscale x N` is Invalid,
then avoid
>> selecting that VF.
>> * This has the benefit that we don't need to do work up-front to
>>   discard scalable VFs, keeping the LV design simpler.
>> * This makes gaps in the cost-model more difficult to spot.
>> 
> 
> I think if we would support scalarization for scalable vectors via a loop,
then the cost of predicating any given instruction would not be invalid, just
possibly quite high (depending on the upper bound for the vector), right? So we
should  still be able to assert that each result != Invalid.
> 
>> Note that it's not useful to combine Option 1 and Option 2, because
having
>> two ways to choose from takes away the need to do legalisation
beforehand,
>> and so that's basically a choice for Option 2.
>> 
>> Both approaches lead to the same end-result, but we currently have a
few
>> patches in flight that have taken Option 1, and this led to some
questions
>> about the approach from both Florian and David Green. So we're
looking to
>> reach to a consensus and decision on what way to move forward.
> 
> I think one concern that came up during the discussion was that option 1
means that we need to add multiple isLegalToXXX helpers to TTI, which need to be
kept in sync with the already existing cost functions. It also more closely
couples legality checks and cost-modeling. I’m not sure if/how much native
predication support will complicate things and there may be more places that
need to be taught about native predication support. I’m not saying this is a
blocker, just a trade-off to consider. Also, if we missed a case or add a new
case that may require scalarization we would need to update/add additional
checks.
> 
> Cheers,
> Florian

> On Jun 24, 2021, at 16:12, Sander De Smalen <Sander.DeSmalen at
arm.com> wrote:
> 
> Hi Florian, Vineet,
> 
> Thanks both for your input!
> 
> From the comments here and from conversations off-list, it seems there is
no objection -and perhaps even a slight preference- to use the 'Invalid'
state of InstructionCost as a feature. That's probably also the easiest way
forward for now, since it avoids us adding all sorts of TTI methods for
legalisation that we may need to delete again later when we have a scalarization
mechanism for scalable VFs.
> 
> Assuming there is no further objection to this, we'll change our
patches that are currently on Phabricator to pursue this approach instead.

Sounds good to me, thanks! Is this approach suitable for all current patches
in-flight you mentioned that deal with constructs/types that are not legal with
scalable vectors on AArch64?

AFAICT those in-flight patches include some of the patches below?

https://reviews.llvm.org/D102253 <https://reviews.llvm.org/D102253>
https://reviews.llvm.org/D102394 <https://reviews.llvm.org/D102394>
https://reviews.llvm.org/D101916 <https://reviews.llvm.org/D101916>

Cheers,
Florian
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20210701/83f6ebbc/attachment.html>