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

[Reid Kleckner via llvm-dev]

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>