sdk/lib/_internal/compiler/implementation/cps_ir/redundant_phi.dart

// Copyright (c) 2014, 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 dart2js.optimizers;

/// Eliminate redundant phis from the given [FunctionDefinition].
///
/// Phis in this case are [Continuations] together with corresponding
/// [InvokeContinuation]s. A [Continuation] parameter at position i is redundant
/// if for all [InvokeContinuation]s, the parameter at position i is identical
/// (except for feedback). Redundant parameters are removed from the
/// continuation signature, all invocations, and replaced within the
/// continuation body.
class RedundantPhiEliminator extends RecursiveVisitor implements Pass {
  final Map<Continuation, List<InvokeContinuation>> cont2invokes =
      <Continuation, List<InvokeContinuation>>{};
  // For each reference r used in a continuation invocation i, stores the
  // corresponding continuation i.continuation. If required by other passes,
  // we could consider adding parent pointers to references instead.
  final Map<Reference, Continuation> ref2cont = <Reference, Continuation>{};
  final Set<Continuation> workSet = new Set<Continuation>();

  void rewrite(final FunctionDefinition root) {
    // Traverse the tree once to build the work set.
    visit(root);
    workSet.addAll(cont2invokes.keys);

    // Process each continuation one-by-one.
    while (workSet.isNotEmpty) {
      Continuation cont = workSet.first;
      workSet.remove(cont);

      if (cont.isReturnContinuation) {
        continue; // Skip function return continuations.
      }

      List<InvokeContinuation> invokes = cont2invokes[cont];
      assert(invokes != null);

      _processContinuation(cont, invokes);
    }
  }

  /// Called for each continuation on the work set, together with its
  /// invocations.
  void _processContinuation(Continuation cont,
                            List<InvokeContinuation> invokes) {
    /// Returns the unique definition of parameter i if it exists and null
    /// otherwise. A definition is unique if it is the only value used to
    /// invoke the continuation, excluding feedback.
    Definition uniqueDefinitionOf(int i) {
      Definition value = null;
      for (InvokeContinuation invoke in invokes) {
        Definition def = invoke.arguments[i].definition;

        if (cont.parameters[i] == def) {
          // Invocation param == param in LetCont (i.e. a recursive call).
          continue;
        } else if (value == null) {
          value = def; // Set initial comparison value.
        } else if (value != def) {
          return null; // Differing invocation arguments.
        }
      }

      return value;
    }

    // Check if individual parameters are always called with a unique
    // definition, and remove them if that is the case. During each iteration,
    // we read the current parameter/argument from index `src` and copy it
    // to index `dst`.
    int dst = 0;
    for (int src = 0; src < cont.parameters.length; src++) {
      // Is the current phi redundant?
      Definition uniqueDefinition = uniqueDefinitionOf(src);
      if (uniqueDefinition == null) {
        // Reorganize parameters and arguments in case of deletions.
        cont.parameters[dst] = cont.parameters[src];
        for (InvokeContinuation invoke in invokes) {
            invoke.arguments[dst] = invoke.arguments[src];
        }

        dst++;
        continue;
      }

      Definition oldDefinition = cont.parameters[src];

      // Add continuations of about-to-be modified invokes to worklist since
      // we might introduce new optimization opportunities.
      for (Reference ref = oldDefinition.firstRef; ref != null;
           ref = ref.next) {
        Continuation thatCont = ref2cont[ref];
        // thatCont is null if ref does not belong to a continuation invocation.
        if (thatCont != null && thatCont != cont) {
          workSet.add(thatCont);
        }
      }

      // Replace individual parameters:
      // * In the continuation body, replace occurrence of param with value,
      // * and implicitly remove param from continuation signature and
      //   invocations by not incrementing `dst`. References of removed
      //   arguments are unlinked to keep definition usages up to date.
      uniqueDefinition.substituteFor(oldDefinition);
      for (InvokeContinuation invoke in invokes) {
        invoke.arguments[src].unlink();
      }
    }

    // Remove trailing items from parameter and argument lists.
    cont.parameters.length = dst;
    for (InvokeContinuation invoke in invokes) {
      invoke.arguments.length = dst;
    }
  }

  void visitInvokeContinuation(InvokeContinuation node) {
    // Update the continuation map.
    Continuation cont = node.continuation.definition;
    assert(cont != null);
    cont2invokes.putIfAbsent(cont, () => <InvokeContinuation>[])
        .add(node);

    // And the reference map.
    node.arguments.forEach((Reference ref) {
      assert(!ref2cont.containsKey(ref));
      ref2cont[ref] = node.continuation.definition;
    });
  }
}