Enable GVN for polymorphic loads by not expanding them at the HIR level.

Enable GVN for polymorphic loads by not expanding them at the HIR level.

This change adds a new IR instruction for polymorphic loads. It performs
map compares and loads in one IR instruction instead of splitting each
load into a graph of map-compares and field loads.
 
The advantage is a smaller IR and less basic blocks, plus it allows to
do GVN on polymorphic loads.
Committed: http://code.google.com/p/v8/source/detail?r=7336

[fschneider, 2011-03-22 15:15:24]

RFC: Only ia32 for now.

We should also discuss what to do for stores.

[Kevin Millikin (Chromium), 2011-03-23 08:08:53]

I like the approach.  Comments below.

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

http://codereview.chromium.org/6708085/diff/1/src/hydrogen-instructions.cc#ne...
src/hydrogen-instructions.cc:1202: return false;
This requires the order of the types to be the same.  Maybe the type oracle
implementation makes that true, but if not we should relax this requirement.

As long as kMaxLoadPolymorphism is small and this is the last check, we can try
to get away with the List::Contains check here.

http://codereview.chromium.org/6708085/diff/1/src/ia32/lithium-codegen-ia32.cc
File src/ia32/lithium-codegen-ia32.cc (right):

http://codereview.chromium.org/6708085/diff/1/src/ia32/lithium-codegen-ia32.c...
src/ia32/lithium-codegen-ia32.cc:2126: Register object,
Indentation is off here.

http://codereview.chromium.org/6708085/diff/1/src/ia32/lithium-codegen-ia32.c...
src/ia32/lithium-codegen-ia32.cc:2145: Register object =
ToRegister(instr->InputAt(0));
I don't like relying on the order of the operands. This will still compile if
the order changes, and it's hard to grep for InputAt and find sites that need to
change.

We should act as if InputAt is private and define an accessor for object().

http://codereview.chromium.org/6708085/diff/1/src/ia32/lithium-codegen-ia32.c...
src/ia32/lithium-codegen-ia32.cc:2148: int num_maps =
instr->hydrogen()->types()->length();
map_count is only one character longer and avoids the abbreviation :)

http://codereview.chromium.org/6708085/diff/1/src/ia32/lithium-codegen-ia32.c...
src/ia32/lithium-codegen-ia32.cc:2155: __ cmp(FieldOperand(object,
HeapObject::kMapOffset), map);
We could avoid multiple loads of the map by using a temp register.

http://codereview.chromium.org/6708085/diff/1/src/ia32/lithium-codegen-ia32.c...
src/ia32/lithium-codegen-ia32.cc:2162: if (i < num_maps - 1  ||
instr->hydrogen()->need_generic()) {
If you handle all but the last map in the loop, I think the code is simpler:

int count = instr->hydrogen()->types()->length();
for (int i = 0; i < count - 1; ++i) {
  // Lookup.
  __ cmp(FieldOperand(object, HeapObject::kMapOffset), map);
  __ j(not_equal, &next);
  EmitLoadField(result, object, map, &lookup);
  __ jmp(&done);
  __ bind(&next);
}
if (count > 0) {  // This is probably always true.
  __ cmp(FieldOperand(object, HeapObject::kMapOffset),
         instr->hydrogen()->types()->last());
  if (instr->hydrogen()->needs_generic()) {
    // Call
  } else {
    // Deoptimize
  }
}
__ bind(&done)

http://codereview.chromium.org/6708085/diff/1/src/ia32/lithium-ia32.h
File src/ia32/lithium-ia32.h (right):

http://codereview.chromium.org/6708085/diff/1/src/ia32/lithium-ia32.h#newcode...
src/ia32/lithium-ia32.h:1181: inputs_[0] = object;
Should have an accessor for the operand.

[fschneider, 2011-03-23 13:57:55]

Addressed comments.

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

http://codereview.chromium.org/6708085/diff/1/src/hydrogen-instructions.cc#ne...
src/hydrogen-instructions.cc:1202: return false;
On 2011/03/23 08:08:53, Kevin Millikin wrote:
> This requires the order of the types to be the same.  Maybe the type oracle
> implementation makes that true, but if not we should relax this requirement.
> 
> As long as kMaxLoadPolymorphism is small and this is the last check, we can
try
> to get away with the List::Contains check here.

Done.

http://codereview.chromium.org/6708085/diff/1/src/ia32/lithium-codegen-ia32.cc
File src/ia32/lithium-codegen-ia32.cc (right):

http://codereview.chromium.org/6708085/diff/1/src/ia32/lithium-codegen-ia32.c...
src/ia32/lithium-codegen-ia32.cc:2126: Register object,
On 2011/03/23 08:08:53, Kevin Millikin wrote:
> Indentation is off here.

Done.

http://codereview.chromium.org/6708085/diff/1/src/ia32/lithium-codegen-ia32.c...
src/ia32/lithium-codegen-ia32.cc:2145: Register object =
ToRegister(instr->InputAt(0));
On 2011/03/23 08:08:53, Kevin Millikin wrote:
> I don't like relying on the order of the operands. This will still compile if
> the order changes, and it's hard to grep for InputAt and find sites that need
to
> change.
> 
> We should act as if InputAt is private and define an accessor for object().

Done.

http://codereview.chromium.org/6708085/diff/1/src/ia32/lithium-codegen-ia32.c...
src/ia32/lithium-codegen-ia32.cc:2148: int num_maps =
instr->hydrogen()->types()->length();
On 2011/03/23 08:08:53, Kevin Millikin wrote:
> map_count is only one character longer and avoids the abbreviation :)

Done.

http://codereview.chromium.org/6708085/diff/1/src/ia32/lithium-codegen-ia32.c...
src/ia32/lithium-codegen-ia32.cc:2155: __ cmp(FieldOperand(object,
HeapObject::kMapOffset), map);
On 2011/03/23 08:08:53, Kevin Millikin wrote:
> We could avoid multiple loads of the map by using a temp register.

I'll leave it as is in this change. Another way would be to have a HLoadMap
instructions. It would also allow reusing the map for a sequence of loads from
the same object.

http://codereview.chromium.org/6708085/diff/1/src/ia32/lithium-codegen-ia32.c...
src/ia32/lithium-codegen-ia32.cc:2162: if (i < num_maps - 1  ||
instr->hydrogen()->need_generic()) {
On 2011/03/23 08:08:53, Kevin Millikin wrote:
> If you handle all but the last map in the loop, I think the code is simpler:
> 
> int count = instr->hydrogen()->types()->length();
> for (int i = 0; i < count - 1; ++i) {
>   // Lookup.
>   __ cmp(FieldOperand(object, HeapObject::kMapOffset), map);
>   __ j(not_equal, &next);
>   EmitLoadField(result, object, map, &lookup);
>   __ jmp(&done);
>   __ bind(&next);
> }
> if (count > 0) {  // This is probably always true.
>   __ cmp(FieldOperand(object, HeapObject::kMapOffset),
>          instr->hydrogen()->types()->last());
>   if (instr->hydrogen()->needs_generic()) {
>     // Call
>   } else {
>     // Deoptimize
>   }
> }
> __ bind(&done)

Done.

http://codereview.chromium.org/6708085/diff/1/src/ia32/lithium-ia32.h
File src/ia32/lithium-ia32.h (right):

http://codereview.chromium.org/6708085/diff/1/src/ia32/lithium-ia32.h#newcode...
src/ia32/lithium-ia32.h:1181: inputs_[0] = object;
On 2011/03/23 08:08:53, Kevin Millikin wrote:
> Should have an accessor for the operand.

Done.

[Kevin Millikin (Chromium), 2011-03-23 14:17:04]

http://codereview.chromium.org/6708085/diff/1/src/ia32/lithium-codegen-ia32.cc
File src/ia32/lithium-codegen-ia32.cc (right):

http://codereview.chromium.org/6708085/diff/1/src/ia32/lithium-codegen-ia32.c...
src/ia32/lithium-codegen-ia32.cc:2155: __ cmp(FieldOperand(object,
HeapObject::kMapOffset), map);
OK, leaving it for later sounds good to me.

[fschneider, 2011-03-23 15:13:54]

Added x64 and ARM files.

[Kevin Millikin (Chromium), 2011-03-23 15:37:29]

Next round of comments.

http://codereview.chromium.org/6708085/diff/13003/src/arm/lithium-codegen-arm.cc
File src/arm/lithium-codegen-arm.cc (right):

http://codereview.chromium.org/6708085/diff/13003/src/arm/lithium-codegen-arm...
src/arm/lithium-codegen-arm.cc:2202: int map_count =
instr->hydrogen()->types()->length();
This function still feels too complicated.  Isn't it the case that map_count ==
0 implies needs_generic, because map_count is necessarily less than the number
of maps initially, which is at least two.

Then we could try something like:

if (map_count == 0) {
  ASSERT(needs_generic);
  // Call the IC.
} else {
  for (int i = 0; i < map_count - 1; ++i) ...
  __ cmp(scratch, /* last map */);
  if (needs_generic) {
    Label load;
    __ b(eq, &load);
    // Call the IC.
    __ b(&done);
    __ bind(&load);
  } else {
    DeoptimizeIf(...);
  }
  EmitLoadField(...);
  __ bind(&done);
}

http://codereview.chromium.org/6708085/diff/13003/src/arm/lithium-codegen-arm...
src/arm/lithium-codegen-arm.cc:2207: map->LookupInDescriptors(NULL,
*instr->hydrogen()->name(), &lookup);
I think you can move the call to LookupInDescriptors into EmitLoadField (and not
pass the LookupResult arguments).

http://codereview.chromium.org/6708085/diff/13003/src/arm/lithium-codegen-arm...
src/arm/lithium-codegen-arm.cc:2216: Handle<Map> map =
instr->hydrogen()->types()->at(map_count - 1);
This could be instr->hydrogen()->types()->last();

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

http://codereview.chromium.org/6708085/diff/13003/src/hydrogen-instructions.c...
src/hydrogen-instructions.cc:1163: types_(types->length()),
You could initialize the list to have capacity Min(types->length,
kMaxLoadPolymorphism).  I'm not sure if it makes much difference.

http://codereview.chromium.org/6708085/diff/13003/src/hydrogen-instructions.c...
src/hydrogen-instructions.cc:1203: if
(!types_.at(j).is_identical_to(other->types()->at(i))) {
Should not be negated.

[fschneider, 2011-03-24 08:43:30]

http://codereview.chromium.org/6708085/diff/13003/src/arm/lithium-codegen-arm.cc
File src/arm/lithium-codegen-arm.cc (right):

http://codereview.chromium.org/6708085/diff/13003/src/arm/lithium-codegen-arm...
src/arm/lithium-codegen-arm.cc:2202: int map_count =
instr->hydrogen()->types()->length();
On 2011/03/23 15:37:29, Kevin Millikin wrote:
> This function still feels too complicated.  Isn't it the case that map_count
==
> 0 implies needs_generic, because map_count is necessarily less than the number
> of maps initially, which is at least two.
> 
> Then we could try something like:
> 
> if (map_count == 0) {
>   ASSERT(needs_generic);
>   // Call the IC.
> } else {
>   for (int i = 0; i < map_count - 1; ++i) ...
>   __ cmp(scratch, /* last map */);
>   if (needs_generic) {
>     Label load;
>     __ b(eq, &load);
>     // Call the IC.
>     __ b(&done);
>     __ bind(&load);
>   } else {
>     DeoptimizeIf(...);
>   }
>   EmitLoadField(...);
>   __ bind(&done);
> }

Done.

http://codereview.chromium.org/6708085/diff/13003/src/arm/lithium-codegen-arm...
src/arm/lithium-codegen-arm.cc:2207: map->LookupInDescriptors(NULL,
*instr->hydrogen()->name(), &lookup);
On 2011/03/23 15:37:29, Kevin Millikin wrote:
> I think you can move the call to LookupInDescriptors into EmitLoadField (and
not
> pass the LookupResult arguments).

Done.

http://codereview.chromium.org/6708085/diff/13003/src/arm/lithium-codegen-arm...
src/arm/lithium-codegen-arm.cc:2216: Handle<Map> map =
instr->hydrogen()->types()->at(map_count - 1);
On 2011/03/23 15:37:29, Kevin Millikin wrote:
> This could be instr->hydrogen()->types()->last();

Done.

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

http://codereview.chromium.org/6708085/diff/13003/src/hydrogen-instructions.c...
src/hydrogen-instructions.cc:1163: types_(types->length()),
On 2011/03/23 15:37:29, Kevin Millikin wrote:
> You could initialize the list to have capacity Min(types->length,
> kMaxLoadPolymorphism).  I'm not sure if it makes much difference.

Done.

http://codereview.chromium.org/6708085/diff/13003/src/hydrogen-instructions.c...
src/hydrogen-instructions.cc:1203: if
(!types_.at(j).is_identical_to(other->types()->at(i))) {
On 2011/03/23 15:37:29, Kevin Millikin wrote:
> Should not be negated.

Of course. Thanks.

[Kevin Millikin (Chromium), 2011-03-24 09:28:24]

http://codereview.chromium.org/6708085/diff/14001/src/arm/lithium-codegen-arm.cc
File src/arm/lithium-codegen-arm.cc (right):

http://codereview.chromium.org/6708085/diff/14001/src/arm/lithium-codegen-arm...
src/arm/lithium-codegen-arm.cc:2228: EmitLoadField(result, object, map, name);
BTW, you can write a single call to EmitLoadField by branching on eq and moving
EmitLoadField out of the if:

if (...) {
  Label load;
  __ b(eq, &load);
  // Call
  __ b(&done);
  __ bind(&load);
} else {
  DeoptimizeIf(...);
}
EmitLoadField(...);

It probably doesn't make much difference.