Recursive inlining.

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/assert.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"
 
 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, 250,
-    "Inline only functions with up to threshold instructions");
+    "Inline only functions with up to threshold instructions (default 250)");
+DEFINE_FLAG(int, inlining_depth_threshold, 0,
+    "Inline recursively up to threshold depth (default 0, ie, disabled)");
 DEFINE_FLAG(bool, inline_control_flow, true,
     "Inline functions with control flow.");
 DECLARE_FLAG(bool, print_flow_graph);
 DECLARE_FLAG(int, deoptimization_counter_threshold);
 
 #define TRACE_INLINING(statement)                                              \
   do {                                                                         \
     if (FLAG_trace_inlining) statement;                                        \
   } while (false)
 
 
 // Test if a call is recursive by looking in the deoptimization environment.
 static bool IsCallRecursive(const Function& function, Definition* call) {
   Environment* env = call->env();
   while (env != NULL) {
     if (function.raw() == env->function().raw()) return true;
     env = env->outer();
   }
   return false;
 }
 
 
-class CallSiteInliner : public FlowGraphVisitor {
+// A collection of call sites.
+class CallSites : public FlowGraphVisitor {
  public:
-  explicit CallSiteInliner(FlowGraph* flow_graph)
-      : FlowGraphVisitor(flow_graph->postorder()),
-        caller_graph_(flow_graph),
-        next_ssa_temp_index_(flow_graph->max_virtual_register_number()),
-        inlined_(false),
-        initial_size_(flow_graph->InstructionCount()),
-        inlined_size_(0),
+  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() {
+    return &static_calls_;
+  }
+
+  GrowableArray<ClosureCallInstr*>* closure_calls() {
+    return &closure_calls_;
+  }
+
+  GrowableArray<PolymorphicInstanceCallInstr*>* instance_calls() {
+    return &instance_calls_;
+  }
+
+  bool HasCalls() const {
+    return !(static_calls_.is_empty() &&
+             closure_calls_.is_empty() &&
+             instance_calls_.is_empty());
+  }
+
+  void Clear() {
+    static_calls_.Clear();
+    closure_calls_.Clear();
+    instance_calls_.Clear();
+  }
+
+  void FindCallSites(FlowGraph* graph) {
+    BlockIterator block_it = graph->postorder_iterator();
+    for (; !block_it.Done(); block_it.Advance()) {
+      ForwardInstructionIterator it(block_it.Current());
+      for (; !it.Done(); it.Advance()) {
+        it.Current()->Accept(this);
+      }
+    }
+  }
+
   void VisitClosureCall(ClosureCallInstr* call) {
     closure_calls_.Add(call);
   }
 
   void VisitPolymorphicInstanceCall(PolymorphicInstanceCallInstr* call) {
     instance_calls_.Add(call);
   }
 
   void VisitStaticCall(StaticCallInstr* call) {
     if (call->function().is_inlinable()) static_calls_.Add(call);
   }

[srdjan, 2012/10/04 17:06:26]

Why not adding VisitInstanceCall as well? Then we could use this to check if the
method is leaf method. Maybe have then two methods: HasInlinableCalls and
HasCalls

[zerny-google, 2012/10/08 11:44:28]

The collection of call sites happens after we have applied IC data so, if I
understand correctly, all the remaining (non polymorphic) instance calls are
those with no receiver type information and therefore cannot be inlined. The
identification of leaf methods seems more appropriate earlier in the pipeline
since that information would be useful for inlining too if it were already
computed.

[srdjan, 2012/10/08 15:31:03]

Please add something similar to the comment of the class. IMO, 'CallSite' class
name sounds too generic, what it does is not compute call sites but inlineable
call sites.

 
-  void FindCallSites() {
-    VisitBlocks();
-  }
+ private:
+  GrowableArray<StaticCallInstr*> static_calls_;
+  GrowableArray<ClosureCallInstr*> closure_calls_;
+  GrowableArray<PolymorphicInstanceCallInstr*> instance_calls_;
+
+  DISALLOW_COPY_AND_ASSIGN(CallSites);
+};
+
+
+class CallSiteInliner : public ValueObject {
+ public:
+  explicit CallSiteInliner(FlowGraph* flow_graph)
+      : 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) { }
 
   void InlineCalls() {
-    InlineStaticCalls();
-    InlineClosureCalls();
-    InlineInstanceCalls();
+    // 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_);
+    while (collected_call_sites_->HasCalls()) {
+      TRACE_INLINING(OS::Print("  Depth %"Pd" ----------\n",
+                               inlining_depth_ - 1));
+      // 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_;
+    }

[srdjan, 2012/10/04 17:06:26]

Reset collected_call_sites_ and inlining_call_sites_ to NULL.

[zerny-google, 2012/10/08 11:44:28]

Done.

   }
 
   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,
                    GrowableArray<Value*>* arguments,
                    Definition* call) {
-    TRACE_INLINING(OS::Print("  => %s\n", function.ToCString()));
+    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.is_inlinable()) {
       TRACE_INLINING(OS::Print("     Bailout: not inlinable\n"));
       return false;
     }
 
     // Abort if the callee has optional parameters.
     if (function.HasOptionalParameters()) {
       TRACE_INLINING(OS::Print("     Bailout: optional parameters\n"));
@@ skipping 49 matching lines @@
         isolate->set_ic_data_array(unoptimized_code.ExtractTypeFeedbackArray());
       }
 
       // Build the callee graph.
       FlowGraphBuilder builder(parsed_function);
       builder.SetInitialBlockId(caller_graph_->max_block_id());
       FlowGraph* callee_graph =
           builder.BuildGraph(FlowGraphBuilder::kValueContext);
 
       // Abort if the callee graph contains control flow.
-      if ((callee_graph->preorder().length() != 2) &&
-          !FLAG_inline_control_flow) {
+      if (!FLAG_inline_control_flow &&
+          (callee_graph->preorder().length() != 2)) {
         function.set_is_inlinable(false);
         isolate->set_long_jump_base(base);
         isolate->set_ic_data_array(prev_ic_data.raw());
         TRACE_INLINING(OS::Print("     Bailout: control flow\n"));
         return false;
       }
 
       // Compute SSA on the callee graph, catching bailouts.
       callee_graph->ComputeSSA(next_ssa_temp_index_);
       callee_graph->ComputeUseLists();
@@ skipping 15 matching lines @@
       intptr_t size = callee_graph->InstructionCount();
       if (size > FLAG_inlining_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));
         return false;
       }
 
-      // TODO(zerny): If effort is less than threshold then inline recursively.
+      // If depth is less or equal to threshold recursively add call sites.
+      if (inlining_depth_ <= FLAG_inlining_depth_threshold) {

[srdjan, 2012/10/04 17:06:26]

The inlining depth threshold is not keeping inlining depth from going above it.
Maybe rename the flag to recursive_inlining_depth_threshold.

[zerny-google, 2012/10/08 11:44:28]

Implicitly it is. The flag is an upper bound on the iterations performed in
InlineCalls. The loop termination is separated from the loop in order to avoid
adding call sites to the array which we might not consider inlining.

[srdjan, 2012/10/08 15:31:03]

I am looking at it from the point of user running Dart VM. When I run Dart VM
with --inlining_depth_threshold=1, I expect that one level of inlining occurs,
i.e., a value of 0 should disable inlining, then. Maybe rename it some geekier
name, like inlining_iteration_upper_bound?

+        collected_call_sites_->FindCallSites(callee_graph);
+      }
 
       // Plug result in the caller graph.
       caller_graph_->InlineCall(call, callee_graph);
       next_ssa_temp_index_ = caller_graph_->max_virtual_register_number();
 
       // Remove push arguments of the call.
       for (intptr_t i = 0; i < call->ArgumentCount(); ++i) {
         PushArgumentInstr* push = call->ArgumentAt(i);
         push->ReplaceUsesWith(push->value()->definition());
         push->RemoveFromGraph();
@@ skipping 33 matching lines @@
       isolate->object_store()->clear_sticky_error();
       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: %s\n", error.ToErrorCString()));
       return false;
     }
   }
 
   void InlineStaticCalls() {
-    TRACE_INLINING(OS::Print("  Static Calls (%d)\n",
-                             static_calls_.length()));
-    for (intptr_t i = 0; i < static_calls_.length(); ++i) {
-      StaticCallInstr* call = static_calls_[i];
+    const GrowableArray<StaticCallInstr*>& 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(), &arguments, call);
     }
   }
 
   void InlineClosureCalls() {
-    TRACE_INLINING(OS::Print("  Closure Calls (%d)\n",
-                             closure_calls_.length()));
-    for (intptr_t i = 0; i < closure_calls_.length(); ++i) {
-      ClosureCallInstr* call = closure_calls_[i];
+    const GrowableArray<ClosureCallInstr*>& 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() - 1);
       for (int i = 1; i < call->ArgumentCount(); ++i) {
         arguments.Add(call->ArgumentAt(i)->value());
       }
       TryInlining(closure->function(), &arguments, call);
     }
   }
 
   void InlineInstanceCalls() {
+    const GrowableArray<PolymorphicInstanceCallInstr*>& calls =
+        *inlining_call_sites_->instance_calls();
     TRACE_INLINING(OS::Print("  Polymorphic Instance Calls (%d)\n",
-                             instance_calls_.length()));
-    for (intptr_t i = 0; i < instance_calls_.length(); ++i) {
-      PolymorphicInstanceCallInstr* instr = instance_calls_[i];
+                             calls.length()));
+    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("     Bailout: %"Pd" checks target '%s'\n",
                                  ic_data.NumberOfChecks(),
                                  target.ToCString()));
         continue;
       }
       GrowableArray<Value*> arguments(instr->ArgumentCount());
       for (int i = 0; i < instr->ArgumentCount(); ++i) {
         arguments.Add(instr->ArgumentAt(i)->value());
       }
       TryInlining(target, &arguments, instr);
     }
   }
 
   FlowGraph* caller_graph_;
   intptr_t next_ssa_temp_index_;
   bool inlined_;
   intptr_t initial_size_;
   intptr_t inlined_size_;
+  intptr_t inlining_depth_;
+  CallSites* collected_call_sites_;
+  CallSites* inlining_call_sites_;
 
-  GrowableArray<StaticCallInstr*> static_calls_;
-  GrowableArray<ClosureCallInstr*> closure_calls_;
-  GrowableArray<PolymorphicInstanceCallInstr*> instance_calls_;
+  DISALLOW_COPY_AND_ASSIGN(CallSiteInliner);
 };
 
 
 void FlowGraphInliner::Inline() {
   if ((FLAG_inlining_filter != NULL) &&
       (strstr(flow_graph_->
               parsed_function().function().ToFullyQualifiedCString(),
               FLAG_inlining_filter) == NULL)) {
     return;
   }
 
   TRACE_INLINING(OS::Print(
       "Inlining calls in %s\n",
       flow_graph_->parsed_function().function().ToCString()));
 
   if (FLAG_trace_inlining && FLAG_print_flow_graph) {
     OS::Print("Before Inlining of %s\n", flow_graph_->
               parsed_function().function().ToFullyQualifiedCString());
     FlowGraphPrinter printer(*flow_graph_);
     printer.PrintBlocks();
   }
 
   CallSiteInliner inliner(flow_graph_);
-  inliner.FindCallSites();
   inliner.InlineCalls();
 
   if (inliner.inlined()) {
     if (FLAG_trace_inlining) {
       OS::Print("Inlining growth factor: %f\n", inliner.GrowthFactor());
       if (FLAG_print_flow_graph) {
         OS::Print("After Inlining of %s\n", flow_graph_->
                   parsed_function().function().ToFullyQualifiedCString());
         FlowGraphPrinter printer(*flow_graph_);
         printer.PrintBlocks();
       }
     }
   }
 }
 
 }  // namespace dart