[builtins] Implement Array.prototype.reduce in the CSA

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) {}
 
-  typedef std::function<Node*(Node* o, Node* len)> BuiltinResultGenerator;
-  typedef std::function<void(Node* a, Node* pK, Node* value)>
+  typedef std::function<std::pair<Node*, Node*>(

[danno, 2017/03/17 10:26:31]

Per Camillo's comments, I am going to add comments there to explain the
arguments and make them a little more useful, the names are taken from the spec
and that makes it a little hard to reason about in the code.

+      ArrayBuiltinCodeStubAssembler* masm, Node* this_arg, Node* o, Node* len)>
+      BuiltinResultGenerator;
+
+  typedef std::function<Node*(ArrayBuiltinCodeStubAssembler* masm,
+                              Node* context, Node* callbackfn, Node* this_arg,
+                              Node* k_value, Node* k, Node* o, Node* a)>
       CallResultProcessor;
 
+  typedef std::function<void(ArrayBuiltinCodeStubAssembler* masm, Node* context,
+                             Node* a)>
+      PostLoopAction;
+
   void GenerateIteratingArrayBuiltinBody(
       const char* name, const BuiltinResultGenerator& generator,
-      const CallResultProcessor& processor,
+      const CallResultProcessor& processor, const PostLoopAction& action,
       const Callable& slow_case_continuation) {
     Node* receiver = Parameter(IteratingArrayBuiltinDescriptor::kReceiver);
     Node* callbackfn = Parameter(IteratingArrayBuiltinDescriptor::kCallback);
     Node* this_arg = Parameter(IteratingArrayBuiltinDescriptor::kThisArg);
     Node* context = Parameter(IteratingArrayBuiltinDescriptor::kContext);
     Node* new_target = Parameter(IteratingArrayBuiltinDescriptor::kNewTarget);
 
     Variable k(this, MachineRepresentation::kTagged, SmiConstant(0));
-    Label non_array(this), slow(this, &k), array_changes(this, &k);
+    Variable a(this, MachineRepresentation::kTagged, UndefinedConstant());
+    Label non_array(this), slow(this, {&k, &a}), array_changes(this, {&k, &a});
 
     // TODO(danno): Seriously? Do we really need to throw the exact error
     // message on null and undefined so that the webkit tests pass?
     Label throw_null_undefined_exception(this, Label::kDeferred);
     GotoIf(WordEqual(receiver, NullConstant()),
            &throw_null_undefined_exception);
     GotoIf(WordEqual(receiver, UndefinedConstant()),
            &throw_null_undefined_exception);
 
     // By the book: taken directly from the ECMAScript 2015 specification
@@ skipping 35 matching lines @@
 
     Bind(&type_exception);
     {
       CallRuntime(Runtime::kThrowTypeError, context,
                   SmiConstant(MessageTemplate::kCalledNonCallable), callbackfn);
       Unreachable();
     }
 
     Bind(&done);
 
-    Node* a = generator(o, len);
+    Node* initial_a;
+    Node* initial_k;
+    std::tie(initial_a, initial_k) = generator(this, this_arg, o, len);
 
     // 6. If thisArg was supplied, let T be thisArg; else let T be undefined.
     // [Already done by the arguments adapter]
 
-    HandleFastElements(context, this_arg, o, len, callbackfn, processor, a, k,
-                       &slow);
+    // 7. Let k be 0.
+    k.Bind(initial_k);
+    a.Bind(initial_a);
 
-    // 7. Let k be 0.
-    // Already done above in initialization of the Variable k
+    HandleFastElements(context, this_arg, o, len, callbackfn, processor, action,
+                       a, k, &slow);
 
     Bind(&slow);
 
     Node* target = LoadFromFrame(StandardFrameConstants::kFunctionOffset,
                                  MachineType::TaggedPointer());
     TailCallStub(
         slow_case_continuation, context, target, new_target,
         Int32Constant(IteratingArrayBuiltinLoopContinuationDescriptor::kArity),
-        receiver, callbackfn, this_arg, a, o, k.value(), len);
+        receiver, callbackfn, this_arg, a.value(), o, k.value(), len);
   }
 
   void GenerateIteratingArrayBuiltinLoopContinuation(
-      const CallResultProcessor& processor) {
+      const CallResultProcessor& processor, const PostLoopAction& action) {
     Node* callbackfn =
         Parameter(IteratingArrayBuiltinLoopContinuationDescriptor::kCallback);
     Node* this_arg =
         Parameter(IteratingArrayBuiltinLoopContinuationDescriptor::kThisArg);
-    Node* a =
+    Node* initial_a =
         Parameter(IteratingArrayBuiltinLoopContinuationDescriptor::kArray);
     Node* o =
         Parameter(IteratingArrayBuiltinLoopContinuationDescriptor::kObject);
     Node* initial_k =
         Parameter(IteratingArrayBuiltinLoopContinuationDescriptor::kInitialK);
     Node* len =
         Parameter(IteratingArrayBuiltinLoopContinuationDescriptor::kLength);
     Node* context =
         Parameter(IteratingArrayBuiltinLoopContinuationDescriptor::kContext);
 
     // 8. Repeat, while k < len
     Variable k(this, MachineRepresentation::kTagged, initial_k);
-    Label loop(this, &k);
+    Variable a(this, MachineRepresentation::kTagged, initial_a);
+    Label loop(this, {&k, &a});
     Label after_loop(this);
     Goto(&loop);
     Bind(&loop);
     {
       GotoUnlessNumberLessThan(k.value(), len, &after_loop);
 
       Label done_element(this);
       // a. Let Pk be ToString(k).
       Node* p_k = ToString(context, k.value());
 
       // b. Let kPresent be HasProperty(O, Pk).
       // c. ReturnIfAbrupt(kPresent).
       Node* k_present = HasProperty(o, p_k, context);
 
       // 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.value());
 
       // iii. Let funcResult be Call(callbackfn, T, «kValue, k, O»).
       // iv. ReturnIfAbrupt(funcResult).
-      Node* result = CallJS(CodeFactory::Call(isolate()), context, callbackfn,
-                            this_arg, k_value, k.value(), o);
-
-      processor(a, p_k, result);
+      a.Bind(processor(this, context, callbackfn, this_arg, k_value, k.value(),
+                       o, a.value()));
       Goto(&done_element);
       Bind(&done_element);
 
       // e. Increase k by 1.
       k.Bind(NumberInc(k.value()));
       Goto(&loop);
     }
     Bind(&after_loop);
-    Return(a);
+
+    action(this, context, a.value());
+
+    Return(a.value());
   }
 
-  void ForEachProcessor(Node* a, Node* p_k, Node* value) {}
+  std::pair<Node*, Node*> ForEachResultGenerator(Node* this_arg, Node* o,
+                                                 Node* len) {
+    return std::make_pair(UndefinedConstant(), SmiConstant(0));
+  }
 
-  void SomeProcessor(Node* a, Node* p_k, Node* value) {
+  Node* ForEachProcessor(Node* context, Node* callbackfn, Node* this_arg,
+                         Node* k_value, Node* k, Node* o, Node* a) {
+    CallJS(CodeFactory::Call(isolate()), context, callbackfn, this_arg, k_value,
+           k, o);
+    return a;
+  }
+
+  std::pair<Node*, Node*> SomeResultGenerator(Node* this_arg, Node* o,
+                                              Node* len) {
+    return std::make_pair(FalseConstant(), SmiConstant(0));
+  }
+
+  Node* SomeProcessor(Node* context, Node* callbackfn, Node* this_arg,
+                      Node* k_value, Node* k, Node* o, Node* a) {
+    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;
   }
 
-  void EveryProcessor(Node* a, Node* p_k, Node* value) {
+  std::pair<Node*, Node*> EveryResultGenerator(Node* this_arg, Node* o,
+                                               Node* len) {
+    return std::make_pair(TrueConstant(), SmiConstant(0));
+  }
+
+  Node* EveryProcessor(Node* context, Node* callbackfn, Node* this_arg,
+                       Node* k_value, Node* k, Node* o, Node* a) {
+    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;
   }
 
+  std::pair<Node*, Node*> ReduceResultGenerator(Node* initial_value, Node* o,
+                                                Node* len) {
+    Variable a(this, MachineRepresentation::kTagged, UndefinedConstant());
+    Label no_initial_value(this), has_initial_value(this), done(this, {&a});
+
+    // 8. If initialValue is present, then
+    Node* parent_frame_ptr = LoadParentFramePointer();
+    Node* marker_or_function = LoadBufferObject(
+        parent_frame_ptr, CommonFrameConstants::kContextOrFrameTypeOffset);
+    GotoIf(
+        MarkerIsNotFrameType(marker_or_function, StackFrame::ARGUMENTS_ADAPTOR),
+        &has_initial_value);
+
+    // Has arguments adapter, check count.
+    Node* adapted_parameter_count = LoadBufferObject(
+        parent_frame_ptr, ArgumentsAdaptorFrameConstants::kLengthOffset);
+    Branch(SmiLessThan(adapted_parameter_count,
+                       SmiConstant(IteratingArrayBuiltinDescriptor::kThisArg)),
+           &no_initial_value, &has_initial_value);
+
+    // a. Set accumulator to initialValue.
+    Bind(&has_initial_value);
+    a.Bind(initial_value);
+    Goto(&done);
+
+    // 9. Else initialValue is not present,
+    Bind(&no_initial_value);
+
+    // a. Let kPresent be false.
+    a.Bind(TheHoleConstant());
+    Goto(&done);
+    Bind(&done);
+    return std::make_pair(a.value(), SmiConstant(0));
+  }
+
+  Node* ReduceProcessor(Node* context, Node* callbackfn, Node* this_arg,
+                        Node* k_value, Node* k, Node* o, Node* a) {
+    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(Node* context, Node* a) {
+    Label ok(this);
+    GotoIf(WordNotEqual(a, TheHoleConstant()), &ok);
+    CallRuntime(Runtime::kThrowTypeError, context,
+                SmiConstant(MessageTemplate::kReduceNoInitial));
+    Unreachable();
+    Bind(&ok);
+  }
+
+  void NullPostLoopAction(Node* context, Node* a) {}
+
  private:
   Node* VisitAllFastElementsOneKind(Node* context, ElementsKind kind,
                                     Node* this_arg, Node* o, Node* len,
                                     Node* callbackfn,
                                     const CallResultProcessor& processor,
-                                    Node* a, Label* array_changed,
+                                    Variable& a, Label* array_changed,
                                     ParameterMode mode) {
     Comment("begin VisitAllFastElementsOneKind");
     Variable original_map(this, MachineRepresentation::kTagged);
     original_map.Bind(LoadMap(o));
-    VariableList list({&original_map}, zone());
+    VariableList list({&original_map, &a}, zone());
     Node* last_index = nullptr;
     BuildFastLoop(
         list, IntPtrOrSmiConstant(0, mode), TaggedToParameter(len, mode),
-        [=, &original_map, &last_index](Node* index) {
+        [=, &a, &original_map, &last_index](Node* index) {
           last_index = index;
           Label one_element_done(this), hole_element(this);
 
           // Check if o's map has changed during the callback. If so, we have to
           // fall back to the slower spec implementation for the rest of the
           // iteration.
           Node* o_map = LoadMap(o);
           GotoIf(WordNotEqual(o_map, original_map.value()), array_changed);
 
           // Check if o's length has changed during the callback and if the
@@ skipping 14 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);
           }
-          Node* result = CallJS(CodeFactory::Call(isolate()), context,
-                                callbackfn, this_arg, value, tagged_index, o);
-          processor(a, tagged_index, result);
+          a.Bind(processor(this, context, callbackfn, this_arg, value,
+                           tagged_index, o, a.value()));
           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);
         },
         1, mode, IndexAdvanceMode::kPost);
     Comment("end VisitAllFastElementsOneKind");
     return last_index;
   }
 
   void HandleFastElements(Node* context, Node* this_arg, Node* o, Node* len,
-                          Node* callbackfn, CallResultProcessor processor,
-                          Node* a, Variable& k, Label* slow) {
+                          Node* callbackfn,
+                          const CallResultProcessor& processor,
+                          const PostLoopAction& action, Variable& a,
+                          Variable& k, Label* slow) {
     Label switch_on_elements_kind(this), fast_elements(this),
         maybe_double_elements(this), fast_double_elements(this);
 
     Comment("begin HandleFastElements");
     // Non-smi lengths must use the slow path.
     GotoIf(TaggedIsNotSmi(len), slow);
 
     BranchIfFastJSArray(o, context,
                         CodeStubAssembler::FastJSArrayAccessMode::INBOUNDS_READ,
                         &switch_on_elements_kind, slow);
 
     Bind(&switch_on_elements_kind);
     // Select by ElementsKind
     Node* o_map = LoadMap(o);
     Node* bit_field2 = LoadMapBitField2(o_map);
     Node* kind = DecodeWord32<Map::ElementsKindBits>(bit_field2);
     Branch(Int32GreaterThan(kind, Int32Constant(FAST_HOLEY_ELEMENTS)),
            &maybe_double_elements, &fast_elements);
 
     ParameterMode mode = OptimalParameterMode();
     Bind(&fast_elements);
     {
       Label array_changed(this, Label::kDeferred);
       Node* last_index = VisitAllFastElementsOneKind(
           context, FAST_ELEMENTS, this_arg, o, len, callbackfn, processor, a,
           &array_changed, mode);
 
+      action(this, context, a.value());
+
       // No exception, return success
-      Return(a);
+      Return(a.value());
 
       Bind(&array_changed);
       k.Bind(ParameterToTagged(last_index, mode));
       Goto(slow);
     }
 
     Bind(&maybe_double_elements);
     Branch(Int32GreaterThan(kind, Int32Constant(FAST_HOLEY_DOUBLE_ELEMENTS)),
            slow, &fast_double_elements);
 
     Bind(&fast_double_elements);
     {
       Label array_changed(this, Label::kDeferred);
       Node* last_index = VisitAllFastElementsOneKind(
           context, FAST_DOUBLE_ELEMENTS, this_arg, o, len, callbackfn,
           processor, a, &array_changed, mode);
 
+      action(this, context, a.value());
+
       // No exception, return success
-      Return(a);
+      Return(a.value());
 
       Bind(&array_changed);
       k.Bind(ParameterToTagged(last_index, mode));
       Goto(slow);
     }
   }
 };
 
 TF_BUILTIN(FastArrayPush, CodeStubAssembler) {
   Variable arg_index(this, MachineType::PointerRepresentation());
@@ skipping 144 matching lines @@
   {
     Node* target = LoadFromFrame(StandardFrameConstants::kFunctionOffset,
                                  MachineType::TaggedPointer());
     TailCallStub(CodeFactory::ArrayPush(isolate()), context, target, new_target,
                  argc);
   }
 }
 
 TF_BUILTIN(ArrayForEachLoopContinuation, ArrayBuiltinCodeStubAssembler) {
   GenerateIteratingArrayBuiltinLoopContinuation(
-      [this](Node* a, Node* p_k, Node* value) {
-        ForEachProcessor(a, p_k, value);
-      });
+      &ArrayBuiltinCodeStubAssembler::ForEachProcessor,
+      &ArrayBuiltinCodeStubAssembler::NullPostLoopAction);
 }
 
 TF_BUILTIN(ArrayForEach, ArrayBuiltinCodeStubAssembler) {
   GenerateIteratingArrayBuiltinBody(
       "Array.prototype.forEach",
-      [=](Node*, Node*) { return UndefinedConstant(); },
-      [this](Node* a, Node* p_k, Node* value) {
-        ForEachProcessor(a, p_k, value);
-      },
+      &ArrayBuiltinCodeStubAssembler::ForEachResultGenerator,
+      &ArrayBuiltinCodeStubAssembler::ForEachProcessor,
+      &ArrayBuiltinCodeStubAssembler::NullPostLoopAction,
       CodeFactory::ArrayForEachLoopContinuation(isolate()));
 }
 
 TF_BUILTIN(ArraySomeLoopContinuation, ArrayBuiltinCodeStubAssembler) {
   GenerateIteratingArrayBuiltinLoopContinuation(
-      [this](Node* a, Node* p_k, Node* value) {
-        SomeProcessor(a, p_k, value);
-      });
+      &ArrayBuiltinCodeStubAssembler::SomeProcessor,
+      &ArrayBuiltinCodeStubAssembler::NullPostLoopAction);
 }
 
 TF_BUILTIN(ArraySome, ArrayBuiltinCodeStubAssembler) {
   GenerateIteratingArrayBuiltinBody(
-      "Array.prototype.some", [=](Node*, Node*) { return FalseConstant(); },
-      [this](Node* a, Node* p_k, Node* value) { SomeProcessor(a, p_k, value); },
+      "Array.prototype.some",
+      &ArrayBuiltinCodeStubAssembler::SomeResultGenerator,
+      &ArrayBuiltinCodeStubAssembler::SomeProcessor,
+      &ArrayBuiltinCodeStubAssembler::NullPostLoopAction,
       CodeFactory::ArraySomeLoopContinuation(isolate()));
 }
 
 TF_BUILTIN(ArrayEveryLoopContinuation, ArrayBuiltinCodeStubAssembler) {
   GenerateIteratingArrayBuiltinLoopContinuation(
-      [this](Node* a, Node* p_k, Node* value) {
-        EveryProcessor(a, p_k, value);
-      });
+      &ArrayBuiltinCodeStubAssembler::EveryProcessor,
+      &ArrayBuiltinCodeStubAssembler::NullPostLoopAction);
 }
 
 TF_BUILTIN(ArrayEvery, ArrayBuiltinCodeStubAssembler) {
   GenerateIteratingArrayBuiltinBody(
-      "Array.prototype.every", [=](Node*, Node*) { return TrueConstant(); },
-      [this](Node* a, Node* p_k, Node* value) {
-        EveryProcessor(a, p_k, value);
-      },
+      "Array.prototype.every",
+      &ArrayBuiltinCodeStubAssembler::EveryResultGenerator,
+      &ArrayBuiltinCodeStubAssembler::EveryProcessor,
+      &ArrayBuiltinCodeStubAssembler::NullPostLoopAction,
       CodeFactory::ArrayEveryLoopContinuation(isolate()));
 }
 
+TF_BUILTIN(ArrayReduceLoopContinuation, ArrayBuiltinCodeStubAssembler) {
+  GenerateIteratingArrayBuiltinLoopContinuation(
+      &ArrayBuiltinCodeStubAssembler::ReduceProcessor,
+      &ArrayBuiltinCodeStubAssembler::ReducePostLoopAction);
+}
+
+TF_BUILTIN(ArrayReduce, ArrayBuiltinCodeStubAssembler) {
+  GenerateIteratingArrayBuiltinBody(
+      "Array.prototype.reduce",
+      &ArrayBuiltinCodeStubAssembler::ReduceResultGenerator,
+      &ArrayBuiltinCodeStubAssembler::ReduceProcessor,
+      &ArrayBuiltinCodeStubAssembler::ReducePostLoopAction,
+      CodeFactory::ArrayReduceLoopContinuation(isolate()));
+}
+
 TF_BUILTIN(ArrayIsArray, CodeStubAssembler) {
   Node* object = Parameter(1);
   Node* context = Parameter(4);
 
   Label call_runtime(this), return_true(this), return_false(this);
 
   GotoIf(TaggedIsSmi(object), &return_false);
   Node* instance_type = LoadInstanceType(object);
 
   GotoIf(Word32Equal(instance_type, Int32Constant(JS_ARRAY_TYPE)),
@@ skipping 1034 matching lines @@
   {
     Node* message = SmiConstant(MessageTemplate::kDetachedOperation);
     CallRuntime(Runtime::kThrowTypeError, context, message,
                 HeapConstant(operation));
     Unreachable();
   }
 }
 
 }  // namespace internal
 }  // namespace v8