llvm dev - Aug 2015 - Possible bug in adjusting PHINode from removePredecessor?

Hi,
Simple description of the problem below. I have code coming into
pruneEH as follows
fn a {
entry:
call fn b
...

for_cond:
%i = phi [1, entry] [%x, for_body]
cmp $i with someval
cond-br for_body or for_exit

for_body:
...
$x = $i + 1
branch for_cond

for_exit
...
}

PruneEH determines that the call to fn-b won't return. The code is
modified thus.

fn a {
entry:
call fn b
unreachable insn /* Instructions after call to fn-b replaced with
unreachable insn */

for_cond: /* No path from entry block */
%i = phi [%x, for_body]
cmp $i with someval
cond-br for_body or for_exit

for_body:
...
$x = $i + 1
branch for_cond

for_exit
...
}

which then becomes

fn a {
entry:
call fn b
unreachable insn /* Instructions after call to fn-b replaced with
unreachable insn */

for_cond: /* No path from entry block */
cmp $x with someval
cond-br for_body or for_exit

for_body:
...
$x = $x + 1
branch for_cond

for_exit
...
}

The instruction
$x = $x + 1
is obviously illegal in SSA form, which shows up as an infinite loop
in value numbering.

The source of the problem exists in BasicBlock::removePredecessor
function in BasicBlock.cpp. The comment in that function describes
this exact scenario

 // If there are exactly two predecessors, then we want to nuke the PHI nodes
 // altogether. However, we cannot do this, if this in this case:
 //
 // Loop:
 //   %x = phi [X, Loop]
 //   %x2 = add %x, 1        ;; This would become %x2 = add %x2, 1
 //   br Loop                ;; %x2 does not dominate all uses
 //
 // This is because the PHI node input is actually taken from the predecessor
 // basic block. The only case this can happen is with a self loop, so we
 // check for this case explicitly now.

but goes on to cause the same issue. There are 2 potential problems in
this function.

1. The comment above describes a self-loop block. The same problem can
occur in loops with more than 1 block, as our example shows. In
general, this can happen when the predecessor being removed does not
belong to the same loop level as the basic block containing the
PhiNode.
2. The version which introduced this comment r2694 did implement the
self-loop case okay. A subsequent change - revision 22664 - broke
this.

The revision 22664 dates back to 2005, so this issue probably has been
around for 10 years. I am not sure why nobody else has seen a problem
here.

I saw this issue in a large testcase. I will try to get a small repro
to illustrate the issue.

Regards
Hari

Unreachable code has interesting implications for SSA. Unreachable infinite
loops like yours allow formation of code like "%x = add i32 %x, i32
1". I
don't think this is a bug.

It's good form for passes to clean up any unreachable code that they
introduce, but I don't think this is a hard requirement. Downstream passes
are supposed to be resilient to unreachable code. That said, we tend to
solve any problems that arise by inserting more calls to
removeUnreachableBlocks.

On Mon, Aug 10, 2015 at 1:24 PM, Hariharan Sandanagobalane via llvm-dev <
llvm-dev at lists.llvm.org> wrote:
> Hi,
> Simple description of the problem below. I have code coming into
> pruneEH as follows
> fn a {
> entry:
> call fn b
> ...
>
> for_cond:
> %i = phi [1, entry] [%x, for_body]
> cmp $i with someval
> cond-br for_body or for_exit
>
> for_body:
> ...
> $x = $i + 1
> branch for_cond
>
> for_exit
> ...
> }
>
> PruneEH determines that the call to fn-b won't return. The code is
> modified thus.
>
> fn a {
> entry:
> call fn b
> unreachable insn /* Instructions after call to fn-b replaced with
> unreachable insn */
>
> for_cond: /* No path from entry block */
> %i = phi [%x, for_body]
> cmp $i with someval
> cond-br for_body or for_exit
>
> for_body:
> ...
> $x = $i + 1
> branch for_cond
>
> for_exit
> ...
> }
>
> which then becomes
>
> fn a {
> entry:
> call fn b
> unreachable insn /* Instructions after call to fn-b replaced with
> unreachable insn */
>
> for_cond: /* No path from entry block */
> cmp $x with someval
> cond-br for_body or for_exit
>
> for_body:
> ...
> $x = $x + 1
> branch for_cond
>
> for_exit
> ...
> }
>
> The instruction
> $x = $x + 1
> is obviously illegal in SSA form, which shows up as an infinite loop
> in value numbering.
>
> The source of the problem exists in BasicBlock::removePredecessor
> function in BasicBlock.cpp. The comment in that function describes
> this exact scenario
>
>  // If there are exactly two predecessors, then we want to nuke the PHI
> nodes
>  // altogether. However, we cannot do this, if this in this case:
>  //
>  // Loop:
>  //   %x = phi [X, Loop]
>  //   %x2 = add %x, 1        ;; This would become %x2 = add %x2, 1
>  //   br Loop                ;; %x2 does not dominate all uses
>  //
>  // This is because the PHI node input is actually taken from the
> predecessor
>  // basic block. The only case this can happen is with a self loop, so we
>  // check for this case explicitly now.
>
> but goes on to cause the same issue. There are 2 potential problems in
> this function.
>
> 1. The comment above describes a self-loop block. The same problem can
> occur in loops with more than 1 block, as our example shows. In
> general, this can happen when the predecessor being removed does not
> belong to the same loop level as the basic block containing the
> PhiNode.
> 2. The version which introduced this comment r2694 did implement the
> self-loop case okay. A subsequent change - revision 22664 - broke
> this.
>
> The revision 22664 dates back to 2005, so this issue probably has been
> around for 10 years. I am not sure why nobody else has seen a problem
> here.
>
> I saw this issue in a large testcase. I will try to get a small repro
> to illustrate the issue.
>
> Regards
> Hari
> _______________________________________________
> LLVM Developers mailing list
> llvm-dev at lists.llvm.org         http://llvm.cs.uiuc.edu
> http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20150811/5e3ae1f9/attachment-0001.html>

The following change fixes this issue in trunk. Does this fix look good?

Thanks
Hari

$ svn diff PruneEH.cpp
Index: PruneEH.cpp
==================================================================---
PruneEH.cpp (revision 243617)
+++ PruneEH.cpp (working copy)
@@ -268,7 +268,7 @@
   std::vector<BasicBlock*> Succs(succ_begin(BB), succ_end(BB));

   for (unsigned i = 0, e = Succs.size(); i != e; ++i)
-    Succs[i]->removePredecessor(BB);
+    Succs[i]->removePredecessor(BB, true);

   BB->eraseFromParent();
 }

On Mon, Aug 10, 2015 at 1:24 PM, Hariharan Sandanagobalane
<hariharan.gcc at gmail.com> wrote:
> Hi,
> Simple description of the problem below. I have code coming into
> pruneEH as follows
> fn a {
> entry:
> call fn b
> ...
>
> for_cond:
> %i = phi [1, entry] [%x, for_body]
> cmp $i with someval
> cond-br for_body or for_exit
>
> for_body:
> ...
> $x = $i + 1
> branch for_cond
>
> for_exit
> ...
> }
>
> PruneEH determines that the call to fn-b won't return. The code is
> modified thus.
>
> fn a {
> entry:
> call fn b
> unreachable insn /* Instructions after call to fn-b replaced with
> unreachable insn */
>
> for_cond: /* No path from entry block */
> %i = phi [%x, for_body]
> cmp $i with someval
> cond-br for_body or for_exit
>
> for_body:
> ...
> $x = $i + 1
> branch for_cond
>
> for_exit
> ...
> }
>
> which then becomes
>
> fn a {
> entry:
> call fn b
> unreachable insn /* Instructions after call to fn-b replaced with
> unreachable insn */
>
> for_cond: /* No path from entry block */
> cmp $x with someval
> cond-br for_body or for_exit
>
> for_body:
> ...
> $x = $x + 1
> branch for_cond
>
> for_exit
> ...
> }
>
> The instruction
> $x = $x + 1
> is obviously illegal in SSA form, which shows up as an infinite loop
> in value numbering.
>
> The source of the problem exists in BasicBlock::removePredecessor
> function in BasicBlock.cpp. The comment in that function describes
> this exact scenario
>
>  // If there are exactly two predecessors, then we want to nuke the PHI
nodes
>  // altogether. However, we cannot do this, if this in this case:
>  //
>  // Loop:
>  //   %x = phi [X, Loop]
>  //   %x2 = add %x, 1        ;; This would become %x2 = add %x2, 1
>  //   br Loop                ;; %x2 does not dominate all uses
>  //
>  // This is because the PHI node input is actually taken from the
predecessor
>  // basic block. The only case this can happen is with a self loop, so we
>  // check for this case explicitly now.
>
> but goes on to cause the same issue. There are 2 potential problems in
> this function.
>
> 1. The comment above describes a self-loop block. The same problem can
> occur in loops with more than 1 block, as our example shows. In
> general, this can happen when the predecessor being removed does not
> belong to the same loop level as the basic block containing the
> PhiNode.
> 2. The version which introduced this comment r2694 did implement the
> self-loop case okay. A subsequent change - revision 22664 - broke
> this.
>
> The revision 22664 dates back to 2005, so this issue probably has been
> around for 10 years. I am not sure why nobody else has seen a problem
> here.
>
> I saw this issue in a large testcase. I will try to get a small repro
> to illustrate the issue.
>
> Regards
> Hari

I suspect such a change will only paper over your actual problem.

On Wed, Aug 12, 2015 at 2:39 PM, Hariharan Sandanagobalane via llvm-commits
<llvm-commits at lists.llvm.org> wrote:
> The following change fixes this issue in trunk. Does this fix look good?
>
> Thanks
> Hari
>
> $ svn diff PruneEH.cpp
> Index: PruneEH.cpp
> ==================================================================> ---
PruneEH.cpp (revision 243617)
> +++ PruneEH.cpp (working copy)
> @@ -268,7 +268,7 @@
>    std::vector<BasicBlock*> Succs(succ_begin(BB), succ_end(BB));
>
>    for (unsigned i = 0, e = Succs.size(); i != e; ++i)
> -    Succs[i]->removePredecessor(BB);
> +    Succs[i]->removePredecessor(BB, true);
>
>    BB->eraseFromParent();
>  }
>
> On Mon, Aug 10, 2015 at 1:24 PM, Hariharan Sandanagobalane
> <hariharan.gcc at gmail.com> wrote:
> > Hi,
> > Simple description of the problem below. I have code coming into
> > pruneEH as follows
> > fn a {
> > entry:
> > call fn b
> > ...
> >
> > for_cond:
> > %i = phi [1, entry] [%x, for_body]
> > cmp $i with someval
> > cond-br for_body or for_exit
> >
> > for_body:
> > ...
> > $x = $i + 1
> > branch for_cond
> >
> > for_exit
> > ...
> > }
> >
> > PruneEH determines that the call to fn-b won't return. The code is
> > modified thus.
> >
> > fn a {
> > entry:
> > call fn b
> > unreachable insn /* Instructions after call to fn-b replaced with
> > unreachable insn */
> >
> > for_cond: /* No path from entry block */
> > %i = phi [%x, for_body]
> > cmp $i with someval
> > cond-br for_body or for_exit
> >
> > for_body:
> > ...
> > $x = $i + 1
> > branch for_cond
> >
> > for_exit
> > ...
> > }
> >
> > which then becomes
> >
> > fn a {
> > entry:
> > call fn b
> > unreachable insn /* Instructions after call to fn-b replaced with
> > unreachable insn */
> >
> > for_cond: /* No path from entry block */
> > cmp $x with someval
> > cond-br for_body or for_exit
> >
> > for_body:
> > ...
> > $x = $x + 1
> > branch for_cond
> >
> > for_exit
> > ...
> > }
> >
> > The instruction
> > $x = $x + 1
> > is obviously illegal in SSA form, which shows up as an infinite loop
> > in value numbering.
> >
> > The source of the problem exists in BasicBlock::removePredecessor
> > function in BasicBlock.cpp. The comment in that function describes
> > this exact scenario
> >
> >  // If there are exactly two predecessors, then we want to nuke the
PHI
> nodes
> >  // altogether. However, we cannot do this, if this in this case:
> >  //
> >  // Loop:
> >  //   %x = phi [X, Loop]
> >  //   %x2 = add %x, 1        ;; This would become %x2 = add %x2, 1
> >  //   br Loop                ;; %x2 does not dominate all uses
> >  //
> >  // This is because the PHI node input is actually taken from the
> predecessor
> >  // basic block. The only case this can happen is with a self loop, so
we
> >  // check for this case explicitly now.
> >
> > but goes on to cause the same issue. There are 2 potential problems in
> > this function.
> >
> > 1. The comment above describes a self-loop block. The same problem can
> > occur in loops with more than 1 block, as our example shows. In
> > general, this can happen when the predecessor being removed does not
> > belong to the same loop level as the basic block containing the
> > PhiNode.
> > 2. The version which introduced this comment r2694 did implement the
> > self-loop case okay. A subsequent change - revision 22664 - broke
> > this.
> >
> > The revision 22664 dates back to 2005, so this issue probably has been
> > around for 10 years. I am not sure why nobody else has seen a problem
> > here.
> >
> > I saw this issue in a large testcase. I will try to get a small repro
> > to illustrate the issue.
> >
> > Regards
> > Hari
> _______________________________________________
> llvm-commits mailing list
> llvm-commits at lists.llvm.org
> http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-commits
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20150812/95ff43fd/attachment.html>