Sort checks by counts before emitting test-and-call polymorphic instance calls.

runtime/vm/flow_graph_compiler.cc

 // Copyright (c) 2012, the Dart project authors.  Please see the AUTHORS file
 // for details. All rights reserved. Use of this source code is governed by a
 // BSD-style license that can be found in the LICENSE file.
 
 #include "vm/globals.h"  // Needed here to get TARGET_ARCH_XXX.
 
 #include "vm/flow_graph_compiler.h"
 
 #include "vm/cha.h"
 #include "vm/dart_entry.h"
@@ skipping 610 matching lines @@
 
 
 void FlowGraphCompiler::EmitComment(Instruction* instr) {
   char buffer[256];
   BufferFormatter f(buffer, sizeof(buffer));
   instr->PrintTo(&f);
   assembler()->Comment("%s", buffer);
 }
 
 
+struct CidTarget {
+  intptr_t cid;
+  Function* target;
+  intptr_t count;
+  CidTarget(intptr_t cid_arg,
+            Function* target_arg,
+            intptr_t count_arg)
+      : cid(cid_arg), target(target_arg), count(count_arg) {}
+};
+
+
+// Returns 'sorted' array in decreasing count order.
+// The expected number of elements to sort is less than 10.
+static void SortICDataByCount(const ICData& ic_data,
+                              GrowableArray<CidTarget>* sorted) {
+  ASSERT(ic_data.num_args_tested() == 1);
+  const intptr_t len = ic_data.NumberOfChecks();
+  sorted->Clear();
+
+  for (int i = 0; i < len; i++) {
+    sorted->Add(CidTarget(ic_data.GetReceiverClassIdAt(i),
+                          &Function::ZoneHandle(ic_data.GetTargetAt(i)),
+                          ic_data.GetCountAt(i)));
+  }
+  for (int i = 0; i < len; i++) {
+    intptr_t largest_ix = i;
+    for (int k = i + 1; k < len; k++) {
+      if ((*sorted)[largest_ix].count < (*sorted)[k].count) {

[regis, 2012/12/27 17:52:30]

You could assign (*sorted)[largest_ix].count to largest_count outside of the
loop for better readability and greater speed, in debug mode at least :-)

[srdjan, 2012/12/27 18:19:42]

largest_ix is not loop invariant. Maintaining the largest count in sync with
largest_ix makes the code less readable, IMHO. Let me know if you disagree.

[regis, 2012/12/27 18:26:35]

I do not disagree :-) Slow start after the break... 

+        largest_ix = k;
+      }
+    }
+    if (i != largest_ix) {
+      // Swap.
+      CidTarget temp = (*sorted)[i];
+      (*sorted)[i] = (*sorted)[largest_ix];
+      (*sorted)[largest_ix] = temp;
+    }
+  }
+}
+
+
 void FlowGraphCompiler::EmitTestAndCall(const ICData& ic_data,
                                         Register class_id_reg,
                                         intptr_t arg_count,
                                         const Array& arg_names,
                                         Label* deopt,
                                         intptr_t deopt_id,
                                         intptr_t token_index,
                                         LocationSummary* locs) {
   ASSERT(!ic_data.IsNull() && (ic_data.NumberOfChecks() > 0));
   Label match_found;
   const intptr_t len = ic_data.NumberOfChecks();
+  GrowableArray<CidTarget> sorted(len);
+  SortICDataByCount(ic_data, &sorted);
   for (intptr_t i = 0; i < len; i++) {
     const bool is_last_check = (i == (len - 1));
     Label next_test;
-    assembler()->cmpl(class_id_reg, Immediate(ic_data.GetReceiverClassIdAt(i)));
+    assembler()->cmpl(class_id_reg, Immediate(sorted[i].cid));
     if (is_last_check) {
       assembler()->j(NOT_EQUAL, deopt);
     } else {
       assembler()->j(NOT_EQUAL, &next_test);
     }
-    const Function& target = Function::ZoneHandle(ic_data.GetTargetAt(i));
     GenerateStaticCall(deopt_id,
                        token_index,
-                       target,
+                       *sorted[i].target,
                        arg_count,
                        arg_names,
                        locs);
     if (!is_last_check) {
       assembler()->jmp(&match_found);
     }
     assembler()->Bind(&next_test);
   }
   assembler()->Bind(&match_found);
 }
@@ skipping 367 matching lines @@
     const AbstractTypeArguments& type_arguments =
         AbstractTypeArguments::Handle(type.arguments());
     const bool is_raw_type = type_arguments.IsNull() ||
         type_arguments.IsRaw(type_arguments.Length());
     return is_raw_type;
   }
   return true;
 }
 
 }  // namespace dart