[stubs] Generalize loop handling in CodeStubAssembler and improve common loop performance

src/code-stub-assembler.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/code-stub-assembler.h"
 #include "src/code-factory.h"
 #include "src/frames-inl.h"
 #include "src/frames.h"
 #include "src/ic/handler-configuration.h"
 #include "src/ic/stub-cache.h"
@@ skipping 1420 matching lines @@
     Heap::RootListIndex value_root_index, ParameterMode mode) {
   bool is_double = IsFastDoubleElementsKind(kind);
   DCHECK(value_root_index == Heap::kTheHoleValueRootIndex ||
          value_root_index == Heap::kUndefinedValueRootIndex);
   DCHECK_IMPLIES(is_double, value_root_index == Heap::kTheHoleValueRootIndex);
   STATIC_ASSERT(kHoleNanLower32 == kHoleNanUpper32);
   Node* double_hole =
       Is64() ? Int64Constant(kHoleNanInt64) : Int32Constant(kHoleNanLower32);
   Node* value = LoadRoot(value_root_index);
 
-  const int first_element_offset = FixedArray::kHeaderSize - kHeapObjectTag;
-  int32_t to;
-  bool constant_to = ToInt32Constant(to_node, to);
-  int32_t from;
-  bool constant_from = ToInt32Constant(from_node, from);
-  if (constant_to && constant_from &&
-      (to - from) <= kElementLoopUnrollThreshold) {
-    for (int i = from; i < to; ++i) {
-      Node* index = IntPtrConstant(i);
-      if (is_double) {
-        Node* offset = ElementOffsetFromIndex(index, kind, INTPTR_PARAMETERS,
-                                              first_element_offset);
-        // Don't use doubles to store the hole double, since manipulating the
-        // signaling NaN used for the hole in C++, e.g. with bit_cast, will
-        // change its value on ia32 (the x87 stack is used to return values
-        // and stores to the stack silently clear the signalling bit).
-        //
-        // TODO(danno): When we have a Float32/Float64 wrapper class that
-        // preserves double bits during manipulation, remove this code/change
-        // this to an indexed Float64 store.
-        if (Is64()) {
-          StoreNoWriteBarrier(MachineRepresentation::kWord64, array, offset,
-                              double_hole);
+  BuildFastFixedArrayForEach(
+      array, kind, from_node, to_node,
+      [value, is_double, double_hole](CodeStubAssembler* assembler, Node* array,
+                                      Node* offset) {
+        if (is_double) {
+          // Don't use doubles to store the hole double, since manipulating the
+          // signaling NaN used for the hole in C++, e.g. with bit_cast, will
+          // change its value on ia32 (the x87 stack is used to return values
+          // and stores to the stack silently clear the signalling bit).
+          //
+          // TODO(danno): When we have a Float32/Float64 wrapper class that
+          // preserves double bits during manipulation, remove this code/change
+          // this to an indexed Float64 store.
+          if (assembler->Is64()) {
+            assembler->StoreNoWriteBarrier(MachineRepresentation::kWord64,
+                                           array, offset, double_hole);
+          } else {
+            assembler->StoreNoWriteBarrier(MachineRepresentation::kWord32,
+                                           array, offset, double_hole);
+            assembler->StoreNoWriteBarrier(
+                MachineRepresentation::kWord32, array,
+                assembler->IntPtrAdd(offset,
+                                     assembler->IntPtrConstant(kPointerSize)),
+                double_hole);
+          }
         } else {
-          StoreNoWriteBarrier(MachineRepresentation::kWord32, array, offset,
-                              double_hole);
-          offset = ElementOffsetFromIndex(index, kind, INTPTR_PARAMETERS,
-                                          first_element_offset + kPointerSize);
-          StoreNoWriteBarrier(MachineRepresentation::kWord32, array, offset,
-                              double_hole);
+          assembler->StoreNoWriteBarrier(MachineRepresentation::kTagged, array,
+                                         offset, value);
         }
-      } else {
-        StoreFixedArrayElement(array, index, value, SKIP_WRITE_BARRIER,
-                               INTPTR_PARAMETERS);
-      }
-    }
-  } else {
-    Variable current(this, MachineRepresentation::kTagged);
-    Label test(this);
-    Label decrement(this, &current);
-    Label done(this);
-    Node* limit =
-        IntPtrAdd(array, ElementOffsetFromIndex(from_node, kind, mode));
-    current.Bind(IntPtrAdd(array, ElementOffsetFromIndex(to_node, kind, mode)));
-
-    Branch(WordEqual(current.value(), limit), &done, &decrement);
-
-    Bind(&decrement);
-    current.Bind(IntPtrSub(
-        current.value(),
-        IntPtrConstant(IsFastDoubleElementsKind(kind) ? kDoubleSize
-                                                      : kPointerSize)));
-    if (is_double) {
-      // Don't use doubles to store the hole double, since manipulating the
-      // signaling NaN used for the hole in C++, e.g. with bit_cast, will
-      // change its value on ia32 (the x87 stack is used to return values
-      // and stores to the stack silently clear the signalling bit).
-      //
-      // TODO(danno): When we have a Float32/Float64 wrapper class that
-      // preserves double bits during manipulation, remove this code/change
-      // this to an indexed Float64 store.
-      if (Is64()) {
-        StoreNoWriteBarrier(MachineRepresentation::kWord64, current.value(),
-                            Int64Constant(first_element_offset), double_hole);
-      } else {
-        StoreNoWriteBarrier(MachineRepresentation::kWord32, current.value(),
-                            Int32Constant(first_element_offset), double_hole);
-        StoreNoWriteBarrier(MachineRepresentation::kWord32, current.value(),
-                            Int32Constant(kPointerSize + first_element_offset),
-                            double_hole);
-      }
-    } else {
-      StoreNoWriteBarrier(MachineType::PointerRepresentation(), current.value(),
-                          IntPtrConstant(first_element_offset), value);
-    }
-    Node* compare = WordNotEqual(current.value(), limit);
-    Branch(compare, &decrement, &done);
-
-    Bind(&done);
-  }
+      },
+      mode);
 }
 
 void CodeStubAssembler::CopyFixedArrayElements(
     ElementsKind from_kind, Node* from_array, ElementsKind to_kind,
     Node* to_array, Node* element_count, Node* capacity,
     WriteBarrierMode barrier_mode, ParameterMode mode) {
   STATIC_ASSERT(FixedArray::kHeaderSize == FixedDoubleArray::kHeaderSize);
   const int first_element_offset = FixedArray::kHeaderSize - kHeapObjectTag;
   Comment("[ CopyFixedArrayElements");
 
@@ skipping 1761 matching lines @@
     var_entry->Bind(entry);
     Goto(&loop);
   }
 }
 
 void CodeStubAssembler::DescriptorLookupLinear(Node* unique_name,
                                                Node* descriptors, Node* nof,
                                                Label* if_found,
                                                Variable* var_name_index,
                                                Label* if_not_found) {
-  Variable var_descriptor(this, MachineType::PointerRepresentation());
-  Label loop(this, &var_descriptor);
-  var_descriptor.Bind(IntPtrConstant(0));
-  Goto(&loop);
+  Node* first_inclusive = IntPtrConstant(DescriptorArray::ToKeyIndex(0));
+  Node* factor = IntPtrConstant(DescriptorArray::kDescriptorSize);
+  Node* last_exclusive = IntPtrAdd(first_inclusive, IntPtrMul(nof, factor));
 
-  Bind(&loop);
-  {
-    Node* index = var_descriptor.value();
-    Node* name_offset = IntPtrConstant(DescriptorArray::ToKeyIndex(0));
-    Node* factor = IntPtrConstant(DescriptorArray::kDescriptorSize);
-    GotoIf(WordEqual(index, nof), if_not_found);
-    Node* name_index = IntPtrAdd(name_offset, IntPtrMul(index, factor));
-    Node* candidate_name =
-        LoadFixedArrayElement(descriptors, name_index, 0, INTPTR_PARAMETERS);
-    var_name_index->Bind(name_index);
-    GotoIf(WordEqual(candidate_name, unique_name), if_found);
-    var_descriptor.Bind(IntPtrAdd(index, IntPtrConstant(1)));
-    Goto(&loop);
-  }
+  BuildFastLoop(
+      MachineType::PointerRepresentation(), last_exclusive, first_inclusive,
+      [descriptors, unique_name, if_found, var_name_index](
+          CodeStubAssembler* assembler, Node* name_index) {
+        Node* candidate_name = assembler->LoadFixedArrayElement(
+            descriptors, name_index, 0, INTPTR_PARAMETERS);
+        var_name_index->Bind(name_index);
+        assembler->GotoIf(assembler->WordEqual(candidate_name, unique_name),
+                          if_found);
+      },
+      -DescriptorArray::kDescriptorSize, IndexAdvanceMode::kPre);
+  Goto(if_not_found);
 }
 
 void CodeStubAssembler::TryLookupProperty(
     Node* object, Node* map, Node* instance_type, Node* unique_name,
     Label* if_found_fast, Label* if_found_dict, Label* if_found_global,
     Variable* var_meta_storage, Variable* var_name_index, Label* if_not_found,
     Label* if_bailout) {
   DCHECK_EQ(MachineRepresentation::kTagged, var_meta_storage->rep());
   DCHECK_EQ(MachineType::PointerRepresentation(), var_name_index->rep());
 
@@ skipping 2362 matching lines @@
   StoreObjectField(cell, WeakCell::kValueOffset, value);
   StoreObjectFieldRoot(cell, WeakCell::kNextOffset,
                        Heap::kTheHoleValueRootIndex);
 
   // Store the WeakCell in the feedback vector.
   StoreFixedArrayElement(feedback_vector, slot, cell, UPDATE_WRITE_BARRIER,
                          CodeStubAssembler::SMI_PARAMETERS);
   return cell;
 }
 
+void CodeStubAssembler::BuildFastLoop(
+    MachineRepresentation index_rep, Node* start_index, Node* end_index,
+    std::function<void(CodeStubAssembler* assembler, Node* index)> body,
+    int increment, IndexAdvanceMode mode) {
+  Variable var(this, index_rep);
+  var.Bind(start_index);
+  Label loop(this, &var);
+  Label after_loop(this);
+  BranchIf(WordEqual(var.value(), end_index), &after_loop, &loop);
+  Bind(&loop);
+  {

[Igor Sheludko, 2016/10/04 09:32:25]

Why not just put 
  GotoIf(WordEqual(var.value(), end_index), &after_loop);
here instead of a condition check before the loop and another one below?
Is it about how TurboFan orders the blocks?

[danno, 2016/10/04 16:10:23]

As discussed offline, for efficiency. Comment added.

+    if (mode == IndexAdvanceMode::kPre) {
+      var.Bind(IntPtrAdd(var.value(), IntPtrConstant(increment)));
+    }
+    body(this, var.value());
+    if (mode == IndexAdvanceMode::kPost) {
+      var.Bind(IntPtrAdd(var.value(), IntPtrConstant(increment)));
+    }
+    BranchIf(WordNotEqual(var.value(), end_index), &loop, &after_loop);
+  }
+  Bind(&after_loop);
+}
+
+void CodeStubAssembler::BuildFastFixedArrayForEach(
+    compiler::Node* fixed_array, ElementsKind kind,
+    compiler::Node* first_element_inclusive,
+    compiler::Node* last_element_exclusive,
+    std::function<void(CodeStubAssembler* assembler,
+                       compiler::Node* fixed_array, compiler::Node* offset)>
+        body,
+    ParameterMode mode, ForEachDirection direction) {

[Igor Sheludko, 2016/10/04 09:32:25]

I think we should put this assert somewhere in this function:

// The code below relies on array headers having the same size.
STATIC_ASSERT(FixedArray::kHeaderSize == FixedDoubleArray::kHeaderSize);

[danno, 2016/10/04 16:10:23]

Done.

+  int32_t first_val;
+  bool constant_first = ToInt32Constant(first_element_inclusive, first_val);
+  int32_t last_val;
+  bool constent_last = ToInt32Constant(last_element_exclusive, last_val);
+  if (constant_first && constent_last) {
+    int delta = last_val - first_val;
+    DCHECK(delta >= 0);
+    if (delta <= kElementLoopUnrollThreshold) {
+      if (direction == ForEachDirection::kForward) {
+        for (int i = first_val; i < last_val; ++i) {
+          Node* index = IntPtrConstant(i);
+          Node* offset =
+              ElementOffsetFromIndex(index, FAST_ELEMENTS, mode,

[Igor Sheludko, 2016/10/04 09:32:25]

I think you intended to use |kind| instead of |FAST_ELEMENTS| and 
INTPTR_PARAMETERS instead of |mode| here.

[danno, 2016/10/04 16:10:23]

Done.

+                                     FixedArray::kHeaderSize - kHeapObjectTag);
+          body(this, fixed_array, offset);
+        }
+      } else {
+        for (int i = last_val - 1; i >= first_val; --i) {
+          Node* index = IntPtrConstant(i);
+          Node* offset =
+              ElementOffsetFromIndex(index, FAST_ELEMENTS, mode,

[Igor Sheludko, 2016/10/04 09:32:25]

Same here

[danno, 2016/10/04 16:10:23]

Done.

+                                     FixedArray::kHeaderSize - kHeapObjectTag);
+          body(this, fixed_array, offset);
+        }
+      }
+      return;
+    }
+  }
+
+  Node* start =
+      ElementOffsetFromIndex(first_element_inclusive, kind, mode,
+                             FixedArray::kHeaderSize - kHeapObjectTag);
+  Node* limit =
+      ElementOffsetFromIndex(last_element_exclusive, kind, mode,
+                             FixedArray::kHeaderSize - kHeapObjectTag);
+  if (direction == ForEachDirection::kReverse) std::swap(start, limit);
+
+  int increment = IsFastDoubleElementsKind(kind) ? kDoubleSize : kPointerSize;
+  BuildFastLoop(
+      MachineType::PointerRepresentation(), start, limit,
+      [fixed_array, body](CodeStubAssembler* assembler, Node* index) {

[Igor Sheludko, 2016/10/04 09:32:25]

s/index/offset/

[danno, 2016/10/04 16:10:23]

Done.

+        body(assembler, fixed_array, index);
+      },
+      direction == ForEachDirection::kReverse ? -increment : increment,
+      direction == ForEachDirection::kReverse ? IndexAdvanceMode::kPre
+                                              : IndexAdvanceMode::kPost);
+}
+
 }  // namespace internal
 }  // namespace v8