Subzero: Fix a bug in advanced phi lowering.

Subzero: Fix a bug in advanced phi lowering.

The motivating example (simplified) is this:

%__698:eax = phi i32 [ %__646:ebx, %__188 ] // LIVEEND={%__646:ebx}
%__617:bh =  phi i8  [ %__618:ah,  %__188 ] // LIVEEND={%__618:ah}
%__615:bl =  phi i8  [ %__616:al,  %__188 ] // LIVEEND={%__616:al}

By default, it first lowers the __698 assignment.  However, that assignment has two "predecessors" because there are two other instructions whose dest variable aliases the __698 assignment's source operand.  This triggers an assertion failure where we assume there is only one predecessor.

The fix is two-pronged.  First, we go ahead and generate as many temp assignments as needed to break the cycle, simply by changing an "if" to a "while".  Second, when we need to break a cycle, we give preference to an instruction with only one predecessor so that only one temp assignment needs to be added.

(It might be possible to prove that the second approach, i.e. preferring single-predecessor assignments, makes the first approach unnecessary, i.e. changing "if" to "while".)

This change has no effect on the x86 output for spec2k.

BUG= https://bugs.chromium.org/p/nativeclient/issues/detail?id=4365
R=jpp@chromium.org

Committed: https://gerrit.chromium.org/gerrit/gitweb?p=native_client/pnacl-subzero.git;a=commit;h=bbd449d2042278c004d9bad80c529f88092b4550

[Jim Stichnoth, 2016-03-30 15:53:12]

Description was changed from

==========
Subzero: Fix a bug in advanced phi lowering.

BUG= https://bugs.chromium.org/p/nativeclient/issues/detail?id=4365
==========

to

==========
Subzero: Fix a bug in advanced phi lowering.

The motivating example (simplified) is this:

%__698:eax = phi i32 [ %__646:ebx, %__188 ] // LIVEEND={%__646:ebx}
%__617:bh =  phi i8  [ %__618:ah,  %__188 ] // LIVEEND={%__618:ah}
%__615:bl =  phi i8  [ %__616:al,  %__188 ] // LIVEEND={%__616:al}

By default, it first lowers the __698 assignment.  However, that assignment has
two "predecessors" because there are two other instructions whose dest variable
aliases the __698 assignment's source operand.  This triggers an assertion
failure where we assume there is only one predecessor.

The fix is two-pronged.  First, we go ahead and generate as many temp
assignments as needed to break the cycle, simply by changing an "if" to a
"while".  Second, when we need to break a cycle, we give preference to an
instruction with only one predecessor so that only one temp assignment needs to
be added.

(It might be possible to prove that the second approach, i.e. preferring
single-predecessor assignments, makes the first approach unnecessary, i.e.
changing "if" to "while".)

This change has no effect on the x86 output for spec2k.

BUG= https://bugs.chromium.org/p/nativeclient/issues/detail?id=4365
==========

[Jim Stichnoth, 2016-03-30 15:56:57]

stichnot@chromium.org changed reviewers:
+ eholk@chromium.org, jpp@chromium.org, kschimpf@google.com, sehr@chromium.org

[John, 2016-03-30 15:59:47]

is it possible to add a test for this?

[John, 2016-03-30 15:59:54]

lgtm

[Jim Stichnoth, 2016-03-30 22:30:12]

On 2016/03/30 15:59:47, John wrote:
> is it possible to add a test for this?

I tried, but I just can't seem to outsmart the compiler.  :(

[Jim Stichnoth, 2016-03-30 22:30:33]

Description was changed from

==========
Subzero: Fix a bug in advanced phi lowering.

The motivating example (simplified) is this:

%__698:eax = phi i32 [ %__646:ebx, %__188 ] // LIVEEND={%__646:ebx}
%__617:bh =  phi i8  [ %__618:ah,  %__188 ] // LIVEEND={%__618:ah}
%__615:bl =  phi i8  [ %__616:al,  %__188 ] // LIVEEND={%__616:al}

By default, it first lowers the __698 assignment.  However, that assignment has
two "predecessors" because there are two other instructions whose dest variable
aliases the __698 assignment's source operand.  This triggers an assertion
failure where we assume there is only one predecessor.

The fix is two-pronged.  First, we go ahead and generate as many temp
assignments as needed to break the cycle, simply by changing an "if" to a
"while".  Second, when we need to break a cycle, we give preference to an
instruction with only one predecessor so that only one temp assignment needs to
be added.

(It might be possible to prove that the second approach, i.e. preferring
single-predecessor assignments, makes the first approach unnecessary, i.e.
changing "if" to "while".)

This change has no effect on the x86 output for spec2k.

BUG= https://bugs.chromium.org/p/nativeclient/issues/detail?id=4365
==========

to

==========
Subzero: Fix a bug in advanced phi lowering.

The motivating example (simplified) is this:

%__698:eax = phi i32 [ %__646:ebx, %__188 ] // LIVEEND={%__646:ebx}
%__617:bh =  phi i8  [ %__618:ah,  %__188 ] // LIVEEND={%__618:ah}
%__615:bl =  phi i8  [ %__616:al,  %__188 ] // LIVEEND={%__616:al}

By default, it first lowers the __698 assignment.  However, that assignment has
two "predecessors" because there are two other instructions whose dest variable
aliases the __698 assignment's source operand.  This triggers an assertion
failure where we assume there is only one predecessor.

The fix is two-pronged.  First, we go ahead and generate as many temp
assignments as needed to break the cycle, simply by changing an "if" to a
"while".  Second, when we need to break a cycle, we give preference to an
instruction with only one predecessor so that only one temp assignment needs to
be added.

(It might be possible to prove that the second approach, i.e. preferring
single-predecessor assignments, makes the first approach unnecessary, i.e.
changing "if" to "while".)

This change has no effect on the x86 output for spec2k.

BUG= https://bugs.chromium.org/p/nativeclient/issues/detail?id=4365
R=jpp@chromium.org

Committed:
https://gerrit.chromium.org/gerrit/gitweb?p=native_client/pnacl-subzero.git;a...
==========

[Jim Stichnoth, 2016-03-30 22:30:35]

Committed patchset #2 (id:20001) manually as
bbd449d2042278c004d9bad80c529f88092b4550 (presubmit successful).