| OLD | NEW |
|---|
| (Empty) |
| 1 // Copyright (c) 2015, the Dart project authors. Please see the AUTHORS file | |
| 2 // for details. All rights reserved. Use of this source code is governed by a | |
| 3 // BSD-style license that can be found in the LICENSE file. | |
| 4 | |
| 5 library dart2js.cps_ir.mutable_ssa; | |
| 6 | |
| 7 import 'cps_ir_nodes.dart'; | |
| 8 import 'optimizers.dart'; | |
| 9 | |
| 10 /// Determines which mutable variables should be rewritten to phi assignments | |
| 11 /// in this pass. | |
| 12 /// | |
| 13 /// We do not rewrite variables that have an assignment inside a try block that | |
| 14 /// does not contain its declaration. | |
| 15 class MutableVariablePreanalysis extends TrampolineRecursiveVisitor { | |
| 16 // Number of try blocks enclosing the current position. | |
| 17 int currentDepth = 0; | |
| 18 | |
| 19 /// Number of try blocks enclosing the declaration of a given mutable | |
| 20 /// variable. | |
| 21 /// | |
| 22 /// All mutable variables seen will be present in the map after the analysis. | |
| 23 Map<MutableVariable, int> variableDepth = <MutableVariable, int>{}; | |
| 24 | |
| 25 /// Variables with an assignment inside a try block that does not contain | |
| 26 /// its declaration. | |
| 27 Set<MutableVariable> hasAssignmentInTry = new Set<MutableVariable>(); | |
| 28 | |
| 29 @override | |
| 30 Expression traverseLetHandler(LetHandler node) { | |
| 31 push(node.handler); | |
| 32 ++currentDepth; | |
| 33 pushAction(() => --currentDepth); | |
| 34 return node.body; | |
| 35 } | |
| 36 | |
| 37 void processLetMutable(LetMutable node) { | |
| 38 variableDepth[node.variable] = currentDepth; | |
| 39 } | |
| 40 | |
| 41 void processSetMutable(SetMutable node) { | |
| 42 MutableVariable variable = node.variable; | |
| 43 if (currentDepth > variableDepth[variable]) { | |
| 44 hasAssignmentInTry.add(variable); | |
| 45 } | |
| 46 } | |
| 47 | |
| 48 /// True if there are no mutable variables or they are all assigned inside | |
| 49 /// a try block. In this case, there is nothing to do and the pass should | |
| 50 /// be skipped. | |
| 51 bool get allMutablesAreAssignedInTryBlocks { | |
| 52 return hasAssignmentInTry.length == variableDepth.length; | |
| 53 } | |
| 54 } | |
| 55 | |
| 56 /// Replaces mutable variables with continuation parameters, effectively | |
| 57 /// bringing them into SSA form. | |
| 58 /// | |
| 59 /// This pass is intended to clean up mutable variables that were introduced | |
| 60 /// by an optimization in the type propagation pass. | |
| 61 /// | |
| 62 /// This implementation potentially creates a lot of redundant and dead phi | |
| 63 /// parameters. These will be cleaned up by redundant phi elimination and | |
| 64 /// shrinking reductions. | |
| 65 /// | |
| 66 /// Discussion: | |
| 67 /// For methods with a lot of mutable variables, creating all the spurious | |
| 68 /// parameters might be too expensive. If this is the case, we should | |
| 69 /// improve this pass to avoid most spurious parameters in practice. | |
| 70 class MutableVariableEliminator implements Pass { | |
| 71 String get passName => 'Mutable variable elimination'; | |
| 72 | |
| 73 /// Mutable variables currently in scope, in order of declaration. | |
| 74 /// This list determines the order of the corresponding phi parameters. | |
| 75 final List<MutableVariable> mutableVariables = <MutableVariable>[]; | |
| 76 | |
| 77 /// Number of phi parameters added to the given continuation. | |
| 78 final Map<Continuation, int> continuationPhiCount = <Continuation, int>{}; | |
| 79 | |
| 80 /// Stack of yet unprocessed continuations interleaved with the | |
| 81 /// mutable variables currently in scope. | |
| 82 /// | |
| 83 /// Continuations are processed when taken off the stack and mutable | |
| 84 /// variables fall out of scope (i.e. removed from [mutableVariables]) when | |
| 85 /// taken off the stack. | |
| 86 final List<StackItem> stack = <StackItem>[]; | |
| 87 | |
| 88 MutableVariablePreanalysis analysis; | |
| 89 | |
| 90 void rewrite(FunctionDefinition node) { | |
| 91 analysis = new MutableVariablePreanalysis()..visit(node); | |
| 92 if (analysis.allMutablesAreAssignedInTryBlocks) { | |
| 93 // Skip the pass if there is nothing to do. | |
| 94 return; | |
| 95 } | |
| 96 processBlock(node.body, <MutableVariable, Primitive>{}); | |
| 97 while (stack.isNotEmpty) { | |
| 98 StackItem item = stack.removeLast(); | |
| 99 if (item is ContinuationItem) { | |
| 100 processBlock(item.continuation.body, item.environment); | |
| 101 } else { | |
| 102 assert(item is VariableItem); | |
| 103 mutableVariables.removeLast(); | |
| 104 } | |
| 105 } | |
| 106 } | |
| 107 | |
| 108 bool shouldRewrite(MutableVariable variable) { | |
| 109 return !analysis.hasAssignmentInTry.contains(variable); | |
| 110 } | |
| 111 | |
| 112 bool isJoinContinuation(Continuation cont) { | |
| 113 return !cont.hasExactlyOneUse || cont.firstRef.parent is InvokeContinuation; | |
| 114 } | |
| 115 | |
| 116 /// If some useful source information is attached to exactly one of the | |
| 117 /// two definitions, the information is copied onto the other. | |
| 118 void mergeHints(MutableVariable variable, Primitive value) { | |
| 119 if (variable.hint == null) { | |
| 120 variable.hint = value.hint; | |
| 121 } else if (value.hint == null) { | |
| 122 value.hint = variable.hint; | |
| 123 } | |
| 124 } | |
| 125 | |
| 126 /// Processes a basic block, replacing mutable variable uses with direct | |
| 127 /// references to their values. | |
| 128 /// | |
| 129 /// [environment] is the current value of each mutable variable. The map | |
| 130 /// will be mutated during the processing. | |
| 131 /// | |
| 132 /// Continuations to be processed are put on the stack for later processing. | |
| 133 void processBlock( | |
| 134 Expression node, Map<MutableVariable, Primitive> environment) { | |
| 135 Expression next = node.next; | |
| 136 for (; node is! TailExpression; node = next, next = node.next) { | |
| 137 if (node is LetMutable && shouldRewrite(node.variable)) { | |
| 138 // Put the new mutable variable on the stack while processing the body, | |
| 139 // and pop it off again when done with the body. | |
| 140 mutableVariables.add(node.variable); | |
| 141 stack.add(new VariableItem()); | |
| 142 | |
| 143 // Put the initial value into the environment. | |
| 144 Primitive value = node.value; | |
| 145 environment[node.variable] = value; | |
| 146 | |
| 147 // Preserve variable names. | |
| 148 mergeHints(node.variable, value); | |
| 149 | |
| 150 // Remove the mutable variable binding. | |
| 151 node.valueRef.unlink(); | |
| 152 node.remove(); | |
| 153 } else if (node is LetPrim && node.primitive is SetMutable) { | |
| 154 SetMutable setter = node.primitive; | |
| 155 MutableVariable variable = setter.variable; | |
| 156 if (shouldRewrite(variable)) { | |
| 157 // As above, update the environment, preserve variables and remove | |
| 158 // the mutable variable assignment. | |
| 159 environment[variable] = setter.value; | |
| 160 mergeHints(variable, setter.value); | |
| 161 setter.valueRef.unlink(); | |
| 162 node.remove(); | |
| 163 } | |
| 164 } else if (node is LetPrim && node.primitive is GetMutable) { | |
| 165 GetMutable getter = node.primitive; | |
| 166 MutableVariable variable = getter.variable; | |
| 167 if (shouldRewrite(variable)) { | |
| 168 // Replace with the reaching definition from the environment. | |
| 169 Primitive value = environment[variable]; | |
| 170 getter.replaceUsesWith(value); | |
| 171 mergeHints(variable, value); | |
| 172 node.remove(); | |
| 173 } | |
| 174 } else if (node is LetCont) { | |
| 175 // Create phi parameters for each join continuation bound here, and put | |
| 176 // them on the stack for later processing. | |
| 177 // Note that non-join continuations are handled at the use-site. | |
| 178 for (Continuation cont in node.continuations) { | |
| 179 if (!isJoinContinuation(cont)) continue; | |
| 180 // Create a phi parameter for every mutable variable in scope. | |
| 181 // At the same time, build the environment to use for processing | |
| 182 // the continuation (mapping mutables to phi parameters). | |
| 183 continuationPhiCount[cont] = mutableVariables.length; | |
| 184 Map<MutableVariable, Primitive> environment = | |
| 185 <MutableVariable, Primitive>{}; | |
| 186 for (MutableVariable variable in mutableVariables) { | |
| 187 Parameter phi = new Parameter(variable.hint); | |
| 188 phi.type = variable.type; | |
| 189 cont.parameters.add(phi); | |
| 190 phi.parent = cont; | |
| 191 environment[variable] = phi; | |
| 192 } | |
| 193 stack.add(new ContinuationItem(cont, environment)); | |
| 194 } | |
| 195 } else if (node is LetHandler) { | |
| 196 // Process the catch block later and continue into the try block. | |
| 197 // We can use the same environment object for the try and catch blocks. | |
| 198 // The current environment bindings cannot change inside the try block | |
| 199 // because we exclude all variables assigned inside a try block. | |
| 200 // The environment might be extended with more bindings before we | |
| 201 // analyze the catch block, but that's ok. | |
| 202 stack.add(new ContinuationItem(node.handler, environment)); | |
| 203 } | |
| 204 } | |
| 205 | |
| 206 // Analyze the terminal node. | |
| 207 if (node is InvokeContinuation) { | |
| 208 Continuation cont = node.continuation; | |
| 209 if (cont.isReturnContinuation) return; | |
| 210 // This is a call to a join continuation. Add arguments for the phi | |
| 211 // parameters that were added to this continuation. | |
| 212 int phiCount = continuationPhiCount[cont]; | |
| 213 for (int i = 0; i < phiCount; ++i) { | |
| 214 Primitive value = environment[mutableVariables[i]]; | |
| 215 Reference<Primitive> arg = new Reference<Primitive>(value); | |
| 216 node.argumentRefs.add(arg); | |
| 217 arg.parent = node; | |
| 218 } | |
| 219 } else if (node is Branch) { | |
| 220 // Enqueue both branches with the current environment. | |
| 221 // Clone the environments once so the processing of one branch does not | |
| 222 // mutate the environment needed to process the other branch. | |
| 223 stack.add(new ContinuationItem(node.trueContinuation, | |
| 224 new Map<MutableVariable, Primitive>.from(environment))); | |
| 225 stack.add(new ContinuationItem(node.falseContinuation, environment)); | |
| 226 } else { | |
| 227 assert(node is Throw || node is Unreachable); | |
| 228 } | |
| 229 } | |
| 230 } | |
| 231 | |
| 232 abstract class StackItem {} | |
| 233 | |
| 234 /// Represents a mutable variable that is in scope. | |
| 235 /// | |
| 236 /// The topmost mutable variable falls out of scope when this item is | |
| 237 /// taken off the stack. | |
| 238 class VariableItem extends StackItem {} | |
| 239 | |
| 240 /// Represents a yet unprocessed continuation together with the | |
| 241 /// environment in which to process it. | |
| 242 class ContinuationItem extends StackItem { | |
| 243 final Continuation continuation; | |
| 244 final Map<MutableVariable, Primitive> environment; | |
| 245 | |
| 246 ContinuationItem(this.continuation, this.environment); | |
| 247 } | |
| OLD | NEW |
|---|
Chromium Code Reviews
