thr3ads.net - llvm dev - [LLVMdev] loop vectorizer issue [Nov 2013]

If this information is useful, please help other people find it:
Share via:

Sara Elshobaky

2013-Nov-03 18:39 UTC

[LLVMdev] loop vectorizer issue

Actually what I meant in my original loop, that there is a dependency
between every two consecutive iterations. So, how the loop vectorizer says
'we can vectorize this loop'?

for(int k=20;k<50;k++)

     dataY[k] = dataY[k-1];

 

 

From: Henrique Santos [mailto:henrique.nazare.santos at gmail.com] 
Sent: Sunday, November 03, 2013 4:28 PM
To: Sara Elshobaky
Cc: <llvmdev at cs.uiuc.edu>
Subject: Re: [LLVMdev] loop vectorizer issue

 

Notice that the code you provided, for globals and stack allocations, at
least, 
is semantically equivalent to:

  int a = d[19];
  for(int k = 20; k < 50; k++)
    dataY[k] = a;

Like so, the load you see missing was redundant, probably hoisted by GVN/PRE

and replaced with "%.pre".

H.

 

On Sun, Nov 3, 2013 at 11:26 AM, Sara Elshobaky <sara.elshobaky at
gmail.com>
wrote:

Hello,

I was trying to trace the Loop vectorizer of the LLVM, I wrote a simple loop
with a clear dependency. 

But found that the debug shows that 'we can vectorize this loop'

 

Here you are my  loop with dependency:

for(int k=20;k<50;k++)

     dataY[k] = dataY[k-1];

 

And the debug prints:

LV: Checking a loop in "main"

LV: Found a loop: for.body4

LV: Found an induction variable.

LV: Found a write-only loop!

LV: We can vectorize this loop!

...

LV: Vectorization is possible but not beneficial.

 
>From the LLVM IR, it contains only one 'store' instruction with
'%.pre'.Seems that no 'load' instruction prevented the Vectorizer to detect
dependency.

Is that a bug, or I'm missing something? Please advice

 

for.body4:                                        ; preds = %for.body4,
%for.cond2.preheader

  %k.030 = phi i32 [ 20, %for.cond2.preheader ], [ %inc8, %for.body4 ]

  %arrayidx6 = getelementptr inbounds i32* %0, i32 %k.030

  store i32 %.pre, i32* %arrayidx6, align 4, !tbaa !0

  %inc8 = add nsw i32 %k.030, 1

  %exitcond32 = icmp eq i32 %inc8, 50

  br i1 %exitcond32, label %for.cond10.preheader, label %for.body4

 

 

Thanks in advance,

Sara Elshobaky

 

 


_______________________________________________
LLVM Developers mailing list
LLVMdev at cs.uiuc.edu         http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev

 

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

Arnold Schwaighofer

2013-Nov-03 22:04 UTC

head link

[LLVMdev] loop vectorizer issue

Hi Sarah,

the loop vectorizer runs not on the C code but on LLVM IR this c code was
lowered to. Before the loop vectorizer runs many other optimization change the
shape of this IR.

You can see in the LLVM IR you referenced below, a preceding LLVM IR
transformation has change your loop from:
> for(int k=20;k<50;k++)
>      dataY[k] = dataY[k-1];
to
>   int a = d[19];
>   for(int k = 20; k < 50; k++)
>     dataY[k] = a;

which is allowed because they are semantically equivalent and beneficial because
we safe many loads.

We can vectorize the latter loop. You can see in the debug output there is no
load in the loop once the loop vectorizer gets to see it:
> And the debug prints:
> LV: Checking a loop in "main"
> LV: Found a loop: for.body4
> LV: Found an induction variable.
> LV: Found a write-only loop! // <<<< Write-only.
> LV: We can vectorize this loop!
> ...
> LV: Vectorization is possible but not beneficial.


This is not a bug but a great example of how one optimization can enable
another.

Best,
Arnold

On Nov 3, 2013, at 10:39 AM, Sara Elshobaky <sara.elshobaky at gmail.com>
wrote:
> Actually what I meant in my original loop, that there is a dependency
between every two consecutive iterations. So, how the loop vectorizer says ‘we
can vectorize this loop’?
> for(int k=20;k<50;k++)
>      dataY[k] = dataY[k-1];
>  
>  
> From: Henrique Santos [mailto:henrique.nazare.santos at gmail.com] 
> Sent: Sunday, November 03, 2013 4:28 PM
> To: Sara Elshobaky
> Cc: <llvmdev at cs.uiuc.edu>
> Subject: Re: [LLVMdev] loop vectorizer issue
>  
> Notice that the code you provided, for globals and stack allocations, at
least,
> is semantically equivalent to:
> 
>   int a = d[19];
>   for(int k = 20; k < 50; k++)
>     dataY[k] = a;
> 
> Like so, the load you see missing was redundant, probably hoisted by
GVN/PRE
> and replaced with "%.pre".
> 
> H.
> 
>  
> 
> On Sun, Nov 3, 2013 at 11:26 AM, Sara Elshobaky <sara.elshobaky at
gmail.com> wrote:
> Hello,
> I was trying to trace the Loop vectorizer of the LLVM, I wrote a simple
loop with a clear dependency.
> But found that the debug shows that ‘we can vectorize this loop’
>  
> Here you are my  loop with dependency:
> for(int k=20;k<50;k++)
>      dataY[k] = dataY[k-1];
>  
> And the debug prints:
> LV: Checking a loop in "main"
> LV: Found a loop: for.body4
> LV: Found an induction variable.
> LV: Found a write-only loop!
> LV: We can vectorize this loop!
> ...
> LV: Vectorization is possible but not beneficial.
>  
> From the LLVM IR, it contains only one ‘store’ instruction with ‘%.pre’.
Seems that no ‘load’ instruction prevented the Vectorizer to detect dependency.
> Is that a bug, or I’m missing something? Please advice
>  
> for.body4:                                        ; preds = %for.body4,
%for.cond2.preheader
>   %k.030 = phi i32 [ 20, %for.cond2.preheader ], [ %inc8, %for.body4 ]
>   %arrayidx6 = getelementptr inbounds i32* %0, i32 %k.030
>   store i32 %.pre, i32* %arrayidx6, align 4, !tbaa !0
>   %inc8 = add nsw i32 %k.030, 1
>   %exitcond32 = icmp eq i32 %inc8, 50
>   br i1 %exitcond32, label %for.cond10.preheader, label %for.body4
>  
>  
> Thanks in advance,
> Sara Elshobaky
>  
>  
> 
> _______________________________________________
> LLVM Developers mailing list
> LLVMdev at cs.uiuc.edu         http://llvm.cs.uiuc.edu
> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
> 
>  
> _______________________________________________
> LLVM Developers mailing list
> LLVMdev at cs.uiuc.edu         http://llvm.cs.uiuc.edu
> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev

Gregory Junker

2013-Nov-04 02:53 UTC

head link

[LLVMdev] loop vectorizer issue

On 11/3/2013 10:39 AM, Sara Elshobaky wrote:> Actually what I meant in my original loop, that there is a dependency
> between every two consecutive iterations. So, how the loop vectorizer
> says ‘we can vectorize this loop’?
>
> for(int k=20;k<50;k++)
>
> dataY[k] = dataY[k-1];
The reason that this is equivalent to

 >    int a = d[19];
 >    for(int k = 20; k < 50; k++)
 >      dataY[k] = a;

may not be immediately clear. But if you manually unroll the original 
loop it may make more sense. So your loop, fully unrolled, would look like

dataY[20] = dataY[19];
dataY[21] = dataY[20];
dataY[22] = dataY[21];
  ...
dataY[49] = dataY[48];

 From this you should be able to see that after you have run the 30 
iterations, all of the LHS values (in other words, this whole section of 
the dataY array) will end up with the same value that is in dataY[19]. 
That is why the compiler can make this optimization.

Does that make sense?

Greg

Sara Elshobaky

2013-Nov-04 09:10 UTC

head link

[LLVMdev] loop vectorizer issue

I got it , thank you


On Mon, Nov 4, 2013 at 12:04 AM, Arnold Schwaighofer <
aschwaighofer at apple.com> wrote:
> Hi Sarah,
>
> the loop vectorizer runs not on the C code but on LLVM IR this c code was
> lowered to. Before the loop vectorizer runs many other optimization change
> the shape of this IR.
>
> You can see in the LLVM IR you referenced below, a preceding LLVM IR
> transformation has change your loop from:
>
> > for(int k=20;k<50;k++)
> >      dataY[k] = dataY[k-1];
>
> to
>
> >   int a = d[19];
> >   for(int k = 20; k < 50; k++)
> >     dataY[k] = a;
>
>
> which is allowed because they are semantically equivalent and beneficial
> because we safe many loads.
>
> We can vectorize the latter loop. You can see in the debug output there is
> no load in the loop once the loop vectorizer gets to see it:
>
> > And the debug prints:
> > LV: Checking a loop in "main"
> > LV: Found a loop: for.body4
> > LV: Found an induction variable.
> > LV: Found a write-only loop! // <<<< Write-only.
> > LV: We can vectorize this loop!
> > ...
> > LV: Vectorization is possible but not beneficial.
>
>
>
> This is not a bug but a great example of how one optimization can enable
> another.
>
> Best,
> Arnold
>
> On Nov 3, 2013, at 10:39 AM, Sara Elshobaky <sara.elshobaky at
gmail.com>
> wrote:
>
> > Actually what I meant in my original loop, that there is a dependency
> between every two consecutive iterations. So, how the loop vectorizer says
> ‘we can vectorize this loop’?
> > for(int k=20;k<50;k++)
> >      dataY[k] = dataY[k-1];
> >
> >
> > From: Henrique Santos [mailto:henrique.nazare.santos at gmail.com]
> > Sent: Sunday, November 03, 2013 4:28 PM
> > To: Sara Elshobaky
> > Cc: <llvmdev at cs.uiuc.edu>
> > Subject: Re: [LLVMdev] loop vectorizer issue
> >
> > Notice that the code you provided, for globals and stack allocations,
at
> least,
> > is semantically equivalent to:
> >
> >   int a = d[19];
> >   for(int k = 20; k < 50; k++)
> >     dataY[k] = a;
> >
> > Like so, the load you see missing was redundant, probably hoisted by
> GVN/PRE
> > and replaced with "%.pre".
> >
> > H.
> >
> >
> >
> > On Sun, Nov 3, 2013 at 11:26 AM, Sara Elshobaky <
> sara.elshobaky at gmail.com> wrote:
> > Hello,
> > I was trying to trace the Loop vectorizer of the LLVM, I wrote a
simple
> loop with a clear dependency.
> > But found that the debug shows that ‘we can vectorize this loop’
> >
> > Here you are my  loop with dependency:
> > for(int k=20;k<50;k++)
> >      dataY[k] = dataY[k-1];
> >
> > And the debug prints:
> > LV: Checking a loop in "main"
> > LV: Found a loop: for.body4
> > LV: Found an induction variable.
> > LV: Found a write-only loop!
> > LV: We can vectorize this loop!
> > ...
> > LV: Vectorization is possible but not beneficial.
> >
> > From the LLVM IR, it contains only one ‘store’ instruction with
‘%.pre’.
> Seems that no ‘load’ instruction prevented the Vectorizer to detect
> dependency.
> > Is that a bug, or I’m missing something? Please advice
> >
> > for.body4:                                        ; preds =
%for.body4,
> %for.cond2.preheader
> >   %k.030 = phi i32 [ 20, %for.cond2.preheader ], [ %inc8, %for.body4 ]
> >   %arrayidx6 = getelementptr inbounds i32* %0, i32 %k.030
> >   store i32 %.pre, i32* %arrayidx6, align 4, !tbaa !0
> >   %inc8 = add nsw i32 %k.030, 1
> >   %exitcond32 = icmp eq i32 %inc8, 50
> >   br i1 %exitcond32, label %for.cond10.preheader, label %for.body4
> >
> >
> > Thanks in advance,
> > Sara Elshobaky
> >
> >
> >
> > _______________________________________________
> > LLVM Developers mailing list
> > LLVMdev at cs.uiuc.edu         http://llvm.cs.uiuc.edu
> > http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
> >
> >
> > _______________________________________________
> > LLVM Developers mailing list
> > LLVMdev at cs.uiuc.edu         http://llvm.cs.uiuc.edu
> > http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
>
>-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20131104/a4379b0c/attachment.html>

Possibly Parallel Threads

Search for more apparently analagous threads

llvm dev - Nov 2013 - [LLVMdev] loop vectorizer issue

[LLVMdev] loop vectorizer issue

[LLVMdev] loop vectorizer issue

[LLVMdev] loop vectorizer issue

[LLVMdev] loop vectorizer issue

Possibly Parallel Threads