pkg/compiler/lib/src/cps_ir/share_interceptors.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 dart2js.cps_ir.share_interceptors;

import 'optimizers.dart';
import 'cps_ir_nodes.dart';
import 'loop_hierarchy.dart';
import '../constants/values.dart';

/// Removes redundant `getInterceptor` calls.
/// 
/// The pass performs three optimizations for interceptors:
///- pull interceptors out of loops
///- replace interceptors with constants
///- share interceptors when one is in scope of the other
class ShareInterceptors extends RecursiveVisitor implements Pass {
  String get passName => 'Share interceptors';

  /// The innermost loop containing a given primitive.
  final Map<Primitive, Continuation> loopHeaderFor =
      <Primitive, Continuation>{};

  /// An interceptor currently in scope for a given primitive.
  final Map<Primitive, Primitive> interceptorFor =
      <Primitive, Primitive>{};

  /// A primitive currently in scope holding a given interceptor constant.
  final Map<ConstantValue, Primitive> sharedConstantFor =
      <ConstantValue, Primitive>{};

  /// Interceptors to be hoisted out of the given loop.
  final Map<Continuation, List<Primitive>> loopHoistedInterceptors =
      <Continuation, List<Primitive>>{};

  LoopHierarchy loopHierarchy;
  Continuation currentLoopHeader;

  void rewrite(FunctionDefinition node) {
    loopHierarchy = new LoopHierarchy(node);
    visit(node.body);
  }

  @override
  Expression traverseContinuation(Continuation cont) {
    Continuation oldLoopHeader = currentLoopHeader;
    pushAction(() {
      currentLoopHeader = oldLoopHeader;
    });
    currentLoopHeader = loopHierarchy.getLoopHeader(cont);
    for (Parameter param in cont.parameters) {
      loopHeaderFor[param] = currentLoopHeader;
    }
    if (cont.isRecursive) {
      pushAction(() {
        // After the loop body has been processed, all interceptors hoisted
        // to this loop fall out of scope and should be removed from the
        // environment.
        List<Primitive> hoisted = loopHoistedInterceptors[cont];
        if (hoisted != null) {
          for (Primitive interceptor in hoisted) {
            if (interceptor is Interceptor) {
              Primitive input = interceptor.input.definition;
              assert(interceptorFor[input] == interceptor);
              interceptorFor.remove(input);
            } else if (interceptor is Constant) {
              assert(sharedConstantFor[interceptor.value] == interceptor);
              sharedConstantFor.remove(interceptor.value);
            } else {
              throw "Unexpected interceptor: $interceptor";
            }
          }
        }
      });
    }
    return cont.body;
  }

  @override
  Expression traverseLetPrim(LetPrim node) {
    loopHeaderFor[node.primitive] = currentLoopHeader;
    Expression next = node.body;
    if (node.primitive is! Interceptor) {
      return next;
    }
    Interceptor interceptor = node.primitive;
    Primitive input = interceptor.input.definition;

    // Try to reuse an existing interceptor for the same input.
    Primitive existing = interceptorFor[input];
    if (existing != null) {
      if (existing is Interceptor) {
        existing.interceptedClasses.addAll(interceptor.interceptedClasses);
      }
      existing.substituteFor(interceptor);
      interceptor.destroy();
      node.remove();
      return next;
    }

    // There is no interceptor obtained from this particular input, but
    // there might one obtained from another input that is known to
    // have the same result, so try to reuse that.
    InterceptorConstantValue constant = interceptor.constantValue;
    if (constant != null) {
      existing = sharedConstantFor[constant];
      if (existing != null) {
        existing.substituteFor(interceptor);
        interceptor.destroy();
        node.remove();
        return next;
      }

      // The interceptor could not be shared. Replace it with a constant.
      Constant constantPrim = new Constant(constant);
      node.primitive = constantPrim;
      constantPrim.hint = interceptor.hint;
      constantPrim.type = interceptor.type;
      constantPrim.substituteFor(interceptor);
      interceptor.destroy();
      sharedConstantFor[constant] = constantPrim;
    } else {
      interceptorFor[input] = interceptor;
    }

    // Determine the outermost loop where the input to the interceptor call
    // is available.  Constant interceptors take no input and can thus be
    // hoisted all way to the top-level.
    Continuation referencedLoop = constant != null
        ? null
        : lowestCommonAncestor(loopHeaderFor[input], currentLoopHeader);
    if (referencedLoop != currentLoopHeader) {
      // [referencedLoop] contains the binding for [input], so we cannot hoist
      // the interceptor outside that loop.  Find the loop nested one level
      // inside referencedLoop, and hoist the interceptor just outside that one.
      Continuation loop = currentLoopHeader;
      Continuation enclosing = loopHierarchy.getEnclosingLoop(loop);
      while (enclosing != referencedLoop) {
        assert(loop != null);
        loop = enclosing;
        enclosing = loopHierarchy.getEnclosingLoop(loop);
      }
      assert(loop != null);

      // Move the LetPrim above the loop binding.
      LetCont loopBinding = loop.parent;
      node.remove();
      node.insertAbove(loopBinding);

      // A different loop now contains the interceptor.
      loopHeaderFor[node.primitive] = enclosing;

      // Register the interceptor as hoisted to that loop, so it will be
      // removed from the environment when it falls out of scope.
      loopHoistedInterceptors
          .putIfAbsent(loop, () => <Primitive>[])
          .add(node.primitive);
    } else if (constant != null) {
      // The LetPrim was not hoisted. Remove the bound interceptor from the
      // environment when leaving the LetPrim body.
      pushAction(() {
        assert(sharedConstantFor[constant] == node.primitive);
        sharedConstantFor.remove(constant);
      });
    } else {
      pushAction(() {
        assert(interceptorFor[input] == node.primitive);
        interceptorFor.remove(input);
      });
    }
    return next;
  }

  /// Returns the the innermost loop that effectively encloses both
  /// c1 and c2 (or `null` if there is no such loop).
  Continuation lowestCommonAncestor(Continuation c1, Continuation c2) {
    int d1 = getDepth(c1), d2 = getDepth(c2);
    while (c1 != c2) {
      if (d1 <= d2) {
        c2 = loopHierarchy.getEnclosingLoop(c2);
        d2 = getDepth(c2);
      } else {
        c1 = loopHierarchy.getEnclosingLoop(c1);
        d1 = getDepth(c1);
      }
    }
    return c1;
  }

  int getDepth(Continuation loop) {
    if (loop == null) return -1;
    return loopHierarchy.loopDepth[loop];
  }
}