Optimize the equality check case of ICCompare stubs.

Optimize the equality check case of ICCompare stubs.

This includes specialcasing the generation when we know that the maps
of the two objects are the same. In addition, a new specialized
compare ic known objects cache is created.

The reason for the cache is that we need to have access to the stub
code from the roots; if we do not, the GC will collect the stub. In
this specialized case we use the map pointer as key in the cache, and
we always do a lookup before generating code. Actually hitting
something in the cache will happen very rarely, but we could
potentially overwrite an existing stub, which again will lead to the
GC collecting this old stub (even if it is referenced from other code
objects)
Committed: http://code.google.com/p/v8/source/detail?r=10216

[Rico, 2011-11-10 15:28:52]

This is the ia32 only version, if it looks good I will do the x64 and arm
versions

[Kevin Millikin (Chromium), 2011-11-10 19:08:42]

Even though I have a bunch of comments, this is pretty close.

http://codereview.chromium.org/8520006/diff/17001/src/code-stubs.cc
File src/code-stubs.cc (right):

http://codereview.chromium.org/8520006/diff/17001/src/code-stubs.cc#newcode105
src/code-stubs.cc:105: if (use_special_cache || !FindCodeInCache(&code)) {
I think this is a little clearer if it is something like:

if (use_special_cache) {
  if (FindCodeInSpecialCache(&code)) return Handle<Code>(code);
} else {
  if (FindCodeInCache(&code)) return Handle<Code>(code);
}

or if you wanted to be a bit twisted:

if (use_special_cache
        ? FindCodeInSpecialCache(&code)
        : FindCodeInCache(&code)) {
  return Handle<Code>(code);
}

http://codereview.chromium.org/8520006/diff/17001/src/code-stubs.cc#newcode176
src/code-stubs.cc:176: Isolate* isolate = Isolate::Current();
If you want to avoid TLS to fetch the isolate, you could pass in the one you
have from GetCode or else use new_object->isolate().

http://codereview.chromium.org/8520006/diff/17001/src/code-stubs.h
File src/code-stubs.h (right):

http://codereview.chromium.org/8520006/diff/17001/src/code-stubs.h#newcode447
src/code-stubs.h:447: static void GenerateKnownObjects(MacroAssembler* masm,
Map* map);
Put this down in the private section with the other Generate... functions.  Make
it non-static.  Do not pass map (== known_map_) as an argument, but instead use
known_map_ in the generate function.

http://codereview.chromium.org/8520006/diff/17001/src/code-stubs.h#newcode449
src/code-stubs.h:449: void set_known_map(Map* map) { known_map_ = map; }
Make map a Handle<Map>.  There's a risk that a GC occurs between
set_known_map(map) and Generate().

http://codereview.chromium.org/8520006/diff/17001/src/code-stubs.h#newcode476
src/code-stubs.h:476: Map* known_map_;
Handle<Map>.

http://codereview.chromium.org/8520006/diff/17001/src/hydrogen.cc
File src/hydrogen.cc (right):

http://codereview.chromium.org/8520006/diff/17001/src/hydrogen.cc#newcode6000
src/hydrogen.cc:6000: case Token::EQ_STRICT: {
I guess if EQ_STRICT, then we'll never have a compare map (because we don't go
to KNOWN_OBJECTS in that case).  I wonder if we should?

http://codereview.chromium.org/8520006/diff/17001/src/ia32/code-stubs-ia32.cc
File src/ia32/code-stubs-ia32.cc (right):

http://codereview.chromium.org/8520006/diff/17001/src/ia32/code-stubs-ia32.cc...
src/ia32/code-stubs-ia32.cc:6521: __ bind(&miss);
All the code from here and below looks like it could be generated by a call to
GenerateMiss(masm) (if this function were non-static).

http://codereview.chromium.org/8520006/diff/17001/src/ia32/code-stubs-ia32.cc...
src/ia32/code-stubs-ia32.cc:6524: __ pop(ecx);
And come to think of it, I don't know why we preserve the incoming arguments
under the return address in the existing code.  Instead, it would be a bit more
straightforward to save them above and save a pair of push/pops to do:

{ FrameScope scope(masm, StackFrame::INTERNAL);
  __ push(edx);  // Preserve edx and eax.
  __ push(eax);
  __ push(edx);  // And also use them as the arguments.
  __ push(eax);
  __ push(Immediate(Smi::FromInt(Token::EQ)));
  __ CallExternalReference(runtime, 3);
  __ pop(eax);
  __ pop(edx);
}
// Compute the entry point of the rewritten stub.
__ lea(edi, FieldOperand(eax, Code::kHeaderSize));
// Do a tail call to the rewritten stub.
__ jmp(edi);

http://codereview.chromium.org/8520006/diff/17001/src/ia32/ic-ia32.cc
File src/ia32/ic-ia32.cc (right):

http://codereview.chromium.org/8520006/diff/17001/src/ia32/ic-ia32.cc#newcode...
src/ia32/ic-ia32.cc:1630: rewritten = stub.GetCode(true);
Nicer to have a virtual "UseSpecialCache" function you can override for just
this stub, instead of the parameter (with a default, and a boolean).

http://codereview.chromium.org/8520006/diff/17001/src/ic.cc
File src/ic.cc (right):

http://codereview.chromium.org/8520006/diff/17001/src/ic.cc#newcode2336
src/ic.cc:2336: if (state == UNINITIALIZED && x->IsSmi() && y->IsSmi()) {
I don't like this function.  It's really hard to figure out what transitions
will happen.

It seems to be programmed after listing the possible output types with some
exceptions up front, but that's not the way that most people think about state
transitions.  What about rewriting it to something more structured like:

switch (state) {
  case UNINITIALIZED:
    if (x->IsSmi() && y->IsSmi()) return SMIS;
    if (x->IsNumber() && y->IsNumber()) return HEAP_NUMBERS;
    if (!Token::IsEqualityOp(op_)) return GENERIC;
    if (x->IsSymbol() && y->IsSymbol()) return SYMBOLS;
    if (x->IsString() && y->IsString()) return STRINGS;
    if (x->IsJSObject() && y->IsJSObject()) {
      // Your new stuff here.
    }
    return GENERIC;
  case SMIS:
    return has_inlined_smi_code && x->IsNumber() && y->IsNumber()
        ? HEAP_NUMBERS
        : GENERIC;
  case SYMBOLS:
    ASSERT(Token::IsEqualityOp(op_));
    return x->IsString() && y->IsString() ? STRINGS : GENERIC;
  case HEAP_NUMBERS:
  case STRINGS:
  case OBJECTS:
  case KNOWN_OBJECTS:
  case GENERIC:
    return GENERIC;
}

[Kevin Millikin (Chromium), 2011-11-10 19:11:18]

http://codereview.chromium.org/8520006/diff/17001/src/code-stubs.cc
File src/code-stubs.cc (right):

http://codereview.chromium.org/8520006/diff/17001/src/code-stubs.cc#newcode105
src/code-stubs.cc:105: if (use_special_cache || !FindCodeInCache(&code)) {

And then include the compilation code starting with the HandleScope, obviously.

http://codereview.chromium.org/8520006/diff/17001/src/ia32/code-stubs-ia32.cc
File src/ia32/code-stubs-ia32.cc (right):

http://codereview.chromium.org/8520006/diff/17001/src/ia32/code-stubs-ia32.cc...
src/ia32/code-stubs-ia32.cc:6524: __ pop(ecx);
Actually, that code has a bug.  You need lea before popping to restore eax.

[Rico, 2011-11-11 08:49:10]

Comments addressed.
GenerateKnownObjects being static was a leftover from just creating the code and
returning it without using the cache, changed to non-static and simplified by
using the normal GenerateMiss.

http://codereview.chromium.org/8520006/diff/17001/src/code-stubs.cc
File src/code-stubs.cc (right):

http://codereview.chromium.org/8520006/diff/17001/src/code-stubs.cc#newcode105
src/code-stubs.cc:105: if (use_special_cache || !FindCodeInCache(&code)) {
On 2011/11/10 19:08:42, Kevin Millikin wrote:
> I think this is a little clearer if it is something like:
> 
> if (use_special_cache) {
>   if (FindCodeInSpecialCache(&code)) return Handle<Code>(code);
> } else {
>   if (FindCodeInCache(&code)) return Handle<Code>(code);
> }
> 
> or if you wanted to be a bit twisted:
> 
> if (use_special_cache
>         ? FindCodeInSpecialCache(&code)
>         : FindCodeInCache(&code)) {
>   return Handle<Code>(code);
> }

Done and moved the pregenerated check up here

http://codereview.chromium.org/8520006/diff/17001/src/code-stubs.cc#newcode176
src/code-stubs.cc:176: Isolate* isolate = Isolate::Current();
On 2011/11/10 19:08:42, Kevin Millikin wrote:
> If you want to avoid TLS to fetch the isolate, you could pass in the one you
> have from GetCode or else use new_object->isolate().

Done.

http://codereview.chromium.org/8520006/diff/17001/src/code-stubs.h
File src/code-stubs.h (right):

http://codereview.chromium.org/8520006/diff/17001/src/code-stubs.h#newcode447
src/code-stubs.h:447: static void GenerateKnownObjects(MacroAssembler* masm,
Map* map);
On 2011/11/10 19:08:42, Kevin Millikin wrote:
> Put this down in the private section with the other Generate... functions. 
Make
> it non-static.  Do not pass map (== known_map_) as an argument, but instead
use
> known_map_ in the generate function.

Done.

http://codereview.chromium.org/8520006/diff/17001/src/code-stubs.h#newcode449
src/code-stubs.h:449: void set_known_map(Map* map) { known_map_ = map; }
On 2011/11/10 19:08:42, Kevin Millikin wrote:
> Make map a Handle<Map>.  There's a risk that a GC occurs between
> set_known_map(map) and Generate().
OK, will do, but maps don't move right, and we already have handles to the
objects with the maps, so I think this should be safe even without handles

http://codereview.chromium.org/8520006/diff/17001/src/code-stubs.h#newcode476
src/code-stubs.h:476: Map* known_map_;
On 2011/11/10 19:08:42, Kevin Millikin wrote:
> Handle<Map>.

Done.

http://codereview.chromium.org/8520006/diff/17001/src/hydrogen.cc
File src/hydrogen.cc (right):

http://codereview.chromium.org/8520006/diff/17001/src/hydrogen.cc#newcode6000
src/hydrogen.cc:6000: case Token::EQ_STRICT: {
On 2011/11/10 19:08:42, Kevin Millikin wrote:
> I guess if EQ_STRICT, then we'll never have a compare map (because we don't go
> to KNOWN_OBJECTS in that case).  I wonder if we should?
Of course we should, nice catch.

http://codereview.chromium.org/8520006/diff/17001/src/ia32/code-stubs-ia32.cc
File src/ia32/code-stubs-ia32.cc (right):

http://codereview.chromium.org/8520006/diff/17001/src/ia32/code-stubs-ia32.cc...
src/ia32/code-stubs-ia32.cc:6521: __ bind(&miss);
On 2011/11/10 19:08:42, Kevin Millikin wrote:
> All the code from here and below looks like it could be generated by a call to
> GenerateMiss(masm) (if this function were non-static).

Done.

http://codereview.chromium.org/8520006/diff/17001/src/ia32/ic-ia32.cc
File src/ia32/ic-ia32.cc (right):

http://codereview.chromium.org/8520006/diff/17001/src/ia32/ic-ia32.cc#newcode...
src/ia32/ic-ia32.cc:1630: rewritten = stub.GetCode(true);
On 2011/11/10 19:08:42, Kevin Millikin wrote:
> Nicer to have a virtual "UseSpecialCache" function you can override for just
> this stub, instead of the parameter (with a default, and a boolean).

Done.

http://codereview.chromium.org/8520006/diff/17001/src/ic.cc
File src/ic.cc (right):

http://codereview.chromium.org/8520006/diff/17001/src/ic.cc#newcode2336
src/ic.cc:2336: if (state == UNINITIALIZED && x->IsSmi() && y->IsSmi()) {
On 2011/11/10 19:08:42, Kevin Millikin wrote:
> I don't like this function.  It's really hard to figure out what transitions
> will happen.
> 
> It seems to be programmed after listing the possible output types with some
> exceptions up front, but that's not the way that most people think about state
> transitions.  What about rewriting it to something more structured like:
> 
> switch (state) {
>   case UNINITIALIZED:
>     if (x->IsSmi() && y->IsSmi()) return SMIS;
>     if (x->IsNumber() && y->IsNumber()) return HEAP_NUMBERS;
>     if (!Token::IsEqualityOp(op_)) return GENERIC;
>     if (x->IsSymbol() && y->IsSymbol()) return SYMBOLS;
>     if (x->IsString() && y->IsString()) return STRINGS;
>     if (x->IsJSObject() && y->IsJSObject()) {
>       // Your new stuff here.
>     }
>     return GENERIC;
>   case SMIS:
>     return has_inlined_smi_code && x->IsNumber() && y->IsNumber()
>         ? HEAP_NUMBERS
>         : GENERIC;
>   case SYMBOLS:
>     ASSERT(Token::IsEqualityOp(op_));
>     return x->IsString() && y->IsString() ? STRINGS : GENERIC;
>   case HEAP_NUMBERS:
>   case STRINGS:
>   case OBJECTS:
>   case KNOWN_OBJECTS:
>   case GENERIC:
>     return GENERIC;
> }

Done.

[Kevin Millikin (Chromium), 2011-11-11 10:12:34]

Next round of comments.

http://codereview.chromium.org/8520006/diff/29001/src/code-stubs.cc
File src/code-stubs.cc (right):

http://codereview.chromium.org/8520006/diff/29001/src/code-stubs.cc#newcode107
src/code-stubs.cc:107: CHECK(IsPregenerated() == code->is_pregenerated());
Maybe I'm missing a good reason for this, but please change this to an ASSERT.

http://codereview.chromium.org/8520006/diff/29001/src/code-stubs.cc#newcode134
src/code-stubs.cc:134: CHECK(AddToSpecialCache(new_object));
This function can only return true, so get rid of the CHECK and make the return
type void.

http://codereview.chromium.org/8520006/diff/29001/src/code-stubs.cc#newcode174
src/code-stubs.cc:174: Isolate* isolate = new_object->GetIsolate();
I still don't fully understand why we need a separate caching mechanism here
(but didn't before).  I want to talk to the GC gurus a bit more.

I'm worried that adding special caches doesn't scale.  Could we instead add just
a special symbol and use the cache in the map.  The implementation would become
something like:

void ICCompareStub::AddToSpecialCache(Handle<Code> new_object) {
  return Map::UpdateCodeCache(known_map_,
                              factory()->compare_ic_symbol(),
                              new_object);
}

http://codereview.chromium.org/8520006/diff/29001/src/code-stubs.cc#newcode194
src/code-stubs.cc:194: UNREACHABLE();
Huh?

http://codereview.chromium.org/8520006/diff/29001/src/code-stubs.cc#newcode228
src/code-stubs.cc:228: GenerateKnownObjects(masm, known_map_);
No real need to pass known_map_ here.

http://codereview.chromium.org/8520006/diff/29001/src/code-stubs.h
File src/code-stubs.h (right):

http://codereview.chromium.org/8520006/diff/29001/src/code-stubs.h#newcode474
src/code-stubs.h:474: bool AddToSpecialCache(Handle<Code> new_object);
It seems better to declare these virtual.

http://codereview.chromium.org/8520006/diff/29001/src/ia32/code-stubs-ia32.cc
File src/ia32/code-stubs-ia32.cc (right):

http://codereview.chromium.org/8520006/diff/29001/src/ia32/code-stubs-ia32.cc...
src/ia32/code-stubs-ia32.cc:6506: Handle<Map> map) {
No need for the extra argument.

http://codereview.chromium.org/8520006/diff/29001/src/ia32/code-stubs-ia32.cc...
src/ia32/code-stubs-ia32.cc:6514: __ cmp(ecx, map);
cmp(ecx, known_map_)

http://codereview.chromium.org/8520006/diff/29001/src/ia32/code-stubs-ia32.cc...
src/ia32/code-stubs-ia32.cc:6529: __ pop(ecx);
I'm not sure why this code is written this way, but since you're in this file,
could you clean it up a bit: there is no reason to pop the return address to
save eax and edx in the caller's frame.  Just save them on the internal frame
since there's going to be one anyway.

http://codereview.chromium.org/8520006/diff/29001/src/ic.cc
File src/ic.cc (right):

http://codereview.chromium.org/8520006/diff/29001/src/ic.cc#newcode2343
src/ic.cc:2343: (op_ == Token::EQ || op_ == Token::EQ_STRICT)) {
This is much nicer.

The last check can be written Token::IsEqualityOp(op_)

[Rico, 2011-11-15 10:12:26]

Comments addressed

http://codereview.chromium.org/8520006/diff/29001/src/code-stubs.cc
File src/code-stubs.cc (right):

http://codereview.chromium.org/8520006/diff/29001/src/code-stubs.cc#newcode107
src/code-stubs.cc:107: CHECK(IsPregenerated() == code->is_pregenerated());
On 2011/11/11 10:12:34, Kevin Millikin wrote:
> Maybe I'm missing a good reason for this, but please change this to an ASSERT.
Done (checked with Erik that we can actally make this an ASSERT again (it was
introduced in revision 9482 to catch a bug)

http://codereview.chromium.org/8520006/diff/29001/src/code-stubs.cc#newcode134
src/code-stubs.cc:134: CHECK(AddToSpecialCache(new_object));
On 2011/11/11 10:12:34, Kevin Millikin wrote:
> This function can only return true, so get rid of the CHECK and make the
return
> type void.

Done.

http://codereview.chromium.org/8520006/diff/29001/src/code-stubs.cc#newcode174
src/code-stubs.cc:174: Isolate* isolate = new_object->GetIsolate();
On 2011/11/11 10:12:34, Kevin Millikin wrote:
> I still don't fully understand why we need a separate caching mechanism here
> (but didn't before).  I want to talk to the GC gurus a bit more.
> 
> I'm worried that adding special caches doesn't scale.  Could we instead add
just
> a special symbol and use the cache in the map.  The implementation would
become
> something like:
> 
> void ICCompareStub::AddToSpecialCache(Handle<Code> new_object) {
>   return Map::UpdateCodeCache(known_map_,
>                               factory()->compare_ic_symbol(),
>                               new_object);
> }
I discussed with Erik and found a solution for using the code-cache (see the new
change in mark-compact.cc)

http://codereview.chromium.org/8520006/diff/29001/src/code-stubs.cc#newcode194
src/code-stubs.cc:194: UNREACHABLE();
On 2011/11/11 10:12:34, Kevin Millikin wrote:
> Huh?

Done.

http://codereview.chromium.org/8520006/diff/29001/src/code-stubs.cc#newcode228
src/code-stubs.cc:228: GenerateKnownObjects(masm, known_map_);
On 2011/11/11 10:12:34, Kevin Millikin wrote:
> No real need to pass known_map_ here.

Done.

http://codereview.chromium.org/8520006/diff/29001/src/code-stubs.h
File src/code-stubs.h (right):

http://codereview.chromium.org/8520006/diff/29001/src/code-stubs.h#newcode474
src/code-stubs.h:474: bool AddToSpecialCache(Handle<Code> new_object);
On 2011/11/11 10:12:34, Kevin Millikin wrote:
> It seems better to declare these virtual.

Done.

http://codereview.chromium.org/8520006/diff/29001/src/ia32/code-stubs-ia32.cc
File src/ia32/code-stubs-ia32.cc (right):

http://codereview.chromium.org/8520006/diff/29001/src/ia32/code-stubs-ia32.cc...
src/ia32/code-stubs-ia32.cc:6506: Handle<Map> map) {
On 2011/11/11 10:12:34, Kevin Millikin wrote:
> No need for the extra argument.

Done.

http://codereview.chromium.org/8520006/diff/29001/src/ia32/code-stubs-ia32.cc...
src/ia32/code-stubs-ia32.cc:6514: __ cmp(ecx, map);
On 2011/11/11 10:12:34, Kevin Millikin wrote:
> cmp(ecx, known_map_)
Done (and below)

http://codereview.chromium.org/8520006/diff/29001/src/ia32/code-stubs-ia32.cc...
src/ia32/code-stubs-ia32.cc:6529: __ pop(ecx);
On 2011/11/11 10:12:34, Kevin Millikin wrote:
> I'm not sure why this code is written this way, but since you're in this file,
> could you clean it up a bit: there is no reason to pop the return address to
> save eax and edx in the caller's frame.  Just save them on the internal frame
> since there's going to be one anyway.

Done.

http://codereview.chromium.org/8520006/diff/29001/src/ic.cc
File src/ic.cc (right):

http://codereview.chromium.org/8520006/diff/29001/src/ic.cc#newcode2343
src/ic.cc:2343: (op_ == Token::EQ || op_ == Token::EQ_STRICT)) {
On 2011/11/11 10:12:34, Kevin Millikin wrote:
> This is much nicer.
> 
> The last check can be written Token::IsEqualityOp(op_)

Done.

[Kevin Millikin (Chromium), 2011-12-08 13:38:15]

LGTM, except I'm not sure why we never look compare stubs in the map code cache.

http://codereview.chromium.org/8520006/diff/48001/src/code-stubs.cc
File src/code-stubs.cc (right):

http://codereview.chromium.org/8520006/diff/48001/src/code-stubs.cc#newcode131
src/code-stubs.cc:131: // Update the dictionary and the root in Heap.
Move this comment into the else branch.

http://codereview.chromium.org/8520006/diff/48001/src/code-stubs.cc#newcode183
src/code-stubs.cc:183: return false;
Why don't we look it up in the map?

http://codereview.chromium.org/8520006/diff/48001/src/heap.h
File src/heap.h (right):

http://codereview.chromium.org/8520006/diff/48001/src/heap.h#newcode238
src/heap.h:238: V(compare_ic_symbol, "compare_ic")                              
      \
Maybe choose a symbol that isn't a valid identifier so it is less likely to
clash with property names?

[Rico, 2011-12-08 15:54:56]

Added lookup in the map cache, please take a quick look on this

http://codereview.chromium.org/8520006/diff/48001/src/code-stubs.cc
File src/code-stubs.cc (right):

http://codereview.chromium.org/8520006/diff/48001/src/code-stubs.cc#newcode131
src/code-stubs.cc:131: // Update the dictionary and the root in Heap.
On 2011/12/08 13:38:15, Kevin Millikin wrote:
> Move this comment into the else branch.

Done.

http://codereview.chromium.org/8520006/diff/48001/src/code-stubs.cc#newcode183
src/code-stubs.cc:183: return false;
On 2011/12/08 13:38:15, Kevin Millikin wrote:
> Why don't we look it up in the map?

Done.

http://codereview.chromium.org/8520006/diff/48001/src/heap.h
File src/heap.h (right):

http://codereview.chromium.org/8520006/diff/48001/src/heap.h#newcode238
src/heap.h:238: V(compare_ic_symbol, "compare_ic")                              
      \
On 2011/12/08 13:38:15, Kevin Millikin wrote:
> Maybe choose a symbol that isn't a valid identifier so it is less likely to
> clash with property names?

Done.

[Kevin Millikin (Chromium), 2011-12-08 16:07:40]

OK.  Still LGTM.

http://codereview.chromium.org/8520006/diff/56014/src/heap.h
File src/heap.h (right):

http://codereview.chromium.org/8520006/diff/56014/src/heap.h#newcode238
src/heap.h:238: V(compare_ic_symbol, "(compare_ic)")                            
      \
I think the ones just above are print names.  We sometimes use something like
".compare_ic" for secret identifiers (.result, .catch-var, etc.).