| // 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.mutable_ssa; |
| |
| import 'cps_ir_nodes.dart'; |
| import 'optimizers.dart'; |
| |
| /// Determines which mutable variables should be rewritten to phi assignments |
| /// in this pass. |
| /// |
| /// We do not rewrite variables that have an assignment inside a try block that |
| /// does not contain its declaration. |
| class MutableVariablePreanalysis extends RecursiveVisitor { |
| // Number of try blocks enclosing the current position. |
| int currentDepth = 0; |
| |
| /// Number of try blocks enclosing the declaration of a given mutable |
| /// variable. |
| /// |
| /// All mutable variables seen will be present in the map after the analysis. |
| Map<MutableVariable, int> variableDepth = <MutableVariable, int>{}; |
| |
| /// Variables with an assignment inside a try block that does not contain |
| /// its declaration. |
| Set<MutableVariable> hasAssignmentInTry = new Set<MutableVariable>(); |
| |
| @override |
| Expression traverseLetHandler(LetHandler node) { |
| push(node.handler); |
| ++currentDepth; |
| pushAction(() => --currentDepth); |
| return node.body; |
| } |
| |
| void processLetMutable(LetMutable node) { |
| variableDepth[node.variable] = currentDepth; |
| } |
| |
| void processSetMutable(SetMutable node) { |
| MutableVariable variable = node.variable.definition; |
| if (currentDepth > variableDepth[variable]) { |
| hasAssignmentInTry.add(variable); |
| } |
| } |
| |
| /// True if there are no mutable variables or they are all assigned inside |
| /// a try block. In this case, there is nothing to do and the pass should |
| /// be skipped. |
| bool get allMutablesAreAssignedInTryBlocks { |
| return hasAssignmentInTry.length == variableDepth.length; |
| } |
| } |
| |
| /// Replaces mutable variables with continuation parameters, effectively |
| /// bringing them into SSA form. |
| /// |
| /// This pass is intended to clean up mutable variables that were introduced |
| /// by an optimization in the type propagation pass. |
| /// |
| /// This implementation potentially creates a lot of redundant and dead phi |
| /// parameters. These will be cleaned up by redundant phi elimination and |
| /// shrinking reductions. |
| /// |
| /// Discussion: |
| /// For methods with a lot of mutable variables, creating all the spurious |
| /// parameters might be too expensive. If this is the case, we should |
| /// improve this pass to avoid most spurious parameters in practice. |
| class MutableVariableEliminator implements Pass { |
| String get passName => 'Mutable variable elimination'; |
| |
| /// Mutable variables currently in scope, in order of declaration. |
| /// This list determines the order of the corresponding phi parameters. |
| final List<MutableVariable> mutableVariables = <MutableVariable>[]; |
| |
| /// Number of phi parameters added to the given continuation. |
| final Map<Continuation, int> continuationPhiCount = <Continuation, int>{}; |
| |
| /// Stack of yet unprocessed continuations interleaved with the |
| /// mutable variables currently in scope. |
| /// |
| /// Continuations are processed when taken off the stack and mutable |
| /// variables fall out of scope (i.e. removed from [mutableVariables]) when |
| /// taken off the stack. |
| final List<StackItem> stack = <StackItem>[]; |
| |
| MutableVariablePreanalysis analysis; |
| |
| void rewrite(FunctionDefinition node) { |
| analysis = new MutableVariablePreanalysis()..visit(node); |
| if (analysis.allMutablesAreAssignedInTryBlocks) { |
| // Skip the pass if there is nothing to do. |
| return; |
| } |
| processBlock(node.body, <MutableVariable, Primitive>{}); |
| while (stack.isNotEmpty) { |
| StackItem item = stack.removeLast(); |
| if (item is ContinuationItem) { |
| processBlock(item.continuation.body, item.environment); |
| } else { |
| assert(item is VariableItem); |
| mutableVariables.removeLast(); |
| } |
| } |
| } |
| |
| bool shouldRewrite(MutableVariable variable) { |
| return !analysis.hasAssignmentInTry.contains(variable); |
| } |
| |
| bool isJoinContinuation(Continuation cont) { |
| return !cont.hasExactlyOneUse || |
| cont.firstRef.parent is InvokeContinuation; |
| } |
| |
| void removeNode(InteriorNode node) { |
| InteriorNode parent = node.parent; |
| parent.body = node.body; |
| node.body.parent = parent; |
| } |
| |
| /// If some useful source information is attached to exactly one of the |
| /// two definitions, the information is copied onto the other. |
| void mergeHints(MutableVariable variable, Primitive value) { |
| if (variable.hint == null) { |
| variable.hint = value.hint; |
| } else if (value.hint == null) { |
| value.hint = variable.hint; |
| } |
| } |
| |
| /// Processes a basic block, replacing mutable variable uses with direct |
| /// references to their values. |
| /// |
| /// [environment] is the current value of each mutable variable. The map |
| /// will be mutated during the processing. |
| /// |
| /// Continuations to be processed are put on the stack for later processing. |
| void processBlock(Expression node, |
| Map<MutableVariable, Primitive> environment) { |
| for (; node is! TailExpression; node = node.next) { |
| if (node is LetMutable && shouldRewrite(node.variable)) { |
| // Put the new mutable variable on the stack while processing the body, |
| // and pop it off again when done with the body. |
| mutableVariables.add(node.variable); |
| stack.add(new VariableItem()); |
| |
| // Put the initial value into the environment. |
| Primitive value = node.value.definition; |
| environment[node.variable] = value; |
| |
| // Preserve variable names. |
| mergeHints(node.variable, value); |
| |
| // Remove the mutable variable binding. |
| node.value.unlink(); |
| removeNode(node); |
| } else if (node is LetPrim && node.primitive is SetMutable) { |
| SetMutable setter = node.primitive; |
| MutableVariable variable = setter.variable.definition; |
| if (shouldRewrite(variable)) { |
| // As above, update the environment, preserve variables and remove |
| // the mutable variable assignment. |
| environment[variable] = setter.value.definition; |
| mergeHints(variable, setter.value.definition); |
| setter.value.unlink(); |
| removeNode(node); |
| } |
| } else if (node is LetPrim && node.primitive is GetMutable) { |
| GetMutable getter = node.primitive; |
| MutableVariable variable = getter.variable.definition; |
| if (shouldRewrite(variable)) { |
| // Replace with the reaching definition from the environment. |
| Primitive value = environment[variable]; |
| value.substituteFor(getter); |
| mergeHints(variable, value); |
| removeNode(node); |
| } |
| } else if (node is LetCont) { |
| // Create phi parameters for each join continuation bound here, and put |
| // them on the stack for later processing. |
| // Note that non-join continuations are handled at the use-site. |
| for (Continuation cont in node.continuations) { |
| if (!isJoinContinuation(cont)) continue; |
| // Create a phi parameter for every mutable variable in scope. |
| // At the same time, build the environment to use for processing |
| // the continuation (mapping mutables to phi parameters). |
| continuationPhiCount[cont] = mutableVariables.length; |
| Map<MutableVariable, Primitive> environment = |
| <MutableVariable, Primitive>{}; |
| for (MutableVariable variable in mutableVariables) { |
| Parameter phi = new Parameter(variable.hint); |
| cont.parameters.add(phi); |
| phi.parent = cont; |
| environment[variable] = phi; |
| } |
| stack.add(new ContinuationItem(cont, environment)); |
| } |
| } else if (node is LetHandler) { |
| // Process the catch block later and continue into the try block. |
| // We can use the same environment object for the try and catch blocks. |
| // The current environment bindings cannot change inside the try block |
| // because we exclude all variables assigned inside a try block. |
| // The environment might be extended with more bindings before we |
| // analyze the catch block, but that's ok. |
| stack.add(new ContinuationItem(node.handler, environment)); |
| } |
| } |
| |
| // Analyze the terminal node. |
| if (node is InvokeContinuation) { |
| Continuation cont = node.continuation.definition; |
| if (cont.isReturnContinuation) return; |
| // This is a call to a join continuation. Add arguments for the phi |
| // parameters that were added to this continuation. |
| int phiCount = continuationPhiCount[cont]; |
| for (int i = 0; i < phiCount; ++i) { |
| Primitive value = environment[mutableVariables[i]]; |
| Reference<Primitive> arg = new Reference<Primitive>(value); |
| node.arguments.add(arg); |
| arg.parent = node; |
| } |
| } else if (node is Branch) { |
| // Enqueue both branches with the current environment. |
| // Clone the environments once so the processing of one branch does not |
| // mutate the environment needed to process the other branch. |
| stack.add(new ContinuationItem( |
| node.trueContinuation.definition, |
| new Map<MutableVariable, Primitive>.from(environment))); |
| stack.add(new ContinuationItem( |
| node.falseContinuation.definition, |
| environment)); |
| } else { |
| assert(node is Throw || node is Unreachable); |
| } |
| } |
| } |
| |
| abstract class StackItem {} |
| |
| /// Represents a mutable variable that is in scope. |
| /// |
| /// The topmost mutable variable falls out of scope when this item is |
| /// taken off the stack. |
| class VariableItem extends StackItem {} |
| |
| /// Represents a yet unprocessed continuation together with the |
| /// environment in which to process it. |
| class ContinuationItem extends StackItem { |
| final Continuation continuation; |
| final Map<MutableVariable, Primitive> environment; |
| |
| ContinuationItem(this.continuation, this.environment); |
| } |