Supported folding of constant size allocation followed by dynamic size allocation.

src/hydrogen-instructions.cc

 // Copyright 2012 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 768 matching lines @@
   if (block->last() == previous) {
     block->set_last(this);
   }
   if (position() == RelocInfo::kNoPosition &&
       previous->position() != RelocInfo::kNoPosition) {
     set_position(previous->position());
   }
 }
 
 
+bool HInstruction::Dominates(HInstruction* other) {
+  if (block() != other->block()) {
+    return block()->Dominates(other->block());
+  }
+  // Both instructions are in the same basic block. This instruction
+  // should precede the other one in order to dominate it.
+  for (HInstruction* instr = next(); instr != NULL; instr = instr->next()) {
+    if (instr == other) {
+      return true;
+    }
+  }
+  return false;
+}
+
+
 #ifdef DEBUG
 void HInstruction::Verify() {
   // Verify that input operands are defined before use.
   HBasicBlock* cur_block = block();
   for (int i = 0; i < OperandCount(); ++i) {
     HValue* other_operand = OperandAt(i);
     if (other_operand == NULL) continue;
     HBasicBlock* other_block = other_operand->block();
     if (cur_block == other_block) {
       if (!other_operand->IsPhi()) {
@@ skipping 2616 matching lines @@
 
   // Try to fold allocations together with their dominating allocations.
   if (!dominator->IsAllocate()) {
     if (FLAG_trace_allocation_folding) {
       PrintF("#%d (%s) cannot fold into #%d (%s)\n",
           id(), Mnemonic(), dominator->id(), dominator->Mnemonic());
     }
     return;
   }
 
+  // This allocation has wired allocation with dynamic size
+  // (JSArray + FixedArray). We want them to be allocated together instead
+  // of trying to fold first allocation to some other dominating allocation
+  // because otherwise it will prevent write barrier optimization.

[Hannes Payer (out of office), 2013/12/04 08:27:22]

I just discussed the wired concept with Danno. We agreed on keeping the folding
code simple, i.e., don't wire allocations together, since it has no performance
impact.

[Igor Sheludko, 2013/12/30 19:20:48]

Ok, I'll revert wiring and implement explicit allocation size upper bound
propagation.

+  if (wired_allocate_ != NULL &&
+      !wired_allocate_->size()->IsInteger32Constant()) {

[Hannes Payer (out of office), 2013/11/29 09:14:29]

Can we not bail out here and check if the wired allocation fits?

A general comment: What about using the wired allocation concept to also get rid
of allocation mementos? For that, we would have to wire mementos to their
objects and make sure that the wired allocation also has enough space to get
folded.

We could then get rid of manual folding, in a separate cl.

 

[Igor Sheludko, 2013/12/30 19:20:48]

As we decided to revert wiring this note is no longer applicable.

+    return;
+  }
+
   HAllocate* dominator_allocate = HAllocate::cast(dominator);
   HValue* dominator_size = dominator_allocate->size();
   HValue* current_size = size();
 
   // TODO(hpayer): Add support for non-constant allocation in dominator.
-  if (!current_size->IsInteger32Constant() ||
-      !dominator_size->IsInteger32Constant()) {
+  if (!dominator_size->IsInteger32Constant()) {
     if (FLAG_trace_allocation_folding) {
-      PrintF("#%d (%s) cannot fold into #%d (%s), dynamic allocation size\n",
+      PrintF("#%d (%s) cannot fold into #%d (%s), "
+             "dynamic allocation size in dominator\n",
           id(), Mnemonic(), dominator->id(), dominator->Mnemonic());
     }
     return;
   }
 
   dominator_allocate = GetFoldableDominator(dominator_allocate);
   if (dominator_allocate == NULL) {
     return;
   }
 
+  if (!current_size->IsInteger32Constant()) {
+    // Currently we allow folding of constant size allocation with dynamic
+    // size allocation only if they are wired.
+    if (dominator_allocate->wired_allocate_ != this) {
+      if (FLAG_trace_allocation_folding) {
+        PrintF("#%d (%s) cannot fold into #%d (%s), "
+               "can't estimate total allocation size\n",
+            id(), Mnemonic(), dominator->id(), dominator->Mnemonic());
+      }
+      return;
+    }
+
+    // If it's not constant then it is a size_in_bytes calculation graph
+    // like this: (const_header_size + const_element_size * size).
+    ASSERT(current_size->IsInstruction());
+
+    HInstruction* current_instr = HInstruction::cast(current_size);
+    if (!current_instr->Dominates(dominator_allocate)) {
+      if (FLAG_trace_allocation_folding) {
+        PrintF("#%d (%s) cannot fold into #%d (%s), dynamic size "
+               "value does not dominate target allocation\n",
+            id(), Mnemonic(), dominator->id(), dominator->Mnemonic());
+      }
+      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 original_object_size =
       HConstant::cast(dominator_size)->GetInteger32Constant();
   int32_t dominator_size_constant = original_object_size;
-  int32_t current_size_constant =
-      HConstant::cast(current_size)->GetInteger32Constant();
-  int32_t new_dominator_size = dominator_size_constant + current_size_constant;
+
+  if (MustAllocateDoubleAligned()) {
+    if ((dominator_size_constant & kDoubleAlignmentMask) != 0) {
+      dominator_size_constant += kDoubleSize / 2;
+    }
+  }
+
+  HInstruction* new_dominator_size_value;
+
+  if (current_size->IsInteger32Constant()) {
+    int32_t current_size_value = size()->GetInteger32Constant();
+    int32_t new_dominator_size = dominator_size_constant + current_size_value;
+
+    if (new_dominator_size >
+        isolate()->heap()->MaxRegularSpaceAllocationSize()) {
+      if (FLAG_trace_allocation_folding) {
+        PrintF("#%d (%s) cannot fold into #%d (%s), "
+               "resulting allocation size is too big\n",
+            id(), Mnemonic(), dominator->id(), dominator->Mnemonic());
+      }
+      return;
+    }
+
+    new_dominator_size_value =
+        HConstant::CreateAndInsertBefore(zone,
+                                         context(),
+                                         new_dominator_size,
+                                         Representation::None(),
+                                         dominator_allocate);
+  } else {
+    ASSERT(dominator_allocate->wired_allocate_ == this);
+    dominator_allocate->wired_allocate_ = NULL;
+
+    HValue* new_dominator_size_constant =
+        HConstant::CreateAndInsertBefore(zone,
+                                         context(),
+                                         dominator_size_constant,
+                                         Representation::Integer32(),
+                                         dominator_allocate);
+
+    // Add old and new size together and insert
+    current_size->ChangeRepresentation(Representation::Integer32());
+
+    new_dominator_size_value = HAdd::New(zone, context(),
+        new_dominator_size_constant, current_size);
+    new_dominator_size_value->ClearFlag(HValue::kCanOverflow);
+    new_dominator_size_value->ChangeRepresentation(Representation::Integer32());
+
+    new_dominator_size_value->InsertBefore(dominator_allocate);
+  }
+
+  dominator_allocate->UpdateSize(new_dominator_size_value);
 
   if (MustAllocateDoubleAligned()) {
     if (!dominator_allocate->MustAllocateDoubleAligned()) {
       dominator_allocate->MakeDoubleAligned();
     }
-    if ((dominator_size_constant & kDoubleAlignmentMask) != 0) {
-      dominator_size_constant += kDoubleSize / 2;
-      new_dominator_size += kDoubleSize / 2;
-    }
   }
 
-  if (new_dominator_size > isolate()->heap()->MaxRegularSpaceAllocationSize()) {
-    if (FLAG_trace_allocation_folding) {
-      PrintF("#%d (%s) cannot fold into #%d (%s) due to size: %d\n",
-          id(), Mnemonic(), dominator_allocate->id(),
-          dominator_allocate->Mnemonic(), new_dominator_size);
-    }
-    return;
-  }
-
-  HInstruction* new_dominator_size_constant = HConstant::CreateAndInsertBefore(
-      zone,
-      context(),
-      new_dominator_size,
-      Representation::None(),
-      dominator_allocate);
-  dominator_allocate->UpdateSize(new_dominator_size_constant);
-
 #ifdef VERIFY_HEAP
   if (FLAG_verify_heap && dominator_allocate->IsNewSpaceAllocation()) {
     dominator_allocate->MakePrefillWithFiller();
   } else {
     // TODO(hpayer): This is a short-term hack to make allocation mementos
     // work again in new space.
     dominator_allocate->ClearNextMapWord(original_object_size);
   }
 #else
   // TODO(hpayer): This is a short-term hack to make allocation mementos
@@ skipping 916 matching lines @@
       break;
     case kExternalMemory:
       stream->Add("[external-memory]");
       break;
   }
 
   stream->Add("@%d", offset());
 }
 
 } }  // namespace v8::internal