Subzero, MIPS32: Intrinsic call Cttz for i32

Subzero, MIPS32: Intrinsic call Cttz for i32

Implements intrinsic call llvm.cttz for i32

R=stichnot@chromium.org

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

[obucinac, 2016-09-22 19:21:55]

Description was changed from

==========
Subzero, MIPS32: Intrinsic call Cttz for i32

Implements intrinsic call llvm.ctlz for i32
==========

to

==========
Subzero, MIPS32: Intrinsic call Cttz for i32

Implements intrinsic call llvm.ctlz for i32
==========

[obucinac, 2016-09-22 19:21:56]

obucinac@gmail.com changed reviewers:
+ eholk@chromium.org, jaydeep.patil@imgtec.com, jpp@chromium.org,
kschimpf@google.com, sagar.thakur@imgtec.com, stichnot@chromium.org

[obucinac, 2016-09-22 19:29:58]

This is partially done (encoding check is missing), and not suitable for commit
at the moment. I just need comments on what may be wrong here.

In Om1, it produces desired code:

addiu   $v1, $v0, -1
nor     $a0, $v0, $zero
and     $v1, $a0, $v1
clz     $v1, $v1
addiu   $a0, $zero, 32
subu    $a0, $a0, $v1

Similar to what llc produces:

addiu	$1, $4, -1              # encoding: [0xff,0xff,0x81,0x24]
not	$2, $4                  # encoding: [0x27,0x10,0x80,0x00]
and	$1, $2, $1              # encoding: [0x24,0x08,0x41,0x00]
clz	$1, $1                  # encoding: [0x20,0x08,0x21,0x70]
addiu	$2, $zero, 32           # encoding: [0x20,0x00,0x02,0x24]
subu	$2, $2, $1              # encoding: [0x23,0x10,0x41,0x00]
jr	$ra                     # encoding: [0x08,0x00,0xe0,0x03]

However, in O2, I am getting liveness errors.

LLC, in O2, produces same code, but with jr in front of subu:

addiu	$1, $4, -1              # encoding: [0xff,0xff,0x81,0x24]
not	$2, $4                  # encoding: [0x27,0x10,0x80,0x00]
and	$1, $2, $1              # encoding: [0x24,0x08,0x41,0x00]
clz	$1, $1                  # encoding: [0x20,0x08,0x21,0x70]
addiu	$2, $zero, 32           # encoding: [0x20,0x00,0x02,0x24]
jr	$ra                     # encoding: [0x08,0x00,0xe0,0x03]
subu	$2, $2, $1              # encoding: [0x23,0x10,0x41,0x00]

[obucinac, 2016-09-22 19:30:27]

Description was changed from

==========
Subzero, MIPS32: Intrinsic call Cttz for i32

Implements intrinsic call llvm.ctlz for i32
==========

to

==========
Subzero, MIPS32: Intrinsic call Cttz for i32

Implements intrinsic call llvm.cttz for i32
==========

[Jim Stichnoth, 2016-09-23 06:13:07]

On 2016/09/22 19:29:58, obucinac wrote:
> This is partially done (encoding check is missing), and not suitable for
commit
> at the moment. I just need comments on what may be wrong here.
> 
> In Om1, it produces desired code:
> 
> addiu   $v1, $v0, -1
> nor     $a0, $v0, $zero
> and     $v1, $a0, $v1
> clz     $v1, $v1
> addiu   $a0, $zero, 32
> subu    $a0, $a0, $v1
> 
> Similar to what llc produces:
> 
> addiu	$1, $4, -1              # encoding: [0xff,0xff,0x81,0x24]
> not	$2, $4                  # encoding: [0x27,0x10,0x80,0x00]
> and	$1, $2, $1              # encoding: [0x24,0x08,0x41,0x00]
> clz	$1, $1                  # encoding: [0x20,0x08,0x21,0x70]
> addiu	$2, $zero, 32           # encoding: [0x20,0x00,0x02,0x24]
> subu	$2, $2, $1              # encoding: [0x23,0x10,0x41,0x00]
> jr	$ra                     # encoding: [0x08,0x00,0xe0,0x03]
> 
> However, in O2, I am getting liveness errors.
> 
> LLC, in O2, produces same code, but with jr in front of subu:
> 
> addiu	$1, $4, -1              # encoding: [0xff,0xff,0x81,0x24]
> not	$2, $4                  # encoding: [0x27,0x10,0x80,0x00]
> and	$1, $2, $1              # encoding: [0x24,0x08,0x41,0x00]
> clz	$1, $1                  # encoding: [0x20,0x08,0x21,0x70]
> addiu	$2, $zero, 32           # encoding: [0x20,0x00,0x02,0x24]
> jr	$ra                     # encoding: [0x08,0x00,0xe0,0x03]
> subu	$2, $2, $1              # encoding: [0x23,0x10,0x41,0x00]

If you run "pnacl-sz ... -verbose=all", you get more detailed output, including
an attempt to explain the liveness error.

In -O2 compilation, liveness analysis includes full live range construction for
use in register allocation.  To make live range construction fast, the data
structures assume/require that any variable has its live range begin at most
once in a block, and end at most once in a block.

What I get from the diagnostic messages is that T2 has two distinct live ranges
in the cttz lowering sequence.  To fix it, I would do something like this:
  _addiu(T1, SrcR, -1);
  _not(T2, SrcR);
  _and(T3, T2, T1);
  _clz(T4, T3);
  _addiu(T5, getZero(), 32);
  _subu(T6, T5, T4);
  _mov(Dest, T6);

[Jim Stichnoth, 2016-09-23 06:13:47]

https://codereview.chromium.org/2358393004/diff/1/src/IceTargetLoweringMIPS32...
File src/IceTargetLoweringMIPS32.cpp (right):

https://codereview.chromium.org/2358393004/diff/1/src/IceTargetLoweringMIPS32...
src/IceTargetLoweringMIPS32.cpp:2862: Context.insert<InstFakeUse>(SrcR);
This FakeUse doesn't seem necessary?

[obucinac, 2016-09-23 11:37:33]

https://codereview.chromium.org/2358393004/diff/1/src/IceTargetLoweringMIPS32...
File src/IceTargetLoweringMIPS32.cpp (right):

https://codereview.chromium.org/2358393004/diff/1/src/IceTargetLoweringMIPS32...
src/IceTargetLoweringMIPS32.cpp:2862: Context.insert<InstFakeUse>(SrcR);
On 2016/09/23 06:13:47, stichnot wrote:
> This FakeUse doesn't seem necessary?

Done.

[Jim Stichnoth, 2016-09-23 13:59:39]

lgtm

[Jim Stichnoth, 2016-09-23 13:59:52]

Description was changed from

==========
Subzero, MIPS32: Intrinsic call Cttz for i32

Implements intrinsic call llvm.cttz for i32
==========

to

==========
Subzero, MIPS32: Intrinsic call Cttz for i32

Implements intrinsic call llvm.cttz for i32

R=stichnot@chromium.org

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

[Jim Stichnoth, 2016-09-23 13:59:54]

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