Replace a set of Hydrogen instructions with rotate instructions on ARM

Replace a set of Hydrogen instructions with rotate instructions on ARM
BUG=none
TEST=none

[Erik Corry, 2012-09-27 14:45:44]

http://codereview.chromium.org/10984057/diff/1/src/arm/simulator-arm.cc
File src/arm/simulator-arm.cc (right):

http://codereview.chromium.org/10984057/diff/1/src/arm/simulator-arm.cc#newco...
src/arm/simulator-arm.cc:1504: int32_t left = result >> shift_amount;
How does this work with a negative input?

http://codereview.chromium.org/10984057/diff/1/src/hydrogen-instructions.cc
File src/hydrogen-instructions.cc (right):

http://codereview.chromium.org/10984057/diff/1/src/hydrogen-instructions.cc#n...
src/hydrogen-instructions.cc:1624: : new(zone) Range();
Don't you have to Ror the result here?

http://codereview.chromium.org/10984057/diff/1/src/hydrogen-instructions.h
File src/hydrogen-instructions.h (right):

http://codereview.chromium.org/10984057/diff/1/src/hydrogen-instructions.h#ne...
src/hydrogen-instructions.h:3638:
ChangeRepresentation(Representation::Integer32());
Why is HRor different from all other bit ops here?

http://codereview.chromium.org/10984057/diff/1/src/hydrogen.cc
File src/hydrogen.cc (right):

http://codereview.chromium.org/10984057/diff/1/src/hydrogen.cc#newcode1043
src/hydrogen.cc:1043: !shl->representation().IsInteger32())
Missing {}

http://codereview.chromium.org/10984057/diff/1/src/hydrogen.cc#newcode1052
src/hydrogen.cc:1052: if (!shr->right()->IsSub()) return false;
This function needs a comment explaining what it is looking for, and the line
above here needs an explanation of why only a sub function is OK here.

http://codereview.chromium.org/10984057/diff/1/src/hydrogen.cc#newcode1062
src/hydrogen.cc:1062: if (sub->right()->OperandAt(0) !=
shl->right()->OperandAt(0))
Missing {}

http://codereview.chromium.org/10984057/diff/1/src/hydrogen.cc#newcode1083
src/hydrogen.cc:1083: bool HGraph::TryRotateRight(HInstruction* instr) {
There is a lot of copied code here - can they be combined into one function with
a flag?

http://codereview.chromium.org/10984057/diff/1/src/token.h
File src/token.h (right):

http://codereview.chromium.org/10984057/diff/1/src/token.h#newcode102
src/token.h:102: T(ROR, "rotate right", 11)                                     
      \
This needs a comment to explain that it is only used in Crankshaft.

[ulan, 2012-09-27 14:55:30]

http://codereview.chromium.org/10984057/diff/1/src/arm/simulator-arm.cc
File src/arm/simulator-arm.cc (right):

http://codereview.chromium.org/10984057/diff/1/src/arm/simulator-arm.cc#newco...
src/arm/simulator-arm.cc:1507: *carry_out = false;
The carry_out should contain the last shifted bit according to the spec.

http://codereview.chromium.org/10984057/diff/1/src/arm/simulator-arm.cc#newco...
src/arm/simulator-arm.cc:1511: 
We can remove this empty line.

http://codereview.chromium.org/10984057/diff/1/src/hydrogen.cc
File src/hydrogen.cc (right):

http://codereview.chromium.org/10984057/diff/1/src/hydrogen.cc#newcode1041
src/hydrogen.cc:1041: if (shl->UseCount()>1 || shr->UseCount()>1) return false;
Please add space before and after each ">" operator.

http://codereview.chromium.org/10984057/diff/1/src/hydrogen.cc#newcode1089
src/hydrogen.cc:1089: if (bor->left()->IsShl() && bor->right()->IsShr()) {
Please add space before and after each ">" operator.

[ulan, 2012-09-27 15:30:09]

http://codereview.chromium.org/10984057/diff/1/src/hydrogen.cc
File src/hydrogen.cc (right):

http://codereview.chromium.org/10984057/diff/1/src/hydrogen.cc#newcode3539
src/hydrogen.cc:3539: #if defined(V8_TARGET_ARCH_ARM)
I am concerned with this ifdef. Hydrogen should contain platform independent
code and these kind of optimizations should be done on the Lithium level.

[Michael Starzinger, 2012-09-27 23:53:27]

Some general high-level observations about this change:

1) This is a very specialized optimization targeting one specific instruction
(i.e. rotation). I think a more general approach that performs general pattern
matching might scale better and cover other peephole optimizations as well (e.g.
scaled array access, algebraic simplification or other strength reductions)

2) Is this a common pattern in JavaScript applications or is this tracked by any
benchmark? I would be interested to know what particular use case this
optimization targets.

3) Adding a token for something that has no equivalent in JavaScript seems
wrong. We only do this in rare cases where we need to push information about
variable initialization through the AST, but not for Crankshaft optimizations.

4) This change definitely needs better test coverage.

[Jay Conrod, 2012-09-29 22:17:45]

On 2012/09/27 23:53:27, Michael Starzinger wrote:
> Some general high-level observations about this change:
> 
> 1) This is a very specialized optimization targeting one specific instruction
> (i.e. rotation). I think a more general approach that performs general pattern
> matching might scale better and cover other peephole optimizations as well
(e.g.
> scaled array access, algebraic simplification or other strength reductions)

In this case, we focused on getting StringSHA1 performance to improve quickly. I
agree that a more general approach would be best. For this kind of thing, a
tiling instruction selector would work very well, but it's hard to implement
that kind of thing with the coarse granularity of Lithium. Perhaps we can work
together on something of this nature in the future. It would definitely help ARM
platforms which are more sensitive to instructions emitted than x86.

> 2) Is this a common pattern in JavaScript applications or is this tracked by
any
> benchmark? I would be interested to know what particular use case this
> optimization targets.

Rotations are common in cryptography, and pretty much every major benchmark has
a crypto component. When we wrote this, we were targeting StringSHA1 in
BrowserMark, which has the following function:

rotateLeft: function(n, s) {
  var t4 = ( n << s ) | (n >>> (32 - s));
  return t4;
},

> 3) Adding a token for something that has no equivalent in JavaScript seems
> wrong. We only do this in rare cases where we need to push information about
> variable initialization through the AST, but not for Crankshaft optimizations.

I think it's strange that the LShift instruction uses AST tokens to determine
what operation to perform. It seems like a common pattern, so we didn't want to
change it. Maybe it would be better to have separate enums for syntax and
operations, since, as in this case, we want to represent a wider variety of
operations than the syntax allows.

> 
> 4) This change definitely needs better test coverage.

Agree.

I have refactored this change, incorporating as much as the above feedback as I
could (although I'm not making any architectural changes for now). Once the new
revision passes legal review (should be Monday), I'll upload here. Test cases
will follow soon after that.

[ulan, 2012-10-01 18:10:59]

Hi Jay,

While waiting for the new revision of this patch set, I started prototyping
implementation of ROR for ia32 and x64 architectures, so that we can get rid of
the ARM specific #ifdef in hydrogen.cc.

You can review the CL at https://chromiumcodereview.appspot.com/11033005/

Once you upload new patch set, we can combine both CLs to get something in
landable state.

I also added some tests and moved detection of the ROR pattern to the visitor of
the bitwise OR. This seems cleaner to me than adding a new hydrogen phase just
to detect one specific pattern, WDYT?

Please note that I checked the generated code but didn't check performance on
StringSHA1 yet. How can I do this?