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

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.

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.

[cid:image003.jpg at 01D29CF1.122287F0]

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


From: Nema, Ashutosh
Sent: Wednesday, March 1, 2017 10:42 AM
To: 'Daniel Berlin' <dberlin at dberlin.org>
Cc: anemet at apple.com; Hal Finkel <hfinkel at anl.gov>; Zaks, Ayal
<ayal.zaks at intel.com>; Renato Golin <renato.golin at linaro.org>;
mkuper at google.com; Mehdi Amini <mehdi.amini at apple.com>; llvm-dev
<llvm-dev at lists.llvm.org>
Subject: RE: [llvm-dev] [Proposal][RFC] Epilog loop vectorization

Sorry I misunderstood, gvn/newgvn/gvnhoist cannot help here as these checks are
not dominated by all paths.

Regards,
Ashutosh

From: Daniel Berlin [mailto:dberlin at dberlin.org]
Sent: Tuesday, February 28, 2017 6:58 PM
To: Nema, Ashutosh <Ashutosh.Nema at amd.com<mailto:Ashutosh.Nema at
amd.com>>
Cc: anemet at apple.com<mailto:anemet at apple.com>; Hal Finkel
<hfinkel at anl.gov<mailto:hfinkel at anl.gov>>; Zaks, Ayal
<ayal.zaks at intel.com<mailto:ayal.zaks at intel.com>>; Renato
Golin <renato.golin at linaro.org<mailto:renato.golin at
linaro.org>>; mkuper at google.com<mailto:mkuper at google.com>;
Mehdi Amini <mehdi.amini at apple.com<mailto:mehdi.amini at
apple.com>>; llvm-dev <llvm-dev at lists.llvm.org<mailto:llvm-dev at
lists.llvm.org>>
Subject: Re: [llvm-dev] [Proposal][RFC] Epilog loop vectorization

Hoisting or removing?
Neither pass does hoisting, you'd need gvnhoist for that.

Even then:
Staring at your example, none of the checks are fully redundant  (IE they are
not dominated by other checks) or execute on all paths.

Thus, hoisting them  would be purely speculative code motion, which none of our
passes do.

If you would like these sets of checks to be removed, you would need to place
them in a place that they execute unconditionally.

Otherwise, this is not a standard code hoisting/removal transform.

The only redundancy i can see here at all is the repeated getelementptr
computation.
If you move it to the preheader, it will be eliminated.
Otherwise, none of the checks are redundant.

What would you hope to happen in this case?

On Tue, Feb 28, 2017 at 5:09 AM, Nema, Ashutosh <Ashutosh.Nema at
amd.com<mailto:Ashutosh.Nema at amd.com>> wrote:
I have tried running both gvn and newgvn but it did not helped in hoisting the
alias checks:

Please check, maybe I have missed something.

<TestCase>
void foo (char *A, char *B, char *C, int len) {
  int i = 0;
  for (i=0 ; i< len; i++)
    A[i] = B[i] + C[i];
}

<Command>
  $ opt –O3 –gvn test.ll –o test.opt.ll
  $ opt –O3 –newgvn test.ll –o test.opt.ll

“test.ll” is attached, it got already vectorized by the approach running
vectorizer twice by annotate the remainder loop with metadata to limit the
vectorization factor for epilog vector loop.

Regards,
Ashutosh

From: anemet at apple.com<mailto:anemet at apple.com> [mailto:anemet at
apple.com<mailto:anemet at apple.com>]
Sent: Tuesday, February 28, 2017 1:33 AM
To: Hal Finkel <hfinkel at anl.gov<mailto:hfinkel at anl.gov>>
Cc: Daniel Berlin <dberlin at dberlin.org<mailto:dberlin at
dberlin.org>>; Nema, Ashutosh <Ashutosh.Nema at
amd.com<mailto:Ashutosh.Nema at amd.com>>; Zaks, Ayal <ayal.zaks at
intel.com<mailto:ayal.zaks at intel.com>>; Renato Golin
<renato.golin at linaro.org<mailto:renato.golin at linaro.org>>;
mkuper at google.com<mailto:mkuper at google.com>; Mehdi Amini
<mehdi.amini at apple.com<mailto:mehdi.amini at apple.com>>;
llvm-dev <llvm-dev at lists.llvm.org<mailto:llvm-dev at
lists.llvm.org>>
Subject: Re: [llvm-dev] [Proposal][RFC] Epilog loop vectorization


On Feb 27, 2017, at 12:01 PM, Hal Finkel <hfinkel at
anl.gov<mailto:hfinkel at anl.gov>> wrote:


On 02/27/2017 01:47 PM, Daniel Berlin wrote:


On Mon, Feb 27, 2017 at 11:29 AM, Adam Nemet <anemet at
apple.com<mailto:anemet at apple.com>> wrote:

On Feb 27, 2017, at 10:11 AM, Hal Finkel <hfinkel at
anl.gov<mailto:hfinkel at anl.gov>> wrote:


On 02/27/2017 11:47 AM, Adam Nemet wrote:

On Feb 27, 2017, at 9:39 AM, Daniel Berlin <dberlin at
dberlin.org<mailto:dberlin at dberlin.org>> wrote:



On Mon, Feb 27, 2017 at 9:29 AM, Adam Nemet <anemet at
apple.com<mailto:anemet at apple.com>> wrote:

On Feb 27, 2017, at 7:27 AM, Hal Finkel <hfinkel at anl.gov<mailto:hfinkel
at anl.gov>> wrote:


On 02/27/2017 06:29 AM, Nema, Ashutosh wrote:
Thanks for looking into this.

1) Issues with re running vectorizer:
Vectorizer might generate redundant alias checks while vectorizing epilog loop.
Redundant alias checks are expensive, we like to reuse the results of already
computed alias checks.
With metadata we can limit the width of epilog loop, but not sure about reusing
alias check result.
Any thoughts on rerunning vectorizer with reusing the alias check result ?

One way of looking at this is: Reusing the alias-check result is really just a
conditional propagation problem; if we don't already have an optimization
that can combine these after the fact, then we should.

+Danny

Isn’t Extended SSA supposed to help with this?

Yes, it will solve this with no issue already.  GVN probably does already too.

even if if you have

if (a == b)
if (a == c)
 if (a == d)
 if (a == e)
 if (a == g)


and  we can prove a ... g equivalent, newgvn will eliminate them all and set all
the branches true.

If you need a simpler clean up pass, we could run it on sub-graphs.

Yes we probably don’t want to run a full GVN after the “loop-scheduling” passes.

FWIW, we could, just without the memory-dependence analysis enabled (i.e. set
the NoLoads constructor parameter to true). GVN is pretty fast in that mode.

OK.  Another data point is that I’ve seen cases in the past where the alias
checks required for the loop passes could enable GVN to remove redundant
loads/stores.  Currently we can only pick these up with LTO when GVN is rerun.

This is just GVN brokenness, newgvn should not have this problem.
If it does, i'd love to see it.

I thought that the problem is that we just don't run GVN after that point in
the pipeline.

Yeah, that is the problem but I think Danny misunderstood what I was trying to
say.

This was a datapoint to possibly rerun GVN with memory-awareness.


 -Hal

(I'm working on the last few parts of turning it on by default, but it
requires a new getModRefInfo interface to be able to get the last few testcases)



--

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/6b274a3b/attachment-0001.html>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: image003.jpg
Type: image/jpeg
Size: 18444 bytes
Desc: image003.jpg
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20170314/6b274a3b/attachment-0001.jpg>

On 03/14/2017 08:00 AM, Nema, Ashutosh wrote:
>
> 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.
>
> 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.
>
I think think this is reasonable. One thing: In the proposed block 
layout, if the alias check fails, we jump to the  "Min Iter Check 2". 
 From there we re-check the alias-check result (which will be false 
again), and then jump to the scalar loop. This is one more branch than 
necessary in the case where the alias check fails. If the alias check 
fails, we should jump directly to the scalar loop.

Thanks again,
Hal
> Regards,
>
> Ashutosh
>
> *From:*Nema, Ashutosh
> *Sent:* Wednesday, March 1, 2017 10:42 AM
> *To:* 'Daniel Berlin' <dberlin at dberlin.org>
> *Cc:* anemet at apple.com; Hal Finkel <hfinkel at anl.gov>; Zaks,
Ayal
> <ayal.zaks at intel.com>; Renato Golin <renato.golin at
linaro.org>;
> mkuper at google.com; Mehdi Amini <mehdi.amini at apple.com>;
llvm-dev
> <llvm-dev at lists.llvm.org>
> *Subject:* RE: [llvm-dev] [Proposal][RFC] Epilog loop vectorization
>
> Sorry I misunderstood, gvn/newgvn/gvnhoist cannot help here as these 
> checks are not dominated by all paths.
>
> Regards,
>
> Ashutosh
>
> *From:*Daniel Berlin [mailto:dberlin at dberlin.org]
> *Sent:* Tuesday, February 28, 2017 6:58 PM
> *To:* Nema, Ashutosh <Ashutosh.Nema at amd.com 
> <mailto:Ashutosh.Nema at amd.com>>
> *Cc:* anemet at apple.com <mailto:anemet at apple.com>; Hal Finkel 
> <hfinkel at anl.gov <mailto:hfinkel at anl.gov>>; Zaks, Ayal 
> <ayal.zaks at intel.com <mailto:ayal.zaks at intel.com>>;
Renato Golin
> <renato.golin at linaro.org <mailto:renato.golin at
linaro.org>>;
> mkuper at google.com <mailto:mkuper at google.com>; Mehdi Amini 
> <mehdi.amini at apple.com <mailto:mehdi.amini at apple.com>>;
llvm-dev
> <llvm-dev at lists.llvm.org <mailto:llvm-dev at
lists.llvm.org>>
> *Subject:* Re: [llvm-dev] [Proposal][RFC] Epilog loop vectorization
>
> Hoisting or removing?
> Neither pass does hoisting, you'd need gvnhoist for that.
>
> Even then:
> Staring at your example, none of the checks are fully redundant  (IE 
> they are not dominated by other checks) or execute on all paths.
>
> Thus, hoisting them  would be purely speculative code motion, which 
> none of our passes do.
>
> If you would like these sets of checks to be removed, you would need 
> to place them in a place that they execute unconditionally.
>
> Otherwise, this is not a standard code hoisting/removal transform.
>
> The only redundancy i can see here at all is the repeated 
> getelementptr computation.
>
> If you move it to the preheader, it will be eliminated.
>
> Otherwise, none of the checks are redundant.
>
>
> What would you hope to happen in this case?
>
> On Tue, Feb 28, 2017 at 5:09 AM, Nema, Ashutosh <Ashutosh.Nema at
amd.com
> <mailto:Ashutosh.Nema at amd.com>> wrote:
>
>     I have tried running both gvn and newgvn but it did not helped in
>     hoisting the alias checks:
>
>     Please check, maybe I have missed something.
>
>     <TestCase>
>
>     void foo (char *A, char *B, char *C, int len) {
>
>     int i = 0;
>
>     for (i=0 ; i< len; i++)
>
>     A[i] = B[i] + C[i];
>
>     }
>
>     <Command>
>
>     $ opt –O3 –gvn test.ll –o test.opt.ll
>
>     $ opt –O3 –newgvn test.ll –o test.opt.ll
>
>     “test.ll” is attached, it got already vectorized by the approach
>     running vectorizer twice by annotate the remainder loop with
>     metadata to limit the vectorization factor for epilog vector loop.
>
>     Regards,
>
>     Ashutosh
>
>     *From:*anemet at apple.com <mailto:anemet at apple.com>
>     [mailto:anemet at apple.com <mailto:anemet at apple.com>]
>     *Sent:* Tuesday, February 28, 2017 1:33 AM
>     *To:* Hal Finkel <hfinkel at anl.gov <mailto:hfinkel at
anl.gov>>
>     *Cc:* Daniel Berlin <dberlin at dberlin.org
>     <mailto:dberlin at dberlin.org>>; Nema, Ashutosh
>     <Ashutosh.Nema at amd.com <mailto:Ashutosh.Nema at
amd.com>>; Zaks, Ayal
>     <ayal.zaks at intel.com <mailto:ayal.zaks at intel.com>>;
Renato Golin
>     <renato.golin at linaro.org <mailto:renato.golin at
linaro.org>>;
>     mkuper at google.com <mailto:mkuper at google.com>; Mehdi Amini
>     <mehdi.amini at apple.com <mailto:mehdi.amini at
apple.com>>; llvm-dev
>     <llvm-dev at lists.llvm.org <mailto:llvm-dev at
lists.llvm.org>>
>     *Subject:* Re: [llvm-dev] [Proposal][RFC] Epilog loop vectorization
>
>         On Feb 27, 2017, at 12:01 PM, Hal Finkel <hfinkel at anl.gov
>         <mailto:hfinkel at anl.gov>> wrote:
>
>         On 02/27/2017 01:47 PM, Daniel Berlin wrote:
>
>             On Mon, Feb 27, 2017 at 11:29 AM, Adam Nemet
>             <anemet at apple.com <mailto:anemet at apple.com>>
wrote:
>
>                     On Feb 27, 2017, at 10:11 AM, Hal Finkel
>                     <hfinkel at anl.gov <mailto:hfinkel at
anl.gov>> wrote:
>
>                     On 02/27/2017 11:47 AM, Adam Nemet wrote:
>
>                             On Feb 27, 2017, at 9:39 AM, Daniel Berlin
>                             <dberlin at dberlin.org
>                             <mailto:dberlin at dberlin.org>>
wrote:
>
>                             On Mon, Feb 27, 2017 at 9:29 AM, Adam
>                             Nemet <anemet at apple.com
>                             <mailto:anemet at apple.com>> wrote:
>
>                                     On Feb 27, 2017, at 7:27 AM, Hal
>                                     Finkel <hfinkel at anl.gov
>                                     <mailto:hfinkel at anl.gov>>
wrote:
>
>
>                                     On 02/27/2017 06:29 AM, Nema,
>                                     Ashutosh wrote:
>
>                                         Thanks for looking into this.
>
>                                         1) Issues with re running
>                                         vectorizer:
>
>                                         Vectorizer might generate
>                                         redundant alias checks while
>                                         vectorizing epilog loop.
>
>                                         Redundant alias checks are
>                                         expensive, we like to reuse
>                                         the results of already
>                                         computed alias checks.
>
>                                         With metadata we can limit the
>                                         width of epilog loop, but not
>                                         sure about reusing alias check
>                                         result.
>
>                                         Any thoughts on rerunning
>                                         vectorizer with reusing the
>                                         alias check result ?
>
>
>                                     One way of looking at this is:
>                                     Reusing the alias-check result is
>                                     really just a conditional
>                                     propagation problem; if we don't
>                                     already have an optimization that
>                                     can combine these after the fact,
>                                     then we should.
>
>                                 +Danny
>
>                                 Isn’t Extended SSA supposed to help
>                                 with this?
>
>                             Yes, it will solve this with no issue
>                             already.  GVN probably does already too.
>
>                             even if if you have
>
>                             if (a == b)
>
>                             if (a == c)
>
>                              if (a == d)
>
>                              if (a == e)
>
>                              if (a == g)
>
>                             and  we can prove a ... g equivalent,
>                             newgvn will eliminate them all and set all
>                             the branches true.
>
>                             If you need a simpler clean up pass, we
>                             could run it on sub-graphs.
>
>                         Yes we probably don’t want to run a full GVN
>                         after the “loop-scheduling” passes.
>
>
>                     FWIW, we could, just without the memory-dependence
>                     analysis enabled (i.e. set the NoLoads constructor
>                     parameter to true). GVN is pretty fast in that mode.
>
>                 OK. Another data point is that I’ve seen cases in the
>                 past where the alias checks required for the loop
>                 passes could enable GVN to remove redundant
>                 loads/stores.  Currently we can only pick these up
>                 with LTO when GVN is rerun.
>
>             This is just GVN brokenness, newgvn should not have this
>             problem.
>
>             If it does, i'd love to see it.
>
>
>         I thought that the problem is that we just don't run GVN after
>         that point in the pipeline.
>
>     Yeah, that is the problem but I think Danny misunderstood what I
>     was trying to say.
>
>     This was a datapoint to possibly rerun GVN with memory-awareness.
>
>
>          -Hal
>
>             (I'm working on the last few parts of turning it on by
>             default, but it requires a new getModRefInfo interface to
>             be able to get the last few testcases)
>
>         -- 
>
>         Hal Finkel
>
>         Lead, Compiler Technology and Programming Languages
>
>         Leadership Computing Facility
>
>         Argonne National Laboratory
>
-- 
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/ae8a5aaa/attachment-0001.html>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Type: image/jpeg
Size: 18444 bytes
Desc: not available
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20170314/ae8a5aaa/attachment-0001.jpe>

> On Mar 14, 2017, at 6:00 AM, Nema, Ashutosh <Ashutosh.Nema at
amd.com> wrote:
> 
> 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.
> 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.
>  

I don’t understand. Looks like you have the same alias checks for the epilog
loop too.  How is this CFG different from the re-vectorization of the scalar
loop?  Would be good to have both CFGs here and highlighting the difference.

I thought that the whole point was that *if* you reached the epilog vector loop
via the first vector loop, you want to bypass the alias checks before the epilog
vector.

I still don’t understand why that’s not possible with some sophisticated
predicate propagation independent from the vectorizer.  I am not saying it’s
already possible but it should be.

Adam

>  
> 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
<https://reviews.llvm.org/file/data/fxg5vx3capyj257rrn5j/PHID-FILE-x6thnbf6ub55ep5yhalu/LayoutDescription.png>
>  
> Approach-1 looks feasible, please comment if any objections.
>  
> Regards,
> Ashutosh
>  
>  
> From: Nema, Ashutosh 
> Sent: Wednesday, March 1, 2017 10:42 AM
> To: 'Daniel Berlin' <dberlin at dberlin.org <mailto:dberlin
at dberlin.org>>
> Cc: anemet at apple.com <mailto:anemet at apple.com>; Hal Finkel
<hfinkel at anl.gov <mailto:hfinkel at anl.gov>>; Zaks, Ayal
<ayal.zaks at intel.com <mailto:ayal.zaks at intel.com>>; Renato
Golin <renato.golin at linaro.org <mailto:renato.golin at
linaro.org>>; mkuper at google.com <mailto:mkuper at google.com>;
Mehdi Amini <mehdi.amini at apple.com <mailto:mehdi.amini at
apple.com>>; llvm-dev <llvm-dev at lists.llvm.org <mailto:llvm-dev
at lists.llvm.org>>
> Subject: RE: [llvm-dev] [Proposal][RFC] Epilog loop vectorization
>  
> Sorry I misunderstood, gvn/newgvn/gvnhoist cannot help here as these checks
are not dominated by all paths.
>  
> Regards,
> Ashutosh
>  
> From: Daniel Berlin [mailto:dberlin at dberlin.org <mailto:dberlin at
dberlin.org>]
> Sent: Tuesday, February 28, 2017 6:58 PM
> To: Nema, Ashutosh <Ashutosh.Nema at amd.com <mailto:Ashutosh.Nema at
amd.com>>
> Cc: anemet at apple.com <mailto:anemet at apple.com>; Hal Finkel
<hfinkel at anl.gov <mailto:hfinkel at anl.gov>>; Zaks, Ayal
<ayal.zaks at intel.com <mailto:ayal.zaks at intel.com>>; Renato
Golin <renato.golin at linaro.org <mailto:renato.golin at
linaro.org>>; mkuper at google.com <mailto:mkuper at google.com>;
Mehdi Amini <mehdi.amini at apple.com <mailto:mehdi.amini at
apple.com>>; llvm-dev <llvm-dev at lists.llvm.org <mailto:llvm-dev
at lists.llvm.org>>
> Subject: Re: [llvm-dev] [Proposal][RFC] Epilog loop vectorization
>  
> Hoisting or removing?
> Neither pass does hoisting, you'd need gvnhoist for that.
>  
> Even then:
> Staring at your example, none of the checks are fully redundant  (IE they
are not dominated by other checks) or execute on all paths.
>  
> Thus, hoisting them  would be purely speculative code motion, which none of
our passes do.
>  
> If you would like these sets of checks to be removed, you would need to
place them in a place that they execute unconditionally.
>  
> Otherwise, this is not a standard code hoisting/removal transform.
>  
> The only redundancy i can see here at all is the repeated getelementptr
computation.
> If you move it to the preheader, it will be eliminated.
> Otherwise, none of the checks are redundant.
> 
> What would you hope to happen in this case?
>  
> On Tue, Feb 28, 2017 at 5:09 AM, Nema, Ashutosh <Ashutosh.Nema at
amd.com <mailto:Ashutosh.Nema at amd.com>> wrote:
> I have tried running both gvn and newgvn but it did not helped in hoisting
the alias checks:
>  
> Please check, maybe I have missed something.
>  
> <TestCase>
> void foo (char *A, char *B, char *C, int len) {
>   int i = 0;
>   for (i=0 ; i< len; i++)
>     A[i] = B[i] + C[i];
> }
>  
> <Command>
>   $ opt –O3 –gvn test.ll –o test.opt.ll
>   $ opt –O3 –newgvn test.ll –o test.opt.ll
>  
> “test.ll” is attached, it got already vectorized by the approach running
vectorizer twice by annotate the remainder loop with metadata to limit the
vectorization factor for epilog vector loop.
>  
> Regards,
> Ashutosh
>  
> From: anemet at apple.com <mailto:anemet at apple.com> [mailto:anemet
at apple.com <mailto:anemet at apple.com>]
> Sent: Tuesday, February 28, 2017 1:33 AM
> To: Hal Finkel <hfinkel at anl.gov <mailto:hfinkel at anl.gov>>
> Cc: Daniel Berlin <dberlin at dberlin.org <mailto:dberlin at
dberlin.org>>; Nema, Ashutosh <Ashutosh.Nema at amd.com
<mailto:Ashutosh.Nema at amd.com>>; Zaks, Ayal <ayal.zaks at
intel.com <mailto:ayal.zaks at intel.com>>; Renato Golin
<renato.golin at linaro.org <mailto:renato.golin at linaro.org>>;
mkuper at google.com <mailto:mkuper at google.com>; Mehdi Amini
<mehdi.amini at apple.com <mailto:mehdi.amini at apple.com>>;
llvm-dev <llvm-dev at lists.llvm.org <mailto:llvm-dev at
lists.llvm.org>>
> Subject: Re: [llvm-dev] [Proposal][RFC] Epilog loop vectorization
>  
>  
> On Feb 27, 2017, at 12:01 PM, Hal Finkel <hfinkel at anl.gov
<mailto:hfinkel at anl.gov>> wrote:
>  
>  
> On 02/27/2017 01:47 PM, Daniel Berlin wrote:
>  
>  
> On Mon, Feb 27, 2017 at 11:29 AM, Adam Nemet <anemet at apple.com
<mailto:anemet at apple.com>> wrote:
>  
> On Feb 27, 2017, at 10:11 AM, Hal Finkel <hfinkel at anl.gov
<mailto:hfinkel at anl.gov>> wrote:
>  
>  
> On 02/27/2017 11:47 AM, Adam Nemet wrote:
>  
> On Feb 27, 2017, at 9:39 AM, Daniel Berlin <dberlin at dberlin.org
<mailto:dberlin at dberlin.org>> wrote:
>  
>  
>  
> On Mon, Feb 27, 2017 at 9:29 AM, Adam Nemet <anemet at apple.com
<mailto:anemet at apple.com>> wrote:
>  
> On Feb 27, 2017, at 7:27 AM, Hal Finkel <hfinkel at anl.gov
<mailto:hfinkel at anl.gov>> wrote:
>  
> 
> On 02/27/2017 06:29 AM, Nema, Ashutosh wrote:
> Thanks for looking into this.
>  
> 1) Issues with re running vectorizer:
> Vectorizer might generate redundant alias checks while vectorizing epilog
loop.
> Redundant alias checks are expensive, we like to reuse the results of
already computed alias checks.
> With metadata we can limit the width of epilog loop, but not sure about
reusing alias check result.
> Any thoughts on rerunning vectorizer with reusing the alias check result ?
> 
> One way of looking at this is: Reusing the alias-check result is really
just a conditional propagation problem; if we don't already have an
optimization that can combine these after the fact, then we should.
>  
> +Danny
>  
> Isn’t Extended SSA supposed to help with this?
>  
> Yes, it will solve this with no issue already.  GVN probably does already
too.
>  
> even if if you have
>  
> if (a == b)
> if (a == c)
>  if (a == d)
>  if (a == e)
>  if (a == g)
>  
>  
> and  we can prove a ... g equivalent, newgvn will eliminate them all and
set all the branches true.
>  
> If you need a simpler clean up pass, we could run it on sub-graphs.
>  
> Yes we probably don’t want to run a full GVN after the “loop-scheduling”
passes.
> 
> FWIW, we could, just without the memory-dependence analysis enabled (i.e.
set the NoLoads constructor parameter to true). GVN is pretty fast in that mode.
>  
> OK.  Another data point is that I’ve seen cases in the past where the alias
checks required for the loop passes could enable GVN to remove redundant
loads/stores.  Currently we can only pick these up with LTO when GVN is rerun.
>  
> This is just GVN brokenness, newgvn should not have this problem.
> If it does, i'd love to see it.
> 
> I thought that the problem is that we just don't run GVN after that
point in the pipeline.
>  
> Yeah, that is the problem but I think Danny misunderstood what I was trying
to say.
>  
> This was a datapoint to possibly rerun GVN with memory-awareness.
>  
> 
> 
>  -Hal
> 
>  
> (I'm working on the last few parts of turning it on by default, but it
requires a new getModRefInfo interface to be able to get the last few testcases)
>  
>  
> 
> -- 
> 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/6276eebc/attachment-0001.html>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: image003.jpg
Type: image/jpeg
Size: 18444 bytes
Desc: not available
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20170314/6276eebc/attachment-0001.jpg>

On 03/14/2017 11:21 AM, Adam Nemet wrote:
>
>> On Mar 14, 2017, at 6:00 AM, Nema, Ashutosh <Ashutosh.Nema at
amd.com
>> <mailto:Ashutosh.Nema at amd.com>> wrote:
>>
>> 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.
>> 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.
>
>
> I don’t understand. Looks like you have the same alias checks for the 
> epilog loop too.  How is this CFG different from the re-vectorization 
> of the scalar loop?
You're looking at the wrong thing. This *is* the image from 
re-vectorization. The other image (linked below in step (3)) shows the 
other option.
>  Would be good to have both CFGs here and highlighting the difference.
>
> I thought that the whole point was that *if* you reached the epilog 
> vector loop via the first vector loop, you want to bypass the alias 
> checks before the epilog vector.
Yes, but, that's not quite true now. You can also reach the epilogue 
loop if you fail the min-trip-count check, and so you don't know 
anything about the aliasing checks.

  -Hal
>
> I still don’t understand why that’s not possible with some 
> sophisticated predicate propagation independent from the vectorizer. 
>  I am not saying it’s already possible but it should be.
>
> Adam
>
>
>> 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
>> *From:*Nema, Ashutosh
>> *Sent:*Wednesday, March 1, 2017 10:42 AM
>> *To:*'Daniel Berlin' <dberlin at dberlin.org
<mailto:dberlin at dberlin.org>>
>> *Cc:*anemet at apple.com <mailto:anemet at apple.com>; Hal Finkel
>> <hfinkel at anl.gov <mailto:hfinkel at anl.gov>>; Zaks,
Ayal
>> <ayal.zaks at intel.com <mailto:ayal.zaks at intel.com>>;
Renato Golin
>> <renato.golin at linaro.org 
>> <mailto:renato.golin at linaro.org>>;mkuper at google.com 
>> <mailto:mkuper at google.com>; Mehdi Amini <mehdi.amini at
apple.com
>> <mailto:mehdi.amini at apple.com>>; llvm-dev <llvm-dev at
lists.llvm.org
>> <mailto:llvm-dev at lists.llvm.org>>
>> *Subject:*RE: [llvm-dev] [Proposal][RFC] Epilog loop vectorization
>> Sorry I misunderstood, gvn/newgvn/gvnhoist cannot help here as these 
>> checks are not dominated by all paths.
>> Regards,
>> Ashutosh
>> *From:*Daniel Berlin [mailto:dberlin at dberlin.org]
>> *Sent:*Tuesday, February 28, 2017 6:58 PM
>> *To:*Nema, Ashutosh <Ashutosh.Nema at amd.com 
>> <mailto:Ashutosh.Nema at amd.com>>
>> *Cc:*anemet at apple.com <mailto:anemet at apple.com>; Hal Finkel
>> <hfinkel at anl.gov <mailto:hfinkel at anl.gov>>; Zaks,
Ayal
>> <ayal.zaks at intel.com <mailto:ayal.zaks at intel.com>>;
Renato Golin
>> <renato.golin at linaro.org 
>> <mailto:renato.golin at linaro.org>>;mkuper at google.com 
>> <mailto:mkuper at google.com>; Mehdi Amini <mehdi.amini at
apple.com
>> <mailto:mehdi.amini at apple.com>>; llvm-dev <llvm-dev at
lists.llvm.org
>> <mailto:llvm-dev at lists.llvm.org>>
>> *Subject:*Re: [llvm-dev] [Proposal][RFC] Epilog loop vectorization
>> Hoisting or removing?
>> Neither pass does hoisting, you'd need gvnhoist for that.
>> Even then:
>> Staring at your example, none of the checks are fully redundant  (IE 
>> they are not dominated by other checks) or execute on all paths.
>> Thus, hoisting them  would be purely speculative code motion, which 
>> none of our passes do.
>> If you would like these sets of checks to be removed, you would need 
>> to place them in a place that they execute unconditionally.
>> Otherwise, this is not a standard code hoisting/removal transform.
>> The only redundancy i can see here at all is the repeated 
>> getelementptr computation.
>> If you move it to the preheader, it will be eliminated.
>> Otherwise, none of the checks are redundant.
>>
>> What would you hope to happen in this case?
>> On Tue, Feb 28, 2017 at 5:09 AM, Nema, Ashutosh 
>> <Ashutosh.Nema at amd.com <mailto:Ashutosh.Nema at
amd.com>> wrote:
>>
>>     I have tried running both gvn and newgvn but it did not helped in
>>     hoisting the alias checks:
>>     Please check, maybe I have missed something.
>>     <TestCase>
>>     void foo (char *A, char *B, char *C, int len) {
>>       int i = 0;
>>       for (i=0 ; i< len; i++)
>>         A[i] = B[i] + C[i];
>>     }
>>     <Command>
>>       $ opt –O3 –gvn test.ll –o test.opt.ll
>>       $ opt –O3 –newgvn test.ll –o test.opt.ll
>>     “test.ll” is attached, it got already vectorized by the approach
>>     running vectorizer twice by annotate the remainder loop with
>>     metadata to limit the vectorization factor for epilog vector loop.
>>     Regards,
>>     Ashutosh
>>     *From:*anemet at apple.com
>>     <mailto:anemet at apple.com>[mailto:anemet at apple.com
>>     <mailto:anemet at apple.com>]
>>     *Sent:*Tuesday, February 28, 2017 1:33 AM
>>     *To:*Hal Finkel <hfinkel at anl.gov <mailto:hfinkel at
anl.gov>>
>>     *Cc:*Daniel Berlin <dberlin at dberlin.org
>>     <mailto:dberlin at dberlin.org>>; Nema, Ashutosh
>>     <Ashutosh.Nema at amd.com <mailto:Ashutosh.Nema at
amd.com>>; Zaks,
>>     Ayal <ayal.zaks at intel.com <mailto:ayal.zaks at
intel.com>>; Renato
>>     Golin <renato.golin at linaro.org
>>     <mailto:renato.golin at linaro.org>>;mkuper at google.com
>>     <mailto:mkuper at google.com>; Mehdi Amini <mehdi.amini at
apple.com
>>     <mailto:mehdi.amini at apple.com>>; llvm-dev
>>     <llvm-dev at lists.llvm.org <mailto:llvm-dev at
lists.llvm.org>>
>>     *Subject:*Re: [llvm-dev] [Proposal][RFC] Epilog loop vectorization
>>
>>         On Feb 27, 2017, at 12:01 PM, Hal Finkel <hfinkel at anl.gov
>>         <mailto:hfinkel at anl.gov>> wrote:
>>         On 02/27/2017 01:47 PM, Daniel Berlin wrote:
>>
>>             On Mon, Feb 27, 2017 at 11:29 AM, Adam Nemet
>>             <anemet at apple.com <mailto:anemet at
apple.com>> wrote:
>>
>>                     On Feb 27, 2017, at 10:11 AM, Hal Finkel
>>                     <hfinkel at anl.gov <mailto:hfinkel at
anl.gov>> wrote:
>>                     On 02/27/2017 11:47 AM, Adam Nemet wrote:
>>
>>                             On Feb 27, 2017, at 9:39 AM, Daniel
>>                             Berlin <dberlin at dberlin.org
>>                             <mailto:dberlin at dberlin.org>>
wrote:
>>                             On Mon, Feb 27, 2017 at 9:29 AM, Adam
>>                             Nemet <anemet at apple.com
>>                             <mailto:anemet at apple.com>>
wrote:
>>
>>                                     On Feb 27, 2017, at 7:27 AM, Hal
>>                                     Finkel <hfinkel at anl.gov
>>                                     <mailto:hfinkel at
anl.gov>> wrote:
>>
>>                                     On 02/27/2017 06:29 AM, Nema,
>>                                     Ashutosh wrote:
>>
>>                                         Thanks for looking into this.
>>                                         1) Issues with re running
>>                                         vectorizer:
>>                                         Vectorizer might generate
>>                                         redundant alias checks while
>>                                         vectorizing epilog loop.
>>                                         Redundant alias checks are
>>                                         expensive, we like to reuse
>>                                         the results of already
>>                                         computed alias checks.
>>                                         With metadata we can limit
>>                                         the width of epilog loop, but
>>                                         not sure about reusing alias
>>                                         check result.
>>                                         Any thoughts on rerunning
>>                                         vectorizer with reusing the
>>                                         alias check result ?
>>
>>
>>                                     One way of looking at this is:
>>                                     Reusing the alias-check result is
>>                                     really just a conditional
>>                                     propagation problem; if we
don't
>>                                     already have an optimization that
>>                                     can combine these after the fact,
>>                                     then we should.
>>
>>                                 +Danny
>>                                 Isn’t Extended SSA supposed to help
>>                                 with this?
>>
>>                             Yes, it will solve this with no issue
>>                             already.  GVN probably does already too.
>>                             even if if you have
>>                             if (a == b)
>>                             if (a == c)
>>                              if (a == d)
>>                              if (a == e)
>>                              if (a == g)
>>                             and  we can prove a ... g equivalent,
>>                             newgvn will eliminate them all and set
>>                             all the branches true.
>>                             If you need a simpler clean up pass, we
>>                             could run it on sub-graphs.
>>
>>                         Yes we probably don’t want to run a full GVN
>>                         after the “loop-scheduling” passes.
>>
>>
>>                     FWIW, we could, just without the
>>                     memory-dependence analysis enabled (i.e. set the
>>                     NoLoads constructor parameter to true). GVN is
>>                     pretty fast in that mode.
>>
>>                 OK. Another data point is that I’ve seen cases in the
>>                 past where the alias checks required for the loop
>>                 passes could enable GVN to remove redundant
>>                 loads/stores. Currently we can only pick these up
>>                 with LTO when GVN is rerun.
>>
>>             This is just GVN brokenness, newgvn should not have this
>>             problem.
>>             If it does, i'd love to see it.
>>
>>
>>         I thought that the problem is that we just don't run GVN
>>         after that point in the pipeline.
>>
>>     Yeah, that is the problem but I think Danny misunderstood what I
>>     was trying to say.
>>     This was a datapoint to possibly rerun GVN with memory-awareness.
>>
>>
>>          -Hal
>>
>>             (I'm working on the last few parts of turning it on by
>>             default, but it requires a new getModRefInfo interface to
>>             be able to get the last few testcases)
>>
>>         -- 
>>
>>         Hal Finkel
>>
>>         Lead, Compiler Technology and Programming Languages
>>
>>         Leadership Computing Facility
>>
>>         Argonne National Laboratory
>>
>
-- 
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/b6c4e0a2/attachment-0001.html>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Type: image/jpeg
Size: 18444 bytes
Desc: not available
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20170314/b6c4e0a2/attachment-0001.jpe>

I'm still not sure about this, for a few reasons:

1) I'd like to try to treat epilogue loops the same way regardless of
whether the main loop was vectorized by hand or automatically. So if
someone hand-wrote an avx-512 16-wide loop, with alias checks, and we
decide it's profitable to vectorize the epilogue loop by 4 and re-use the
checks, it ought to be done the same way. I realize this may be a
pipe-dream, though.

2) I'm still somewhat worried about "tiny loops". As I wrote
before, we
explicitly refuse to vectorize loops we know have a trip-count less than
16, because our profitability heuristic for such loops is probably bad.
IIUC the only reason we don't bail due to the threshold is because we use
the same loop for "failed min iters check" and "failed alias
check". So,
because it's reachable through the alias-check path, the max trip count
isn't actually known, even though the typical trip count is probably small.
It's true that you currently don't try to vectorize the epilogue if the
original VF is below 16, but this is a somewhat different condition.

3) Technically speaking, constructing a new InnerLoopVectorizer to
vectorize this one loop sounds weird. We already have a worklist in the
vectorizer that's currently running.

I don't think (1) is a blocker, and (3) should be easy to fix, but I'm
not
sure whether the way this is going to handle (2) is sufficient.  If I'm the
only one that this bothers, I won't stand in the way, but I'd like to at
least make sure we've fully considered this.

On Mar 14, 2017 06:00, "Nema, Ashutosh" <Ashutosh.Nema at
amd.com> wrote:
> 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.
>
> 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
>
>
>
>
>
> *From:* Nema, Ashutosh
> *Sent:* Wednesday, March 1, 2017 10:42 AM
> *To:* 'Daniel Berlin' <dberlin at dberlin.org>
> *Cc:* anemet at apple.com; Hal Finkel <hfinkel at anl.gov>; Zaks,
Ayal <
> ayal.zaks at intel.com>; Renato Golin <renato.golin at
linaro.org>;
> mkuper at google.com; Mehdi Amini <mehdi.amini at apple.com>;
llvm-dev <
> llvm-dev at lists.llvm.org>
> *Subject:* RE: [llvm-dev] [Proposal][RFC] Epilog loop vectorization
>
>
>
> Sorry I misunderstood, gvn/newgvn/gvnhoist cannot help here as these
> checks are not dominated by all paths.
>
>
>
> Regards,
>
> Ashutosh
>
>
>
> *From:* Daniel Berlin [mailto:dberlin at dberlin.org <dberlin at
dberlin.org>]
> *Sent:* Tuesday, February 28, 2017 6:58 PM
> *To:* Nema, Ashutosh <Ashutosh.Nema at amd.com>
> *Cc:* anemet at apple.com; Hal Finkel <hfinkel at anl.gov>; Zaks,
Ayal <
> ayal.zaks at intel.com>; Renato Golin <renato.golin at
linaro.org>;
> mkuper at google.com; Mehdi Amini <mehdi.amini at apple.com>;
llvm-dev <
> llvm-dev at lists.llvm.org>
> *Subject:* Re: [llvm-dev] [Proposal][RFC] Epilog loop vectorization
>
>
>
> Hoisting or removing?
> Neither pass does hoisting, you'd need gvnhoist for that.
>
>
>
> Even then:
> Staring at your example, none of the checks are fully redundant  (IE they
> are not dominated by other checks) or execute on all paths.
>
>
>
> Thus, hoisting them  would be purely speculative code motion, which none
> of our passes do.
>
>
>
> If you would like these sets of checks to be removed, you would need to
> place them in a place that they execute unconditionally.
>
>
>
> Otherwise, this is not a standard code hoisting/removal transform.
>
>
>
> The only redundancy i can see here at all is the repeated getelementptr
> computation.
>
> If you move it to the preheader, it will be eliminated.
>
> Otherwise, none of the checks are redundant.
>
>
> What would you hope to happen in this case?
>
>
>
> On Tue, Feb 28, 2017 at 5:09 AM, Nema, Ashutosh <Ashutosh.Nema at
amd.com>
> wrote:
>
> I have tried running both gvn and newgvn but it did not helped in hoisting
> the alias checks:
>
>
>
> Please check, maybe I have missed something.
>
>
>
> <TestCase>
>
> void foo (char *A, char *B, char *C, int len) {
>
>   int i = 0;
>
>   for (i=0 ; i< len; i++)
>
>     A[i] = B[i] + C[i];
>
> }
>
>
>
> <Command>
>
>   $ opt –O3 –gvn test.ll –o test.opt.ll
>
>   $ opt –O3 –newgvn test.ll –o test.opt.ll
>
>
>
> “test.ll” is attached, it got already vectorized by the approach running
> vectorizer twice by annotate the remainder loop with metadata to limit the
> vectorization factor for epilog vector loop.
>
>
>
> Regards,
>
> Ashutosh
>
>
>
> *From:* anemet at apple.com [mailto:anemet at apple.com]
> *Sent:* Tuesday, February 28, 2017 1:33 AM
> *To:* Hal Finkel <hfinkel at anl.gov>
> *Cc:* Daniel Berlin <dberlin at dberlin.org>; Nema, Ashutosh <
> Ashutosh.Nema at amd.com>; Zaks, Ayal <ayal.zaks at intel.com>;
Renato Golin <
> renato.golin at linaro.org>; mkuper at google.com; Mehdi Amini <
> mehdi.amini at apple.com>; llvm-dev <llvm-dev at lists.llvm.org>
> *Subject:* Re: [llvm-dev] [Proposal][RFC] Epilog loop vectorization
>
>
>
>
>
> On Feb 27, 2017, at 12:01 PM, Hal Finkel <hfinkel at anl.gov> wrote:
>
>
>
>
>
> On 02/27/2017 01:47 PM, Daniel Berlin wrote:
>
>
>
>
>
> On Mon, Feb 27, 2017 at 11:29 AM, Adam Nemet <anemet at apple.com>
wrote:
>
>
>
> On Feb 27, 2017, at 10:11 AM, Hal Finkel <hfinkel at anl.gov> wrote:
>
>
>
>
>
> On 02/27/2017 11:47 AM, Adam Nemet wrote:
>
>
>
> On Feb 27, 2017, at 9:39 AM, Daniel Berlin <dberlin at dberlin.org>
wrote:
>
>
>
>
>
>
>
> On Mon, Feb 27, 2017 at 9:29 AM, Adam Nemet <anemet at apple.com>
wrote:
>
>
>
> On Feb 27, 2017, at 7:27 AM, Hal Finkel <hfinkel at anl.gov> wrote:
>
>
>
>
> On 02/27/2017 06:29 AM, Nema, Ashutosh wrote:
>
> Thanks for looking into this.
>
>
>
> 1) Issues with re running vectorizer:
>
> Vectorizer might generate redundant alias checks while vectorizing epilog
> loop.
>
> Redundant alias checks are expensive, we like to reuse the results of
> already computed alias checks.
>
> With metadata we can limit the width of epilog loop, but not sure about
> reusing alias check result.
>
> Any thoughts on rerunning vectorizer with reusing the alias check result ?
>
>
> One way of looking at this is: Reusing the alias-check result is really
> just a conditional propagation problem; if we don't already have an
> optimization that can combine these after the fact, then we should.
>
>
>
> +Danny
>
>
>
> Isn’t Extended SSA supposed to help with this?
>
>
>
> Yes, it will solve this with no issue already.  GVN probably does already
> too.
>
>
>
> even if if you have
>
>
>
> if (a == b)
>
> if (a == c)
>
>  if (a == d)
>
>  if (a == e)
>
>  if (a == g)
>
>
>
>
>
> and  we can prove a ... g equivalent, newgvn will eliminate them all and
> set all the branches true.
>
>
>
> If you need a simpler clean up pass, we could run it on sub-graphs.
>
>
>
> Yes we probably don’t want to run a full GVN after the “loop-scheduling”
> passes.
>
>
> FWIW, we could, just without the memory-dependence analysis enabled (i.e.
> set the NoLoads constructor parameter to true). GVN is pretty fast in that
> mode.
>
>
>
> OK.  Another data point is that I’ve seen cases in the past where the
> alias checks required for the loop passes could enable GVN to remove
> redundant loads/stores.  Currently we can only pick these up with LTO when
> GVN is rerun.
>
>
>
> This is just GVN brokenness, newgvn should not have this problem.
>
> If it does, i'd love to see it.
>
>
> I thought that the problem is that we just don't run GVN after that
point
> in the pipeline.
>
>
>
> Yeah, that is the problem but I think Danny misunderstood what I was
> trying to say.
>
>
>
> This was a datapoint to possibly rerun GVN with memory-awareness.
>
>
>
>
>  -Hal
>
>
>
> (I'm working on the last few parts of turning it on by default, but it
> requires a new getModRefInfo interface to be able to get the last few
> testcases)
>
>
>
>
>
> --
>
> 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/2d49242b/attachment.html>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: image003.jpg
Type: image/jpeg
Size: 18444 bytes
Desc: not available
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20170314/2d49242b/attachment.jpg>

On 03/14/2017 09:00 AM, Hal Finkel via llvm-dev wrote:
>
>
> On 03/14/2017 08:00 AM, Nema, Ashutosh wrote:
>>
>> 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.
>>
>> 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.
>>
>
> I think think this is reasonable. One thing: In the proposed block 
> layout, if the alias check fails, we jump to the  "Min Iter Check
2".
> From there we re-check the alias-check result (which will be false 
> again), and then jump to the scalar loop. This is one more branch than 
> necessary in the case where the alias check fails. If the alias check 
> fails, we should jump directly to the scalar loop.
There's another issue as well. If the trip count is small, it is 
important that the critical path through the checks to the scalar loop 
is as small as possible. If we use this layout, then in the case where 
the trip count is very small, we've now introduced an extra check (or 
set of checks) to get to the scalar loop. We need to do it the other 
way: Check the smaller trip count first. If that fails, go to the scalar 
loop. Only if the small trip count succeeds, then we check the larger 
trip count. The path length through the trip counts must be largest when 
we have the most work over which to amortize the checks (i.e. when the 
trip count is largest).

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

On 03/14/2017 11:58 AM, Michael Kuperstein wrote:
> I'm still not sure about this, for a few reasons:
>
> 1) I'd like to try to treat epilogue loops the same way regardless of 
> whether the main loop was vectorized by hand or automatically. So if 
> someone hand-wrote an avx-512 16-wide loop, with alias checks, and we 
> decide it's profitable to vectorize the epilogue loop by 4 and re-use 
> the checks, it ought to be done the same way. I realize this may be a 
> pipe-dream, though.
I agree that sounds ideal. Identifying the effective vectorization 
factor of the hand-vectorized loop seems fragile. However, if someone is 
hand vectorizing then it seems like a small price to add a pragma to the 
scalar loop restricting the vectorization factor (and/or specifying that 
it is safe to execute). As a result, I'm not sure how much effort we 
should make here.
>
> 2) I'm still somewhat worried about "tiny loops". As I wrote
before,
> we explicitly refuse to vectorize loops we know have a trip-count less 
> than 16, because our profitability heuristic for such loops is 
> probably bad. IIUC the only reason we don't bail due to the threshold 
> is because we use the same loop for "failed min iters check" and 
> "failed alias check". So, because it's reachable through the 
> alias-check path, the max trip count isn't actually known, even though 
> the typical trip count is probably small.
> It's true that you currently don't try to vectorize the epilogue if
> the original VF is below 16, but this is a somewhat different condition.
I think that the reason we have that limit, however, is that we don't 
model the costs of the checks. Not that the cost model is otherwise too 
inaccurate for low-trip-count loops. If we modeled the costs of the 
checks, then I don't think this would be a problem.
>
> 3) Technically speaking, constructing a new InnerLoopVectorizer to 
> vectorize this one loop sounds weird. We already have a worklist in 
> the vectorizer that's currently running.
I agree, although we do want to reuse the cost and legality analysis 
(which I think is a worthwhile engineering decision because that 
analysis involves SCEV, AA, and TTI, all of which can get expensive). If 
we can do that and also just add the new loop to the work queue, that 
certainly might be cleaner.

  -Hal
>
> I don't think (1) is a blocker, and (3) should be easy to fix, but
I'm
> not sure whether the way this is going to handle (2) is sufficient.  
> If I'm the only one that this bothers, I won't stand in the way,
but
> I'd like to at least make sure we've fully considered this.
>
> On Mar 14, 2017 06:00, "Nema, Ashutosh" <Ashutosh.Nema at
amd.com
> <mailto:Ashutosh.Nema at amd.com>> wrote:
>
>     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.
>
>     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
>    
<https://reviews.llvm.org/file/data/fxg5vx3capyj257rrn5j/PHID-FILE-x6thnbf6ub55ep5yhalu/LayoutDescription.png>
>
>     Approach-1 looks feasible, please comment if any objections.
>
>     Regards,
>
>     Ashutosh
>
>     *From:*Nema, Ashutosh
>     *Sent:* Wednesday, March 1, 2017 10:42 AM
>     *To:* 'Daniel Berlin' <dberlin at dberlin.org
>     <mailto:dberlin at dberlin.org>>
>     *Cc:* anemet at apple.com <mailto:anemet at apple.com>; Hal
Finkel
>     <hfinkel at anl.gov <mailto:hfinkel at anl.gov>>; Zaks,
Ayal
>     <ayal.zaks at intel.com <mailto:ayal.zaks at intel.com>>;
Renato Golin
>     <renato.golin at linaro.org <mailto:renato.golin at
linaro.org>>;
>     mkuper at google.com <mailto:mkuper at google.com>; Mehdi Amini
>     <mehdi.amini at apple.com <mailto:mehdi.amini at
apple.com>>; llvm-dev
>     <llvm-dev at lists.llvm.org <mailto:llvm-dev at
lists.llvm.org>>
>     *Subject:* RE: [llvm-dev] [Proposal][RFC] Epilog loop vectorization
>
>     Sorry I misunderstood, gvn/newgvn/gvnhoist cannot help here as
>     these checks are not dominated by all paths.
>
>     Regards,
>
>     Ashutosh
>
>     *From:*Daniel Berlin [mailto:dberlin at dberlin.org]
>     *Sent:* Tuesday, February 28, 2017 6:58 PM
>     *To:* Nema, Ashutosh <Ashutosh.Nema at amd.com
>     <mailto:Ashutosh.Nema at amd.com>>
>     *Cc:* anemet at apple.com <mailto:anemet at apple.com>; Hal
Finkel
>     <hfinkel at anl.gov <mailto:hfinkel at anl.gov>>; Zaks,
Ayal
>     <ayal.zaks at intel.com <mailto:ayal.zaks at intel.com>>;
Renato Golin
>     <renato.golin at linaro.org <mailto:renato.golin at
linaro.org>>;
>     mkuper at google.com <mailto:mkuper at google.com>; Mehdi Amini
>     <mehdi.amini at apple.com <mailto:mehdi.amini at
apple.com>>; llvm-dev
>     <llvm-dev at lists.llvm.org <mailto:llvm-dev at
lists.llvm.org>>
>     *Subject:* Re: [llvm-dev] [Proposal][RFC] Epilog loop vectorization
>
>     Hoisting or removing?
>     Neither pass does hoisting, you'd need gvnhoist for that.
>
>     Even then:
>     Staring at your example, none of the checks are fully redundant
>      (IE they are not dominated by other checks) or execute on all paths.
>
>     Thus, hoisting them  would be purely speculative code motion,
>     which none of our passes do.
>
>     If you would like these sets of checks to be removed, you would
>     need to place them in a place that they execute unconditionally.
>
>     Otherwise, this is not a standard code hoisting/removal transform.
>
>     The only redundancy i can see here at all is the repeated
>     getelementptr computation.
>
>     If you move it to the preheader, it will be eliminated.
>
>     Otherwise, none of the checks are redundant.
>
>
>     What would you hope to happen in this case?
>
>     On Tue, Feb 28, 2017 at 5:09 AM, Nema, Ashutosh
>     <Ashutosh.Nema at amd.com <mailto:Ashutosh.Nema at
amd.com>> wrote:
>
>         I have tried running both gvn and newgvn but it did not helped
>         in hoisting the alias checks:
>
>         Please check, maybe I have missed something.
>
>         <TestCase>
>
>         void foo (char *A, char *B, char *C, int len) {
>
>         int i = 0;
>
>         for (i=0 ; i< len; i++)
>
>         A[i] = B[i] + C[i];
>
>         }
>
>         <Command>
>
>         $ opt –O3 –gvn test.ll –o test.opt.ll
>
>         $ opt –O3 –newgvn test.ll –o test.opt.ll
>
>         “test.ll” is attached, it got already vectorized by the
>         approach running vectorizer twice by annotate the remainder
>         loop with metadata to limit the vectorization factor for
>         epilog vector loop.
>
>         Regards,
>
>         Ashutosh
>
>         *From:*anemet at apple.com <mailto:anemet at apple.com>
>         [mailto:anemet at apple.com <mailto:anemet at apple.com>]
>         *Sent:* Tuesday, February 28, 2017 1:33 AM
>         *To:* Hal Finkel <hfinkel at anl.gov <mailto:hfinkel at
anl.gov>>
>         *Cc:* Daniel Berlin <dberlin at dberlin.org
>         <mailto:dberlin at dberlin.org>>; Nema, Ashutosh
>         <Ashutosh.Nema at amd.com <mailto:Ashutosh.Nema at
amd.com>>; Zaks,
>         Ayal <ayal.zaks at intel.com <mailto:ayal.zaks at
intel.com>>;
>         Renato Golin <renato.golin at linaro.org
>         <mailto:renato.golin at linaro.org>>; mkuper at google.com
>         <mailto:mkuper at google.com>; Mehdi Amini <mehdi.amini at
apple.com
>         <mailto:mehdi.amini at apple.com>>; llvm-dev
>         <llvm-dev at lists.llvm.org <mailto:llvm-dev at
lists.llvm.org>>
>         *Subject:* Re: [llvm-dev] [Proposal][RFC] Epilog loop
>         vectorization
>
>             On Feb 27, 2017, at 12:01 PM, Hal Finkel <hfinkel at anl.gov
>             <mailto:hfinkel at anl.gov>> wrote:
>
>             On 02/27/2017 01:47 PM, Daniel Berlin wrote:
>
>                 On Mon, Feb 27, 2017 at 11:29 AM, Adam Nemet
>                 <anemet at apple.com <mailto:anemet at
apple.com>> wrote:
>
>                         On Feb 27, 2017, at 10:11 AM, Hal Finkel
>                         <hfinkel at anl.gov <mailto:hfinkel at
anl.gov>> wrote:
>
>                         On 02/27/2017 11:47 AM, Adam Nemet wrote:
>
>                                 On Feb 27, 2017, at 9:39 AM, Daniel
>                                 Berlin <dberlin at dberlin.org
>                                 <mailto:dberlin at dberlin.org>>
wrote:
>
>                                 On Mon, Feb 27, 2017 at 9:29 AM, Adam
>                                 Nemet <anemet at apple.com
>                                 <mailto:anemet at apple.com>>
wrote:
>
>                                         On Feb 27, 2017, at 7:27 AM,
>                                         Hal Finkel <hfinkel at anl.gov
>                                         <mailto:hfinkel at
anl.gov>> wrote:
>
>
>                                         On 02/27/2017 06:29 AM, Nema,
>                                         Ashutosh wrote:
>
>                                             Thanks for looking into this.
>
>                                             1) Issues with re running
>                                             vectorizer:
>
>                                             Vectorizer might generate
>                                             redundant alias checks
>                                             while vectorizing epilog loop.
>
>                                             Redundant alias checks are
>                                             expensive, we like to
>                                             reuse the results of
>                                             already computed alias checks.
>
>                                             With metadata we can limit
>                                             the width of epilog loop,
>                                             but not sure about reusing
>                                             alias check result.
>
>                                             Any thoughts on rerunning
>                                             vectorizer with reusing
>                                             the alias check result ?
>
>
>                                         One way of looking at this is:
>                                         Reusing the alias-check result
>                                         is really just a conditional
>                                         propagation problem; if we
>                                         don't already have an
>                                         optimization that can combine
>                                         these after the fact, then we
>                                         should.
>
>                                     +Danny
>
>                                     Isn’t Extended SSA supposed to
>                                     help with this?
>
>                                 Yes, it will solve this with no issue
>                                 already.  GVN probably does already too.
>
>                                 even if if you have
>
>                                 if (a == b)
>
>                                 if (a == c)
>
>                                  if (a == d)
>
>                                  if (a == e)
>
>                                  if (a == g)
>
>                                 and  we can prove a ... g equivalent,
>                                 newgvn will eliminate them all and set
>                                 all the branches true.
>
>                                 If you need a simpler clean up pass,
>                                 we could run it on sub-graphs.
>
>                             Yes we probably don’t want to run a full
>                             GVN after the “loop-scheduling” passes.
>
>
>                         FWIW, we could, just without the
>                         memory-dependence analysis enabled (i.e. set
>                         the NoLoads constructor parameter to true).
>                         GVN is pretty fast in that mode.
>
>                     OK.  Another data point is that I’ve seen cases in
>                     the past where the alias checks required for the
>                     loop passes could enable GVN to remove redundant
>                     loads/stores. Currently we can only pick these up
>                     with LTO when GVN is rerun.
>
>                 This is just GVN brokenness, newgvn should not have
>                 this problem.
>
>                 If it does, i'd love to see it.
>
>
>             I thought that the problem is that we just don't run GVN
>             after that point in the pipeline.
>
>         Yeah, that is the problem but I think Danny misunderstood what
>         I was trying to say.
>
>         This was a datapoint to possibly rerun GVN with memory-awareness.
>
>
>              -Hal
>
>                 (I'm working on the last few parts of turning it on by
>                 default, but it requires a new getModRefInfo interface
>                 to be able to get the last few testcases)
>
>             -- 
>
>             Hal Finkel
>
>             Lead, Compiler Technology and Programming Languages
>
>             Leadership Computing Facility
>
>             Argonne National Laboratory
>
-- 
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/e3aff734/attachment-0001.html>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Type: image/jpeg
Size: 18444 bytes
Desc: not available
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20170314/e3aff734/attachment-0001.jpe>

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). 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.



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.

[cid:image002.jpg at 01D29D24.95DCE170]

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


From: Nema, Ashutosh
Sent: Wednesday, March 1, 2017 10:42 AM
To: 'Daniel Berlin' <dberlin at dberlin.org<mailto:dberlin at
dberlin.org>>
Cc: anemet at apple.com<mailto:anemet at apple.com>; Hal Finkel
<hfinkel at anl.gov<mailto:hfinkel at anl.gov>>; Zaks, Ayal
<ayal.zaks at intel.com<mailto:ayal.zaks at intel.com>>; Renato
Golin <renato.golin at linaro.org<mailto:renato.golin at
linaro.org>>; mkuper at google.com<mailto:mkuper at google.com>;
Mehdi Amini <mehdi.amini at apple.com<mailto:mehdi.amini at
apple.com>>; llvm-dev <llvm-dev at lists.llvm.org<mailto:llvm-dev at
lists.llvm.org>>
Subject: RE: [llvm-dev] [Proposal][RFC] Epilog loop vectorization

Sorry I misunderstood, gvn/newgvn/gvnhoist cannot help here as these checks are
not dominated by all paths.

Regards,
Ashutosh

From: Daniel Berlin [mailto:dberlin at dberlin.org]
Sent: Tuesday, February 28, 2017 6:58 PM
To: Nema, Ashutosh <Ashutosh.Nema at amd.com<mailto:Ashutosh.Nema at
amd.com>>
Cc: anemet at apple.com<mailto:anemet at apple.com>; Hal Finkel
<hfinkel at anl.gov<mailto:hfinkel at anl.gov>>; Zaks, Ayal
<ayal.zaks at intel.com<mailto:ayal.zaks at intel.com>>; Renato
Golin <renato.golin at linaro.org<mailto:renato.golin at
linaro.org>>; mkuper at google.com<mailto:mkuper at google.com>;
Mehdi Amini <mehdi.amini at apple.com<mailto:mehdi.amini at
apple.com>>; llvm-dev <llvm-dev at lists.llvm.org<mailto:llvm-dev at
lists.llvm.org>>
Subject: Re: [llvm-dev] [Proposal][RFC] Epilog loop vectorization

Hoisting or removing?
Neither pass does hoisting, you'd need gvnhoist for that.

Even then:
Staring at your example, none of the checks are fully redundant  (IE they are
not dominated by other checks) or execute on all paths.

Thus, hoisting them  would be purely speculative code motion, which none of our
passes do.

If you would like these sets of checks to be removed, you would need to place
them in a place that they execute unconditionally.

Otherwise, this is not a standard code hoisting/removal transform.

The only redundancy i can see here at all is the repeated getelementptr
computation.
If you move it to the preheader, it will be eliminated.
Otherwise, none of the checks are redundant.

What would you hope to happen in this case?

On Tue, Feb 28, 2017 at 5:09 AM, Nema, Ashutosh <Ashutosh.Nema at
amd.com<mailto:Ashutosh.Nema at amd.com>> wrote:
I have tried running both gvn and newgvn but it did not helped in hoisting the
alias checks:

Please check, maybe I have missed something.

<TestCase>
void foo (char *A, char *B, char *C, int len) {
  int i = 0;
  for (i=0 ; i< len; i++)
    A[i] = B[i] + C[i];
}

<Command>
  $ opt –O3 –gvn test.ll –o test.opt.ll
  $ opt –O3 –newgvn test.ll –o test.opt.ll

“test.ll” is attached, it got already vectorized by the approach running
vectorizer twice by annotate the remainder loop with metadata to limit the
vectorization factor for epilog vector loop.

Regards,
Ashutosh

From: anemet at apple.com<mailto:anemet at apple.com> [mailto:anemet at
apple.com<mailto:anemet at apple.com>]
Sent: Tuesday, February 28, 2017 1:33 AM
To: Hal Finkel <hfinkel at anl.gov<mailto:hfinkel at anl.gov>>
Cc: Daniel Berlin <dberlin at dberlin.org<mailto:dberlin at
dberlin.org>>; Nema, Ashutosh <Ashutosh.Nema at
amd.com<mailto:Ashutosh.Nema at amd.com>>; Zaks, Ayal <ayal.zaks at
intel.com<mailto:ayal.zaks at intel.com>>; Renato Golin
<renato.golin at linaro.org<mailto:renato.golin at linaro.org>>;
mkuper at google.com<mailto:mkuper at google.com>; Mehdi Amini
<mehdi.amini at apple.com<mailto:mehdi.amini at apple.com>>;
llvm-dev <llvm-dev at lists.llvm.org<mailto:llvm-dev at
lists.llvm.org>>
Subject: Re: [llvm-dev] [Proposal][RFC] Epilog loop vectorization


On Feb 27, 2017, at 12:01 PM, Hal Finkel <hfinkel at
anl.gov<mailto:hfinkel at anl.gov>> wrote:


On 02/27/2017 01:47 PM, Daniel Berlin wrote:


On Mon, Feb 27, 2017 at 11:29 AM, Adam Nemet <anemet at
apple.com<mailto:anemet at apple.com>> wrote:

On Feb 27, 2017, at 10:11 AM, Hal Finkel <hfinkel at
anl.gov<mailto:hfinkel at anl.gov>> wrote:


On 02/27/2017 11:47 AM, Adam Nemet wrote:

On Feb 27, 2017, at 9:39 AM, Daniel Berlin <dberlin at
dberlin.org<mailto:dberlin at dberlin.org>> wrote:



On Mon, Feb 27, 2017 at 9:29 AM, Adam Nemet <anemet at
apple.com<mailto:anemet at apple.com>> wrote:

On Feb 27, 2017, at 7:27 AM, Hal Finkel <hfinkel at anl.gov<mailto:hfinkel
at anl.gov>> wrote:


On 02/27/2017 06:29 AM, Nema, Ashutosh wrote:
Thanks for looking into this.

1) Issues with re running vectorizer:
Vectorizer might generate redundant alias checks while vectorizing epilog loop.
Redundant alias checks are expensive, we like to reuse the results of already
computed alias checks.
With metadata we can limit the width of epilog loop, but not sure about reusing
alias check result.
Any thoughts on rerunning vectorizer with reusing the alias check result ?

One way of looking at this is: Reusing the alias-check result is really just a
conditional propagation problem; if we don't already have an optimization
that can combine these after the fact, then we should.

+Danny

Isn’t Extended SSA supposed to help with this?

Yes, it will solve this with no issue already.  GVN probably does already too.

even if if you have

if (a == b)
if (a == c)
 if (a == d)
 if (a == e)
 if (a == g)


and  we can prove a ... g equivalent, newgvn will eliminate them all and set all
the branches true.

If you need a simpler clean up pass, we could run it on sub-graphs.

Yes we probably don’t want to run a full GVN after the “loop-scheduling” passes.

FWIW, we could, just without the memory-dependence analysis enabled (i.e. set
the NoLoads constructor parameter to true). GVN is pretty fast in that mode.

OK.  Another data point is that I’ve seen cases in the past where the alias
checks required for the loop passes could enable GVN to remove redundant
loads/stores.  Currently we can only pick these up with LTO when GVN is rerun.

This is just GVN brokenness, newgvn should not have this problem.
If it does, i'd love to see it.

I thought that the problem is that we just don't run GVN after that point in
the pipeline.

Yeah, that is the problem but I think Danny misunderstood what I was trying to
say.

This was a datapoint to possibly rerun GVN with memory-awareness.


 -Hal

(I'm working on the last few parts of turning it on by default, but it
requires a new getModRefInfo interface to be able to get the last few testcases)



--

Hal Finkel

Lead, Compiler Technology and Programming Languages

Leadership Computing Facility

Argonne National Laboratory


---------------------------------------------------------------------
Intel Israel (74) Limited

This e-mail and any attachments may contain confidential material for
the sole use of the intended recipient(s). Any review or distribution
by others is strictly prohibited. If you are not the intended
recipient, please contact the sender and delete all copies.
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20170314/80fd2a32/attachment-0001.html>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: image002.jpg
Type: image/jpeg
Size: 10060 bytes
Desc: image002.jpg
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20170314/80fd2a32/attachment-0001.jpg>

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>

From: Michael Kuperstein [mailto:mkuper at google.com]
Sent: Tuesday, March 14, 2017 10:29 PM
To: Nema, Ashutosh <Ashutosh.Nema at amd.com>
Cc: Adam Nemet <anemet at apple.com>; Hal Finkel <hfinkel at
anl.gov>; Renato Golin <renato.golin at linaro.org>; llvm-dev
<llvm-dev at lists.llvm.org>; Mehdi Amini <mehdi.amini at
apple.com>; Daniel Berlin <dberlin at dberlin.org>; Zaks, Ayal
<ayal.zaks at intel.com>
Subject: RE: [llvm-dev] [Proposal][RFC] Epilog loop vectorization

I'm still not sure about this, for a few reasons:

1) I'd like to try to treat epilogue loops the same way regardless of
whether the main loop was vectorized by hand or automatically. So if someone
hand-wrote an avx-512 16-wide loop, with alias checks, and we decide it's
profitable to vectorize the epilogue loop by 4 and re-use the checks, it ought
to be done the same way. I realize this may be a pipe-dream, though.

Ideally it should be like this, but introduction of alias checks comes with its
own challenges.

2) I'm still somewhat worried about "tiny loops". As I wrote
before, we explicitly refuse to vectorize loops we know have a trip-count less
than 16, because our profitability heuristic for such loops is probably bad.
IIUC the only reason we don't bail due to the threshold is because we use
the same loop for "failed min iters check" and "failed alias
check". So, because it's reachable through the alias-check path, the
max trip count isn't actually known, even though the typical trip count is
probably small.
It's true that you currently don't try to vectorize the epilogue if the
original VF is below 16, but this is a somewhat different condition.

Prerequisite for epilog vectorization is the original loop should get vectorize,
for tiny loops if vectorizer refuse to vectorize then epilog version will not be
generated.
Once we will have the proper costing for checks (i.e. alias, min-itr) then we
can make more accurate decision to vectorize epilog loop by considering checks
cost.

3) Technically speaking, constructing a new InnerLoopVectorizer to vectorize
this one loop sounds weird. We already have a worklist in the vectorizer
that's currently running.

Adding epilog loop to the loop list comes with following challenges:


a)      If we like to add the epilog loop to the list then I’m not sure how we
will handle the “alias check result”.

For epilog vector loop after minimum iteration check it should check the result
of already computed “alias check result” if the result asserts ‘alias’ then
execute scalar epilog loop else execute epilog vector loop. As the execution of
the epilog vector loop is dependent of already computed “alias check result”,
not sure how we will check this fact by adding loop to the list.

Probably loop versioning based on the “alias check result” condition followed by
adding the no-alias version to the list can help here. i.e.

[cid:image001.jpg at 01D29D8C.F47BC4E0]

If “Scalar LoopVersion1” asserts no alias property then add it to the loop list.

This versioning design looks weird, it’s just used to show the “alias check
result” fact.



Any other thoughts handling “alias check result” without versioning ?



b)      Loop Vectorizer anyway creates instance of “InnerLoopVectorizer” for
vectorizing each loop, the only difference is we are creating instance of
“InnerLoopVectorizer” after generating first vector version within the
processing of same loop to cater epilog loop vectorization. The intent is when
vectorizer is processing a loop from the list it should process it completely by
generating both original and epilog vector version.



c)       In the proposed patch, instead of creating a new instance of
“InnerLoopVectorizer”, we can clear the state of existing “InnerLoopVectorizer”
object and use it for epilog loop vectorization.


I don't think (1) is a blocker, and (3) should be easy to fix, but I'm
not sure whether the way this is going to handle (2) is sufficient.  If I'm
the only one that this bothers, I won't stand in the way, but I'd like
to at least make sure we've fully considered this.

Regards,
Ashutosh
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20170315/1639054e/attachment-0001.html>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: image001.jpg
Type: image/jpeg
Size: 38373 bytes
Desc: image001.jpg
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20170315/1639054e/attachment-0001.jpg>

From: Zaks, Ayal [mailto:ayal.zaks at intel.com]
Sent: Wednesday, March 15, 2017 4:39 AM
To: Nema, Ashutosh <Ashutosh.Nema at amd.com>; anemet at apple.com; Hal
Finkel <hfinkel at anl.gov>; Renato Golin <renato.golin at
linaro.org>; mkuper at google.com; Mehdi Amini <mehdi.amini at
apple.com>; Daniel Berlin <dberlin at dberlin.org>
Cc: llvm-dev <llvm-dev at lists.llvm.org>
Subject: RE: [llvm-dev] [Proposal][RFC] Epilog loop vectorization

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.

I did not get this point completely. Yes, we can record the maximum width for
epilog vectorization but what you meant by “path-sensitive context attached”.
Please elaborate more on this and how does it help in reusing alias check result
?



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).

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.



Each vector version incurs extra cost by adding extra checks, considering this
fact I have limit the patch to only generate one epilog vector version.

We can generate multiple epilog versions but we have to understand the tradeoff
of generating them. Once we have the proper costing of checks we can make more
precise decisions. I like to defer this for later enhancements.



Masked instructions are available is AVX512 and of course it’s better solution
then this. But architectures which does not have masked instruction support
epilog vector version is one of the technique to vectorize epilog iterations.




Ayal.


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