Revert "dart2js: Initial implementation of inlining."

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

Index: pkg/compiler/lib/src/cps_ir/inline.dart
diff --git a/pkg/compiler/lib/src/cps_ir/inline.dart b/pkg/compiler/lib/src/cps_ir/inline.dart
deleted file mode 100644
index 0e37570cdabce4bf1c96e795819c17ea695ceb4a..0000000000000000000000000000000000000000
--- a/pkg/compiler/lib/src/cps_ir/inline.dart
+++ /dev/null
@@ -1,495 +0,0 @@
-// 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_nodes.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 '../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 {
-  static const int ABSENT = -1;
-  static const int NO_INLINE = 0;
-
-  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();
-
-  void _putInternal(ExecutableElement element, CallStructure callStructure,
-      TypeMask receiver,
-      List<TypeMask> arguments,
-      bool decision,
-      FunctionDefinition function) {
-    map.putIfAbsent(element, () => <CacheEntry>[])
-        .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.
-  ///
-  /// A positive lookup result return the IR function definition.  A negative
-  /// lookup result returns [NO_INLINE].  If there is no cached result,
-  /// [ABSENT] is returned.
-  get(ExecutableElement element, CallStructure callStructure, TypeMask receiver,
-      List<TypeMask> arguments) {
-    List<CacheEntry> entries = map[element];
-    if (entries != null) {
-      for (CacheEntry entry in entries) {
-        if (entry.match(callStructure, receiver, arguments)) {
-          if (entry.decision) {
-            FunctionDefinition function = copier.copy(entry.function);
-            ParentVisitor.setParents(function);
-            return function;
-          }
-          return NO_INLINE;
-        }
-      }
-    }
-    return ABSENT;
-  }
-}
-
-class Inliner implements Pass {
-  get passName => 'Inline calls';
-
-  final CpsFunctionCompiler functionCompiler;
-
-  final InliningCache cache = new InliningCache();
-
-  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 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;
-}
-
-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.
-  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.Intercepted ||
-        node.callingConvention == CallingConvention.DummyIntercepted) {
-      ++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.
-    if (!target.hasNode) return null;
-    if (target.asyncMarker != AsyncMarker.SYNC) return null;
-
-    Reference<Primitive> dartReceiver = invoke.dartReceiverReference;
-    TypeMask abstractReceiver =
-        dartReceiver == null ? null : abstractType(dartReceiver);
-    List<TypeMask> abstractArguments =
-        invoke.arguments.map(abstractType).toList();
-    var cachedResult = _inliner.cache.get(target, callStructure,
-        abstractReceiver,
-        abstractArguments);
-
-    // Negative inlining result in the cache.
-    if (cachedResult == InliningCache.NO_INLINE) return null;
-
-    // Positive inlining result in the cache.
-    if (cachedResult is FunctionDefinition) {
-      FunctionDefinition function = cachedResult;
-      _fragment = new CpsFragment(invoke.sourceInformation);
-      Primitive receiver = invoke.receiver?.definition;
-      List<Primitive> arguments =
-          invoke.arguments.map((Reference ref) => ref.definition).toList();
-      // Add a null check to the inlined function body if necessary.  The
-      // cached function body does not contain the null check.
-      if (dartReceiver != null && abstractReceiver.isNullable) {
-        Primitive check =
-            _fragment.letPrim(new NullCheck(dartReceiver.definition,
-                invoke.sourceInformation));
-        check.type = abstractReceiver.nonNullable();
-        if (invoke.callingConvention == CallingConvention.Intercepted) {
-          arguments[0] = check;
-        } else {
-          receiver = check;
-        }
-      }
-      return _fragment.inlineFunction(function, receiver, arguments,
-          hint: invoke.hint);
-    }
-
-    // We have not seen this combination of target and abstract arguments
-    // before.  Make an inlining decision.
-    assert(cachedResult == InliningCache.ABSENT);
-    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);
-    Primitive receiver = invoke.receiver?.definition;
-    List<Primitive> arguments =
-        invoke.arguments.map((Reference ref) => ref.definition).toList();
-    if (dartReceiver != null && abstractReceiver.isNullable) {
-      Primitive check =
-          _fragment.letPrim(new NullCheck(dartReceiver.definition,
-              invoke.sourceInformation));
-      check.type = abstractReceiver.nonNullable();
-      if (invoke.callingConvention == CallingConvention.Intercepted) {
-        arguments[0] = check;
-      } else {
-        receiver = check;
-      }
-    }
-    return _fragment.inlineFunction(function, receiver, arguments,
-        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);
-  }
-}