Subzero: Fix lowering for x86 div/rem instructions.

Subzero: Fix lowering for x86 div/rem instructions.

The x86 lowering sequences for sdiv/udiv/srem/urem all have a problem, in that they don't reflect the fact that two registers are affected by the instruction.

For example, the urem instruction:
  dest = src0 urem src1
lowers to something like this:
  t1:eax = src0
  t2:edx = 0
  t2:edx = (t1:eax and t2:edx) div src1
  dest = t2:edx

The problem is that there is no indication that the div instruction smashes eax.  As such, it's possible that the register allocator could erroneously assume that src0 is still available in eax after the div instruction.

To fix this, we make use of the FakeDef instruction.  In this example, we change the div instruction to "officially" produce eax as its result, then fakedef edx in terms of eax.  This means that as long as the urem result is actually used, the definitions of eax and edx will be preserved, but if the urem result is unused, then the whole sequence can be dead-code eliminated.

  t1:eax = src0
  t2:edx = 0
  t1:eax = (t1:eax and t2:edx) div src1  # dest var changed to t1:eax
  t2:edx = fakedef t1:eax                # fakedef instruction added
  dest = t2:edx

BUG= none
R=jpp@chromium.org

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

[Jim Stichnoth, 2016-07-18 23:31:57]

Description was changed from

==========
Subzero: Fix lowering for x86 div/rem instructions.

BUG= none
==========

to

==========
Subzero: Fix lowering for x86 div/rem instructions.

The x86 lowering sequences for sdiv/udiv/srem/urem all have a problem, in that
they don't reflect the fact that two registers are affected by the instruction.

For example, the urem instruction:
  dest = src0 urem src1
lowers to something like this:
  t1:eax = src0
  t2:edx = 0
  t2:edx = (t1:eax and t2:edx) div src1
  dest = t2:edx

The problem is that there is no indication that the div instruction smashes eax.
 As such, it's possible that the register allocator could erroneously assume
that src0 is still available in eax after the div instruction.

To fix this, we make use of the FakeDef instruction.  In this example, we change
the div instruction to "officially" produce eax as its result, then fakedef edx
in terms of eax.  This means that as long as the urem result is actually used,
the definitions of eax and edx will be preserved, but if the urem result is
unused, then the whole sequence can be dead-code eliminated.

  t1:eax = src0
  t2:edx = 0
  t1:eax = (t1:eax and t2:edx) div src1
  t2:edx = fakedef t1:eax
  dest = t2:edx

BUG= none
==========

[Jim Stichnoth, 2016-07-18 23:33:01]

Description was changed from

==========
Subzero: Fix lowering for x86 div/rem instructions.

The x86 lowering sequences for sdiv/udiv/srem/urem all have a problem, in that
they don't reflect the fact that two registers are affected by the instruction.

For example, the urem instruction:
  dest = src0 urem src1
lowers to something like this:
  t1:eax = src0
  t2:edx = 0
  t2:edx = (t1:eax and t2:edx) div src1
  dest = t2:edx

The problem is that there is no indication that the div instruction smashes eax.
 As such, it's possible that the register allocator could erroneously assume
that src0 is still available in eax after the div instruction.

To fix this, we make use of the FakeDef instruction.  In this example, we change
the div instruction to "officially" produce eax as its result, then fakedef edx
in terms of eax.  This means that as long as the urem result is actually used,
the definitions of eax and edx will be preserved, but if the urem result is
unused, then the whole sequence can be dead-code eliminated.

  t1:eax = src0
  t2:edx = 0
  t1:eax = (t1:eax and t2:edx) div src1
  t2:edx = fakedef t1:eax
  dest = t2:edx

BUG= none
==========

to

==========
Subzero: Fix lowering for x86 div/rem instructions.

The x86 lowering sequences for sdiv/udiv/srem/urem all have a problem, in that
they don't reflect the fact that two registers are affected by the instruction.

For example, the urem instruction:
  dest = src0 urem src1
lowers to something like this:
  t1:eax = src0
  t2:edx = 0
  t2:edx = (t1:eax and t2:edx) div src1
  dest = t2:edx

The problem is that there is no indication that the div instruction smashes eax.
 As such, it's possible that the register allocator could erroneously assume
that src0 is still available in eax after the div instruction.

To fix this, we make use of the FakeDef instruction.  In this example, we change
the div instruction to "officially" produce eax as its result, then fakedef edx
in terms of eax.  This means that as long as the urem result is actually used,
the definitions of eax and edx will be preserved, but if the urem result is
unused, then the whole sequence can be dead-code eliminated.

  t1:eax = src0
  t2:edx = 0
  t1:eax = (t1:eax and t2:edx) div src1  # dest var changed to t1:eax
  t2:edx = fakedef t1:eax                # fakedef instruction added
  dest = t2:edx

BUG= none
==========

[Jim Stichnoth, 2016-07-18 23:33:35]

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

[Jim Stichnoth, 2016-07-18 23:36:10]

Spec2k output is unchanged by this, except for emitting commented-out "fakedef"
instructions.

I was unable to construct any failing tests against the original code, but it
showed up in the local variable splitting CL I'm working on now.

[John, 2016-07-19 03:18:19]

lgtm

https://codereview.chromium.org/2158213002/diff/1/src/IceTargetLoweringX86Bas...
File src/IceTargetLoweringX86BaseImpl.h (right):

https://codereview.chromium.org/2158213002/diff/1/src/IceTargetLoweringX86Bas...
src/IceTargetLoweringX86BaseImpl.h:2349: Context.insert<InstFakeDef>(T, T_edx);
can you use the _redefined method here?

_redefined(Context.insert<InstFakeDef>(T, T_edx))

[Jim Stichnoth, 2016-07-19 13:35:35]

https://codereview.chromium.org/2158213002/diff/1/src/IceTargetLoweringX86Bas...
File src/IceTargetLoweringX86BaseImpl.h (right):

https://codereview.chromium.org/2158213002/diff/1/src/IceTargetLoweringX86Bas...
src/IceTargetLoweringX86BaseImpl.h:2349: Context.insert<InstFakeDef>(T, T_edx);
On 2016/07/19 03:18:19, John wrote:
> can you use the _redefined method here?
> 
> _redefined(Context.insert<InstFakeDef>(T, T_edx))

Done.

[Jim Stichnoth, 2016-07-19 13:35:56]

Description was changed from

==========
Subzero: Fix lowering for x86 div/rem instructions.

The x86 lowering sequences for sdiv/udiv/srem/urem all have a problem, in that
they don't reflect the fact that two registers are affected by the instruction.

For example, the urem instruction:
  dest = src0 urem src1
lowers to something like this:
  t1:eax = src0
  t2:edx = 0
  t2:edx = (t1:eax and t2:edx) div src1
  dest = t2:edx

The problem is that there is no indication that the div instruction smashes eax.
 As such, it's possible that the register allocator could erroneously assume
that src0 is still available in eax after the div instruction.

To fix this, we make use of the FakeDef instruction.  In this example, we change
the div instruction to "officially" produce eax as its result, then fakedef edx
in terms of eax.  This means that as long as the urem result is actually used,
the definitions of eax and edx will be preserved, but if the urem result is
unused, then the whole sequence can be dead-code eliminated.

  t1:eax = src0
  t2:edx = 0
  t1:eax = (t1:eax and t2:edx) div src1  # dest var changed to t1:eax
  t2:edx = fakedef t1:eax                # fakedef instruction added
  dest = t2:edx

BUG= none
==========

to

==========
Subzero: Fix lowering for x86 div/rem instructions.

The x86 lowering sequences for sdiv/udiv/srem/urem all have a problem, in that
they don't reflect the fact that two registers are affected by the instruction.

For example, the urem instruction:
  dest = src0 urem src1
lowers to something like this:
  t1:eax = src0
  t2:edx = 0
  t2:edx = (t1:eax and t2:edx) div src1
  dest = t2:edx

The problem is that there is no indication that the div instruction smashes eax.
 As such, it's possible that the register allocator could erroneously assume
that src0 is still available in eax after the div instruction.

To fix this, we make use of the FakeDef instruction.  In this example, we change
the div instruction to "officially" produce eax as its result, then fakedef edx
in terms of eax.  This means that as long as the urem result is actually used,
the definitions of eax and edx will be preserved, but if the urem result is
unused, then the whole sequence can be dead-code eliminated.

  t1:eax = src0
  t2:edx = 0
  t1:eax = (t1:eax and t2:edx) div src1  # dest var changed to t1:eax
  t2:edx = fakedef t1:eax                # fakedef instruction added
  dest = t2:edx

BUG= none
R=jpp@chromium.org

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

[Jim Stichnoth, 2016-07-19 13:35:57]

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