Use call counts to prevent cold calls from being inlined.

runtime/vm/flow_graph_inliner.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/flow_graph_inliner.h"
 
 #include "vm/compiler.h"
 #include "vm/flags.h"
 #include "vm/flow_graph.h"
 #include "vm/flow_graph_builder.h"
@@ skipping 18 matching lines @@
 DEFINE_FLAG(int, inlining_in_loop_size_threshold, 80,
     "Inline functions in loops that have threshold or fewer instructions");
 DEFINE_FLAG(int, inlining_callee_call_sites_threshold, 1,
     "Always inline functions containing threshold or fewer calls.");
 DEFINE_FLAG(int, inlining_constant_arguments_count, 1,
     "Inline function calls with sufficient constant arguments "
     "and up to the increased threshold on instructions");
 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);
 DECLARE_FLAG(bool, verify_compiler);
 DECLARE_FLAG(bool, compiler_stats);
 
 #define TRACE_INLINING(statement)                                              \
   do {                                                                         \
     if (FLAG_trace_inlining) statement;                                        \
   } while (false)
@@ skipping 127 matching lines @@
 
 
 // A collection of call sites to consider for inlining.
 class CallSites : public FlowGraphVisitor {
  public:
   explicit CallSites(FlowGraph* flow_graph)
       : FlowGraphVisitor(flow_graph->postorder()),  // We don't use this order.
         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());
   }
 
   void Clear() {
     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());
     const Code& code = Code::Handle(function.unoptimized_code());
     skip_static_call_deopt_ids_.Clear();
     code.ExtractUncalledStaticCallDeoptIds(&skip_static_call_deopt_ids_);
     for (BlockIterator block_it = graph->postorder_iterator();
          !block_it.Done();
          block_it.Advance()) {
       for (ForwardInstructionIterator it(block_it.Current());
            !it.Done();
            it.Advance()) {
         it.Current()->Accept(this);
       }
     }
+    caller_count_ = prev_caller_count;
   }
 
   void VisitClosureCall(ClosureCallInstr* call) {
     closure_calls_.Add(call);
   }
 
   void VisitPolymorphicInstanceCall(PolymorphicInstanceCallInstr* call) {
     instance_calls_.Add(call);
+    instance_calls_caller_count_.Add(caller_count_);
   }
 
   void VisitStaticCall(StaticCallInstr* call) {
     if (!call->function().IsInlineable()) return;
     const intptr_t call_deopt_id = call->deopt_id();
     for (intptr_t i = 0; i < skip_static_call_deopt_ids_.length(); i++) {
       if (call_deopt_id == skip_static_call_deopt_ids_[i]) {
         // Do not inline this call.
         return;
       }
     }
     static_calls_.Add(call);
   }
 
  private:
   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);
 };
 
 
 class CallSiteInliner : public ValueObject {
  public:
   explicit CallSiteInliner(FlowGraph* flow_graph)
       : caller_graph_(flow_graph),
         inlined_(false),
@@ skipping 31 matching lines @@
   void InlineCalls() {
     // If inlining depth is less then one abort.
     if (FLAG_inlining_depth_threshold < 1) return;
     // Create two call site collections to swap between.
     CallSites sites1(caller_graph_);
     CallSites sites2(caller_graph_);
     CallSites* call_sites_temp = NULL;
     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.
       call_sites_temp = collected_call_sites_;
       collected_call_sites_ = inlining_call_sites_;
       inlining_call_sites_ = call_sites_temp;
       collected_call_sites_->Clear();
       // Inline call sites at the current depth.
       InlineStaticCalls();
       InlineClosureCalls();
       InlineInstanceCalls();
       // Increment the inlining depth. Checked before recursive inlining.
       ++inlining_depth_;
     }
     collected_call_sites_ = NULL;
     inlining_call_sites_ = NULL;
   }
 
   bool inlined() const { return inlined_; }
 
   double GrowthFactor() const {
     return static_cast<double>(inlined_size_) /
         static_cast<double>(initial_size_);
   }
 
  private:
   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()));
 
     // Abort if the inlinable bit on the function is low.
     if (!function.IsInlineable()) {
       TRACE_INLINING(OS::Print("     Bailout: not inlinable\n"));
       return false;
     }
 
@@ skipping 156 matching lines @@
                                  "const args: %"Pd"\n",
                                  loop_depth,
                                  size,
                                  info.call_site_count(),
                                  constants_count));
         return false;
       }
 
       // 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);
       }
 
       {
         TimerScope timer(FLAG_compiler_stats,
                          &CompilerStats::graphinliner_subst_timer,
                          isolate);
 
         // Plug result in the caller graph.
         caller_graph_->InlineCall(call, callee_graph);
 
@@ skipping 69 matching lines @@
     }
     *in_cache = false;
     ParsedFunction* parsed_function = new ParsedFunction(function);
     Parser::ParseFunction(parsed_function);
     parsed_function->AllocateVariables();
     return parsed_function;
   }
 
   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];
       GrowableArray<Value*> arguments(call->ArgumentCount());
       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];
       // Find the closure of the callee.
       ASSERT(call->ArgumentCount() > 0);
       const CreateClosureInstr* closure =
           call->ArgumentAt(0)->value()->definition()->AsCreateClosure();
       if (closure == NULL) {
         TRACE_INLINING(OS::Print("     Bailout: non-closure operator\n"));
         continue;
       }
       GrowableArray<Value*> arguments(call->ArgumentCount());
       for (int i = 0; i < call->ArgumentCount(); ++i) {
         arguments.Add(call->ArgumentAt(i)->value());
       }
       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]);
     }
   }
 
   void AdjustForOptionalParameters(const ParsedFunction& parsed_function,
                                    const Array& argument_names,
                                    GrowableArray<Value*>* arguments,
                                    GrowableArray<Definition*>* param_stubs,
                                    FlowGraph* callee_graph) {
     const Function& function = parsed_function.function();
     // The language and this code does not support both optional positional
@@ skipping 123 matching lines @@
         OS::Print("After Inlining of %s\n", flow_graph_->
                   parsed_function().function().ToFullyQualifiedCString());
         FlowGraphPrinter printer(*flow_graph_);
         printer.PrintBlocks();
       }
     }
   }
 }
 
 }  // namespace dart