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");
+DEFINE_FLAG(int, inlining_size_threshold, 20,
+  "Always inline functions that have threshold or fewer instructions");
+DEFINE_FLAG(int, inlining_in_loop_size_threshold, 60,
+  "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, 40,
+  "Inline function calls with sufficient constant arguments "
+  "and up to the increased threshold on instructions");

[srdjan, 2012/10/25 20:38:50]

Indent  4 characters (continuation of a 'statement').

[zerny-google, 2012/10/29 16:44:25]

Done.

+
 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.

[srdjan, 2012/10/25 20:38:50]

about inlineable callee graphs

[zerny-google, 2012/10/29 16:44:25]

Done.

+class GraphInfoCollector : public ValueObject {
+ public:
+  explicit GraphInfoCollector()

[srdjan, 2012/10/25 20:38:50]

remove explicit

[zerny-google, 2012/10/29 16:44:25]

Done.

+      : 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,

[srdjan, 2012/10/25 20:38:50]

Size of what? Please name better

[zerny-google, 2012/10/29 16:44:25]

s/size/instr_count

+                      intptr_t call_sites,

[srdjan, 2012/10/25 20:38:50]

num_call_sites?

[zerny-google, 2012/10/29 16:44:25]

s/call_sites/call_site_count

+                      intptr_t constant_args) {
+    if (size <= FLAG_inlining_size_threshold) {
+      return true;
+    }
+    if (call_sites <= FLAG_inlining_callee_call_sites_threshold) {
+      return true;
+    }
+    if ((loop_depth > 0) && (size <= FLAG_inlining_in_loop_size_threshold)) {
+      return true;
+    }
+    if ((constant_args >= FLAG_inlining_constant_arguments_count) &&
+        (size <= FLAG_inlining_constant_arguments_size_threshold)) {
+      return true;
+    }
+    return false;
+  }
+
   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 61 matching lines @@
     }
 
     // Abort if we are running legacy support for optional parameters.
     if (!FLAG_reject_named_argument_as_positional &&
         function.HasOptionalPositionalParameters() &&
         (!argument_names.IsNull() && (argument_names.Length() > 0))) {
       function.set_is_inlinable(false);
       TRACE_INLINING(OS::Print(
           "     Bailout: named optional positional parameter\n"));
       return false;
     }

[srdjan, 2012/10/25 20:38:50]

Could you use a modified inlining_size_threshold value to copmpare it against
the code size of the function (class Code) instead of bailing out after the
function has been parsed and the graph has been built?

[Kevin Millikin (Google), 2012/10/26 12:07:22]

We could definitely do that.  In fact, we could cache things like number of
instructions, number of calls, etc. in the function --- as long as we can
compute them from the unoptimized compilation.

[zerny-google, 2012/10/29 16:44:25]

The is_inlinable bit approximated this (line 479), but with this CL I changed
the behavior so the bit is set to low only if the size is above all the
thresholds. This way, we can use different heuristics at different call sites.
Of course, this means a function between size_threshold and
in_loop_size_threshold will be parsed and built repeatedly even if it will only
be inlined when in a loop context.

 
     Isolate* isolate = Isolate::Current();
     // Save and clear IC data.
     const Array& prev_ic_data = Array::Handle(isolate->ic_data_array());
     isolate->set_ic_data_array(Array::null());
     // Save and clear deopt id.
     const intptr_t prev_deopt_id = isolate->deopt_id();
     isolate->set_deopt_id(0);
     // Install bailout jump.
     LongJump* base = isolate->long_jump_base();
@@ skipping 11 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