Subzero: Transform suitable Load/Arith/Store sequences into RMW ops.

Subzero: Transform suitable Load/Arith/Store sequences into RMW ops.

Search for sequences of Load/Arith/Store instructions that can be transformed into single non-atomic Read-Modify-Write instructions.  Corresponding operands must match up, and it is limited to the operator/type combinations that have simple lowerings.

For suitable sequences, an RMW pseudo-instruction is added.  Extra variables are attached to the RMW instruction and the original Store instruction, to make it easy to figure out whether to retain the original Store instruction or the new RMW instruction (but never both).

The RMW instructions are similar to their non-RMW counterparts, except that the RMW instruction has no Dest variable - the Src[0] operand doubles as the memory-operand dest.

The x86-32 integrated assembler has some new forms of existing instructions added.

Note: this CL puts the machinery in place to identify, lower, and emit RMW operations only for the "add" instruction operating on i32/i16/i8 operands.  The next CL will fill in the rest of the options.

BUG= https://code.google.com/p/nativeclient/issues/detail?id=4095
R=jvoung@chromium.org

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

[Jim Stichnoth, 2015-06-16 07:04:27]

stichnot@chromium.org changed reviewers:
+ jpp@chromium.org, jvoung@chromium.org, kschimpf@google.com,
mtrofin@chromium.org

[jvoung (off chromium), 2015-06-16 17:59:22]

https://codereview.chromium.org/1182603004/diff/20001/src/IceInst.cpp
File src/IceInst.cpp (right):

https://codereview.chromium.org/1182603004/diff/20001/src/IceInst.cpp#newcode429
src/IceInst.cpp:429: addSource(Data);
Would it be safer to have nullptr as the dummy? Then the getRmwBeacon() would be
dyn_cast_or_null<...>(). Otherwise what happens if Data is a variable. Would the
Beacon be right?

https://codereview.chromium.org/1182603004/diff/20001/src/IceInst.cpp#newcode433
src/IceInst.cpp:433: Dest = llvm::dyn_cast<Variable>(getData());
is this okay if Data isn't a variable when setting the rmw beacon?

https://codereview.chromium.org/1182603004/diff/20001/src/IceInstX8632.cpp
File src/IceInstX8632.cpp (right):

https://codereview.chromium.org/1182603004/diff/20001/src/IceInstX8632.cpp#ne...
src/IceInstX8632.cpp:389: getData()->dump(Func);
Would it be helpful for this to dump the beacon too?

https://codereview.chromium.org/1182603004/diff/20001/src/IceInstX8632.h
File src/IceInstX8632.h (right):

https://codereview.chromium.org/1182603004/diff/20001/src/IceInstX8632.h#newc...
src/IceInstX8632.h:814: static InstX8632BinopRMW *create(Cfg *Func, Operand
*DestSrc0,
Can DestSrc0 be type OperandX8632* ? Store uses OperandX8632* as the "Mem"
argument type.

https://codereview.chromium.org/1182603004/diff/20001/src/IceTargetLoweringX8...
File src/IceTargetLoweringX8632.cpp (right):

https://codereview.chromium.org/1182603004/diff/20001/src/IceTargetLoweringX8...
src/IceTargetLoweringX8632.cpp:593: return !isI64 && !isVector; //
TODO(stichnot): implement
not TODO for Add anymore?

https://codereview.chromium.org/1182603004/diff/20001/src/IceTargetLoweringX8...
src/IceTargetLoweringX8632.cpp:611: //   shift on i64 and vectors
Maybe put this earlier, to explain the "return !isI64 && !isVector;" conditions

https://codereview.chromium.org/1182603004/diff/20001/src/IceTargetLoweringX8...
src/IceTargetLoweringX8632.cpp:645: //   b = Store b, addr, x
Is this redefinition of b from " b = Store b, addr, x" okay for liveness because
of inferTwoAddress ?

https://codereview.chromium.org/1182603004/diff/20001/src/IceTargetLoweringX8...
src/IceTargetLoweringX8632.cpp:688: Node->getInsts().insert(I3, RMW);
Just checking: should this be insert(I3, RMW) or insert(BeaconDef, RMW)?

https://codereview.chromium.org/1182603004/diff/20001/src/IceTargetLoweringX8...
src/IceTargetLoweringX8632.cpp:4494: void TargetX8632::doAddressOptStore() {
At some point, is it worth having a doAddressOptRMW() ?

[Jim Stichnoth, 2015-06-17 00:15:40]

https://codereview.chromium.org/1182603004/diff/20001/src/IceInst.cpp
File src/IceInst.cpp (right):

https://codereview.chromium.org/1182603004/diff/20001/src/IceInst.cpp#newcode429
src/IceInst.cpp:429: addSource(Data);
On 2015/06/16 17:59:21, jvoung wrote:
> Would it be safer to have nullptr as the dummy? Then the getRmwBeacon() would
be
> dyn_cast_or_null<...>(). Otherwise what happens if Data is a variable. Would
the
> Beacon be right?

There's a strong assumption that source operands are non-null (see e.g. the
assert in Inst::addSource()), so that's not a possibility.

The main requirement for the default value is that it does not change the
liveness analysis for existing variables in the Cfg.  One possibility is to use
an operand that contains no variables, such as a constant 0 or undef.  But I'm
not thrilled about doing a locked constant pool lookup for that.  Instead, I
chose to reuse the Data operand because if it contains any uses of variables, it
doesn't affect liveness whether there are one versus two uses of the same
variable.

https://codereview.chromium.org/1182603004/diff/20001/src/IceInst.cpp#newcode433
src/IceInst.cpp:433: Dest = llvm::dyn_cast<Variable>(getData());
On 2015/06/16 17:59:21, jvoung wrote:
> is this okay if Data isn't a variable when setting the rmw beacon?

Yes - the RMW optimization should only be calling setRmwBeacon when Data is the
same as the Dest of the preceding arithmetic instruction.

But if that doesn't happen, and Data is not a variable, then Dest gets set to
nullptr and the Store instruction cannot be DCE'd and so the RMW instruction
lowering will remove itself.

https://codereview.chromium.org/1182603004/diff/20001/src/IceInstX8632.cpp
File src/IceInstX8632.cpp (right):

https://codereview.chromium.org/1182603004/diff/20001/src/IceInstX8632.cpp#ne...
src/IceInstX8632.cpp:389: getData()->dump(Func);
On 2015/06/16 17:59:21, jvoung wrote:
> Would it be helpful for this to dump the beacon too?

Done.

https://codereview.chromium.org/1182603004/diff/20001/src/IceInstX8632.h
File src/IceInstX8632.h (right):

https://codereview.chromium.org/1182603004/diff/20001/src/IceInstX8632.h#newc...
src/IceInstX8632.h:814: static InstX8632BinopRMW *create(Cfg *Func, Operand
*DestSrc0,
On 2015/06/16 17:59:21, jvoung wrote:
> Can DestSrc0 be type OperandX8632* ? Store uses OperandX8632* as the "Mem"
> argument type.

It turns out it can just as well be OperandX8632Mem.

The Store instruction can't use OperandX8632Mem because of VariableSplit, but
that shouldn't be an option here.

https://codereview.chromium.org/1182603004/diff/20001/src/IceTargetLoweringX8...
File src/IceTargetLoweringX8632.cpp (right):

https://codereview.chromium.org/1182603004/diff/20001/src/IceTargetLoweringX8...
src/IceTargetLoweringX8632.cpp:593: return !isI64 && !isVector; //
TODO(stichnot): implement
On 2015/06/16 17:59:22, jvoung wrote:
> not TODO for Add anymore?

I meant implement the i64 and vector variants.  Clarified.

https://codereview.chromium.org/1182603004/diff/20001/src/IceTargetLoweringX8...
src/IceTargetLoweringX8632.cpp:611: //   shift on i64 and vectors
On 2015/06/16 17:59:22, jvoung wrote:
> Maybe put this earlier, to explain the "return !isI64 && !isVector;"
conditions

Done.

https://codereview.chromium.org/1182603004/diff/20001/src/IceTargetLoweringX8...
src/IceTargetLoweringX8632.cpp:645: //   b = Store b, addr, x
On 2015/06/16 17:59:21, jvoung wrote:
> Is this redefinition of b from " b = Store b, addr, x" okay for liveness
because
> of inferTwoAddress ?

Yes, clarified in the comment.

https://codereview.chromium.org/1182603004/diff/20001/src/IceTargetLoweringX8...
src/IceTargetLoweringX8632.cpp:688: Node->getInsts().insert(I3, RMW);
On 2015/06/16 17:59:21, jvoung wrote:
> Just checking: should this be insert(I3, RMW) or insert(BeaconDef, RMW)?

This is as intended.  First we insert the BeaconDef before I3 (the store
instruction):
  I1: a = Load addr
  I2: b = <op> a, other
      x = FakeDef
  I3: b = Store b, addr, x

Then we insert the RMW before I3:
  I1: a = Load addr
  I2: b = <op> a, other
      x = FakeDef
      RMW <op>, addr, other, x
  I3: b = Store b, addr, x

https://codereview.chromium.org/1182603004/diff/20001/src/IceTargetLoweringX8...
src/IceTargetLoweringX8632.cpp:4494: void TargetX8632::doAddressOptStore() {
On 2015/06/16 17:59:22, jvoung wrote:
> At some point, is it worth having a doAddressOptRMW() ?

Yikes!  I didn't mean to disable address mode optimization for RMW.

I moved findRMW() to be after address mode optimization, using a deeper test of
whether the Load and Dest addresses are the same.

[jvoung (off chromium), 2015-06-17 16:40:23]

otherwise LGTM

https://codereview.chromium.org/1182603004/diff/20001/src/IceTargetLoweringX8...
File src/IceTargetLoweringX8632.cpp (right):

https://codereview.chromium.org/1182603004/diff/20001/src/IceTargetLoweringX8...
src/IceTargetLoweringX8632.cpp:4494: void TargetX8632::doAddressOptStore() {
On 2015/06/17 00:15:40, stichnot wrote:
> On 2015/06/16 17:59:22, jvoung wrote:
> > At some point, is it worth having a doAddressOptRMW() ?
> 
> Yikes!  I didn't mean to disable address mode optimization for RMW.
> 
> I moved findRMW() to be after address mode optimization, using a deeper test
of
> whether the Load and Dest addresses are the same.


Could add a test case to the .ll that shows address mode optimization still
succeeds from the new pass ordering?

https://codereview.chromium.org/1182603004/diff/40001/src/IceInstX8632.h
File src/IceInstX8632.h (right):

https://codereview.chromium.org/1182603004/diff/40001/src/IceInstX8632.h#newc...
src/IceInstX8632.h:317: // InstX8632FakeRMW represents a non-atomic
read-modify-write
In this case the "Fake" seems a bit different from FakeDef/FakeUse. It seems to
represent more of a high level instruction that hasn't been lowered yet (like
AddRMW is). Might be worth pointing out that there's still some lowering?

https://codereview.chromium.org/1182603004/diff/40001/src/IceInstX8632.h#newc...
src/IceInstX8632.h:840: InstX8632BinopRMW(Cfg *Func, Operand *DestSrc0, Operand
*Src1)
OperandX8632Mem *DestSrc0 too?

[Jim Stichnoth, 2015-06-18 05:15:12]

https://codereview.chromium.org/1182603004/diff/20001/src/IceTargetLoweringX8...
File src/IceTargetLoweringX8632.cpp (right):

https://codereview.chromium.org/1182603004/diff/20001/src/IceTargetLoweringX8...
src/IceTargetLoweringX8632.cpp:4494: void TargetX8632::doAddressOptStore() {
On 2015/06/17 16:40:22, jvoung wrote:
> On 2015/06/17 00:15:40, stichnot wrote:
> > On 2015/06/16 17:59:22, jvoung wrote:
> > > At some point, is it worth having a doAddressOptRMW() ?
> > 
> > Yikes!  I didn't mean to disable address mode optimization for RMW.
> > 
> > I moved findRMW() to be after address mode optimization, using a deeper test
> of
> > whether the Load and Dest addresses are the same.
> 
> 
> Could add a test case to the .ll that shows address mode optimization still
> succeeds from the new pass ordering?

Another good catch!  I forgot that the address mode optimization deletes the
original load/store instruction and inserts a new one, so the deleted
instructions need to be skipped over.

Added a new test.

https://codereview.chromium.org/1182603004/diff/40001/src/IceInstX8632.h
File src/IceInstX8632.h (right):

https://codereview.chromium.org/1182603004/diff/40001/src/IceInstX8632.h#newc...
src/IceInstX8632.h:317: // InstX8632FakeRMW represents a non-atomic
read-modify-write
On 2015/06/17 16:40:22, jvoung wrote:
> In this case the "Fake" seems a bit different from FakeDef/FakeUse. It seems
to
> represent more of a high level instruction that hasn't been lowered yet (like
> AddRMW is). Might be worth pointing out that there's still some lowering?

Done.

https://codereview.chromium.org/1182603004/diff/40001/src/IceInstX8632.h#newc...
src/IceInstX8632.h:840: InstX8632BinopRMW(Cfg *Func, Operand *DestSrc0, Operand
*Src1)
On 2015/06/17 16:40:22, jvoung wrote:
> OperandX8632Mem *DestSrc0 too?

Done.

[Jim Stichnoth, 2015-06-18 05:16:07]

Committed patchset #4 (id:60001) manually as
e4f65d86d863cc8ec0851846b5716280443cd882 (presubmit successful).