[llvm-dev] Possible bug in adjusting PHINode from removePredecessor?

[Hariharan Sandanagobalane via llvm-dev]

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