[VM-Compiler] Don't inline if we don't have inlining budget enough to fully inline.

runtime/vm/compiler/backend/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.
 
 #if !defined(DART_PRECOMPILED_RUNTIME)
 
 #include "vm/compiler/backend/inliner.h"
 
 #include "vm/compiler/aot/aot_call_specializer.h"
 #include "vm/compiler/aot/precompiler.h"
@@ skipping 438 matching lines @@
 
 class CallSiteInliner;
 
 class PolymorphicInliner : public ValueObject {
  public:
   PolymorphicInliner(CallSiteInliner* owner,
                      PolymorphicInstanceCallInstr* call,
                      const Function& caller_function,
                      intptr_t caller_inlining_id);
 
-  void Inline();
+  bool Inline();
 
  private:
   bool CheckInlinedDuplicate(const Function& target);
   bool CheckNonInlinedDuplicate(const Function& target);
 
   bool TryInliningPoly(const TargetInfo& target);
   bool TryInlineRecognizedMethod(intptr_t receiver_cid, const Function& target);
 
   TargetEntryInstr* BuildDecisionGraph();
 
@@ skipping 143 matching lines @@
         inlined_info_() {}
 
   FlowGraph* caller_graph() const { return caller_graph_; }
 
   Thread* thread() const { return caller_graph_->thread(); }
   Isolate* isolate() const { return caller_graph_->isolate(); }
   Zone* zone() const { return caller_graph_->zone(); }
 
   bool trace_inlining() const { return inliner_->trace_inlining(); }
 
+  int inlining_depth() { return inlining_depth_; }
+
+  struct InliningDecision {
+    InliningDecision(bool b, const char* r) : value(b), reason(r) {}
+    bool value;
+    const char* reason;
+    static InliningDecision Yes(const char* reason) {
+      return InliningDecision(true, reason);
+    }
+    static InliningDecision No(const char* reason) {
+      return InliningDecision(false, reason);
+    }
+  };
+
   // 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) {
+  InliningDecision ShouldWeInline(const Function& callee,
+                                  intptr_t instr_count,
+                                  intptr_t call_site_count,
+                                  intptr_t const_arg_count) {
     if (inliner_->AlwaysInline(callee)) {
-      return true;
+      return InliningDecision::Yes("AlwaysInline");
     }
     if (inlined_size_ > FLAG_inlining_caller_size_threshold) {
       // Prevent methods becoming humongous and thus slow to compile.
-      return false;
+      return InliningDecision::No("--inlining-caller-size-threshold");
     }
     if (const_arg_count > 0) {
       if (instr_count > FLAG_inlining_constant_arguments_max_size_threshold) {
-        return false;
+        return InliningDecision(
+            false, "--inlining-constant-arguments-max-size-threshold");
       }
     } else if (instr_count > FLAG_inlining_callee_size_threshold) {
-      return false;
+      return InliningDecision::No("--inlining-callee-size-threshold");
+    }
+    int callee_inlining_depth = callee.inlining_depth();
+    if (callee_inlining_depth > 0 && callee_inlining_depth + inlining_depth_ >
+                                         FLAG_inlining_depth_threshold) {
+      return InliningDecision::No("--inlining-depth-threshold");
     }
     // 'instr_count' can be 0 if it was not computed yet.
     if ((instr_count != 0) && (instr_count <= FLAG_inlining_size_threshold)) {
-      return true;
+      return InliningDecision::Yes("--inlining-size-threshold");
     }
     if (call_site_count <= FLAG_inlining_callee_call_sites_threshold) {
-      return true;
+      return InliningDecision::Yes("--inlining-callee-call-sites-threshold");
     }
     if ((const_arg_count >= FLAG_inlining_constant_arguments_count) &&
         (instr_count <= FLAG_inlining_constant_arguments_min_size_threshold)) {
-      return true;
+      return InliningDecision(true,
+                              "--inlining-constant-arguments-count and "
+                              "inlining-constant-arguments-min-size-threshold");
     }
-    return false;
+    return InliningDecision::No("default");
   }
 
   void InlineCalls() {
     // If inlining depth is less than one abort.
     if (inlining_depth_threshold_ < 1) return;
     if (caller_graph_->function().deoptimization_counter() >=
         FLAG_deoptimization_counter_inlining_threshold) {
       return;
     }
     // Create two call site collections to swap between.
@@ skipping 14 matching lines @@
       if (FLAG_print_inlining_tree) {
         THR_Print("**Depth % " Pd " calls to inline %" Pd "\n", inlining_depth_,
                   collected_call_sites_->NumCalls());
       }
       // 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.
-      InlineInstanceCalls();
-      InlineStaticCalls();
-      InlineClosureCalls();
-      // Increment the inlining depths. Checked before subsequent inlining.
-      ++inlining_depth_;
-      if (inlined_recursive_call_) {
-        ++inlining_recursion_depth_;
-        inlined_recursive_call_ = false;
+      bool inlined_instance = InlineInstanceCalls();
+      bool inlined_statics = InlineStaticCalls();
+      bool inlined_closures = InlineClosureCalls();
+      if (inlined_instance || inlined_statics || inlined_closures) {
+        // Increment the inlining depths. Checked before subsequent inlining.
+        ++inlining_depth_;
+        if (inlined_recursive_call_) {
+          ++inlining_recursion_depth_;
+          inlined_recursive_call_ = false;
+        }
+        thread()->CheckForSafepoint();
       }
-      thread()->CheckForSafepoint();
     }
 
     collected_call_sites_ = NULL;
     inlining_call_sites_ = NULL;
   }
 
   bool inlined() const { return inlined_; }
 
   double GrowthFactor() const {
     return static_cast<double>(inlined_size_) /
@@ skipping 36 matching lines @@
     if (FLAG_precompiled_mode && function.is_intrinsic() &&
         !inliner_->AlwaysInline(function)) {
       TRACE_INLINING(THR_Print("     Bailout: intrinisic\n"));
       PRINT_INLINING_TREE("intrinsic", &call_data->caller, &function,
                           call_data->call);
       return false;
     }
 
     // Do not rely on function type feedback or presence of code to determine
     // if a function was compiled.
-    if (!FLAG_precompiled_mode && !function.was_compiled()) {
+    if (!FLAG_precompiled_mode && !function.WasCompiled()) {
       TRACE_INLINING(THR_Print("     Bailout: not compiled yet\n"));
       PRINT_INLINING_TREE("Not compiled", &call_data->caller, &function,
                           call_data->call);
       return false;
     }
 
     if ((inliner_->precompiler_ != NULL) &&
         inliner_->precompiler_->HasFeedback() &&
         (function.usage_counter() <= 0) && !inliner_->AlwaysInline(function)) {
       TRACE_INLINING(THR_Print("     Bailout: not compiled yet\n"));
@@ skipping 23 matching lines @@
 
     const char* kNeverInlineAnnotation = "NeverInline";
     if (FLAG_enable_inlining_annotations &&
         HasAnnotation(function, kNeverInlineAnnotation)) {
       TRACE_INLINING(THR_Print("     Bailout: NeverInline annotation\n"));
       return false;
     }
 
     GrowableArray<Value*>* arguments = call_data->arguments;
     const intptr_t constant_arguments = CountConstants(*arguments);
-    if (!ShouldWeInline(function, function.optimized_instruction_count(),
-                        function.optimized_call_site_count(),
-                        constant_arguments)) {
+    InliningDecision decision = ShouldWeInline(
+        function, function.optimized_instruction_count(),
+        function.optimized_call_site_count(), constant_arguments);
+    if (!decision.value) {
       TRACE_INLINING(
-          THR_Print("     Bailout: early heuristics with "
+          THR_Print("     Bailout: early heuristics (%s) with "
                     "code size:  %" Pd ", "
                     "call sites: %" Pd ", "
+                    "inlining depth of callee: %d, "
                     "const args: %" Pd "\n",
-                    function.optimized_instruction_count(),
-                    function.optimized_call_site_count(), constant_arguments));
+                    decision.reason, function.optimized_instruction_count(),
+                    function.optimized_call_site_count(),
+                    function.inlining_depth(), constant_arguments));
       PRINT_INLINING_TREE("Early heuristic", &call_data->caller, &function,
                           call_data->call);
       return false;
     }
 
     // Abort if this is a recursive occurrence.
     Definition* call = call_data->call;
     // Added 'volatile' works around a possible GCC 4.9 compiler bug.
     volatile bool is_recursive_call = IsCallRecursive(function, call);
     if (is_recursive_call &&
@@ skipping 220 matching lines @@
         // TODO(zerny): Do this after CP and dead code elimination.
         intptr_t constants_count = 0;
         for (intptr_t i = 0; i < param_stubs->length(); ++i) {
           if ((*param_stubs)[i]->IsConstant()) ++constants_count;
         }
 
         FlowGraphInliner::CollectGraphInfo(callee_graph);
         const intptr_t size = function.optimized_instruction_count();
         const intptr_t call_site_count = function.optimized_call_site_count();
 
-        function.set_optimized_instruction_count(size);
-        function.set_optimized_call_site_count(call_site_count);
-
         // Use heuristics do decide if this call should be inlined.
-        if (!ShouldWeInline(function, size, call_site_count, constants_count)) {
+        InliningDecision decision =
+            ShouldWeInline(function, size, call_site_count, constants_count);
+        if (!decision.value) {
           // If size is larger than all thresholds, don't consider it again.
           if ((size > FLAG_inlining_size_threshold) &&
               (call_site_count > FLAG_inlining_callee_call_sites_threshold) &&
               (size > FLAG_inlining_constant_arguments_min_size_threshold) &&
               (size > FLAG_inlining_constant_arguments_max_size_threshold)) {
             function.set_is_inlinable(false);
           }
           thread()->set_deopt_id(prev_deopt_id);
           TRACE_INLINING(
-              THR_Print("     Bailout: heuristics with "
+              THR_Print("     Bailout: heuristics (%s) with "
                         "code size:  %" Pd ", "
                         "call sites: %" Pd ", "
+                        "inlining depth of callee: %d, "
                         "const args: %" Pd "\n",
-                        size, call_site_count, constants_count));
+                        decision.reason, size, call_site_count,
+                        function.inlining_depth(), constants_count));
           PRINT_INLINING_TREE("Heuristic fail", &call_data->caller, &function,
                               call_data->call);
           return false;
         }
 
         // Inline dispatcher methods regardless of the current depth.
         const intptr_t depth =
             function.IsDispatcherOrImplicitAccessor() ? 0 : inlining_depth_;
         collected_call_sites_->FindCallSites(callee_graph, depth,
                                              &inlined_info_);
@@ skipping 175 matching lines @@
     *in_cache = false;
     ParsedFunction* parsed_function =
         new (Z) ParsedFunction(thread(), function);
     if (!UseKernelFrontEndFor(parsed_function)) {
       Parser::ParseFunction(parsed_function);
       parsed_function->AllocateVariables();
     }
     return parsed_function;
   }
 
-  void InlineStaticCalls() {
+  bool InlineStaticCalls() {
+    bool inlined = false;
     const GrowableArray<CallSites::StaticCallInfo>& call_info =
         inlining_call_sites_->static_calls();
     TRACE_INLINING(THR_Print("  Static Calls (%" Pd ")\n", call_info.length()));
     for (intptr_t call_idx = 0; call_idx < call_info.length(); ++call_idx) {
       StaticCallInstr* call = call_info[call_idx].call;
       const Function& target = call->function();
       if (!inliner_->AlwaysInline(target) &&
           (call_info[call_idx].ratio * 100) < FLAG_inlining_hotness) {
         if (trace_inlining()) {
           String& name = String::Handle(target.QualifiedUserVisibleName());
           THR_Print("  => %s (deopt count %d)\n     Bailout: cold %f\n",
                     name.ToCString(), target.deoptimization_counter(),
                     call_info[call_idx].ratio);
         }
         PRINT_INLINING_TREE("Too cold", &call_info[call_idx].caller(),
                             &call->function(), call);
         continue;
       }
       GrowableArray<Value*> arguments(call->ArgumentCount());
       for (int i = 0; i < call->ArgumentCount(); ++i) {
         arguments.Add(call->PushArgumentAt(i)->value());
       }
       InlinedCallData call_data(
           call, call->FirstArgIndex(), &arguments, call_info[call_idx].caller(),
           call_info[call_idx].caller_graph->inlining_id());
       if (TryInlining(call->function(), call->argument_names(), &call_data)) {
         InlineCall(&call_data);
+        inlined = true;
       }
     }
+    return inlined;
   }
 
-  void InlineClosureCalls() {
+  bool InlineClosureCalls() {
+    bool inlined = false;
     const GrowableArray<CallSites::ClosureCallInfo>& call_info =
         inlining_call_sites_->closure_calls();
     TRACE_INLINING(
         THR_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 =
@@ skipping 21 matching lines @@
 
       GrowableArray<Value*> arguments(call->ArgumentCount());
       for (int i = 0; i < call->ArgumentCount(); ++i) {
         arguments.Add(call->PushArgumentAt(i)->value());
       }
       InlinedCallData call_data(
           call, call->FirstArgIndex(), &arguments, call_info[call_idx].caller(),
           call_info[call_idx].caller_graph->inlining_id());
       if (TryInlining(target, call->argument_names(), &call_data)) {
         InlineCall(&call_data);
+        inlined = true;
       }
     }
+    return inlined;
   }
 
-  void InlineInstanceCalls() {
+  bool InlineInstanceCalls() {
+    bool inlined = false;
     const GrowableArray<CallSites::InstanceCallInfo>& call_info =
         inlining_call_sites_->instance_calls();
     TRACE_INLINING(THR_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;
       // PolymorphicInliner introduces deoptimization paths.
       if (!call->complete() && !FLAG_polymorphic_with_deopt) {
         TRACE_INLINING(
             THR_Print("  => %s\n     Bailout: call with checks\n",
                       call->instance_call()->function_name().ToCString()));
         continue;
       }
       const Function& cl = call_info[call_idx].caller();
       intptr_t caller_inlining_id =
           call_info[call_idx].caller_graph->inlining_id();
       PolymorphicInliner inliner(this, call, cl, caller_inlining_id);
-      inliner.Inline();
+      if (inliner.Inline()) inlined = true;
     }
+    return inlined;
   }
 
   bool AdjustForOptionalParameters(const ParsedFunction& parsed_function,
                                    intptr_t first_arg_index,
                                    const Array& argument_names,
                                    GrowableArray<Value*>* arguments,
                                    ZoneGrowableArray<Definition*>* param_stubs,
                                    FlowGraph* callee_graph) {
     const Function& function = parsed_function.function();
     // The language and this code does not support both optional positional
@@ skipping 534 matching lines @@
   int percent = total == 0 ? 0 : (100 * targets.TargetAt(idx)->count) / total;
   THR_Print("%s cid %" Pd "-%" Pd ": %" Pd "/%" Pd " %d%% %s\n",
             name.ToCString(), targets[idx].cid_start, targets[idx].cid_end,
             targets.TargetAt(idx)->count, total, percent, message);
 }
 
 bool PolymorphicInliner::trace_inlining() const {
   return owner_->trace_inlining();
 }
 
-void PolymorphicInliner::Inline() {
+bool PolymorphicInliner::Inline() {
   ASSERT(&variants_ == &call_->targets_);
 
   intptr_t total = call_->total_call_count();
   for (intptr_t var_idx = 0; var_idx < variants_.length(); ++var_idx) {
     TargetInfo* info = variants_.TargetAt(var_idx);
     if (variants_.length() > FLAG_max_polymorphic_checks) {
       non_inlined_variants_->Add(info);
       continue;
     }
 
@@ skipping 52 matching lines @@
       TRACE_INLINING(TracePolyInlining(variants_, var_idx, total, "inlined"));
       inlined_variants_.Add(&variants_[var_idx]);
     } else {
       TRACE_INLINING(
           TracePolyInlining(variants_, var_idx, total, "not inlined"));
       non_inlined_variants_->Add(&variants_[var_idx]);
     }
   }
 
   // If there are no inlined variants, leave the call in place.
-  if (inlined_variants_.is_empty()) return;
+  if (inlined_variants_.is_empty()) return false;
 
   // Now build a decision tree (a DAG because of shared inline variants) and
   // inline it at the call site.
   TargetEntryInstr* entry = BuildDecisionGraph();
   exit_collector_->ReplaceCall(entry);
-}
-
-static uint16_t ClampUint16(intptr_t v) {
-  return (v > 0xFFFF) ? 0xFFFF : static_cast<uint16_t>(v);
+  return true;
 }
 
 static bool ShouldTraceInlining(FlowGraph* flow_graph) {
   const Function& top = flow_graph->parsed_function().function();
   return FLAG_trace_inlining && FlowGraphPrinter::ShouldPrint(top);
 }
 
 FlowGraphInliner::FlowGraphInliner(
     FlowGraph* flow_graph,
     GrowableArray<const Function*>* inline_id_to_function,
@@ skipping 12 matching lines @@
       precompiler_(precompiler) {
   ASSERT(!use_speculative_inlining || (inlining_black_list != NULL));
 }
 
 void FlowGraphInliner::CollectGraphInfo(FlowGraph* flow_graph, bool force) {
   const Function& function = flow_graph->function();
   if (force || (function.optimized_instruction_count() == 0)) {
     GraphInfoCollector info;
     info.Collect(*flow_graph);
 
-    function.set_optimized_instruction_count(
-        ClampUint16(info.instruction_count()));
-    function.set_optimized_call_site_count(ClampUint16(info.call_site_count()));
+    function.SetOptimizedInstructionCountClamped(info.instruction_count());
+    function.SetOptimizedCallSiteCountClamped(info.call_site_count());
   }
 }
 
 // TODO(srdjan): This is only needed when disassembling and/or profiling.
 // Sets inlining id for all instructions of this flow-graph, as well for the
 // FlowGraph itself.
 void FlowGraphInliner::SetInliningId(FlowGraph* flow_graph,
                                      intptr_t inlining_id) {
   ASSERT(flow_graph->inlining_id() < 0);
   flow_graph->set_inlining_id(inlining_id);
@@ skipping 41 matching lines @@
       IsInlineableOperator(function) ||
       (function.kind() == RawFunction::kConstructor)) {
     const intptr_t count = function.optimized_instruction_count();
     if ((count != 0) && (count < FLAG_inline_getters_setters_smaller_than)) {
       return true;
     }
   }
   return MethodRecognizer::AlwaysInline(function);
 }
 
-void FlowGraphInliner::Inline() {
+int 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_->function();
   if ((FLAG_inlining_filter != NULL) &&
       (strstr(top.ToFullyQualifiedCString(), FLAG_inlining_filter) == NULL)) {
-    return;
+    return 0;
   }
 
   if (trace_inlining()) {
     String& name = String::Handle(top.QualifiedUserVisibleName());
     THR_Print("Inlining calls in %s\n", name.ToCString());
   }
 
   if (FLAG_support_il_printer && trace_inlining() &&
       (FLAG_print_flow_graph || FLAG_print_flow_graph_optimized)) {
     THR_Print("Before Inlining of %s\n",
@@ skipping 20 matching lines @@
       THR_Print("Inlining growth factor: %f\n", inliner.GrowthFactor());
       if (FLAG_support_il_printer &&
           (FLAG_print_flow_graph || FLAG_print_flow_graph_optimized)) {
         THR_Print("After Inlining of %s\n",
                   flow_graph_->function().ToFullyQualifiedCString());
         FlowGraphPrinter printer(*flow_graph_);
         printer.PrintBlocks();
       }
     }
   }
+  return inliner.inlining_depth();
 }
 
 intptr_t FlowGraphInliner::NextInlineId(const Function& function,
                                         TokenPosition tp,
                                         intptr_t parent_id) {
   const intptr_t id = inline_id_to_function_->length();
   // TODO(johnmccutchan): Do not allow IsNoSource once all nodes have proper
   // source positions.
   ASSERT(tp.IsReal() || tp.IsSynthetic() || tp.IsNoSource());
   inline_id_to_function_->Add(&function);
@@ skipping 1578 matching lines @@
     }
 
     default:
       return false;
   }
 }
 
 }  // namespace dart
 
 #endif  // !defined(DART_PRECOMPILED_RUNTIME)