Improve inlining heuristics.

pkg/compiler/lib/src/ssa/builder.dart

 // 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.
 
 import 'dart:collection';
 
 import 'package:js_runtime/shared/embedded_names.dart';
 
 import '../closure.dart';
 import '../common.dart';
@@ skipping 460 matching lines @@
           isReachable = false;
           return false;
         }
       }
 
       return true;
     }
 
     bool doesNotContainCode() {
       // A function with size 1 does not contain any code.
-      return InlineWeeder.canBeInlined(functionResolvedAst, 1, true,
+      return InlineWeeder.canBeInlined(elements, functionResolvedAst, 1, true,
           enableUserAssertions: compiler.options.enableUserAssertions);
     }
 
     bool reductiveHeuristic() {
       // The call is on a path which is executed rarely, so inline only if it
       // does not make the program larger.
       if (isCalledOnce(element)) {
-        return InlineWeeder.canBeInlined(functionResolvedAst, -1, false,
-            enableUserAssertions: compiler.options.enableUserAssertions);
+        return InlineWeeder.canBeInlined(elements, functionResolvedAst, -1,
+            false, enableUserAssertions: compiler.options.enableUserAssertions);
       }
       // TODO(sra): Measure if inlining would 'reduce' the size.  One desirable
       // case we miss by doing nothing is inlining very simple constructors
       // where all fields are initialized with values from the arguments at this
       // call site.  The code is slightly larger (`new Foo(1)` vs `Foo$(1)`) but
       // that usually means the factory constructor is left unused and not
       // emitted.
       // We at least inline bodies that are empty (and thus have a size of 1).
       return doesNotContainCode();
     }
@@ skipping 16 matching lines @@
       }
 
       // Do not inline code that is rarely executed unless it reduces size.
       if (inExpressionOfThrow || inLazyInitializerExpression) {
         return reductiveHeuristic();
       }
 
       if (cachedCanBeInlined == true) {
         // We may have forced the inlining of some methods. Therefore check
         // if we can inline this method regardless of size.
-        assert(InlineWeeder.canBeInlined(functionResolvedAst, -1, false,
-            allowLoops: true,
+        assert(InlineWeeder.canBeInlined(elements, functionResolvedAst, -1,
+            false, allowLoops: true,
             enableUserAssertions: compiler.options.enableUserAssertions));
         return true;
       }
 
       int numParameters = function.functionSignature.parameterCount;
       int maxInliningNodes;
       bool useMaxInliningNodes = true;
       if (insideLoop) {
         maxInliningNodes = InlineWeeder.INLINING_NODES_INSIDE_LOOP +
             InlineWeeder.INLINING_NODES_INSIDE_LOOP_ARG_FACTOR * numParameters;
       } else {
         maxInliningNodes = InlineWeeder.INLINING_NODES_OUTSIDE_LOOP +
             InlineWeeder.INLINING_NODES_OUTSIDE_LOOP_ARG_FACTOR * numParameters;
       }
 
       // If a method is called only once, and all the methods in the
       // inlining stack are called only once as well, we know we will
       // save on output size by inlining this method.
       if (isCalledOnce(element)) {
         useMaxInliningNodes = false;
       }
       bool canInline;
       canInline = InlineWeeder.canBeInlined(
+          elements,
           functionResolvedAst, maxInliningNodes, useMaxInliningNodes,
           enableUserAssertions: compiler.options.enableUserAssertions);
       if (canInline) {
         backend.inlineCache.markAsInlinable(element, insideLoop: insideLoop);
       } else {
         backend.inlineCache.markAsNonInlinable(element, insideLoop: insideLoop);
       }
       return canInline;
     }
 
@@ skipping 6047 matching lines @@
   static const INLINING_NODES_INSIDE_LOOP_ARG_FACTOR = 4;
 
   bool seenReturn = false;
   bool tooDifficult = false;
   int nodeCount = 0;
   final int maxInliningNodes;
   final bool useMaxInliningNodes;
   final bool allowLoops;
   final bool enableUserAssertions;
 
-  InlineWeeder(this.maxInliningNodes, this.useMaxInliningNodes, this.allowLoops,
+  final TreeElements elements;
+
+  InlineWeeder(this.elements,
+      this.maxInliningNodes, this.useMaxInliningNodes, this.allowLoops,
       this.enableUserAssertions);
 
   static bool canBeInlined(
+      TreeElements elements,
       ResolvedAst resolvedAst, int maxInliningNodes, bool useMaxInliningNodes,
       {bool allowLoops: false, bool enableUserAssertions: null}) {
     assert(enableUserAssertions is bool); // Ensure we passed it.
     if (resolvedAst.elements.containsTryStatement) return false;

[sra1, 2017/02/28 22:48:28]

elements does not need to be passed in, since it it resolvedAst.elements

[floitsch, 2017/03/01 08:50:45]

even better.

 
-    InlineWeeder weeder = new InlineWeeder(maxInliningNodes,
+    InlineWeeder weeder = new InlineWeeder(elements,
+        maxInliningNodes,
         useMaxInliningNodes, allowLoops, enableUserAssertions);
     ast.FunctionExpression functionExpression = resolvedAst.node;
+
     weeder.visit(functionExpression.initializers);
     weeder.visit(functionExpression.body);
     weeder.visit(functionExpression.asyncModifier);
     return !weeder.tooDifficult;
   }
 
   bool registerNode() {
     if (!useMaxInliningNodes) return true;
     if (nodeCount++ > maxInliningNodes) {
       tooDifficult = true;
@@ skipping 34 matching lines @@
     if (!registerNode()) return;
     tooDifficult = true;
   }
 
   void visitFunctionDeclaration(ast.Node node) {
     if (!registerNode()) return;
     tooDifficult = true;
   }
 
   void visitSend(ast.Send node) {
+    /*

[floitsch, 2016/12/21 10:36:24]

Enabling this, slightly increases the output size.

I think we can play a bit with the max-sizes, though. If we count references to
the arguments as less important, then we can try to decrease the overall
inlining size.

+    Element element = elements[node];
+    if (element != null && element.isParameter) {
+      // Don't count as additional node, since it's likely that passing the
+      // argument would cost us as much space as we inline.

[sra1, 2017/02/28 19:36:15]

It will cost a temporary if it is used twice.
Can we count uses?

[floitsch, 2017/03/01 08:50:45]

That's true, unless the parameter is a constant or already in a temporary.
I do agree that we shouldn't just ignore sends to arguments, *but* they should
be counted less than other variables. Lots of chances of optimizations when one
can inline declarations to their uses.

+      return;
+    }
+    */
     if (!registerNode()) return;
     node.visitChildren(this);
   }
 
   visitLoop(ast.Node node) {
     // It's actually not difficult to inline a method with a loop, but
     // our measurements show that it's currently better to not inline a
     // method that contains a loop.
     if (!allowLoops) tooDifficult = true;
   }
 
   void visitRedirectingFactoryBody(ast.RedirectingFactoryBody node) {
     if (!registerNode()) return;
     tooDifficult = true;
   }
 
+  void visitConditional(ast.Conditional node) {
+    visit(node.condition);
+    if (tooDifficult) return;
+    int oldCount = nodeCount;

[sra1, 2017/02/28 19:36:15]

I think this code would be easier to understand if this was called
commonPrefixCount, and the then/else were explicitly computed.

[floitsch, 2017/03/01 08:50:45]

Acknowledged.

+    visit(node.thenExpression);
+    if (tooDifficult) return;
+    int thenCount = nodeCount;

[sra1, 2017/02/28 19:36:15]

int thenCount = nodeCount - commonPrefixCount
...
int elseCount = nodeCount - commonPrefixCount


nodeCount = commonPrefixCount + max(thenCount, elseCount);
...
nodeCount = commonPrefixCount + thenCount + elseCount;

[floitsch, 2017/03/01 08:50:45]

Acknowledged.

+    nodeCount = oldCount;
+    visit(node.elseExpression);
+    if (tooDifficult) return;
+    if (node.condition.asSend() != null &&

[sra1, 2017/02/28 19:36:15]

Add a comment that this is a heuristic - a parameter directly used in a
conditional is likely to be a constant, so count only the biggest arm.

[floitsch, 2017/03/01 08:50:45]

Acknowledged.

+        elements[node.condition]?.isParameter == true) {
+      nodeCount = thenCount > nodeCount ? thenCount : nodeCount;
+    } else {
+      nodeCount += (thenCount - oldCount);
+    }
+    if (!registerNode()) return;
+
+  }
+
   void visitRethrow(ast.Rethrow node) {
     if (!registerNode()) return;
     tooDifficult = true;
   }
 
   void visitReturn(ast.Return node) {
     if (!registerNode()) return;
     if (seenReturn || identical(node.beginToken.stringValue, 'native')) {
       tooDifficult = true;
       return;
@@ skipping 40 matching lines @@
       this.oldReturnLocal,
       this.oldReturnType,
       this.oldResolvedAst,
       this.oldStack,
       this.oldLocalsHandler,
       this.inTryStatement,
       this.allFunctionsCalledOnce,
       this.oldElementInferenceResults)
       : super(function);
 }