llvm dev - Jan 2021 - [RFC] Introduce a new stepvector operation

> On Jan 20, 2021, at 16:03, David Sherwood via llvm-dev <llvm-dev at
lists.llvm.org> wrote:
> 
> Hi,
>  
> As part of adding support for scalable vectorization we need to update
llvm::InnerLoopVectorizer::getStepVector for scalable vectors. Currently this
just returns a constant vector with the sequence <0, 1, 2, 3, ..>, however
this assumes we are using fixed length vectors. For scalable vectors we need an
operation that does the same thing, but without having to explicitly initalise
all the elements. Any new stepvector operation we provide could also be used for
fixed length vectors too if desired.
>  
> I believe the desirable properties of the operation should be:
>  
> 1. The operation requires no arguments and simply returns a vector with the
numeric sequence <0, 1, 2, …>
> 2. For types with a large number of elements, e.g. <vscale x 32 x i8>
(vscale = 16), there is the possibility of the sequence value exceeding the
limit of the type midway through the vector. In such cases we define the
operation such that those elements are undefined or poison values.
>  
> A simple ‘stepvector’ operation (however we choose to implement it) with
the properties described above can then be used together with additional ‘mul’
and ‘add’ instructions to create any arbitrary linear sequence, i.e. <0, 2,
4, 6, …> or <1, 3, 5, 7, …>
>  
> The first possible implementation with the properties as described above
involves using a new llvm.stepvector() intrinsic with no arguments that simply
returns a vector sequence <0, 1, 2, …> of the requested type, i.e.
>  
>   declare <vscale x 4 x i32> @llvm.stepvector.nxv4i32()
>  
> Introducing a new intrinsic is simple to implement and we can easily come
up with an appropriate cost model – cheap for fixed width vectors or scalable
vectors using SVE where we have the ‘index’ instruction.
Are you planning on updating the existing code that generates vector constants
to use @llvm.stepvector for fixed width vectors?
 
>  
> However, since such an intrinsic is effectively returning a constant vector
sequence we could instead implement it using a new ‘stepvector’ constant in a
similar way to how ‘zeroinitializer’ works. This would be done using a new
ConstantStepVector class similar to ConstantAggregateZero and would return a
vector with the numeric sequence <0, 1, 2, …>. The main advantages of
using a constant over an intrinsic are:
>  
> 1. It is easy to write tests in LLVM IR since ‘stepvector’ would work in
the same way as ‘zeroinitializer’, i.e. “%1 = add <4 x i32> %0,
stepvector”
> 2. Creation of the node is easy with the simple interface:
>   static Constant *ConstantStepVector::get(Type Ty)
If there’s IRBuilder::createStepVector(Ty), the creation of the intrinsic should
be also quite simple as well. A potential inconvenience of the intrinsic
compared to a constant is that we may generate redundant intrinsic calls . Not
sure how big of an issue that is going to be, but it shouldn’t be too big in
practice, as long as only a few places create step vectors.
> 3. It is easy to do optimisations, e.g. CSE, and pattern matching in IR.
I think if the intrinsic has the right attributes (e.g. readnone), things like
DCE, GVN & CSE should work automatically for the intrinsic. As for
pattern-matching, you could just add a matcher for stepvector, so patterns would
look similar regardless whether it is a constant or an intrinsic?

Given that we already have an intrinsic for vscale and there are going to be
named shuffle intrinsics for scalable vectors, having another intrinsic for
stepvector seems consistent with the previous decisions and the path of least
resistance.  Personally I am not convinced that mentioned benefits of the named
constant are worth the trouble if we still have a set of intrinsics for vscale
& the named shuffle.

Cheer,
Florian
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20210122/143cd4ea/attachment.html>

Hi Florian,

RE: “Are you planning on updating the existing code that generates vector
constants to use @llvm.stepvector for fixed width vectors?”
Are you referring to InnerLoopVectorizer::getStepVector()? I guess this might be
worthwhile for consistency and will ensure greater test coverage, provided it
doesn’t
cause regressions in code quality?

With regards to the use of constants there is currently an ongoing discussion in
another set of replies around the use of vector literals such as <0, 2, …>
or
<1, 3, …>, which you might be interested in? I agree that using an
intrinsic should
be quite straightforward, but there suggestions for changing how we deal with
shufflevectors that would make use of such vector literals.

Kind Regards,
David.

From: Florian Hahn <florian_hahn at apple.com>
Sent: 22 January 2021 12:57
To: David Sherwood <David.Sherwood at arm.com>; llvm-dev at lists.llvm.org
Subject: Re: [llvm-dev] [RFC] Introduce a new stepvector operation




On Jan 20, 2021, at 16:03, David Sherwood via llvm-dev <llvm-dev at
lists.llvm.org<mailto:llvm-dev at lists.llvm.org>> wrote:

Hi,

As part of adding support for scalable vectorization we need to update
llvm::InnerLoopVectorizer::getStepVector for scalable vectors. Currently this
just returns a constant vector with the sequence <0, 1, 2, 3, ..>, however
this assumes we are using fixed length vectors. For scalable vectors we need an
operation that does the same thing, but without having to explicitly initalise
all the elements. Any new stepvector operation we provide could also be used for
fixed length vectors too if desired.

I believe the desirable properties of the operation should be:

1. The operation requires no arguments and simply returns a vector with the
numeric sequence <0, 1, 2, …>
2. For types with a large number of elements, e.g. <vscale x 32 x i8>
(vscale = 16), there is the possibility of the sequence value exceeding the
limit of the type midway through the vector. In such cases we define the
operation such that those elements are undefined or poison values.

A simple ‘stepvector’ operation (however we choose to implement it) with the
properties described above can then be used together with additional ‘mul’ and
‘add’ instructions to create any arbitrary linear sequence, i.e. <0, 2, 4, 6,
…> or <1, 3, 5, 7, …>

The first possible implementation with the properties as described above
involves using a new llvm.stepvector() intrinsic with no arguments that simply
returns a vector sequence <0, 1, 2, …> of the requested type, i.e.

  declare <vscale x 4 x i32> @llvm.stepvector.nxv4i32()

Introducing a new intrinsic is simple to implement and we can easily come up
with an appropriate cost model – cheap for fixed width vectors or scalable
vectors using SVE where we have the ‘index’ instruction.

Are you planning on updating the existing code that generates vector constants
to use @llvm.stepvector for fixed width vectors?


However, since such an intrinsic is effectively returning a constant vector
sequence we could instead implement it using a new ‘stepvector’ constant in a
similar way to how ‘zeroinitializer’ works. This would be done using a new
ConstantStepVector class similar to ConstantAggregateZero and would return a
vector with the numeric sequence <0, 1, 2, …>. The main advantages of
using a constant over an intrinsic are:

1. It is easy to write tests in LLVM IR since ‘stepvector’ would work in the
same way as ‘zeroinitializer’, i.e. “%1 = add <4 x i32> %0, stepvector”
2. Creation of the node is easy with the simple interface:
  static Constant *ConstantStepVector::get(Type Ty)

If there’s IRBuilder::createStepVector(Ty), the creation of the intrinsic should
be also quite simple as well. A potential inconvenience of the intrinsic
compared to a constant is that we may generate redundant intrinsic calls . Not
sure how big of an issue that is going to be, but it shouldn’t be too big in
practice, as long as only a few places create step vectors.


3. It is easy to do optimisations, e.g. CSE, and pattern matching in IR.

I think if the intrinsic has the right attributes (e.g. readnone), things like
DCE, GVN & CSE should work automatically for the intrinsic. As for
pattern-matching, you could just add a matcher for stepvector, so patterns would
look similar regardless whether it is a constant or an intrinsic?

Given that we already have an intrinsic for vscale and there are going to be
named shuffle intrinsics for scalable vectors, having another intrinsic for
stepvector seems consistent with the previous decisions and the path of least
resistance.  Personally I am not convinced that mentioned benefits of the named
constant are worth the trouble if we still have a set of intrinsics for vscale
& the named shuffle.

Cheer,
Florian
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20210122/13808945/attachment.html>