[turbofan] Relax limitation for using BaseWithIndexAndDisplacement for load/stores

[turbofan] Relax limitation for using BaseWithIndexAndDisplacement for load/stores

Enable using BaseWithIndexAndDisplacement addressing mode for an address 
used by multiple load/stores. It can reduce one instruction to calculate 
the address and one register to store the address.

BUG=

Review-Url: https://codereview.chromium.org/2620293004
Cr-Commit-Position: refs/heads/master@{#43402}
Committed: https://chromium.googlesource.com/v8/v8/+/bd74f1cf57c951612aad501be68ec8d791825705

[shiyu.zhang, 2017-01-22 03:09:06]

Description was changed from

==========
[turbofan] Relax limitation for using BaseWithIndexAndDisplacement for
load/stores


BUG=
==========

to

==========
[turbofan] Relax limitation for using BaseWithIndexAndDisplacement for
load/stores

Enable using BaseWithIndexAndDisplacement addressing mode for an address used by
multiple load/stores. It can reduce one instruction to calculate the address and
one register to store the address.

BUG=
==========

[shiyu.zhang, 2017-01-22 03:12:25]

Description was changed from

==========
[turbofan] Relax limitation for using BaseWithIndexAndDisplacement for
load/stores

Enable using BaseWithIndexAndDisplacement addressing mode for an address used by
multiple load/stores. It can reduce one instruction to calculate the address and
one register to store the address.

BUG=
==========

to

==========
[turbofan] Relax limitation for using BaseWithIndexAndDisplacement for
load/stores

Enable using BaseWithIndexAndDisplacement addressing mode for an address 
used by multiple load/stores. It can reduce one instruction to calculate 
the address and one register to store the address.

BUG=
==========

[shiyu.zhang, 2017-01-22 03:39:16]

The address used by multiple load/stores cannot use BaseWithIndexAndDisplacement
addressing mode.
This patch relax the limitation. For example,

lea esi,[eax*8+0x7]
movsd xmm2,[esi+edi*1]
...
movsd [esi+ecx*1],xmm2

can be transformed to

movsd xmm2,[edi+eax*8+0x7]
...
movsd [ecx+eax*8+0x7],xmm2

Thus one lea instruction and one esi register usage can be reduced.

[shiyu.zhang, 2017-01-22 03:39:16]

The address used by multiple load/stores cannot use BaseWithIndexAndDisplacement
addressing mode.
This patch relax the limitation. For example,

lea esi,[eax*8+0x7]
movsd xmm2,[esi+edi*1]
...
movsd [esi+ecx*1],xmm2

can be transformed to

movsd xmm2,[edi+eax*8+0x7]
...
movsd [ecx+eax*8+0x7],xmm2

Thus one lea instruction and one esi register usage can be reduced.

[shiyu.zhang, 2017-02-07 06:26:44]

Rebase the patch and the following improvements can be observed on Atom with the
patch:

	ia32	x64
octane2-NavierStokes	5.80%	3.30%
jetstream-navier-stokes	5.90%	3.80%
kraken-fft	3.60%	4.80%
kraken-desaturate	11%	8%

[Pan, 2017-02-07 09:07:49]

The CQ bit was checked by pan.deng@intel.com

[Pan, 2017-02-07 09:07:51]

The CQ bit was unchecked by pan.deng@intel.com

[danno, 2017-02-08 10:14:00]

danno@chromium.org changed reviewers:
+ danno@chromium.org

[danno, 2017-02-08 10:14:01]

Hi Shiyu,

Thanks for the patch. Could you elaborate a little bit on the tradeoffs of
re-using the addressing mode? Specifically, are combed complex memory operand
addressing modes _always_ no more expensive than simple memory accesses? Or only
in some situations? Is this also true on all Intel cores?

For example, the code generated by the Call0 bytecode here:

https://codereview.chromium.org/2673833003/

Uses multiple complex memory addressing mode to access byte code operands, and
we are considering pre-computing base addresses to simplify the memory accesses
to improve performance. Will that not help no Intel platform? It certainly will
for ARM and other RISC architectures. 

Thanks,
Danno

[shiyu.zhang, 2017-02-21 09:54:31]

On 2017/02/08 10:14:01, danno wrote:
> Hi Shiyu,
> 
> Thanks for the patch. Could you elaborate a little bit on the tradeoffs of
> re-using the addressing mode? Specifically, are combed complex memory operand
> addressing modes _always_ no more expensive than simple memory accesses? Or
only
> in some situations? Is this also true on all Intel cores?
> 
> For example, the code generated by the Call0 bytecode here:
> 
> https://codereview.chromium.org/2673833003/
> 
> Uses multiple complex memory addressing mode to access byte code operands, and
> we are considering pre-computing base addresses to simplify the memory
accesses
> to improve performance. Will that not help no Intel platform? It certainly
will
> for ARM and other RISC architectures. 
> 
> Thanks,
> Danno

Hi Danno,

Thanks for your comments. Of course combed complex addressing (Base + index [+
Offset]) memory accesses are more expensive than simple addressing (Base +
Offset < 2048) memory accesses for Intel cores after Sandy Bridge.  You can find
latency details in Table 2-19 in
http://www.intel.com/content/dam/www/public/us/en/documents/manuals/64-ia-32-...

I think this patch (after patch set 5) will not change combed complex addressing
to simple addressing. Meanwhile it will change addressing from one complex mode
[esi+edi*1] to another complex mode [edi+eax*8+0x7] as in the example I listed
above. And both two complex addressing modes have the same latency according to
the manual. So this patch should introduce no regression.

As for the Call0 bytecode you mentioned, I found the following multiple complex
memory addressing in the generated code:
  movsxlq rbx, [r14+r12*1+0x1]
  movl rdx, [r14+r12*1+0x9]
  movsxlq rcx, [r14+r12*1+0x5]

I think it should improve performance on Intel platform by pre-computing base
addresses to simplify the memory accesses, just like:
  lea r10, [r14+r12*1]
  movsxlq rbx, [r10+0x1]
  movl rdx, [r10+0x9]
  movsxlq rcx, [r10+0x5]

However, when measuring latency of memory references, many factors can influence
the observed latency exposure such as access patterns, cache locality, effect of
the hardware prefetchers ... It’s hard to tell which addressing mode is
absolutely good. I think we should rely on the benchmarks performance for better
tradeoff.

Thanks,
Shiyu

[danno, 2017-02-21 16:11:01]

Thanks for the analysis and the information about addressing modes, Shiyu. The
latest version looks better, but could you please add tests for the cases you
have changed (there are extensive tests for the
BaseWithIndexAndDisplacementXXXMatchers in node-matchers-unittest.cc)?

https://codereview.chromium.org/2620293004/diff/80001/src/compiler/node.cc
File src/compiler/node.cc (right):

https://codereview.chromium.org/2620293004/diff/80001/src/compiler/node.cc#ne...
src/compiler/node.cc:303: from->opcode() != IrOpcode::kStore &&
Careful here, don't you have to make sure that the input is the store address
and not the store value? If it's the latter, then it is not owned by just by
addressing operand.

[danno, 2017-02-22 14:48:42]

danno@chromium.org changed reviewers:
+ leszeks@chromium.org, rmcilroy@chromium.org

[shiyu.zhang, 2017-02-23 01:20:48]

Thanks for the advice, Danno. I am working on the tests.

https://codereview.chromium.org/2620293004/diff/80001/src/compiler/node.cc
File src/compiler/node.cc (right):

https://codereview.chromium.org/2620293004/diff/80001/src/compiler/node.cc#ne...
src/compiler/node.cc:303: from->opcode() != IrOpcode::kStore &&
On 2017/02/21 16:11:01, danno wrote:
> Careful here, don't you have to make sure that the input is the store address
> and not the store value? If it's the latter, then it is not owned by just by
> addressing operand.

OwnedByAddressingOperand is only used by left operand ( InputAt(0) ) and right
operand ( InputAt(1) ) . For store node, InputAt(0) and InputAt(1) are base and
index, InputAt(2) is value. So there is no need to check here, right?

[danno, 2017-02-23 08:49:34]

Thanks for the update, Shiyu. I'm looking forward to the updated patch.

https://codereview.chromium.org/2620293004/diff/80001/src/compiler/node.cc
File src/compiler/node.cc (right):

https://codereview.chromium.org/2620293004/diff/80001/src/compiler/node.cc#ne...
src/compiler/node.cc:303: from->opcode() != IrOpcode::kStore &&
On 2017/02/23 01:20:48, shiyu.zhang wrote:
> On 2017/02/21 16:11:01, danno wrote:
> > Careful here, don't you have to make sure that the input is the store
address
> > and not the store value? If it's the latter, then it is not owned by just by
> > addressing operand.
> 
> OwnedByAddressingOperand is only used by left operand ( InputAt(0) ) and right
> operand ( InputAt(1) ) . For store node, InputAt(0) and InputAt(1) are base
and
> index, InputAt(2) is value. So there is no need to check here, right?

Well, this builds in a pretty explicit and fragile assumption that
OwnedByAddressingOperand is only used by the scaled matcher. I would prefer if
it were possible to make it more robust, including with unit tests of the
function that ensure it only returns true in the cases that it's supposed to,
regardless of how careful the caller is.

[shiyu.zhang, 2017-02-23 11:22:56]

Hi Danno, tests are added.

And you are right. Use as store’s value should not be counted as
OwnedByAddressingOperand. Thanks for your reminder! Appreciate your further
comments.

[danno, 2017-02-23 20:53:33]

lgtm! Thanks for the patch.

[shiyu.zhang, 2017-02-24 00:14:20]

The CQ bit was checked by shiyu.zhang@intel.com

[commit-bot: I haz the power, 2017-02-24 00:14:28]

CQ is trying da patch. Follow status at
 
https://chromium-cq-status.appspot.com/v2/patch-status/codereview.chromium.or...

[commit-bot: I haz the power, 2017-02-24 00:33:44]

The CQ bit was unchecked by commit-bot@chromium.org

[commit-bot: I haz the power, 2017-02-24 00:33:45]

Try jobs failed on following builders:
  v8_linux_dbg_ng on master.tryserver.v8 (JOB_FAILED,
http://build.chromium.org/p/tryserver.v8/builders/v8_linux_dbg_ng/builds/21560)
  v8_linux_dbg_ng_triggered on master.tryserver.v8 (JOB_FAILED,
http://build.chromium.org/p/tryserver.v8/builders/v8_linux_dbg_ng_triggered/b...)

[shiyu.zhang, 2017-02-24 06:36:28]

The CQ bit was checked by shiyu.zhang@intel.com

[shiyu.zhang, 2017-02-24 06:36:28]

The patchset sent to the CQ was uploaded after l-g-t-m from danno@chromium.org
Link to the patchset: https://codereview.chromium.org/2620293004/#ps120001
(title: "Fix some test bugs")

[commit-bot: I haz the power, 2017-02-24 06:36:38]

CQ is trying da patch. Follow status at
 
https://chromium-cq-status.appspot.com/v2/patch-status/codereview.chromium.or...

[commit-bot: I haz the power, 2017-02-24 06:38:14]

CQ is committing da patch.

Bot data: {"patchset_id": 120001, "attempt_start_ts": 1487918188279580,
"parent_rev": "27fb7b8348aa125ad225b2c3949b0605c184729c", "commit_rev":
"bd74f1cf57c951612aad501be68ec8d791825705"}

[commit-bot: I haz the power, 2017-02-24 06:38:21]

Description was changed from

==========
[turbofan] Relax limitation for using BaseWithIndexAndDisplacement for
load/stores

Enable using BaseWithIndexAndDisplacement addressing mode for an address 
used by multiple load/stores. It can reduce one instruction to calculate 
the address and one register to store the address.

BUG=
==========

to

==========
[turbofan] Relax limitation for using BaseWithIndexAndDisplacement for
load/stores

Enable using BaseWithIndexAndDisplacement addressing mode for an address 
used by multiple load/stores. It can reduce one instruction to calculate 
the address and one register to store the address.

BUG=

Review-Url: https://codereview.chromium.org/2620293004
Cr-Commit-Position: refs/heads/master@{#43402}
Committed:
https://chromium.googlesource.com/v8/v8/+/bd74f1cf57c951612aad501be68ec8d7918...
==========

[commit-bot: I haz the power, 2017-02-24 06:38:22]

Committed patchset #7 (id:120001) as
https://chromium.googlesource.com/v8/v8/+/bd74f1cf57c951612aad501be68ec8d7918...