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

[Hal Finkel via llvm-dev]

On 03/14/2017 06:09 PM, Zaks, Ayal wrote:
>
> *From:*Nema, Ashutosh [mailto:Ashutosh.Nema at amd.com]
>
> Summarizing the discussion on the implementation approaches.
>
> Discussed about two approaches, first running ‘InnerLoopVectorizer’ 
> again on the epilog loop immediately after vectorizing the original 
> loop within the same vectorization pass, the second approach where 
> re-running vectorization pass and limiting vectorization factor of 
> epilog loop by metadata.
>
> <Approach-2>
>
> Challenges with re-running the vectorizer pass:
>
> 1)Reusing alias check result:
>
> When vectorizer pass runs again it finds the epilog loop as a new loop 
> and it may generates alias check, this new alias check may overkill 
> the gains of epilog vectorization.
>
> We should use the already computed alias check result instead of re 
> computing again.
>
> Right, can this challenge be addressed – can we record the “simple” 
> fact that the epilog loop is vectorizable with trip count at-most 
> VF*UF when reached from the vectorized loop? This is akin to passing 
> similar information from the front-end when supplied by, e.g., OpenMP 
> pragmas, with the additional path-sensitive context attached.
>
> Agreed, if each loop is handled independently, the multiple 
> minimum-trip-count tests should be revisited to optimize for smallest 
> trip-count first.
>
> If the main loop was vectorized by VF and unrolled by UF>1, it may be 
> reasonable to vectorize the remainder loop with the same VF (w/o 
> unrolling).
>

I agree; this is a good point. We need to consider VF*UF and scale back 
from there.

> And then possibly vectorize the remainder of that with a smaller, say, 
> VF/2. In addition, situations having small types and large vectors may 
> result in large VF, again leaving room for possibly repeated epilog 
> vectorizations with decreasing VF’s. At some point it would be good to 
> try the alternative of a (final) masked vector epilog.
>

The follow-on to this is that we need to think carefully about how to do 
the cost modeling for this. We can't have so many checks along some 
paths that is defeats the benefit for some small loops with small trip 
counts.

  -Hal

> Ayal.
>
> 2)Rerun the vectorizer and hoist the new alias check:
>
> It’s not possible to hoist alias checks as its not fully redundant 
> (not dominated by other checks), it’s not getting execute in all paths.
>
> NOTE: We cannot prepone alias check as its expensive compared to other 
> checks.
>
> <Approach-1>
>
> 1)Current patch depends on the existing functionality of 
> LoopVectorizer, it uses ‘InnerLoopVectorizer’ again to vectorize the 
> epilog loop, as it happens in the same vectorization pass we have 
> flexibility to reuse already computed alias result check & limit 
> vectorization factor for the epilog loop.
>
> 2)It does not generate the blocks for new block layout explicitly, 
> rather it depends on ‘InnerLoopVectorizer::createEmptyLoop’ to 
> generate new block layout. The new block layout get automatically 
> generated by calling the ‘InnerLoopVectorizer:: vectorize’ again.
>
> 3)Block layout description with epilog loop vectorization is available at
>
> https://reviews.llvm.org/file/data/fxg5vx3capyj257rrn5j/PHID-FILE-x6thnbf6ub55ep5yhalu/LayoutDescription.png
>
> Approach-1 looks feasible, please comment if any objections.
>
> Regards,
>
> Ashutosh
>
> ...

-- 
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/20170314/dfafa318/attachment.html>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Type: image/jpeg
Size: 10060 bytes
Desc: not available
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20170314/dfafa318/attachment.jpe>