Inline array constructor.

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 1540 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::BuildAllocateArrayFromLength(
+    JSArrayBuilder* array_builder,
+    HValue* length_argument) {
+  if (length_argument->IsConstant() &&
+      HConstant::cast(length_argument)->HasSmiValue()) {
+    int array_length = HConstant::cast(length_argument)->Integer32Value();
+    HValue* new_object = (array_length == 0)

[Toon Verwaest, 2013/11/11 13:59:28]

Remove the parentheses.

[mvstanton, 2013/11/13 14:12:52]

Done.

+        ? array_builder->AllocateEmptyArray()
+        : array_builder->AllocateArray(length_argument, length_argument);
+    return new_object;
+  }
+
+  HValue* constant_zero = graph()->GetConstant0();
+  HConstant* max_alloc_length =
+      Add<HConstant>(JSObject::kInitialMaxFastElementArray);
+  const int initial_capacity = JSArray::kPreallocatedArrayElements;
+  HConstant* initial_capacity_node = Add<HConstant>(initial_capacity);

[Toon Verwaest, 2013/11/11 13:59:28]

Move this down to the case where initial-capacity-node is used.

[mvstanton, 2013/11/13 14:12:52]

Done.

+  HInstruction* checked_length = Add<HBoundsCheck>(length_argument,
+                                                   max_alloc_length);
+  IfBuilder if_builder(this);
+  if_builder.If<HCompareNumericAndBranch>(checked_length, constant_zero,
+                                          Token::EQ);
+  if_builder.Then();
+  Push(initial_capacity_node);  // capacity
+  Push(constant_zero);          // length
+  if_builder.Else();
+  Push(checked_length);         // capacity
+  Push(checked_length);         // length
+  if_builder.End();
+
+  // Figure out total size
+  HValue* length = Pop();
+  HValue* capacity = Pop();
+  return array_builder->AllocateArray(capacity, length);
+}
+
 HValue* HGraphBuilder::BuildAllocateElements(ElementsKind kind,
                                              HValue* capacity) {
   int elements_size;
   InstanceType instance_type;
 
   if (IsFastDoubleElementsKind(kind)) {
     elements_size = kDoubleSize;
     instance_type = FIXED_DOUBLE_ARRAY_TYPE;
   } else {
     elements_size = kPointerSize;
@@ skipping 168 matching lines @@
   // Fast elements kinds need to be initialized in case statements below cause
   // a garbage collection.
   Factory* factory = isolate()->factory();
 
   double nan_double = FixedDoubleArray::hole_nan_as_double();
   HValue* hole = IsFastSmiOrObjectElementsKind(elements_kind)
       ? Add<HConstant>(factory->the_hole_value())
       : Add<HConstant>(nan_double);
 
   // Special loop unfolding case
-  static const int kLoopUnfoldLimit = 4;
+  static const int kLoopUnfoldLimit = 6;
   bool unfold_loop = false;
-  int initial_capacity = JSArray::kPreallocatedArrayElements;
-  if (from->IsConstant() && to->IsConstant() &&
-      initial_capacity <= kLoopUnfoldLimit) {
-    HConstant* constant_from = HConstant::cast(from);
-    HConstant* constant_to = HConstant::cast(to);
+  int initial_capacity;
+
+  if (from->ActualValue()->IsConstant() && to->ActualValue()->IsConstant()) {

[Toon Verwaest, 2013/11/11 13:59:28]

Please put this is a separate CL (that also more widely applies ActualValue to
values you expect to be HConstant).

[mvstanton, 2013/11/13 14:12:52]

I made another CL that isolates the idef of HForceRepresentation that was
needed. But the wider application is so wide that I'd like to think about the
best solution a bit. My small CL will solve it locally here and then a follow up
will happen.

+    HConstant* constant_from = HConstant::cast(from->ActualValue());
+    HConstant* constant_to = HConstant::cast(to->ActualValue());
 
     if (constant_from->HasInteger32Value() &&
         constant_from->Integer32Value() == 0 &&
         constant_to->HasInteger32Value() &&
-        constant_to->Integer32Value() == initial_capacity) {
+        constant_to->Integer32Value() <= kLoopUnfoldLimit) {
       unfold_loop = true;
+      initial_capacity = constant_to->Integer32Value();
     }
   }
 
   // Since we're about to store a hole value, the store instruction below must
   // assume an elements kind that supports heap object values.
   if (IsFastSmiOrObjectElementsKind(elements_kind)) {
     elements_kind = FAST_HOLEY_ELEMENTS;
   }
 
   if (unfold_loop) {
@@ skipping 225 matching lines @@
       Add<HConstant>(static_cast<int32_t>(Context::ARRAY_FUNCTION_INDEX));
   return Add<HLoadKeyed>(
       native_context, index, static_cast<HValue*>(NULL), FAST_ELEMENTS);
 }
 
 
 HGraphBuilder::JSArrayBuilder::JSArrayBuilder(HGraphBuilder* builder,
     ElementsKind kind,
     HValue* allocation_site_payload,
     HValue* constructor_function,
-    AllocationSiteOverrideMode override_mode) :
+    AllocationSiteOverrideMode override_mode,
+    bool is_inlined) :
         builder_(builder),
         kind_(kind),
         allocation_site_payload_(allocation_site_payload),
-        constructor_function_(constructor_function) {
+        constructor_function_(constructor_function),
+        is_inlined_(is_inlined) {
   mode_ = override_mode == DISABLE_ALLOCATION_SITES
       ? DONT_TRACK_ALLOCATION_SITE
       : AllocationSite::GetMode(kind);
 }
 
 
 HGraphBuilder::JSArrayBuilder::JSArrayBuilder(HGraphBuilder* builder,
                                               ElementsKind kind,
                                               HValue* constructor_function) :
     builder_(builder),
     kind_(kind),
     mode_(DONT_TRACK_ALLOCATION_SITE),
     allocation_site_payload_(NULL),
-    constructor_function_(constructor_function) {
+    constructor_function_(constructor_function),
+    is_inlined_(false) {
 }
 
 
 HValue* HGraphBuilder::JSArrayBuilder::EmitMapCode() {
+  if (is_inlined_) {

[Toon Verwaest, 2013/11/11 13:59:28]

Is it good enough to use IsStub() rather than is_inlined? Then we don't need an
enum after all.

[mvstanton, 2013/11/13 14:12:52]

Sure is, thanks for the idea. Done.

+    // A constant map is fine.
+    Handle<Map> map(builder()->isolate()->get_initial_js_array_map(kind_),
+                    builder()->isolate());
+    return builder()->Add<HConstant>(map);
+  }
+
   if (kind_ == GetInitialFastElementsKind()) {
     // No need for a context lookup if the kind_ matches the initial
     // map, because we can just load the map in that case.
     HObjectAccess access = HObjectAccess::ForPrototypeOrInitialMap();
     return builder()->AddLoadNamedField(constructor_function_, access);
   }
 
   HInstruction* native_context = builder()->BuildGetNativeContext();
   HInstruction* index = builder()->Add<HConstant>(
       static_cast<int32_t>(Context::JS_ARRAY_MAPS_INDEX));
@@ skipping 20 matching lines @@
   ASSERT(length_node != NULL);
 
   int base_size = JSArray::kSize;
   if (mode_ == TRACK_ALLOCATION_SITE) {
     base_size += AllocationMemento::kSize;
   }
 
   STATIC_ASSERT(FixedDoubleArray::kHeaderSize == FixedArray::kHeaderSize);
   base_size += FixedArray::kHeaderSize;
 
+  if (length_node->IsConstant()) {
+    HConstant* constant_length_node = HConstant::cast(length_node);
+    if (constant_length_node->HasInteger32Value()) {
+      int size = base_size + elements_size() *
+          constant_length_node->Integer32Value();
+      HInstruction* const_size = builder()->Add<HConstant>(size);
+      return const_size;

[Toon Verwaest, 2013/11/11 13:59:28]

I think constant folding should take care of this. (And in other places where
you added such code, if there are such).

[mvstanton, 2013/11/13 14:12:52]

Indeed, thx!

+    }
+  }
+
   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;
 }
@@ skipping 11 matching lines @@
 
   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);
+                       builder()->graph()->GetConstant0());
 }
 
 
 HValue* HGraphBuilder::JSArrayBuilder::AllocateArray(HValue* capacity,
                                                      HValue* length_field,
-                                                     bool fill_with_hole) {
+                                                     FillMode fill_mode) {
   HValue* size_in_bytes = EstablishAllocationSize(capacity);
-  return AllocateArray(size_in_bytes, capacity, length_field, fill_with_hole);
+  return AllocateArray(size_in_bytes, capacity, length_field, fill_mode);
 }
 
 
 HValue* HGraphBuilder::JSArrayBuilder::AllocateArray(HValue* size_in_bytes,
                                                      HValue* capacity,
                                                      HValue* length_field,
-                                                     bool fill_with_hole) {
+                                                     FillMode fill_mode) {
   // 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());
   // Allocate (dealing with failure appropriately)
   HAllocate* new_object = builder()->Add<HAllocate>(size_in_bytes,
       HType::JSArray(), NOT_TENURED, JS_ARRAY_TYPE);
@@ skipping 13 matching lines @@
   elements_location_ = builder()->BuildJSArrayHeader(new_object,
                                                      map,
                                                      mode_,
                                                      kind_,
                                                      allocation_site_payload_,
                                                      length_field);
 
   // Initialize the elements
   builder()->BuildInitializeElementsHeader(elements_location_, kind_, capacity);
 
-  if (fill_with_hole) {
+  if (fill_mode == FILL_WITH_HOLE) {
     builder()->BuildFillElementsWithHole(elements_location_, kind_,
                                          graph()->GetConstant0(), capacity);
   }
 
   return new_object;
 }
 
 
 HStoreNamedField* HGraphBuilder::AddStoreMapConstant(HValue *object,
                                                      Handle<Map> map) {
@@ skipping 5000 matching lines @@
 
       call = New<HCallFunction>(function, argument_count);
       Drop(argument_count + 1);
     }
   }
 
   return ast_context()->ReturnInstruction(call, expr->id());
 }
 
 
+void HOptimizedGraphBuilder::BuildInlinedCallNewArray(CallNew* expr) {
+  NoObservableSideEffectsScope no_effects(this);
+
+  int argument_count = expr->arguments()->length();
+  // We should at least have the constructor on the expression stack.
+  ASSERT(!environment()->ExpressionStackIsEmpty());

[Toon Verwaest, 2013/11/11 13:59:28]

I this ASSERT and the comment necessary? Doesn't the expression below fail if
ExpressionStackAt(...) is out of bounds? If it doesn't, can we just make that
fail?

[mvstanton, 2013/11/13 14:12:52]

Done.

+  HValue* constructor = environment()->ExpressionStackAt(argument_count);
+
+  ElementsKind kind = expr->elements_kind();
+  Handle<Cell> cell = expr->allocation_info_cell();
+  AllocationSite* site = AllocationSite::cast(cell->value());
+
+  // Register on the site for deoptimization if the cell value changes.
+  site->AddDependentCompilationInfo(AllocationSite::TRANSITIONS, top_info());
+  HInstruction* cell_instruction = Add<HConstant>(cell);
+
+  // In the single constant argument case, we may have to adjust elements kind
+  // to avoid creating a packed non-empty array (not kosher).

[Toon Verwaest, 2013/11/11 13:59:28]

I'd remove the (not kosher) part.

[mvstanton, 2013/11/13 14:12:52]

Done.

+  if (argument_count == 1 && !IsHoleyElementsKind(kind)) {

[Toon Verwaest, 2013/11/11 13:59:28]

Can't we just do this in BuildAllocateArrayFromLength? That would seem better
encapsulated.

[mvstanton, 2013/11/13 14:12:52]

Hmm, I'd rather not because then the JSArrayBuilder would have to allow you to
change ElementsKind, currently passed in at constructor time. This is a special
case, and I think it's at the right place for now. I like the semantics that
kind becomes fixed once you have a JSArrayBuilder.

+    HValue* argument = environment()->Top();
+    if (argument->IsConstant()) {
+      HConstant* constant_argument = HConstant::cast(argument);
+      ASSERT(constant_argument->HasSmiValue());
+      int constant_array_size = constant_argument->Integer32Value();
+      if (constant_array_size != 0) {
+        kind = GetHoleyElementsKind(kind);
+      }
+    }
+  }
+
+  // Build the array.
+  JSArrayBuilder array_builder(this,
+                               kind,
+                               cell_instruction,
+                               constructor,
+                               DISABLE_ALLOCATION_SITES,
+                               true);
+  HValue* new_object;
+  if (argument_count == 0) {
+    new_object = array_builder.AllocateEmptyArray();
+  } else if (argument_count == 1) {
+    HValue* argument = environment()->Top();
+    new_object = BuildAllocateArrayFromLength(&array_builder, argument);
+  } else {
+    HValue* length = Add<HConstant>(argument_count);
+    // Smi arrays need to initialize array elements with the hole because
+    // bailout could occur if the arguments don't fit in a smi.
+    //
+    // TODO(mvstanton): If all the arguments are constants in smi range, then
+    // we could set fill_with_hole to false and save a few instructions.
+    JSArrayBuilder::FillMode fill_mode = IsFastSmiElementsKind(kind)
+        ? JSArrayBuilder::FILL_WITH_HOLE
+        : JSArrayBuilder::DONT_FILL_WITH_HOLE;
+    new_object = array_builder.AllocateArray(length, length, fill_mode);
+    HValue* elements = array_builder.GetElementsLocation();
+    for (int i = 0; i < argument_count; i++) {
+      HValue* value = environment()->ExpressionStackAt(argument_count - i - 1);
+      HValue* constant_i = Add<HConstant>(i);
+      Add<HStoreKeyed>(elements, constant_i, value, kind);
+    }
+  }
+
+  Drop(argument_count + 1);  // drop constructor and args.
+  ast_context()->ReturnValue(new_object);
+}
+
+
 // Checks whether allocation using the given constructor can be inlined.
 static bool IsAllocationInlineable(Handle<JSFunction> constructor) {
   return constructor->has_initial_map() &&
       constructor->initial_map()->instance_type() == JS_OBJECT_TYPE &&
       constructor->initial_map()->instance_size() < HAllocate::kMaxInlineSize &&
       constructor->initial_map()->InitialPropertiesLength() == 0;
 }
 
 
+bool HOptimizedGraphBuilder::IsCallNewArrayInlineable(CallNew* expr) {
+  bool inline_ok = false;
+  Handle<JSFunction> caller = current_info()->closure();
+  Handle<JSFunction> target(isolate()->global_context()->array_function(),
+                            isolate());
+  int argument_count = expr->arguments()->length();
+  // We should have the function plus array arguments on the environment stack.
+  ASSERT(environment()->length() >= (argument_count + 1));
+  Handle<Cell> cell = expr->allocation_info_cell();
+  AllocationSite* site = AllocationSite::cast(cell->value());
+  if (site->CanInlineCall()) {
+    // We also want to avoid inlining in certain 1 argument scenarios.
+    if (argument_count == 1) {
+      HValue* argument = Top();
+      if (argument->IsConstant()) {
+        // Do not inline if the constant length argument is not a smi or
+        // outside the valid range for a fast array.
+        HConstant* constant_argument = HConstant::cast(argument);
+        if (constant_argument->HasSmiValue()) {
+          int value = constant_argument->Integer32Value();
+          inline_ok = value >= 0 &&
+              value < JSObject::kInitialMaxFastElementArray;
+          if (!inline_ok) {
+            TraceInline(target, caller,
+                        "Length outside of valid array range");
+          }
+        }
+      } else {
+        // The amount of code we'd have to generate doubles if we have a
+        // non-constant length, but packed elements_kind feedback. Don't
+        // inline this case.
+        inline_ok = IsHoleyElementsKind(expr->elements_kind());

[Toon Verwaest, 2013/11/11 13:59:28]

Shouldn't we just deopt if the passed length is non-zero?

[mvstanton, 2013/11/13 14:12:52]

Yep, done. I also added a test in array-constructor-feedback.js to ensure this
works as expected.

+        if (!inline_ok) {
+          TraceInline(target, caller,
+                      "Non-holey elements kind for single argument");
+        }
+      }
+    } else {
+      inline_ok = true;
+    }
+  } else {
+    TraceInline(target, caller, "AllocationSite requested no inlining.");
+  }
+
+  if (inline_ok) {
+    TraceInline(target, caller, NULL);
+  }
+  return inline_ok;
+}
+
+
 void HOptimizedGraphBuilder::VisitCallNew(CallNew* expr) {
   ASSERT(!HasStackOverflow());
   ASSERT(current_block() != NULL);
   ASSERT(current_block()->HasPredecessor());
   if (!FLAG_emit_opt_code_positions) SetSourcePosition(expr->position());
   int argument_count = expr->arguments()->length() + 1;  // Plus constructor.
   Factory* factory = isolate()->factory();
 
+  // The constructor function is on the stack in the unoptimized code
+  // during evaluation of the arguments.
+  CHECK_ALIVE(VisitForValue(expr->expression()));
+  HValue* function = Top();
+  CHECK_ALIVE(VisitExpressions(expr->arguments()));
+
   if (FLAG_inline_construct &&
       expr->IsMonomorphic() &&
       IsAllocationInlineable(expr->target())) {
-    // The constructor function is on the stack in the unoptimized code
-    // during evaluation of the arguments.
-    CHECK_ALIVE(VisitForValue(expr->expression()));
-    HValue* function = Top();
-    CHECK_ALIVE(VisitExpressions(expr->arguments()));
     Handle<JSFunction> constructor = expr->target();
     HValue* check = Add<HCheckValue>(function, constructor);
 
     // Force completion of inobject slack tracking before generating
     // allocation code to finalize instance size.
     if (constructor->shared()->IsInobjectSlackTrackingInProgress()) {
       constructor->shared()->CompleteInobjectSlackTracking();
     }
 
     // Calculate instance size from initial map of constructor.
@@ skipping 66 matching lines @@
     check->DeleteAndReplaceWith(NULL);
     environment()->SetExpressionStackAt(receiver_index, function);
     HInstruction* call =
       PreProcessCall(New<HCallNew>(function, argument_count));
     return ast_context()->ReturnInstruction(call, expr->id());
   } else {
     // The constructor function is both an operand to the instruction and an
     // argument to the construct call.
     Handle<JSFunction> array_function(
         isolate()->global_context()->array_function(), isolate());
-    CHECK_ALIVE(VisitArgument(expr->expression()));
-    HValue* constructor = HPushArgument::cast(Top())->argument();
-    CHECK_ALIVE(VisitArgumentList(expr->arguments()));
+    bool use_call_new_array = expr->target().is_identical_to(array_function);
+    Handle<Cell> cell = expr->allocation_info_cell();
+    if (use_call_new_array && IsCallNewArrayInlineable(expr)) {
+      // Verify we are still calling the array function for our native context.
+      Add<HCheckValue>(function, array_function);
+      BuildInlinedCallNewArray(expr);
+      return;
+    }
+
     HBinaryCall* call;
-    if (expr->target().is_identical_to(array_function)) {
-      Handle<Cell> cell = expr->allocation_info_cell();
-      Add<HCheckValue>(constructor, array_function);
-      call = New<HCallNewArray>(constructor, argument_count,
-                                cell, expr->elements_kind());
+    if (use_call_new_array) {
+      Add<HCheckValue>(function, array_function);
+      call = New<HCallNewArray>(function, argument_count, cell,
+                                expr->elements_kind());
     } else {
-      call = New<HCallNew>(constructor, argument_count);
+      call = New<HCallNew>(function, argument_count);
     }
-    Drop(argument_count);
+    PreProcessCall(call);
     return ast_context()->ReturnInstruction(call, expr->id());
   }
 }
 
 
 // Support for generating inlined runtime functions.
 
 // Lookup table for generators for runtime calls that are generated inline.
 // Elements of the table are member pointers to functions of
 // HOptimizedGraphBuilder.
@@ skipping 2517 matching lines @@
   if (ShouldProduceTraceOutput()) {
     isolate()->GetHTracer()->TraceHydrogen(name(), graph_);
   }
 
 #ifdef DEBUG
   graph_->Verify(false);  // No full verify.
 #endif
 }
 
 } }  // namespace v8::internal