Linter Demo

Errors: 0

Warnings: 4

File: /home/fstrocco/Dart/dart/benchmark/compiler/lib/src/tree_ir/optimization/statement_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. part of tree_ir.optimization; /** * Performs the following transformations on the tree: * - Assignment propagation * - If-to-conditional conversion * - Flatten nested ifs * - Break inlining * - Redirect breaks * * The above transformations all eliminate statements from the tree, and may * introduce redexes of each other. * * * ASSIGNMENT PROPAGATION: * Single-use definitions are propagated to their use site when possible. * For example: * * { v0 = foo(); return v0; } * ==> * return foo() * * After translating out of CPS, all intermediate values are bound by [Assign]. * This transformation propagates such definitions to their uses when it is * safe and profitable. Bindings are processed "on demand" when their uses are * seen, but are only processed once to keep this transformation linear in * the size of the tree. * * The transformation builds an environment containing [Assign] bindings that * are in scope. These bindings have yet-untranslated definitions. When a use * is encountered the transformation determines if it is safe and profitable * to propagate the definition to its use. If so, it is removed from the * environment and the definition is recursively processed (in the * new environment at the use site) before being propagated. * * See [visitVariableUse] for the implementation of the heuristic for * propagating a definition. * * * IF-TO-CONDITIONAL CONVERSION: * If-statement are converted to conditional expressions when possible. * For example: * * if (v0) { v1 = foo(); break L } else { v1 = bar(); break L } * ==> * { v1 = v0 ? foo() : bar(); break L } * * This can lead to inlining of L, which in turn can lead to further propagation * of the variable v1. * * See [visitIf]. * * * FLATTEN NESTED IFS: * An if inside an if is converted to an if with a logical operator. * For example: * * if (E1) { if (E2) {S} else break L } else break L * ==> * if (E1 && E2) {S} else break L * * This may lead to inlining of L. * * * BREAK INLINING: * Single-use labels are inlined at [Break] statements. * For example: * * L0: { v0 = foo(); break L0 }; return v0; * ==> * v0 = foo(); return v0; * * This can lead to propagation of v0. * * See [visitBreak] and [visitLabeledStatement]. * * * REDIRECT BREAKS: * Labeled statements whose next is a break become flattened and all breaks * to their label are redirected. * For example, where 'jump' is either break or continue: * * L0: {... break L0 ...}; jump L1 * ==> * {... jump L1 ...} * * This may trigger a flattening of nested ifs in case the eliminated label * separated two ifs. */ class StatementRewriter extends Transformer implements Pass { String get passName => 'Statement rewriter'; @override void rewrite(RootNode node) { node.replaceEachBody(visitStatement); } // The binding environment. The rightmost element of the list is the nearest // available enclosing binding. List<Assign> environment = <Assign>[]; /// Binding environment for variables that are assigned to effectively /// constant expressions (see [isEffectivelyConstant]). final Map<Variable, Expression> constantEnvironment; /// Substitution map for labels. Any break to a label L should be substituted /// for a break to L' if L maps to L'. Map<Label, Jump> labelRedirects = <Label, Jump>{}; /// Rewriter for methods. StatementRewriter() : constantEnvironment = <Variable, Expression>{}; /// Rewriter for nested functions. StatementRewriter.nested(StatementRewriter parent) : constantEnvironment = parent.constantEnvironment; /// A set of labels that can be safely inlined at their use. /// /// The successor statements for labeled statements that have only one break /// from them are normally rewritten inline at the site of the break. This /// is not safe if the code would be moved inside the scope of an exception /// handler (i.e., if the code would be moved into a try from outside it). Set<Label> safeForInlining = new Set<Label>(); /// Returns the redirect target of [jump] or [jump] itself if it should not /// be redirected. Jump redirect(Jump jump) { Jump newJump = labelRedirects[jump.target]; return newJump != null ? newJump : jump; } void inEmptyEnvironment(void action()) { List<Assign> oldEnvironment = environment; environment = <Assign>[]; action(); assert(environment.isEmpty); environment = oldEnvironment; } Expression visitExpression(Expression e) => e.processed ? e : e.accept(this); @override Expression visitVariableUse(VariableUse node) { // Propagate constant to use site. Expression constant = constantEnvironment[node.variable]; if (constant != null) { --node.variable.readCount; return constant; } // Propagate a variable's definition to its use site if: // 1. It has a single use, to avoid code growth and potential duplication // of side effects, AND // 2. It was the most recent expression evaluated so that we do not // reorder expressions with side effects. if (!environment.isEmpty && environment.last.variable == node.variable && node.variable.readCount == 1) { --node.variable.readCount; return visitExpression(environment.removeLast().value); } // If the definition could not be propagated, leave the variable use. return node; } /// Returns true if [exp] has no side effects and has a constant value within /// any given activation of the enclosing method. bool isEffectivelyConstant(Expression exp) { // TODO(asgerf): Can be made more aggressive e.g. by checking conditional // expressions recursively. Determine if that is a valuable optimization // and/or if it is better handled at the CPS level. return exp is Constant || exp is This || exp is ReifyTypeVar || exp is VariableUse && constantEnvironment.containsKey(exp.variable); } Statement visitAssign(Assign node) { if (isEffectivelyConstant(node.value) && node.variable.writeCount == 1) { // Handle constant assignments specially. // They are always safe to propagate (though we should avoid duplication). // Moreover, they should not prevent other expressions from propagating. if (node.variable.readCount <= 1) { // A single-use constant should always be propagted to its use site. constantEnvironment[node.variable] = visitExpression(node.value); --node.variable.writeCount; return visitStatement(node.next); } else { // With more than one use, we cannot propagate the constant. // Visit the following statement without polluting [environment] so // that any preceding non-constant assignments might still propagate. node.next = visitStatement(node.next); node.value = visitExpression(node.value); return node; } } else { // Try to propagate assignment, and block previous assignment until this // has propagated. environment.add(node); Statement next = visitStatement(node.next); if (!environment.isEmpty && environment.last == node) { // The definition could not be propagated. Residualize the let binding. node.next = next; environment.removeLast(); node.value = visitExpression(node.value); return node; } assert(!environment.contains(node)); --node.variable.writeCount; // This assignment was removed. return next; } } Expression visitInvokeStatic(InvokeStatic node) { // Process arguments right-to-left, the opposite of evaluation order. for (int i = node.arguments.length - 1; i >= 0; --i) { node.arguments[i] = visitExpression(node.arguments[i]); } return node; } Expression visitInvokeMethod(InvokeMethod node) { for (int i = node.arguments.length - 1; i >= 0; --i) { node.arguments[i] = visitExpression(node.arguments[i]); } node.receiver = visitExpression(node.receiver); return node; } Expression visitInvokeMethodDirectly(InvokeMethodDirectly node) { for (int i = node.arguments.length - 1; i >= 0; --i) { node.arguments[i] = visitExpression(node.arguments[i]); } node.receiver = visitExpression(node.receiver); return node; } Expression visitInvokeConstructor(InvokeConstructor node) { for (int i = node.arguments.length - 1; i >= 0; --i) { node.arguments[i] = visitExpression(node.arguments[i]); } return node; } Expression visitConcatenateStrings(ConcatenateStrings node) { for (int i = node.arguments.length - 1; i >= 0; --i) { node.arguments[i] = visitExpression(node.arguments[i]); } return node; } Expression visitConditional(Conditional node) { node.condition = visitExpression(node.condition); inEmptyEnvironment(() { node.thenExpression = visitExpression(node.thenExpression); node.elseExpression = visitExpression(node.elseExpression); }); return node; } Expression visitLogicalOperator(LogicalOperator node) { node.left = visitExpression(node.left); // Impure expressions may not propagate across the branch. inEmptyEnvironment(() { node.right = visitExpression(node.right); }); return node; } Expression visitNot(Not node) { node.operand = visitExpression(node.operand); return node; } Expression visitFunctionExpression(FunctionExpression node) { new StatementRewriter.nested(this).rewrite(node.definition); return node; } Statement visitFunctionDeclaration(FunctionDeclaration node) { new StatementRewriter.nested(this).rewrite(node.definition); node.next = visitStatement(node.next); return node; } Statement visitReturn(Return node) { node.value = visitExpression(node.value); return node; } Statement visitBreak(Break node) { // Redirect through chain of breaks. // Note that useCount was accounted for at visitLabeledStatement. // Note redirect may return either a Break or Continue statement. Jump jump = redirect(node); if (jump is Break && jump.target.useCount == 1 && safeForInlining.contains(jump.target)) { --jump.target.useCount; return visitStatement(jump.target.binding.next); } return jump; } Statement visitContinue(Continue node) { return node; } Statement visitLabeledStatement(LabeledStatement node) { if (node.next is Jump) { // Eliminate label if next is a break or continue statement // Breaks to this label are redirected to the outer label. // Note that breakCount for the two labels is updated proactively here // so breaks can reliably tell if they should inline their target. Jump next = node.next; Jump newJump = redirect(next); labelRedirects[node.label] = newJump; newJump.target.useCount += node.label.useCount - 1; node.label.useCount = 0; Statement result = visitStatement(node.body); labelRedirects.remove(node.label); // Save some space. return result; } safeForInlining.add(node.label); node.body = visitStatement(node.body); safeForInlining.remove(node.label); if (node.label.useCount == 0) { // Eliminate the label if next was inlined at a break return node.body; } // Do not propagate assignments into the successor statements, since they // may be overwritten by assignments in the body. inEmptyEnvironment(() { node.next = visitStatement(node.next); }); return node; } Statement visitIf(If node) { node.condition = visitExpression(node.condition); // Do not propagate assignments into branches. Doing so will lead to code // duplication. // TODO(kmillikin): Rethink this. Propagating some assignments // (e.g. variables) is benign. If they can occur here, they should // be handled well. inEmptyEnvironment(() { node.thenStatement = visitStatement(node.thenStatement); node.elseStatement = visitStatement(node.elseStatement); }); tryCollapseIf(node); Statement reduced = combineStatementsWithSubexpressions( node.thenStatement, node.elseStatement, (t,f) => new Conditional(node.condition, t, f)..processed = true); if (reduced != null) { // TODO(asgerf): Avoid revisiting nodes or visiting nodes that we created. // This breaks the assumption that all subexpressions are // variable uses, and it can be expensive. // Revisit in case the break can now be inlined. return visitStatement(reduced); } return node; } Statement visitWhileTrue(WhileTrue node) { // Do not propagate assignments into loops. Doing so is not safe for // variables modified in the loop (the initial value will be propagated). inEmptyEnvironment(() { node.body = visitStatement(node.body); }); return node; } Statement visitWhileCondition(WhileCondition node) { // Not introduced yet throw "Unexpected WhileCondition in StatementRewriter"; } Statement visitTry(Try node) { inEmptyEnvironment(() { Set<Label> saved = safeForInlining; safeForInlining = new Set<Label>(); node.tryBody = visitStatement(node.tryBody); safeForInlining = saved; node.catchBody = visitStatement(node.catchBody); }); return node; } Expression visitConstant(Constant node) { return node; } Expression visitThis(This node) { return node; } Expression visitReifyTypeVar(ReifyTypeVar node) { return node; } Expression visitLiteralList(LiteralList node) { // Process values right-to-left, the opposite of evaluation order. for (int i = node.values.length - 1; i >= 0; --i) { node.values[i] = visitExpression(node.values[i]); } return node; } Expression visitLiteralMap(LiteralMap node) { // Process arguments right-to-left, the opposite of evaluation order. for (LiteralMapEntry entry in node.entries.reversed) { entry.value = visitExpression(entry.value); entry.key = visitExpression(entry.key); } return node; } Expression visitTypeOperator(TypeOperator node) { node.receiver = visitExpression(node.receiver); return node; } Statement visitExpressionStatement(ExpressionStatement node) { node.expression = visitExpression(node.expression); // Do not allow propagation of assignments past an expression evaluated // for its side effects because it risks reordering side effects. // TODO(kmillikin): Rethink this. Some propagation is benign, // e.g. variables, or other pure values that are not destroyed by // the expression statement. If they can occur here they should be // handled well. inEmptyEnvironment(() { node.next = visitStatement(node.next); }); return node; } Statement visitSetField(SetField node) { node.next = visitStatement(node.next); node.value = visitExpression(node.value); node.object = visitExpression(node.object); return node; } Expression visitGetField(GetField node) { node.object = visitExpression(node.object); return node; } Expression visitCreateBox(CreateBox node) { return node; } Expression visitCreateInstance(CreateInstance node) { for (int i = node.arguments.length - 1; i >= 0; --i) { node.arguments[i] = visitExpression(node.arguments[i]); } return node; } Expression visitReifyRuntimeType(ReifyRuntimeType node) { node.value = visitExpression(node.value); return node; } Expression visitReadTypeVariable(ReadTypeVariable node) { node.target = visitExpression(node.target); return node; } @override Expression visitTypeExpression(TypeExpression node) { for (int i = node.arguments.length - 1; i >= 0; --i) { node.arguments[i] = visitExpression(node.arguments[i]); } return node; } /// If [s] and [t] are similar statements we extract their subexpressions /// and returns a new statement of the same type using expressions combined /// with the [combine] callback. For example: /// /// combineStatements(Return E1, Return E2) = Return combine(E1, E2) /// /// If [combine] returns E1 then the unified statement is equivalent to [s], /// and if [combine] returns E2 the unified statement is equivalence to [t]. /// /// It is guaranteed that no side effects occur between the beginning of the /// statement and the position of the combined expression. /// /// Returns null if the statements are too different. /// /// If non-null is returned, the caller MUST discard [s] and [t] and use /// the returned statement instead. static Statement combineStatementsWithSubexpressions( Statement s, Statement t, Expression combine(Expression s, Expression t)) { if (s is Return && t is Return) { return new Return(combine(s.value, t.value)); } if (s is Assign && t is Assign && s.variable == t.variable) { Statement next = combineStatements(s.next, t.next); if (next != null) { // Destroy both original assignments to the variable. --s.variable.writeCount; --t.variable.writeCount; // The Assign constructor will increment the reference count again. return new Assign(s.variable, combine(s.value, t.value), next); } } if (s is ExpressionStatement && t is ExpressionStatement) { Statement next = combineStatements(s.next, t.next); if (next != null) { return new ExpressionStatement(combine(s.expression, t.expression), next); } } return null; } /// Returns a statement equivalent to both [s] and [t], or null if [s] and /// [t] are incompatible. /// If non-null is returned, the caller MUST discard [s] and [t] and use /// the returned statement instead. /// If two breaks are combined, the label's break counter will be decremented. static Statement combineStatements(Statement s, Statement t) { if (s is Break && t is Break && s.target == t.target) { --t.target.useCount; // Two breaks become one. return s; } if (s is Continue && t is Continue && s.target == t.target) { --t.target.useCount; // Two continues become one. return s; } if (s is Return && t is Return) { Expression e = combineExpressions(s.value, t.value); if (e != null) { return new Return(e); } } if (s is Assign && t is Assign && s.variable == t.variable && isSameVariable(s.value, t.value)) { Statement next = combineStatements(s.next, t.next); if (next != null) { s.next = next; --t.variable.writeCount; --(t.value as VariableUse).variable.readCount; return s; } } return null; } /// Returns an expression equivalent to both [e1] and [e2]. /// If non-null is returned, the caller must discard [e1] and [e2] and use /// the resulting expression in the tree. static Expression combineExpressions(Expression e1, Expression e2) { if (e1 is VariableUse && e2 is VariableUse && e1.variable == e2.variable) { --e1.variable.readCount; // Two references become one. return e1; } if (e1 is Constant && e2 is Constant && e1.value == e2.value) { return e1; } return null; } /// Try to collapse nested ifs using && and || expressions. /// For example: /// /// if (E1) { if (E2) S else break L } else break L /// ==> /// if (E1 && E2) S else break L /// /// [branch1] and [branch2] control the position of the S statement. /// /// Returns true if another collapse redex might have been introduced. void tryCollapseIf(If node) { // Repeatedly try to collapse nested ifs. // The transformation is shrinking (destroys an if) so it remains linear. // Here is an example where more than one iteration is required: // // if (E1) // if (E2) break L2 else break L1 // else // break L1 // // L1.target ::= // if (E3) S else break L2 // // After first collapse: // // if (E1 && E2) // break L2 // else // {if (E3) S else break L2} (inlined from break L1) // // We can then do another collapse using the inlined nested if. bool changed = true; while (changed) { changed = false; if (tryCollapseIfAux(node, true, true)) { changed = true; } if (tryCollapseIfAux(node, true, false)) { changed = true; } if (tryCollapseIfAux(node, false, true)) { changed = true; } if (tryCollapseIfAux(node, false, false)) { changed = true; } } } bool tryCollapseIfAux(If outerIf, bool branch1, bool branch2) { // NOTE: We name variables here as if S is in the then-then position. Statement outerThen = getBranch(outerIf, branch1); Statement outerElse = getBranch(outerIf, !branch1); if (outerThen is If) { If innerIf = outerThen; Statement innerThen = getBranch(innerIf, branch2); Statement innerElse = getBranch(innerIf, !branch2); Statement combinedElse = combineStatements(innerElse, outerElse); if (combinedElse != null) { // We always put S in the then branch of the result, and adjust the // condition expression if S was actually found in the else branch(es). outerIf.condition = new LogicalOperator.and( makeCondition(outerIf.condition, branch1), makeCondition(innerIf.condition, branch2)); outerIf.thenStatement = innerThen; // Try to inline the remaining break. Do not propagate assignments. inEmptyEnvironment(() { // TODO(asgerf): Avoid quadratic cost from repeated processing. This // should be easier after we introduce basic blocks. outerIf.elseStatement = visitStatement(combinedElse); }); return outerIf.elseStatement is If; } } return false; } static bool isSameVariable(Expression e1, Expression e2) { return e1 is VariableUse && e2 is VariableUse && e1.variable == e2.variable; } Expression makeCondition(Expression e, bool polarity) { return polarity ? e : new Not(e); } Statement getBranch(If node, bool polarity) { return polarity ? node.thenStatement : node.elseStatement; } }