Consolidate similar KeyedLoads to worst case instead of transitioning elements

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 5731 matching lines @@
   }
 }
 
 
 HInstruction* HGraphBuilder::BuildMonomorphicElementAccess(HValue* object,
                                                            HValue* key,
                                                            HValue* val,
                                                            HValue* dependency,
                                                            Handle<Map> map,
                                                            bool is_store) {
-  HInstruction* mapcheck =
-      AddInstruction(new(zone()) HCheckMaps(object, map, zone(), dependency));
+  HCheckMaps* mapcheck = new(zone()) HCheckMaps(object, map,
+                                                zone(), dependency);
+  AddInstruction(mapcheck);
+  if (dependency) {
+    mapcheck->ClearGVNFlag(kDependsOnElementsKind);
+  }
+  return BuildUncheckedMonomorphicElementAccess(object, key, val,
+                                                mapcheck, map, is_store);
+}
+
+
+HInstruction* HGraphBuilder::BuildUncheckedMonomorphicElementAccess(
+    HValue* object,
+    HValue* key,
+    HValue* val,
+    HCheckMaps* mapcheck,
+    Handle<Map> map,
+    bool is_store) {
   // No GVNFlag is necessary for ElementsKind if there is an explicit dependency
   // on a HElementsTransition instruction. The flag can also be removed if the
   // map to check has FAST_HOLEY_ELEMENTS, since there can be no further
   // ElementsKind transitions. Finally, the dependency can be removed for stores
   // for FAST_ELEMENTS, since a transition to HOLEY elements won't change the
   // generated store code.
-  if (dependency ||
-      (map->elements_kind() == FAST_HOLEY_ELEMENTS) ||
+  if ((map->elements_kind() == FAST_HOLEY_ELEMENTS) ||
       (map->elements_kind() == FAST_ELEMENTS && is_store)) {
     mapcheck->ClearGVNFlag(kDependsOnElementsKind);
   }
   bool fast_smi_only_elements = map->has_fast_smi_elements();
   bool fast_elements = map->has_fast_object_elements();
   HInstruction* elements = AddInstruction(new(zone()) HLoadElements(object));
   if (is_store && (fast_elements || fast_smi_only_elements)) {
     HCheckMaps* check_cow_map = new(zone()) HCheckMaps(
         elements, isolate()->factory()->fixed_array_map(), zone());
     check_cow_map->ClearGVNFlag(kDependsOnElementsKind);
@@ skipping 18 matching lines @@
                                                        HType::Smi()));
   } else {
     length = AddInstruction(new(zone()) HFixedArrayBaseLength(elements));
   }
   checked_key = AddInstruction(new(zone()) HBoundsCheck(key, length));
   return BuildFastElementAccess(elements, checked_key, val,
                                 map->elements_kind(), is_store);
 }
 
 
+HInstruction* HGraphBuilder::TryBuildConsolidatedElementLoad(
+    HValue* object,
+    HValue* key,
+    HValue* val,
+    SmallMapList* maps) {
+  // For polymorphic loads of similar elements kinds (i.e. all tagged or all
+  // double), always use the "worst case" code without a transition.  This is
+  // much faster than transitioning the elements to the worst case, trading a
+  // HTransitionElements for a HCheckMaps, and avoiding mutation of the array.
+  bool has_double_maps = false;
+  bool has_smi_or_object_maps = false;
+  bool has_js_array_access = false;
+  bool has_non_js_array_access = false;
+  Handle<Map> most_general_consolidated_map;
+  for (int i = 0; i < maps->length(); ++i) {
+    Handle<Map> map = maps->at(i);
+    // Don't allow mixing of JSArrays with JSObjects.
+    if (map->instance_type() == JS_ARRAY_TYPE) {
+      if (has_non_js_array_access) return NULL;
+      has_js_array_access = true;
+    } else if (has_js_array_access) {
+      return NULL;
+    } else {
+      has_non_js_array_access = true;
+    }
+    // Don't allow mixed, incompatible elements kinds.
+    if (map->has_fast_double_elements()) {
+      if (has_smi_or_object_maps) return NULL;
+      has_double_maps = true;
+    } else if (map->has_fast_smi_or_object_elements()) {
+      if (has_double_maps) return NULL;
+      has_smi_or_object_maps = true;
+    } else {
+      return NULL;
+    }
+    // Remember the most general elements kind, the code for its load will
+    // properly handle all of the more specific cases.
+    if ((i == 0) || IsMoreGeneralElementsKindTransition(
+            most_general_consolidated_map->elements_kind(),
+            map->elements_kind())) {
+      most_general_consolidated_map = map;
+    }
+  }
+  if (!has_double_maps && !has_smi_or_object_maps) return NULL;
+
+  HCheckMaps* check_maps =
+      new(zone()) HCheckMaps(object, maps, zone());

[Jakob Kummerow, 2012/06/29 18:42:41]

nit: fits on one line

[danno, 2012/07/02 11:07:14]

Done.

+  AddInstruction(check_maps);
+  HInstruction* instr = BuildUncheckedMonomorphicElementAccess(
+      object, key, val,
+      check_maps, most_general_consolidated_map, false);

[Jakob Kummerow, 2012/06/29 18:42:41]

nit: fits on the same line as "object, key, val".

[danno, 2012/07/02 11:07:14]

Done.

+  return instr;
+}
+
+
 HValue* HGraphBuilder::HandlePolymorphicElementAccess(HValue* object,
                                                       HValue* key,
                                                       HValue* val,
                                                       Expression* prop,
                                                       int ast_id,
                                                       int position,
                                                       bool is_store,
                                                       bool* has_side_effects) {
   *has_side_effects = false;
   AddInstruction(new(zone()) HCheckNonSmi(object));
   SmallMapList* maps = prop->GetReceiverTypes();
   bool todo_external_array = false;
 
+  if (!is_store) {
+    HInstruction* consolidated_load =
+        TryBuildConsolidatedElementLoad(object, key, val, maps);
+    if (consolidated_load != NULL) {
+      AddInstruction(consolidated_load);
+      *has_side_effects |= consolidated_load->HasObservableSideEffects();
+      consolidated_load->set_position(position);
+      return consolidated_load;
+    }
+  }
+
   static const int kNumElementTypes = kElementsKindCount;
   bool type_todo[kNumElementTypes];
   for (int i = 0; i < kNumElementTypes; ++i) {
     type_todo[i] = false;
   }
 
   // Elements_kind transition support.
   MapHandleList transition_target(maps->length());
   // Collect possible transition targets.
   MapHandleList possible_transitioned_maps(maps->length());
@@ skipping 35 matching lines @@
       untransitionable_map = map;
     }
   }
 
   // If only one map is left after transitioning, handle this case
   // monomorphically.
   if (num_untransitionable_maps == 1) {
     HInstruction* instr = NULL;
     if (untransitionable_map->has_slow_elements_kind()) {
       instr = AddInstruction(is_store ? BuildStoreKeyedGeneric(object, key, val)
-                                      : BuildLoadKeyedGeneric(object, key));
+                             : BuildLoadKeyedGeneric(object, key));

[Jakob Kummerow, 2012/06/29 18:42:41]

nit: why this change?

[danno, 2012/07/02 11:07:14]

Done.

     } else {
       instr = AddInstruction(BuildMonomorphicElementAccess(
           object, key, val, transition, untransitionable_map, is_store));
     }
     *has_side_effects |= instr->HasObservableSideEffects();
     instr->set_position(position);
     return is_store ? NULL : instr;
   }
 
   AddInstruction(HCheckInstanceType::NewIsSpecObject(object, zone()));
@@ skipping 3561 matching lines @@
     }
   }
 
 #ifdef DEBUG
   if (graph_ != NULL) graph_->Verify(false);  // No full verify.
   if (allocator_ != NULL) allocator_->Verify();
 #endif
 }
 
 } }  // namespace v8::internal