Added allocation folding support for old space allocations.

src/hydrogen-instructions.cc

Index: src/hydrogen-instructions.cc
diff --git a/src/hydrogen-instructions.cc b/src/hydrogen-instructions.cc
index 28511f714208f6fcc9eb84a4d1812723f09ba01b..3ba611aab906d838ca22e3d226905b1f589e977e 100644
--- a/src/hydrogen-instructions.cc
+++ b/src/hydrogen-instructions.cc
@@ -3306,6 +3306,7 @@ Representation HUnaryMathOperation::RepresentationFromInputs() {
 void HAllocate::HandleSideEffectDominator(GVNFlag side_effect,
                                           HValue* dominator) {
   ASSERT(side_effect == kChangesNewSpacePromotion);
+  Zone* zone = block()->zone();
   if (!FLAG_use_allocation_folding) return;
 
   // Try to fold allocations together with their dominating allocations.
@@ -3317,22 +3318,34 @@ void HAllocate::HandleSideEffectDominator(GVNFlag side_effect,
     return;
   }
 
-  HAllocate* dominator_allocate_instr = HAllocate::cast(dominator);
-  HValue* dominator_size = dominator_allocate_instr->size();
+  HAllocate* dominator_allocate = HAllocate::cast(dominator);
+  HValue* dominator_size = dominator_allocate->size();
   HValue* current_size = size();
-  // We can just fold allocations that are guaranteed in new space.
+
   // TODO(hpayer): Add support for non-constant allocation in dominator.
-  if (!IsNewSpaceAllocation() || !current_size->IsInteger32Constant() ||
-      !dominator_allocate_instr->IsNewSpaceAllocation() ||
+  if (!current_size->IsInteger32Constant() ||
       !dominator_size->IsInteger32Constant()) {
     if (FLAG_trace_allocation_folding) {
-      PrintF("#%d (%s) cannot fold into #%d (%s)\n",
+      PrintF("#%d (%s) cannot fold into #%d (%s), dynamic allocation size\n",
           id(), Mnemonic(), dominator->id(), dominator->Mnemonic());
     }
     return;
   }
 
+  dominator_allocate = GetFoldableDominator(dominator_allocate);
+  if (dominator_allocate == NULL) {
+    return;
+  }
+
+  ASSERT((IsNewSpaceAllocation() &&
+         dominator_allocate->IsNewSpaceAllocation()) ||
+         (IsOldDataSpaceAllocation() &&
+         dominator_allocate->IsOldDataSpaceAllocation()) ||
+         (IsOldPointerSpaceAllocation() &&
+         dominator_allocate->IsOldPointerSpaceAllocation()));
+
   // First update the size of the dominator allocate instruction.
+  dominator_size = dominator_allocate->size();
   int32_t dominator_size_constant =
       HConstant::cast(dominator_size)->GetInteger32Constant();
   int32_t current_size_constant =
@@ -3340,8 +3353,8 @@ void HAllocate::HandleSideEffectDominator(GVNFlag side_effect,
   int32_t new_dominator_size = dominator_size_constant + current_size_constant;
 
   if (MustAllocateDoubleAligned()) {
-    if (!dominator_allocate_instr->MustAllocateDoubleAligned()) {
-      dominator_allocate_instr->MakeDoubleAligned();
+    if (!dominator_allocate->MustAllocateDoubleAligned()) {
+      dominator_allocate->MakeDoubleAligned();
     }
     if ((dominator_size_constant & kDoubleAlignmentMask) != 0) {
       dominator_size_constant += kDoubleSize / 2;
@@ -3352,21 +3365,19 @@ void HAllocate::HandleSideEffectDominator(GVNFlag side_effect,
   if (new_dominator_size > Page::kMaxNonCodeHeapObjectSize) {
     if (FLAG_trace_allocation_folding) {
       PrintF("#%d (%s) cannot fold into #%d (%s) due to size: %d\n",
-          id(), Mnemonic(), dominator->id(), dominator->Mnemonic(),
-          new_dominator_size);
+          id(), Mnemonic(), dominator_allocate->id(),
+          dominator_allocate->Mnemonic(), new_dominator_size);
     }
     return;
   }
-  HBasicBlock* block = dominator->block();
-  Zone* zone = block->zone();
-  HInstruction* new_dominator_size_constant =
-      HConstant::New(zone, context(), new_dominator_size);
-  new_dominator_size_constant->InsertBefore(dominator_allocate_instr);
-  dominator_allocate_instr->UpdateSize(new_dominator_size_constant);
+
+  HInstruction* new_dominator_size_constant = HConstant::CreateAndInsertBefore(
+      zone, context(), new_dominator_size, dominator_allocate);
+  dominator_allocate->UpdateSize(new_dominator_size_constant);
 
 #ifdef VERIFY_HEAP
-  if (FLAG_verify_heap) {
-    dominator_allocate_instr->MakePrefillWithFiller();
+  if (FLAG_verify_heap && dominator_allocate->IsNewSpaceAllocation()) {
+    dominator_allocate->MakePrefillWithFiller();
   }
 #endif
 
@@ -3374,15 +3385,121 @@ void HAllocate::HandleSideEffectDominator(GVNFlag side_effect,
   HInstruction* dominated_allocate_instr =
       HInnerAllocatedObject::New(zone,
                                  context(),
-                                 dominator_allocate_instr,
+                                 dominator_allocate,
                                  dominator_size_constant,
                                  type());
   dominated_allocate_instr->InsertBefore(this);
   DeleteAndReplaceWith(dominated_allocate_instr);
   if (FLAG_trace_allocation_folding) {
     PrintF("#%d (%s) folded into #%d (%s)\n",
-        id(), Mnemonic(), dominator->id(), dominator->Mnemonic());
+        id(), Mnemonic(), dominator_allocate->id(),
+        dominator_allocate->Mnemonic());
+  }
+}
+
+
+HAllocate* HAllocate::GetFoldableDominator(HAllocate* dominator) {
+  if (!IsFoldable(dominator)) {
+    // We cannot hoist old space allocations over new space allocations.
+    if (IsNewSpaceAllocation() || dominator->IsNewSpaceAllocation()) {
+      if (FLAG_trace_allocation_folding) {
+        PrintF("#%d (%s) cannot fold into #%d (%s), new space hoisting\n",
+            id(), Mnemonic(), dominator->id(), dominator->Mnemonic());
+      }
+      return NULL;
+    }
+
+    // We can hoist old data space allocations over an old pointer space
+    // allocation and vice versa. For that we have to check the dominator
+    // of the dominator allocate instruction.
+    if (dominator->dominating_allocate_ == NULL) {
+      dominating_allocate_ = dominator;
+      if (FLAG_trace_allocation_folding) {
+        PrintF("#%d (%s) cannot fold into #%d (%s), different spaces\n",
+            id(), Mnemonic(), dominator->id(), dominator->Mnemonic());
+      }
+      return NULL;
+    }
+
+    // If we stored a dominator in our actual dominator, then it must be in
+    // the space of the dominated allocation operation. We can hoist the old
+    // space allocation over the actual dominator.
+    dominator = dominator->dominating_allocate_;
+
+    // We can just fold old space allocations that are in the same basic block,
+    // since it is not guaranteed that we fill up the whole allocated old
+    // space memory.

[Michael Starzinger, 2013/08/09 09:22:58]

nit: Seems like an "otherwise" is missing at the end of this sentence.

+    // TODO(hpayer): Remove this limitation and add filler maps for each each
+    // allocation as soon as we have store elimination.
+    if (block()->block_id() != dominator->block()->block_id()) {
+      if (FLAG_trace_allocation_folding) {
+        PrintF("#%d (%s) cannot fold into #%d (%s), different basic blocks\n",
+            id(), Mnemonic(), dominator->id(), dominator->Mnemonic());
+      }
+      return NULL;
+    }
+
+    ASSERT((IsOldDataSpaceAllocation() &&
+           dominator->IsOldDataSpaceAllocation()) ||
+           (IsOldPointerSpaceAllocation() &&
+           dominator->IsOldPointerSpaceAllocation()));
+
+    int32_t current_size = HConstant::cast(size())->GetInteger32Constant();
+    HConstant* dominator_free_space_size = dominator->filler_free_space_size_;
+    if (dominator_free_space_size != NULL) {
+      // We already hoisted one old space allocation, i.e., we already installed
+      // a filler map. Hence, we just have to update the free space size.
+      UpdateFreeSpaceFiller(dominator_free_space_size,

[Michael Starzinger, 2013/08/09 09:22:58]

It seems these methods are called on the allocations being folded away. I think
it would make much more sense to actually call them on the dominating
allocation. These methods look like "bastard static functions not being static".
This would also make it easier to address the  comment in
HAllocate::UpdateFreeSpaceFiller.

[Hannes Payer (out of office), 2013/08/09 11:10:43]

Done, much better now!

+          dominator_free_space_size->GetInteger32Constant() + current_size);
+    } else {
+      // This is the first old space allocation that gets hoisted. We have to
+      // install a filler map since the follwing allocation may cause a GC.
+      int32_t dominator_size =
+          HConstant::cast(dominator->size())->GetInteger32Constant();
+      CreateFreeSpaceFiller(dominator, dominator_size, current_size);

[Michael Starzinger, 2013/08/09 09:22:58]

Addressing the comment above would allow you to not pass the dominator as a
parameter but as the receiver instead.

[Hannes Payer (out of office), 2013/08/09 11:10:43]

Done.

+    }
   }
+  return dominator;
+}
+
+
+void HAllocate::UpdateFreeSpaceFiller(HConstant* old_filler_size,
+                                      int32_t filler_size) {
+  Zone* zone = block()->zone();
+  HConstant* new_free_space_size = HConstant::CreateAndInsertBefore(
+      zone, context(), filler_size, old_filler_size);
+  old_filler_size->DeleteAndReplaceWith(new_free_space_size);

[Michael Starzinger, 2013/08/09 09:22:58]

This looks dangerous, can you guarantee that "old_filler_size" is only used by
the dominating allocation and not something else as well? Can we either assert
that this is the only use or set Hallocate::filler_free_space_size explicitly?

[Hannes Payer (out of office), 2013/08/09 11:10:43]

Done.

+}
+
+
+void HAllocate::CreateFreeSpaceFiller(HAllocate* dominator,
+                                      int32_t dominator_size,
+                                      int32_t filler_size) {
+  Zone* zone = block()->zone();
+  HInstruction* free_space_instr =
+      HInnerAllocatedObject::New(zone, context(), dominator, dominator_size,
+          type());
+  free_space_instr->InsertAfter(dominator);
+  HConstant* filler_map = HConstant::New(
+      zone,
+      context(),
+      isolate()->factory()->free_space_map(),
+      UniqueValueId(isolate()->heap()->free_space_map()));
+  filler_map->InsertAfter(free_space_instr);
+  HInstruction* store_map = HStoreNamedField::New(zone, context(),
+      free_space_instr, HObjectAccess::ForMap(), filler_map);
+  store_map->SetFlag(HValue::kHasNoObservableSideEffects);
+  store_map->InsertAfter(filler_map);
+
+  HConstant* free_space_size = HConstant::CreateAndInsertAfter(
+      zone, context(), filler_size, store_map);
+  dominator->filler_free_space_size_ = free_space_size;
+  HObjectAccess access =
+      HObjectAccess::ForJSObjectOffset(FreeSpace::kSizeOffset);
+  HInstruction* store_size = HStoreNamedField::New(zone, context(),
+      free_space_instr, access, free_space_size);
+  store_size->SetFlag(HValue::kHasNoObservableSideEffects);
+  store_size->InsertAfter(free_space_size);
 }