llvm dev - Nov 2020 - [Proposal] Introducing the concept of invalid costs to the IR cost model

Hi,

I'd like to propose a change to our cost interfaces so that instead of
returning
an unsigned value from functions like getInstructionCost, getUserCost, etc., we
instead return a wrapper class that encodes an integer cost along with extra
state. The extra state can be used to express:

1. A cost as infinitely expensive in order to prevent certain optimisations
taking place. For example, there are already examples in LLVM where the cost is
set extremely high, but not so high that it would cause overflow. This might be
to
prevent vectorisation in cases where we would have to scalarize the operation,
which is particularly relevant for scalable vectors, where scalarisation is
not [yet] available. There isn't currently a standard value for something
that
constitutes very expensive and we can replace all the magic numbers with a
single invalid state.
2. A cost as unknown, where the user is simply unable to determine an accurate
cost for an operation.

This new wrapper class would work almost seamlessly with existing code as it
would contain the full set of operators required for arithmetic and comparisons.
This is in addition to the ability to create invalid costs and query the
validity
of an existing cost. Once a cost becomes invalid or unknown it will remain in
that
state regardless of any further arithmetic performed.

Kind Regards,
David Sherwood.

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

> On Nov 5, 2020, at 7:42 AM, David Sherwood via llvm-dev <llvm-dev at
lists.llvm.org> wrote:
> 
> Hi,
>  
> I'd like to propose a change to our cost interfaces so that instead of
returning
> an unsigned value from functions like getInstructionCost, getUserCost,
etc., we
> instead return a wrapper class that encodes an integer cost along with
extra
> state. The extra state can be used to express:
>  
> 1. A cost as infinitely expensive in order to prevent certain optimisations
> taking place. For example, there are already examples in LLVM where the
cost is
> set extremely high, but not so high that it would cause overflow. This
might be to
> prevent vectorisation in cases where we would have to scalarize the
operation,
> which is particularly relevant for scalable vectors, where scalarisation is
> not [yet] available. There isn't currently a standard value for
something that
> constitutes very expensive and we can replace all the magic numbers with a
> single invalid state.
> 2. A cost as unknown, where the user is simply unable to determine an
accurate
> cost for an operation.
>  
> This new wrapper class would work almost seamlessly with existing code as
it
> would contain the full set of operators required for arithmetic and
comparisons.
> This is in addition to the ability to create invalid costs and query the
validity
> of an existing cost. Once a cost becomes invalid or unknown it will remain
in that
> state regardless of any further arithmetic performed.
This sounds like a great step to me David,

-Chris


-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20201105/9013a862/attachment.html>

You're being quite vague about what the extra state is. Is this because you
haven't yet settled on what it should be, or do you actually intend to let
it be a template parameter:

template <typename T>
struct Cost {
  unsigned Val;
  T State;
}

Thanks,
   Christopher Tetreault

From: llvm-dev <llvm-dev-bounces at lists.llvm.org> On Behalf Of David
Sherwood via llvm-dev
Sent: Thursday, November 5, 2020 7:43 AM
To: llvm-dev at lists.llvm.org
Subject: [EXT] [llvm-dev] [Proposal] Introducing the concept of invalid costs to
the IR cost model

Hi,

I'd like to propose a change to our cost interfaces so that instead of
returning
an unsigned value from functions like getInstructionCost, getUserCost, etc., we
instead return a wrapper class that encodes an integer cost along with extra
state. The extra state can be used to express:

1. A cost as infinitely expensive in order to prevent certain optimisations
taking place. For example, there are already examples in LLVM where the cost is
set extremely high, but not so high that it would cause overflow. This might be
to
prevent vectorisation in cases where we would have to scalarize the operation,
which is particularly relevant for scalable vectors, where scalarisation is
not [yet] available. There isn't currently a standard value for something
that
constitutes very expensive and we can replace all the magic numbers with a
single invalid state.
2. A cost as unknown, where the user is simply unable to determine an accurate
cost for an operation.

This new wrapper class would work almost seamlessly with existing code as it
would contain the full set of operators required for arithmetic and comparisons.
This is in addition to the ability to create invalid costs and query the
validity
of an existing cost. Once a cost becomes invalid or unknown it will remain in
that
state regardless of any further arithmetic performed.

Kind Regards,
David Sherwood.

-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20201105/6bf4a905/attachment.html>

Hi Chris,

Thanks for the reply. My email was really to just ask if people were ok with the
idea
in principle and I kind of deliberately avoided getting into too many details at
this
point. If people are happy with the idea in principle I can push a patch up soon
that
shows what such a class could like so that people can comment on it?

Regards,
David Sherwood.

From: Chris Tetreault <ctetreau at quicinc.com>
Sent: 05 November 2020 19:23
To: David Sherwood <David.Sherwood at arm.com>; LLVM Dev <llvm-dev at
lists.llvm.org>
Subject: RE: [llvm-dev] [Proposal] Introducing the concept of invalid costs to
the IR cost model

You're being quite vague about what the extra state is. Is this because you
haven't yet settled on what it should be, or do you actually intend to let
it be a template parameter:

template <typename T>
struct Cost {
  unsigned Val;
  T State;
}

Thanks,
   Christopher Tetreault

From: llvm-dev <llvm-dev-bounces at lists.llvm.org<mailto:llvm-dev-bounces
at lists.llvm.org>> On Behalf Of David Sherwood via llvm-dev
Sent: Thursday, November 5, 2020 7:43 AM
To: llvm-dev at lists.llvm.org<mailto:llvm-dev at lists.llvm.org>
Subject: [EXT] [llvm-dev] [Proposal] Introducing the concept of invalid costs to
the IR cost model

Hi,

I'd like to propose a change to our cost interfaces so that instead of
returning
an unsigned value from functions like getInstructionCost, getUserCost, etc., we
instead return a wrapper class that encodes an integer cost along with extra
state. The extra state can be used to express:

1. A cost as infinitely expensive in order to prevent certain optimisations
taking place. For example, there are already examples in LLVM where the cost is
set extremely high, but not so high that it would cause overflow. This might be
to
prevent vectorisation in cases where we would have to scalarize the operation,
which is particularly relevant for scalable vectors, where scalarisation is
not [yet] available. There isn't currently a standard value for something
that
constitutes very expensive and we can replace all the magic numbers with a
single invalid state.
2. A cost as unknown, where the user is simply unable to determine an accurate
cost for an operation.

This new wrapper class would work almost seamlessly with existing code as it
would contain the full set of operators required for arithmetic and comparisons.
This is in addition to the ability to create invalid costs and query the
validity
of an existing cost. Once a cost becomes invalid or unknown it will remain in
that
state regardless of any further arithmetic performed.

Kind Regards,
David Sherwood.

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

Hi David,

This would be a very useful upgrade to the cost model.

One thing I want to add is that we need to be mindful of the cases where 
the cost is proportional (or inversely proportional) to the VF, for 
instance in the 
LoopVectorizationCostModel::selectVectorizationFactor(ElementCount 
MaxVF), there is a point where expected cost is divided by the VF. I 
believe there are other places where the instruction cost is dependent 
on the actual number of elements in the vector. While this is not a 
problem for fixed vectors, for scalable vectors we need to account for 
the vscale component of the VF.  I guess using the polynomial type for 
the base cost type might work.

Also, for scalable vectors, when making the cost based decision of 
whether to vectorize or not, we will need to consider the special case 
of comparing the scalable vectorization cost with the scalar loop cost, 
which is considered to be a fixed vector cost of VF=1. A simple solution 
might be to always assume that for scalable vectors, vectorization is 
always beneficial. Another option might be to assume that the vscale 
value is always at least 2, and compare the cost with the scalar loop 
based on that.

Thanks and Regards,

Vineet


On 2020-11-05 9:12 p.m., David Sherwood via llvm-dev
wrote:
>
> Hi,
>
> I'd like to propose a change to our cost interfaces so that instead of 
> returning
>
> an unsigned value from functions like getInstructionCost, getUserCost, 
> etc., we
>
> instead return a wrapper class that encodes an integer cost along with 
> extra
>
> state. The extra state can be used to express:
>
> 1. A cost as infinitely expensive in order to prevent certain 
> optimisations
>
> taking place. For example, there are already examples in LLVM where 
> the cost is
>
> set extremely high, but not so high that it would cause overflow. This 
> might be to
>
> prevent vectorisation in cases where we would have to scalarize the 
> operation,
>
> which is particularly relevant for scalable vectors, where 
> scalarisation is
>
> not [yet] available. There isn't currently a standard value for 
> something that
>
> constitutes very expensive and we can replace all the magic numbers with a
>
> single invalid state.
>
> 2. A cost as unknown, where the user is simply unable to determine an 
> accurate
>
> cost for an operation.
>
> This new wrapper class would work almost seamlessly with existing code 
> as it
>
> would contain the full set of operators required for arithmetic and 
> comparisons.
>
> This is in addition to the ability to create invalid costs and query 
> the validity
>
> of an existing cost. Once a cost becomes invalid or unknown it will 
> remain in that
>
> state regardless of any further arithmetic performed.
>
> Kind Regards,
>
> David Sherwood.
>
>
> _______________________________________________
> LLVM Developers mailing list
> llvm-dev at lists.llvm.org
> https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev

http://bsc.es/disclaimer
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20201117/e6456a0c/attachment.html>