Array index computation dehoisting.

Array index computation dehoisting.

When an array index (in an array access) is a simple "expression + constant", just embed the constant in the array access operation so that the full index expression is (potentially) no longer used and its live range can be much shorter.
This is effective in conjunction with array bounds check removal (otherwise the index is anyway used in the check).

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

[Massi, 2012-05-08 12:40:40]

This should be reviewable: all tests pass and also more complex code executes
correctly.

[Jakob Kummerow, 2012-05-08 13:46:26]

Looks good overall. I have some suggestions for simplification.

https://chromiumcodereview.appspot.com/10382055/diff/1/src/flag-definitions.h
File src/flag-definitions.h (right):

https://chromiumcodereview.appspot.com/10382055/diff/1/src/flag-definitions.h...
src/flag-definitions.h:200: DEFINE_bool(array_index_dehoisting, true,
Is there a reason to keep the flag around?

https://chromiumcodereview.appspot.com/10382055/diff/1/src/hydrogen-instructi...
File src/hydrogen-instructions.h (right):

https://chromiumcodereview.appspot.com/10382055/diff/1/src/hydrogen-instructi...
src/hydrogen-instructions.h:3992: uint32_t index_offset_;
Why is this a uint32_t? In hydrogen.cc, you're passing in an int32_t that indeed
can be negative. Please use consistently signed variable types. (Same below.)

https://chromiumcodereview.appspot.com/10382055/diff/1/src/hydrogen-instructi...
src/hydrogen-instructions.h:3998: HLoadKeyedFastDoubleElement(HValue* elements,
HValue* key) :
nit: the colon goes in the next line (see HLoadKeyedFastElement as an example)

https://chromiumcodereview.appspot.com/10382055/diff/1/src/hydrogen.cc
File src/hydrogen.cc (right):

https://chromiumcodereview.appspot.com/10382055/diff/1/src/hydrogen.cc#newcod...
src/hydrogen.cc:3122: // FIXME(mmassi): decide meaningful bound
fix this before landing? :-)

https://chromiumcodereview.appspot.com/10382055/diff/1/src/hydrogen.cc#newcod...
src/hydrogen.cc:3127: counters->array_indexes_removed()->Increment();
Is it useful to keep those counters, or have they served their purpose?

https://chromiumcodereview.appspot.com/10382055/diff/1/src/hydrogen.cc#newcod...
src/hydrogen.cc:3143: if (instr->IsLoadKeyedFastElement()) {
This is a lot of duplicate code...

Suggestion: 
class ArrayInstructionInterface {
 public:
  virtual HInstruction* key() = 0;
  virtual int32_t key_position { return 1; }
  virtual void SetIndexOffset(int32_t index_offset) = 0;
}
Then you can let H{Load,Store}Keyed{Fast,FastDouble,SpecializedArray}Element
inherit that and make DehoistArrayIndex() a whole lot easier (or even inline it
into its single remaining call site).
The downside would be that those three virtual methods can no longer be inlined,
but I think they're not that performance critical.

https://chromiumcodereview.appspot.com/10382055/diff/1/src/ia32/lithium-codeg...
File src/ia32/lithium-codegen-ia32.cc (right):

https://chromiumcodereview.appspot.com/10382055/diff/1/src/ia32/lithium-codeg...
src/ia32/lithium-codegen-ia32.cc:2433: instr->additional_index()));
You can use "instr->hydrogen()->index_offset()" here. (Same below.)

https://chromiumcodereview.appspot.com/10382055/diff/1/src/ia32/lithium-codeg...
src/ia32/lithium-codegen-ia32.cc:2458: instr->elements(),
Leaving these on one line is fine, actually. But if you prefer, you can split
them.

https://chromiumcodereview.appspot.com/10382055/diff/1/src/ia32/lithium-codeg...
src/ia32/lithium-codegen-ia32.cc:2472: uint32_t additional_index) {
int32_t

https://chromiumcodereview.appspot.com/10382055/diff/1/src/ia32/lithium-codeg...
src/ia32/lithium-codegen-ia32.cc:3485: - kHeapObjectTag,
Nit: this is ugly, please move all parameters to the next line, indented by 4
spaces.

https://chromiumcodereview.appspot.com/10382055/diff/1/src/ia32/lithium-codeg...
File src/ia32/lithium-codegen-ia32.h (right):

https://chromiumcodereview.appspot.com/10382055/diff/1/src/ia32/lithium-codeg...
src/ia32/lithium-codegen-ia32.h:246: uint32_t additional_index = 0);
int32_t please.

https://chromiumcodereview.appspot.com/10382055/diff/1/src/ia32/lithium-ia32.cc
File src/ia32/lithium-ia32.cc (right):

https://chromiumcodereview.appspot.com/10382055/diff/1/src/ia32/lithium-ia32....
src/ia32/lithium-ia32.cc:1964: instr->index_offset());
Again, I think you don't need any of the changes to this file.

https://chromiumcodereview.appspot.com/10382055/diff/1/src/ia32/lithium-ia32.h
File src/ia32/lithium-ia32.h (right):

https://chromiumcodereview.appspot.com/10382055/diff/1/src/ia32/lithium-ia32....
src/ia32/lithium-ia32.h:1250: uint32_t additional_index_;
You don't need to pass this value to the LInstruction. Just use the hydrogen()
accessor to fetch it from the associated HInstruction.
I think that obsoletes all of the changes to this file.

[fschneider, 2012-05-09 10:32:27]

dbc:

https://chromiumcodereview.appspot.com/10382055/diff/1/src/ia32/lithium-codeg...
File src/ia32/lithium-codegen-ia32.cc (right):

https://chromiumcodereview.appspot.com/10382055/diff/1/src/ia32/lithium-codeg...
src/ia32/lithium-codegen-ia32.cc:2481: (constant_value + additional_index) * (1
<< shift_size)
You could just rewrite

expr * (1 << shift_size) into

expr << shift_size

[Massi, 2012-05-14 13:48:52]

Addressed all comments and fixed a *nasty* bug on x64.

https://chromiumcodereview.appspot.com/10382055/diff/1/src/flag-definitions.h
File src/flag-definitions.h (right):

https://chromiumcodereview.appspot.com/10382055/diff/1/src/flag-definitions.h...
src/flag-definitions.h:200: DEFINE_bool(array_index_dehoisting, true,
On 2012/05/08 13:46:26, Jakob wrote:
> Is there a reason to keep the flag around?

I am removing the counters but temporarily keeping the flags.

https://chromiumcodereview.appspot.com/10382055/diff/1/src/hydrogen-instructi...
File src/hydrogen-instructions.h (right):

https://chromiumcodereview.appspot.com/10382055/diff/1/src/hydrogen-instructi...
src/hydrogen-instructions.h:3992: uint32_t index_offset_;
On 2012/05/08 13:46:26, Jakob wrote:
> Why is this a uint32_t? In hydrogen.cc, you're passing in an int32_t that
indeed
> can be negative.

This is unsigned because on ia32 and x64 we can only put positive displacements
in the machine code (I mean, embedded in the array element access instruction).
Making this signed would generate more inconsistencies (or checks) in Lithium.

That said, you are right, I can use an unsigned type in the signature of
DehoistArrayIndex (when I extract the value from the HConstant) and with deal
signed values only inside that function, and this will make the code cleaner.

https://chromiumcodereview.appspot.com/10382055/diff/1/src/hydrogen-instructi...
src/hydrogen-instructions.h:3998: HLoadKeyedFastDoubleElement(HValue* elements,
HValue* key) :
On 2012/05/08 13:46:26, Jakob wrote:
> nit: the colon goes in the next line (see HLoadKeyedFastElement as an example)

Done.

https://chromiumcodereview.appspot.com/10382055/diff/1/src/hydrogen.cc
File src/hydrogen.cc (right):

https://chromiumcodereview.appspot.com/10382055/diff/1/src/hydrogen.cc#newcod...
src/hydrogen.cc:3122: // FIXME(mmassi): decide meaningful bound
On 2012/05/08 13:46:26, Jakob wrote:
> fix this before landing? :-)

Done.

https://chromiumcodereview.appspot.com/10382055/diff/1/src/hydrogen.cc#newcod...
src/hydrogen.cc:3127: counters->array_indexes_removed()->Increment();
On 2012/05/08 13:46:26, Jakob wrote:
> Is it useful to keep those counters, or have they served their purpose?

Done.

https://chromiumcodereview.appspot.com/10382055/diff/1/src/hydrogen.cc#newcod...
src/hydrogen.cc:3143: if (instr->IsLoadKeyedFastElement()) {
On 2012/05/08 13:46:26, Jakob wrote:
> class ArrayInstructionInterface {
>  [...]

Oddly enough, this was my original idea but Sven decided against it, likely on
the base that we would still need the switch to detect those 6 instructions.

But I still like the "interface" approach more so I will happily implement it.

https://chromiumcodereview.appspot.com/10382055/diff/1/src/ia32/lithium-codeg...
File src/ia32/lithium-codegen-ia32.cc (right):

https://chromiumcodereview.appspot.com/10382055/diff/1/src/ia32/lithium-codeg...
src/ia32/lithium-codegen-ia32.cc:2433: instr->additional_index()));
On 2012/05/08 13:46:26, Jakob wrote:
> You can use "instr->hydrogen()->index_offset()" here. (Same below.)

Done.

https://chromiumcodereview.appspot.com/10382055/diff/1/src/ia32/lithium-codeg...
src/ia32/lithium-codegen-ia32.cc:2458: instr->elements(),
On 2012/05/08 13:46:26, Jakob wrote:
> Leaving these on one line is fine, actually. But if you prefer, you can split
> them.

Done.

https://chromiumcodereview.appspot.com/10382055/diff/1/src/ia32/lithium-codeg...
src/ia32/lithium-codegen-ia32.cc:2472: uint32_t additional_index) {
On 2012/05/08 13:46:26, Jakob wrote:
> int32_t

See above.

https://chromiumcodereview.appspot.com/10382055/diff/1/src/ia32/lithium-codeg...
src/ia32/lithium-codegen-ia32.cc:2481: (constant_value + additional_index) * (1
<< shift_size)
On 2012/05/09 10:32:27, fschneider wrote:
> You could just rewrite
> 
> expr * (1 << shift_size) into
> 
> expr << shift_size

Done (on all archs).

https://chromiumcodereview.appspot.com/10382055/diff/1/src/ia32/lithium-codeg...
src/ia32/lithium-codegen-ia32.cc:3485: - kHeapObjectTag,
On 2012/05/08 13:46:26, Jakob wrote:
> Nit: this is ugly, please move all parameters to the next line, indented by 4
> spaces.

Done.

https://chromiumcodereview.appspot.com/10382055/diff/1/src/ia32/lithium-codeg...
File src/ia32/lithium-codegen-ia32.h (right):

https://chromiumcodereview.appspot.com/10382055/diff/1/src/ia32/lithium-codeg...
src/ia32/lithium-codegen-ia32.h:246: uint32_t additional_index = 0);
On 2012/05/08 13:46:26, Jakob wrote:
> int32_t please.

uint32_t everywhere :-)

https://chromiumcodereview.appspot.com/10382055/diff/1/src/ia32/lithium-ia32.cc
File src/ia32/lithium-ia32.cc (right):

https://chromiumcodereview.appspot.com/10382055/diff/1/src/ia32/lithium-ia32....
src/ia32/lithium-ia32.cc:1964: instr->index_offset());
On 2012/05/08 13:46:26, Jakob wrote:
> Again, I think you don't need any of the changes to this file.

Well, I decided to add an accessor just for convenience (like in the other
Lithium files)...

https://chromiumcodereview.appspot.com/10382055/diff/1/src/ia32/lithium-ia32.h
File src/ia32/lithium-ia32.h (right):

https://chromiumcodereview.appspot.com/10382055/diff/1/src/ia32/lithium-ia32....
src/ia32/lithium-ia32.h:1250: uint32_t additional_index_;
On 2012/05/08 13:46:26, Jakob wrote:
> You don't need to pass this value to the LInstruction. Just use the hydrogen()
> accessor to fetch it from the associated HInstruction.
> I think that obsoletes all of the changes to this file.

Done.

[Jakob Kummerow, 2012-05-15 15:53:23]

LGTM if comments are addressed (they're mostly nits).

Personally, I don't think the "uint32_t additional_index() const { return
hydrogen()->index_offset(); }" accessors in the LInstructions add much value,
but you can keep them if you wish.

https://chromiumcodereview.appspot.com/10382055/diff/4019/src/arm/lithium-arm.cc
File src/arm/lithium-arm.cc (right):

https://chromiumcodereview.appspot.com/10382055/diff/4019/src/arm/lithium-arm...
src/arm/lithium-arm.cc:1959: LLoadKeyedFastElement* result =
nit: why this change?

https://chromiumcodereview.appspot.com/10382055/diff/4019/src/arm/lithium-arm...
src/arm/lithium-arm.cc:2039: return new(zone())
LStoreKeyedFastDoubleElement(elements,
nit: why this change?

https://chromiumcodereview.appspot.com/10382055/diff/4019/src/arm/lithium-cod...
File src/arm/lithium-codegen-arm.cc (right):

https://chromiumcodereview.appspot.com/10382055/diff/4019/src/arm/lithium-cod...
src/arm/lithium-codegen-arm.cc:2751: __ ldr(result,
Formatting proposal:

  uint32_t offset = FixedArray::kHeaderSize +
                    (instr->additional_index() << kPointerSizeLog2);
  __ ldr(result, FieldMemOperand(scratch, offset));

https://chromiumcodereview.appspot.com/10382055/diff/4019/src/arm/lithium-cod...
src/arm/lithium-codegen-arm.cc:2794: + (instr->additional_index() <<
shift_size)));
nit: for consistency, the operator goes at the end of the last line.

https://chromiumcodereview.appspot.com/10382055/diff/4019/src/arm/lithium-cod...
src/arm/lithium-codegen-arm.cc:2844: constant_key * (1 << shift_size) +
additional_offset)
nit: drop the "* (1". Just "(constant_key << shift_size)". It's cleaner.

https://chromiumcodereview.appspot.com/10382055/diff/4019/src/arm/lithium-cod...
src/arm/lithium-codegen-arm.cc:3746: * kPointerSize + FixedArray::kHeaderSize;
nit: looks like "* kPointerSize" might just fit onto the line before, which
would make more sense.

https://chromiumcodereview.appspot.com/10382055/diff/4019/src/arm/lithium-cod...
src/arm/lithium-codegen-arm.cc:3860: ? MemOperand(external_pointer, key, LSL,
shift_size)
nit: 4 space indent please.

https://chromiumcodereview.appspot.com/10382055/diff/4019/src/hydrogen-instru...
File src/hydrogen-instructions.h (right):

https://chromiumcodereview.appspot.com/10382055/diff/4019/src/hydrogen-instru...
src/hydrogen-instructions.h:3967: : hole_check_mode_(hole_check_mode),
index_offset_(0) {
how about ", is_dehoisted_(false)"?

https://chromiumcodereview.appspot.com/10382055/diff/4019/src/hydrogen-instru...
src/hydrogen-instructions.h:4001: return hole_check_mode_ ==
other_load->hole_check_mode_;
I think you need to add a comparison of index_offset_ here. (Same for the other
classes.)

https://chromiumcodereview.appspot.com/10382055/diff/4019/src/hydrogen.cc
File src/hydrogen.cc (right):

https://chromiumcodereview.appspot.com/10382055/diff/4019/src/hydrogen.cc#new...
src/hydrogen.cc:3084: Counters* counters) {
No need to pass in |counters| any more, is there?

https://chromiumcodereview.appspot.com/10382055/diff/4019/src/hydrogen.cc#new...
src/hydrogen.cc:3086: array_operation->SetDehoisted(false);
It's cleaner to do this in the instruction's c'tor (see comment there).

https://chromiumcodereview.appspot.com/10382055/diff/4019/src/ia32/lithium-ia...
File src/ia32/lithium-ia32.cc (right):

https://chromiumcodereview.appspot.com/10382055/diff/4019/src/ia32/lithium-ia...
src/ia32/lithium-ia32.cc:1961: LLoadKeyedFastElement* result =
nit: why this change?

https://chromiumcodereview.appspot.com/10382055/diff/4019/src/v8-counters.h
File src/v8-counters.h (right):

https://chromiumcodereview.appspot.com/10382055/diff/4019/src/v8-counters.h#n...
src/v8-counters.h:1: // Copyright 2011 the V8 project authors. All rights
reserved.
nit: 2012

https://chromiumcodereview.appspot.com/10382055/diff/4019/src/x64/lithium-cod...
File src/x64/lithium-codegen-x64.cc (right):

https://chromiumcodereview.appspot.com/10382055/diff/4019/src/x64/lithium-cod...
src/x64/lithium-codegen-x64.cc:2378: if (instr->hydrogen()->IsDehoisted()) {
Doesn't this need an additional "&& !instr->key()->IsConstantOperand()"? Same
question five more times below.

https://chromiumcodereview.appspot.com/10382055/diff/4019/src/x64/lithium-cod...
src/x64/lithium-codegen-x64.cc:2380: // and the dehoisted address computation
happens in 64 bits
nit: please end the sentence with a full stop.

https://chromiumcodereview.appspot.com/10382055/diff/4019/src/x64/lithium-cod...
src/x64/lithium-codegen-x64.cc:3460: - kHeapObjectTag,
nit: I'd change the indentation to:

Operand operand =
    BuildFastArrayOperand(instr->object(),
                          instr->key(),
                          FAST_ELEMENTS,
                          FixedArray::kHeaderSize - kHeapObjectTag,
                          instr->additional_index());

https://chromiumcodereview.appspot.com/10382055/diff/4019/src/x64/lithium-x64.cc
File src/x64/lithium-x64.cc (right):

https://chromiumcodereview.appspot.com/10382055/diff/4019/src/x64/lithium-x64...
src/x64/lithium-x64.cc:1966: return new(zone())
nit: why this change?

[Massi, 2012-05-18 13:01:01]

Addressed all comments (just left the accessors in the Lithium insts), should
commit on Monday after rebasing.