Print inlined tree using --print_inline_tree.

runtime/vm/flow_graph_inliner.cc

 // Copyright (c) 2013, 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/block_scheduler.h"
 #include "vm/compiler.h"
 #include "vm/flags.h"
 #include "vm/flow_graph.h"
@@ skipping 29 matching lines @@
     "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, 10,
     "Inline only hotter calls, in percents (0 .. 100); "
     "default 10%: calls above-equal 10% of max-count are inlined.");
 DEFINE_FLAG(bool, inline_recursive, true,
     "Inline recursive calls.");
+DEFINE_FLAG(bool, print_inline_tree, false, "Print inlining tree");
 
 DECLARE_FLAG(bool, print_flow_graph);
 DECLARE_FLAG(bool, print_flow_graph_optimized);
 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;                                        \
@@ skipping 94 matching lines @@
 
 
 // A collection of call sites to consider for inlining.
 class CallSites : public ValueObject {
  public:
   explicit CallSites(FlowGraph* flow_graph)
       : static_calls_(),
         closure_calls_(),
         instance_calls_() { }
 
-  const GrowableArray<ClosureCallInstr*>& closure_calls() const {
-    return closure_calls_;
-  }
-
   struct InstanceCallInfo {
     PolymorphicInstanceCallInstr* call;
     double ratio;
-    explicit InstanceCallInfo(PolymorphicInstanceCallInstr* call_arg)
-        : call(call_arg), ratio(0.0) {}
+    const Function* caller;
+    InstanceCallInfo(PolymorphicInstanceCallInstr* call_arg,
+                     FlowGraph* flow_graph)
+        : call(call_arg),
+          ratio(0.0),
+          caller(&flow_graph->parsed_function().function()) {}
   };
 
   struct StaticCallInfo {
     StaticCallInstr* call;
     double ratio;
-    explicit StaticCallInfo(StaticCallInstr* value)
-        : call(value), ratio(0.0) {}
+    const Function* caller;
+    StaticCallInfo(StaticCallInstr* value, FlowGraph* flow_graph)
+        : call(value),
+          ratio(0.0),
+          caller(&flow_graph->parsed_function().function()) {}
+  };
+
+  struct ClosureCallInfo {
+    ClosureCallInstr* call;
+    const Function* caller;
+    ClosureCallInfo(ClosureCallInstr* value, FlowGraph* flow_graph)
+        : call(value),
+          caller(&flow_graph->parsed_function().function()) {}
   };
 
   const GrowableArray<InstanceCallInfo>& instance_calls() const {
     return instance_calls_;
   }
 
   const GrowableArray<StaticCallInfo>& static_calls() const {
     return static_calls_;
   }
 
+  const GrowableArray<ClosureCallInfo>& closure_calls() const {
+    return closure_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();
@@ skipping 54 matching lines @@
          !block_it.Done();
          block_it.Advance()) {
       for (ForwardInstructionIterator it(block_it.Current());
            !it.Done();
            it.Advance()) {
         Instruction* current = it.Current();
         if (only_recognized_methods) {
           PolymorphicInstanceCallInstr* instance_call =
               current->AsPolymorphicInstanceCall();
           if ((instance_call != NULL) && instance_call->HasRecognizedTarget()) {
-            instance_calls_.Add(InstanceCallInfo(instance_call));
+            instance_calls_.Add(InstanceCallInfo(instance_call, graph));
           }
           continue;
         }
         // Collect all call sites (!only_recognized_methods).
         ClosureCallInstr* closure_call = current->AsClosureCall();
         if (closure_call != NULL) {
-          closure_calls_.Add(closure_call);
+          closure_calls_.Add(ClosureCallInfo(closure_call, graph));
           continue;
         }
         StaticCallInstr* static_call = current->AsStaticCall();
         if (static_call != NULL) {
-          static_calls_.Add(StaticCallInfo(static_call));
+          static_calls_.Add(StaticCallInfo(static_call, graph));
           continue;
         }
         PolymorphicInstanceCallInstr* instance_call =
             current->AsPolymorphicInstanceCall();
         if (instance_call != NULL) {
-          instance_calls_.Add(InstanceCallInfo(instance_call));
+          instance_calls_.Add(InstanceCallInfo(instance_call, graph));
           continue;
         }
       }
     }
     ComputeCallSiteRatio(static_call_start_ix, instance_call_start_ix);
   }
 
  private:
   GrowableArray<StaticCallInfo> static_calls_;
-  GrowableArray<ClosureCallInstr*> closure_calls_;
+  GrowableArray<ClosureCallInfo> closure_calls_;
   GrowableArray<InstanceCallInfo> instance_calls_;
 
   DISALLOW_COPY_AND_ASSIGN(CallSites);
 };
 
 
 struct InlinedCallData {
-  InlinedCallData(Definition* call, GrowableArray<Value*>* arguments)
+  InlinedCallData(Definition* call,
+                  GrowableArray<Value*>* arguments,
+                  const Function& caller)
       : call(call),
         arguments(arguments),
         callee_graph(NULL),
         parameter_stubs(NULL),
-        exit_collector(NULL) { }
+        exit_collector(NULL),
+        caller_(caller) { }
 
   Definition* call;
   GrowableArray<Value*>* arguments;
   FlowGraph* callee_graph;
   ZoneGrowableArray<Definition*>* parameter_stubs;
   InlineExitCollector* exit_collector;
+  const Function& caller_;
+};
+
+
+// Structure for collecting inline data needed to print inlining tree.
+struct InlinedInfo {
+  const Function* caller;
+  const Function* inlined;
+  intptr_t inlined_depth;
+  const Definition* call_instr;
+  InlinedInfo(const Function* caller_function,
+              const Function* inlined_function,
+              const intptr_t depth,
+              const Definition* call)
+      : caller(caller_function),
+        inlined(inlined_function),
+        inlined_depth(depth),
+        call_instr(call) {}
 };
 
 
 class CallSiteInliner;
 
 class PolymorphicInliner : public ValueObject {
  public:
   PolymorphicInliner(CallSiteInliner* owner,
-                     PolymorphicInstanceCallInstr* call);
+                     PolymorphicInstanceCallInstr* call,
+                     const Function& caller_function);
 
   void Inline();
 
  private:
   bool CheckInlinedDuplicate(const Function& target);
   bool CheckNonInlinedDuplicate(const Function& target);
 
-  bool TryInlining(intptr_t receiver_cid, const Function& target);
+  bool TryInliningPoly(intptr_t receiver_cid, const Function& target);
   bool TryInlineRecognizedMethod(intptr_t receiver_cid, const Function& target);
 
   TargetEntryInstr* BuildDecisionGraph();
 
   CallSiteInliner* const owner_;
   PolymorphicInstanceCallInstr* const call_;
   const intptr_t num_variants_;
   GrowableArray<CidTarget> variants_;
 
   GrowableArray<CidTarget> inlined_variants_;
   GrowableArray<CidTarget> non_inlined_variants_;
   GrowableArray<BlockEntryInstr*> inlined_entries_;
   InlineExitCollector* exit_collector_;
+
+  const Function& caller_function_;
 };
 
 
 class CallSiteInliner : public ValueObject {
  public:
   explicit CallSiteInliner(FlowGraph* flow_graph)
       : caller_graph_(flow_graph),
         inlined_(false),
         initial_size_(flow_graph->InstructionCount()),
         inlined_size_(0),
         inlining_depth_(1),
         collected_call_sites_(NULL),
         inlining_call_sites_(NULL),
-        function_cache_() { }
+        function_cache_(),
+        inlined_info_() { }
 
   FlowGraph* caller_graph() const { return caller_graph_; }
 
   // Inlining heuristics based on Cooper et al. 2008.
   bool ShouldWeInline(const Function& callee,
                       intptr_t instr_count,
                       intptr_t call_site_count,
                       intptr_t const_arg_count) {
     if (inlined_size_ > FLAG_inlining_caller_size_threshold) {
       // Prevent methods becoming humongous and thus slow to compile.
@@ skipping 274 matching lines @@
       // list of guarded fields.
       for (intptr_t i = 0; i < callee_graph->guarded_fields()->length(); ++i) {
         FlowGraph::AddToGuardedFields(caller_graph_->guarded_fields(),
                                       (*callee_graph->guarded_fields())[i]);
       }
 
       // We allocate a ZoneHandle for the unoptimized code so that it cannot be
       // disconnected from its function during the rest of compilation.
       Code::ZoneHandle(unoptimized_code.raw());
       TRACE_INLINING(OS::Print("     Success\n"));
+      if (FLAG_print_inline_tree) {
+        inlined_info_.Add(
+            InlinedInfo(&call_data->caller_, &function, inlining_depth_, call));
+      }
       return true;
     } else {
       Error& error = Error::Handle();
       error = isolate->object_store()->sticky_error();
       isolate->object_store()->clear_sticky_error();
       isolate->set_deopt_id(prev_deopt_id);
       TRACE_INLINING(OS::Print("     Bailout: %s\n", error.ToErrorCString()));
       return false;
     }
   }
 
+  void PrintInlinedInfo(const Function& top) {
+    OS::Print("Inlining into: %s\n", top.ToFullyQualifiedCString());
+    PrintInlinedInfoFor(top, 1);
+  }
+
  private:
   friend class PolymorphicInliner;
 
+  void PrintInlinedInfoFor(const Function& caller, intptr_t depth) {
+    for (intptr_t i = 0; i < inlined_info_.length(); i++) {
+      const InlinedInfo& info = inlined_info_[i];
+      if ((info.inlined_depth == depth) &&
+          (info.caller->raw() == caller.raw())) {
+        for (int t = 0; t < depth; t++) {
+          OS::Print("  ");
+        }
+        OS::Print("%" Pd " %s\n",
+            info.call_instr->GetDeoptId(),
+            info.inlined->ToQualifiedCString());
+        PrintInlinedInfoFor(*info.inlined, depth + 1);
+      }
+    }
+  }
+
   void InlineCall(InlinedCallData* call_data) {
     TimerScope timer(FLAG_compiler_stats,
                      &CompilerStats::graphinliner_subst_timer,
                      Isolate::Current());
 
     // For closure calls: Store context value.
     FlowGraph* callee_graph = call_data->callee_graph;
     TargetEntryInstr* callee_entry =
         callee_graph->graph_entry()->normal_entry();
     ClosureCallInstr* closure_call = call_data->call->AsClosureCall();
@@ skipping 102 matching lines @@
             "  => %s (deopt count %d)\n     Bailout: cold %f\n",
             target.ToCString(),
             target.deoptimization_counter(),
             call_info[call_idx].ratio));
         continue;
       }
       GrowableArray<Value*> arguments(call->ArgumentCount());
       for (int i = 0; i < call->ArgumentCount(); ++i) {
         arguments.Add(call->PushArgumentAt(i)->value());
       }
-      InlinedCallData call_data(call, &arguments);
+      InlinedCallData call_data(call, &arguments, *call_info[call_idx].caller);
       if (TryInlining(call->function(), call->argument_names(), &call_data)) {
         InlineCall(&call_data);
       }
     }
   }
 
   void InlineClosureCalls() {
-    const GrowableArray<ClosureCallInstr*>& calls =
+    const GrowableArray<CallSites::ClosureCallInfo>& call_info =
         inlining_call_sites_->closure_calls();
-    TRACE_INLINING(OS::Print("  Closure Calls (%" Pd ")\n", calls.length()));
-    for (intptr_t i = 0; i < calls.length(); ++i) {
-      ClosureCallInstr* call = calls[i];
+    TRACE_INLINING(OS::Print("  Closure Calls (%" Pd ")\n",
+        call_info.length()));
+    for (intptr_t call_idx = 0; call_idx < call_info.length(); ++call_idx) {
+      ClosureCallInstr* call = call_info[call_idx].call;
       // Find the closure of the callee.
       ASSERT(call->ArgumentCount() > 0);
       Function& target = Function::ZoneHandle();
       AllocateObjectInstr* alloc =
           call->ArgumentAt(0)->AsAllocateObject();
       if ((alloc != NULL) && !alloc->closure_function().IsNull()) {
         target ^= alloc->closure_function().raw();
         ASSERT(target.signature_class() == alloc->cls().raw());
       }
       if (target.IsNull()) {
         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->PushArgumentAt(i)->value());
       }
-      InlinedCallData call_data(call, &arguments);
+      InlinedCallData call_data(call, &arguments, *call_info[call_idx].caller);
       if (TryInlining(target,
                       call->argument_names(),
                       &call_data)) {
         InlineCall(&call_data);
       }
     }
   }
 
   void InlineInstanceCalls() {
     const GrowableArray<CallSites::InstanceCallInfo>& call_info =
         inlining_call_sites_->instance_calls();
     TRACE_INLINING(OS::Print("  Polymorphic Instance Calls (%" Pd ")\n",
                              call_info.length()));
     for (intptr_t call_idx = 0; call_idx < call_info.length(); ++call_idx) {
       PolymorphicInstanceCallInstr* call = call_info[call_idx].call;
       if (call->with_checks()) {
-        PolymorphicInliner inliner(this, call);
+        const Function& cl = *call_info[call_idx].caller;
+        PolymorphicInliner inliner(this, call, cl);
         inliner.Inline();
         continue;
       }
 
       const ICData& ic_data = call->ic_data();
       const Function& target = Function::ZoneHandle(ic_data.GetTargetAt(0));
       if (!FlowGraphInliner::AlwaysInline(target) &&
           (call_info[call_idx].ratio * 100) < FLAG_inlining_hotness) {
         TRACE_INLINING(OS::Print(
             "  => %s (deopt count %d)\n     Bailout: cold %f\n",
             target.ToCString(),
             target.deoptimization_counter(),
             call_info[call_idx].ratio));
         continue;
       }
       GrowableArray<Value*> arguments(call->ArgumentCount());
       for (int arg_i = 0; arg_i < call->ArgumentCount(); ++arg_i) {
         arguments.Add(call->PushArgumentAt(arg_i)->value());
       }
-      InlinedCallData call_data(call, &arguments);
+      InlinedCallData call_data(call, &arguments, *call_info[call_idx].caller);
       if (TryInlining(target,
                       call->instance_call()->argument_names(),
                       &call_data)) {
         InlineCall(&call_data);
       }
     }
   }
 
   bool AdjustForOptionalParameters(const ParsedFunction& parsed_function,
                                    const Array& argument_names,
@@ skipping 80 matching lines @@
       if (arg != NULL) {
         param_stubs->Add(CreateParameterStub(i, arg, callee_graph));
       } else {
         param_stubs->Add(
             GetDefaultValue(i - fixed_param_count, parsed_function));
       }
     }
     return argument_names_count == match_count;
   }
 
-
   FlowGraph* caller_graph_;
   bool inlined_;
   intptr_t initial_size_;
   intptr_t inlined_size_;
   intptr_t inlining_depth_;
   CallSites* collected_call_sites_;
   CallSites* inlining_call_sites_;
   GrowableArray<ParsedFunction*> function_cache_;
+  GrowableArray<InlinedInfo> inlined_info_;
 
   DISALLOW_COPY_AND_ASSIGN(CallSiteInliner);
 };
 
 
 PolymorphicInliner::PolymorphicInliner(CallSiteInliner* owner,
-                                       PolymorphicInstanceCallInstr* call)
+                                       PolymorphicInstanceCallInstr* call,
+                                       const Function& caller_function)
     : owner_(owner),
       call_(call),
       num_variants_(call->ic_data().NumberOfChecks()),
       variants_(num_variants_),
       inlined_variants_(num_variants_),
       non_inlined_variants_(num_variants_),
       inlined_entries_(num_variants_),
-      exit_collector_(new InlineExitCollector(owner->caller_graph(), call)) {
+      exit_collector_(new InlineExitCollector(owner->caller_graph(), call)),
+      caller_function_(caller_function) {
 }
 
 
 // Inlined bodies are shared if two different class ids have the same
 // inlined target.  This sharing is represented by using three different
 // types of entries in the inlined_entries_ array:
 //
 //   * GraphEntry: the inlined body is not shared.
 //
 //   * TargetEntry: the inlined body is shared and this is the first variant.
@@ skipping 55 matching lines @@
   for (intptr_t i = 0; i < non_inlined_variants_.length(); ++i) {
     if (target.raw() == non_inlined_variants_[i].target->raw()) {
       return true;
     }
   }
 
   return false;
 }
 
 
-bool PolymorphicInliner::TryInlining(intptr_t receiver_cid,
-                                     const Function& target) {
+bool PolymorphicInliner::TryInliningPoly(intptr_t receiver_cid,
+                                        const Function& target) {
   if (!target.IsInlineable()) {
     if (TryInlineRecognizedMethod(receiver_cid, target)) {
       owner_->inlined_ = true;
       return true;
     }
     return false;
   }
 
   GrowableArray<Value*> arguments(call_->ArgumentCount());
   for (int i = 0; i < call_->ArgumentCount(); ++i) {
     arguments.Add(call_->PushArgumentAt(i)->value());
   }
-  InlinedCallData call_data(call_, &arguments);
+  InlinedCallData call_data(call_, &arguments, caller_function_);
   if (!owner_->TryInlining(target,
                            call_->instance_call()->argument_names(),
                            &call_data)) {
     return false;
   }
 
   FlowGraph* callee_graph = call_data.callee_graph;
   call_data.exit_collector->PrepareGraphs(callee_graph);
   inlined_entries_.Add(callee_graph->graph_entry());
   exit_collector_->Union(call_data.exit_collector);
@@ skipping 319 matching lines @@
 
     // Also check if this is the same target as an earlier non-inlined
     // variant.  If so and since inlining decisions are costly, do not try
     // to inline this variant.
     if (CheckNonInlinedDuplicate(target)) {
       non_inlined_variants_.Add(variants_[var_idx]);
       continue;
     }
 
     // Make an inlining decision.
-    if (TryInlining(receiver_cid, target)) {
+    if (TryInliningPoly(receiver_cid, target)) {
       inlined_variants_.Add(variants_[var_idx]);
     } else {
       non_inlined_variants_.Add(variants_[var_idx]);
     }
   }
 
   // If there are no inlined variants, leave the call in place.
   if (inlined_variants_.is_empty()) return;
 
   // Now build a decision tree (a DAG because of shared inline variants) and
@@ skipping 28 matching lines @@
   }
   return MethodRecognizer::AlwaysInline(function);
 }
 
 
 void FlowGraphInliner::Inline() {
   // Collect graph info and store it on the function.
   // We might later use it for an early bailout from the inlining.
   CollectGraphInfo(flow_graph_);
 
+  const Function& top = flow_graph_->parsed_function().function();
   if ((FLAG_inlining_filter != NULL) &&
-      (strstr(flow_graph_->
-              parsed_function().function().ToFullyQualifiedCString(),
-              FLAG_inlining_filter) == NULL)) {
+      (strstr(top.ToFullyQualifiedCString(), FLAG_inlining_filter) == NULL)) {
     return;
   }
 
-  TRACE_INLINING(OS::Print(
-      "Inlining calls in %s\n",
-      flow_graph_->parsed_function().function().ToCString()));
+  TRACE_INLINING(OS::Print("Inlining calls in %s\n", top.ToCString()));
 
   if (FLAG_trace_inlining &&
       (FLAG_print_flow_graph || FLAG_print_flow_graph_optimized)) {
     OS::Print("Before Inlining of %s\n", flow_graph_->
               parsed_function().function().ToFullyQualifiedCString());
     FlowGraphPrinter printer(*flow_graph_);
     printer.PrintBlocks();
   }
 
   CallSiteInliner inliner(flow_graph_);
   inliner.InlineCalls();
+  if (FLAG_print_inline_tree) {
+    inliner.PrintInlinedInfo(top);
+  }
 
   if (inliner.inlined()) {
     flow_graph_->DiscoverBlocks();
     if (FLAG_trace_inlining) {
       OS::Print("Inlining growth factor: %f\n", inliner.GrowthFactor());
       if (FLAG_print_flow_graph || FLAG_print_flow_graph_optimized) {
         OS::Print("After Inlining of %s\n", flow_graph_->
                   parsed_function().function().ToFullyQualifiedCString());
         FlowGraphPrinter printer(*flow_graph_);
         printer.PrintBlocks();
       }
     }
   }
 }
 
 }  // namespace dart