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

src/hydrogen.cc

 // Copyright 2013 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 1891 matching lines @@
             elements, isolate()->factory()->fixed_array_map(), top_info());
         check_cow_map->ClearGVNFlag(kDependsOnElementsKind);
       }
     }
   }
   return AddElementAccess(elements, checked_key, val, checked_object,
                           elements_kind, is_store, load_mode);
 }
 
 
+HValue* HGraphBuilder::BuildCalculateElementsSize(ElementsKind kind,
+                                                  HValue* capacity) {
+  HValue* actual_capacity = capacity->ActualValue();
+
+  if (actual_capacity->IsInteger32Constant()) {
+    int length = HConstant::cast(actual_capacity)->GetInteger32Constant();
+    int base_size = IsFastDoubleElementsKind(kind)
+        ? FixedDoubleArray::SizeFor(length)
+        : FixedArray::SizeFor(length);
+
+    return Add<HConstant>(base_size);
+
+  } else {
+    int elements_size = IsFastDoubleElementsKind(kind)

[mvstanton, 2013/11/14 10:04:20]

I just ran into a similar situation. Constant-folding should take care of this,
so you don't need to manually optimize the code in this way. Have a look at the
generated hydrogen and you'll see that the "else" block here ends up as an
HConstant because it recognizes that the operands to HMul and HAdd are constant
themselves. You might have to teach HAdd::New and HMul::New to respect
ActualValue() to make it work.

[Igor Sheludko, 2013/11/27 12:52:01]

On 2013/11/14 10:04:20, mvstanton wrote:
Ok, I removed manual constant folding code from here in this CL and in a
separate CL I'll make sure that constant folding works here as expected.

+        ? kDoubleSize
+        : kPointerSize;
+
+    HConstant* elements_size_value = Add<HConstant>(elements_size);
+    HValue* mul = Add<HMul>(capacity, elements_size_value);
+    mul->ClearFlag(HValue::kCanOverflow);
+
+    HConstant* header_size = Add<HConstant>(FixedArray::kHeaderSize);
+    HValue* total_size = Add<HAdd>(mul, header_size);
+    total_size->ClearFlag(HValue::kCanOverflow);
+    return total_size;
+  }
+}
+
 HValue* HGraphBuilder::BuildAllocateElements(ElementsKind kind,
-                                             HValue* capacity) {
-  int elements_size;
-  InstanceType instance_type;
+                                             HValue* size_in_bytes,
+                                             PretenureFlag pretenure) {
+  InstanceType instance_type = IsFastDoubleElementsKind(kind)
+      ? FIXED_DOUBLE_ARRAY_TYPE
+      : FIXED_ARRAY_TYPE;
 
-  if (IsFastDoubleElementsKind(kind)) {
-    elements_size = kDoubleSize;
-    instance_type = FIXED_DOUBLE_ARRAY_TYPE;
-  } else {
-    elements_size = kPointerSize;
-    instance_type = FIXED_ARRAY_TYPE;
-  }
-
-  HConstant* elements_size_value = Add<HConstant>(elements_size);
-  HValue* mul = Add<HMul>(capacity, elements_size_value);
-  mul->ClearFlag(HValue::kCanOverflow);
-
-  HConstant* header_size = Add<HConstant>(FixedArray::kHeaderSize);
-  HValue* total_size = Add<HAdd>(mul, header_size);
-  total_size->ClearFlag(HValue::kCanOverflow);
-
-  return Add<HAllocate>(total_size, HType::JSArray(),
-      isolate()->heap()->GetPretenureMode(), instance_type);
+  return Add<HAllocate>(size_in_bytes, HType::JSArray(),
+                        pretenure, instance_type);
 }
 
 
 void HGraphBuilder::BuildInitializeElementsHeader(HValue* elements,
                                                   ElementsKind kind,
                                                   HValue* capacity) {
   Factory* factory = isolate()->factory();
   Handle<Map> map = IsFastDoubleElementsKind(kind)
       ? factory->fixed_double_array_map()
       : factory->fixed_array_map();
 
   AddStoreMapConstant(elements, map);
   Add<HStoreNamedField>(elements, HObjectAccess::ForFixedArrayLength(),
                         capacity);
 }
 
 
 HValue* HGraphBuilder::BuildAllocateElementsAndInitializeElementsHeader(
     ElementsKind kind,
     HValue* capacity) {
   // The HForceRepresentation is to prevent possible deopt on int-smi
   // conversion after allocation but before the new object fields are set.
   capacity = Add<HForceRepresentation>(capacity, Representation::Smi());
-  HValue* new_elements = BuildAllocateElements(kind, capacity);
+  HValue* size_in_bytes = BuildCalculateElementsSize(kind, capacity);
+  HValue* new_elements = BuildAllocateElements(
+      kind, size_in_bytes, isolate()->heap()->GetPretenureMode());
   BuildInitializeElementsHeader(new_elements, kind, capacity);
   return new_elements;
 }
 
 
-HInnerAllocatedObject* HGraphBuilder::BuildJSArrayHeader(HValue* array,
-    HValue* array_map,
-    AllocationSiteMode mode,
-    ElementsKind elements_kind,
-    HValue* allocation_site_payload,
-    HValue* length_field) {
-
+void HGraphBuilder::BuildJSArrayHeader(HValue* array,
+                                       HValue* array_map,
+                                       AllocationSiteMode mode,
+                                       ElementsKind elements_kind,
+                                       HValue* allocation_site_payload,
+                                       HValue* length_field) {
   Add<HStoreNamedField>(array, HObjectAccess::ForMap(), array_map);
 
   HConstant* empty_fixed_array =
     Add<HConstant>(isolate()->factory()->empty_fixed_array());
 
-  HObjectAccess access = HObjectAccess::ForPropertiesPointer();
-  Add<HStoreNamedField>(array, access, empty_fixed_array);
-  Add<HStoreNamedField>(array, HObjectAccess::ForArrayLength(elements_kind),
-                        length_field);
+  Add<HStoreNamedField>(
+      array, HObjectAccess::ForPropertiesPointer(), empty_fixed_array);
+
+  Add<HStoreNamedField>(
+      array, HObjectAccess::ForElementsPointer(), empty_fixed_array);
+
+  Add<HStoreNamedField>(
+      array, HObjectAccess::ForArrayLength(elements_kind), length_field);
 
   if (mode == TRACK_ALLOCATION_SITE) {
     BuildCreateAllocationMemento(array,
                                  JSArray::kSize,
                                  allocation_site_payload);
   }
-
-  int elements_location = JSArray::kSize;
-  if (mode == TRACK_ALLOCATION_SITE) {
-    elements_location += AllocationMemento::kSize;
-  }
-
-  HValue* elements = Add<HInnerAllocatedObject>(array, elements_location);
-  Add<HStoreNamedField>(array, HObjectAccess::ForElementsPointer(), elements);
-  return static_cast<HInnerAllocatedObject*>(elements);
 }
 
 
 HInstruction* HGraphBuilder::AddElementAccess(
     HValue* elements,
     HValue* checked_key,
     HValue* val,
     HValue* dependency,
     ElementsKind elements_kind,
     bool is_store,
@@ skipping 394 matching lines @@
 }
 
 
 HValue* HGraphBuilder::JSArrayBuilder::EmitInternalMapCode() {
   // Find the map near the constructor function
   HObjectAccess access = HObjectAccess::ForPrototypeOrInitialMap();
   return builder()->AddLoadNamedField(constructor_function_, access);
 }
 
 
-HValue* HGraphBuilder::JSArrayBuilder::EstablishAllocationSize(
-    HValue* length_node) {
-  ASSERT(length_node != NULL);
-
+HValue* HGraphBuilder::JSArrayBuilder::EstablishHeaderAllocationSize() {
   int base_size = JSArray::kSize;
   if (mode_ == TRACK_ALLOCATION_SITE) {
     base_size += AllocationMemento::kSize;
   }
-
-  STATIC_ASSERT(FixedDoubleArray::kHeaderSize == FixedArray::kHeaderSize);
-  base_size += FixedArray::kHeaderSize;
-
-  HInstruction* elements_size_value =
-      builder()->Add<HConstant>(elements_size());
-  HInstruction* mul = builder()->Add<HMul>(length_node, elements_size_value);
-  mul->ClearFlag(HValue::kCanOverflow);
-
-  HInstruction* base = builder()->Add<HConstant>(base_size);
-  HInstruction* total_size = builder()->Add<HAdd>(base, mul);
-  total_size->ClearFlag(HValue::kCanOverflow);
-  return total_size;
-}
-
-
-HValue* HGraphBuilder::JSArrayBuilder::EstablishEmptyArrayAllocationSize() {
-  int base_size = JSArray::kSize;
-  if (mode_ == TRACK_ALLOCATION_SITE) {
-    base_size += AllocationMemento::kSize;
-  }
-
-  base_size += IsFastDoubleElementsKind(kind_)
-      ? FixedDoubleArray::SizeFor(initial_capacity())
-      : FixedArray::SizeFor(initial_capacity());
-
   return builder()->Add<HConstant>(base_size);
 }
 
 
 HValue* HGraphBuilder::JSArrayBuilder::AllocateEmptyArray() {
-  HValue* size_in_bytes = EstablishEmptyArrayAllocationSize();
   HConstant* capacity = builder()->Add<HConstant>(initial_capacity());
-  return AllocateArray(size_in_bytes,
-                       capacity,
-                       builder()->graph()->GetConstant0(),
-                       true);
+  return AllocateArray(capacity,
+                        builder()->graph()->GetConstant0(),
+                        true);
 }
 
 
 HValue* HGraphBuilder::JSArrayBuilder::AllocateArray(HValue* capacity,
                                                      HValue* length_field,
                                                      bool fill_with_hole) {
-  HValue* size_in_bytes = EstablishAllocationSize(capacity);
-  return AllocateArray(size_in_bytes, capacity, length_field, fill_with_hole);
-}
-
-
-HValue* HGraphBuilder::JSArrayBuilder::AllocateArray(HValue* size_in_bytes,
-                                                     HValue* capacity,
-                                                     HValue* length_field,
-                                                     bool fill_with_hole) {
   // These HForceRepresentations are because we store these as fields in the
   // objects we construct, and an int32-to-smi HChange could deopt. Accept
   // the deopt possibility now, before allocation occurs.
   capacity = builder()->Add<HForceRepresentation>(capacity,
                                                   Representation::Smi());
   length_field = builder()->Add<HForceRepresentation>(length_field,
                                                       Representation::Smi());
+
+  // Generate size calculation code here in order to make it dominate
+  // the JSArray allocation.

[mvstanton, 2013/11/14 10:04:20]

Nice.

[Igor Sheludko, 2013/11/27 12:52:01]

Done.

+  HValue* elms_size = builder()->BuildCalculateElementsSize(kind_, capacity);
+
   // Allocate (dealing with failure appropriately)
-  HAllocate* new_object = builder()->Add<HAllocate>(size_in_bytes,
+  HValue* array_object_size = EstablishHeaderAllocationSize();
+  HAllocate* array_object = builder()->Add<HAllocate>(array_object_size,
       HType::JSArray(), NOT_TENURED, JS_ARRAY_TYPE);
 
-  // Folded array allocation should be aligned if it has fast double elements.
-  if (IsFastDoubleElementsKind(kind_)) {
-     new_object->MakeDoubleAligned();

[mvstanton, 2013/11/14 10:04:20]

Why was this removed, is it handled during the folding step?

[Igor Sheludko, 2013/11/27 12:52:01]

This flag is set in the constructor of the HAllocate for fixed array. And yes,
the folding step takes care of that.

-  }
-
   // Fill in the fields: map, properties, length
   HValue* map;
   if (allocation_site_payload_ == NULL) {
     map = EmitInternalMapCode();
   } else {
     map = EmitMapCode();
   }
-  elements_location_ = builder()->BuildJSArrayHeader(new_object,
-                                                     map,
-                                                     mode_,
-                                                     kind_,
-                                                     allocation_site_payload_,
-                                                     length_field);
 
-  // Initialize the elements
+  builder()->BuildJSArrayHeader(array_object,
+                                map,
+                                mode_,
+                                kind_,
+                                allocation_site_payload_,
+                                length_field);
+
+  // Allocate and initialize the elements
+  elements_location_ =
+      builder()->BuildAllocateElements(kind_, elms_size, NOT_TENURED);
+
   builder()->BuildInitializeElementsHeader(elements_location_, kind_, capacity);
 
+  // Set the elements
+  builder()->Add<HStoreNamedField>(
+      array_object, HObjectAccess::ForElementsPointer(), elements_location_);
+

[mvstanton, 2013/11/14 10:04:20]

Can you verify that a write barrier isn't used for the store of the elements
pointer? Previously, we were protected because elements_location was an
HInnerAllocatedObject. Now, we should be protected by the fact that both
allocations are NEW_SPACE allocations.

[Igor Sheludko, 2013/11/27 12:52:01]

If two allocations folds together then the second one becomes HInnerAllocation
with all the benefits as before. Unfortunately, if the allocations are not
folded then write barrier is NOT eliminated.

   if (fill_with_hole) {
     builder()->BuildFillElementsWithHole(elements_location_, kind_,
                                          graph()->GetConstant0(), capacity);
   }
 
-  return new_object;
+  return array_object;
 }
 
 
 HStoreNamedField* HGraphBuilder::AddStoreMapConstant(HValue *object,
                                                      Handle<Map> map) {
   return Add<HStoreNamedField>(object, HObjectAccess::ForMap(),
                                Add<HConstant>(map));
 }
 
 
@@ skipping 7650 matching lines @@
   if (ShouldProduceTraceOutput()) {
     isolate()->GetHTracer()->TraceHydrogen(name(), graph_);
   }
 
 #ifdef DEBUG
   graph_->Verify(false);  // No full verify.
 #endif
 }
 
 } }  // namespace v8::internal