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

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

I guess the pipeline to experiment with for now is opt -loop-vectorize
-loop-vectorize -newgvn.

Adam
> The only thing you'd have to do is write some code to set "live on
entry" subgraph variables in their own congruence classes.
> We already do this for incoming arguments.
> 
> Otherwise, it's trivial to make it only walk things in the subgraph.
> 
> 
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20170227/36ec6dae/attachment.html>

On Mon, Feb 27, 2017 at 9:47 AM, Adam Nemet <anemet at apple.com> 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.
>
> I guess the pipeline to experiment with for now is opt -loop-vectorize
> -loop-vectorize -newgvn.
>
> Adam
>
Right, and if you guarantee the conditions involve scalars (IE the pointer
is not from a load ), it can be made evenfaster by turning off the memory
handling (IE not building memoryssa)..

NewGVN will still give correct answers if you value number any instruction
you like as "unknown expression".
I have a patch to add a debug counter that does just that.
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20170227/6bb1108f/attachment-0001.html>

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.

  -Hal
>
> I guess the pipeline to experiment with for now is opt -loop-vectorize 
> -loop-vectorize -newgvn.
>
> Adam
>
>> The only thing you'd have to do is write some code to set
"live on
>> entry" subgraph variables in their own congruence classes.
>> We already do this for incoming arguments.
>>
>> Otherwise, it's trivial to make it only walk things in the
subgraph.
>>
>>
>
-- 
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/20170227/df36dddf/attachment.html>

There's another issue with re-running the vectorizer (which I support, btw
- I'm just saying there are more problems to solve on the way :-) )

Historically, we haven't even tried to evaluate the cost of the
"constant"
(not per-iteration) vectorization overhead - things like alias checks.
Instead, we have hard bounds - we won't perform alias checks that are
"too
expensive", and, more importantly, we don't even try to vectorize loops
with known low iteration counts. The bound right now is 16, IIRC. That
means we don't have a good way to evaluate whether vectorizing a loop with
a low iteration count is profitable or not.

This also makes me wary of the "we can clean up redundant alias checks
later" approach. When trying to decide whether to vectorize by 4 a loop
that has no more than 8 iterations (because we just vectorized by 8 and
it's the remainder loop), we really want to know if the alias checks
we're
introducing are going to survive a not.

Michael

On Mon, 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.
>
>  -Hal
>
>
> I guess the pipeline to experiment with for now is opt -loop-vectorize
> -loop-vectorize -newgvn.
>
> Adam
>
> The only thing you'd have to do is write some code to set "live on
entry"
> subgraph variables in their own congruence classes.
> We already do this for incoming arguments.
>
> Otherwise, it's trivial to make it only walk things in the subgraph.
>
>
>
>
> --
> 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/20170227/07fa6f12/attachment.html>

>
>
> 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.
>
Yeah, same. We can definitely make it work to clean up the redundant checks
cheaply.
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20170227/45a8572b/attachment.html>

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

Adam
> 
>  -Hal
> 
>> 
>> I guess the pipeline to experiment with for now is opt -loop-vectorize
-loop-vectorize -newgvn.
>> 
>> Adam
>> 
>>> The only thing you'd have to do is write some code to set
"live on entry" subgraph variables in their own congruence classes.
>>> We already do this for incoming arguments.
>>> 
>>> Otherwise, it's trivial to make it only walk things in the
subgraph.
>>> 
>>> 
>> 
> 
> -- 
> 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/20170227/4292bc10/attachment.html>