Implement explicit back pointers in transition tree.

Implement explicit back pointers in transition tree.

This makes back pointers in the map transition tree explicit by having
accurate back pointers throughout the lifetime of maps instead of
establishing and destroying back pointers before and after each marking
phase. This is a prerequisite for being able to clear map transitions
during incremental marking.

R=vegorov@chromium.org
BUG=v8:1465
Committed: https://code.google.com/p/v8/source/detail?r=11528

[Vyacheslav Egorov (Chromium), 2012-05-08 14:29:19]

lgtm

https://chromiumcodereview.appspot.com/10381053/diff/1/src/mark-compact.cc
File src/mark-compact.cc (left):

https://chromiumcodereview.appspot.com/10381053/diff/1/src/mark-compact.cc#ol...
src/mark-compact.cc:683: if (collect_maps_) CreateBackPointers();
side effect of always having back pointer and always treating it as a strong
reference is that map trees will never be able to die from the root (which could
previously happen when running V8 with --nocollect-maps). 

We have seen obscure cases when this would lead to OOM.

Consider making back pointer weak when appropriate to fully mimic old
--collect-maps behavior.

https://chromiumcodereview.appspot.com/10381053/diff/1/src/objects.cc
File src/objects.cc (right):

https://chromiumcodereview.appspot.com/10381053/diff/1/src/objects.cc#newcode...
src/objects.cc:5172: Object* header = *Header();
is this change really required?

https://chromiumcodereview.appspot.com/10381053/diff/1/src/objects.cc#newcode...
src/objects.cc:5174: proto_trans_->length() >= Map::kProtoTransitionHeaderSize);
should not this just be >?

https://chromiumcodereview.appspot.com/10381053/diff/1/src/objects.h
File src/objects.h (right):

https://chromiumcodereview.appspot.com/10381053/diff/1/src/objects.h#newcode4729
src/objects.h:4729: DECL_ACCESSORS(back_pointer, Object)
I would prefer if this was declared as GetBackPointer() and SetBackPointer() to
show that this is not a trivial getter/setter.

https://chromiumcodereview.appspot.com/10381053/diff/1/src/profile-generator.cc
File src/profile-generator.cc (right):

https://chromiumcodereview.appspot.com/10381053/diff/1/src/profile-generator....
src/profile-generator.cc:2155: SetInternalReference(map, entry,
You might also want to include back pointer as a strong reference (which it is).

[Michael Starzinger, 2012-05-09 07:30:02]

Addressed comments. Rebased. Landed.

https://chromiumcodereview.appspot.com/10381053/diff/1/src/mark-compact.cc
File src/mark-compact.cc (left):

https://chromiumcodereview.appspot.com/10381053/diff/1/src/mark-compact.cc#ol...
src/mark-compact.cc:683: if (collect_maps_) CreateBackPointers();
On 2012/05/08 14:29:19, Vyacheslav Egorov wrote:
> side effect of always having back pointer and always treating it as a strong
> reference is that map trees will never be able to die from the root (which
could
> previously happen when running V8 with --nocollect-maps). 
> 
> We have seen obscure cases when this would lead to OOM.
> 
> Consider making back pointer weak when appropriate to fully mimic old
> --collect-maps behavior. 

Yes, that is a good point. I will address this comment in the follow-up CL that
enables map collection for incremental marking. Because it's much easier to do
that once we don't have to special-case incremental marking anymore.

https://chromiumcodereview.appspot.com/10381053/diff/1/src/objects.cc
File src/objects.cc (right):

https://chromiumcodereview.appspot.com/10381053/diff/1/src/objects.cc#newcode...
src/objects.cc:5172: Object* header = *Header();
On 2012/05/08 14:29:19, Vyacheslav Egorov wrote:
> is this change really required?

Yes it is, because this iterator overwrites the map of the prototype_transitions
array to hold a SMI representing the iteration index. So here I need to check
whether proto_trans_ actually is a valid FixedArray only if the map is still
intact.

I admit it's mighty confusing, so I tried to clean it up a bit.

https://chromiumcodereview.appspot.com/10381053/diff/1/src/objects.cc#newcode...
src/objects.cc:5174: proto_trans_->length() >= Map::kProtoTransitionHeaderSize);
On 2012/05/08 14:29:19, Vyacheslav Egorov wrote:
> should not this just be >?

Done. The length check is obsolete actually. The prototype transitions can never
have an empty fixed array as a backing store, it's size is always >
kProtoTransitionHeaderSize.

https://chromiumcodereview.appspot.com/10381053/diff/1/src/objects.h
File src/objects.h (right):

https://chromiumcodereview.appspot.com/10381053/diff/1/src/objects.h#newcode4729
src/objects.h:4729: DECL_ACCESSORS(back_pointer, Object)
On 2012/05/08 14:29:19, Vyacheslav Egorov wrote:
> I would prefer if this was declared as GetBackPointer() and SetBackPointer()
to
> show that this is not a trivial getter/setter.

Done.

https://chromiumcodereview.appspot.com/10381053/diff/1/src/profile-generator.cc
File src/profile-generator.cc (right):

https://chromiumcodereview.appspot.com/10381053/diff/1/src/profile-generator....
src/profile-generator.cc:2155: SetInternalReference(map, entry,
On 2012/05/08 14:29:19, Vyacheslav Egorov wrote:
> You might also want to include back pointer as a strong reference (which it
is).

Done.