[turbofan] Optimize add operations to use 'leal' instruction on x64

[turbofan] Optimize add operations to use 'leal' instruction on x64

Add MemoryOperandMatcher that recognizes node clusters in the form
[%r1 + %r2*SCALE + OFFSET] and explicit support in the x64 Int32Add
selector to use it to translate complex adds to 'leal' instructions.

R=titzer@chromium.org

Committed: https://code.google.com/p/v8/source/detail?r=25223

[danno, 2014-11-05 12:32:48]

danno@chromium.org changed reviewers:
+ bmeurer@chromium.org, titzer@chromium.org

[danno, 2014-11-05 12:32:48]

PTAL. It's about +3.5% on Octane zlib

[titzer, 2014-11-05 13:16:09]

https://codereview.chromium.org/704713003/diff/120001/src/compiler/x64/instru...
File src/compiler/x64/instruction-selector-x64.cc (right):

https://codereview.chromium.org/704713003/diff/120001/src/compiler/x64/instru...
src/compiler/x64/instruction-selector-x64.cc:370: : public ValueMatcher<int32_t,
IrOpcode::kInt32Add> {
What do you inherit from ValueMatcher here?

https://codereview.chromium.org/704713003/diff/120001/src/compiler/x64/instru...
src/compiler/x64/instruction-selector-x64.cc:378: MatchMemoryOperand(selector);
This method is only used in the constructor and I think inlining it would be
more readable.

https://codereview.chromium.org/704713003/diff/120001/src/compiler/x64/instru...
src/compiler/x64/instruction-selector-x64.cc:393: if (scale_factor_ == 1) {
This pattern with switching on the scale factor could be shortened with a
subroutine like:

pickAddressingModeFromScale(scale_factor, AddressingMode[4] modes)

https://codereview.chromium.org/704713003/diff/120001/src/compiler/x64/instru...
src/compiler/x64/instruction-selector-x64.cc:456: static bool
TryCombine(InstructionSelector* selector, Node* use, Node* node,
This is tough to follow, partly because of the pointers to pointers. E.g. see
questions below.

https://codereview.chromium.org/704713003/diff/120001/src/compiler/x64/instru...
src/compiler/x64/instruction-selector-x64.cc:461: *constant = node;
Why would the constant already be non-null and why would it be ok to fall
through and return true?

https://codereview.chromium.org/704713003/diff/120001/src/compiler/x64/instru...
src/compiler/x64/instruction-selector-x64.cc:468: if (leftm.IsPowerOf2() &&
leftm.Value() <= 8) {
This can't happen because Int32BinopMatcher puts constants on the right
automatically for commutative operators, which Int32Mul should be.

https://codereview.chromium.org/704713003/diff/120001/src/compiler/x64/instru...
src/compiler/x64/instruction-selector-x64.cc:494: return false;
So we can return false if scaled and unscaled are set to non-null? What are they
supposed to be prior to the call to this method?

https://codereview.chromium.org/704713003/diff/120001/src/compiler/x64/instru...
src/compiler/x64/instruction-selector-x64.cc:546: selector->CanCover(node,
right)) {
What happens if we handled left already here?

https://codereview.chromium.org/704713003/diff/120001/src/compiler/x64/instru...
src/compiler/x64/instruction-selector-x64.cc:613: if (TryLeaInt32Add(this,
node)) return;
I think this would be more readable if it was inline too, since then you don't
need to pass around the InstructionSelector, too.

[danno, 2014-11-06 10:53:03]

Not ready to land, but is this more like you envisioned it? I'll wait for your
feedback before writing matcher tests, etc.

[titzer, 2014-11-06 11:47:06]

Yeah I like the stateless matcher much better.

https://codereview.chromium.org/704713003/diff/160001/src/compiler/node-match...
File src/compiler/node-matchers.h (right):

https://codereview.chromium.org/704713003/diff/160001/src/compiler/node-match...
src/compiler/node-matchers.h:184: bool IsScaledInput(Node* node) const {
You could also have this method return the scaled power of 2, with -1
representing no match.

https://codereview.chromium.org/704713003/diff/160001/src/compiler/node-match...
src/compiler/node-matchers.h:320: bool Matches() const { return matches_; }
Lower case for simple getters.

https://codereview.chromium.org/704713003/diff/160001/src/compiler/x64/instru...
File src/compiler/x64/instruction-selector-x64.cc (right):

https://codereview.chromium.org/704713003/diff/160001/src/compiler/x64/instru...
src/compiler/x64/instruction-selector-x64.cc:369: static AddressingMode
ScaleFactorToAddressingMode(
If you use the scale power of 2, then you can just do a linear index into this
array, then you can maybe even inline this method.

[danno, 2014-11-06 23:34:07]

PTAL, now with feedback addressed and lots of tests

https://codereview.chromium.org/704713003/diff/160001/src/compiler/node-match...
File src/compiler/node-matchers.h (right):

https://codereview.chromium.org/704713003/diff/160001/src/compiler/node-match...
src/compiler/node-matchers.h:184: bool IsScaledInput(Node* node) const {
On 2014/11/06 11:47:06, titzer wrote:
> You could also have this method return the scaled power of 2, with -1
> representing no match.

Done.

https://codereview.chromium.org/704713003/diff/160001/src/compiler/node-match...
src/compiler/node-matchers.h:320: bool Matches() const { return matches_; }
On 2014/11/06 11:47:06, titzer wrote:
> Lower case for simple getters.

Done.

https://codereview.chromium.org/704713003/diff/160001/src/compiler/x64/instru...
File src/compiler/x64/instruction-selector-x64.cc (right):

https://codereview.chromium.org/704713003/diff/160001/src/compiler/x64/instru...
src/compiler/x64/instruction-selector-x64.cc:369: static AddressingMode
ScaleFactorToAddressingMode(
On 2014/11/06 11:47:06, titzer wrote:
> If you use the scale power of 2, then you can just do a linear index into this
> array, then you can maybe even inline this method.

Done.

[dcarney, 2014-11-07 09:11:43]

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

[dcarney, 2014-11-07 09:11:43]

https://codereview.chromium.org/704713003/diff/220001/src/compiler/x64/instru...
File src/compiler/x64/instruction-selector-x64.cc (right):

https://codereview.chromium.org/704713003/diff/220001/src/compiler/x64/instru...
src/compiler/x64/instruction-selector-x64.cc:382: static const AddressingMode
kMRnI_modes[] = {kMode_MR1I, kMode_MR2I,
for all these you can just use

AdjustAddressingMode(kMode_MR1I, scale)

like in instruction-selector-ia32

[titzer, 2014-11-07 16:17:38]

lgtm

https://codereview.chromium.org/704713003/diff/220001/src/compiler/x64/instru...
File src/compiler/x64/instruction-selector-x64.cc (right):

https://codereview.chromium.org/704713003/diff/220001/src/compiler/x64/instru...
src/compiler/x64/instruction-selector-x64.cc:370: int scale_factor, Node*
offset,
Let's call it scale_exponent to avoid confusion.

[danno, 2014-11-07 16:43:32]

Feedback addressed, landing

https://codereview.chromium.org/704713003/diff/220001/src/compiler/x64/instru...
File src/compiler/x64/instruction-selector-x64.cc (right):

https://codereview.chromium.org/704713003/diff/220001/src/compiler/x64/instru...
src/compiler/x64/instruction-selector-x64.cc:370: int scale_factor, Node*
offset,
On 2014/11/07 16:17:38, titzer wrote:
> Let's call it scale_exponent to avoid confusion.

Done.

https://codereview.chromium.org/704713003/diff/220001/src/compiler/x64/instru...
src/compiler/x64/instruction-selector-x64.cc:382: static const AddressingMode
kMRnI_modes[] = {kMode_MR1I, kMode_MR2I,
On 2014/11/07 09:11:43, dcarney wrote:
> for all these you can just use
> 
> AdjustAddressingMode(kMode_MR1I, scale)
> 
> like in instruction-selector-ia32

That would mean copying the code here, and the implicit Mode -> int conversion
seems a bit dangerous, I actually prefer the explicit list.

[danno, 2014-11-07 16:47:35]

Committed patchset #13 (id:240001) manually as 25223 (presubmit successful).

[danno, 2014-11-14 13:51:47]

Patchset #14 (id:260001) has been deleted