More inlining flags and tuned heuristics.

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"
 #include "vm/flow_graph_optimizer.h"
 #include "vm/il_printer.h"
 #include "vm/intrinsifier.h"
 #include "vm/longjump.h"
 #include "vm/object.h"
 #include "vm/object_store.h"
 #include "vm/timer.h"
 
 namespace dart {
 
 DEFINE_FLAG(bool, trace_inlining, false, "Trace inlining");
 DEFINE_FLAG(charp, inlining_filter, NULL, "Inline only in named function");
-DEFINE_FLAG(int, inlining_size_threshold, 50,
-    "Inline only functions with up to threshold instructions (default 50)");
-// TODO(srdjan): set to 3 once crash in apidoc.dart is resolved.
+
+// Flags for inlining heuristics.
 DEFINE_FLAG(int, inlining_depth_threshold, 3,
-    "Inline recursively up to threshold depth (default 3)");
+  "Inline function calls up to threshold nesting depth");

[Kevin Millikin (Google), 2012/10/25 14:44:08]

Inline ==> Always inline

+DEFINE_FLAG(int, inlining_size_threshold, 20,
+  "Inline function calls that have up to threshold instruction");

[Kevin Millikin (Google), 2012/10/25 14:44:08]

instruction ==> instructions

+DEFINE_FLAG(int, inlining_in_loop_size_threshold, 60,
+  "Inline function calls in loops that have up to threshold instructions");
+DEFINE_FLAG(int, inlining_callee_call_sites_threshold, 1,
+  "Inline function calls containing up to threshold call sites.");

[Kevin Millikin (Google), 2012/10/25 14:44:08]

"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, 40,
+  "Inline function calls with sufficient constant arguments "
+  "and up to the increased threshold on instructions");
+
 DECLARE_FLAG(bool, print_flow_graph);
 DECLARE_FLAG(int, deoptimization_counter_threshold);
 DECLARE_FLAG(bool, verify_compiler);
 DECLARE_FLAG(bool, compiler_stats);
 DECLARE_FLAG(bool, reject_named_argument_as_positional);
 
 #define TRACE_INLINING(statement)                                              \
   do {                                                                         \
     if (FLAG_trace_inlining) statement;                                        \
   } while (false)
@@ skipping 83 matching lines @@
 // Pair of an argument name and its value.
 struct NamedArgument : ValueObject {
  public:
   String* name;
   Value* value;
   NamedArgument(String* name, Value* value)
     : name(name), value(value) { }
 };
 
 
+// Helper to collect information about a callee graph.
+class GraphInfoCollector : public ValueObject {
+ public:
+  explicit GraphInfoCollector()
+      : call_site_count_(0),
+        instruction_count_(0) { }
+
+  void Collect(const FlowGraph& graph) {
+    call_site_count_ = 0;
+    instruction_count_ = 0;
+    for (BlockIterator block_it = graph.postorder_iterator();
+         !block_it.Done();
+         block_it.Advance()) {
+      for (ForwardInstructionIterator it(block_it.Current());
+           !it.Done();
+           it.Advance()) {
+        ++instruction_count_;
+        if (it.Current()->IsStaticCall() ||
+            it.Current()->IsClosureCall() ||
+            it.Current()->IsPolymorphicInstanceCall()) {
+          ++call_site_count_;
+        }
+      }
+    }
+  }
+
+  intptr_t call_site_count() const { return call_site_count_; }
+  intptr_t instruction_count() const { return instruction_count_; }
+
+ private:
+  intptr_t call_site_count_;
+  intptr_t instruction_count_;
+};
+
+
 // 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_() { }
 
   GrowableArray<StaticCallInstr*>* static_calls() {
@@ skipping 59 matching lines @@
       : caller_graph_(flow_graph),
         next_ssa_temp_index_(flow_graph->max_virtual_register_number()),
         inlined_(false),
         initial_size_(flow_graph->InstructionCount()),
         inlined_size_(0),
         inlining_depth_(1),
         collected_call_sites_(NULL),
         inlining_call_sites_(NULL),
         function_cache_() { }
 
+  // Inlining heuristics based on Cooper et al. 2008.
+  bool ShouldWeInline(intptr_t loop_depth,
+                      intptr_t size,
+                      intptr_t call_sites,
+                      intptr_t constant_args) {
+    return ((size <= FLAG_inlining_size_threshold) ||

[Kevin Millikin (Google), 2012/10/25 14:44:08]

This might be easier to read and modify if it were written:

if (size <= FLAG_inlining_size_threshold) return true;

if (call_sites <= FLAG_inlining_callee_call_sites_threshold) return true;

// etc.

return false;

+            (call_sites <= FLAG_inlining_callee_call_sites_threshold) ||
+            ((loop_depth > 0)
+             && (size <= FLAG_inlining_in_loop_size_threshold)) ||
+            ((constant_args >= FLAG_inlining_constant_arguments_count)
+             && (size <= FLAG_inlining_constant_arguments_size_threshold)));
+  }
+
   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.
@@ skipping 93 matching lines @@
       }
 
       // Load IC data for the callee.
       if (function.HasCode()) {
         const Code& unoptimized_code =
             Code::Handle(function.unoptimized_code());
         isolate->set_ic_data_array(unoptimized_code.ExtractTypeFeedbackArray());
       }
 
       // Build the callee graph.
+      const intptr_t loop_depth = call->GetBlock()->loop_depth();
       FlowGraphBuilder builder(*parsed_function);
       builder.SetInitialBlockId(caller_graph_->max_block_id());
       FlowGraph* callee_graph;
       {
         TimerScope timer(FLAG_compiler_stats,
                          &CompilerStats::graphinliner_build_timer,
                          isolate);
-        callee_graph = builder.BuildGraph(FlowGraphBuilder::kValueContext);
+        callee_graph =
+            builder.BuildGraph(FlowGraphBuilder::kValueContext, loop_depth);
       }
 
       // The parameter stubs are a copy of the actual arguments providing
       // concrete information about the values, for example constant values,
       // without linking between the caller and callee graphs.
       // TODO(zerny): Put more information in the stubs, eg, type information.
       GrowableArray<Definition*> param_stubs(function.NumParameters());
 
       // Create a parameter stub for each fixed positional parameter.
       for (intptr_t i = 0; i < function.num_fixed_parameters(); ++i) {
@@ skipping 44 matching lines @@
         callee_graph->ComputeUseLists();
       }
 
       if (FLAG_trace_inlining && FLAG_print_flow_graph) {
         OS::Print("Callee graph for inlining %s\n",
                   function.ToFullyQualifiedCString());
         FlowGraphPrinter printer(*callee_graph);
         printer.PrintBlocks();
       }
 
-      // If result is more than size threshold then abort.
+      // Collect information about the call site and caller graph.
       // TODO(zerny): Do this after CP and dead code elimination.
-      intptr_t size = callee_graph->InstructionCount();
-      if (size > FLAG_inlining_size_threshold) {
-        function.set_is_inlinable(false);
+      intptr_t constants_count = 0;
+      for (intptr_t i = 0; i < param_stubs.length(); ++i) {
+        if (param_stubs[i]->IsConstant()) ++constants_count;
+      }
+      GraphInfoCollector info;
+      info.Collect(*callee_graph);
+      const intptr_t size = info.instruction_count();
+      // Use heuristics do decide if this call should be inlined.
+      if (!ShouldWeInline(loop_depth,
+                          size,
+                          info.call_site_count(),
+                          constants_count)) {
+        // If size is larger than all thresholds, don't consider it again.
+        if ((size > FLAG_inlining_size_threshold) &&
+            (size > FLAG_inlining_in_loop_size_threshold) &&
+            (size > FLAG_inlining_callee_call_sites_threshold) &&
+            (size > FLAG_inlining_constant_arguments_size_threshold)) {
+          function.set_is_inlinable(false);
+        }
         isolate->set_long_jump_base(base);
         isolate->set_deopt_id(prev_deopt_id);
         isolate->set_ic_data_array(prev_ic_data.raw());
-        TRACE_INLINING(OS::Print("     Bailout: graph size %"Pd"\n", size));
+        TRACE_INLINING(OS::Print("     Bailout: heuristics with "
+                                 "loop depth: %"Pd", "
+                                 "code size:  %"Pd", "
+                                 "call sites: %"Pd", "
+                                 "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);
       }
 
       {
         TimerScope timer(FLAG_compiler_stats,
@@ skipping 282 matching lines @@
         OS::Print("After Inlining of %s\n", flow_graph_->
                   parsed_function().function().ToFullyQualifiedCString());
         FlowGraphPrinter printer(*flow_graph_);
         printer.PrintBlocks();
       }
     }
   }
 }
 
 }  // namespace dart