llvm dev - Feb 2017 - [Proposal][RFC] Epilog loop vectorization

Hi,

This is a proposal about epilog loop vectorization.

Currently Loop Vectorizer inserts an epilogue loop for handling loops that
don't have known iteration counts.

The Loop Vectorizer supports loops with an unknown trip count, unknown trip
count may not be a multiple of the vector width, and the vectorizer has to
execute the last few iterations as scalar code. It keeps a scalar copy of the
loop for the remaining iterations.

Loop with the large width has a high possibility of executing many scalar
iterations.
i.e. i8 data type with 256bits target register can vectorize with vector width
32, with that maximum trip count possibility for scalar(epilog) loop is 31,
which is significant & worth vectorizing.

Large vector factor has following challenges:

1)    Possibility of remainder iteration is substantial.

2)    Actual trip count at runtime is substantial but not meeting minimum trip
count to execute vector loop.

These challenges can be addressed by mask instructions, but these instructions
are limited and may not be available to all targets.

By epilog vectorization our aim to vectorize epilog loop where original loop is
vectorized with large vector factor and has a high possibility of executing
scalar iterations.

This require following changes:

1)    Costing: Preserve all profitable vector factor.

2)    Transform: Create an additional vector loop with next profitable vector
factor.

Please refer attached file (BlockLayout.png) for the details about transformed
block layout.

Patch is available at: https://reviews.llvm.org/D30247

Regards,
Ashutosh

-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20170222/19e2c18d/attachment-0001.html>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: BlockLayout.png
Type: image/png
Size: 135761 bytes
Desc: BlockLayout.png
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20170222/19e2c18d/attachment-0001.png>

Hi Ashutosh,
> On Feb 22, 2017, at 1:57 AM, Nema, Ashutosh via llvm-dev <llvm-dev at
lists.llvm.org> wrote:
> 
> Hi,
>  
> This is a proposal about epilog loop vectorization.
>  
> Currently Loop Vectorizer inserts an epilogue loop for handling loops that
don’t have known iteration counts.
>  
> The Loop Vectorizer supports loops with an unknown trip count, unknown trip
count may not be a multiple of the vector width, and the vectorizer has to
execute the last few iterations as scalar code. It keeps a scalar copy of the
loop for the remaining iterations.
>  
> Loop with the large width has a high possibility of executing many scalar
iterations.
> i.e. i8 data type with 256bits target register can vectorize with vector
width 32, with that maximum trip count possibility for scalar(epilog) loop is
31, which is significant & worth vectorizing.
>  
> Large vector factor has following challenges:
> 1)    Possibility of remainder iteration is substantial.
> 2)    Actual trip count at runtime is substantial but not meeting minimum
trip count to execute vector loop.
>  
> These challenges can be addressed by mask instructions, but these
instructions are limited and may not be available to all targets.
>  
> By epilog vectorization our aim to vectorize epilog loop where original
loop is vectorized with large vector factor and has a high possibility of
executing scalar iterations.
>  
> This require following changes:
> 1)    Costing: Preserve all profitable vector factor.
> 2)    Transform: Create an additional vector loop with next profitable
vector factor.
Is this something that you propose to be on by default for wide VPU
architectures without masking support? I.e. how widely is this applicable?   If
not then perhaps a better strategy would be to just annotate the remainder loop
with some metadata to limit the vectorization factor and just rerun the
vectorizer.

Adam
>  
> Please refer attached file (BlockLayout.png) for the details about
transformed block layout.
>  
> Patch is available at: https://reviews.llvm.org/D30247
<https://reviews.llvm.org/D30247>
>  
> Regards,
> Ashutosh
>  
> <BlockLayout.png>_______________________________________________
> LLVM Developers mailing list
> llvm-dev at lists.llvm.org <mailto:llvm-dev at lists.llvm.org>
> http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
<http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev>
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20170222/91ad63de/attachment-0001.html>

Hi,

Looks interesting!

I’m wondering about the extra cost in code-size and how much it could outweigh
the benefit?

What data can you provide on benchmarks (code size and performance)?

Thanks,

— 
Mehdi
> On Feb 22, 2017, at 1:57 AM, Nema, Ashutosh via llvm-dev <llvm-dev at
lists.llvm.org> wrote:
> 
> Hi,
>  
> This is a proposal about epilog loop vectorization.
>  
> Currently Loop Vectorizer inserts an epilogue loop for handling loops that
don’t have known iteration counts.
>  
> The Loop Vectorizer supports loops with an unknown trip count, unknown trip
count may not be a multiple of the vector width, and the vectorizer has to
execute the last few iterations as scalar code. It keeps a scalar copy of the
loop for the remaining iterations.
>  
> Loop with the large width has a high possibility of executing many scalar
iterations.
> i.e. i8 data type with 256bits target register can vectorize with vector
width 32, with that maximum trip count possibility for scalar(epilog) loop is
31, which is significant & worth vectorizing.
>  
> Large vector factor has following challenges:
> 1)    Possibility of remainder iteration is substantial.
> 2)    Actual trip count at runtime is substantial but not meeting minimum
trip count to execute vector loop.
>  
> These challenges can be addressed by mask instructions, but these
instructions are limited and may not be available to all targets.
>  
> By epilog vectorization our aim to vectorize epilog loop where original
loop is vectorized with large vector factor and has a high possibility of
executing scalar iterations.
>  
> This require following changes:
> 1)    Costing: Preserve all profitable vector factor.
> 2)    Transform: Create an additional vector loop with next profitable
vector factor.
>  
> Please refer attached file (BlockLayout.png) for the details about
transformed block layout.
>  
> Patch is available at: https://reviews.llvm.org/D30247
<https://reviews.llvm.org/D30247>
>  
> Regards,
> Ashutosh
>  
> <BlockLayout.png>_______________________________________________
> LLVM Developers mailing list
> llvm-dev at lists.llvm.org <mailto:llvm-dev at lists.llvm.org>
> http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
<http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev>
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20170222/52908138/attachment.html>

On 02/22/2017 11:52 AM, Adam Nemet via llvm-dev wrote:
> Hi Ashutosh,
>
>> On Feb 22, 2017, at 1:57 AM, Nema, Ashutosh via llvm-dev 
>> <llvm-dev at lists.llvm.org <mailto:llvm-dev at
lists.llvm.org>> wrote:
>>
>> Hi,
>> This is a proposal about epilog loop vectorization.
>> Currently Loop Vectorizer inserts an epilogue loop for handling loops 
>> that don’t have known iteration counts.
>> The Loop Vectorizer supports loops with an unknown trip count, 
>> unknown trip count may not be a multiple of the vector width, and the 
>> vectorizer has to execute the last few iterations as scalar code. It 
>> keeps a scalar copy of the loop for the remaining iterations.
>> Loop with the large width has a high possibility of executing many 
>> scalar iterations.
>> i.e. i8 data type with 256bits target register can vectorize with 
>> vector width 32, with that maximum trip count possibility for 
>> scalar(epilog) loop is 31, which is significant & worth
vectorizing.
>> Large vector factor has following challenges:
>> 1)Possibility of remainder iteration is substantial.
>> 2)Actual trip count at runtime is substantial but not meeting minimum 
>> trip count to execute vector loop.
>> These challenges can be addressed by mask instructions, but these 
>> instructions are limited and may not be available to all targets.
>> By epilog vectorization our aim to vectorize epilog loop where 
>> original loop is vectorized with large vector factor and has a high 
>> possibility of executing scalar iterations.
>> This require following changes:
>> 1)Costing: Preserve all profitable vector factor.
>> 2)Transform: Create an additional vector loop with next profitable 
>> vector factor.
>
> Is this something that you propose to be on by default for wide VPU 
> architectures without masking support? I.e. how widely is this 
> applicable?   If not then perhaps a better strategy would be to just 
> annotate the remainder loop with some metadata to limit the 
> vectorization factor and just rerun the vectorizer.
Why would this solution (annotating the remainder loop to limit 
vectorization and rerunning the vectorization process) not be preferred 
regardless?

One issue that might be relevant here are runtime aliasing checks, which 
are probably going to be redundant, or partially redundant, between the 
different vectorized versions. Will we be able to do any necessary 
cleanup after the fact? Moreover, we often don't hoist (unswitch) these 
checks out of inner loops (perhaps because they're inside the trip-count 
checks?); I wonder if the proposed block structure will make this 
situation better or worse (or have no overall effect).

Thanks again,
Hal
>
> Adam
>
>> Please refer attached file (BlockLayout.png) for the details about 
>> transformed block layout.
>> Patch is available at:https://reviews.llvm.org/D30247
>> Regards,
>> Ashutosh
>> <BlockLayout.png>_______________________________________________
>> LLVM Developers mailing list
>> llvm-dev at lists.llvm.org <mailto:llvm-dev at lists.llvm.org>
>> http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
>
>
>
> _______________________________________________
> LLVM Developers mailing list
> llvm-dev at lists.llvm.org
> http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
-- 
Hal Finkel
Lead, Compiler Technology and Programming Languages
Leadership Computing Facility
Argonne National Laboratory

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