[builtins] implement JSBuiltinReducer for ArrayIteratorNext()

src/compiler/js-builtin-reducer.cc

 // Copyright 2014 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/compiler/js-builtin-reducer.h"
 
 #include "src/compilation-dependencies.h"
 #include "src/compiler/access-builder.h"
 #include "src/compiler/js-graph.h"
 #include "src/compiler/node-matchers.h"
@@ skipping 159 matching lines @@
          IsFastElementsKind(receiver_map->elements_kind()) &&
          !receiver_map->is_dictionary_map() && receiver_map->is_extensible() &&
          (!receiver_map->is_prototype_map() || receiver_map->is_stable()) &&
          isolate->IsFastArrayConstructorPrototypeChainIntact() &&
          isolate->IsAnyInitialArrayPrototype(receiver_prototype) &&
          !IsReadOnlyLengthDescriptor(receiver_map);
 }
 
 }  // namespace
 
+Reduction JSBuiltinReducer::ReduceArrayIterator(Node* node,
+                                                IterationKind kind) {
+  Handle<Map> receiver_map;
+  Node* receiver = NodeProperties::GetValueInput(node, 1);
+  Node* effect = NodeProperties::GetEffectInput(node);
+  Node* control = NodeProperties::GetControlInput(node);
+
+  if (GetMapWitness(node).ToHandle(&receiver_map)) {
+    int map_index = -1;
+    Node* object_map = jsgraph()->UndefinedConstant();
+    switch (receiver_map->instance_type()) {
+      case JS_ARRAY_TYPE:
+        if (kind == IterationKind::kKeys) {
+          map_index = Context::FAST_ARRAY_KEY_ITERATOR_MAP_INDEX;
+        } else {
+          map_index =
+              kind == IterationKind::kValues
+                  ? Context::FAST_SMI_ARRAY_VALUE_ITERATOR_MAP_INDEX
+                  : Context::FAST_SMI_ARRAY_KEY_VALUE_ITERATOR_MAP_INDEX;
+          if (IsFastElementsKind(receiver_map->elements_kind())) {
+            map_index += static_cast<int>(receiver_map->elements_kind());
+            object_map = jsgraph()->Constant(receiver_map);
+          } else {
+            map_index += (Context::GENERIC_ARRAY_VALUE_ITERATOR_MAP_INDEX -
+                          Context::FAST_SMI_ARRAY_VALUE_ITERATOR_MAP_INDEX);
+          }
+        }
+        break;
+      case JS_TYPED_ARRAY_TYPE:
+        if (kind == IterationKind::kKeys) {
+          map_index = Context::TYPED_ARRAY_KEY_ITERATOR_MAP_INDEX;
+        } else {
+          DCHECK_GE(receiver_map->elements_kind(), UINT8_ELEMENTS);
+          DCHECK_LE(receiver_map->elements_kind(), UINT8_CLAMPED_ELEMENTS);
+          map_index =
+              (kind == IterationKind::kValues
+                   ? Context::UINT8_ARRAY_VALUE_ITERATOR_MAP_INDEX
+                   : Context::UINT8_ARRAY_KEY_VALUE_ITERATOR_MAP_INDEX) +
+              (receiver_map->elements_kind() - UINT8_ELEMENTS);
+        }
+        break;
+      default:
+        if (kind == IterationKind::kKeys) {
+          map_index = Context::GENERIC_ARRAY_KEY_ITERATOR_MAP_INDEX;
+        } else if (kind == IterationKind::kValues) {
+          map_index = Context::GENERIC_ARRAY_VALUE_ITERATOR_MAP_INDEX;
+        } else {
+          map_index = Context::GENERIC_ARRAY_KEY_VALUE_ITERATOR_MAP_INDEX;
+        }

[Benedikt Meurer, 2016/11/08 05:29:48]

Add a break for the default

+    }
+
+    DCHECK_GE(map_index, Context::TYPED_ARRAY_KEY_ITERATOR_MAP_INDEX);
+    DCHECK_LE(map_index, Context::GENERIC_ARRAY_VALUE_ITERATOR_MAP_INDEX);
+
+    Handle<Map> map(Map::cast(native_context()->get(map_index)), isolate());
+
+    // allocate new iterator
+    effect = graph()->NewNode(
+        common()->BeginRegion(RegionObservability::kNotObservable), effect);
+    Node* value = effect = graph()->NewNode(
+        simplified()->Allocate(NOT_TENURED),
+        jsgraph()->Constant(JSArrayIterator::kSize), effect, control);
+    effect = graph()->NewNode(simplified()->StoreField(AccessBuilder::ForMap()),
+                              value, jsgraph()->Constant(map), effect, control);
+    effect = graph()->NewNode(
+        simplified()->StoreField(AccessBuilder::ForJSObjectProperties()), value,
+        jsgraph()->EmptyFixedArrayConstant(), effect, control);
+    effect = graph()->NewNode(
+        simplified()->StoreField(AccessBuilder::ForJSObjectElements()), value,
+        jsgraph()->EmptyFixedArrayConstant(), effect, control);
+
+    // attach the iterator to this object
+    effect = graph()->NewNode(
+        simplified()->StoreField(AccessBuilder::ForJSArrayIteratorObject()),
+        value, receiver, effect, control);
+    effect = graph()->NewNode(
+        simplified()->StoreField(AccessBuilder::ForJSArrayIteratorIndex()),
+        value, jsgraph()->SmiConstant(0), effect, control);

[Benedikt Meurer, 2016/11/08 05:29:49]

Nit: use jsgraph()->ZeroConstant() here.

+    effect = graph()->NewNode(
+        simplified()->StoreField(AccessBuilder::ForJSArrayIteratorObjectMap()),
+        value, object_map, effect, control);
+
+    value = effect = graph()->NewNode(common()->FinishRegion(), value, effect);
+
+    // replace it
+    ReplaceWithValue(node, value, effect, control);
+    return Replace(value);
+  }
+  return NoChange();
+}
+
+Reduction JSBuiltinReducer::ReduceFastArrayIteratorNext(
+    Handle<Map> iterator_map, Node* node, IterationKind kind) {
+  Node* iterator = NodeProperties::GetValueInput(node, 1);
+  Node* effect = NodeProperties::GetEffectInput(node);
+  Node* control = NodeProperties::GetControlInput(node);
+  Node* context = NodeProperties::GetContextInput(node);
+
+  if (kind != IterationKind::kKeys && !isolate()->CanInlineArrayIterator()) {
+    // Avoid deopt loops for non-key iteration if the array_iterator_protector
+    // cell has been invalidated.
+    return NoChange();
+  }
+
+  ElementsKind elements_kind = JSArrayIterator::ElementsKindForInstanceType(
+      iterator_map->instance_type());
+
+  Node* array = effect = graph()->NewNode(
+      simplified()->LoadField(AccessBuilder::ForJSArrayIteratorObject()),

[Benedikt Meurer, 2016/11/08 05:29:48]

Move this after the condition below, otherwise you create a dangling LoadField
in the effect chain if the condition doesn't hold and you return NoChange.

+      iterator, effect, control);
+
+  Handle<Map> array_map;
+  if (IsFastHoleyElementsKind(elements_kind)) {
+    if (!GetMapWitness(array).ToHandle(&array_map)) {

[Benedikt Meurer, 2016/11/08 05:29:48]

This won't work in general, as there's no guarantee that you visit the array
first, plus there's LoadElimination happening at this point which would fold the
LoadField away and present you with a CheckMaps on the actual object. So for
holey elements you'll always abort here.

Instead if you see holey elements_kind here, you must abort if you the array
protector is invalid, and if it's valid, add a code dependency on it, and just
convert all holes to undefined. Plus during construction of the iterator you
must check that the prototype of fast holey arrays is the Array.prototype, and
use the generic iterator for holey arrays with non-Array.prototype.

[caitp, 2016/11/08 06:27:59]

Okay, I've updated this to set up a generic iterator if the prototype isn't
something that the protector cell can track (and gotten rid of the
CanTreatHoleAsUndefiend() helpers copied from
js-native-context-specialization.cc)

+      // Don't inline if there may be elements on the prototype chain.
+      return NoChange();
+    }
+  }
+
+  Node* check0 = effect = graph()->NewNode(
+      javascript()->StrictEqual(CompareOperationHint::kNone), array,

[Benedikt Meurer, 2016/11/08 05:29:48]

Use simplified()->ReferenceEqual() instead of StrictEqual here.

+      jsgraph()->UndefinedConstant(), context, effect, control);
+  Node* branch0 =
+      graph()->NewNode(common()->Branch(BranchHint::kFalse), check0, control);
+
+  Node* vdone_false0;
+  Node* vfalse0;
+  Node* efalse0 = effect;
+  Node* if_false0 = graph()->NewNode(common()->IfFalse(), branch0);
+  {
+    // iterator.[[IteratedObject]] !== undefined, continue iterating.
+    Node* index = efalse0 = graph()->NewNode(
+        simplified()->LoadField(AccessBuilder::ForJSArrayIteratorIndex(
+            JS_ARRAY_TYPE, elements_kind)),
+        iterator, efalse0, if_false0);
+
+    Node* length = efalse0 = graph()->NewNode(
+        simplified()->LoadField(AccessBuilder::ForJSArrayLength(elements_kind)),
+        array, efalse0, if_false0);
+    Node* check1 =
+        graph()->NewNode(simplified()->NumberLessThan(), index, length);
+    Node* branch1 = graph()->NewNode(common()->Branch(BranchHint::kTrue),
+                                     check1, if_false0);
+
+    Node* vdone_true1;
+    Node* vtrue1;
+    Node* etrue1 = efalse0;
+    Node* if_true1 = graph()->NewNode(common()->IfTrue(), branch1);
+    {
+      // iterator.[[NextIndex]] < array.length, continue iterating
+      vdone_true1 = jsgraph()->FalseConstant();
+      if (kind == IterationKind::kKeys) {
+        vtrue1 = index;
+      } else {
+        // For value/entry iteration, first step is a mapcheck to ensure
+        // inlining is still valid.
+        Node* orig_map = etrue1 =
+            graph()->NewNode(simplified()->LoadField(
+                                 AccessBuilder::ForJSArrayIteratorObjectMap()),
+                             iterator, effect, control);

[Benedikt Meurer, 2016/11/08 05:29:49]

s/effect/etrue1

+        etrue1 = graph()->NewNode(simplified()->CheckMaps(1), array, orig_map,
+                                  effect, control);

[Benedikt Meurer, 2016/11/08 05:29:48]

s/effect/etrue1/

+      }
+
+      Node* next_index = graph()->NewNode(simplified()->NumberAdd(), index,

[Benedikt Meurer, 2016/11/08 05:29:49]

You need to truncate the next_index via NumberToUint32 to teach TurboFan that
this cannot overflow (for general JSArray, the input types don't provide this
information, as the index can be any Unsigned32), otherwise TurboFan will be
forced to pick Float64Add here for the general JSArray case.

+                                          jsgraph()->OneConstant());
+      etrue1 = graph()->NewNode(
+          simplified()->StoreField(AccessBuilder::ForJSArrayIteratorIndex(
+              JS_ARRAY_TYPE, elements_kind)),
+          iterator, next_index, etrue1, if_true1);
+
+      if (kind != IterationKind::kKeys) {
+        Node* elements = etrue1 = graph()->NewNode(
+            simplified()->LoadField(AccessBuilder::ForJSObjectElements()),
+            array, etrue1, if_true1);
+        Node* value = etrue1 = graph()->NewNode(
+            simplified()->LoadElement(
+                AccessBuilder::ForFixedArrayElement(elements_kind)),
+            elements, index, etrue1, if_true1);
+
+        // Handle loading from holey backing stores correctly, by either mapping
+        // the hole to undefined if possible, or deoptimizing otherwise.

[Benedikt Meurer, 2016/11/08 05:29:48]

You cannot deoptimize for hole here, as that'll be a deoptimization loop. See
above.

+        if (elements_kind == FAST_HOLEY_ELEMENTS ||
+            elements_kind == FAST_HOLEY_SMI_ELEMENTS) {
+          // Check if we are allowed to turn the hole into undefined.
+          DCHECK(!array_map.is_null());
+          if (CanTreatHoleAsUndefined(array_map)) {
+            // Turn the hole into undefined.
+            value = graph()->NewNode(
+                simplified()->ConvertTaggedHoleToUndefined(), value);
+          } else {
+            // Bailout if we see the hole.
+            value = etrue1 = graph()->NewNode(simplified()->CheckTaggedHole(),
+                                              value, etrue1, if_true1);
+          }
+        } else if (elements_kind == FAST_HOLEY_DOUBLE_ELEMENTS) {
+          // Perform the hole check on the result.
+          DCHECK(!array_map.is_null());
+          CheckFloat64HoleMode mode = CheckFloat64HoleMode::kNeverReturnHole;
+          // Check if we are allowed to return the hole directly.
+          if (CanTreatHoleAsUndefined(array_map)) {

[Benedikt Meurer, 2016/11/08 05:29:49]

Same as above.

+            // Return the signaling NaN hole directly if all uses are
+            // truncating.
+            mode = CheckFloat64HoleMode::kAllowReturnHole;
+          }
+          value = etrue1 = graph()->NewNode(
+              simplified()->CheckFloat64Hole(mode), value, etrue1, if_true1);
+        }
+
+        if (kind == IterationKind::kEntries) {
+          // Allocate elements for key/value pair
+          etrue1 = graph()->NewNode(
+              common()->BeginRegion(RegionObservability::kNotObservable),
+              etrue1);
+          Node* elements = etrue1 = graph()->NewNode(
+              simplified()->Allocate(NOT_TENURED),
+              jsgraph()->Constant(FixedArray::SizeFor(2)), etrue1, if_true1);
+          etrue1 = graph()->NewNode(
+              simplified()->StoreField(AccessBuilder::ForMap()), elements,
+              jsgraph()->Constant(isolate()->factory()->fixed_array_map()),
+              etrue1, if_true1);
+          etrue1 = graph()->NewNode(
+              simplified()->StoreField(AccessBuilder::ForFixedArrayLength()),
+              elements, jsgraph()->Constant(2));
+          etrue1 = graph()->NewNode(
+              simplified()->StoreElement(
+                  AccessBuilder::ForFixedArrayElement(FAST_ELEMENTS)),
+              elements, jsgraph()->Constant(0), index, etrue1, if_true1);
+          etrue1 = graph()->NewNode(
+              simplified()->StoreElement(
+                  AccessBuilder::ForFixedArrayElement(FAST_ELEMENTS)),
+              elements, jsgraph()->Constant(1), value, etrue1, if_true1);
+          elements = etrue1 =
+              graph()->NewNode(common()->FinishRegion(), elements, etrue1);
+
+          // Allocate JSArray for key/value pair
+          etrue1 = graph()->NewNode(
+              common()->BeginRegion(RegionObservability::kNotObservable),
+              etrue1);
+          Node* entry = etrue1 = graph()->NewNode(
+              simplified()->Allocate(NOT_TENURED),
+              jsgraph()->Constant(JSArray::kSize), etrue1, if_true1);
+          etrue1 = graph()->NewNode(
+              simplified()->StoreField(AccessBuilder::ForMap()), entry,
+              jsgraph()->Constant(
+                  handle(native_context()->js_array_fast_elements_map_index())),
+              etrue1, if_true1);
+          etrue1 = graph()->NewNode(
+              simplified()->StoreField(AccessBuilder::ForJSObjectProperties()),
+              entry, jsgraph()->EmptyFixedArrayConstant(), etrue1, if_true1);
+          etrue1 = graph()->NewNode(
+              simplified()->StoreField(AccessBuilder::ForJSObjectElements()),
+              entry, elements, etrue1, if_true1);
+          etrue1 = graph()->NewNode(
+              simplified()->StoreField(
+                  AccessBuilder::ForJSArrayLength(elements_kind)),
+              entry, jsgraph()->Constant(2), etrue1, if_true1);
+          entry = etrue1 =
+              graph()->NewNode(common()->FinishRegion(), entry, etrue1);
+          vtrue1 = entry;
+        } else {
+          DCHECK(kind == IterationKind::kValues);
+          vtrue1 = value;
+        }
+      }
+    }
+
+    Node* vdone_false1;
+    Node* vfalse1;
+    Node* efalse1 = efalse0;
+    Node* if_false1 = graph()->NewNode(common()->IfFalse(), branch1);
+    {
+      // iterator.[[NextIndex]] >= array.length, stop iterating.
+      vdone_false1 = jsgraph()->TrueConstant();
+      vfalse1 = jsgraph()->UndefinedConstant();
+      efalse1 = graph()->NewNode(
+          simplified()->StoreField(AccessBuilder::ForJSArrayIteratorObject()),
+          iterator, vfalse1, efalse1, if_false1);
+    }
+
+    if_false0 = graph()->NewNode(common()->Merge(2), if_true1, if_false1);
+    efalse0 =
+        graph()->NewNode(common()->EffectPhi(2), etrue1, efalse1, if_false0);
+    vfalse0 = graph()->NewNode(common()->Phi(MachineRepresentation::kTagged, 2),
+                               vtrue1, vfalse1, if_false0);
+    vdone_false0 =
+        graph()->NewNode(common()->Phi(MachineRepresentation::kTagged, 2),
+                         vdone_true1, vdone_false1, if_false0);
+  }
+
+  Node* vdone_true0;
+  Node* vtrue0;
+  Node* etrue0 = effect;
+  Node* if_true0 = graph()->NewNode(common()->IfTrue(), branch0);
+  {
+    // iterator.[[IteratedObject]] === undefined, the iterator is done.
+    vdone_true0 = jsgraph()->TrueConstant();
+    vtrue0 = jsgraph()->UndefinedConstant();
+  }
+
+  control = graph()->NewNode(common()->Merge(2), if_false0, if_true0);
+  effect = graph()->NewNode(common()->EffectPhi(2), efalse0, etrue0, control);
+  Node* value =
+      graph()->NewNode(common()->Phi(MachineRepresentation::kTagged, 2),
+                       vfalse0, vtrue0, control);
+  Node* done =
+      graph()->NewNode(common()->Phi(MachineRepresentation::kTagged, 2),
+                       vdone_false0, vdone_true0, control);
+
+  // Create IteratorResult object.
+  value = effect = graph()->NewNode(javascript()->CreateIterResultObject(),
+                                    value, done, context, effect);
+  ReplaceWithValue(node, value, effect, control);
+  return Replace(value);
+}
+
+Reduction JSBuiltinReducer::ReduceTypedArrayIteratorNext(
+    Handle<Map> iterator_map, Node* node, IterationKind kind) {
+  Node* iterator = NodeProperties::GetValueInput(node, 1);
+  Node* effect = NodeProperties::GetEffectInput(node);
+  Node* control = NodeProperties::GetControlInput(node);
+  Node* context = NodeProperties::GetContextInput(node);
+
+  ElementsKind elements_kind = JSArrayIterator::ElementsKindForInstanceType(
+      iterator_map->instance_type());
+
+  Node* array = effect = graph()->NewNode(
+      simplified()->LoadField(AccessBuilder::ForJSArrayIteratorObject()),
+      iterator, effect, control);
+  Node* check0 = effect = graph()->NewNode(
+      javascript()->StrictEqual(CompareOperationHint::kNone), array,
+      jsgraph()->UndefinedConstant(), context, effect, control);
+  Node* branch0 =
+      graph()->NewNode(common()->Branch(BranchHint::kFalse), check0, control);
+
+  Node* vdone_false0;
+  Node* vfalse0;
+  Node* efalse0 = effect;
+  Node* if_false0 = graph()->NewNode(common()->IfFalse(), branch0);
+  {
+    // iterator.[[IteratedObject]] !== undefined, continue iterating.
+    Node* index = efalse0 = graph()->NewNode(
+        simplified()->LoadField(AccessBuilder::ForJSArrayIteratorIndex(
+            JS_TYPED_ARRAY_TYPE, elements_kind)),
+        iterator, efalse0, if_false0);
+
+    // typedarray.[[ViewedArrayBuffer]]
+    Node* buffer = efalse0 = graph()->NewNode(
+        simplified()->LoadField(AccessBuilder::ForJSArrayBufferViewBuffer()),
+        array, efalse0, if_false0);
+
+    Node* check1 = efalse0 = graph()->NewNode(
+        simplified()->ArrayBufferWasNeutered(), buffer, efalse0, if_false0);
+    Node* branch1 = graph()->NewNode(common()->Branch(BranchHint::kFalse),
+                                     check1, if_false0);
+
+    Node* vfalse1;
+    Node* efalse1 = efalse0;
+    Node* if_false1 = graph()->NewNode(common()->IfFalse(), branch1);
+    {
+      vfalse1 = efalse1 = graph()->NewNode(
+          simplified()->LoadField(AccessBuilder::ForJSTypedArrayLength()),
+          array, efalse1, if_false1);
+    }
+
+    Node* vtrue1;
+    Node* etrue1 = efalse0;
+    Node* if_true1 = graph()->NewNode(common()->IfTrue(), branch1);
+    {
+      // TODO(caitp): If IsDetached(buffer) is true, throw a TypeError, per
+      // https://github.com/tc39/ecma262/issues/713
+      vtrue1 = jsgraph()->Constant(0);
+    }
+
+    if_false0 = graph()->NewNode(common()->Merge(2), if_false1, if_true1);
+    efalse0 =
+        graph()->NewNode(common()->EffectPhi(2), efalse1, etrue1, if_false0);
+    Node* length =
+        graph()->NewNode(common()->Phi(MachineRepresentation::kTagged, 2),
+                         vfalse1, vtrue1, if_false0);
+
+    Node* check2 =
+        graph()->NewNode(simplified()->NumberLessThan(), index, length);
+    Node* branch2 = graph()->NewNode(common()->Branch(BranchHint::kTrue),
+                                     check2, if_false0);
+
+    Node* vdone_true2;
+    Node* vtrue2;
+    Node* etrue2 = efalse0;
+    Node* if_true2 = graph()->NewNode(common()->IfTrue(), branch2);
+    {
+      // iterator.[[NextIndex]] < array.length, continue iterating
+      vdone_true2 = jsgraph()->FalseConstant();
+      if (kind == IterationKind::kKeys) {
+        vtrue2 = index;
+      }
+
+      Node* next_index = graph()->NewNode(simplified()->NumberAdd(), index,
+                                          jsgraph()->OneConstant());
+      etrue2 = graph()->NewNode(
+          simplified()->StoreField(AccessBuilder::ForJSArrayIteratorIndex(
+              JS_TYPED_ARRAY_TYPE, elements_kind)),
+          iterator, next_index, etrue2, if_true2);
+
+      if (kind != IterationKind::kKeys) {
+        Node* elements = etrue2 = graph()->NewNode(
+            simplified()->LoadField(AccessBuilder::ForJSObjectElements()),
+            array, etrue2, if_true2);
+        Node* base_ptr = etrue2 = graph()->NewNode(
+            simplified()->LoadField(
+                AccessBuilder::ForFixedTypedArrayBaseBasePointer()),
+            elements, etrue2, if_true2);
+        Node* external_ptr = etrue2 = graph()->NewNode(
+            simplified()->LoadField(
+                AccessBuilder::ForFixedTypedArrayBaseExternalPointer()),
+            elements, etrue2, if_true2);
+
+        ExternalArrayType array_type = kExternalInt8Array;
+        switch (elements_kind) {
+#define TYPED_ARRAY_CASE(Type, type, TYPE, ctype, size) \
+  case TYPE##_ELEMENTS:                                 \
+    array_type = kExternal##Type##Array;
+          TYPED_ARRAYS(TYPED_ARRAY_CASE)
+          default:
+            UNREACHABLE();
+#undef TYPED_ARRAY_CASE
+        }
+
+        Node* value = etrue2 =
+            graph()->NewNode(simplified()->LoadTypedElement(array_type), buffer,
+                             base_ptr, external_ptr, index, etrue2, if_true2);
+
+        if (kind == IterationKind::kEntries) {
+          // Allocate elements for key/value pair
+          etrue2 = graph()->NewNode(
+              common()->BeginRegion(RegionObservability::kNotObservable),
+              etrue2);
+          Node* elements = etrue2 = graph()->NewNode(
+              simplified()->Allocate(NOT_TENURED),
+              jsgraph()->Constant(FixedArray::SizeFor(2)), etrue2, if_true2);
+          etrue2 = graph()->NewNode(
+              simplified()->StoreField(AccessBuilder::ForMap()), elements,
+              jsgraph()->Constant(isolate()->factory()->fixed_array_map()),
+              etrue1, if_true2);
+          etrue2 = graph()->NewNode(
+              simplified()->StoreField(AccessBuilder::ForFixedArrayLength()),
+              elements, jsgraph()->Constant(2));
+          etrue2 = graph()->NewNode(
+              simplified()->StoreElement(
+                  AccessBuilder::ForFixedArrayElement(FAST_ELEMENTS)),
+              elements, jsgraph()->Constant(0), index, etrue2, if_true2);
+          etrue2 = graph()->NewNode(
+              simplified()->StoreElement(
+                  AccessBuilder::ForFixedArrayElement(FAST_ELEMENTS)),
+              elements, jsgraph()->Constant(1), value, etrue2, if_true2);
+          elements = etrue2 =
+              graph()->NewNode(common()->FinishRegion(), elements, etrue2);
+
+          // Allocate JSArray for key/value pair
+          etrue2 = graph()->NewNode(
+              common()->BeginRegion(RegionObservability::kNotObservable),
+              etrue2);
+          Node* entry = etrue2 = graph()->NewNode(
+              simplified()->Allocate(NOT_TENURED),
+              jsgraph()->Constant(JSArray::kSize), etrue2, if_true2);
+          etrue2 = graph()->NewNode(
+              simplified()->StoreField(AccessBuilder::ForMap()), entry,
+              jsgraph()->Constant(
+                  handle(native_context()->js_array_fast_elements_map_index())),
+              etrue2, if_true2);
+          etrue2 = graph()->NewNode(
+              simplified()->StoreField(AccessBuilder::ForJSObjectProperties()),
+              entry, jsgraph()->EmptyFixedArrayConstant(), etrue2, if_true2);
+          etrue2 = graph()->NewNode(
+              simplified()->StoreField(AccessBuilder::ForJSObjectElements()),
+              entry, elements, etrue2, if_true2);
+          etrue2 = graph()->NewNode(
+              simplified()->StoreField(
+                  AccessBuilder::ForJSArrayLength(elements_kind)),
+              entry, jsgraph()->Constant(2), etrue2, if_true2);
+          entry = etrue1 =
+              graph()->NewNode(common()->FinishRegion(), entry, etrue2);
+          vtrue2 = entry;
+        } else {
+          DCHECK(kind == IterationKind::kValues);
+          vtrue2 = value;
+        }
+      }
+    }
+
+    Node* vdone_false2;
+    Node* vfalse2;
+    Node* efalse2 = efalse0;
+    Node* if_false2 = graph()->NewNode(common()->IfFalse(), branch2);
+    {
+      // iterator.[[NextIndex]] >= array.length, stop iterating.
+      vdone_false2 = jsgraph()->TrueConstant();
+      vfalse2 = jsgraph()->UndefinedConstant();
+      efalse2 = graph()->NewNode(
+          simplified()->StoreField(AccessBuilder::ForJSArrayIteratorObject()),
+          iterator, vfalse2, efalse2, if_false2);
+    }
+
+    if_false0 = graph()->NewNode(common()->Merge(2), if_true2, if_false2);
+    efalse0 =
+        graph()->NewNode(common()->EffectPhi(2), etrue2, efalse2, if_false0);
+    vfalse0 = graph()->NewNode(common()->Phi(MachineRepresentation::kTagged, 2),
+                               vtrue2, vfalse2, if_false0);
+    vdone_false0 =
+        graph()->NewNode(common()->Phi(MachineRepresentation::kTagged, 2),
+                         vdone_true2, vdone_false2, if_false0);
+  }
+
+  Node* vdone_true0;
+  Node* vtrue0;
+  Node* etrue0 = effect;
+  Node* if_true0 = graph()->NewNode(common()->IfTrue(), branch0);
+  {
+    // iterator.[[IteratedObject]] === undefined, the iterator is done.
+    vdone_true0 = jsgraph()->TrueConstant();
+    vtrue0 = jsgraph()->UndefinedConstant();
+  }
+
+  control = graph()->NewNode(common()->Merge(2), if_false0, if_true0);
+  effect = graph()->NewNode(common()->EffectPhi(2), efalse0, etrue0, control);
+  Node* value =
+      graph()->NewNode(common()->Phi(MachineRepresentation::kTagged, 2),
+                       vfalse0, vtrue0, control);
+  Node* done =
+      graph()->NewNode(common()->Phi(MachineRepresentation::kTagged, 2),
+                       vdone_false0, vdone_true0, control);
+
+  // Create IteratorResult object.
+  value = effect = graph()->NewNode(javascript()->CreateIterResultObject(),
+                                    value, done, context, effect);
+  ReplaceWithValue(node, value, effect, control);
+  return Replace(value);
+}
+
+Reduction JSBuiltinReducer::ReduceArrayIteratorNext(Node* node) {
+  Handle<Map> receiver_map;
+  if (GetMapWitness(node).ToHandle(&receiver_map)) {
+    switch (receiver_map->instance_type()) {
+      case JS_TYPED_ARRAY_KEY_ITERATOR_TYPE:
+        return ReduceTypedArrayIteratorNext(receiver_map, node,
+                                            IterationKind::kKeys);
+
+      case JS_FAST_ARRAY_KEY_ITERATOR_TYPE:
+        return ReduceFastArrayIteratorNext(receiver_map, node,
+                                           IterationKind::kKeys);
+
+      case JS_INT8_ARRAY_KEY_VALUE_ITERATOR_TYPE:
+      case JS_UINT8_ARRAY_KEY_VALUE_ITERATOR_TYPE:
+      case JS_INT16_ARRAY_KEY_VALUE_ITERATOR_TYPE:
+      case JS_UINT16_ARRAY_KEY_VALUE_ITERATOR_TYPE:
+      case JS_INT32_ARRAY_KEY_VALUE_ITERATOR_TYPE:
+      case JS_UINT32_ARRAY_KEY_VALUE_ITERATOR_TYPE:
+      case JS_FLOAT32_ARRAY_KEY_VALUE_ITERATOR_TYPE:
+      case JS_FLOAT64_ARRAY_KEY_VALUE_ITERATOR_TYPE:
+      case JS_UINT8_CLAMPED_ARRAY_KEY_VALUE_ITERATOR_TYPE:
+        return ReduceTypedArrayIteratorNext(receiver_map, node,
+                                            IterationKind::kEntries);
+
+      case JS_FAST_SMI_ARRAY_KEY_VALUE_ITERATOR_TYPE:
+      case JS_FAST_HOLEY_SMI_ARRAY_KEY_VALUE_ITERATOR_TYPE:
+      case JS_FAST_ARRAY_KEY_VALUE_ITERATOR_TYPE:
+      case JS_FAST_HOLEY_ARRAY_KEY_VALUE_ITERATOR_TYPE:
+      case JS_FAST_DOUBLE_ARRAY_KEY_VALUE_ITERATOR_TYPE:
+      case JS_FAST_HOLEY_DOUBLE_ARRAY_KEY_VALUE_ITERATOR_TYPE:
+        return ReduceFastArrayIteratorNext(receiver_map, node,
+                                           IterationKind::kEntries);
+
+      case JS_INT8_ARRAY_VALUE_ITERATOR_TYPE:
+      case JS_UINT8_ARRAY_VALUE_ITERATOR_TYPE:
+      case JS_INT16_ARRAY_VALUE_ITERATOR_TYPE:
+      case JS_UINT16_ARRAY_VALUE_ITERATOR_TYPE:
+      case JS_INT32_ARRAY_VALUE_ITERATOR_TYPE:
+      case JS_UINT32_ARRAY_VALUE_ITERATOR_TYPE:
+      case JS_FLOAT32_ARRAY_VALUE_ITERATOR_TYPE:
+      case JS_FLOAT64_ARRAY_VALUE_ITERATOR_TYPE:
+      case JS_UINT8_CLAMPED_ARRAY_VALUE_ITERATOR_TYPE:
+        return ReduceTypedArrayIteratorNext(receiver_map, node,
+                                            IterationKind::kValues);
+
+      case JS_FAST_SMI_ARRAY_VALUE_ITERATOR_TYPE:
+      case JS_FAST_HOLEY_SMI_ARRAY_VALUE_ITERATOR_TYPE:
+      case JS_FAST_ARRAY_VALUE_ITERATOR_TYPE:
+      case JS_FAST_HOLEY_ARRAY_VALUE_ITERATOR_TYPE:
+      case JS_FAST_DOUBLE_ARRAY_VALUE_ITERATOR_TYPE:
+      case JS_FAST_HOLEY_DOUBLE_ARRAY_VALUE_ITERATOR_TYPE:
+        return ReduceFastArrayIteratorNext(receiver_map, node,
+                                           IterationKind::kValues);
+
+      default:
+        // Slow array iterators are not reduced
+        return NoChange();
+    }
+  }
+  return NoChange();
+}
+
 // ES6 section 22.1.3.17 Array.prototype.pop ( )
 Reduction JSBuiltinReducer::ReduceArrayPop(Node* node) {
   Handle<Map> receiver_map;
   Node* receiver = NodeProperties::GetValueInput(node, 1);
   Node* effect = NodeProperties::GetEffectInput(node);
   Node* control = NodeProperties::GetControlInput(node);
   // TODO(turbofan): Extend this to also handle fast (holey) double elements
   // once we got the hole NaN mess sorted out in TurboFan/V8.
   if (GetMapWitness(node).ToHandle(&receiver_map) &&
       CanInlineArrayResizeOperation(receiver_map) &&
@@ skipping 1063 matching lines @@
   return NoChange();
 }
 
 Reduction JSBuiltinReducer::Reduce(Node* node) {
   Reduction reduction = NoChange();
   JSCallReduction r(node);
 
   // Dispatch according to the BuiltinFunctionId if present.
   if (!r.HasBuiltinFunctionId()) return NoChange();
   switch (r.GetBuiltinFunctionId()) {
+    case kArrayEntries:
+      return ReduceArrayIterator(node, IterationKind::kEntries);
+    case kArrayKeys:
+      return ReduceArrayIterator(node, IterationKind::kKeys);
+    case kArrayValues:
+      return ReduceArrayIterator(node, IterationKind::kValues);
+    case kArrayIteratorNext:
+      return ReduceArrayIteratorNext(node);
     case kArrayPop:
       return ReduceArrayPop(node);
     case kArrayPush:
       return ReduceArrayPush(node);
     case kDateGetTime:
       return ReduceDateGetTime(node);
     case kGlobalIsFinite:
       reduction = ReduceGlobalIsFinite(node);
       break;
     case kGlobalIsNaN:
@@ skipping 160 matching lines @@
   return graph()->NewNode(simplified()->PlainPrimitiveToNumber(), input);
 }
 
 Node* JSBuiltinReducer::ToUint32(Node* input) {
   input = ToNumber(input);
   Type* input_type = NodeProperties::GetType(input);
   if (input_type->Is(Type::Unsigned32())) return input;
   return graph()->NewNode(simplified()->NumberToUint32(), input);
 }
 
+bool JSBuiltinReducer::CanTreatHoleAsUndefined(Handle<Map> receiver_map) {
+  std::vector<Handle<Map>> receiver_maps = {receiver_map};
+  return CanTreatHoleAsUndefined(receiver_maps);
+}
+
+bool JSBuiltinReducer::CanTreatHoleAsUndefined(
+    std::vector<Handle<Map>> const& receiver_maps) {
+  // Check if the array prototype chain is intact.
+  if (!isolate()->IsFastArrayConstructorPrototypeChainIntact()) return false;
+
+  // Make sure both the initial Array and Object prototypes are stable.
+  Handle<JSObject> initial_array_prototype(
+      native_context()->initial_array_prototype(), isolate());
+  Handle<JSObject> initial_object_prototype(
+      native_context()->initial_object_prototype(), isolate());
+  if (!initial_array_prototype->map()->is_stable() ||
+      !initial_object_prototype->map()->is_stable()) {
+    return false;
+  }
+
+  // Check if all {receiver_maps} either have the initial Array.prototype
+  // or the initial Object.prototype as their prototype, as those are
+  // guarded by the array protector cell.
+  for (Handle<Map> map : receiver_maps) {
+    if (map->prototype() != *initial_array_prototype &&
+        map->prototype() != *initial_object_prototype) {
+      return false;
+    }
+  }
+
+  // Install code dependencies on the prototype maps.
+  for (Handle<Map> map : receiver_maps) {
+    dependencies()->AssumePrototypeMapsStable(map, initial_object_prototype);
+  }
+
+  // Install code dependency on the array protector cell.
+  dependencies()->AssumePropertyCell(factory()->array_protector());
+  return true;
+}
+
 Graph* JSBuiltinReducer::graph() const { return jsgraph()->graph(); }
 
 Factory* JSBuiltinReducer::factory() const { return isolate()->factory(); }
 
 Isolate* JSBuiltinReducer::isolate() const { return jsgraph()->isolate(); }
 
 
 CommonOperatorBuilder* JSBuiltinReducer::common() const {
   return jsgraph()->common();
 }
 
 
 SimplifiedOperatorBuilder* JSBuiltinReducer::simplified() const {
   return jsgraph()->simplified();
 }
 
 JSOperatorBuilder* JSBuiltinReducer::javascript() const {
   return jsgraph()->javascript();
 }
 
 }  // namespace compiler
 }  // namespace internal
 }  // namespace v8