dart2js: Initial implementation of inlining.

pkg/compiler/lib/src/cps_ir/inline.dart

+// Copyright (c) 2015, 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.
+
+library cps_ir.optimization.inline;
+
+import 'cps_fragment.dart';
+import 'cps_ir_builder.dart' show ThisParameterLocal;
+import 'cps_ir_integrity.dart' show CheckCpsIntegrity;
+import 'cps_ir_nodes.dart';
+import 'cps_ir_nodes_sexpr.dart';
+import 'optimizers.dart';
+import 'type_mask_system.dart' show TypeMaskSystem;
+import '../compiler.dart' show Compiler;
+import '../dart_types.dart' show DartType, GenericType;
+import '../io/source_information.dart' show SourceInformation;
+import '../world.dart' show World;
+import '../constants/values.dart' show ConstantValue;
+import '../diagnostics/invariant.dart' show DEBUG_MODE;
+import '../elements/elements.dart';
+import '../js_backend/js_backend.dart' show JavaScriptBackend;
+import '../js_backend/codegen/task.dart' show CpsFunctionCompiler;
+import '../types/types.dart' show
+    FlatTypeMask, ForwardingTypeMask, TypeMask, UnionTypeMask;
+import '../universe/call_structure.dart' show CallStructure;
+import '../universe/selector.dart' show Selector;
+
+/// Inlining stack entries.
+///
+/// During inlining, a stack is used to detect cycles in the call graph.
+class StackEntry {
+  // Dynamically resolved calls might be targeting an adapter function that
+  // fills in optional arguments not passed at the call site.  Therefore these
+  // calls are represented by the eventual target and the call structure at
+  // the call site, which together identify the target.  Statically resolved
+  // calls are represented by the target element and a null call structure.
+  final ExecutableElement target;
+  final CallStructure callStructure;
+
+  StackEntry(this.target, this.callStructure);
+
+  bool match(ExecutableElement otherTarget, CallStructure otherCallStructure) {
+    if (target != otherTarget) return false;
+    if (callStructure == null) return otherCallStructure == null;
+    return otherCallStructure != null &&
+        callStructure.match(otherCallStructure);
+  }
+}
+
+/// Inlining cache entries.
+class CacheEntry {
+  // The cache maps a function element to a list of entries, where each entry
+  // is a tuple of (call structure, abstract receiver, abstract arguments)
+  // along with the inlining decision and optional IR function definition.
+  final CallStructure callStructure;
+  final TypeMask receiver;
+  final List<TypeMask> arguments;
+
+  final bool decision;
+  final FunctionDefinition function;
+
+  CacheEntry(this.callStructure, this.receiver, this.arguments, this.decision,
+      this.function);
+
+  bool match(CallStructure otherCallStructure, TypeMask otherReceiver,
+      List<TypeMask> otherArguments) {
+    if (callStructure == null) {
+      if (otherCallStructure != null) return false;
+    } else if (otherCallStructure == null ||
+               !callStructure.match(otherCallStructure)) {
+      return false;
+    }
+
+    if (receiver != otherReceiver) return false;
+    assert(arguments.length == otherArguments.length);
+    for (int i = 0; i < arguments.length; ++i) {
+      if (arguments[i] != otherArguments[i]) return false;
+    }
+    return true;
+  }
+}
+
+/// An inlining cache.
+///
+/// During inlining a cache is used to remember inlining decisions for shared
+/// parts of the call graph, to avoid exploring them more than once.
+///
+/// The cache maps a tuple of (function element, call structure,
+/// abstract receiver, abstract arguments) to a boolean inlining decision and
+/// an IR function definition if the decision is positive.
+class InliningCache {
+  final Map<ExecutableElement, List<CacheEntry>> map =
+      <ExecutableElement, List<CacheEntry>>{};
+
+  // When function definitions are put into or removed from the cache, they are
+  // copied because the compiler passes will mutate them.
+  final CopyingVisitor copier = new CopyingVisitor();
+
+  bool shouldInline = false;
+  bool shouldNotInline = false;
+  FunctionDefinition function = null;
+
+  void _putInternal(ExecutableElement element, CallStructure callStructure,
+      TypeMask receiver,
+      List<TypeMask> arguments,
+      bool decision,
+      FunctionDefinition function) {
+    List<CacheEntry> entries = map[element];
+    if (entries == null) {
+      map[element] = entries = <CacheEntry>[];
+    }

[sra1, 2015/12/18 02:16:26]

map.putIfAbsent(element, () => <CacheEntry>())
  .add(...)

[Kevin Millikin (Google), 2015/12/21 12:28:03]

Done.

+    entries.add(new CacheEntry(callStructure, receiver, arguments, decision,
+        function));
+  }
+
+  /// Put a positive inlining decision in the cache.
+  ///
+  /// A positive inlining decision maps to an IR function definition.
+  void putPositive(ExecutableElement element, CallStructure callStructure,
+      TypeMask receiver,
+      List<TypeMask> arguments,
+      FunctionDefinition function) {
+    _putInternal(element, callStructure, receiver, arguments, true,
+        copier.copy(function));
+  }
+
+  /// Put a negative inlining decision in the cache.
+  void putNegative(ExecutableElement element,
+      CallStructure callStructure,
+      TypeMask receiver,
+      List<TypeMask> arguments) {
+    _putInternal(element, callStructure, receiver, arguments, false, null);
+  }
+
+  /// Look up a tuple in the cache.
+  ///
+  /// The result of the most recent lookup is available from the fields of the
+  /// cache:
+  ///   * A negative result sets [shouldNotInline] to true, [shouldInline] to
+  ///     false, and [function] to null.
+  ///   * A positive result sets [shouldInline] to true, [shouldNotInline] to
+  ///     true, and [function] to the IR function definition.
+  ///   * No cached result sets [shouldNotInline] and [shouldInline] to false,
+  ///     and [function] to null.
+  void get(ExecutableElement element, CallStructure callStructure,
+      Typemask receiver,
+      List<TypeMask> arguments) {

[asgerf, 2015/12/17 15:40:35]

This really ought to return something instead.

I think a mixed-type return value would be suitable here, e.g:
FunctionDefinition -> inline
false -> no inline
null -> undecided

Probably false and null should be replaced by some class constants so they're
not magical.

Btw the receiver seems to have type "Typemask" with lowercase m.

[Kevin Millikin (Google), 2015/12/21 12:28:03]

So it does.  I like how that's just OK.

I've changed it to return a value and gotten rid of the state variables.

+    List<CacheEntry> entries = map[element];
+    if (entries != null) {
+      for (CacheEntry entry in entries) {
+        if (entry.match(callStructure, receiver, arguments)) {
+          shouldInline = entry.decision;
+          shouldNotInline = !shouldInline;
+          if (shouldInline) {
+            function = copier.copy(entry.function);
+            ParentVisitor.setParents(function);
+          } else {
+            function = null;
+          }
+          return;
+        }
+      }
+    }
+
+    shouldInline = shouldNotInline = false;
+    function = null;
+    return;
+  }
+}
+
+class Inliner implements Pass {
+  get passName => 'Inline calls';
+
+  final CpsFunctionCompiler functionCompiler;
+
+  final InliningCache cache = new InliningCache();

[sra1, 2015/12/18 02:16:26]

FYI.

SSA has 'layered' inlining caches.
The main distinction is loop vs non-loop, 'layered' meaning if there is a hit in
the non-loop cache then we should definitely inline in the loop case.

Other distinctions that are useful:

error-path vs non-error-path:
Don't inline RangeError down to the allocator - it adds a lot of code for no
benefit

execute-once vs execute-many:
SSA is very conservative inlining in lazy static initializers. On some programs
this make a big difference. On one program that had many protobufs this saved
several percent in code size.
I'm sure we could identify other used-once code, e.g. main().

[Kevin Millikin (Google), 2015/12/21 12:28:02]

Acknowledged.

+
+  final List<StackEntry> stack = <StackEntry>[];
+
+  Inliner(this.functionCompiler);
+
+  bool isCalledOnce(Element element) {
+    return functionCompiler.compiler.typesTask.typesInferrer.isCalledOnce(
+        element);
+  }
+
+  void rewrite(FunctionDefinition node, [CallStructure callStructure]) {
+    Element function = node.element;
+
+    // Inlining in asynchronous or generator functions is disabled.  Inlining
+    // triggers a bug in the async rewriter.
+    // TODO(kmillikin): Fix the bug and eliminate this restriction if it makes
+    // sense.
+    if (function is FunctionElement &&
+        function.asyncMarker != AsyncMarker.SYNC) {
+      return;
+    }
+
+    stack.add(new StackEntry(function, callStructure));
+    new InliningVisitor(this).visit(node);
+    assert(stack.last.match(function, callStructure));
+    stack.removeLast();
+    new CheckCpsIntegrity().check(node, passName);

[asgerf, 2015/12/17 15:40:34]

Should not check integrity in production.

[Kevin Millikin (Google), 2015/12/21 12:28:03]

Oops, that's leftover debugging code.

+    new ShrinkingReducer().rewrite(node);
+  }
+}
+
+/// Compute an abstract size of an IR function definition.
+///
+/// The size represents the cost of inlining at a call site.
+class SizeVisitor extends TrampolineRecursiveVisitor {
+  int size = 0;
+
+  void countArgument(Reference<Primitive> argument, Parameter parameter) {
+    // If a parameter is unused and the corresponding argument has only the
+    // one use at the invocation, then inlining the call might enable
+    // elimination of the argument.  This 'pays for itself' by decreasing the
+    // cost of inlining at the call site.
+    if (argument != null &&
+        argument.definition.hasExactlyOneUse &&
+        parameter.hasNoUses) {
+      --size;
+    }
+  }
+
+  static int sizeOf(InvocationPrimitive invoke, FunctionDefinition function) {
+    SizeVisitor visitor = new SizeVisitor();
+    visitor.visit(function);
+    visitor.countArgument(invoke.receiver, function.thisParameter);
+    for (int i = 0; i < invoke.arguments.length; ++i) {
+      visitor.countArgument(invoke.arguments[i], function.parameters[i]);
+    }
+    return visitor.size;
+  }
+
+  // Inlining a function incurs a cost equal to the number of primitives and
+  // non-jump tail expressions.
+  // TODO(kmillikin): Tune the size computation and size bound.
+  processLetPrim(LetPrim node) => ++size;
+  processLetMutable(LetMutable node) => ++size;
+  processBranch(Branch node) => ++size;
+  processThrow(Throw nose) => ++size;
+  processRethrow(Rethrow node) => ++size;
+}
+
+String formatTypeMask(TypeMask type) {

[asgerf, 2015/12/17 15:40:34]

Leftover debugging code. Btw, what's wrong with TypeMask.toString()?

[sra1, 2015/12/18 02:16:26]

IMHO we should change the toString() for these types to be 'terms', e.g.
ContainerTypeMask(...)

[Kevin Millikin (Google), 2015/12/21 12:28:03]

Yeah, debugging code copied from another place.  TypeMask.toString() is random,
not guaranteed to work well in the S-expression representation (not that it
should, necessarily).  For example: 'null|exact=Object', where the | is
interpreted as a kind of bracket.

[Kevin Millikin (Google), 2015/12/21 12:28:03]

Agreed.

+  if (type is UnionTypeMask) {
+    return '[${type.disjointMasks.map(formatTypeMask).join(', ')}]';
+  } else if (type is FlatTypeMask) {
+    if (type.isEmpty) {
+      return "null";
+    }
+    String suffix = (type.isExact ? "" : "+") + (type.isNullable ? "?" : "!");
+    return '${type.base.name}$suffix';
+  } else if (type is ForwardingTypeMask) {
+    return formatTypeMask(type.forwardTo);
+  }
+  throw 'unsupported: $type';
+}
+
+String printType(nodeOrRef, String s) {

[asgerf, 2015/12/17 15:40:34]

More debugging code.

We should change the .toString methods on IR nodes and references to do
something more useful by default.

[Kevin Millikin (Google), 2015/12/21 12:28:02]

Agreed.

+  Node node = nodeOrRef is Reference ? nodeOrRef.definition : nodeOrRef;
+  return node is Variable && node.type != null
+      ? '$s:${formatTypeMask(node.type)}'
+      : s;
+}
+
+class InliningVisitor extends TrampolineRecursiveVisitor {
+  final Inliner _inliner;
+
+  // A successful inlining attempt returns the [Primitive] that represents the
+  // result of the inlined call or null.  If the result is non-null, the body
+  // of the inlined function is available in this field.
+  CpsFragment _fragment;
+
+  InliningVisitor(this._inliner);
+
+  JavaScriptBackend get backend => _inliner.functionCompiler.backend;
+  TypeMaskSystem get typeSystem => _inliner.functionCompiler.typeSystem;
+  World get world => _inliner.functionCompiler.compiler.world;
+
+  FunctionDefinition compileToCpsIr(AstElement element) {
+    return _inliner.functionCompiler.compileToCpsIr(element);
+  }
+
+  void optimizeBeforeInlining(FunctionDefinition function) {
+    _inliner.functionCompiler.optimizeCpsBeforeInlining(function);
+  }
+
+  void applyCpsPass(Pass pass, FunctionDefinition function) {
+    return _inliner.functionCompiler.applyCpsPass(pass, function);
+  }
+
+  bool isRecursive(Element target, CallStructure callStructure) {
+    return _inliner.stack.any((StackEntry s) => s.match(target, callStructure));
+  }
+
+  @override
+  Expression traverseLetPrim(LetPrim node) {
+    // A successful inlining attempt will set the node's body to null, so it is
+    // read before visiting the primitive.
+    Expression next = node.body;
+    Primitive replacement = visit(node.primitive);
+    if (replacement != null) {
+      node.primitive.replaceWithFragment(_fragment, replacement);
+    }
+    return next;
+  }
+
+  TypeMask abstractType(Reference<Primitive> ref) {
+    return ref.definition.type ?? typeSystem.dynamicType;
+  }
+
+  /// Build the IR term for the function that adapts a call site targeting a
+  /// function that takes optional arguments not passed at the call site.

[asgerf, 2015/12/17 15:40:34]

Not for this CL, but going forward maybe we should move this to the IR builder
and access it from here through the function compiler?

[Kevin Millikin (Google), 2015/12/21 12:28:03]

Agreed.  We actually have similar code in about four other places, but they each
end up doing something a bit different.

+  FunctionDefinition buildAdapter(InvokeMethod node, FunctionElement target) {
+    Parameter thisParameter = new Parameter(new ThisParameterLocal(target))
+        ..type = node.receiver.definition.type;
+    List<Parameter> parameters = new List<Parameter>.generate(
+        node.arguments.length,
+        (int index) {
+          // TODO(kmillikin): Use a hint for the parameter names.
+          return new Parameter(null)
+              ..type = node.arguments[index].definition.type;
+        });
+    Continuation returnContinuation = new Continuation.retrn();
+    CpsFragment cps = new CpsFragment();
+
+    FunctionSignature signature = target.functionSignature;
+    int requiredParameterCount = signature.requiredParameterCount;
+    if (node.callingConvention != CallingConvention.Normal) {

[asgerf, 2015/12/17 15:40:35]

Also missing a case for the new OneShotIntercepted calling convention (although
it can't occur this early in the pipeline).

Stephen suggested we make calling conventions into objects that can do some of
this work, or at least answer if it has an extra first argument.
Seems like we need this now (but also not for this CL).

[sra1, 2015/12/18 02:16:26]

I think we should have a separate interceptor, (dart)receiver and
(dart)arguments, uniform for every invoke.
Static calls are just missing the first two.
We can fix that later.

[Kevin Millikin (Google), 2015/12/21 12:28:02]

Acknowledged.

[Kevin Millikin (Google), 2015/12/21 12:28:02]

Acknowledged.

+      ++requiredParameterCount;
+    }
+    List<Primitive> arguments = new List<Primitive>.generate(
+        requiredParameterCount,
+        (int index) => parameters[index]);
+
+    int parameterIndex = requiredParameterCount;
+    CallStructure newCallStructure;
+    if (signature.optionalParametersAreNamed) {
+      List<String> incomingNames =
+          node.selector.callStructure.getOrderedNamedArguments();
+      List<String> outgoingNames = <String>[];
+      int nameIndex = 0;
+      signature.orderedOptionalParameters.forEach((ParameterElement formal) {
+        if (nameIndex < incomingNames.length &&
+            formal.name == incomingNames[nameIndex]) {
+          arguments.add(parameters[parameterIndex++]);
+          ++nameIndex;
+        } else {
+          Constant defaultValue = cps.makeConstant(
+              backend.constants.getConstantValueForVariable(formal));
+          defaultValue.type = typeSystem.getParameterType(formal);
+          arguments.add(defaultValue);
+        }
+        outgoingNames.add(formal.name);
+      });
+      newCallStructure =
+      new CallStructure(signature.parameterCount, outgoingNames);
+    } else {
+      signature.forEachOptionalParameter((ParameterElement formal) {
+        if (parameterIndex < parameters.length) {
+          arguments.add(parameters[parameterIndex++]);
+        } else {
+          Constant defaultValue = cps.makeConstant(
+              backend.constants.getConstantValueForVariable(formal));
+          defaultValue.type = typeSystem.getParameterType(formal);
+          arguments.add(defaultValue);
+        }
+      });
+      newCallStructure = new CallStructure(signature.parameterCount);
+    }
+
+    Selector newSelector =
+        new Selector(node.selector.kind, node.selector.memberName,
+            newCallStructure);
+    Primitive result = cps.invokeMethod(thisParameter, newSelector, node.mask,
+        arguments, node.callingConvention);
+    result.type = typeSystem.getInvokeReturnType(node.selector, node.mask);
+    cps.invokeContinuation(returnContinuation, <Primitive>[result]);
+    return new FunctionDefinition(target, thisParameter, parameters,
+        returnContinuation,
+        cps.root);
+  }
+
+  // Given an invocation and a known target, possibly perform inlining.
+  //
+  // An optional call structure indicates a dynamic call.  Calls that are
+  // already resolved statically have a null call structure.
+  //
+  // The [Primitive] representing the result of the inlined call is returned
+  // if the call was inlined, and the inlined function body is available in
+  // [_fragment].  If the call was not inlined, null is returned.
+  Primitive tryInlining(InvocationPrimitive invoke, FunctionElement target,
+                        CallStructure callStructure) {
+    // Quick checks: do not inline or even cache calls to targets without an
+    // AST node or targets that are asynchronous or generator functions.

[sra1, 2015/12/18 02:16:26]

I believe 'containing try-catch' is also trivially available.

[Kevin Millikin (Google), 2015/12/21 12:28:02]

Yeah, I planned on investigating what to do about try/catch as future work. 
These checks are for correctness of the implementation not performance.

+    if (!target.hasNode) return null;
+    if (target.asyncMarker != AsyncMarker.SYNC) return null;
+
+    TypeMask abstractReceiver =
+        invoke.receiver == null ? null : abstractType(invoke.receiver);

[sra1, 2015/12/18 02:16:26]

Should be the dartReceiver?

[Kevin Millikin (Google), 2015/12/21 12:28:03]

Yes, you are right.  That's a very dumb mistake that happened when I combined
separate code for static/instance functions.

+    List<TypeMask> abstractArguments =
+        invoke.arguments.map(abstractType).toList();
+    _inliner.cache.get(target, callStructure, abstractReceiver,
+        abstractArguments);
+
+    // Negative inlining result in the cache.
+    if (_inliner.cache.shouldNotInline) return null;
+
+    // Positive inlining result in the cache.
+    if (_inliner.cache.shouldInline) {
+      FunctionDefinition function = _inliner.cache.function;
+      _fragment = new CpsFragment(invoke.sourceInformation);
+      // Add a null check to the inlined function body if necessary.  The
+      // cached function body does not contain the null check.
+      if (invoke.receiver != null && abstractReceiver.isNullable) {
+        _fragment.letPrim(new NullCheck(invoke.receiver.definition,
+            invoke.sourceInformation));
+      }
+      return _fragment.inlineFunction(function, invoke.receiver?.definition,
+          invoke.arguments.map((Reference ref) => ref.definition).toList(),
+          hint: invoke.hint);
+    }
+
+    // We have not seen this combination of target and abstract arguments
+    // before.  Make an inlining decision.
+    Primitive doNotInline() {
+      _inliner.cache.putNegative(target, callStructure, abstractReceiver,
+          abstractArguments);
+      return null;
+    }
+    if (backend.annotations.noInline(target)) return doNotInline();
+    if (isRecursive(target, callStructure)) return doNotInline();
+
+    FunctionDefinition function;
+    if (callStructure != null &&
+        target.functionSignature.parameterCount !=
+            callStructure.argumentCount) {
+      // The argument count at the call site does not match the target's
+      // formal parameter count.  Build the IR term for an adapter function
+      // body.
+      function = buildAdapter(invoke, target);
+    } else {
+      function = _inliner.functionCompiler.compileToCpsIr(target);
+      void setValue(Variable variable, Reference<Primitive> value) {
+        variable.type = value.definition.type;
+      }
+      if (invoke.receiver != null) {
+        setValue(function.thisParameter, invoke.receiver);
+      }
+      for (int i = 0; i < invoke.arguments.length; ++i) {
+        setValue(function.parameters[i], invoke.arguments[i]);
+      }
+      optimizeBeforeInlining(function);
+    }
+
+    // Inline calls in the body.
+    _inliner.rewrite(function, callStructure);
+
+    // Compute the size.
+    // TODO(kmillikin): Tune the size bound.
+    int size = SizeVisitor.sizeOf(invoke, function);
+    if (!_inliner.isCalledOnce(target) && size > 11) return doNotInline();
+
+    _inliner.cache.putPositive(target, callStructure, abstractReceiver,
+        abstractArguments, function);
+    _fragment = new CpsFragment(invoke.sourceInformation);
+    if (invoke.receiver != null && abstractReceiver.isNullable) {
+      _fragment.letPrim(new NullCheck(invoke.receiver.definition,

[asgerf, 2015/12/17 15:40:34]

It seems for intercepted methods we generate a null check on the interceptor?

We should use the Dart receiver instead. Maybe add the dartReceiver getter to
InvocationPrimitive:

class InvocationPrimitive {
  Primitive get dartReceiver => receiver?.definition; // Overriden by
InvokeMethod
}

The NullCheck acts as a refinement node, so it would be better with something
like,

  receiver = letPrim(new NullCheck(receiver, ..)

so the refined receiver is used in the inlined body.

[sra1, 2015/12/18 02:16:26]

This is what I saw in generated code.

[Kevin Millikin (Google), 2015/12/21 12:28:02]

Done.

+          invoke.sourceInformation));
+    }
+    return _fragment.inlineFunction(function, invoke.receiver?.definition,
+        invoke.arguments.map((Reference ref) => ref.definition).toList(),
+        hint: invoke.hint);
+  }
+
+  @override
+  Primitive visitInvokeStatic(InvokeStatic node) {
+    return tryInlining(node, node.target, null);
+  }
+
+  @override
+  Primitive visitInvokeMethod(InvokeMethod node) {
+    Primitive receiver = node.dartReceiver;
+    Element element = world.locateSingleElement(node.selector, receiver.type);
+    if (element == null || element is! FunctionElement) return null;
+    if (node.selector.isGetter != element.isGetter) return null;
+    if (node.selector.isSetter != element.isSetter) return null;
+    if (node.selector.name != element.name) return null;
+
+    return tryInlining(node, element.asFunctionElement(),
+        node.selector.callStructure);
+  }
+
+  @override
+  Primitive visitInvokeMethodDirectly(InvokeMethodDirectly node) {
+    if (node.selector.isGetter != node.target.isGetter) return null;
+    if (node.selector.isSetter != node.target.isSetter) return null;
+    return tryInlining(node, node.target, null);
+  }
+
+  @override
+  Primitive visitInvokeConstructor(InvokeConstructor node) {
+    if (node.dartType is GenericType) {
+      // We cannot inline a constructor invocation containing type arguments
+      // because CreateInstance in the body does not know the type arguments.
+      // We would incorrectly instantiate a class like A instead of A<B>.
+      // TODO(kmillikin): try to fix this.
+      GenericType generic = node.dartType;
+      if (generic.typeArguments.any((DartType t) => !t.isDynamic)) return null;
+    }
+    return tryInlining(node, node.target, null);
+  }
+}