Use call counts to prevent cold calls from being inlined.

runtime/vm/flow_graph_inliner.cc

Index: runtime/vm/flow_graph_inliner.cc
===================================================================
--- runtime/vm/flow_graph_inliner.cc	(revision 16141)
+++ runtime/vm/flow_graph_inliner.cc	(working copy)
@@ -36,6 +36,9 @@
 DEFINE_FLAG(int, inlining_constant_arguments_size_threshold, 60,
     "Inline function calls with sufficient constant arguments "
     "and up to the increased threshold on instructions");
+DEFINE_FLAG(int, inlining_hotness, 15,
+    "Inline only hotter calls, in percents (0 .. 100); "
+    "default 20%: calls above-equal 20% of max-count are inlined.");

[Vyacheslav Egorov (Google), 2012/12/17 13:16:05]

comment does not match the default value.

[srdjan, 2012/12/17 22:46:13]

Done.

 
 DECLARE_FLAG(bool, print_flow_graph);
 DECLARE_FLAG(int, deoptimization_counter_threshold);
@@ -183,21 +186,28 @@
         static_calls_(),
         closure_calls_(),
         instance_calls_(),
-        skip_static_call_deopt_ids_() { }
+        instance_calls_caller_count_(),
+        skip_static_call_deopt_ids_(),
+        caller_count_(1) { }
 
-  GrowableArray<StaticCallInstr*>* static_calls() {
-    return &static_calls_;
+  const GrowableArray<StaticCallInstr*>& static_calls() const {
+    return static_calls_;
   }
 
-  GrowableArray<ClosureCallInstr*>* closure_calls() {
-    return &closure_calls_;
+  const GrowableArray<ClosureCallInstr*>& closure_calls() const {
+    return closure_calls_;
   }
 
-  GrowableArray<PolymorphicInstanceCallInstr*>* instance_calls() {
-    return &instance_calls_;
+  const GrowableArray<PolymorphicInstanceCallInstr*>& instance_calls() const {

[Vyacheslav Egorov (Google), 2012/12/17 13:16:05]

I'd prefer that this array contained a two field structure instead of having two
disconnected arrays with an assumption.

[srdjan, 2012/12/17 22:46:13]

Done.

+    return instance_calls_;
   }
 
+  const GrowableArray<intptr_t>& instance_calls_caller_count() const {
+    return instance_calls_caller_count_;
+  }
+
   bool HasCalls() const {
+    ASSERT(instance_calls_.length() == instance_calls_caller_count_.length());
     return !(static_calls_.is_empty() &&
              closure_calls_.is_empty() &&
              instance_calls_.is_empty());
@@ -207,10 +217,13 @@
     static_calls_.Clear();
     closure_calls_.Clear();
     instance_calls_.Clear();
+    instance_calls_caller_count_.Clear();
     skip_static_call_deopt_ids_.Clear();
   }
 
-  void FindCallSites(FlowGraph* graph) {
+  void FindCallSites(FlowGraph* graph, intptr_t caller_count) {
+    const intptr_t prev_caller_count = caller_count_;
+    caller_count_ = caller_count;
     ASSERT(graph != NULL);
     const Function& function = graph->parsed_function().function();
     ASSERT(function.HasCode());
@@ -226,6 +239,7 @@
         it.Current()->Accept(this);
       }
     }
+    caller_count_ = prev_caller_count;
   }
 
   void VisitClosureCall(ClosureCallInstr* call) {
@@ -234,6 +248,7 @@
 
   void VisitPolymorphicInstanceCall(PolymorphicInstanceCallInstr* call) {
     instance_calls_.Add(call);
+    instance_calls_caller_count_.Add(caller_count_);
   }
 
   void VisitStaticCall(StaticCallInstr* call) {
@@ -252,7 +267,9 @@
   GrowableArray<StaticCallInstr*> static_calls_;
   GrowableArray<ClosureCallInstr*> closure_calls_;
   GrowableArray<PolymorphicInstanceCallInstr*> instance_calls_;
+  GrowableArray<intptr_t> instance_calls_caller_count_;
   GrowableArray<intptr_t> skip_static_call_deopt_ids_;
+  intptr_t caller_count_;
 
   DISALLOW_COPY_AND_ASSIGN(CallSites);
 };
@@ -304,7 +321,7 @@
     collected_call_sites_ = &sites1;
     inlining_call_sites_ = &sites2;
     // Collect initial call sites.
-    collected_call_sites_->FindCallSites(caller_graph_);
+    collected_call_sites_->FindCallSites(caller_graph_, 1);
     while (collected_call_sites_->HasCalls()) {
       TRACE_INLINING(OS::Print("  Depth %"Pd" ----------\n", inlining_depth_));
       // Swap collected and inlining arrays and clear the new collecting array.
@@ -334,7 +351,8 @@
   bool TryInlining(const Function& function,
                    const Array& argument_names,
                    GrowableArray<Value*>* arguments,
-                   Definition* call) {
+                   Definition* call,
+                   intptr_t caller_count) {
     TRACE_INLINING(OS::Print("  => %s (deopt count %d)\n",
                              function.ToCString(),
                              function.deoptimization_counter()));
@@ -511,7 +529,7 @@
 
       // If depth is less or equal to threshold recursively add call sites.
       if (inlining_depth_ < FLAG_inlining_depth_threshold) {
-        collected_call_sites_->FindCallSites(callee_graph);
+        collected_call_sites_->FindCallSites(callee_graph, caller_count);
       }
 
       {
@@ -601,7 +619,7 @@
 
   void InlineStaticCalls() {
     const GrowableArray<StaticCallInstr*>& calls =
-        *inlining_call_sites_->static_calls();
+        inlining_call_sites_->static_calls();
     TRACE_INLINING(OS::Print("  Static Calls (%d)\n", calls.length()));
     for (intptr_t i = 0; i < calls.length(); ++i) {
       StaticCallInstr* call = calls[i];
@@ -609,13 +627,17 @@
       for (int i = 0; i < call->ArgumentCount(); ++i) {
         arguments.Add(call->ArgumentAt(i)->value());
       }
-      TryInlining(call->function(), call->argument_names(), &arguments, call);
+      TryInlining(call->function(),
+                  call->argument_names(),
+                  &arguments,
+                  call,
+                  1);
     }
   }
 
   void InlineClosureCalls() {
     const GrowableArray<ClosureCallInstr*>& calls =
-        *inlining_call_sites_->closure_calls();
+        inlining_call_sites_->closure_calls();
     TRACE_INLINING(OS::Print("  Closure Calls (%d)\n", calls.length()));
     for (intptr_t i = 0; i < calls.length(); ++i) {
       ClosureCallInstr* call = calls[i];
@@ -634,35 +656,60 @@
       TryInlining(closure->function(),
                   call->argument_names(),
                   &arguments,
-                  call);
+                  call,
+                  1);
     }
   }
 
   void InlineInstanceCalls() {
     const GrowableArray<PolymorphicInstanceCallInstr*>& calls =
-        *inlining_call_sites_->instance_calls();
+        inlining_call_sites_->instance_calls();
+    const GrowableArray<intptr_t>& calls_caller_count =
+        inlining_call_sites_->instance_calls_caller_count();
     TRACE_INLINING(OS::Print("  Polymorphic Instance Calls (%d)\n",
                              calls.length()));
+    GrowableArray<intptr_t> call_counts(calls.length());
+    intptr_t max_count = 0;
     for (intptr_t i = 0; i < calls.length(); ++i) {
+      const intptr_t count =
+          calls[i]->ic_data().AggregateCount() * calls_caller_count[i];

[Vyacheslav Egorov (Google), 2012/12/17 13:16:05]

I can't fully grasp the physical meaning behind this multiplication.

If we a descending through the call chain then as we go deeper call counts in
the callee are already in some sense including the call count of the caller. But
at the same time as we descend down we might encounter counters induced by some
other callchains to become higher.

Why do we multiply them?

Compare two call chains:

Imagine the following code:

A() { B() /* 10 */; D() /* 10 */; }
B() { C() /* 10 */; }
C() { /* code */ }
D() { E() /* 60 */; }
E() { /* code */ }
Z() { D(); /* 50 */ }

for (var i = 0; i < 50; i++) Z();
for (var i = 0; i < 10; i++) A();

According to this formula when compiling A and inlining both B and D we'll get
callsite C with count 100 and callsite E with count 600. This does not make much
sense to me. It contradicts the fact that call paths A => B => C and A => D => E
is equally hot.

[srdjan, 2012/12/17 22:46:13]

You are right. Changed to use a ratio per one scope.

+      call_counts.Add(count);
+      if (count > max_count) {
+        max_count = count;
+      }
+    }
+    for (intptr_t i = 0; i < calls.length(); ++i) {
       PolymorphicInstanceCallInstr* instr = calls[i];
       const ICData& ic_data = instr->ic_data();
       const Function& target = Function::ZoneHandle(ic_data.GetTargetAt(0));
       if (instr->with_checks()) {
         TRACE_INLINING(OS::Print(
-          "  => %s (deopt count %d)\n     Bailout: %"Pd" checks\n",
-          target.ToCString(),
-          target.deoptimization_counter(),
-          ic_data.NumberOfChecks()));
+            "  => %s (deopt count %d)\n     Bailout: %"Pd" checks\n",
+            target.ToCString(),
+            target.deoptimization_counter(),
+            ic_data.NumberOfChecks()));
         continue;
       }
+      const intptr_t count_threshold = FLAG_inlining_hotness < 0 ?
+          0 : (max_count * FLAG_inlining_hotness) / 100;
+      if (call_counts[i] < count_threshold) {
+        TRACE_INLINING(OS::Print(
+            "  => %s (deopt count %d)\n     Bailout: cold %"Pd" limit %"Pd"\n",
+            target.ToCString(),
+            target.deoptimization_counter(),
+            call_counts[i],
+            count_threshold));
+        continue;
+      }
       GrowableArray<Value*> arguments(instr->ArgumentCount());
-      for (int i = 0; i < instr->ArgumentCount(); ++i) {
-        arguments.Add(instr->ArgumentAt(i)->value());
+      for (int arg_i = 0; arg_i < instr->ArgumentCount(); ++arg_i) {
+        arguments.Add(instr->ArgumentAt(arg_i)->value());
       }
       TryInlining(target,
                   instr->instance_call()->argument_names(),
                   &arguments,
-                  instr);
+                  instr,
+                  call_counts[i]);
     }
   }