Support for inlining small methods (independent of they're called inside a loop or not)

sdk/lib/_internal/compiler/implementation/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.
 
 part of ssa;
 
 /**
  * A special element for the extra parameter taken by intercepted
  * methods. We need to override [Element.computeType] because our
  * optimizers may look at its declared type.
@@ skipping 911 matching lines @@
       activationVariables = new Map<Element, HLocalValue>(),
       jumpTargets = new Map<TargetElement, JumpHandler>(),
       parameters = new Map<Element, HInstruction>(),
       sourceElementStack = <Element>[work.element],
       inliningStack = <InliningState>[],
       rti = builder.backend.rti,
       super(work.resolutionTree) {
     localsHandler = new LocalsHandler(this);
   }
 
-  static const MAX_INLINING_DEPTH = 3;
-  static const MAX_INLINING_NODES = 46;
+  static const MAX_INLINING_DEPTH = 5;

[ngeoffray, 2013/07/16 08:04:45]

Consider moving inlining considerations into its own class.

[kustermann, 2013/07/16 13:27:50]

Moved it now to InlineWeeder.

+  // Invariant: *INSIDE_LOOP* > *OUTSIDE_LOOP*
+  static const INLINING_NODES_OUTSIDE_LOOP = 10;
+  static const INLINING_NODES_OUTSIDE_LOOP_ARG_FACTOR = 10;
+  static const INLINING_NODES_INSIDE_LOOP = 35;
+  static const INLINING_NODES_INSIDE_LOOP_ARG_FACTOR = 15;
 
   List<InliningState> inliningStack;
 
   Element returnElement;
   DartType returnType;
 
   bool inTryStatement = false;
   int loopNesting = 0;
 
   HBasicBlock get current => _current;
@@ skipping 274 matching lines @@
   bool tryInlineMethod(Element element,
                        Selector selector,
                        List<HInstruction> providedArguments,
                        Node currentNode) {
     backend.registerStaticUse(element, compiler.enqueuer.codegen);
 
     // Ensure that [element] is an implementation element.
     element = element.implementation;
     FunctionElement function = element;
 
-    bool cachedCanBeInlined = backend.canBeInlined[function];
+    var insideLoop = loopNesting > 0 || graph.calledInLoop;

[ngeoffray, 2013/07/16 08:04:45]

var -> bool

[kustermann, 2013/07/16 13:27:50]

Done.

+
+    // Bail out early if the inlining decision is in the cache and we can't
+    // inline (no need to check the hard constraints).
+    bool cachedCanBeInlined =
+        backend.inlineCache.canInline(function, insideLoop: insideLoop);
     if (cachedCanBeInlined == false) return false;
 
     bool meetsHardConstraints() {
       // We cannot inline a method from a deferred library into a method
       // which isn't deferred.
       // TODO(ahe): But we should still inline into the same
       // connected-component of the deferred library.
       if (compiler.deferredLoadTask.isDeferred(element)) return false;
       if (compiler.disableInlining) return false;
 
@@ skipping 13 matching lines @@
 
       // Don't inline if the return type was inferred to be non-null empty. This
       // means that the function always throws an exception.
       TypeMask returnType =
           compiler.typesTask.getGuaranteedReturnTypeOfElement(element);
       if (returnType != null && returnType.isEmpty && !returnType.isNullable) {
         isReachable = false;
         return false;
       }
 
+      // Don't inline recursivly

[ngeoffray, 2013/07/16 08:04:45]

Shouldn't that be part of the heuristics?

[kustermann, 2013/07/16 13:27:50]

Why should this be part of a heuristic? We require that the inliner doesn't run
into an infinite loop (=> hard constraint).

We could of course say that we allow recursive inlining up to a certain depth or
so. But I'm not sure if this would be worth it.

+      if (inliningStack.any((entry) => entry.function == function))

[kustermann, 2013/07/15 17:40:27]

I'll add a test to make sure this guard against recursive inlining works.

[ngeoffray, 2013/07/16 08:04:45]

Nit: add braces with a newline on an if.

[kustermann, 2013/07/16 13:27:50]

I saw this style
  if (cond)
    return x;
quite a lot in the code, so I thought that's how the dart2js gods like it.

+        return false;
+
       return true;
     }
 
-    bool heuristicsSayGoodToGo(FunctionExpression functionExpression,
-                                TreeElements newElements) {
-      if (loopNesting == 0 && !graph.calledInLoop) return false;
+    bool heuristicSayGoodToGo(FunctionExpression functionExpression) {
+      //if (inliningStack.length >= MAX_INLINING_DEPTH) {

[kustermann, 2013/07/15 17:40:27]

Don't know if we should limit the inlining depth here (we may want to inline
small functions always).

[ngeoffray, 2013/07/16 08:04:45]

Should we have a canBeInlined cache for methods that are inlined after
MAX_INLINING_DEPTH? This cache would be filled with small methods, smaller than
the current INLINING_NODES constants.

[kustermann, 2013/07/16 13:27:50]

I think we should not make our inlining decisions based on how deep the inlining
stack is. There are other things we should consider for the heuristics, but not
the inlining depth
 - guessing the number of call sites of a function (could be collected by the
type inference algorithm?)
 - ...

This code was probably here only to guard against running into a recursion.

+      //  return false;
+      //}
 
-      int maxDepth = (loopNesting > 0) ? MAX_INLINING_DEPTH : 1;
-      if (inliningStack.length >= maxDepth) return false;
+      if (cachedCanBeInlined == true)
+        return cachedCanBeInlined;

[ngeoffray, 2013/07/16 08:04:45]

One line, or braces.

[kustermann, 2013/07/16 13:27:50]

Done.

 
-      if (cachedCanBeInlined == null) {
-        var canBeInlined =
-            InlineWeeder.canBeInlined(functionExpression, newElements);
-        backend.canBeInlined[function] = canBeInlined;
-        return canBeInlined;
+      var numParameters = function.functionSignature.parameterCount;

[ngeoffray, 2013/07/16 08:04:45]

var -> int

[kustermann, 2013/07/16 13:27:50]

Done.

+      var maxInliningNodes;

[ngeoffray, 2013/07/16 08:04:45]

var -> int.

[kustermann, 2013/07/16 13:27:50]

Done.

+      if (insideLoop) {
+        maxInliningNodes = SsaBuilder.INLINING_NODES_INSIDE_LOOP +
+            SsaBuilder.INLINING_NODES_INSIDE_LOOP_ARG_FACTOR * numParameters;
+      } else {
+        maxInliningNodes = SsaBuilder.INLINING_NODES_OUTSIDE_LOOP +
+            SsaBuilder.INLINING_NODES_OUTSIDE_LOOP_ARG_FACTOR * numParameters;
       }
-      return cachedCanBeInlined;
+      var canBeInlined = InlineWeeder.canBeInlined(

[ngeoffray, 2013/07/16 08:04:45]

var -> bool

[kustermann, 2013/07/16 13:27:50]

Done.

+          functionExpression, maxInliningNodes);
+      if (canBeInlined) {
+        backend.inlineCache.markAsInlinable(element, insideLoop: insideLoop);
+      } else {
+        backend.inlineCache.markAsNonInlinable(element, insideLoop: insideLoop);
+      }
+      return canBeInlined;
     }
 
     void doInlining(FunctionExpression functionExpression) {
       // Add an explicit null check on the receiver before doing the
       // inlining. We use [element] to get the same name in the
       // NoSuchMethodError message as if we had called it.
       if (element.isInstanceMember()
           && !element.isGenerativeConstructorBody()
           && (selector.mask == null || selector.mask.isNullable)) {
         addWithPosition(
@@ skipping 11 matching lines @@
         });
         element.isGenerativeConstructor()
             ? buildFactory(element)
             : functionExpression.body.accept(this);
       });
       leaveInlinedMethod(state);
     }
 
     if (meetsHardConstraints()) {
       FunctionExpression functionExpression = function.parseNode(compiler);
-      TreeElements newElements =
-          compiler.enqueuer.resolution.getCachedElements(function);
-      if (newElements == null) {
-        compiler.internalError("Element not resolved: $function");
-      }
 
-      if (heuristicsSayGoodToGo(functionExpression, newElements)) {
+      if (heuristicSayGoodToGo(functionExpression)) {
         doInlining(functionExpression);
         return true;
       }
     }
 
     return false;
   }
 
   inlinedFrom(Element element, f()) {
     assert(element is FunctionElement || element is VariableElement);
@@ skipping 3791 matching lines @@
     builder.add(instruction);
     return instruction;
   }
 }
 
 /**
  * This class visits the method that is a candidate for inlining and
  * finds whether it is too difficult to inline.
  */
 class InlineWeeder extends Visitor {
-  final TreeElements elements;
-
   bool seenReturn = false;
   bool tooDifficult = false;
   int nodeCount = 0;
+  int maxInliningNodes;

[ngeoffray, 2013/07/16 08:04:45]

final

[kustermann, 2013/07/16 13:27:50]

Done.

 
-  InlineWeeder(this.elements);
+  InlineWeeder(this.maxInliningNodes);
 
   static bool canBeInlined(FunctionExpression functionExpression,
-                           TreeElements elements) {
-    InlineWeeder weeder = new InlineWeeder(elements);
+                           int maxInliningNodes) {
+    InlineWeeder weeder = new InlineWeeder(maxInliningNodes);
     weeder.visit(functionExpression.initializers);
     weeder.visit(functionExpression.body);
-    if (weeder.tooDifficult) return false;
-    return true;
+    return !weeder.tooDifficult;
   }
 
   bool registerNode() {
-    if (nodeCount++ > SsaBuilder.MAX_INLINING_NODES) {
+    if (nodeCount++ > maxInliningNodes) {
       tooDifficult = true;
       return false;
     } else {
       return true;
     }
   }
 
   void visit(Node node) {
     if (node != null) node.accept(this);
   }
@@ skipping 310 matching lines @@
           new HSubGraphBlockInformation(elseBranch.graph));
 
     HBasicBlock conditionStartBlock = conditionBranch.block;
     conditionStartBlock.setBlockFlow(info, joinBlock);
     SubGraph conditionGraph = conditionBranch.graph;
     HIf branch = conditionGraph.end.last;
     assert(branch is HIf);
     branch.blockInformation = conditionStartBlock.blockFlow;
   }
 }