In-place shrinking of descriptor arrays with non-live transitions.

In-place shrinking of descriptor arrays with non-live transitions.
Instead of overwriting non-live transitions with NULL_DESCRIPTORs, we remove them from the array by compacting the array (shifting live values to the left) and in-place trimming the array. If the final descriptor array contains no live values (only contained transitions which are now all cleared), we move bit_field3 back from the descriptor array to the map. The descriptor array itself will be collected in the next GC.


BUG=
TEST=

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

[Toon Verwaest, 2012-06-20 11:48:13]

PTAL.

[Michael Starzinger, 2012-06-25 11:21:57]

First round.

https://chromiumcodereview.appspot.com/10575032/diff/1/src/ic.cc
File src/ic.cc (left):

https://chromiumcodereview.appspot.com/10575032/diff/1/src/ic.cc#oldcode1443
src/ic.cc:1443: ASSERT(lookup->type() != NULL_DESCRIPTOR);
We should actually keep this and assert against NONEXISTENT now.

https://chromiumcodereview.appspot.com/10575032/diff/1/src/ic.cc#oldcode1945
src/ic.cc:1945: ASSERT(lookup->type() != NULL_DESCRIPTOR);
Likewise.

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

https://chromiumcodereview.appspot.com/10575032/diff/1/src/objects-inl.h#newc...
src/objects-inl.h:3487: void Map::SetOwnBitField3(int value) {
That method name is mighty confusing! Is should actually be named
ClearDescriptorArray I guess.

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

https://chromiumcodereview.appspot.com/10575032/diff/1/src/objects.cc#newcode...
src/objects.cc:7346: static void RightTrimFixedArray(Heap* heap, FixedArray*
elms, int to_trim) {
Add a comment that this function is only called from within the GC. Otherwise
the live-bytes counter will be inconsistent.

https://chromiumcodereview.appspot.com/10575032/diff/1/src/objects.cc#newcode...
src/objects.cc:7355: STATIC_ASSERT(FixedArray::kHeaderSize == 2 * kPointerSize);
These asserts are not needed for left-trimming!

https://chromiumcodereview.appspot.com/10575032/diff/1/src/objects.cc#newcode...
src/objects.cc:7357: const int len = elms->length();
Add an ASSERT(to_trim < len), other cases aren't handled correctly here.

https://chromiumcodereview.appspot.com/10575032/diff/1/src/objects.cc#newcode...
src/objects.cc:7359: Address new_end = elms->address() + FixedArray::kHeaderSize
+
Better use "elms->address() + FixedArray::SizeFor(len - to_trim)" here.

https://chromiumcodereview.appspot.com/10575032/diff/1/src/objects.cc#newcode...
src/objects.cc:7361: if (to_trim > FixedArray::kHeaderSize / kPointerSize &&
This condition doesn't make much sense to me. And as discussed offline, the
zapping is probably only needed for debug mode with the new GC.

https://chromiumcodereview.appspot.com/10575032/diff/1/src/objects.cc#newcode...
src/objects.cc:7364: // formerly part of the array so that the GC (aided by the
card-based
Comment no longer applies.

https://chromiumcodereview.appspot.com/10575032/diff/1/src/objects.cc#newcode...
src/objects.cc:7389: static bool ClearDescriptor(Heap* heap,
We should give this function the "ClearNonLive" prefix as well. How about
"ClearNonLiveTransitionsFromDescriptor"?

Also a comment describing the semantics of the return value would nice.

https://chromiumcodereview.appspot.com/10575032/diff/1/src/objects.cc#newcode...
src/objects.cc:7454: while (descriptor_index < d->number_of_descriptors() &&
Is there a strong reason why this loop is split into two parts and interleaved
with the clearing of elements transitions? Is seems overly complicated. Can we
merge these two loops into one?

[Toon Verwaest, 2012-06-25 12:20:48]

Addressed comments, PTAL.

https://chromiumcodereview.appspot.com/10575032/diff/1/src/ic.cc
File src/ic.cc (left):

https://chromiumcodereview.appspot.com/10575032/diff/1/src/ic.cc#oldcode1443
src/ic.cc:1443: ASSERT(lookup->type() != NULL_DESCRIPTOR);
As discussed offline, replaced with IsFound().

On 2012/06/25 11:21:57, Michael Starzinger wrote:
> We should actually keep this and assert against NONEXISTENT now.

https://chromiumcodereview.appspot.com/10575032/diff/1/src/ic.cc#oldcode1945
src/ic.cc:1945: ASSERT(lookup->type() != NULL_DESCRIPTOR);
On 2012/06/25 11:21:57, Michael Starzinger wrote:
> Likewise.

Done.

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

https://chromiumcodereview.appspot.com/10575032/diff/1/src/objects-inl.h#newc...
src/objects-inl.h:3487: void Map::SetOwnBitField3(int value) {
On 2012/06/25 11:21:57, Michael Starzinger wrote:
> That method name is mighty confusing! Is should actually be named
> ClearDescriptorArray I guess.

Done.

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

https://chromiumcodereview.appspot.com/10575032/diff/1/src/objects.cc#newcode...
src/objects.cc:7346: static void RightTrimFixedArray(Heap* heap, FixedArray*
elms, int to_trim) {
On 2012/06/25 11:21:57, Michael Starzinger wrote:
> Add a comment that this function is only called from within the GC. Otherwise
> the live-bytes counter will be inconsistent.

Done.

https://chromiumcodereview.appspot.com/10575032/diff/1/src/objects.cc#newcode...
src/objects.cc:7355: STATIC_ASSERT(FixedArray::kHeaderSize == 2 * kPointerSize);
On 2012/06/25 11:21:57, Michael Starzinger wrote:
> These asserts are not needed for left-trimming!

Done.

https://chromiumcodereview.appspot.com/10575032/diff/1/src/objects.cc#newcode...
src/objects.cc:7357: const int len = elms->length();
On 2012/06/25 11:21:57, Michael Starzinger wrote:
> Add an ASSERT(to_trim < len), other cases aren't handled correctly here.

Done.

https://chromiumcodereview.appspot.com/10575032/diff/1/src/objects.cc#newcode...
src/objects.cc:7359: Address new_end = elms->address() + FixedArray::kHeaderSize
+
On 2012/06/25 11:21:57, Michael Starzinger wrote:
> Better use "elms->address() + FixedArray::SizeFor(len - to_trim)" here.

Done.

https://chromiumcodereview.appspot.com/10575032/diff/1/src/objects.cc#newcode...
src/objects.cc:7361: if (to_trim > FixedArray::kHeaderSize / kPointerSize &&
On 2012/06/25 11:21:57, Michael Starzinger wrote:
> This condition doesn't make much sense to me. And as discussed offline, the
> zapping is probably only needed for debug mode with the new GC.

Done.

https://chromiumcodereview.appspot.com/10575032/diff/1/src/objects.cc#newcode...
src/objects.cc:7364: // formerly part of the array so that the GC (aided by the
card-based
On 2012/06/25 11:21:57, Michael Starzinger wrote:
> Comment no longer applies.

Done.

https://chromiumcodereview.appspot.com/10575032/diff/1/src/objects.cc#newcode...
src/objects.cc:7389: static bool ClearDescriptor(Heap* heap,
On 2012/06/25 11:21:57, Michael Starzinger wrote:
> We should give this function the "ClearNonLive" prefix as well. How about
> "ClearNonLiveTransitionsFromDescriptor"?
> 
> Also a comment describing the semantics of the return value would nice.

Done.

https://chromiumcodereview.appspot.com/10575032/diff/1/src/objects.cc#newcode...
src/objects.cc:7454: while (descriptor_index < d->number_of_descriptors() &&
On 2012/06/25 11:21:57, Michael Starzinger wrote:
> Is there a strong reason why this loop is split into two parts and interleaved
> with the clearing of elements transitions? Is seems overly complicated. Can we
> merge these two loops into one?

Done.

[Michael Starzinger, 2012-06-25 12:48:37]

LGTM (with a few final nits).

https://chromiumcodereview.appspot.com/10575032/diff/6001/src/ic.cc
File src/ic.cc (right):

https://chromiumcodereview.appspot.com/10575032/diff/6001/src/ic.cc#newcode1942
src/ic.cc:1942: ASSERT(lookup->IsFound());
Add an empty line so that it looks consistent with StoreIC::UpdateCaches.

https://chromiumcodereview.appspot.com/10575032/diff/6001/src/objects.cc
File src/objects.cc (right):

https://chromiumcodereview.appspot.com/10575032/diff/6001/src/objects.cc#newc...
src/objects.cc:7364: !heap->InNewSpace(elms)) {
Since it's debug code now, I think we should just unconditionally zap, no matter
how much we trim or in which space we trim.

https://chromiumcodereview.appspot.com/10575032/diff/6001/src/objects.cc#newc...
src/objects.cc:7367: zap++;  // Header of filler must be at least one word so
skip that.
Using the same reasoning, I think we should also just zap the first word.

https://chromiumcodereview.appspot.com/10575032/diff/6001/src/objects.cc#newc...
src/objects.cc:7390: static bool ClearNonLiveTransitionsFromDescriptor(Heap*
heap,
Add a comment describing the semantics of the return value.

https://chromiumcodereview.appspot.com/10575032/diff/6001/src/objects.h
File src/objects.h (right):

https://chromiumcodereview.appspot.com/10575032/diff/6001/src/objects.h#newco...
src/objects.h:4776: // store transitions, which does not contain any live
transitions anymore.
"[...] store transitions and does not [...]"