Provide baseline for experimental GC implementation.

src/mark-compact.cc

 // Copyright 2006-2008 the V8 project authors. All rights reserved.
 // Redistribution and use in source and binary forms, with or without
 // modification, are permitted provided that the following conditions are
 // met:
 //
 //     * Redistributions of source code must retain the above copyright
 //       notice, this list of conditions and the following disclaimer.
 //     * Redistributions in binary form must reproduce the above
 //       copyright notice, this list of conditions and the following
 //       disclaimer in the documentation and/or other materials provided
@@ skipping 63 matching lines @@
   // Prepare has selected whether to compact the old generation or not.
   // Tell the tracer.
   if (IsCompacting()) tracer_->set_is_compacting();
 
   MarkLiveObjects();
 
   if (FLAG_collect_maps) ClearNonLiveTransitions();
 
   SweepLargeObjectSpace();
 
-  if (IsCompacting()) {
-    GCTracer::Scope gc_scope(tracer_, GCTracer::Scope::MC_COMPACT);
-    EncodeForwardingAddresses();
-
-    Heap::MarkMapPointersAsEncoded(true);
-    UpdatePointers();
-    Heap::MarkMapPointersAsEncoded(false);
-    PcToCodeCache::FlushPcToCodeCache();
-
-    RelocateObjects();
-  } else {
-    SweepSpaces();
-    PcToCodeCache::FlushPcToCodeCache();
-  }
+  SweepSpaces();
+  PcToCodeCache::FlushPcToCodeCache();
 
   Finish();
 
   // Save the count of marked objects remaining after the collection and
   // null out the GC tracer.
   previous_marked_count_ = tracer_->marked_count();
   ASSERT(previous_marked_count_ == 0);
   tracer_ = NULL;
 }
 
 
 void MarkCompactCollector::Prepare(GCTracer* tracer) {
+  FLAG_flush_code = false;
+  FLAG_always_compact = false;
+  FLAG_never_compact = true;
+
   // Rather than passing the tracer around we stash it in a static member
   // variable.
   tracer_ = tracer;
 
 #ifdef DEBUG
   ASSERT(state_ == IDLE);
   state_ = PREPARE_GC;
 #endif
   ASSERT(!FLAG_always_compact || !FLAG_never_compact);
 
@@ skipping 1326 matching lines @@
         on_dead_path = false;
         current->ClearNonLiveTransitions(real_prototype);
       }
       *HeapObject::RawField(current, Map::kPrototypeOffset) =
           real_prototype;
       current = reinterpret_cast<Map*>(next);
     }
   }
 }
 
-// -------------------------------------------------------------------------
-// Phase 2: Encode forwarding addresses.
-// When compacting, forwarding addresses for objects in old space and map
-// space are encoded in their map pointer word (along with an encoding of
-// their map pointers).
-//
-// The excact encoding is described in the comments for class MapWord in
-// objects.h.
-//
-// An address range [start, end) can have both live and non-live objects.
-// Maximal non-live regions are marked so they can be skipped on subsequent
-// sweeps of the heap.  A distinguished map-pointer encoding is used to mark
-// free regions of one-word size (in which case the next word is the start
-// of a live object).  A second distinguished map-pointer encoding is used
-// to mark free regions larger than one word, and the size of the free
-// region (including the first word) is written to the second word of the
-// region.
-//
-// Any valid map page offset must lie in the object area of the page, so map
-// page offsets less than Page::kObjectStartOffset are invalid.  We use a
-// pair of distinguished invalid map encodings (for single word and multiple
-// words) to indicate free regions in the page found during computation of
-// forwarding addresses and skipped over in subsequent sweeps.
-
-
-// Encode a free region, defined by the given start address and size, in the
-// first word or two of the region.
-void EncodeFreeRegion(Address free_start, int free_size) {
-  ASSERT(free_size >= kIntSize);
-  if (free_size == kIntSize) {
-    Memory::uint32_at(free_start) = MarkCompactCollector::kSingleFreeEncoding;
-  } else {
-    ASSERT(free_size >= 2 * kIntSize);
-    Memory::uint32_at(free_start) = MarkCompactCollector::kMultiFreeEncoding;
-    Memory::int_at(free_start + kIntSize) = free_size;
-  }
-
-#ifdef DEBUG
-  // Zap the body of the free region.
-  if (FLAG_enable_slow_asserts) {
-    for (int offset = 2 * kIntSize;
-         offset < free_size;
-         offset += kPointerSize) {
-      Memory::Address_at(free_start + offset) = kZapValue;
-    }
-  }
-#endif
-}
-
-
-// Try to promote all objects in new space.  Heap numbers and sequential
-// strings are promoted to the code space, large objects to large object space,
-// and all others to the old space.
-inline MaybeObject* MCAllocateFromNewSpace(HeapObject* object,
-                                           int object_size) {
-  MaybeObject* forwarded;
-  if (object_size > Heap::MaxObjectSizeInPagedSpace()) {
-    forwarded = Failure::Exception();
-  } else {
-    OldSpace* target_space = Heap::TargetSpace(object);
-    ASSERT(target_space == Heap::old_pointer_space() ||
-           target_space == Heap::old_data_space());
-    forwarded = target_space->MCAllocateRaw(object_size);
-  }
-  Object* result;
-  if (!forwarded->ToObject(&result)) {
-    result = Heap::new_space()->MCAllocateRaw(object_size)->ToObjectUnchecked();
-  }
-  return result;
-}
-
-
-// Allocation functions for the paged spaces call the space's MCAllocateRaw.
-MUST_USE_RESULT inline MaybeObject* MCAllocateFromOldPointerSpace(
-    HeapObject* ignore,
-    int object_size) {
-  return Heap::old_pointer_space()->MCAllocateRaw(object_size);
-}
-
-
-MUST_USE_RESULT inline MaybeObject* MCAllocateFromOldDataSpace(
-    HeapObject* ignore,
-    int object_size) {
-  return Heap::old_data_space()->MCAllocateRaw(object_size);
-}
-
-
-MUST_USE_RESULT inline MaybeObject* MCAllocateFromCodeSpace(
-    HeapObject* ignore,
-    int object_size) {
-  return Heap::code_space()->MCAllocateRaw(object_size);
-}
-
-
-MUST_USE_RESULT inline MaybeObject* MCAllocateFromMapSpace(
-    HeapObject* ignore,
-    int object_size) {
-  return Heap::map_space()->MCAllocateRaw(object_size);
-}
-
-
-MUST_USE_RESULT inline MaybeObject* MCAllocateFromCellSpace(HeapObject* ignore,
-                                                            int object_size) {
-  return Heap::cell_space()->MCAllocateRaw(object_size);
-}
-
-
-// The forwarding address is encoded at the same offset as the current
-// to-space object, but in from space.
-inline void EncodeForwardingAddressInNewSpace(HeapObject* old_object,
-                                              int object_size,
-                                              Object* new_object,
-                                              int* ignored) {
-  int offset =
-      Heap::new_space()->ToSpaceOffsetForAddress(old_object->address());
-  Memory::Address_at(Heap::new_space()->FromSpaceLow() + offset) =
-      HeapObject::cast(new_object)->address();
-}
-
-
-// The forwarding address is encoded in the map pointer of the object as an
-// offset (in terms of live bytes) from the address of the first live object
-// in the page.
-inline void EncodeForwardingAddressInPagedSpace(HeapObject* old_object,
-                                                int object_size,
-                                                Object* new_object,
-                                                int* offset) {
-  // Record the forwarding address of the first live object if necessary.
-  if (*offset == 0) {
-    Page::FromAddress(old_object->address())->mc_first_forwarded =
-        HeapObject::cast(new_object)->address();
-  }
-
-  MapWord encoding =
-      MapWord::EncodeAddress(old_object->map()->address(), *offset);
-  old_object->set_map_word(encoding);
-  *offset += object_size;
-  ASSERT(*offset <= Page::kObjectAreaSize);
-}
-
-
-// Most non-live objects are ignored.
-inline void IgnoreNonLiveObject(HeapObject* object) {}
-
-
-// Function template that, given a range of addresses (eg, a semispace or a
-// paged space page), iterates through the objects in the range to clear
-// mark bits and compute and encode forwarding addresses.  As a side effect,
-// maximal free chunks are marked so that they can be skipped on subsequent
-// sweeps.
-//
-// The template parameters are an allocation function, a forwarding address
-// encoding function, and a function to process non-live objects.
-template<MarkCompactCollector::AllocationFunction Alloc,
-         MarkCompactCollector::EncodingFunction Encode,
-         MarkCompactCollector::ProcessNonLiveFunction ProcessNonLive>
-inline void EncodeForwardingAddressesInRange(Address start,
-                                             Address end,
-                                             int* offset) {
-  // The start address of the current free region while sweeping the space.
-  // This address is set when a transition from live to non-live objects is
-  // encountered.  A value (an encoding of the 'next free region' pointer)
-  // is written to memory at this address when a transition from non-live to
-  // live objects is encountered.
-  Address free_start = NULL;
-
-  // A flag giving the state of the previously swept object.  Initially true
-  // to ensure that free_start is initialized to a proper address before
-  // trying to write to it.
-  bool is_prev_alive = true;
-
-  int object_size;  // Will be set on each iteration of the loop.
-  for (Address current = start; current < end; current += object_size) {
-    HeapObject* object = HeapObject::FromAddress(current);
-    if (object->IsMarked()) {
-      object->ClearMark();
-      MarkCompactCollector::tracer()->decrement_marked_count();
-      object_size = object->Size();
-
-      // Allocation cannot fail, because we are compacting the space.
-      Object* forwarded = Alloc(object, object_size)->ToObjectUnchecked();
-      Encode(object, object_size, forwarded, offset);
-
-#ifdef DEBUG
-      if (FLAG_gc_verbose) {
-        PrintF("forward %p -> %p.\n", object->address(),
-               HeapObject::cast(forwarded)->address());
-      }
-#endif
-      if (!is_prev_alive) {  // Transition from non-live to live.
-        EncodeFreeRegion(free_start, static_cast<int>(current - free_start));
-        is_prev_alive = true;
-      }
-    } else {  // Non-live object.
-      object_size = object->Size();
-      ProcessNonLive(object);
-      if (is_prev_alive) {  // Transition from live to non-live.
-        free_start = current;
-        is_prev_alive = false;
-      }
-    }
-  }
-
-  // If we ended on a free region, mark it.
-  if (!is_prev_alive) {
-    EncodeFreeRegion(free_start, static_cast<int>(end - free_start));
-  }
-}
-
-
-// Functions to encode the forwarding pointers in each compactable space.
-void MarkCompactCollector::EncodeForwardingAddressesInNewSpace() {
-  int ignored;
-  EncodeForwardingAddressesInRange<MCAllocateFromNewSpace,
-                                   EncodeForwardingAddressInNewSpace,
-                                   IgnoreNonLiveObject>(
-      Heap::new_space()->bottom(),
-      Heap::new_space()->top(),
-      &ignored);
-}
-
-
-template<MarkCompactCollector::AllocationFunction Alloc,
-         MarkCompactCollector::ProcessNonLiveFunction ProcessNonLive>
-void MarkCompactCollector::EncodeForwardingAddressesInPagedSpace(
-    PagedSpace* space) {
-  PageIterator it(space, PageIterator::PAGES_IN_USE);
-  while (it.has_next()) {
-    Page* p = it.next();
-
-    // The offset of each live object in the page from the first live object
-    // in the page.
-    int offset = 0;
-    EncodeForwardingAddressesInRange<Alloc,
-                                     EncodeForwardingAddressInPagedSpace,
-                                     ProcessNonLive>(
-        p->ObjectAreaStart(),
-        p->AllocationTop(),
-        &offset);
-  }
-}
-
 
 // We scavange new space simultaneously with sweeping. This is done in two
 // passes.
 // The first pass migrates all alive objects from one semispace to another or
 // promotes them to old space. Forwading address is written directly into
 // first word of object without any encoding. If object is dead we are writing
 // NULL as a forwarding address.
 // The second pass updates pointers to new space in all spaces. It is possible
 // to encounter pointers to dead objects during traversal of dirty regions we
 // should clear them to avoid encountering them during next dirty regions
@@ skipping 353 matching lines @@
     } else {
       ASSERT(new_allocation_top_page == first_empty_page);
     }
 #endif
 
     space->SetTop(new_allocation_top);
   }
 }
 
 
-void MarkCompactCollector::EncodeForwardingAddresses() {
-  ASSERT(state_ == ENCODE_FORWARDING_ADDRESSES);
-  // Objects in the active semispace of the young generation may be
-  // relocated to the inactive semispace (if not promoted).  Set the
-  // relocation info to the beginning of the inactive semispace.
-  Heap::new_space()->MCResetRelocationInfo();
-
-  // Compute the forwarding pointers in each space.
-  EncodeForwardingAddressesInPagedSpace<MCAllocateFromOldPointerSpace,
-                                        ReportDeleteIfNeeded>(
-      Heap::old_pointer_space());
-
-  EncodeForwardingAddressesInPagedSpace<MCAllocateFromOldDataSpace,
-                                        IgnoreNonLiveObject>(
-      Heap::old_data_space());
-
-  EncodeForwardingAddressesInPagedSpace<MCAllocateFromCodeSpace,
-                                        ReportDeleteIfNeeded>(
-      Heap::code_space());
-
-  EncodeForwardingAddressesInPagedSpace<MCAllocateFromCellSpace,
-                                        IgnoreNonLiveObject>(
-      Heap::cell_space());
-
-
-  // Compute new space next to last after the old and code spaces have been
-  // compacted.  Objects in new space can be promoted to old or code space.
-  EncodeForwardingAddressesInNewSpace();
-
-  // Compute map space last because computing forwarding addresses
-  // overwrites non-live objects.  Objects in the other spaces rely on
-  // non-live map pointers to get the sizes of non-live objects.
-  EncodeForwardingAddressesInPagedSpace<MCAllocateFromMapSpace,
-                                        IgnoreNonLiveObject>(
-      Heap::map_space());
-
-  // Write relocation info to the top page, so we can use it later.  This is
-  // done after promoting objects from the new space so we get the correct
-  // allocation top.
-  Heap::old_pointer_space()->MCWriteRelocationInfoToPage();
-  Heap::old_data_space()->MCWriteRelocationInfoToPage();
-  Heap::code_space()->MCWriteRelocationInfoToPage();
-  Heap::map_space()->MCWriteRelocationInfoToPage();
-  Heap::cell_space()->MCWriteRelocationInfoToPage();
-}
-
-
-class MapIterator : public HeapObjectIterator {
- public:
-  MapIterator() : HeapObjectIterator(Heap::map_space(), &SizeCallback) { }
-
-  explicit MapIterator(Address start)
-      : HeapObjectIterator(Heap::map_space(), start, &SizeCallback) { }
-
- private:
-  static int SizeCallback(HeapObject* unused) {
-    USE(unused);
-    return Map::kSize;
-  }
-};
-
-
-class MapCompact {
- public:
-  explicit MapCompact(int live_maps)
-    : live_maps_(live_maps),
-      to_evacuate_start_(Heap::map_space()->TopAfterCompaction(live_maps)),
-      map_to_evacuate_it_(to_evacuate_start_),
-      first_map_to_evacuate_(
-          reinterpret_cast<Map*>(HeapObject::FromAddress(to_evacuate_start_))) {
-  }
-
-  void CompactMaps() {
-    // As we know the number of maps to evacuate beforehand,
-    // we stop then there is no more vacant maps.
-    for (Map* next_vacant_map = NextVacantMap();
-         next_vacant_map;
-         next_vacant_map = NextVacantMap()) {
-      EvacuateMap(next_vacant_map, NextMapToEvacuate());
-    }
-
-#ifdef DEBUG
-    CheckNoMapsToEvacuate();
-#endif
-  }
-
-  void UpdateMapPointersInRoots() {
-    Heap::IterateRoots(&map_updating_visitor_, VISIT_ONLY_STRONG);
-    GlobalHandles::IterateWeakRoots(&map_updating_visitor_);
-  }
-
-  void UpdateMapPointersInPagedSpace(PagedSpace* space) {
-    ASSERT(space != Heap::map_space());
-
-    PageIterator it(space, PageIterator::PAGES_IN_USE);
-    while (it.has_next()) {
-      Page* p = it.next();
-      UpdateMapPointersInRange(p->ObjectAreaStart(), p->AllocationTop());
-    }
-  }
-
-  void UpdateMapPointersInNewSpace() {
-    NewSpace* space = Heap::new_space();
-    UpdateMapPointersInRange(space->bottom(), space->top());
-  }
-
-  void UpdateMapPointersInLargeObjectSpace() {
-    LargeObjectIterator it(Heap::lo_space());
-    for (HeapObject* obj = it.next(); obj != NULL; obj = it.next())
-      UpdateMapPointersInObject(obj);
-  }
-
-  void Finish() {
-    Heap::map_space()->FinishCompaction(to_evacuate_start_, live_maps_);
-  }
-
- private:
-  int live_maps_;
-  Address to_evacuate_start_;
-  MapIterator vacant_map_it_;
-  MapIterator map_to_evacuate_it_;
-  Map* first_map_to_evacuate_;
-
-  // Helper class for updating map pointers in HeapObjects.
-  class MapUpdatingVisitor: public ObjectVisitor {
-  public:
-    void VisitPointer(Object** p) {
-      UpdateMapPointer(p);
-    }
-
-    void VisitPointers(Object** start, Object** end) {
-      for (Object** p = start; p < end; p++) UpdateMapPointer(p);
-    }
-
-  private:
-    void UpdateMapPointer(Object** p) {
-      if (!(*p)->IsHeapObject()) return;
-      HeapObject* old_map = reinterpret_cast<HeapObject*>(*p);
-
-      // Moved maps are tagged with overflowed map word.  They are the only
-      // objects those map word is overflowed as marking is already complete.
-      MapWord map_word = old_map->map_word();
-      if (!map_word.IsOverflowed()) return;
-
-      *p = GetForwardedMap(map_word);
-    }
-  };
-
-  static MapUpdatingVisitor map_updating_visitor_;
-
-  static Map* NextMap(MapIterator* it, HeapObject* last, bool live) {
-    while (true) {
-      HeapObject* next = it->next();
-      ASSERT(next != NULL);
-      if (next == last)
-        return NULL;
-      ASSERT(!next->IsOverflowed());
-      ASSERT(!next->IsMarked());
-      ASSERT(next->IsMap() || FreeListNode::IsFreeListNode(next));
-      if (next->IsMap() == live)
-        return reinterpret_cast<Map*>(next);
-    }
-  }
-
-  Map* NextVacantMap() {
-    Map* map = NextMap(&vacant_map_it_, first_map_to_evacuate_, false);
-    ASSERT(map == NULL || FreeListNode::IsFreeListNode(map));
-    return map;
-  }
-
-  Map* NextMapToEvacuate() {
-    Map* map = NextMap(&map_to_evacuate_it_, NULL, true);
-    ASSERT(map != NULL);
-    ASSERT(map->IsMap());
-    return map;
-  }
-
-  static void EvacuateMap(Map* vacant_map, Map* map_to_evacuate) {
-    ASSERT(FreeListNode::IsFreeListNode(vacant_map));
-    ASSERT(map_to_evacuate->IsMap());
-
-    ASSERT(Map::kSize % 4 == 0);
-
-    Heap::CopyBlockToOldSpaceAndUpdateRegionMarks(vacant_map->address(),
-                                                  map_to_evacuate->address(),
-                                                  Map::kSize);
-
-    ASSERT(vacant_map->IsMap());  // Due to memcpy above.
-
-    MapWord forwarding_map_word = MapWord::FromMap(vacant_map);
-    forwarding_map_word.SetOverflow();
-    map_to_evacuate->set_map_word(forwarding_map_word);
-
-    ASSERT(map_to_evacuate->map_word().IsOverflowed());
-    ASSERT(GetForwardedMap(map_to_evacuate->map_word()) == vacant_map);
-  }
-
-  static Map* GetForwardedMap(MapWord map_word) {
-    ASSERT(map_word.IsOverflowed());
-    map_word.ClearOverflow();
-    Map* new_map = map_word.ToMap();
-    ASSERT_MAP_ALIGNED(new_map->address());
-    return new_map;
-  }
-
-  static int UpdateMapPointersInObject(HeapObject* obj) {
-    ASSERT(!obj->IsMarked());
-    Map* map = obj->map();
-    ASSERT(Heap::map_space()->Contains(map));
-    MapWord map_word = map->map_word();
-    ASSERT(!map_word.IsMarked());
-    if (map_word.IsOverflowed()) {
-      Map* new_map = GetForwardedMap(map_word);
-      ASSERT(Heap::map_space()->Contains(new_map));
-      obj->set_map(new_map);
-
-#ifdef DEBUG
-      if (FLAG_gc_verbose) {
-        PrintF("update %p : %p -> %p\n",
-               obj->address(),
-               reinterpret_cast<void*>(map),
-               reinterpret_cast<void*>(new_map));
-      }
-#endif
-    }
-
-    int size = obj->SizeFromMap(map);
-    obj->IterateBody(map->instance_type(), size, &map_updating_visitor_);
-    return size;
-  }
-
-  static void UpdateMapPointersInRange(Address start, Address end) {
-    HeapObject* object;
-    int size;
-    for (Address current = start; current < end; current += size) {
-      object = HeapObject::FromAddress(current);
-      size = UpdateMapPointersInObject(object);
-      ASSERT(size > 0);
-    }
-  }
-
-#ifdef DEBUG
-  void CheckNoMapsToEvacuate() {
-    if (!FLAG_enable_slow_asserts)
-      return;
-
-    for (HeapObject* obj = map_to_evacuate_it_.next();
-         obj != NULL; obj = map_to_evacuate_it_.next())
-      ASSERT(FreeListNode::IsFreeListNode(obj));
-  }
-#endif
-};
-
-MapCompact::MapUpdatingVisitor MapCompact::map_updating_visitor_;
-
-
 void MarkCompactCollector::SweepSpaces() {
   GCTracer::Scope gc_scope(tracer_, GCTracer::Scope::MC_SWEEP);
 
   ASSERT(state_ == SWEEP_SPACES);
   ASSERT(!IsCompacting());
   // Noncompacting collections simply sweep the spaces to clear the mark
   // bits and free the nonlive blocks (for old and map spaces).  We sweep
   // the map space last because freeing non-live maps overwrites them and
   // the other spaces rely on possibly non-live maps to get the sizes for
   // non-live objects.
   SweepSpace(Heap::old_pointer_space());
   SweepSpace(Heap::old_data_space());
   SweepSpace(Heap::code_space());
   SweepSpace(Heap::cell_space());
   { GCTracer::Scope gc_scope(tracer_, GCTracer::Scope::MC_SWEEP_NEWSPACE);
     SweepNewSpace(Heap::new_space());
   }
   SweepSpace(Heap::map_space());
 
   Heap::IterateDirtyRegions(Heap::map_space(),
                             &Heap::IteratePointersInDirtyMapsRegion,
                             &UpdatePointerToNewGen,
                             Heap::WATERMARK_SHOULD_BE_VALID);
 
-  intptr_t live_maps_size = Heap::map_space()->Size();
-  int live_maps = static_cast<int>(live_maps_size / Map::kSize);
-  ASSERT(live_map_objects_size_ == live_maps_size);
-
-  if (Heap::map_space()->NeedsCompaction(live_maps)) {
-    MapCompact map_compact(live_maps);
-
-    map_compact.CompactMaps();
-    map_compact.UpdateMapPointersInRoots();
-
-    PagedSpaces spaces;
-    for (PagedSpace* space = spaces.next();
-         space != NULL; space = spaces.next()) {
-      if (space == Heap::map_space()) continue;
-      map_compact.UpdateMapPointersInPagedSpace(space);
-    }
-    map_compact.UpdateMapPointersInNewSpace();
-    map_compact.UpdateMapPointersInLargeObjectSpace();
-
-    map_compact.Finish();
-  }
+  ASSERT(live_map_objects_size_ == Heap::map_space()->Size());
 }
 
 
 // Iterate the live objects in a range of addresses (eg, a page or a
 // semispace).  The live regions of the range have been linked into a list.
 // The first live region is [first_live_start, first_live_end), and the last
 // address in the range is top.  The callback function is used to get the
 // size of each live object.
 int MarkCompactCollector::IterateLiveObjectsInRange(
     Address start,
@@ skipping 32 matching lines @@
   while (it.has_next()) {
     Page* p = it.next();
     total += IterateLiveObjectsInRange(p->ObjectAreaStart(),
                                        p->AllocationTop(),
                                        size_f);
   }
   return total;
 }
 
 
-// -------------------------------------------------------------------------
-// Phase 3: Update pointers
-
-// Helper class for updating pointers in HeapObjects.
-class UpdatingVisitor: public ObjectVisitor {
- public:
-  void VisitPointer(Object** p) {
-    UpdatePointer(p);
-  }
-
-  void VisitPointers(Object** start, Object** end) {
-    // Mark all HeapObject pointers in [start, end)
-    for (Object** p = start; p < end; p++) UpdatePointer(p);
-  }
-
-  void VisitCodeTarget(RelocInfo* rinfo) {
-    ASSERT(RelocInfo::IsCodeTarget(rinfo->rmode()));
-    Object* target = Code::GetCodeFromTargetAddress(rinfo->target_address());
-    VisitPointer(&target);
-    rinfo->set_target_address(
-        reinterpret_cast<Code*>(target)->instruction_start());
-  }
-
-  void VisitDebugTarget(RelocInfo* rinfo) {
-    ASSERT((RelocInfo::IsJSReturn(rinfo->rmode()) &&
-            rinfo->IsPatchedReturnSequence()) ||
-           (RelocInfo::IsDebugBreakSlot(rinfo->rmode()) &&
-            rinfo->IsPatchedDebugBreakSlotSequence()));
-    Object* target = Code::GetCodeFromTargetAddress(rinfo->call_address());
-    VisitPointer(&target);
-    rinfo->set_call_address(
-        reinterpret_cast<Code*>(target)->instruction_start());
-  }
-
- private:
-  void UpdatePointer(Object** p) {
-    if (!(*p)->IsHeapObject()) return;
-
-    HeapObject* obj = HeapObject::cast(*p);
-    Address old_addr = obj->address();
-    Address new_addr;
-    ASSERT(!Heap::InFromSpace(obj));
-
-    if (Heap::new_space()->Contains(obj)) {
-      Address forwarding_pointer_addr =
-          Heap::new_space()->FromSpaceLow() +
-          Heap::new_space()->ToSpaceOffsetForAddress(old_addr);
-      new_addr = Memory::Address_at(forwarding_pointer_addr);
-
-#ifdef DEBUG
-      ASSERT(Heap::old_pointer_space()->Contains(new_addr) ||
-             Heap::old_data_space()->Contains(new_addr) ||
-             Heap::new_space()->FromSpaceContains(new_addr) ||
-             Heap::lo_space()->Contains(HeapObject::FromAddress(new_addr)));
-
-      if (Heap::new_space()->FromSpaceContains(new_addr)) {
-        ASSERT(Heap::new_space()->FromSpaceOffsetForAddress(new_addr) <=
-               Heap::new_space()->ToSpaceOffsetForAddress(old_addr));
-      }
-#endif
-
-    } else if (Heap::lo_space()->Contains(obj)) {
-      // Don't move objects in the large object space.
-      return;
-
-    } else {
-#ifdef DEBUG
-      PagedSpaces spaces;
-      PagedSpace* original_space = spaces.next();
-      while (original_space != NULL) {
-        if (original_space->Contains(obj)) break;
-        original_space = spaces.next();
-      }
-      ASSERT(original_space != NULL);
-#endif
-      new_addr = MarkCompactCollector::GetForwardingAddressInOldSpace(obj);
-      ASSERT(original_space->Contains(new_addr));
-      ASSERT(original_space->MCSpaceOffsetForAddress(new_addr) <=
-             original_space->MCSpaceOffsetForAddress(old_addr));
-    }
-
-    *p = HeapObject::FromAddress(new_addr);
-
-#ifdef DEBUG
-    if (FLAG_gc_verbose) {
-      PrintF("update %p : %p -> %p\n",
-             reinterpret_cast<Address>(p), old_addr, new_addr);
-    }
-#endif
-  }
-};
-
-
-void MarkCompactCollector::UpdatePointers() {
-#ifdef DEBUG
-  ASSERT(state_ == ENCODE_FORWARDING_ADDRESSES);
-  state_ = UPDATE_POINTERS;
-#endif
-  UpdatingVisitor updating_visitor;
-  Heap::IterateRoots(&updating_visitor, VISIT_ONLY_STRONG);
-  GlobalHandles::IterateWeakRoots(&updating_visitor);
-
-  // Update the pointer to the head of the weak list of global contexts.
-  updating_visitor.VisitPointer(&Heap::global_contexts_list_);
-
-  int live_maps_size = IterateLiveObjects(Heap::map_space(),
-                                          &UpdatePointersInOldObject);
-  int live_pointer_olds_size = IterateLiveObjects(Heap::old_pointer_space(),
-                                                  &UpdatePointersInOldObject);
-  int live_data_olds_size = IterateLiveObjects(Heap::old_data_space(),
-                                               &UpdatePointersInOldObject);
-  int live_codes_size = IterateLiveObjects(Heap::code_space(),
-                                           &UpdatePointersInOldObject);
-  int live_cells_size = IterateLiveObjects(Heap::cell_space(),
-                                           &UpdatePointersInOldObject);
-  int live_news_size = IterateLiveObjects(Heap::new_space(),
-                                          &UpdatePointersInNewObject);
-
-  // Large objects do not move, the map word can be updated directly.
-  LargeObjectIterator it(Heap::lo_space());
-  for (HeapObject* obj = it.next(); obj != NULL; obj = it.next()) {
-    UpdatePointersInNewObject(obj);
-  }
-
-  USE(live_maps_size);
-  USE(live_pointer_olds_size);
-  USE(live_data_olds_size);
-  USE(live_codes_size);
-  USE(live_cells_size);
-  USE(live_news_size);
-  ASSERT(live_maps_size == live_map_objects_size_);
-  ASSERT(live_data_olds_size == live_old_data_objects_size_);
-  ASSERT(live_pointer_olds_size == live_old_pointer_objects_size_);
-  ASSERT(live_codes_size == live_code_objects_size_);
-  ASSERT(live_cells_size == live_cell_objects_size_);
-  ASSERT(live_news_size == live_young_objects_size_);
-}
-
-
-int MarkCompactCollector::UpdatePointersInNewObject(HeapObject* obj) {
-  // Keep old map pointers
-  Map* old_map = obj->map();
-  ASSERT(old_map->IsHeapObject());
-
-  Address forwarded = GetForwardingAddressInOldSpace(old_map);
-
-  ASSERT(Heap::map_space()->Contains(old_map));
-  ASSERT(Heap::map_space()->Contains(forwarded));
-#ifdef DEBUG
-  if (FLAG_gc_verbose) {
-    PrintF("update %p : %p -> %p\n", obj->address(), old_map->address(),
-           forwarded);
-  }
-#endif
-  // Update the map pointer.
-  obj->set_map(reinterpret_cast<Map*>(HeapObject::FromAddress(forwarded)));
-
-  // We have to compute the object size relying on the old map because
-  // map objects are not relocated yet.
-  int obj_size = obj->SizeFromMap(old_map);
-
-  // Update pointers in the object body.
-  UpdatingVisitor updating_visitor;
-  obj->IterateBody(old_map->instance_type(), obj_size, &updating_visitor);
-  return obj_size;
-}
-
-
-int MarkCompactCollector::UpdatePointersInOldObject(HeapObject* obj) {
-  // Decode the map pointer.
-  MapWord encoding = obj->map_word();
-  Address map_addr = encoding.DecodeMapAddress(Heap::map_space());
-  ASSERT(Heap::map_space()->Contains(HeapObject::FromAddress(map_addr)));
-
-  // At this point, the first word of map_addr is also encoded, cannot
-  // cast it to Map* using Map::cast.
-  Map* map = reinterpret_cast<Map*>(HeapObject::FromAddress(map_addr));
-  int obj_size = obj->SizeFromMap(map);
-  InstanceType type = map->instance_type();
-
-  // Update map pointer.
-  Address new_map_addr = GetForwardingAddressInOldSpace(map);
-  int offset = encoding.DecodeOffset();
-  obj->set_map_word(MapWord::EncodeAddress(new_map_addr, offset));
-
-#ifdef DEBUG
-  if (FLAG_gc_verbose) {
-    PrintF("update %p : %p -> %p\n", obj->address(),
-           map_addr, new_map_addr);
-  }
-#endif
-
-  // Update pointers in the object body.
-  UpdatingVisitor updating_visitor;
-  obj->IterateBody(type, obj_size, &updating_visitor);
-  return obj_size;
-}
-
-
-Address MarkCompactCollector::GetForwardingAddressInOldSpace(HeapObject* obj) {
-  // Object should either in old or map space.
-  MapWord encoding = obj->map_word();
-
-  // Offset to the first live object's forwarding address.
-  int offset = encoding.DecodeOffset();
-  Address obj_addr = obj->address();
-
-  // Find the first live object's forwarding address.
-  Page* p = Page::FromAddress(obj_addr);
-  Address first_forwarded = p->mc_first_forwarded;
-
-  // Page start address of forwarded address.
-  Page* forwarded_page = Page::FromAddress(first_forwarded);
-  int forwarded_offset = forwarded_page->Offset(first_forwarded);
-
-  // Find end of allocation in the page of first_forwarded.
-  int mc_top_offset = forwarded_page->AllocationWatermarkOffset();
-
-  // Check if current object's forward pointer is in the same page
-  // as the first live object's forwarding pointer
-  if (forwarded_offset + offset < mc_top_offset) {
-    // In the same page.
-    return first_forwarded + offset;
-  }
-
-  // Must be in the next page, NOTE: this may cross chunks.
-  Page* next_page = forwarded_page->next_page();
-  ASSERT(next_page->is_valid());
-
-  offset -= (mc_top_offset - forwarded_offset);
-  offset += Page::kObjectStartOffset;
-
-  ASSERT_PAGE_OFFSET(offset);
-  ASSERT(next_page->OffsetToAddress(offset) < next_page->AllocationTop());
-
-  return next_page->OffsetToAddress(offset);
-}
-
-
-// -------------------------------------------------------------------------
-// Phase 4: Relocate objects
-
-void MarkCompactCollector::RelocateObjects() {
-#ifdef DEBUG
-  ASSERT(state_ == UPDATE_POINTERS);
-  state_ = RELOCATE_OBJECTS;
-#endif
-  // Relocates objects, always relocate map objects first. Relocating
-  // objects in other space relies on map objects to get object size.
-  int live_maps_size = IterateLiveObjects(Heap::map_space(),
-                                          &RelocateMapObject);
-  int live_pointer_olds_size = IterateLiveObjects(Heap::old_pointer_space(),
-                                                  &RelocateOldPointerObject);
-  int live_data_olds_size = IterateLiveObjects(Heap::old_data_space(),
-                                               &RelocateOldDataObject);
-  int live_codes_size = IterateLiveObjects(Heap::code_space(),
-                                           &RelocateCodeObject);
-  int live_cells_size = IterateLiveObjects(Heap::cell_space(),
-                                           &RelocateCellObject);
-  int live_news_size = IterateLiveObjects(Heap::new_space(),
-                                          &RelocateNewObject);
-
-  USE(live_maps_size);
-  USE(live_pointer_olds_size);
-  USE(live_data_olds_size);
-  USE(live_codes_size);
-  USE(live_cells_size);
-  USE(live_news_size);
-  ASSERT(live_maps_size == live_map_objects_size_);
-  ASSERT(live_data_olds_size == live_old_data_objects_size_);
-  ASSERT(live_pointer_olds_size == live_old_pointer_objects_size_);
-  ASSERT(live_codes_size == live_code_objects_size_);
-  ASSERT(live_cells_size == live_cell_objects_size_);
-  ASSERT(live_news_size == live_young_objects_size_);
-
-  // Flip from and to spaces
-  Heap::new_space()->Flip();
-
-  Heap::new_space()->MCCommitRelocationInfo();
-
-  // Set age_mark to bottom in to space
-  Address mark = Heap::new_space()->bottom();
-  Heap::new_space()->set_age_mark(mark);
-
-  PagedSpaces spaces;
-  for (PagedSpace* space = spaces.next(); space != NULL; space = spaces.next())
-    space->MCCommitRelocationInfo();
-
-  Heap::CheckNewSpaceExpansionCriteria();
-  Heap::IncrementYoungSurvivorsCounter(live_news_size);
-}
-
-
-int MarkCompactCollector::RelocateMapObject(HeapObject* obj) {
-  // Recover map pointer.
-  MapWord encoding = obj->map_word();
-  Address map_addr = encoding.DecodeMapAddress(Heap::map_space());
-  ASSERT(Heap::map_space()->Contains(HeapObject::FromAddress(map_addr)));
-
-  // Get forwarding address before resetting map pointer
-  Address new_addr = GetForwardingAddressInOldSpace(obj);
-
-  // Reset map pointer.  The meta map object may not be copied yet so
-  // Map::cast does not yet work.
-  obj->set_map(reinterpret_cast<Map*>(HeapObject::FromAddress(map_addr)));
-
-  Address old_addr = obj->address();
-
-  if (new_addr != old_addr) {
-    // Move contents.
-    Heap::MoveBlockToOldSpaceAndUpdateRegionMarks(new_addr,
-                                                  old_addr,
-                                                  Map::kSize);
-  }
-
-#ifdef DEBUG
-  if (FLAG_gc_verbose) {
-    PrintF("relocate %p -> %p\n", old_addr, new_addr);
-  }
-#endif
-
-  return Map::kSize;
-}
-
-
-static inline int RestoreMap(HeapObject* obj,
-                             PagedSpace* space,
-                             Address new_addr,
-                             Address map_addr) {
-  // This must be a non-map object, and the function relies on the
-  // assumption that the Map space is compacted before the other paged
-  // spaces (see RelocateObjects).
-
-  // Reset map pointer.
-  obj->set_map(Map::cast(HeapObject::FromAddress(map_addr)));
-
-  int obj_size = obj->Size();
-  ASSERT_OBJECT_SIZE(obj_size);
-
-  ASSERT(space->MCSpaceOffsetForAddress(new_addr) <=
-         space->MCSpaceOffsetForAddress(obj->address()));
-
-#ifdef DEBUG
-  if (FLAG_gc_verbose) {
-    PrintF("relocate %p -> %p\n", obj->address(), new_addr);
-  }
-#endif
-
-  return obj_size;
-}
-
-
-int MarkCompactCollector::RelocateOldNonCodeObject(HeapObject* obj,
-                                                   PagedSpace* space) {
-  // Recover map pointer.
-  MapWord encoding = obj->map_word();
-  Address map_addr = encoding.DecodeMapAddress(Heap::map_space());
-  ASSERT(Heap::map_space()->Contains(map_addr));
-
-  // Get forwarding address before resetting map pointer.
-  Address new_addr = GetForwardingAddressInOldSpace(obj);
-
-  // Reset the map pointer.
-  int obj_size = RestoreMap(obj, space, new_addr, map_addr);
-
-  Address old_addr = obj->address();
-
-  if (new_addr != old_addr) {
-    // Move contents.
-    if (space == Heap::old_data_space()) {
-      Heap::MoveBlock(new_addr, old_addr, obj_size);
-    } else {
-      Heap::MoveBlockToOldSpaceAndUpdateRegionMarks(new_addr,
-                                                    old_addr,
-                                                    obj_size);
-    }
-  }
-
-  ASSERT(!HeapObject::FromAddress(new_addr)->IsCode());
-
-  HeapObject* copied_to = HeapObject::FromAddress(new_addr);
-  if (copied_to->IsJSFunction()) {
-    PROFILE(FunctionMoveEvent(old_addr, new_addr));
-    PROFILE(FunctionCreateEventFromMove(JSFunction::cast(copied_to)));
-  }
-  HEAP_PROFILE(ObjectMoveEvent(old_addr, new_addr));
-
-  return obj_size;
-}
-
-
-int MarkCompactCollector::RelocateOldPointerObject(HeapObject* obj) {
-  return RelocateOldNonCodeObject(obj, Heap::old_pointer_space());
-}
-
-
-int MarkCompactCollector::RelocateOldDataObject(HeapObject* obj) {
-  return RelocateOldNonCodeObject(obj, Heap::old_data_space());
-}
-
-
-int MarkCompactCollector::RelocateCellObject(HeapObject* obj) {
-  return RelocateOldNonCodeObject(obj, Heap::cell_space());
-}
-
-
-int MarkCompactCollector::RelocateCodeObject(HeapObject* obj) {
-  // Recover map pointer.
-  MapWord encoding = obj->map_word();
-  Address map_addr = encoding.DecodeMapAddress(Heap::map_space());
-  ASSERT(Heap::map_space()->Contains(HeapObject::FromAddress(map_addr)));
-
-  // Get forwarding address before resetting map pointer
-  Address new_addr = GetForwardingAddressInOldSpace(obj);
-
-  // Reset the map pointer.
-  int obj_size = RestoreMap(obj, Heap::code_space(), new_addr, map_addr);
-
-  Address old_addr = obj->address();
-
-  if (new_addr != old_addr) {
-    // Move contents.
-    Heap::MoveBlock(new_addr, old_addr, obj_size);
-  }
-
-  HeapObject* copied_to = HeapObject::FromAddress(new_addr);
-  if (copied_to->IsCode()) {
-    // May also update inline cache target.
-    Code::cast(copied_to)->Relocate(new_addr - old_addr);
-    // Notify the logger that compiled code has moved.
-    PROFILE(CodeMoveEvent(old_addr, new_addr));
-  }
-  HEAP_PROFILE(ObjectMoveEvent(old_addr, new_addr));
-
-  return obj_size;
-}
-
-
-int MarkCompactCollector::RelocateNewObject(HeapObject* obj) {
-  int obj_size = obj->Size();
-
-  // Get forwarding address
-  Address old_addr = obj->address();
-  int offset = Heap::new_space()->ToSpaceOffsetForAddress(old_addr);
-
-  Address new_addr =
-    Memory::Address_at(Heap::new_space()->FromSpaceLow() + offset);
-
-#ifdef DEBUG
-  if (Heap::new_space()->FromSpaceContains(new_addr)) {
-    ASSERT(Heap::new_space()->FromSpaceOffsetForAddress(new_addr) <=
-           Heap::new_space()->ToSpaceOffsetForAddress(old_addr));
-  } else {
-    ASSERT(Heap::TargetSpace(obj) == Heap::old_pointer_space() ||
-           Heap::TargetSpace(obj) == Heap::old_data_space());
-  }
-#endif
-
-  // New and old addresses cannot overlap.
-  if (Heap::InNewSpace(HeapObject::FromAddress(new_addr))) {
-    Heap::CopyBlock(new_addr, old_addr, obj_size);
-  } else {
-    Heap::CopyBlockToOldSpaceAndUpdateRegionMarks(new_addr,
-                                                  old_addr,
-                                                  obj_size);
-  }
-
-#ifdef DEBUG
-  if (FLAG_gc_verbose) {
-    PrintF("relocate %p -> %p\n", old_addr, new_addr);
-  }
-#endif
-
-  HeapObject* copied_to = HeapObject::FromAddress(new_addr);
-  if (copied_to->IsJSFunction()) {
-    PROFILE(FunctionMoveEvent(old_addr, new_addr));
-    PROFILE(FunctionCreateEventFromMove(JSFunction::cast(copied_to)));
-  }
-  HEAP_PROFILE(ObjectMoveEvent(old_addr, new_addr));
-
-  return obj_size;
-}
-
-
 void MarkCompactCollector::ReportDeleteIfNeeded(HeapObject* obj) {
 #ifdef ENABLE_LOGGING_AND_PROFILING
   if (obj->IsCode()) {
     PROFILE(CodeDeleteEvent(obj->address()));
   } else if (obj->IsJSFunction()) {
     PROFILE(FunctionDeleteEvent(obj->address()));
   }
 #endif
 }
 
 
 int MarkCompactCollector::SizeOfMarkedObject(HeapObject* obj) {
   MapWord map_word = obj->map_word();
   map_word.ClearMark();
   return obj->SizeFromMap(map_word.ToMap());
 }
 
 
 void MarkCompactCollector::Initialize() {
   StaticPointersToNewGenUpdatingVisitor::Initialize();
   StaticMarkingVisitor::Initialize();
 }
 
 
 } }  // namespace v8::internal