llvm dev - Jul 2015 - [LLVMdev] Improving loop vectorizer support for loops with a volatile iteration variable

Hi all,

I would like to propose an improvement of the “almost dead” block
elimination in Transforms/Local.cpp so that it will preserve the canonical
loop form for loops with a volatile iteration variable.

*** Problem statement
Nested loops in LCALS Subset B (https://codesign.llnl.gov/LCALS.php) are
not vectorized with LLVM -O3 because the LLVM loop vectorizer fails the
test whether the loop latch and exiting block of a loop is the same. The
loops are vectorizable, and get vectorized with LLVM -O2 and also with
other commercial compilers (icc, xlc).

*** Details
These loops ended up with different loop latch and exiting block after a
series of optimizations including loop unswitching, jump threading,
simplify-the-CFG, and loop simplify. The fundamental problem here is that
the above optimizations cannot recognize a loop with a volatile iteration
variable and do not preserve its canonical loop structure.

(1) Loop unswitching generates several empty placeholder BBs only with PHI
nodes after separating out a shorter path with no inner loop execution from
a standard path.

(2) Jump threading and simplify-the-CFG passes independently calls
TryToSimplifyUnconditionalBranchFromEmptyBlock() in
Transforms/Utils/Local.cpp to get rid of almost empty BBs.

(3) TryToSimplifyUnconditionalBranchFromEmtpyBlock() eliminates the
placeholder BBs after loop unswitching and merges them into subsequent
blocks including the header of the inner loop. Before eliminating the
blocks, the function checks if the block is a loop header by looking at its
PHI nodes so that it can be saved, but the test fails with the loops with a
volatile iteration variable. The outer loop is now collapsed into the inner
loop with multiple backedges.

(4) LoopSimplify checks if a loop with multiple backedges can be separated
to nested loops by looking at PHI nodes in the loop header. The test fails
with the loops with a volatile iteration variable.

(5) LoopSimplify then creates a unique backedge block for the loop, and the
loop now has a different loop latch (the unique backedge block created in
(3)) and exiting block (a block where the volatile outer loop variable is
incremented and tested).

*** Proposed solutions
(1) Make LoopInfo available in Jump Threading and Simplify-the-CFG passes
and use LoopInfo to test whether an almost empty BB is a loop header. If
yes, do not eliminate the BB.
      Pros: Leverages existing analysis results, small code changes / Cons:
Add pass dependencies

(2) Instead of using LoopInfo, iterate through BB’s to identify backedges
and loop headers in TryToSimplifyUnconditionalBranchFromEmptyBlock() and
use the results to test if a BB is a loop header. If yes, do not eliminate
the BB. Jump Threading has functions that do similar cheap loop analysis.
      Pros: No need to depend on external analysis results / Cons: More
lines to be added

*** Summary
I would like to propose an improvement of the “almost dead” block
elimination in Transforms/Local.cpp so that it will preserve the canonical
loop form for loops with a volatile iteration variable. On top of the
current algorithm relying on PHI nodes to recognize loops, actual loop
analysis to test if a BB belongs to a loop and etc. can be used.
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20150715/0578e09b/attachment.html>

Regarding your proposed solution (2) - could this be further abstracted from
just the volatile iteration variables so that all conditional dependencies
between BBs could be tracked?  For VLIW architectures with predication support,
it is often advantageous to either clone a BB predecessor (with appropriate
predication) to each of the successor BBs, or to move a dependency from
successor BBs into the predecessor BBs (with appropriate predication).  The
approach you propose might help with this kind of ILP problem.  Currently LLVM
does not seem to do a great job at tracking this kind of ILP data edge
dependency across BBs.  I can achieve this now, but only by using a large amount
of custom coding and I would prefer to use a more generalised abstraction.

 

            MartinO

 

From: llvmdev-bounces at cs.uiuc.edu [mailto:llvmdev-bounces at cs.uiuc.edu] On
Behalf Of Hyojin Sung
Sent: 15 July 2015 20:52
To: llvmdev at cs.uiuc.edu
Subject: [LLVMdev] Improving loop vectorizer support for loops with a volatile
iteration variable

 

Hi all,

I would like to propose an improvement of the “almost dead” block elimination in
Transforms/Local.cpp so that it will preserve the canonical loop form for loops
with a volatile iteration variable.

*** Problem statement
Nested loops in LCALS Subset B (
<https://urldefense.proofpoint.com/v2/url?u=https-3A__codesign.llnl.gov_LCALS.php&d=AwMGaQ&c=8hUWFZcy2Z-Za5rBPlktOQ&r=Mfk2qtn1LTDThVkh6-oGglNfMADXfJdty4_bhmuhMHA&m=aWKfvN4c8lvUSvVn8J0Z2ajTctlBJf0198Au28epBr0&s=4d9dt5ODcDWHHatSrwu5ZYT9ebgVzNEtpOlIR87izCM&e=>
https://codesign.llnl.gov/LCALS.php) are not vectorized with LLVM -O3 because
the LLVM loop vectorizer fails the test whether the loop latch and exiting block
of a loop is the same. The loops are vectorizable, and get vectorized with LLVM
-O2 and also with other commercial compilers (icc, xlc).

*** Details
These loops ended up with different loop latch and exiting block after a series
of optimizations including loop unswitching, jump threading, simplify-the-CFG,
and loop simplify. The fundamental problem here is that the above optimizations
cannot recognize a loop with a volatile iteration variable and do not preserve
its canonical loop structure.

(1) Loop unswitching generates several empty placeholder BBs only with PHI nodes
after separating out a shorter path with no inner loop execution from a standard
path.

(2) Jump threading and simplify-the-CFG passes independently calls
TryToSimplifyUnconditionalBranchFromEmptyBlock() in Transforms/Utils/Local.cpp
to get rid of almost empty BBs.

(3) TryToSimplifyUnconditionalBranchFromEmtpyBlock() eliminates the placeholder
BBs after loop unswitching and merges them into subsequent blocks including the
header of the inner loop. Before eliminating the blocks, the function checks if
the block is a loop header by looking at its PHI nodes so that it can be saved,
but the test fails with the loops with a volatile iteration variable. The outer
loop is now collapsed into the inner loop with multiple backedges.

(4) LoopSimplify checks if a loop with multiple backedges can be separated to
nested loops by looking at PHI nodes in the loop header. The test fails with the
loops with a volatile iteration variable.

(5) LoopSimplify then creates a unique backedge block for the loop, and the loop
now has a different loop latch (the unique backedge block created in (3)) and
exiting block (a block where the volatile outer loop variable is incremented and
tested).

*** Proposed solutions
(1) Make LoopInfo available in Jump Threading and Simplify-the-CFG passes and
use LoopInfo to test whether an almost empty BB is a loop header. If yes, do not
eliminate the BB.
      Pros: Leverages existing analysis results, small code changes / Cons: Add
pass dependencies

(2) Instead of using LoopInfo, iterate through BB’s to identify backedges and
loop headers in TryToSimplifyUnconditionalBranchFromEmptyBlock() and use the
results to test if a BB is a loop header. If yes, do not eliminate the BB. Jump
Threading has functions that do similar cheap loop analysis.
      Pros: No need to depend on external analysis results / Cons: More lines to
be added

*** Summary
I would like to propose an improvement of the “almost dead” block elimination in
Transforms/Local.cpp so that it will preserve the canonical loop form for loops
with a volatile iteration variable. On top of the current algorithm relying on
PHI nodes to recognize loops, actual loop analysis to test if a BB belongs to a
loop and etc. can be used.

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

On Wed, Jul 15, 2015 at 12:55 PM Hyojin Sung <hsung at us.ibm.com> wrote:
> Hi all,
>
> I would like to propose an improvement of the “almost dead” block
> elimination in Transforms/Local.cpp so that it will preserve the canonical
> loop form for loops with a volatile iteration variable.
>
> *** Problem statement
> Nested loops in LCALS Subset B (*https://codesign.llnl.gov/LCALS.php*
>
<https://urldefense.proofpoint.com/v2/url?u=https-3A__codesign.llnl.gov_LCALS.php&d=AwMGaQ&c=8hUWFZcy2Z-Za5rBPlktOQ&r=Mfk2qtn1LTDThVkh6-oGglNfMADXfJdty4_bhmuhMHA&m=aWKfvN4c8lvUSvVn8J0Z2ajTctlBJf0198Au28epBr0&s=4d9dt5ODcDWHHatSrwu5ZYT9ebgVzNEtpOlIR87izCM&e=>)
> are not vectorized with LLVM -O3 because the LLVM loop vectorizer fails the
> test whether the loop latch and exiting block of a loop is the same. The
> loops are vectorizable, and get vectorized with LLVM -O2
>
I would be interested to know why -O2 succeeds here.

> and also with other commercial compilers (icc, xlc).
>
> *** Details
> These loops ended up with different loop latch and exiting block after a
> series of optimizations including loop unswitching, jump threading,
> simplify-the-CFG, and loop simplify. The fundamental problem here is that
> the above optimizations cannot recognize a loop with a volatile iteration
> variable and do not preserve its canonical loop structure.
>
Ok, meta-level question first:

Why do we care about performance of loops with a volatile iteration
variable? That seems both counter-intuitive and unlikely to be a useful
goal. We simply don't optimize volatile operations well in *any* part of
the optimizer, and I'm not sure why we need to start trying to fix that.
This seems like an irreparably broken benchmark, but perhaps there is a
motivation I don't yet see.


Assuming that sufficient motivation arises to try to fix this, see my
comments below:

>
>
> (1) Loop unswitching generates several empty placeholder BBs only with PHI
> nodes after separating out a shorter path with no inner loop execution from
> a standard path.
>
> (2) Jump threading and simplify-the-CFG passes independently calls
> TryToSimplifyUnconditionalBranchFromEmptyBlock() in
> Transforms/Utils/Local.cpp to get rid of almost empty BBs.
>
> (3) TryToSimplifyUnconditionalBranchFromEmtpyBlock() eliminates the
> placeholder BBs after loop unswitching and merges them into subsequent
> blocks including the header of the inner loop. Before eliminating the
> blocks, the function checks if the block is a loop header by looking at its
> PHI nodes so that it can be saved, but the test fails with the loops with a
> volatile iteration variable.
>
Why does this fail for a volatile iteration variable but not for a
non-volatile one? I think understanding that will be key to understanding
how it should be fixed.
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20150716/0f2f5cf8/attachment.html>

On Wed, Jul 15, 2015 at 5:34 PM, Chandler Carruth <chandlerc at
google.com>
wrote:
> On Wed, Jul 15, 2015 at 12:55 PM Hyojin Sung <hsung at us.ibm.com>
wrote:
>
>> Hi all,
>>
>> I would like to propose an improvement of the “almost dead” block
>> elimination in Transforms/Local.cpp so that it will preserve the
canonical
>> loop form for loops with a volatile iteration variable.
>>
>> *** Problem statement
>> Nested loops in LCALS Subset B (*https://codesign.llnl.gov/LCALS.php*
>>
<https://urldefense.proofpoint.com/v2/url?u=https-3A__codesign.llnl.gov_LCALS.php&d=AwMGaQ&c=8hUWFZcy2Z-Za5rBPlktOQ&r=Mfk2qtn1LTDThVkh6-oGglNfMADXfJdty4_bhmuhMHA&m=aWKfvN4c8lvUSvVn8J0Z2ajTctlBJf0198Au28epBr0&s=4d9dt5ODcDWHHatSrwu5ZYT9ebgVzNEtpOlIR87izCM&e=>)
>> are not vectorized with LLVM -O3 because the LLVM loop vectorizer fails
the
>> test whether the loop latch and exiting block of a loop is the same.
The
>> loops are vectorizable, and get vectorized with LLVM -O2
>>
> I would be interested to know why -O2 succeeds here.
>
>
>> and also with other commercial compilers (icc, xlc).
>>
>> *** Details
>> These loops ended up with different loop latch and exiting block after
a
>> series of optimizations including loop unswitching, jump threading,
>> simplify-the-CFG, and loop simplify. The fundamental problem here is
that
>> the above optimizations cannot recognize a loop with a volatile
iteration
>> variable and do not preserve its canonical loop structure.
>>
> Ok, meta-level question first:
>
> Why do we care about performance of loops with a volatile iteration
> variable? That seems both counter-intuitive and unlikely to be a useful
> goal. We simply don't optimize volatile operations well in *any* part
of
> the optimizer, and I'm not sure why we need to start trying to fix
that.
> This seems like an irreparably broken benchmark, but perhaps there is a
> motivation I don't yet see.
>
A quick look at the tarball on the linked site suggests that the volatile
iteration variable is done on purpose so that the outer "run thing N times
and take the average" loop can't be optimized.

-- Sean Silva

>
>
> Assuming that sufficient motivation arises to try to fix this, see my
> comments below:
>
>
>>
>>
>> (1) Loop unswitching generates several empty placeholder BBs only with
>> PHI nodes after separating out a shorter path with no inner loop
execution
>> from a standard path.
>>
>> (2) Jump threading and simplify-the-CFG passes independently calls
>> TryToSimplifyUnconditionalBranchFromEmptyBlock() in
>> Transforms/Utils/Local.cpp to get rid of almost empty BBs.
>>
>> (3) TryToSimplifyUnconditionalBranchFromEmtpyBlock() eliminates the
>> placeholder BBs after loop unswitching and merges them into subsequent
>> blocks including the header of the inner loop. Before eliminating the
>> blocks, the function checks if the block is a loop header by looking at
its
>> PHI nodes so that it can be saved, but the test fails with the loops
with a
>> volatile iteration variable.
>>
> Why does this fail for a volatile iteration variable but not for a
> non-volatile one? I think understanding that will be key to understanding
> how it should be fixed.
>
> _______________________________________________
> 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/20150715/1dc26e05/attachment.html>

----- Original Message -----
> From: "Chandler Carruth" <chandlerc at google.com>
> To: "Hyojin Sung" <hsung at us.ibm.com>, llvmdev at
cs.uiuc.edu
> Sent: Wednesday, July 15, 2015 7:34:54 PM
> Subject: Re: [LLVMdev] Improving loop vectorizer support for loops
> with a volatile iteration variable
> On Wed, Jul 15, 2015 at 12:55 PM Hyojin Sung < hsung at us.ibm.com >
> wrote:
> > Hi all,
> 
> > I would like to propose an improvement of the “almost dead” block
> > elimination in Transforms/Local.cpp so that it will preserve the
> > canonical loop form for loops with a volatile iteration variable.
> 
> > *** Problem statement
> 
> > Nested loops in LCALS Subset B (
> > https://codesign.llnl.gov/LCALS.php
> > ) are not vectorized with LLVM -O3 because the LLVM loop vectorizer
> > fails the test whether the loop latch and exiting block of a loop
> > is
> > the same. The loops are vectorizable, and get vectorized with LLVM
> > -O2
> 
> I would be interested to know why -O2 succeeds here.
> > and also with other commercial compilers (icc, xlc).
> 
> > *** Details
> 
> > These loops ended up with different loop latch and exiting block
> > after a series of optimizations including loop unswitching, jump
> > threading, simplify-the-CFG, and loop simplify. The fundamental
> > problem here is that the above optimizations cannot recognize a
> > loop
> > with a volatile iteration variable and do not preserve its
> > canonical
> > loop structure.
> 
> Ok, meta-level question first:
> Why do we care about performance of loops with a volatile iteration
> variable?
I don't think we do, however, I think that misses the point. In this case,
the volatile iteration variable is just an easy way to expose this problem that
we have with nested loop canonicalization and the vectorizer. To be specific:

This we vectorizer just fine: 

void foo1(float * restrict x, float * restrict y, float * restrict z) { 
for (int i = 0; i < 1000; ++i) { 
for (int j = 0; j < 1600; ++j) { 
x[j] = y[j] + z[j]; 
} 
} 
} 

And, indeed, this we don't (the only change is adding volatile on i): 

void foo2(float * restrict x, float * restrict y, float * restrict z) { 
for (volatile int i = 0; i < 1000; ++i) { 
for (int j = 0; j < 1600; ++j) { 
x[j] = y[j] + z[j]; 
} 
} 
} 

However, this we don't either, and that's a big problem: 

int done(float *x, float *y, float *z); 
void foo3(float * restrict x, float * restrict y, float * restrict z) { 
while (!done(x, y, z)) { 
for (int j = 0; j < 1600; ++j) { 
x[j] = y[j] + z[j]; 
} 
} 
} 

And the underlying reason is the same. The IR at the point in time when the loop
vectorizer runs looks like this:

define void @foo3(float* noalias %x, float* noalias %y, float* noalias %z) #0 { 
entry: 
%call.14 = tail call i32 @done(float* %x, float* %y, float* %z) #1 
%lnot.15 = icmp eq i32 %call.14, 0 
br i1 %lnot.15, label %for.body.preheader, label %while.end 

for.body.preheader: ; preds = %entry 
br label %for.body 

while.cond.loopexit: ; preds = %for.body 
%call = tail call i32 @done(float* %x, float* %y, float* %z) #1 
%lnot = icmp eq i32 %call, 0 
br i1 %lnot, label %for.body.backedge, label %while.end.loopexit 

for.body: ; preds = %for.body.backedge, %for.body.preheader 
%indvars.iv = phi i64 [ 0, %for.body.preheader ], [ %indvars.iv.be,
%for.body.backedge ]
... 
%indvars.iv.next = add nuw nsw i64 %indvars.iv, 1 
%exitcond = icmp eq i64 %indvars.iv.next, 1600 
br i1 %exitcond, label %while.cond.loopexit, label %for.body.backedge 

for.body.backedge: ; preds = %for.body, %while.cond.loopexit 
%indvars.iv.be = phi i64 [ %indvars.iv.next, %for.body ], [ 0,
%while.cond.loopexit ]
br label %for.body 

while.end.loopexit: ; preds = %while.cond.loopexit 
br label %while.end 

while.end: ; preds = %while.end.loopexit, %entry 
ret void 
} 

and we can currently only vectorize loops where the loop latch is also the
loop's exiting block. In this case, as in the case with the volatile
variable, vectorization is blocked by this constraint (here the backedge is from
the terminator of %for.body.backedge, but the loop exiting block is %for.body).
The check in the vectorizer is explicit:

// We only handle bottom-tested loops, i.e. loop in which the condition is 
// checked at the end of each iteration. With that we can assume that all 
// instructions in the loop are executed the same number of times. 
if (TheLoop->getExitingBlock() != TheLoop->getLoopLatch()) { 
... 

-Hal 
> That seems both counter-intuitive and unlikely to be a useful goal.
> We simply don't optimize volatile operations well in *any* part of
> the optimizer, and I'm not sure why we need to start trying to fix
> that. This seems like an irreparably broken benchmark, but perhaps
> there is a motivation I don't yet see.
> Assuming that sufficient motivation arises to try to fix this, see my
> comments below:
> > (1) Loop unswitching generates several empty placeholder BBs only
> > with PHI nodes after separating out a shorter path with no inner
> > loop execution from a standard path.
> 
> > (2) Jump threading and simplify-the-CFG passes independently calls
> > TryToSimplifyUnconditionalBranchFromEmptyBlock() in
> > Transforms/Utils/Local.cpp to get rid of almost empty BBs.
> 
> > (3) TryToSimplifyUnconditionalBranchFromEmtpyBlock() eliminates the
> > placeholder BBs after loop unswitching and merges them into
> > subsequent blocks including the header of the inner loop. Before
> > eliminating the blocks, the function checks if the block is a loop
> > header by looking at its PHI nodes so that it can be saved, but the
> > test fails with the loops with a volatile iteration variable.
> 
> Why does this fail for a volatile iteration variable but not for a
> non-volatile one? I think understanding that will be key to
> understanding how it should be fixed.
> _______________________________________________
> LLVM Developers mailing list
> LLVMdev at cs.uiuc.edu http://llvm.cs.uiuc.edu
> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
-- 

Hal Finkel 
Assistant Computational Scientist 
Leadership Computing Facility 
Argonne National Laboratory 
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20150715/247a0e22/attachment.html>

From:	Chandler Carruth <chandlerc at google.com>
To:	Hyojin Sung/Watson/IBM at IBMUS, llvmdev at cs.uiuc.edu
Date:	07/15/2015 08:35 PM
Subject:	Re: [LLVMdev] Improving loop vectorizer support for loops with
            a volatile iteration variable



On Wed, Jul 15, 2015 at 12:55 PM Hyojin Sung <hsung at us.ibm.com> wrote:
  Hi all,

  I would like to propose an improvement of the “almost dead” block
  elimination in Transforms/Local.cpp so that it will preserve the
  canonical loop form for loops with a volatile iteration variable.

  *** Problem statement
  Nested loops in LCALS Subset B (https://codesign.llnl.gov/LCALS.php) are
  not vectorized with LLVM -O3 because the LLVM loop vectorizer fails the
  test whether the loop latch and exiting block of a loop is the same. The
  loops are vectorizable, and get vectorized with LLVM -O2


I would be interested to know why -O2 succeeds here.


-O2 does not perform loop unswitching which creates artificial empty
placeholder blocks in the outer loop. As long as incrementing and testing
the volatile iteration variable is kept only in the original BB, the block
does not get eliminated.

  and also with other commercial compilers (icc, xlc).

  *** Details
  These loops ended up with different loop latch and exiting block after a
  series of optimizations including loop unswitching, jump threading,
  simplify-the-CFG, and loop simplify. The fundamental problem here is that
  the above optimizations cannot recognize a loop with a volatile iteration
  variable and do not preserve its canonical loop structure.


Ok, meta-level question first:

Why do we care about performance of loops with a volatile iteration
variable? That seems both counter-intuitive and unlikely to be a useful
goal. We simply don't optimize volatile operations well in *any* part of
the optimizer, and I'm not sure why we need to start trying to fix that.
This seems like an irreparably broken benchmark, but perhaps there is a
motivation I don't yet see.


Assuming that sufficient motivation arises to try to fix this, see my
comments below:



  (1) Loop unswitching generates several empty placeholder BBs only with
  PHI nodes after separating out a shorter path with no inner loop
  execution from a standard path.

  (2) Jump threading and simplify-the-CFG passes independently calls
  TryToSimplifyUnconditionalBranchFromEmptyBlock() in
  Transforms/Utils/Local.cpp to get rid of almost empty BBs.

  (3) TryToSimplifyUnconditionalBranchFromEmtpyBlock() eliminates the
  placeholder BBs after loop unswitching and merges them into subsequent
  blocks including the header of the inner loop. Before eliminating the
  blocks, the function checks if the block is a loop header by looking at
  its PHI nodes so that it can be saved, but the test fails with the loops
  with a volatile iteration variable.


Why does this fail for a volatile iteration variable but not for a
non-volatile one? I think understanding that will be key to understanding
how it should be fixed.




-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20150716/670d692e/attachment.html>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: graycol.gif
Type: image/gif
Size: 105 bytes
Desc: not available
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20150716/670d692e/attachment.gif>