Inlining of static functions: applying Florian's CL.

lib/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.
 
 class Interceptors {
   Compiler compiler;
   Interceptors(Compiler this.compiler);
 
   SourceString mapOperatorToMethodName(Operator op) {
     String name = op.source.stringValue;
@@ skipping 819 matching lines @@
   SsaBuilder(SsaBuilderTask builder, WorkItem work)
     : this.builder = builder,
       this.work = work,
       interceptors = builder.interceptors,
       methodInterceptionEnabled = true,
       graph = new HGraph(),
       stack = new List<HInstruction>(),
       activationVariables = new Map<Element, HLocalValue>(),
       jumpTargets = new Map<TargetElement, JumpHandler>(),
       parameters = new Map<Element, HParameterValue>(),
+      inliningStack = <InliningState>[],
       super(work.resolutionTree) {
     localsHandler = new LocalsHandler(this);
   }
 
+  static final MAX_INLINING_DEPTH = 3;
+  static final MAX_INLINING_SOURCE_SIZE = 100;
+  List<InliningState> inliningStack;
+  Element returnElement = null;
+
   void disableMethodInterception() {
     assert(methodInterceptionEnabled);
     methodInterceptionEnabled = false;
   }
 
   void enableMethodInterception() {
     assert(!methodInterceptionEnabled);
     methodInterceptionEnabled = true;
   }
 
@@ skipping 39 matching lines @@
       TreeElements treeElements =
           compiler.resolver.resolveMethodElement(constructor);
       compiler.enqueuer.codegen.addToWorkList(bodyElement, treeElements);
       classElement.backendMembers =
           classElement.backendMembers.prepend(bodyElement);
     }
     assert(bodyElement.kind === ElementKind.GENERATIVE_CONSTRUCTOR_BODY);
     return bodyElement;
   }
 
+  InliningState enterInlinedMethod(PartialFunctionElement function,
+                                   Selector selector,
+                                   Link<Node> arguments) {
+    // Once we start to compile the arguments we must be sure that we don't
+    // abort.
+    List<HInstruction> compiledArguments = new List<HInstruction>();
+    bool succeeded = addStaticSendArgumentsToList(selector,
+                                                  arguments,
+                                                  function,
+                                                  compiledArguments);
+    assert(succeeded);
+
+    InliningState state =
+        new InliningState(function, returnElement, elements, stack);
+    inliningStack.add(state);
+    stack = <HInstruction>[];
+    returnElement = new Element(const SourceString("result"),
+                                ElementKind.VARIABLE,
+                                function);
+    localsHandler.updateLocal(returnElement, graph.addConstantNull());
+    elements = compiler.enqueuer.resolution.getCachedElements(function);
+    FunctionSignature signature = function.computeSignature(compiler);
+    int index = 0;
+    signature.forEachParameter((Element parameter) {
+      HInstruction argument = compiledArguments[index++];
+      localsHandler.updateLocal(parameter, argument);
+      potentiallyCheckType(argument, parameter);
+    });
+    return state;
+  }
+
+  void leaveInlinedMethod(InliningState state) {
+    InliningState poppedState = inliningStack.removeLast();
+    assert(state == poppedState);
+    elements = state.oldElements;
+    stack.add(localsHandler.readLocal(returnElement));
+    returnElement = state.oldReturnElement;
+    assert(stack.length == 1);
+    state.oldStack.add(stack[0]);
+    stack = state.oldStack;
+  }
+
+  bool tryInlineMethod(Element element,
+                       Selector selector,
+                       Link<Node> arguments) {
+    if (element.kind != ElementKind.FUNCTION) return false;
+    if (element is !PartialFunctionElement) return false;
+    if (inliningStack.length > MAX_INLINING_DEPTH) return false;
+    // Don't inline recursive calls. We use the same elements for the inlined
+    // functions and would thus clobber our local variables.
+    if (work.element == element) return false;
+    for (int i = 0; i < inliningStack.length; i++) {
+      if (inliningStack[i].function == element) return false;
+    }
+    // TODO(ngeoffray): Inlining currently does not work in the presence of

[kasperl, 2012/08/23 09:18:51]

I wonder if this restriction could be lifted. Maybe in another CL.

+    // private calls.
+    if (currentLibrary != element.getLibrary()) return false;
+    PartialFunctionElement function = element;
+    int sourceSize =
+        function.endToken.charOffset - function.beginToken.charOffset;
+    if (sourceSize > MAX_INLINING_SOURCE_SIZE) return false;
+    if (!selector.applies(function, compiler)) return false;
+    FunctionExpression functionExpression = function.parseNode(compiler);
+    TreeElements newElements =
+        compiler.enqueuer.resolution.getCachedElements(function);
+    if (newElements === null) {
+      compiler.internalError("Element not resolved: $function");
+    }
+    if (!InlineWeeder.canBeInlined(functionExpression, newElements)) {
+      return false;
+    }
+
+    InliningState state = enterInlinedMethod(function, selector, arguments);
+    functionExpression.body.accept(this);
+    leaveInlinedMethod(state);
+    return true;
+  }
+
   void inlineSuperOrRedirect(FunctionElement constructor,
                              Selector selector,
                              Link<Node> arguments,
                              List<FunctionElement> constructors,
                              Map<Element, HInstruction> fieldValues) {
     constructors.addLast(constructor);
 
     List<HInstruction> compiledArguments = new List<HInstruction>();
     bool succeeded = addStaticSendArgumentsToList(selector,
                                                   arguments,
@@ skipping 1443 matching lines @@
   }
 
   visitStaticSend(Send node) {
     Selector selector = elements.getSelector(node);
     Element element = elements[node];
     if (element === compiler.assertMethod && !compiler.enableUserAssertions) {
       stack.add(graph.addConstantNull());
       return;
     }
     compiler.ensure(element.kind !== ElementKind.GENERATIVE_CONSTRUCTOR);
+
+    if (tryInlineMethod(element, selector, node.arguments)) return;
+
     HInstruction target = new HStatic(element);
     add(target);
     var inputs = <HInstruction>[];
     inputs.add(target);
     if (element.kind == ElementKind.FUNCTION) {
       bool succeeded = addStaticSendArgumentsToList(selector, node.arguments,
                                                     element, inputs);
       if (!succeeded) {
         // TODO(ngeoffray): Match the VM behavior and throw an
         // exception at runtime.
@@ skipping 234 matching lines @@
       native.handleSsaNative(this, node.expression);
       return;
     }
     HInstruction value;
     if (node.expression === null) {
       value = graph.addConstantNull();
     } else {
       visit(node.expression);
       value = pop();
     }
-    close(attachPosition(new HReturn(value), node)).addSuccessor(graph.exit);
+    if (!inliningStack.isEmpty()) {
+      localsHandler.updateLocal(returnElement, value);
+    } else {
+      close(attachPosition(new HReturn(value), node)).addSuccessor(graph.exit);
+    }
   }
 
   visitThrow(Throw node) {
     if (node.expression === null) {
       HInstruction exception = rethrowableException;
       if (exception === null) {
         exception = graph.addConstantNull();
         compiler.reportError(node,
                              'throw without expression outside catch block');
       }
@@ skipping 783 matching lines @@
      node.visitChildren(this);
   }
 
   HInstruction concat(HInstruction left, HInstruction right) {
     HInstruction instruction = new HStringConcat(left, right, diagnosticNode);
     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 AbstractVisitor {
+  final TreeElements elements;
+  bool seenReturn = false;
+  bool tooDifficult = false;
+
+  InlineWeeder(this.elements);
+
+  static bool canBeInlined(FunctionExpression functionExpression,
+                           TreeElements elements) {
+    InlineWeeder weeder = new InlineWeeder(elements);
+    weeder.visit(functionExpression.body);
+    if (weeder.tooDifficult) return false;
+    return true;
+  }
+
+  void visit(Node node) {
+    node.accept(this);
+  }
+
+  void visitNode(Node node) {
+    if (seenReturn) {
+      tooDifficult = true;
+    } else {
+      node.visitChildren(this);
+    }
+  }
+
+  void visitFunctionExpression(Node node) {
+    tooDifficult = true;
+  }
+
+  void visitFunctionDeclaration(Node node) {
+    tooDifficult = true;
+  }
+
+  void visitSend(Node node) {
+    Element element = elements[node];
+    // Native methods rely on the names of the arguments. If we inline they
+    // could change.
+    if (!Element.isInvalid(element) && element.kind == ElementKind.FOREIGN) {
+      tooDifficult = true;
+    } else {
+      node.visitChildren(this);
+    }
+  }
+
+  visitLoop(Node node) {
+    node.visitChildren(this);
+    if (seenReturn) tooDifficult = true;
+  }
+
+  void visitReturn(Node node) {
+    if (seenReturn || node.getBeginToken().stringValue === 'native') {
+      tooDifficult = true;
+      return;
+    }
+    node.visitChildren(this);
+    seenReturn = true;
+  }
+
+  void visitTryStatement(Node node) {
+    tooDifficult = true;
+  }
+}
+
+class InliningState {
+  final PartialFunctionElement function;
+  final Element oldReturnElement;
+  final TreeElements oldElements;
+  final List<HInstruction> oldStack;
+
+  InliningState(this.function,
+                this.oldReturnElement,
+                this.oldElements,
+                this.oldStack);
+}
+
 class SsaBranch {
   final SsaBranchBuilder branchBuilder;
   final HBasicBlock block;
   LocalsHandler startLocals;
   LocalsHandler exitLocals;
   SubGraph graph;
 
   SsaBranch(this.branchBuilder) : block = new HBasicBlock();
 }
 
@@ skipping 212 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;
   }
 }