Make HJSArrayLength more likely to have identical GVNs.

src/hydrogen.cc

Index: src/hydrogen.cc
diff --git a/src/hydrogen.cc b/src/hydrogen.cc
index 1590ab36698d9d5b98605111966ed17b8c7bc2a8..0640434f186bf3ff4b752bd323cf7250caa98277 100644
--- a/src/hydrogen.cc
+++ b/src/hydrogen.cc
@@ -697,6 +697,7 @@ HGraph::HGraph(CompilationInfo* info)
       blocks_(8, info->zone()),
       values_(16, info->zone()),
       phi_list_(NULL),
+      array_lengths_(8, info->zone()),
       uint32_instructions_(NULL),
       info_(info),
       zone_(info->zone()),
@@ -718,6 +719,98 @@ HBasicBlock* HGraph::CreateBasicBlock() {
 }
 
 
+static int CompareJSArrayLengthsByValues(HJSArrayLength* const* x,
+                                         HJSArrayLength* const* y) {
+  return Compare<int>((*x)->value()->id(), (*y)->value()->id());
+}
+
+
+void HGraph::ProcessJSArrayLengths() {
+  HPhase phase("H_ProcessJSArrayLengths", this);
+  array_lengths_.Sort(CompareJSArrayLengthsByValues);
+
+  int group_start_index = 0;
+  while (group_start_index < array_lengths_.length()) {
+    // First, find the set of HJSArrayLength insts that operate on the same

[danno, 2012/11/28 12:44:31]

please don't use abbreviations, "insts" should be "instructions" everywhere in
your CL.

+    // array and see if all the ones that are guarded by a map check do a
+    // check for the same map.
+    bool map_check_can_be_shared = true;
+    HCheckMaps* map_check = NULL;
+    HType type = HType::Tagged();
+    int group_end_index = group_start_index;
+    while (group_end_index < array_lengths_.length() &&

[danno, 2012/11/28 12:44:31]

This algorithm is a no-go. It  is quadratic with respect to
array_lengths_.length().

+        array_lengths_.at(group_end_index)->value()->id() ==
+            array_lengths_.at(group_start_index)->value()->id()) {
+      HJSArrayLength* inst = array_lengths_.at(group_end_index);
+      if (inst->typecheck()->IsCheckMaps()) {
+        HCheckMaps* current_map_check = HCheckMaps::cast(inst->typecheck());
+        if (current_map_check->has_dependency()) {
+          // Element transitions would cause deopts...
+          map_check_can_be_shared = false;
+        } else {
+          if (map_check != NULL) {
+            if (current_map_check->map_set()->length() ==
+                map_check->map_set()->length()) {
+              for (int i = 0; i < map_check->map_set()->length(); i++) {
+                if (*(map_check->map_set()->at(i)) !=
+                    *(current_map_check->map_set()->at(i))) {
+                  map_check_can_be_shared = false;
+                  break;
+                }
+
+                // Record the check higher in the dominator tree.
+                if (current_map_check->block()->Dominates(
+                    map_check->block())) {
+                  map_check = current_map_check;

[danno, 2012/11/28 12:44:31]

This is not sufficient and leads to incorrect code. If an intervening operation
changes array lengths, you will combine one or more length operations that are
not equivalent. That's why we have DependsOn and Changes in GVN in the first
place.

+                }
+              }
+            } else {
+              map_check_can_be_shared = false;
+            }
+          } else {
+            map_check = current_map_check;
+            type = inst->type();
+          }
+        }
+      } else if (!inst->typecheck()->IsCheckInstanceType()) {
+        map_check_can_be_shared = false;
+      }
+
+      group_end_index++;
+    }
+
+    // If we do have a map check and it is unique, make so that all the other
+    // HJSArrayLength instructions are guarded by the same check.
+    if (map_check != NULL && map_check_can_be_shared) {
+      for (int i = group_start_index; i < group_end_index; i++) {
+        HJSArrayLength* inst = array_lengths_.at(i);
+        if (inst->typecheck()->IsCheckInstanceType()) {
+          HValue* typecheck = inst->typecheck();
+          // For now don't handle complex cases which should not even happen.
+          if (typecheck->UseCount() == 1) {
+            // Use new_check directly if it dominates this location, otherwise
+            // create a new identical check (GVN can collapse them anyway).
+            HCheckMaps* new_check;
+            if (map_check->block()->Dominates(inst->block())) {
+              new_check = map_check;
+            } else {
+              new_check = new(zone()) HCheckMaps(
+                  inst->value(), map_check->map_set(), zone());
+              new_check->InsertBefore(inst);
+            }
+            typecheck->DeleteAndReplaceWith(new_check);
+            inst->set_type(type);
+          }
+        }
+      }
+    }
+
+    // Move to next "group".
+    group_start_index = group_end_index;
+  }
+}
+
+
 void HGraph::Canonicalize() {
   if (!FLAG_use_canonicalizing) return;
   HPhase phase("H_Canonicalize", this);
@@ -3302,6 +3395,8 @@ bool HGraph::Optimize(SmartArrayPointer<char>* bailout_reason) {
 
   Canonicalize();
 
+  ProcessJSArrayLengths();
+
   // Perform common subexpression elimination and loop-invariant code motion.
   if (FLAG_use_gvn) {
     HPhase phase("H_Global value numbering", this);
@@ -6164,8 +6259,8 @@ HInstruction* HGraphBuilder::BuildUncheckedMonomorphicElementAccess(
          fast_elements ||
          map->has_fast_double_elements());
   if (map->instance_type() == JS_ARRAY_TYPE) {
-    length = AddInstruction(new(zone()) HJSArrayLength(object, mapcheck,
-                                                       HType::Smi()));
+    length = AddInstruction(HJSArrayLength::Create(
+        graph(), object, mapcheck, HType::Smi()));
   } else {
     length = AddInstruction(new(zone()) HFixedArrayBaseLength(elements));
   }
@@ -6389,8 +6484,8 @@ HValue* HGraphBuilder::HandlePolymorphicElementAccess(HValue* object,
 
         set_current_block(if_jsarray);
         HInstruction* length;
-        length = AddInstruction(new(zone()) HJSArrayLength(object, typecheck,
-                                                           HType::Smi()));
+        length = AddInstruction(HJSArrayLength::Create(
+            graph(), object, typecheck, HType::Smi()));
         checked_key = AddInstruction(new(zone()) HBoundsCheck(key, length,
                                                               ALLOW_SMI_KEY));
         access = AddInstruction(BuildFastElementAccess(
@@ -6595,7 +6690,7 @@ void HGraphBuilder::VisitProperty(Property* expr) {
     AddInstruction(new(zone()) HCheckNonSmi(array));
     HInstruction* mapcheck =
         AddInstruction(HCheckInstanceType::NewIsJSArray(array, zone()));
-    instr = new(zone()) HJSArrayLength(array, mapcheck);
+    instr = HJSArrayLength::Create(graph(), array, mapcheck);
   } else if (expr->IsStringLength()) {
     HValue* string = Pop();
     AddInstruction(new(zone()) HCheckNonSmi(string));