[builtins] Improve performance of array.prototype.filter and map

src/builtins/builtins-array-gen.cc

 // 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.
 
 #include "src/builtins/builtins-utils-gen.h"
 #include "src/builtins/builtins.h"
 #include "src/code-stub-assembler.h"
 
 namespace v8 {
 namespace internal {
 
 class ArrayBuiltinCodeStubAssembler : public CodeStubAssembler {
  public:
   explicit ArrayBuiltinCodeStubAssembler(compiler::CodeAssemblerState* state)
       : CodeStubAssembler(state),
         k_(this, MachineRepresentation::kTagged, SmiConstant(0)),
         a_(this, MachineRepresentation::kTagged, SmiConstant(0)),
         to_(this, MachineRepresentation::kTagged, SmiConstant(0)) {}
 
   typedef std::function<Node*(ArrayBuiltinCodeStubAssembler* masm)>
       BuiltinResultGenerator;
 
   typedef std::function<void(ArrayBuiltinCodeStubAssembler* masm)>
       BuiltinResultIndexInitializer;
 
   typedef std::function<Node*(ArrayBuiltinCodeStubAssembler* masm,
-                              Node* k_value, Node* k)>
+                              ElementsKind o_kind, Node* k_value, Node* k)>
       CallResultProcessor;
 
   typedef std::function<void(ArrayBuiltinCodeStubAssembler* masm)>
       PostLoopAction;
 
   Node* ForEachResultGenerator() { return UndefinedConstant(); }
 
-  Node* ForEachProcessor(Node* k_value, Node* k) {
+  Node* ForEachProcessor(ElementsKind o_kind, Node* k_value, Node* k) {
     CallJS(CodeFactory::Call(isolate()), context(), callbackfn(), this_arg(),
            k_value, k, o());
     return a();
   }
 
   Node* SomeResultGenerator() { return FalseConstant(); }
 
-  Node* SomeProcessor(Node* k_value, Node* k) {
+  Node* SomeProcessor(ElementsKind o_kind, Node* k_value, Node* k) {
     Node* value = CallJS(CodeFactory::Call(isolate()), context(), callbackfn(),
                          this_arg(), k_value, k, o());
     Label false_continue(this), return_true(this);
     BranchIfToBooleanIsTrue(value, &return_true, &false_continue);
     Bind(&return_true);
     Return(TrueConstant());
     Bind(&false_continue);
     return a();
   }
 
   Node* EveryResultGenerator() { return TrueConstant(); }
 
-  Node* EveryProcessor(Node* k_value, Node* k) {
+  Node* EveryProcessor(ElementsKind o_kind, Node* k_value, Node* k) {
     Node* value = CallJS(CodeFactory::Call(isolate()), context(), callbackfn(),
                          this_arg(), k_value, k, o());
     Label true_continue(this), return_false(this);
     BranchIfToBooleanIsTrue(value, &true_continue, &return_false);
     Bind(&return_false);
     Return(FalseConstant());
     Bind(&true_continue);
     return a();
   }
 
@@ skipping 24 matching lines @@
     // 9. Else initialValue is not present,
     Bind(&no_initial_value);
 
     // a. Let kPresent be false.
     a.Bind(TheHoleConstant());
     Goto(&done);
     Bind(&done);
     return a.value();
   }
 
-  Node* ReduceProcessor(Node* k_value, Node* k) {
+  Node* ReduceProcessor(ElementsKind o_kind, Node* k_value, Node* k) {
     Variable result(this, MachineRepresentation::kTagged);
     Label done(this, {&result}), initial(this);
     GotoIf(WordEqual(a(), TheHoleConstant()), &initial);
     result.Bind(CallJS(CodeFactory::Call(isolate()), context(), callbackfn(),
                        UndefinedConstant(), a(), k_value, k, o()));
     Goto(&done);
 
     Bind(&initial);
     result.Bind(k_value);
     Goto(&done);
 
     Bind(&done);
     return result.value();
   }
 
   void ReducePostLoopAction() {
     Label ok(this);
     GotoIf(WordNotEqual(a(), TheHoleConstant()), &ok);
     CallRuntime(Runtime::kThrowTypeError, context(),
                 SmiConstant(MessageTemplate::kReduceNoInitial));
     Unreachable();
     Bind(&ok);
   }
 
   Node* FilterResultGenerator() {
     // 7. Let A be ArraySpeciesCreate(O, 0).
     return ArraySpeciesCreate(context(), o(), SmiConstant(0));
   }
 
-  Node* FilterProcessor(Node* k_value, Node* k) {
+  Node* FilterProcessor(ElementsKind o_kind, Node* k_value, Node* k) {
     // ii. Let selected be ToBoolean(? Call(callbackfn, T, kValue, k, O)).
     Node* selected = CallJS(CodeFactory::Call(isolate()), context(),
                             callbackfn(), this_arg(), k_value, k, o());
     Label true_continue(this, &to_), false_continue(this);
     BranchIfToBooleanIsTrue(selected, &true_continue, &false_continue);
     Bind(&true_continue);
-    // iii. If selected is true, then...
     {
+      // iii. If selected is true, then...
+      Label after_work(this, &to_);
+      if (o_kind < DICTIONARY_ELEMENTS) {

[danno, 2017/04/03 15:35:27]

Please use the predicates in elements-kind.h, e.g. IsFastElementKind().

[mvstanton, 2017/04/06 08:57:36]

Per our discussion, I'll just remove the o_kind parameter (still, good
suggestion!).

+        Node* kind = nullptr;
+
+        // If a() is a JSArray, we can have a fast path.
+        Label fast(this);
+        Label runtime(this);
+        Label object_push_pre(this), object_push(this), double_push(this);

[danno, 2017/04/03 15:35:27]

I think you can make this slightly better. Since you have the elements kind, you
only have to generate the code for either FAST_ELEMENTS or FAST_DOUBLE_ELEMENTS
at compile time.

[mvstanton, 2017/04/06 08:57:36]

Right, because of the vagaries of what can happen with the species constructor,
I'm compelled to handle all cases. There might be some improvements available at
the margin for later.

+        BranchIfFastJSArray(a(), context(), FastJSArrayAccessMode::ANY_ACCESS,
+                            &fast, &runtime);
+
+        Bind(&fast);
+        {
+          kind = EnsureArrayPushable(a(), &runtime);
+          GotoIf(Int32GreaterThan(kind, Int32Constant(FAST_HOLEY_SMI_ELEMENTS)),
+                 &object_push_pre);
+
+          BuildAppendJSArray(FAST_SMI_ELEMENTS, a(), k_value, &runtime);
+          Goto(&after_work);
+        }
+
+        Bind(&object_push_pre);
+        {
+          Branch(Int32GreaterThan(kind, Int32Constant(FAST_HOLEY_ELEMENTS)),
+                 &double_push, &object_push);
+        }
+
+        Bind(&object_push);
+        {
+          BuildAppendJSArray(FAST_ELEMENTS, a(), k_value, &runtime);
+          Goto(&after_work);
+        }
+
+        Bind(&double_push);
+        {
+          BuildAppendJSArray(FAST_DOUBLE_ELEMENTS, a(), k_value, &runtime);
+          Goto(&after_work);
+        }
+
+        Bind(&runtime);
+      }
+
       // 1. Perform ? CreateDataPropertyOrThrow(A, ToString(to), kValue).
       CallRuntime(Runtime::kCreateDataProperty, context(), a(), to_.value(),
                   k_value);
+      Goto(&after_work);
 
-      // 2. Increase to by 1.
-      to_.Bind(NumberInc(to_.value()));
-      Goto(&false_continue);
+      Bind(&after_work);
+      {
+        // 2. Increase to by 1.
+        to_.Bind(NumberInc(to_.value()));
+        Goto(&false_continue);
+      }
     }
     Bind(&false_continue);
     return a();
   }
 
   Node* MapResultGenerator() {
     // 5. Let A be ? ArraySpeciesCreate(O, len).
     return ArraySpeciesCreate(context(), o(), len_);
   }
 
-  Node* MapProcessor(Node* k_value, Node* k) {
+  Node* MapProcessor(ElementsKind o_kind, Node* k_value, Node* k) {
     //  i. Let kValue be ? Get(O, Pk). Performed by the caller of MapProcessor.
     // ii. Let mappedValue be ? Call(callbackfn, T, kValue, k, O).
     Node* mappedValue = CallJS(CodeFactory::Call(isolate()), context(),
                                callbackfn(), this_arg(), k_value, k, o());
 
+    Label finished(this);
+    if (o_kind < DICTIONARY_ELEMENTS) {
+      Node* kind = nullptr;
+      Node* elements = nullptr;
+
+      // If a() is a JSArray, we can have a fast path.
+      // mode is SMI_PARAMETERS because k has tagged representation.
+      ParameterMode mode = SMI_PARAMETERS;
+      Label fast(this);
+      Label runtime(this);
+      Label object_push_pre(this), object_push(this), double_push(this);
+      BranchIfFastJSArray(a(), context(), FastJSArrayAccessMode::ANY_ACCESS,
+                          &fast, &runtime);
+
+      Bind(&fast);
+      {
+        kind = EnsureArrayPushable(a(), &runtime);
+        elements = LoadElements(a());
+        GotoIf(Int32GreaterThan(kind, Int32Constant(FAST_HOLEY_SMI_ELEMENTS)),

[danno, 2017/04/03 15:35:27]

Consider adding/using existing predicates in code-stub-assembler.h like
"IsFastElementsKind" and "IsHoleyFastElementsKind".

[mvstanton, 2017/04/06 08:57:36]

I use a "greater than" metaphor to avoid multiple comparisons.

+               &object_push_pre);
+
+        TryStoreArrayElement(FAST_SMI_ELEMENTS, mode, &runtime, elements, k,
+                             mappedValue);
+        Goto(&finished);
+      }
+
+      Bind(&object_push_pre);
+      {
+        Branch(Int32GreaterThan(kind, Int32Constant(FAST_HOLEY_ELEMENTS)),
+               &double_push, &object_push);
+      }
+
+      Bind(&object_push);
+      {
+        TryStoreArrayElement(FAST_ELEMENTS, mode, &runtime, elements, k,
+                             mappedValue);
+        Goto(&finished);
+      }
+
+      Bind(&double_push);
+      {
+        TryStoreArrayElement(FAST_DOUBLE_ELEMENTS, mode, &runtime, elements, k,
+                             mappedValue);
+        Goto(&finished);
+      }
+
+      Bind(&runtime);
+    }
+
     // iii. Perform ? CreateDataPropertyOrThrow(A, Pk, mappedValue).
     CallRuntime(Runtime::kCreateDataProperty, context(), a(), k, mappedValue);
+    Goto(&finished);
+
+    Bind(&finished);
     return a();
   }
 
   void NullPostLoopAction() {}
 
  protected:
   Node* context() { return context_; }
   Node* receiver() { return receiver_; }
   Node* new_target() { return new_target_; }
   Node* o() { return o_; }
@@ skipping 238 matching lines @@
 
       // d. If kPresent is true, then
       GotoIf(WordNotEqual(k_present, TrueConstant()), &done_element);
 
       // i. Let kValue be Get(O, Pk).
       // ii. ReturnIfAbrupt(kValue).
       Node* k_value = GetProperty(context(), o(), k());
 
       // iii. Let funcResult be Call(callbackfn, T, «kValue, k, O»).
       // iv. ReturnIfAbrupt(funcResult).
-      a_.Bind(processor(this, k_value, k()));
+      a_.Bind(processor(this, DICTIONARY_ELEMENTS, k_value, k()));

[danno, 2017/04/03 15:35:27]

Although I know what you mean here, the elements may not be dictionary at this
point. In fact, they can be anything. I am leaning towards adding a new
ElementsKind kind of like "NO_ELEMENTS", but called "UNKNOWN_ELEMENTS" and to
pass that here.

       Goto(&done_element);
 
       Bind(&done_element);
 
       if (direction == ForEachDirection::kForward) {
         // e. Increase k by 1.
         k_.Bind(NumberInc(k()));
       } else {
         // e. Decrease k by 1.
         k_.Bind(NumberDec(k()));
@@ skipping 32 matching lines @@
       Node* elements = LoadElements(o_);
       Node* base_ptr =
           LoadObjectField(elements, FixedTypedArrayBase::kBasePointerOffset);
       Node* external_ptr =
           LoadObjectField(elements, FixedTypedArrayBase::kExternalPointerOffset,
                           MachineType::Pointer());
       Node* data_ptr = IntPtrAdd(BitcastTaggedToWord(base_ptr), external_ptr);
       Node* value = LoadFixedTypedArrayElementAsTagged(data_ptr, index, kind,
                                                        SMI_PARAMETERS);
       k_.Bind(index);
-      a_.Bind(processor(this, value, index));
+      a_.Bind(processor(this, kind, value, index));
     };
     BuildFastLoop(list, SmiConstant(0), len_, body, 1,
                   ParameterMode::SMI_PARAMETERS, IndexAdvanceMode::kPost);
   }
 
   void VisitAllFastElementsOneKind(ElementsKind kind,
                                    const CallResultProcessor& processor,
                                    Label* array_changed, ParameterMode mode,
                                    ForEachDirection direction) {
     Comment("begin VisitAllFastElementsOneKind");
@@ skipping 35 matching lines @@
           Node* offset = ElementOffsetFromIndex(index, kind, mode, base_size);
           Node* value = nullptr;
           if (kind == FAST_ELEMENTS) {
             value = LoadObjectField(elements, offset);
             GotoIf(WordEqual(value, TheHoleConstant()), &hole_element);
           } else {
             Node* double_value =
                 LoadDoubleWithHoleCheck(elements, offset, &hole_element);
             value = AllocateHeapNumberWithValue(double_value);
           }
-          a_.Bind(processor(this, value, k()));
+          a_.Bind(processor(this, kind, value, k()));
           Goto(&one_element_done);
 
           Bind(&hole_element);
           // Check if o's prototype change unexpectedly has elements after the
           // callback in the case of a hole.
           BranchIfPrototypesHaveNoElements(o_map, &one_element_done,
                                            array_changed);
 
           Bind(&one_element_done);
         },
@@ skipping 82 matching lines @@
   CodeStubArguments args(this, ChangeInt32ToIntPtr(argc));
   Node* receiver = args.GetReceiver();
   Node* kind = nullptr;
 
   Label fast(this);
   BranchIfFastJSArray(receiver, context, FastJSArrayAccessMode::ANY_ACCESS,
                       &fast, &runtime);
 
   Bind(&fast);
   {
-    // Disallow pushing onto prototypes. It might be the JSArray prototype.
-    // Disallow pushing onto non-extensible objects.
-    Comment("Disallow pushing onto prototypes");
-    Node* map = LoadMap(receiver);
-    Node* bit_field2 = LoadMapBitField2(map);
-    int mask = static_cast<int>(Map::IsPrototypeMapBits::kMask) |
-               (1 << Map::kIsExtensible);
-    Node* test = Word32And(bit_field2, Int32Constant(mask));
-    GotoIf(Word32NotEqual(test, Int32Constant(1 << Map::kIsExtensible)),
-           &runtime);
-
-    // Disallow pushing onto arrays in dictionary named property mode. We need
-    // to figure out whether the length property is still writable.
-    Comment("Disallow pushing onto arrays in dictionary named property mode");
-    GotoIf(IsDictionaryMap(map), &runtime);
-
-    // Check whether the length property is writable. The length property is the
-    // only default named property on arrays. It's nonconfigurable, hence is
-    // guaranteed to stay the first property.
-    Node* descriptors = LoadMapDescriptors(map);
-    Node* details =
-        LoadFixedArrayElement(descriptors, DescriptorArray::ToDetailsIndex(0));
-    GotoIf(IsSetSmi(details, PropertyDetails::kAttributesReadOnlyMask),
-           &runtime);
-
     arg_index.Bind(IntPtrConstant(0));
-    kind = DecodeWord32<Map::ElementsKindBits>(bit_field2);
-
+    kind = EnsureArrayPushable(receiver, &runtime);
     GotoIf(Int32GreaterThan(kind, Int32Constant(FAST_HOLEY_SMI_ELEMENTS)),
            &object_push_pre);
 
-    Node* new_length = BuildAppendJSArray(FAST_SMI_ELEMENTS, context, receiver,
-                                          args, arg_index, &smi_transition);
+    Node* new_length = BuildAppendJSArray(FAST_SMI_ELEMENTS, receiver, args,
+                                          arg_index, &smi_transition);
     args.PopAndReturn(new_length);
   }
 
   // If the argument is not a smi, then use a heavyweight SetProperty to
   // transition the array for only the single next element. If the argument is
   // a smi, the failure is due to some other reason and we should fall back on
   // the most generic implementation for the rest of the array.
   Bind(&smi_transition);
   {
     Node* arg = args.AtIndex(arg_index.value());
@@ skipping 17 matching lines @@
   }
 
   Bind(&object_push_pre);
   {
     Branch(Int32GreaterThan(kind, Int32Constant(FAST_HOLEY_ELEMENTS)),
            &double_push, &object_push);
   }
 
   Bind(&object_push);
   {
-    Node* new_length = BuildAppendJSArray(FAST_ELEMENTS, context, receiver,
-                                          args, arg_index, &default_label);
+    Node* new_length = BuildAppendJSArray(FAST_ELEMENTS, receiver, args,
+                                          arg_index, &default_label);
     args.PopAndReturn(new_length);
   }
 
   Bind(&double_push);
   {
-    Node* new_length =
-        BuildAppendJSArray(FAST_DOUBLE_ELEMENTS, context, receiver, args,
-                           arg_index, &double_transition);
+    Node* new_length = BuildAppendJSArray(FAST_DOUBLE_ELEMENTS, receiver, args,
+                                          arg_index, &double_transition);
     args.PopAndReturn(new_length);
   }
 
   // If the argument is not a double, then use a heavyweight SetProperty to
   // transition the array for only the single next element. If the argument is
   // a double, the failure is due to some other reason and we should fall back
   // on the most generic implementation for the rest of the array.
   Bind(&double_transition);
   {
     Node* arg = args.AtIndex(arg_index.value());
@@ skipping 1392 matching lines @@
   {
     Node* message = SmiConstant(MessageTemplate::kDetachedOperation);
     CallRuntime(Runtime::kThrowTypeError, context, message,
                 HeapConstant(operation));
     Unreachable();
   }
 }
 
 }  // namespace internal
 }  // namespace v8