[dart/vm] Improved inlining methods and heuristics

aartbik · commit-bot@chromium.org · commit fa6fce61fae6 · 2019-06-12T19:39:10.000Z
Rationale: Previous method cached graph information (instruction and call site counts) on a per-function level, not accounting for potential specializations. The improved method runs an extra constant folding pass, and only caches per-function information for non-specialized cases. As a result, we inling much better, see for example, the added test as illustration. Since we no longer cache for constants, compile-time may be increased a bit due to the extra scan. In the long run we should consider for common constant "situations" as the call site. #36880 Change-Id: I19f007c7f1860ad0ea88fafb38695dc154189ad5 Reviewed-on: https://dart-review.googlesource.com/c/sdk/+/105460 Commit-Queue: Aart Bik <ajcbik@google.com> Reviewed-by: Martin Kustermann <kustermann@google.com> Reviewed-by: Alexander Markov <alexmarkov@google.com>
diff --git a/runtime/vm/compiler/backend/constant_propagator.cc b/runtime/vm/compiler/backend/constant_propagator.cc
@@ -1453,7 +1453,8 @@ void ConstantPropagator::EliminateRedundantBranches() {
 static void RemovePushArguments(StaticCallInstr* call) {
   for (intptr_t i = 0; i < call->ArgumentCount(); ++i) {
     PushArgumentInstr* push = call->PushArgumentAt(i);
-    ASSERT(push->input_use_list() == nullptr);
+    ASSERT(push->input_use_list() == nullptr);           // no direct uses
+    push->ReplaceUsesWith(push->value()->definition());  // cleanup env uses
     push->RemoveFromGraph();
   }
 }
diff --git a/runtime/vm/compiler/backend/inliner.cc b/runtime/vm/compiler/backend/inliner.cc
@@ -779,6 +779,8 @@ class CallSiteInliner : public ValueObject {
   };
 
   // Inlining heuristics based on Cooper et al. 2008.
+  // TODO(ajcbik): with the better specialized computation of counts,
+  //               do we still want to special-case const_arg_count here?
   InliningDecision ShouldWeInline(const Function& callee,
                                   intptr_t instr_count,
                                   intptr_t call_site_count,
@@ -955,21 +957,28 @@ class CallSiteInliner : public ValueObject {
       return false;
     }
 
+    // Apply early heuristics. For a specialized case
+    // (constants_arg_counts > 0), don't use a previously
+    // estimate of the call site and instruction counts.
+    // Note that at this point, optional constant parameters
+    // are not counted yet, which makes this decision approximate.
     GrowableArray<Value*>* arguments = call_data->arguments;
-    const intptr_t constant_arguments = CountConstants(*arguments);
+    const intptr_t constant_arg_count = CountConstants(*arguments);
+    const intptr_t instruction_count =
+        constant_arg_count == 0 ? function.optimized_instruction_count() : 0;
+    const intptr_t call_site_count =
+        constant_arg_count == 0 ? function.optimized_call_site_count() : 0;
     InliningDecision decision = ShouldWeInline(
-        function, function.optimized_instruction_count(),
-        function.optimized_call_site_count(), constant_arguments);
+        function, instruction_count, call_site_count, constant_arg_count);
     if (!decision.value) {
       TRACE_INLINING(
           THR_Print("     Bailout: early heuristics (%s) with "
                     "code size:  %" Pd ", "
                     "call sites: %" Pd ", "
                     "inlining depth of callee: %d, "
                     "const args: %" Pd "\n",
-                    decision.reason, function.optimized_instruction_count(),
-                    function.optimized_call_site_count(),
-                    function.inlining_depth(), constant_arguments));
+                    decision.reason, instruction_count, call_site_count,
+                    function.inlining_depth(), constant_arg_count));
       PRINT_INLINING_TREE("Early heuristic", &call_data->caller, &function,
                           call_data->call);
       return false;
@@ -1193,26 +1202,30 @@ class CallSiteInliner : public ValueObject {
           printer.PrintBlocks();
         }
 
-        // Collect information about the call site and caller graph.
-        // TODO(zerny): Do this after CP and dead code elimination.
+        // Collect information about the call site and caller graph. At this
+        // point, optional constant parameters are counted too, making the
+        // specialized vs. non-specialized decision accurate.
         intptr_t constants_count = 0;
-        for (intptr_t i = 0; i < param_stubs->length(); ++i) {
+        for (intptr_t i = 0, n = param_stubs->length(); i < n; ++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();
+        intptr_t instruction_count = 0;
+        intptr_t call_site_count = 0;
+        FlowGraphInliner::CollectGraphInfo(callee_graph, constants_count,
+                                           /*force*/ false, &instruction_count,
+                                           &call_site_count);
 
         // Use heuristics do decide if this call should be inlined.
-        InliningDecision decision =
-            ShouldWeInline(function, size, call_site_count, constants_count);
+        InliningDecision decision = ShouldWeInline(
+            function, instruction_count, 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) &&
+          if ((instruction_count > 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)) {
+              (instruction_count >
+               FLAG_inlining_constant_arguments_min_size_threshold) &&
+              (instruction_count >
+               FLAG_inlining_constant_arguments_max_size_threshold)) {
             function.set_is_inlinable(false);
           }
           TRACE_INLINING(
@@ -1221,7 +1234,7 @@ class CallSiteInliner : public ValueObject {
                         "call sites: %" Pd ", "
                         "inlining depth of callee: %d, "
                         "const args: %" Pd "\n",
-                        decision.reason, size, call_site_count,
+                        decision.reason, instruction_count, call_site_count,
                         function.inlining_depth(), constants_count));
           PRINT_INLINING_TREE("Heuristic fail", &call_data->caller, &function,
                               call_data->call);
@@ -1231,6 +1244,7 @@ class CallSiteInliner : public ValueObject {
         // If requested, a stricter heuristic is applied to this inlining. This
         // heuristic always scans the method (rather than possibly reusing
         // cached results) to make sure all specializations are accounted for.
+        // TODO(ajcbik): with the now better bookkeeping, explore removing this
         if (stricter_heuristic) {
           if (!IsSmallLeaf(callee_graph)) {
             TRACE_INLINING(
@@ -1254,7 +1268,7 @@ class CallSiteInliner : public ValueObject {
 
         // Build succeeded so we restore the bailout jump.
         inlined_ = true;
-        inlined_size_ += size;
+        inlined_size_ += instruction_count;
         if (is_recursive_call) {
           inlined_recursive_call_ = true;
         }
@@ -1284,8 +1298,7 @@ class CallSiteInliner : public ValueObject {
         TRACE_INLINING(THR_Print("     Success\n"));
         TRACE_INLINING(THR_Print(
             "       with reason %s, code size %" Pd ", call sites: %" Pd "\n",
-            decision.reason, function.optimized_instruction_count(),
-            call_site_count));
+            decision.reason, instruction_count, call_site_count));
         PRINT_INLINING_TREE(NULL, &call_data->caller, &function, call);
         return true;
       } else {
@@ -1481,6 +1494,10 @@ class CallSiteInliner : public ValueObject {
   }
 
   bool InlineClosureCalls() {
+    // Under this flag, tear off testing closure calls appear before the
+    // StackOverflowInstr, which breaks assertions in our compiler when inlined.
+    // TODO(sjindel): move testing closure calls after first check
+    if (FLAG_enable_testing_pragmas) return false;  // keep all closures
     bool inlined = false;
     const GrowableArray<CallSites::ClosureCallInfo>& call_info =
         inlining_call_sites_->closure_calls();
@@ -2237,15 +2254,37 @@ FlowGraphInliner::FlowGraphInliner(
       speculative_policy_(speculative_policy),
       precompiler_(precompiler) {}
 
-void FlowGraphInliner::CollectGraphInfo(FlowGraph* flow_graph, bool force) {
+void FlowGraphInliner::CollectGraphInfo(FlowGraph* flow_graph,
+                                        intptr_t constants_count,
+                                        bool force,
+                                        intptr_t* instruction_count,
+                                        intptr_t* call_site_count) {
   const Function& function = flow_graph->function();
+  // For OSR, don't even bother.
+  if (flow_graph->IsCompiledForOsr()) {
+    *instruction_count = 0;
+    *call_site_count = 0;
+    return;
+  }
+  // Specialized case: always recompute, never cache.
+  if (constants_count > 0) {
+    ASSERT(!force);
+    GraphInfoCollector info;
+    info.Collect(*flow_graph);
+    *instruction_count = info.instruction_count();
+    *call_site_count = info.call_site_count();
+    return;
+  }
+  // Non-specialized case: unless forced, only recompute on a cache miss.
+  ASSERT(constants_count == 0);
   if (force || (function.optimized_instruction_count() == 0)) {
     GraphInfoCollector info;
     info.Collect(*flow_graph);
-
     function.SetOptimizedInstructionCountClamped(info.instruction_count());
     function.SetOptimizedCallSiteCountClamped(info.call_site_count());
   }
+  *instruction_count = function.optimized_instruction_count();
+  *call_site_count = function.optimized_call_site_count();
 }
 
 // TODO(srdjan): This is only needed when disassembling and/or profiling.
@@ -2312,9 +2351,15 @@ bool FlowGraphInliner::AlwaysInline(const Function& function) {
 }
 
 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_);
+  // Collect some early graph information assuming it is non-specialized
+  // so that the cached approximation may be used later for an early
+  // bailout from inlining.
+  intptr_t instruction_count = 0;
+  intptr_t call_site_count = 0;
+  FlowGraphInliner::CollectGraphInfo(flow_graph_,
+                                     /*constants_count*/ 0,
+                                     /*force*/ false, &instruction_count,
+                                     &call_site_count);
 
   const Function& top = flow_graph_->function();
   if ((FLAG_inlining_filter != NULL) &&
diff --git a/runtime/vm/compiler/backend/inliner.h b/runtime/vm/compiler/backend/inliner.h
@@ -96,8 +96,21 @@ class FlowGraphInliner : ValueObject {
   // depth that we inlined.
   int Inline();
 
-  // Compute graph info if it was not already computed or if 'force' is true.
-  static void CollectGraphInfo(FlowGraph* flow_graph, bool force = false);
+  // Computes graph information (instruction and call site count).
+  // For the non-specialized cases (num_constants_args == 0), the
+  // method uses a cache to avoid recomputing the counts (the cached
+  // value may still be approximate but close). The 'force' flag is
+  // used to update the cached value at the end of running the full pipeline
+  // on non-specialized cases. Specialized cases (num_constants_args > 0)
+  // always recompute the counts without caching.
+  //
+  // TODO(ajcbik): cache for specific constant argument combinations too?
+  static void CollectGraphInfo(FlowGraph* flow_graph,
+                               intptr_t num_constant_args,
+                               bool force,
+                               intptr_t* instruction_count,
+                               intptr_t* call_site_count);
+
   static void SetInliningId(FlowGraph* flow_graph, intptr_t inlining_id);
 
   bool AlwaysInline(const Function& function);
diff --git a/runtime/vm/compiler/compiler_pass.cc b/runtime/vm/compiler/compiler_pass.cc
@@ -217,6 +217,9 @@ void CompilerPass::RunInliningPipeline(PipelineMode mode,
   INVOKE_PASS(TypePropagation);
   INVOKE_PASS(ApplyICData);
   INVOKE_PASS(Canonicalize);
+  // Run constant propagation to make sure we specialize for
+  // (optional) constant arguments passed into the inlined method.
+  INVOKE_PASS(ConstantPropagation);
   // Optimize (a << b) & c patterns, merge instructions. Must occur
   // before 'SelectRepresentations' which inserts conversion nodes.
   INVOKE_PASS(TryOptimizePatterns);
@@ -475,10 +478,17 @@ COMPILER_PASS(WriteBarrierElimination,
               { WriteBarrierElimination(flow_graph); });
 
 COMPILER_PASS(FinalizeGraph, {
-  // Compute and store graph informations (call & instruction counts)
-  // to be later used by the inliner.
-  FlowGraphInliner::CollectGraphInfo(flow_graph, true);
+  // At the end of the pipeline, force recomputing and caching graph
+  // information (instruction and call site counts) for the (assumed)
+  // non-specialized case with better values, for future inlining.
+  intptr_t instruction_count = 0;
+  intptr_t call_site_count = 0;
+  FlowGraphInliner::CollectGraphInfo(flow_graph,
+                                     /*constants_count*/ 0,
+                                     /*force*/ true, &instruction_count,
+                                     &call_site_count);
   flow_graph->function().set_inlining_depth(state->inlining_depth);
+  // Remove redefinitions for the rest of the pipeline.
   flow_graph->RemoveRedefinitions();
 });
 
diff --git a/tests/language_2/vm/inline_heuristic_test.dart b/tests/language_2/vm/inline_heuristic_test.dart

Original file line number	Diff line number	Diff line change
`@@ -1453,7 +1453,8 @@ void ConstantPropagator::EliminateRedundantBranches() {`
`1453`	`1453`	`static void RemovePushArguments(StaticCallInstr* call) {`
`1454`	`1454`	`for (intptr_t i = 0; i < call->ArgumentCount(); ++i) {`
`1455`	`1455`	`PushArgumentInstr* push = call->PushArgumentAt(i);`
`1456`		`- ASSERT(push->input_use_list() == nullptr);`
	`1456`	`+ ASSERT(push->input_use_list() == nullptr); // no direct uses`
	`1457`	`+ push->ReplaceUsesWith(push->value()->definition()); // cleanup env uses`
`1457`	`1458`	`push->RemoveFromGraph();`
`1458`	`1459`	`}`
`1459`	`1460`	`}`