[Turbofan] Inline Array.prototype.map
Bug: v8:1956
Change-Id: I41af0cf5eb2fbb9f1d9d4172f3f546bcc2a715dc
Reviewed-on: https://chromium-review.googlesource.com/548639
Commit-Queue: Michael Stanton <mvstanton@chromium.org>
Reviewed-by: Benedikt Meurer <bmeurer@chromium.org>
Reviewed-by: Daniel Clifford <danno@chromium.org>
Cr-Commit-Position: refs/heads/master@{#46618}diff --git a/src/builtins/builtins-array-gen.cc b/src/builtins/builtins-array-gen.cc
index 5eb9dab..63f9fa9 100644
--- a/src/builtins/builtins-array-gen.cc
+++ b/src/builtins/builtins-array-gen.cc
@@ -1586,6 +1586,47 @@
&ArrayBuiltinCodeStubAssembler::NullPostLoopAction);
}
+TF_BUILTIN(ArrayMapLoopEagerDeoptContinuation, ArrayBuiltinCodeStubAssembler) {
+ Node* context = Parameter(Descriptor::kContext);
+ Node* receiver = Parameter(Descriptor::kReceiver);
+ Node* callbackfn = Parameter(Descriptor::kCallbackFn);
+ Node* this_arg = Parameter(Descriptor::kThisArg);
+ Node* array = Parameter(Descriptor::kArray);
+ Node* initial_k = Parameter(Descriptor::kInitialK);
+ Node* len = Parameter(Descriptor::kLength);
+
+ Callable stub(
+ Builtins::CallableFor(isolate(), Builtins::kArrayMapLoopContinuation));
+ Return(CallStub(stub, context, receiver, callbackfn, this_arg, array,
+ receiver, initial_k, len, UndefinedConstant()));
+}
+
+TF_BUILTIN(ArrayMapLoopLazyDeoptContinuation, ArrayBuiltinCodeStubAssembler) {
+ Node* context = Parameter(Descriptor::kContext);
+ Node* receiver = Parameter(Descriptor::kReceiver);
+ Node* callbackfn = Parameter(Descriptor::kCallbackFn);
+ Node* this_arg = Parameter(Descriptor::kThisArg);
+ Node* array = Parameter(Descriptor::kArray);
+ Node* initial_k = Parameter(Descriptor::kInitialK);
+ Node* len = Parameter(Descriptor::kLength);
+ Node* result = Parameter(Descriptor::kResult);
+
+ // This custom lazy deopt point is right after the callback. map() needs
+ // to pick up at the next step, which is setting the callback result in
+ // the output array. After incrementing k, we can glide into the loop
+ // continuation builtin.
+
+ // iii. Perform ? CreateDataPropertyOrThrow(A, Pk, mappedValue).
+ CallRuntime(Runtime::kCreateDataProperty, context, array, initial_k, result);
+ // Then we have to increment k before going on.
+ initial_k = NumberInc(initial_k);
+
+ Callable stub(
+ Builtins::CallableFor(isolate(), Builtins::kArrayMapLoopContinuation));
+ Return(CallStub(stub, context, receiver, callbackfn, this_arg, array,
+ receiver, initial_k, len, UndefinedConstant()));
+}
+
TF_BUILTIN(ArrayMap, ArrayBuiltinCodeStubAssembler) {
Node* argc =
ChangeInt32ToIntPtr(Parameter(BuiltinDescriptor::kArgumentsCount));
diff --git a/src/builtins/builtins-definitions.h b/src/builtins/builtins-definitions.h
index 7dea7bc..ccb10e3 100644
--- a/src/builtins/builtins-definitions.h
+++ b/src/builtins/builtins-definitions.h
@@ -318,6 +318,10 @@
/* ES6 #sec-array.prototype.foreach */ \
TFS(ArrayMapLoopContinuation, kReceiver, kCallbackFn, kThisArg, kArray, \
kObject, kInitialK, kLength, kTo) \
+ TFJ(ArrayMapLoopEagerDeoptContinuation, 5, kCallbackFn, kThisArg, kArray, \
+ kInitialK, kLength) \
+ TFJ(ArrayMapLoopLazyDeoptContinuation, 6, kCallbackFn, kThisArg, kArray, \
+ kInitialK, kLength, kResult) \
TFJ(ArrayMap, SharedFunctionInfo::kDontAdaptArgumentsSentinel) \
/* ES6 #sec-array.prototype.reduce */ \
TFS(ArrayReduceLoopContinuation, kReceiver, kCallbackFn, kThisArg, \
diff --git a/src/builtins/builtins.cc b/src/builtins/builtins.cc
index e1cda44..3f98d4f 100644
--- a/src/builtins/builtins.cc
+++ b/src/builtins/builtins.cc
@@ -169,6 +169,16 @@
isolate->builtins()->ArrayForEachLoopLazyDeoptContinuation();
return Callable(code, BuiltinDescriptor(isolate));
}
+ case kArrayMapLoopEagerDeoptContinuation: {
+ Handle<Code> code =
+ isolate->builtins()->ArrayMapLoopEagerDeoptContinuation();
+ return Callable(code, BuiltinDescriptor(isolate));
+ }
+ case kArrayMapLoopLazyDeoptContinuation: {
+ Handle<Code> code =
+ isolate->builtins()->ArrayMapLoopLazyDeoptContinuation();
+ return Callable(code, BuiltinDescriptor(isolate));
+ }
default:
UNREACHABLE();
}
diff --git a/src/compiler/access-builder.cc b/src/compiler/access-builder.cc
index 33bdc76..b2ef194 100644
--- a/src/compiler/access-builder.cc
+++ b/src/compiler/access-builder.cc
@@ -501,6 +501,14 @@
return access;
}
+// static
+FieldAccess AccessBuilder::ForMapBitField2() {
+ FieldAccess access = {
+ kTaggedBase, Map::kBitField2Offset, Handle<Name>(),
+ MaybeHandle<Map>(), TypeCache::Get().kUint8, MachineType::Uint8(),
+ kNoWriteBarrier};
+ return access;
+}
// static
FieldAccess AccessBuilder::ForMapBitField3() {
diff --git a/src/compiler/access-builder.h b/src/compiler/access-builder.h
index 7637d8c..31e48b9 100644
--- a/src/compiler/access-builder.h
+++ b/src/compiler/access-builder.h
@@ -167,6 +167,9 @@
// Provides access to Map::bit_field() byte.
static FieldAccess ForMapBitField();
+ // Provides access to Map::bit_field2() byte.
+ static FieldAccess ForMapBitField2();
+
// Provides access to Map::bit_field3() field.
static FieldAccess ForMapBitField3();
diff --git a/src/compiler/effect-control-linearizer.cc b/src/compiler/effect-control-linearizer.cc
index ef11ba8..f82133a 100644
--- a/src/compiler/effect-control-linearizer.cc
+++ b/src/compiler/effect-control-linearizer.cc
@@ -828,6 +828,8 @@
break;
case IrOpcode::kLoadHashMapValue:
result = LowerLoadHashMapValue(node);
+ case IrOpcode::kTransitionAndStoreElement:
+ LowerTransitionAndStoreElement(node);
break;
case IrOpcode::kFloat64RoundUp:
if (!LowerFloat64RoundUp(node).To(&result)) {
@@ -2814,6 +2816,164 @@
storage, index, value);
}
+void EffectControlLinearizer::TransitionElementsTo(Node* node, Node* array,
+ ElementsKind from,
+ ElementsKind to) {
+ DCHECK(IsMoreGeneralElementsKindTransition(from, to));
+ DCHECK(to == HOLEY_ELEMENTS || to == HOLEY_DOUBLE_ELEMENTS);
+
+ Handle<Map> target(to == HOLEY_ELEMENTS ? FastMapParameterOf(node->op())
+ : DoubleMapParameterOf(node->op()));
+ Node* target_map = __ HeapConstant(target);
+
+ if (IsSimpleMapChangeTransition(from, to)) {
+ __ StoreField(AccessBuilder::ForMap(), array, target_map);
+ } else {
+ // Instance migration, call out to the runtime for {array}.
+ Operator::Properties properties = Operator::kNoDeopt | Operator::kNoThrow;
+ Runtime::FunctionId id = Runtime::kTransitionElementsKind;
+ CallDescriptor const* desc = Linkage::GetRuntimeCallDescriptor(
+ graph()->zone(), id, 2, properties, CallDescriptor::kNoFlags);
+ __ Call(desc, __ CEntryStubConstant(1), array, target_map,
+ __ ExternalConstant(ExternalReference(id, isolate())),
+ __ Int32Constant(2), __ NoContextConstant());
+ }
+}
+
+Node* EffectControlLinearizer::IsElementsKindGreaterThan(
+ Node* kind, ElementsKind reference_kind) {
+ Node* ref_kind = __ Int32Constant(reference_kind);
+ Node* ret = __ Int32LessThanOrEqual(ref_kind, kind);
+ return ret;
+}
+
+void EffectControlLinearizer::LowerTransitionAndStoreElement(Node* node) {
+ Node* array = node->InputAt(0);
+ Node* index = node->InputAt(1);
+ Node* value = node->InputAt(2);
+
+ // Possibly transition array based on input and store.
+ //
+ // -- TRANSITION PHASE -----------------
+ // kind = ElementsKind(array)
+ // if value is not smi {
+ // if kind == HOLEY_SMI_ELEMENTS {
+ // if value is heap number {
+ // Transition array to HOLEY_DOUBLE_ELEMENTS
+ // } else {
+ // Transition array to HOLEY_ELEMENTS
+ // }
+ // } else if kind == HOLEY_DOUBLE_ELEMENTS {
+ // if value is not heap number {
+ // Transition array to HOLEY_ELEMENTS
+ // }
+ // }
+ // }
+ //
+ // -- STORE PHASE ----------------------
+ // if kind == HOLEY_DOUBLE_ELEMENTS {
+ // if value is smi {
+ // float_value = convert smi to float
+ // Store array[index] = float_value
+ // } else {
+ // float_value = value
+ // Store array[index] = float_value
+ // }
+ // } else {
+ // // kind is HOLEY_SMI_ELEMENTS or HOLEY_ELEMENTS
+ // Store array[index] = value
+ // }
+ //
+ Node* map = __ LoadField(AccessBuilder::ForMap(), array);
+ Node* kind;
+ {
+ Node* bit_field2 = __ LoadField(AccessBuilder::ForMapBitField2(), map);
+ Node* mask = __ Int32Constant(Map::ElementsKindBits::kMask);
+ Node* andit = __ Word32And(bit_field2, mask);
+ Node* shift = __ Int32Constant(Map::ElementsKindBits::kShift);
+ kind = __ Word32Shr(andit, shift);
+ }
+
+ auto do_store = __ MakeLabel<6>();
+ Node* check1 = ObjectIsSmi(value);
+ __ GotoIf(check1, &do_store);
+ {
+ // {value} is a HeapObject.
+ Node* check2 = IsElementsKindGreaterThan(kind, HOLEY_SMI_ELEMENTS);
+ auto if_array_not_fast_smi = __ MakeLabel<1>();
+ __ GotoIf(check2, &if_array_not_fast_smi);
+ {
+ // Transition {array} from HOLEY_SMI_ELEMENTS to HOLEY_DOUBLE_ELEMENTS or
+ // to HOLEY_ELEMENTS.
+ Node* value_map = __ LoadField(AccessBuilder::ForMap(), value);
+ Node* heap_number_map = __ HeapNumberMapConstant();
+ Node* check3 = __ WordEqual(value_map, heap_number_map);
+ auto if_value_not_heap_number = __ MakeLabel<1>();
+ __ GotoUnless(check3, &if_value_not_heap_number);
+ {
+ // {value} is a HeapNumber.
+ TransitionElementsTo(node, array, HOLEY_SMI_ELEMENTS,
+ HOLEY_DOUBLE_ELEMENTS);
+ __ Goto(&do_store);
+ }
+ __ Bind(&if_value_not_heap_number);
+ {
+ TransitionElementsTo(node, array, HOLEY_SMI_ELEMENTS, HOLEY_ELEMENTS);
+ __ Goto(&do_store);
+ }
+ }
+ __ Bind(&if_array_not_fast_smi);
+ {
+ Node* check3 = IsElementsKindGreaterThan(kind, HOLEY_ELEMENTS);
+ __ GotoUnless(check3, &do_store);
+ // We have double elements kind.
+ Node* value_map = __ LoadField(AccessBuilder::ForMap(), value);
+ Node* heap_number_map = __ HeapNumberMapConstant();
+ Node* check4 = __ WordEqual(value_map, heap_number_map);
+ __ GotoIf(check4, &do_store);
+ // But the value is not a heap number, so we must transition.
+ TransitionElementsTo(node, array, HOLEY_DOUBLE_ELEMENTS, HOLEY_ELEMENTS);
+ __ Goto(&do_store);
+ }
+ }
+
+ __ Bind(&do_store);
+ Node* elements = __ LoadField(AccessBuilder::ForJSObjectElements(), array);
+ Node* check2 = IsElementsKindGreaterThan(kind, HOLEY_ELEMENTS);
+ auto if_kind_is_double = __ MakeLabel<1>();
+ auto done = __ MakeLabel<3>();
+ __ GotoIf(check2, &if_kind_is_double);
+ {
+ // Our ElementsKind is HOLEY_SMI_ELEMENTS or HOLEY_ELEMENTS.
+ __ StoreElement(AccessBuilder::ForFixedArrayElement(HOLEY_ELEMENTS),
+ elements, index, value);
+ __ Goto(&done);
+ }
+ __ Bind(&if_kind_is_double);
+ {
+ // Our ElementsKind is HOLEY_DOUBLE_ELEMENTS.
+ Node* check1 = ObjectIsSmi(value);
+ auto do_double_store = __ MakeLabel<1>();
+ __ GotoUnless(check1, &do_double_store);
+ {
+ Node* int_value = ChangeSmiToInt32(value);
+ Node* float_value = __ ChangeInt32ToFloat64(int_value);
+ __ StoreElement(AccessBuilder::ForFixedDoubleArrayElement(), elements,
+ index, float_value);
+ __ Goto(&done);
+ }
+ __ Bind(&do_double_store);
+ {
+ Node* float_value =
+ __ LoadField(AccessBuilder::ForHeapNumberValue(), value);
+ __ StoreElement(AccessBuilder::ForFixedDoubleArrayElement(), elements,
+ index, float_value);
+ __ Goto(&done);
+ }
+ }
+ __ Bind(&done);
+}
+
Maybe<Node*> EffectControlLinearizer::LowerFloat64RoundUp(Node* node) {
// Nothing to be done if a fast hardware instruction is available.
if (machine()->Float64RoundUp().IsSupported()) {
diff --git a/src/compiler/effect-control-linearizer.h b/src/compiler/effect-control-linearizer.h
index 7e619a9..3cde8d7 100644
--- a/src/compiler/effect-control-linearizer.h
+++ b/src/compiler/effect-control-linearizer.h
@@ -121,6 +121,7 @@
void LowerStoreTypedElement(Node* node);
Node* LowerLookupHashStorageIndex(Node* node);
Node* LowerLoadHashMapValue(Node* node);
+ void LowerTransitionAndStoreElement(Node* node);
// Lowering of optional operators.
Maybe<Node*> LowerFloat64RoundUp(Node* node);
@@ -136,6 +137,7 @@
Node* frame_state);
Node* BuildFloat64RoundDown(Node* value);
Node* LowerStringComparison(Callable const& callable, Node* node);
+ Node* IsElementsKindGreaterThan(Node* kind, ElementsKind reference_kind);
Node* ChangeInt32ToSmi(Node* value);
Node* ChangeUint32ToSmi(Node* value);
@@ -144,6 +146,8 @@
Node* SmiMaxValueConstant();
Node* SmiShiftBitsConstant();
+ void TransitionElementsTo(Node* node, Node* array, ElementsKind from,
+ ElementsKind to);
Factory* factory() const;
Isolate* isolate() const;
diff --git a/src/compiler/js-call-reducer.cc b/src/compiler/js-call-reducer.cc
index 6129728..e05c956 100644
--- a/src/compiler/js-call-reducer.cc
+++ b/src/compiler/js-call-reducer.cc
@@ -721,6 +721,176 @@
return Replace(jsgraph()->UndefinedConstant());
}
+Reduction JSCallReducer::ReduceArrayMap(Handle<JSFunction> function,
+ Node* node) {
+ if (!FLAG_turbo_inline_array_builtins) return NoChange();
+ DCHECK_EQ(IrOpcode::kJSCall, node->opcode());
+ Node* outer_frame_state = NodeProperties::GetFrameStateInput(node);
+ Node* effect = NodeProperties::GetEffectInput(node);
+ Node* control = NodeProperties::GetControlInput(node);
+ Node* context = NodeProperties::GetContextInput(node);
+ CallParameters const& p = CallParametersOf(node->op());
+
+ // Try to determine the {receiver} map.
+ Node* receiver = NodeProperties::GetValueInput(node, 1);
+ Node* fncallback = node->op()->ValueInputCount() > 2
+ ? NodeProperties::GetValueInput(node, 2)
+ : jsgraph()->UndefinedConstant();
+ Node* this_arg = node->op()->ValueInputCount() > 3
+ ? NodeProperties::GetValueInput(node, 3)
+ : jsgraph()->UndefinedConstant();
+ ZoneHandleSet<Map> receiver_maps;
+ NodeProperties::InferReceiverMapsResult result =
+ NodeProperties::InferReceiverMaps(receiver, effect, &receiver_maps);
+ if (result != NodeProperties::kReliableReceiverMaps) {
+ return NoChange();
+ }
+ if (receiver_maps.size() != 1) return NoChange();
+ Handle<Map> receiver_map(receiver_maps[0]);
+ ElementsKind kind = receiver_map->elements_kind();
+ // TODO(danno): Handle holey Smi and Object fast elements kinds and double
+ // packed.
+ if (!IsFastPackedElementsKind(kind) || IsDoubleElementsKind(kind)) {
+ return NoChange();
+ }
+
+ // TODO(danno): map can throw. Hook up exceptional edges.
+ if (NodeProperties::IsExceptionalCall(node)) return NoChange();
+
+ // We want the input to be a generic Array.
+ const int map_index = Context::ArrayMapIndex(kind);
+ Handle<JSFunction> handle_constructor(
+ JSFunction::cast(
+ Map::cast(native_context()->get(map_index))->GetConstructor()),
+ isolate());
+ Node* array_constructor = jsgraph()->HeapConstant(handle_constructor);
+ if (receiver_map->prototype() !=
+ native_context()->get(Context::INITIAL_ARRAY_PROTOTYPE_INDEX)) {
+ return NoChange();
+ }
+
+ // And ensure that any changes to the Array species constructor cause deopt.
+ if (!isolate()->IsArraySpeciesLookupChainIntact()) return NoChange();
+
+ dependencies()->AssumePropertyCell(factory()->species_protector());
+
+ Node* k = jsgraph()->ZeroConstant();
+ Node* orig_map = jsgraph()->HeapConstant(receiver_map);
+
+ // Make sure the map hasn't changed before we construct the output array.
+ {
+ Node* array_map = effect =
+ graph()->NewNode(simplified()->LoadField(AccessBuilder::ForMap()),
+ receiver, effect, control);
+ Node* check_map =
+ graph()->NewNode(simplified()->ReferenceEqual(), array_map, orig_map);
+ effect =
+ graph()->NewNode(simplified()->CheckIf(), check_map, effect, control);
+ }
+
+ Node* original_length = graph()->NewNode(
+ simplified()->LoadField(AccessBuilder::ForJSArrayLength(PACKED_ELEMENTS)),
+ receiver, effect, control);
+
+ // This array should be HOLEY_SMI_ELEMENTS because of the non-zero length.
+ Node* a = control = effect = graph()->NewNode(
+ javascript()->CreateArray(1, Handle<AllocationSite>::null()),
+ array_constructor, array_constructor, original_length, context,
+ outer_frame_state, effect, control);
+
+ Node* loop = control = graph()->NewNode(common()->Loop(2), control, control);
+ Node* eloop = effect =
+ graph()->NewNode(common()->EffectPhi(2), effect, effect, loop);
+ Node* vloop = k = graph()->NewNode(
+ common()->Phi(MachineRepresentation::kTagged, 2), k, k, loop);
+
+ control = loop;
+ effect = eloop;
+
+ Node* continue_test =
+ graph()->NewNode(simplified()->NumberLessThan(), k, original_length);
+ Node* continue_branch = graph()->NewNode(common()->Branch(BranchHint::kTrue),
+ continue_test, control);
+
+ Node* if_true = graph()->NewNode(common()->IfTrue(), continue_branch);
+ Node* if_false = graph()->NewNode(common()->IfFalse(), continue_branch);
+ control = if_true;
+
+ std::vector<Node*> checkpoint_params(
+ {receiver, fncallback, this_arg, a, k, original_length});
+ const int stack_parameters = static_cast<int>(checkpoint_params.size());
+
+ Node* frame_state = CreateJavaScriptBuiltinContinuationFrameState(
+ jsgraph(), function, Builtins::kArrayMapLoopEagerDeoptContinuation,
+ node->InputAt(0), context, &checkpoint_params[0], stack_parameters,
+ outer_frame_state, ContinuationFrameStateMode::EAGER);
+
+ effect =
+ graph()->NewNode(common()->Checkpoint(), frame_state, effect, control);
+
+ // Make sure the map hasn't changed during the iteration
+ Node* array_map = effect =
+ graph()->NewNode(simplified()->LoadField(AccessBuilder::ForMap()),
+ receiver, effect, control);
+ Node* check_map =
+ graph()->NewNode(simplified()->ReferenceEqual(), array_map, orig_map);
+ effect =
+ graph()->NewNode(simplified()->CheckIf(), check_map, effect, control);
+
+ // Make sure that the access is still in bounds, since the callback could have
+ // changed the array's size.
+ Node* length = graph()->NewNode(
+ simplified()->LoadField(AccessBuilder::ForJSArrayLength(PACKED_ELEMENTS)),
+ receiver, effect, control);
+ k = effect =
+ graph()->NewNode(simplified()->CheckBounds(), k, length, effect, control);
+
+ // Reload the elements pointer before calling the callback, since the previous
+ // callback might have resized the array causing the elements buffer to be
+ // re-allocated.
+ Node* elements = graph()->NewNode(
+ simplified()->LoadField(AccessBuilder::ForJSObjectElements()), receiver,
+ effect, control);
+
+ Node* element = graph()->NewNode(
+ simplified()->LoadElement(AccessBuilder::ForFixedArrayElement()),
+ elements, k, effect, control);
+
+ Node* next_k =
+ graph()->NewNode(simplified()->NumberAdd(), k, jsgraph()->OneConstant());
+
+ // This frame state is dealt with by hand in
+ // ArrayMapLoopLazyDeoptContinuation.
+ frame_state = CreateJavaScriptBuiltinContinuationFrameState(
+ jsgraph(), function, Builtins::kArrayMapLoopLazyDeoptContinuation,
+ node->InputAt(0), context, &checkpoint_params[0], stack_parameters,
+ outer_frame_state, ContinuationFrameStateMode::LAZY);
+
+ Node* callback_value = control = effect = graph()->NewNode(
+ javascript()->Call(5, p.frequency()), fncallback, this_arg, element, k,
+ receiver, context, frame_state, effect, control);
+
+ Handle<Map> double_map(Map::cast(
+ native_context()->get(Context::ArrayMapIndex(HOLEY_DOUBLE_ELEMENTS))));
+ Handle<Map> fast_map(
+ Map::cast(native_context()->get(Context::ArrayMapIndex(HOLEY_ELEMENTS))));
+ effect = graph()->NewNode(
+ simplified()->TransitionAndStoreElement(double_map, fast_map), a, k,
+ callback_value, effect, control);
+
+ k = next_k;
+
+ loop->ReplaceInput(1, control);
+ vloop->ReplaceInput(1, k);
+ eloop->ReplaceInput(1, effect);
+
+ control = if_false;
+ effect = eloop;
+
+ ReplaceWithValue(node, a, effect, control);
+ return Replace(a);
+}
+
Reduction JSCallReducer::ReduceCallApiFunction(
Node* node, Handle<FunctionTemplateInfo> function_template_info) {
DCHECK_EQ(IrOpcode::kJSCall, node->opcode());
@@ -1077,6 +1247,8 @@
return ReduceSetPrototypeGetSize(node);
case Builtins::kArrayForEach:
return ReduceArrayForEach(function, node);
+ case Builtins::kArrayMap:
+ return ReduceArrayMap(function, node);
case Builtins::kReturnReceiver:
return ReduceReturnReceiver(node);
default:
diff --git a/src/compiler/js-call-reducer.h b/src/compiler/js-call-reducer.h
index fd8cfdf..d8a0490 100644
--- a/src/compiler/js-call-reducer.h
+++ b/src/compiler/js-call-reducer.h
@@ -69,6 +69,7 @@
Reduction ReduceReflectGetPrototypeOf(Node* node);
Reduction ReduceSetPrototypeGetSize(Node* node);
Reduction ReduceArrayForEach(Handle<JSFunction> function, Node* node);
+ Reduction ReduceArrayMap(Handle<JSFunction> function, Node* node);
Reduction ReduceCallOrConstructWithArrayLikeOrSpread(
Node* node, int arity, CallFrequency const& frequency);
Reduction ReduceJSConstruct(Node* node);
diff --git a/src/compiler/js-create-lowering.h b/src/compiler/js-create-lowering.h
index b14c111..e122d4c 100644
--- a/src/compiler/js-create-lowering.h
+++ b/src/compiler/js-create-lowering.h
@@ -75,6 +75,8 @@
ElementsKind elements_kind, int capacity,
PretenureFlag pretenure);
Node* AllocateElements(Node* effect, Node* control,
+ ElementsKind elements_kind, Node* capacity_and_length);
+ Node* AllocateElements(Node* effect, Node* control,
ElementsKind elements_kind,
std::vector<Node*> const& values,
PretenureFlag pretenure);
diff --git a/src/compiler/load-elimination.cc b/src/compiler/load-elimination.cc
index 282122d..6dd27d3 100644
--- a/src/compiler/load-elimination.cc
+++ b/src/compiler/load-elimination.cc
@@ -114,6 +114,8 @@
return ReduceLoadElement(node);
case IrOpcode::kStoreElement:
return ReduceStoreElement(node);
+ case IrOpcode::kTransitionAndStoreElement:
+ return ReduceTransitionAndStoreElement(node);
case IrOpcode::kStoreTypedElement:
return ReduceStoreTypedElement(node);
case IrOpcode::kLookupHashStorageIndex:
@@ -784,6 +786,30 @@
return UpdateState(node, state);
}
+Reduction LoadElimination::ReduceTransitionAndStoreElement(Node* node) {
+ Node* const object = NodeProperties::GetValueInput(node, 0);
+ Handle<Map> double_map(DoubleMapParameterOf(node->op()));
+ Handle<Map> fast_map(FastMapParameterOf(node->op()));
+ Node* const effect = NodeProperties::GetEffectInput(node);
+ AbstractState const* state = node_states_.Get(effect);
+ if (state == nullptr) return NoChange();
+
+ // We need to add the double and fast maps to the set of possible maps for
+ // this object, because we don't know which of those we'll transition to.
+ // Additionally, we should kill all alias information.
+ ZoneHandleSet<Map> object_maps;
+ if (state->LookupMaps(object, &object_maps)) {
+ object_maps.insert(double_map, zone());
+ object_maps.insert(fast_map, zone());
+ state = state->KillMaps(object, zone());
+ state = state->AddMaps(object, object_maps, zone());
+ }
+ // Kill the elements as well.
+ state =
+ state->KillField(object, FieldIndexOf(JSObject::kElementsOffset), zone());
+ return UpdateState(node, state);
+}
+
Reduction LoadElimination::ReduceLoadField(Node* node) {
FieldAccess const& access = FieldAccessOf(node->op());
Node* const object = NodeProperties::GetValueInput(node, 0);
@@ -1110,6 +1136,15 @@
}
break;
}
+ case IrOpcode::kTransitionAndStoreElement: {
+ Node* const object = NodeProperties::GetValueInput(current, 0);
+ // Invalidate what we know about the {object}s map.
+ state = state->KillMaps(object, zone());
+ // Kill the elements as well.
+ state = state->KillField(
+ object, FieldIndexOf(JSObject::kElementsOffset), zone());
+ break;
+ }
case IrOpcode::kStoreField: {
FieldAccess const& access = FieldAccessOf(current->op());
Node* const object = NodeProperties::GetValueInput(current, 0);
diff --git a/src/compiler/load-elimination.h b/src/compiler/load-elimination.h
index fb32c6f..dc65a12 100644
--- a/src/compiler/load-elimination.h
+++ b/src/compiler/load-elimination.h
@@ -320,6 +320,7 @@
Reduction ReduceStoreField(Node* node);
Reduction ReduceLoadElement(Node* node);
Reduction ReduceStoreElement(Node* node);
+ Reduction ReduceTransitionAndStoreElement(Node* node);
Reduction ReduceStoreTypedElement(Node* node);
Reduction ReduceLookupHashStorageIndex(Node* node);
Reduction ReduceEffectPhi(Node* node);
diff --git a/src/compiler/opcodes.h b/src/compiler/opcodes.h
index cda1a7a..c829a39 100644
--- a/src/compiler/opcodes.h
+++ b/src/compiler/opcodes.h
@@ -346,6 +346,7 @@
V(StoreBuffer) \
V(StoreElement) \
V(StoreTypedElement) \
+ V(TransitionAndStoreElement) \
V(ObjectIsDetectableCallable) \
V(ObjectIsNaN) \
V(ObjectIsNonCallable) \
diff --git a/src/compiler/simplified-lowering.cc b/src/compiler/simplified-lowering.cc
index f525c28..19578fc 100644
--- a/src/compiler/simplified-lowering.cc
+++ b/src/compiler/simplified-lowering.cc
@@ -2591,6 +2591,14 @@
}
return;
}
+ case IrOpcode::kTransitionAndStoreElement: {
+ ProcessInput(node, 0, UseInfo::AnyTagged()); // array
+ ProcessInput(node, 1, UseInfo::TruncatingWord32()); // index
+ ProcessInput(node, 2, UseInfo::AnyTagged()); // value
+ ProcessRemainingInputs(node, 3);
+ SetOutput(node, MachineRepresentation::kNone);
+ return;
+ }
case IrOpcode::kLoadTypedElement: {
MachineRepresentation const rep =
MachineRepresentationFromArrayType(ExternalArrayTypeOf(node->op()));
diff --git a/src/compiler/simplified-operator.cc b/src/compiler/simplified-operator.cc
index 98d1642..29e4669 100644
--- a/src/compiler/simplified-operator.cc
+++ b/src/compiler/simplified-operator.cc
@@ -348,6 +348,55 @@
return OpParameter<ElementsTransition>(op);
}
+namespace {
+
+// Parameters for the TransitionAndStoreElement opcode.
+class TransitionAndStoreElementParameters final {
+ public:
+ TransitionAndStoreElementParameters(Handle<Map> double_map,
+ Handle<Map> fast_map);
+
+ Handle<Map> double_map() const { return double_map_; }
+ Handle<Map> fast_map() const { return fast_map_; }
+
+ private:
+ Handle<Map> const double_map_;
+ Handle<Map> const fast_map_;
+};
+
+TransitionAndStoreElementParameters::TransitionAndStoreElementParameters(
+ Handle<Map> double_map, Handle<Map> fast_map)
+ : double_map_(double_map), fast_map_(fast_map) {}
+
+bool operator==(TransitionAndStoreElementParameters const& lhs,
+ TransitionAndStoreElementParameters const& rhs) {
+ return lhs.fast_map().address() == rhs.fast_map().address() &&
+ lhs.double_map().address() == rhs.double_map().address();
+}
+
+size_t hash_value(TransitionAndStoreElementParameters parameters) {
+ return base::hash_combine(parameters.fast_map().address(),
+ parameters.double_map().address());
+}
+
+std::ostream& operator<<(std::ostream& os,
+ TransitionAndStoreElementParameters parameters) {
+ return os << "fast-map" << Brief(*parameters.fast_map()) << " double-map"
+ << Brief(*parameters.double_map());
+}
+
+} // namespace
+
+Handle<Map> DoubleMapParameterOf(const Operator* op) {
+ DCHECK(op->opcode() == IrOpcode::kTransitionAndStoreElement);
+ return OpParameter<TransitionAndStoreElementParameters>(op).double_map();
+}
+
+Handle<Map> FastMapParameterOf(const Operator* op) {
+ DCHECK(op->opcode() == IrOpcode::kTransitionAndStoreElement);
+ return OpParameter<TransitionAndStoreElementParameters>(op).fast_map();
+}
+
std::ostream& operator<<(std::ostream& os, NumberOperationHint hint) {
switch (hint) {
case NumberOperationHint::kSignedSmall:
@@ -1053,6 +1102,15 @@
ACCESS_OP_LIST(ACCESS)
#undef ACCESS
+const Operator* SimplifiedOperatorBuilder::TransitionAndStoreElement(
+ Handle<Map> double_map, Handle<Map> fast_map) {
+ TransitionAndStoreElementParameters parameters(double_map, fast_map);
+ return new (zone()) Operator1<TransitionAndStoreElementParameters>(
+ IrOpcode::kTransitionAndStoreElement,
+ Operator::kNoDeopt | Operator::kNoThrow, "TransitionAndStoreElement", 3,
+ 1, 1, 0, 1, 0, parameters);
+}
+
} // namespace compiler
} // namespace internal
} // namespace v8
diff --git a/src/compiler/simplified-operator.h b/src/compiler/simplified-operator.h
index e071420..f2739ace 100644
--- a/src/compiler/simplified-operator.h
+++ b/src/compiler/simplified-operator.h
@@ -228,6 +228,10 @@
ElementsTransition const& ElementsTransitionOf(const Operator* op)
WARN_UNUSED_RESULT;
+// Parameters for TransitionAndStoreElement.
+Handle<Map> DoubleMapParameterOf(const Operator* op);
+Handle<Map> FastMapParameterOf(const Operator* op);
+
// A hint for speculative number operations.
enum class NumberOperationHint : uint8_t {
kSignedSmall, // Inputs were always Smi so far, output was in Smi range.
@@ -493,6 +497,10 @@
// store-element [base + index], value
const Operator* StoreElement(ElementAccess const&);
+ // store-element [base + index], value, only with fast arrays.
+ const Operator* TransitionAndStoreElement(Handle<Map> double_map,
+ Handle<Map> fast_map);
+
// load-typed-element buffer, [base + external + index]
const Operator* LoadTypedElement(ExternalArrayType const&);
diff --git a/src/compiler/typer.cc b/src/compiler/typer.cc
index 18fbefd..973b7fe 100644
--- a/src/compiler/typer.cc
+++ b/src/compiler/typer.cc
@@ -1963,6 +1963,10 @@
UNREACHABLE();
}
+Type* Typer::Visitor::TypeTransitionAndStoreElement(Node* node) {
+ UNREACHABLE();
+}
+
Type* Typer::Visitor::TypeStoreTypedElement(Node* node) {
UNREACHABLE();
}
diff --git a/src/compiler/verifier.cc b/src/compiler/verifier.cc
index 9ef842a..dbb0546 100644
--- a/src/compiler/verifier.cc
+++ b/src/compiler/verifier.cc
@@ -1286,6 +1286,9 @@
// CheckValueInputIs(node, 1, ElementAccessOf(node->op()).type));
CheckNotTyped(node);
break;
+ case IrOpcode::kTransitionAndStoreElement:
+ CheckNotTyped(node);
+ break;
case IrOpcode::kStoreTypedElement:
CheckNotTyped(node);
break;
diff --git a/test/mjsunit/optimized-map.js b/test/mjsunit/optimized-map.js
new file mode 100644
index 0000000..604b8b3d
--- /dev/null
+++ b/test/mjsunit/optimized-map.js
@@ -0,0 +1,379 @@
+// Copyright 2017 the V8 project authors. All rights reserved.
+// Use of this source code is governed by a BSD-style license that can be
+// found in the LICENSE file.
+
+// Flags: --allow-natives-syntax --expose-gc --turbo-inline-array-builtins
+// Flags: --opt --no-always-opt
+
+var a = [0, 1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,0,0];
+var b = [1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25];
+var c = [1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25];
+
+// Unknown field access leads to soft-deopt unrelated to map, should still
+// lead to correct result.
+(function() {
+ var result = 0;
+ var eagerDeoptInCalled = function(deopt) {
+ var callback = function(v,i,o) {
+ result += v;
+ if (i == 13 && deopt) {
+ a.abc = 25;
+ }
+ return v;
+ }
+ a.map(callback);
+ }
+ eagerDeoptInCalled();
+ eagerDeoptInCalled();
+ %OptimizeFunctionOnNextCall(eagerDeoptInCalled);
+ eagerDeoptInCalled();
+ eagerDeoptInCalled(true);
+ eagerDeoptInCalled();
+ assertEquals(1500, result);
+})();
+
+// Length change detected during loop, must cause properly handled eager deopt.
+(function() {
+ var result = 0;
+ var eagerDeoptInCalled = function(deopt) {
+ var callback = function(v,i,o) {
+ result += v;
+ a.length = (i == 13 && deopt) ? 25 : 27;
+ return v;
+ }
+ a.map(callback);
+ }
+ eagerDeoptInCalled();
+ eagerDeoptInCalled();
+ %OptimizeFunctionOnNextCall(eagerDeoptInCalled);
+ eagerDeoptInCalled();
+ eagerDeoptInCalled(true);
+ eagerDeoptInCalled();
+ assertEquals(1500, result);
+})();
+
+// Escape analyzed array
+(function() {
+ var result = 0;
+ var eagerDeoptInCalled = function(deopt) {
+ var a_noescape = [0,1,2,3,4,5];
+ var callback = function(v,i,o) {
+ result += v;
+ if (i == 13 && deopt) {
+ a_noescape.length = 25;
+ }
+ return v;
+ }
+ a_noescape.map(callback);
+ }
+ eagerDeoptInCalled();
+ eagerDeoptInCalled();
+ %OptimizeFunctionOnNextCall(eagerDeoptInCalled);
+ eagerDeoptInCalled();
+ eagerDeoptInCalled(true);
+ eagerDeoptInCalled();
+ assertEquals(75, result);
+})();
+
+// Escape analyzed array where callback function isn't inlined, forcing a lazy
+// deopt with GC that relies on the stashed-away return result fro the lazy
+// deopt being properly stored in a place on the stack that gets GC'ed.
+(function() {
+ var result = 0;
+ var lazyDeopt = function(deopt) {
+ var b = [1,2,3];
+ var callback = function(v,i,o) {
+ result += i;
+ if (i == 1 && deopt) {
+ %DeoptimizeFunction(lazyDeopt);
+ }
+ gc(); gc();
+ return v;
+ };
+ %NeverOptimizeFunction(callback);
+ b.map(callback);
+ }
+ lazyDeopt();
+ lazyDeopt();
+ %OptimizeFunctionOnNextCall(lazyDeopt);
+ lazyDeopt();
+ lazyDeopt(true);
+ lazyDeopt();
+})();
+
+// Lazy deopt from runtime call from inlined callback function.
+(function() {
+ var result = 0;
+ var lazyDeopt = function(deopt) {
+ var callback = function(v,i,o) {
+ result += i;
+ if (i == 13 && deopt) {
+ %DeoptimizeNow();
+ }
+ return v;
+ }
+ b.map(callback);
+ }
+ lazyDeopt();
+ lazyDeopt();
+ %OptimizeFunctionOnNextCall(lazyDeopt);
+ lazyDeopt();
+ lazyDeopt(true);
+ lazyDeopt();
+ assertEquals(1500, result);
+})();
+
+// Lazy deopt from runtime call from non-inline callback function.
+(function() {
+ var result = 0;
+ var lazyDeopt = function(deopt) {
+ var callback = function(v,i,o) {
+ result += i;
+ if (i == 13 && deopt) {
+ %DeoptimizeNow();
+ }
+ return v;
+ };
+ %NeverOptimizeFunction(callback);
+ b.map(callback);
+ }
+ lazyDeopt();
+ lazyDeopt();
+ %OptimizeFunctionOnNextCall(lazyDeopt);
+ lazyDeopt();
+ lazyDeopt(true);
+ lazyDeopt();
+ assertEquals(1500, result);
+})();
+
+(function() {
+ var result = 0;
+ var lazyDeopt = function(deopt) {
+ var callback = function(v,i,o) {
+ result += i;
+ if (i == 13 && deopt) {
+ %DeoptimizeNow();
+ gc();
+ gc();
+ gc();
+ }
+ return v;
+ }
+ c.map(callback);
+ }
+ lazyDeopt();
+ lazyDeopt();
+ %OptimizeFunctionOnNextCall(lazyDeopt);
+ lazyDeopt();
+ lazyDeopt(true);
+ lazyDeopt();
+ assertEquals(1500, result);
+})();
+
+// Call to a.map is done inside a try-catch block and the callback function
+// being called actually throws.
+(function() {
+ var caught = false;
+ var result = 0;
+ var lazyDeopt = function(deopt) {
+ var callback = function(v,i,o) {
+ result += i;
+ if (i == 1 && deopt) {
+ throw("a");
+ }
+ return v;
+ }
+ try {
+ c.map(callback);
+ } catch (e) {
+ caught = true;
+ }
+ }
+ lazyDeopt();
+ lazyDeopt();
+ %OptimizeFunctionOnNextCall(lazyDeopt);
+ lazyDeopt();
+ assertDoesNotThrow(lazyDeopt.bind(this, true));
+ assertTrue(caught);
+ lazyDeopt();
+})();
+
+// Call to a.map is done inside a try-catch block and the callback function
+// being called actually throws, but the callback is not inlined.
+(function() {
+ var caught = false;
+ var result = 0;
+ var lazyDeopt = function(deopt) {
+ var callback = function(v,i,o) {
+ result += i;
+ if (i == 1 && deopt) {
+ throw("a");
+ }
+ return v;
+ };
+ %NeverOptimizeFunction(callback);
+ try {
+ c.map(callback);
+ } catch (e) {
+ caught = true;
+ }
+ }
+ lazyDeopt();
+ lazyDeopt();
+ %OptimizeFunctionOnNextCall(lazyDeopt);
+ lazyDeopt();
+ assertDoesNotThrow(lazyDeopt.bind(this, true));
+ assertTrue(caught);
+ lazyDeopt();
+})();
+
+(function() {
+ var re = /Array\.map/;
+ var lazyDeopt = function(deopt) {
+ var b = [1,2,3];
+ var result = 0;
+ var callback = function(v,i,o) {
+ result += v;
+ if (i == 1) {
+ var e = new Error();
+ assertTrue(re.exec(e.stack) !== null);
+ }
+ return v;
+ };
+ var o = [1,2,3];
+ b.map(callback);
+ }
+ lazyDeopt();
+ lazyDeopt();
+ %OptimizeFunctionOnNextCall(lazyDeopt);
+ lazyDeopt();
+})();
+
+(function() {
+ var re = /Array\.map/;
+ var lazyDeopt = function(deopt) {
+ var b = [1,2,3];
+ var result = 0;
+ var callback = function(v,i,o) {
+ result += v;
+ if (i == 1) {
+ var e = new Error();
+ assertTrue(re.exec(e.stack) !== null);
+ }
+ return v;
+ };
+ %NeverOptimizeFunction(callback);
+ var o = [1,2,3];
+ b.map(callback);
+ }
+ lazyDeopt();
+ lazyDeopt();
+ %OptimizeFunctionOnNextCall(lazyDeopt);
+ lazyDeopt();
+})();
+
+(function() {
+ var re = /Array\.map/;
+ var lazyDeopt = function(deopt) {
+ var b = [1,2,3];
+ var result = 0;
+ var callback = function(v,i,o) {
+ result += v;
+ if (i == 1) {
+ %DeoptimizeNow();
+ } else if (i == 2) {
+ var e = new Error();
+ assertTrue(re.exec(e.stack) !== null);
+ }
+ return v;
+ };
+ var o = [1,2,3];
+ b.map(callback);
+ }
+ lazyDeopt();
+ lazyDeopt();
+ %OptimizeFunctionOnNextCall(lazyDeopt);
+ lazyDeopt();
+})();
+
+(function() {
+ var re = /Array\.map/;
+ var a = [1,2,3];
+ var result = 0;
+ var lazyDeopt = function() {
+ var callback = function(v,i,o) {
+ result += i;
+ if (i == 1) {
+ %DeoptimizeFunction(lazyDeopt);
+ throw new Error();
+ }
+ return v;
+ };
+ a.map(callback);
+ }
+ assertThrows(() => lazyDeopt());
+ assertThrows(() => lazyDeopt());
+ try {
+ lazyDeopt();
+ } catch (e) {
+ assertTrue(re.exec(e.stack) !== null);
+ }
+ %OptimizeFunctionOnNextCall(lazyDeopt);
+ try {
+ lazyDeopt();
+ } catch (e) {
+ assertTrue(re.exec(e.stack) !== null);
+ }
+})();
+
+// Verify that we remain in optimized code despite transitions in the output
+// array.
+(function() {
+ var result = 0;
+ var to_double = function() {
+ var callback = function(v,i,o) {
+ result += v;
+ if (i < 5) {
+ // First transition the output array to PACKED_DOUBLE_ELEMENTS.
+ return v + 0.5;
+ } else if (i < 10) {
+ // Then return smi values and make sure they can live in the double
+ // array.
+ return v;
+ } else {
+ // Later, to PACKED_ELEMENTS.
+ return v + 'hello';
+ }
+ }
+ return c.map(callback);
+ }
+ to_double();
+ to_double();
+ %OptimizeFunctionOnNextCall(to_double);
+ var output = to_double();
+ assertEquals(975, result);
+ assertEquals("11hello", output[10]);
+ assertOptimized(to_double);
+})();
+
+// Messing with the Array species constructor causes deoptimization.
+(function() {
+ var result = 0;
+ var a = [1,2,3];
+ var species_breakage = function() {
+ var callback = function(v,i,o) {
+ result += v;
+ return v;
+ }
+ a.map(callback);
+ }
+ species_breakage();
+ species_breakage();
+ %OptimizeFunctionOnNextCall(species_breakage);
+ species_breakage();
+ a.constructor = {};
+ a.constructor[Symbol.species] = function() {};
+ species_breakage();
+ assertUnoptimized(species_breakage);
+ assertEquals(24, result);
+})();
