Instcombine can't remove a PHI cycle when that cycle should be replaced with a PHI

[sbaranga-arm]

Bugzilla Link	25585
Version	trunk
OS	Linux
Attachments	The reproducer
CC	@majnemer,@hfinkel

Extended Description

For the following IR, instcombine should be able to replace %p1 and %p2 with %p0.

target triple = "aarch64-linux-gnueabi"

define i32 @​f(i1 %c) {
entry:
br i1 %c, label %if.else, label %pre

if.else:
br label %pre

pre:
%p0 = phi i32 [ 0, %entry ], [ 1, %if.else ]
br label %loop

loop:
%p1 = phi i32 [ %p2, %loop ], [ %p0, %pre ]
%p2 = phi i32 [ %p0, %loop ] , [ %p1, %pre ]
br i1 %c, label %loop, label %exit

exit:
ret i32 %p2
}

We're already trying to do this, but the current phi cycle elimination algorithm can't handle the case where the value that we should be replacing other the PHIs with is another PHI (in this case %p).

When the value that we would replace the PHI cycle with is not a PHI, this algorithm works as expected:

define i32 @​g(i1 %c, i32 %val) {
entry:
br label %pre

pre:
br label %loop

loop:
%p1 = phi i32 [ %p2, %loop ], [ %val, %pre ]
%p2 = phi i32 [ %val, %loop ] , [ %p1, %pre ]
br i1 %c, label %loop, label %exit

exit:
ret i32 %p2
}

Reproduce with: opt -instcombine ind.ll -S -o -