Make HJSArrayLength more likely to have identical GVNs.

src/hydrogen.cc

 // Copyright 2012 the V8 project authors. All rights reserved.
 // Redistribution and use in source and binary forms, with or without
 // modification, are permitted provided that the following conditions are
 // met:
 //
 //     * Redistributions of source code must retain the above copyright
 //       notice, this list of conditions and the following disclaimer.
 //     * Redistributions in binary form must reproduce the above
 //       copyright notice, this list of conditions and the following
 //       disclaimer in the documentation and/or other materials provided
@@ skipping 679 matching lines @@
 }
 
 
 HGraph::HGraph(CompilationInfo* info)
     : isolate_(info->isolate()),
       next_block_id_(0),
       entry_block_(NULL),
       blocks_(8, info->zone()),
       values_(16, info->zone()),
       phi_list_(NULL),
+      array_lengths_(8, info->zone()),
       uint32_instructions_(NULL),
       info_(info),
       zone_(info->zone()),
       is_recursive_(false),
       use_optimistic_licm_(false),
       type_change_checksum_(0) {
   start_environment_ =
       new(zone_) HEnvironment(NULL, info->scope(), info->closure(), zone_);
   start_environment_->set_ast_id(BailoutId::FunctionEntry());
   entry_block_ = CreateBasicBlock();
   entry_block_->SetInitialEnvironment(start_environment_);
 }
 
 
 HBasicBlock* HGraph::CreateBasicBlock() {
   HBasicBlock* result = new(zone()) HBasicBlock(this);
   blocks_.Add(result, zone());
   return result;
 }
 
 
+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);
   for (int i = 0; i < blocks()->length(); ++i) {
     HInstruction* instr = blocks()->at(i)->first();
     while (instr != NULL) {
       HValue* value = instr->Canonicalize();
       if (value != instr) instr->DeleteAndReplaceWith(value);
       instr = instr->next();
     }
@@ skipping 2564 matching lines @@
 
   InitializeInferredTypes();
 
   // Must be performed before canonicalization to ensure that Canonicalize
   // will not remove semantically meaningful ToInt32 operations e.g. BIT_OR with
   // zero.
   ComputeSafeUint32Operations();
 
   Canonicalize();
 
+  ProcessJSArrayLengths();
+
   // Perform common subexpression elimination and loop-invariant code motion.
   if (FLAG_use_gvn) {
     HPhase phase("H_Global value numbering", this);
     HGlobalValueNumberer gvn(this, info());
     bool removed_side_effects = gvn.Analyze();
     // Trigger a second analysis pass to further eliminate duplicate values that
     // could only be discovered by removing side-effect-generating instructions
     // during the first pass.
     if (FLAG_smi_only_arrays && removed_side_effects) {
       removed_side_effects = gvn.Analyze();
@@ skipping 2842 matching lines @@
         new(zone()) HLoadExternalArrayPointer(elements);
     AddInstruction(external_elements);
     return BuildExternalArrayElementAccess(
         external_elements, checked_key, val, mapcheck,
         map->elements_kind(), is_store);
   }
   ASSERT(fast_smi_only_elements ||
          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));
   }
   checked_key = AddInstruction(new(zone()) HBoundsCheck(key, length,
                                                         ALLOW_SMI_KEY));
   return BuildFastElementAccess(elements, checked_key, val, mapcheck,
                                 map->elements_kind(), is_store);
 }
 
 
@@ skipping 203 matching lines @@
         HBasicBlock* if_jsarray = graph()->CreateBasicBlock();
         HBasicBlock* if_fastobject = graph()->CreateBasicBlock();
         HHasInstanceTypeAndBranch* typecheck =
             new(zone()) HHasInstanceTypeAndBranch(object, JS_ARRAY_TYPE);
         typecheck->SetSuccessorAt(0, if_jsarray);
         typecheck->SetSuccessorAt(1, if_fastobject);
         current_block()->Finish(typecheck);
 
         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(
             elements, checked_key, val, elements_kind_branch,
             elements_kind, is_store));
         if (!is_store) {
           Push(access);
         }
 
         *has_side_effects |= access->HasObservableSideEffects();
@@ skipping 184 matching lines @@
   if (TryArgumentsAccess(expr)) return;
 
   CHECK_ALIVE(VisitForValue(expr->obj()));
 
   HInstruction* instr = NULL;
   if (expr->AsProperty()->IsArrayLength()) {
     HValue* array = Pop();
     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));
     AddInstruction(HCheckInstanceType::NewIsString(string, zone()));
     instr = new(zone()) HStringLength(string);
   } else if (expr->IsStringAccess()) {
     CHECK_ALIVE(VisitForValue(expr->key()));
     HValue* index = Pop();
     HValue* string = Pop();
     HValue* context = environment()->LookupContext();
@@ skipping 3450 matching lines @@
     }
   }
 
 #ifdef DEBUG
   if (graph_ != NULL) graph_->Verify(false);  // No full verify.
   if (allocator_ != NULL) allocator_->Verify();
 #endif
 }
 
 } }  // namespace v8::internal