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.

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

Thanks
Hari

$ svn diff PruneEH.cpp
Index: PruneEH.cpp

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

Hi David,
I agree that my change only tries to maintain SSA sanity, and doesn't
deal with the impact of removing an unreachable call. Over here, i am
only interested in ensuring that the rest of the phases get clean IR
to operate on.

Do you have any suggestions on an alternate way to fix this issue?

Thanks
Hari