Polymorphic named calls optimized for the case of repetitive call targets.

src/hydrogen.cc

 // Copyright 2013 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 6744 matching lines @@
 
 
 void HOptimizedGraphBuilder::HandlePolymorphicCallNamed(
     Call* expr,
     HValue* receiver,
     SmallMapList* types,
     Handle<String> name) {
   if (TryCallPolymorphicAsMonomorphic(expr, receiver, types, name)) return;
 
   int argument_count = expr->arguments()->length() + 1;  // Includes receiver.
-  HBasicBlock* join = NULL;
-  FunctionSorter order[kMaxCallPolymorphism];
-  int ordered_functions = 0;
 
   Handle<Map> initial_string_map(
       isolate()->native_context()->string_function()->initial_map());
   Handle<Map> string_marker_map(
       JSObject::cast(initial_string_map->prototype())->map());
   Handle<Map> initial_number_map(
       isolate()->native_context()->number_function()->initial_map());
   Handle<Map> number_marker_map(
       JSObject::cast(initial_number_map->prototype())->map());
   Handle<Map> heap_number_map = isolate()->factory()->heap_number_map();
 
   bool handle_smi = false;
 
+  // A map from functions to a set of receivers' maps.
+  struct FuncMapEntry {
+    Handle<JSFunction> func;
+    SmallMapList maps;
+  };
+  FuncMapEntry func_map[kMaxCallPolymorphism];
+  FunctionSorter order[kMaxCallPolymorphism];
+  int func_count = 0;
+  int maps_count = 0;
+
   for (int i = 0;
-       i < types->length() && ordered_functions < kMaxCallPolymorphism;
+       i < types->length() && func_count < kMaxCallPolymorphism;
        ++i) {
     Handle<Map> map = types->at(i);
     if (expr->ComputeTarget(map, name)) {
       if (map.is_identical_to(number_marker_map)) handle_smi = true;
-      order[ordered_functions++] =
-          FunctionSorter(i,
-                         expr->target()->shared()->profiler_ticks(),
-                         InliningAstSize(expr->target()),
-                         expr->target()->shared()->SourceSize());
+
+      // Try to find the target function among known targets.
+      int func_index = 0;
+      for (; func_index < func_count; ++func_index) {
+        if (*func_map[func_index].func == *expr->target()) {
+          break;
+        }
+      }
+      FuncMapEntry* entry = &func_map[func_index];
+      if (func_index == func_count) {
+        // Entry not found, "allocate" it.
+        entry->func = expr->target();
+        entry->maps.Reserve(types->length() - maps_count, zone());
+        order[func_index] =
+            FunctionSorter(func_index,
+                           entry->func->shared()->profiler_ticks(),
+                           InliningAstSize(entry->func),
+                           entry->func->shared()->SourceSize());
+        ++func_count;
+      }
+      entry->maps.Add(map, zone());
+      ++maps_count;
     }
   }
 
-  std::sort(order, order + ordered_functions);
+  std::sort(order, order + func_count);
 
   HBasicBlock* number_block = NULL;
+  HBasicBlock* join = NULL;
 
-  for (int fn = 0; fn < ordered_functions; ++fn) {
+  if (func_count > 0) {
+    // Only needed once.
+    join = graph()->CreateBasicBlock();
+    if (handle_smi) {
+      HBasicBlock* empty_smi_block = graph()->CreateBasicBlock();
+      HBasicBlock* not_smi_block = graph()->CreateBasicBlock();
+      number_block = graph()->CreateBasicBlock();
+      FinishCurrentBlock(New<HIsSmiAndBranch>(
+              receiver, empty_smi_block, not_smi_block));

[Toon Verwaest, 2014/01/03 07:42:49]

4-space indent

+      Goto(empty_smi_block, number_block);
+      set_current_block(not_smi_block);
+    } else {
+      BuildCheckHeapObject(receiver);
+    }
+  }
+
+  for (int fn = 0; fn < func_count; ++fn) {
     int i = order[fn].index();
-    Handle<Map> map = types->at(i);
-    if (fn == 0) {
-      // Only needed once.
-      join = graph()->CreateBasicBlock();
-      if (handle_smi) {
-        HBasicBlock* empty_smi_block = graph()->CreateBasicBlock();
-        HBasicBlock* not_smi_block = graph()->CreateBasicBlock();
-        number_block = graph()->CreateBasicBlock();
-        FinishCurrentBlock(New<HIsSmiAndBranch>(
-                receiver, empty_smi_block, not_smi_block));
-        Goto(empty_smi_block, number_block);
-        set_current_block(not_smi_block);
+    FuncMapEntry* func_map_entry = &func_map[i];
+
+    HBasicBlock* call_block = graph()->CreateBasicBlock();
+    HBasicBlock* if_false = NULL;
+
+    int maps_count = func_map_entry->maps.length();
+    for (int m = 0; m < maps_count; ++m) {
+      Handle<Map> map = func_map_entry->maps.at(m);
+      HBasicBlock* if_true = graph()->CreateBasicBlock();
+      if_false = graph()->CreateBasicBlock();
+      HUnaryControlInstruction* compare;
+
+      if (handle_smi && map.is_identical_to(number_marker_map)) {
+        compare =
+            New<HCompareMap>(receiver, heap_number_map, if_true, if_false);
+        map = initial_number_map;
+        expr->set_number_check(
+            Handle<JSObject>(JSObject::cast(map->prototype())));
+      } else if (map.is_identical_to(string_marker_map)) {
+        compare = New<HIsStringAndBranch>(receiver, if_true, if_false);
+        map = initial_string_map;
+        expr->set_string_check(
+            Handle<JSObject>(JSObject::cast(map->prototype())));
       } else {
-        BuildCheckHeapObject(receiver);
+        compare = New<HCompareMap>(receiver, map, if_true, if_false);
+        expr->set_map_check();
       }
-    }
-    HBasicBlock* if_true = graph()->CreateBasicBlock();
-    HBasicBlock* if_false = graph()->CreateBasicBlock();
-    HUnaryControlInstruction* compare;
 
-    if (handle_smi && map.is_identical_to(number_marker_map)) {
-      compare = New<HCompareMap>(receiver, heap_number_map, if_true, if_false);
-      map = initial_number_map;
-      expr->set_number_check(
-          Handle<JSObject>(JSObject::cast(map->prototype())));
-    } else if (map.is_identical_to(string_marker_map)) {
-      compare = New<HIsStringAndBranch>(receiver, if_true, if_false);
-      map = initial_string_map;
-      expr->set_string_check(
-          Handle<JSObject>(JSObject::cast(map->prototype())));
-    } else {
-      compare = New<HCompareMap>(receiver, map, if_true, if_false);
-      expr->set_map_check();
+      FinishCurrentBlock(compare);
+
+      if (expr->check_type() == NUMBER_CHECK) {
+        Goto(if_true, number_block);
+        if_true = number_block;
+        number_block->SetJoinId(expr->id());
+      }
+      set_current_block(if_true);
+
+      expr->ComputeTarget(map, name);
+      ASSERT(*expr->target() == *func_map_entry->func);
+
+      AddCheckPrototypeMaps(expr->holder(), map);
+
+      Goto(if_true, call_block);
+
+      set_current_block(if_false);
     }
 
-    FinishCurrentBlock(compare);
+    // Generate call once for all corresponding maps.
+    call_block->SetJoinId(expr->id());
+    set_current_block(call_block);
 
-    if (expr->check_type() == NUMBER_CHECK) {
-      Goto(if_true, number_block);
-      if_true = number_block;
-      number_block->SetJoinId(expr->id());
-    }
-    set_current_block(if_true);
-
-    expr->ComputeTarget(map, name);
-    AddCheckPrototypeMaps(expr->holder(), map);
     if (FLAG_trace_inlining && FLAG_polymorphic_inlining) {
       Handle<JSFunction> caller = current_info()->closure();
       SmartArrayPointer<char> caller_name =
           caller->shared()->DebugName()->ToCString();
       PrintF("Trying to inline the polymorphic call to %s from %s\n",
              name->ToCString().get(),
              caller_name.get());
     }
     if (FLAG_polymorphic_inlining && TryInlineCall(expr)) {
       // Trying to inline will signal that we should bailout from the
       // entire compilation by setting stack overflow on the visitor.
       if (HasStackOverflow()) return;
     } else {
       HCallConstantFunction* call =
           New<HCallConstantFunction>(expr->target(), argument_count);
       PreProcessCall(call);
       AddInstruction(call);
       if (!ast_context()->IsEffect()) Push(call);
     }
+    if (current_block() != NULL) Goto(join);
 
-    if (current_block() != NULL) Goto(join);
     set_current_block(if_false);
   }
 
   // Finish up.  Unconditionally deoptimize if we've handled all the maps we
   // know about and do not want to handle ones we've never seen.  Otherwise
   // use a generic IC.
-  if (ordered_functions == types->length() && FLAG_deoptimize_uncommon_cases) {
+  if (maps_count == types->length() && FLAG_deoptimize_uncommon_cases) {
     // Because the deopt may be the only path in the polymorphic call, make sure
     // that the environment stack matches the depth on deopt that it otherwise
     // would have had after a successful call.
     Drop(argument_count);
     if (!ast_context()->IsEffect()) Push(graph()->GetConstant0());
     FinishExitWithHardDeoptimization("Unknown map in polymorphic call", join);
   } else {
     HCallNamed* call = New<HCallNamed>(name, argument_count);
     PreProcessCall(call);
 
@@ skipping 3907 matching lines @@
   if (ShouldProduceTraceOutput()) {
     isolate()->GetHTracer()->TraceHydrogen(name(), graph_);
   }
 
 #ifdef DEBUG
   graph_->Verify(false);  // No full verify.
 #endif
 }
 
 } }  // namespace v8::internal