[builtins] TurboFan version of Array.prototype.forEach including fast path for FAST_ELEMENTS

src/builtins/builtins-array.cc

 // Copyright 2016 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.h"
 #include "src/builtins/builtins-utils.h"
 
 #include "src/code-factory.h"
 #include "src/code-stub-assembler.h"
 #include "src/contexts.h"
@@ skipping 408 matching lines @@
 
   if (JSArray::HasReadOnlyLength(array)) {
     return CallJsIntrinsic(isolate, isolate->array_unshift(), args);
   }
 
   ElementsAccessor* accessor = array->GetElementsAccessor();
   int new_length = accessor->Unshift(array, &args, to_add);
   return Smi::FromInt(new_length);
 }
 
+class ForEachCodeStubAssembler : public CodeStubAssembler {
+ public:
+  explicit ForEachCodeStubAssembler(compiler::CodeAssemblerState* state)
+      : CodeStubAssembler(state) {}
+
+  void VisitOneElement(Node* context, Node* this_arg, Node* o, Node* k,
+                       Node* callbackfn) {
+    Comment("begin VisitOneElement");
+
+    // a. Let Pk be ToString(k).
+    Node* p_k = ToString(context, k);
+
+    // b. Let kPresent be HasProperty(O, Pk).
+    // c. ReturnIfAbrupt(kPresent).
+    Node* k_present =
+        CallStub(CodeFactory::HasProperty(isolate()), context, p_k, o);
+
+    // d. If kPresent is true, then
+    Label not_present(this);
+    GotoIf(WordNotEqual(k_present, TrueConstant()), &not_present);
+
+    // i. Let kValue be Get(O, Pk).
+    // ii. ReturnIfAbrupt(kValue).
+    Node* k_value =
+        CallStub(CodeFactory::GetProperty(isolate()), context, o, k);
+
+    // iii. Let funcResult be Call(callbackfn, T, «kValue, k, O»).
+    // iv. ReturnIfAbrupt(funcResult).
+    CallJS(CodeFactory::Call(isolate()), context, callbackfn, this_arg, k_value,
+           k, o);
+
+    Goto(&not_present);
+    Bind(&not_present);
+    Comment("end VisitOneElement");
+  }
+
+  void VisitAllFastElements(Node* context, ElementsKind kind, Node* this_arg,
+                            Node* o, Node* len, Node* callbackfn,
+                            ParameterMode mode) {
+    Comment("begin VisitAllFastElements");
+    Variable original_map(this, MachineRepresentation::kTagged);
+    original_map.Bind(LoadMap(o));
+    VariableList list({&original_map}, zone());
+    BuildFastLoop(
+        list, IntPtrOrSmiConstant(0, mode), TaggedToParameter(len, mode),
+        [context, kind, this, o, &original_map, callbackfn, this_arg,
+         mode](Node* index) {
+          Label one_element_done(this), array_changed(this, Label::kDeferred);
+
+          // 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.
+          GotoIf(WordNotEqual(LoadMap(o), original_map.value()),
+                 &array_changed);
+
+          // Check if o's length has changed during the callback and if the
+          // index is now out of range of the new length.
+          Node* tagged_index = ParameterToTagged(index, mode);
+          GotoIf(SmiGreaterThanOrEqual(tagged_index, LoadJSArrayLength(o)),
+                 &array_changed);
+
+          // Re-load the elements array. If may have been resized.
+          Node* elements = LoadElements(o);
+
+          // Fast case: load the element directly from the elements FixedArray
+          // and call the callback if the element is not the hole.
+          DCHECK(kind == FAST_ELEMENTS || kind == FAST_DOUBLE_ELEMENTS);
+          int base_size = kind == FAST_ELEMENTS
+                              ? FixedArray::kHeaderSize
+                              : (FixedArray::kHeaderSize - kHeapObjectTag);
+          Node* offset = ElementOffsetFromIndex(index, kind, mode, base_size);
+          Node* value = nullptr;
+          if (kind == FAST_ELEMENTS) {
+            value = LoadObjectField(elements, offset);
+            GotoIf(WordEqual(value, TheHoleConstant()), &one_element_done);
+          } else {
+            Node* double_value =
+                LoadDoubleWithHoleCheck(elements, offset, &one_element_done);
+            value = AllocateHeapNumberWithValue(double_value);
+          }

[Benedikt Meurer, 2017/02/02 05:22:38]

You need to handle holey arrays here. I.e. upon reading the hole/hole NaN you
must verify that the array prototype chain is still intact, and if not go to the
slow path, otherwise skip the hole.

[danno, 2017/02/02 17:15:48]

Done.

+          CallJS(CodeFactory::Call(isolate()), context, callbackfn, this_arg,
+                 value, tagged_index, o);
+          Goto(&one_element_done);
+
+          // O's changed during the forEach. Use the implementation precisely
+          // specified in the spec for the rest of the iteration, also making
+          // the failed original_map sticky in case of a subseuent change that
+          // goes back to the original map.
+          Bind(&array_changed);
+          VisitOneElement(context, this_arg, o, ParameterToTagged(index, mode),
+                          callbackfn);
+          original_map.Bind(UndefinedConstant());
+          Goto(&one_element_done);
+
+          Bind(&one_element_done);
+        },
+        1, mode, IndexAdvanceMode::kPost);
+    Comment("end VisitAllFastElements");
+  }
+};
+
+TF_BUILTIN(ArrayForEach, ForEachCodeStubAssembler) {
+  Node* argc = Parameter(BuiltinDescriptor::kArgumentsCount);
+  Node* context = Parameter(BuiltinDescriptor::kContext);
+  Label non_array(this), examine_elements(this), fast_elements(this),
+      slow(this), maybe_double_elements(this), fast_double_elements(this);
+
+  Node* argc_intptr = ChangeInt32ToIntPtr(argc);
+  CodeStubArguments args(this, argc_intptr);
+  Node* receiver = args.GetReceiver();
+
+  Variable callbackfn(this, MachineRepresentation::kTagged);

[Benedikt Meurer, 2017/02/02 05:22:38]

Wouldn't it be easier to just use the arguments adaptor mechanism here? Then
you'll always have callbackFn and thisArg parameters, and if the user supplied
too few or too many, the arguments adaptor will just fill up with undefined.

[danno, 2017/02/02 17:15:48]

Done.

+  Label no_callbackfn(this);
+  callbackfn.Bind(UndefinedConstant());
+  GotoIf(WordEqual(argc_intptr, IntPtrConstant(0)), &no_callbackfn);
+  callbackfn.Bind(args.AtIndex(0));
+  Goto(&no_callbackfn);
+  Bind(&no_callbackfn);
+
+  // TODO(danno): Seriously? Do we really need to throw the exact error message

[Benedikt Meurer, 2017/02/02 05:22:38]

I think it's fine to just let ToObject fail and rebaseline the layout tests; so
don't do this additional check.

[danno, 2017/02/02 17:15:48]

For consistency with the other Array builtins, I'm going to leave this as-is for
now. We should go back and then change all of them to be simpler and consistent
in a separate CL.

+  // 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
+
+  // 1. Let O be ToObject(this value).
+  // 2. ReturnIfAbrupt(O)
+  Node* o = CallStub(CodeFactory::ToObject(isolate()), context, receiver);
+
+  // 3. Let len be ToLength(Get(O, "length")).
+  // 4. ReturnIfAbrupt(len).
+  Variable merged_length(this, MachineRepresentation::kTagged);
+  Label has_length(this, &merged_length), not_js_array(this);
+  GotoIf(DoesntHaveInstanceType(o, JS_ARRAY_TYPE), &not_js_array);
+  merged_length.Bind(LoadJSArrayLength(o));
+  Goto(&has_length);
+  Bind(&not_js_array);
+  Node* len_property =
+      CallStub(CodeFactory::GetProperty(isolate()), context, o,
+               HeapConstant(isolate()->factory()->length_string()));
+  merged_length.Bind(
+      CallStub(CodeFactory::ToLength(isolate()), context, len_property));
+  Goto(&has_length);
+  Bind(&has_length);
+  Node* len = merged_length.value();
+
+  // 5. If IsCallable(callbackfn) is false, throw a TypeError exception.
+  Label type_exception(this, Label::kDeferred);
+  GotoIf(TaggedIsSmi(callbackfn.value()), &type_exception);
+  GotoUnless(IsCallableMap(LoadMap(callbackfn.value())), &type_exception);
+
+  // 6. If thisArg was supplied, let T be thisArg; else let T be undefined.
+  Variable this_arg(this, MachineRepresentation::kTagged);
+  this_arg.Bind(UndefinedConstant());
+  Label this_arg_done(this);
+  GotoIf(WordEqual(argc_intptr, IntPtrConstant(1)), &this_arg_done);
+  this_arg.Bind(args.AtIndex(1));
+  Goto(&this_arg_done);
+  Bind(&this_arg_done);
+
+  // Non-smi lengths must use the slow path.
+  GotoIf(TaggedIsNotSmi(len), &slow);
+
+  BranchIfFastJSArray(o, context,
+                      CodeStubAssembler::FastJSArrayAccessMode::INBOUNDS_READ,
+                      &examine_elements, &slow);
+
+  Bind(&examine_elements);
+
+  ParameterMode mode = OptimalParameterMode();
+
+  // 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);
+
+  Bind(&fast_elements);
+  {
+    VisitAllFastElements(context, FAST_ELEMENTS, this_arg.value(), o, len,
+                         callbackfn.value(), mode);
+
+    // No exception, return success
+    args.PopAndReturn(UndefinedConstant());
+  }
+
+  Bind(&maybe_double_elements);
+  Branch(Int32GreaterThan(kind, Int32Constant(FAST_HOLEY_DOUBLE_ELEMENTS)),
+         &slow, &fast_double_elements);
+
+  Bind(&fast_double_elements);
+  {
+    VisitAllFastElements(context, FAST_DOUBLE_ELEMENTS, this_arg.value(), o,
+                         len, callbackfn.value(), mode);
+
+    // No exception, return success
+    args.PopAndReturn(UndefinedConstant());
+  }
+
+  Bind(&slow);
+  {
+    // By the book: taken from the ECMAScript 2015 specification (cont.)
+
+    // 7. Let k be 0.
+    Variable k(this, MachineRepresentation::kTagged);
+    k.Bind(SmiConstant(0));
+
+    // 8. Repeat, while k < len
+    Label loop(this, &k);
+    Label after_loop(this);
+    Goto(&loop);
+    Bind(&loop);
+    {
+      GotoUnlessNumberLessThan(k.value(), len, &after_loop);
+
+      VisitOneElement(context, this_arg.value(), o, k.value(),
+                      callbackfn.value());
+
+      // e. Increase k by 1.
+      k.Bind(NumberInc(k.value()));
+      Goto(&loop);
+    }
+    Bind(&after_loop);
+    args.PopAndReturn(UndefinedConstant());
+  }
+
+  Bind(&throw_null_undefined_exception);
+  {
+    CallRuntime(Runtime::kThrowTypeError, context,
+                SmiConstant(MessageTemplate::kCalledOnNullOrUndefined),
+                HeapConstant(isolate()->factory()->NewStringFromAsciiChecked(
+                    "Array.prototype.forEach")));
+    args.PopAndReturn(UndefinedConstant());
+  }
+
+  Bind(&type_exception);
+  {
+    CallRuntime(Runtime::kThrowTypeError, context,
+                SmiConstant(MessageTemplate::kCalledNonCallable),
+                callbackfn.value());
+    args.PopAndReturn(UndefinedConstant());
+  }
+}
+
 BUILTIN(ArraySlice) {
   HandleScope scope(isolate);
   Handle<Object> receiver = args.receiver();
   int len = -1;
   int relative_start = 0;
   int relative_end = 0;
 
   if (receiver->IsJSArray()) {
     DisallowHeapAllocation no_gc;
     JSArray* array = JSArray::cast(*receiver);
@@ skipping 2333 matching lines @@
     Node* message = assembler.SmiConstant(MessageTemplate::kDetachedOperation);
     Node* result =
         assembler.CallRuntime(Runtime::kThrowTypeError, context, message,
                               assembler.HeapConstant(operation));
     assembler.Return(result);
   }
 }
 
 }  // namespace internal
 }  // namespace v8