pkg/compiler/lib/src/tree_ir/optimization/loop_rewriter.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.

library tree_ir.optimization.loop_rewriter;

import 'optimization.dart' show Pass;
import '../tree_ir_nodes.dart';

/// Rewrites [WhileTrue] statements into [For] statements.
///
/// Before this phase, loops usually contain a lot of "exit code", that is,
/// code that happens at a point where a [Continue] can no longer be reached,
/// and is therefore not really part of the loop.
/// Exit code is moved down after the loop using the following rewrites rules:
///
/// EXTRACT LABELED STATEMENT:
///
///   L:
///   while (true) {
///     L2: {
///       S1  (has references to L)
///     }
///     S2    (has no references to L)
///   }
///
///     ==>
///
///   L2: {
///     L: while (true) S1
///   }
///   S2
///
/// INTRODUCE CONDITIONAL LOOP:
///
///   L:
///   while (true) {
///     if (E) {
///       S1  (has references to L)
///     } else {
///       S2  (has no references to L)
///     }
///   }
///     ==>
///   L:
///   while (E) {
///     S1
///   };
///   S2
///
/// A similar transformation is used when S2 occurs in the 'then' position.
///
/// Note that the pattern above needs no iteration since nested ifs have been
/// collapsed previously in the [StatementRewriter] phase.
///
///
/// PULL INTO UPDATE EXPRESSION:
///
/// Assignment expressions before the unique continue to a [whileCondition] are
/// pulled into the updates for the loop.
///
///   L:
///   for (; condition; updates) {
///     S [ x = E; continue L ]
///   }
///     ==>
///   L:
///   for (; condition; updates, x = E) {
///     S [ continue L ]
///   }
///
/// The decision to only pull in assignments is a heuristic to balance
/// readability and stack trace usability versus the modest code size
/// reduction one might get by aggressively moving expressions into the
/// updates.
class LoopRewriter extends RecursiveTransformer implements Pass {
  String get passName => 'Loop rewriter';

  Set<Label> usedContinueLabels = new Set<Label>();

  /// Maps loop labels to a list, if that loop can accept update expressions.
  /// The list will then be populated while traversing the body of that loop.
  /// If a loop is not in the map, update expressions cannot be hoisted there.
  Map<Label, List<Expression>> updateExpressions = <Label, List<Expression>>{};

  void rewrite(FunctionDefinition root) {
    root.body = visitStatement(root.body);
  }

  Statement visitContinue(Continue node) {
    usedContinueLabels.add(node.target);
    return node;
  }

  Statement visitWhileTrue(WhileTrue node) {
    assert(!usedContinueLabels.contains(node.label));

    // Pull labeled statements outside the loop when possible.
    // [head] and [tail] are the first and last labeled statements that were
    // pulled out, and null when none have been pulled out.
    LabeledStatement head, tail;
    while (node.body is LabeledStatement) {
      LabeledStatement inner = node.body;
      inner.next = visitStatement(inner.next);
      bool nextHasContinue = usedContinueLabels.remove(node.label);
      if (nextHasContinue) break;
      node.body = inner.body;
      inner.body = node;
      if (head == null) {
        head = tail = inner;
      } else {
        tail.body = inner;
        tail = inner;
      }
    }

    // Rewrite while(true) to for(; condition; updates).
    Statement loop = node;
    if (node.body is If) {
      If body = node.body;
      updateExpressions[node.label] = <Expression>[];
      body.thenStatement = visitStatement(body.thenStatement);
      bool thenHasContinue = usedContinueLabels.remove(node.label);
      body.elseStatement = visitStatement(body.elseStatement);
      bool elseHasContinue = usedContinueLabels.remove(node.label);
      if (thenHasContinue && !elseHasContinue) {
        node.label.binding = null; // Prepare to rebind the label.
        loop = new For(
            node.label,
            body.condition,
            updateExpressions[node.label],
            body.thenStatement,
            body.elseStatement);
      } else if (!thenHasContinue && elseHasContinue) {
        node.label.binding = null;
        loop = new For(
            node.label,
            new Not(body.condition),
            updateExpressions[node.label],
            body.elseStatement,
            body.thenStatement);
      }
    } else if (node.body is LabeledStatement) {
      // If the body is a labeled statement, its .next has already been visited.
      LabeledStatement body = node.body;
      body.body = visitStatement(body.body);
      usedContinueLabels.remove(node.label);
    } else {
      node.body = visitStatement(node.body);
      usedContinueLabels.remove(node.label);
    }

    if (head == null) return loop;
    tail.body = loop;
    return head;
  }

  Statement visitExpressionStatement(ExpressionStatement node) {
    if (updateExpressions.isEmpty) {
      // Avoid allocating a list if there is no loop.
      return super.visitExpressionStatement(node);
    }
    List<ExpressionStatement> statements = <ExpressionStatement>[];
    while (node.next is ExpressionStatement) {
      statements.add(node);
      node = node.next;
    }
    statements.add(node);
    Statement next = visitStatement(node.next);
    if (next is Continue && next.target.useCount == 1) {
      List<Expression> updates = updateExpressions[next.target];
      if (updates != null) {
        // Pull expressions before the continue into the for loop update.
        // As a heuristic, we only pull in assignment expressions.
        // Determine the index of the first assignment to pull in.
        int index = statements.length;
        while (index > 0 && statements[index - 1].expression is Assign) {
          --index;
        }
        for (ExpressionStatement stmt in statements.skip(index)) {
          updates.add(stmt.expression);
        }
        if (index > 0) {
          statements[index - 1].next = next;
          return statements.first;
        } else {
          return next;
        }
      }
    }
    // The expression statements could not be pulled into a loop update.
    node.next = next;
    return statements.first;
  }
}