| 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.redundant_join_elimination; | |
| 6 | |
| 7 import 'cps_ir_nodes.dart'; | |
| 8 import 'optimizers.dart'; | |
| 9 | |
| 10 /// Eliminates redundant join points. | |
| 11 /// | |
| 12 /// A redundant join point is a continuation that immediately branches | |
| 13 /// based on one of its parameters, and that parameter is a constant value | |
| 14 /// at every invocation. Each invocation is redirected to jump directly | |
| 15 /// to the branch target. | |
| 16 /// | |
| 17 /// Internally in this pass, parameters are treated as names with lexical | |
| 18 /// scoping, and a given parameter "name" may be declared by more than | |
| 19 /// one continuation. The reference chains for parameters are therefore | |
| 20 /// meaningless during this pass, until repaired by [AlphaRenamer] at | |
| 21 /// the end. | |
| 22 class RedundantJoinEliminator extends TrampolineRecursiveVisitor | |
| 23 implements Pass { | |
| 24 String get passName => 'Redundant join elimination'; | |
| 25 | |
| 26 final Set<Branch> workSet = new Set<Branch>(); | |
| 27 | |
| 28 void rewrite(FunctionDefinition node) { | |
| 29 visit(node); | |
| 30 | |
| 31 while (workSet.isNotEmpty) { | |
| 32 Branch branch = workSet.first; | |
| 33 workSet.remove(branch); | |
| 34 rewriteBranch(branch); | |
| 35 } | |
| 36 | |
| 37 new AlphaRenamer().visit(node); | |
| 38 } | |
| 39 | |
| 40 void processBranch(Branch node) { | |
| 41 workSet.add(node); | |
| 42 } | |
| 43 | |
| 44 /// Returns the body of [node], ignoring all LetCont nodes. | |
| 45 Expression getEffectiveBody(InteriorNode node) { | |
| 46 while (true) { | |
| 47 Expression body = node.body; | |
| 48 if (body is LetCont) { | |
| 49 node = body; | |
| 50 } else { | |
| 51 return body; | |
| 52 } | |
| 53 } | |
| 54 } | |
| 55 | |
| 56 /// Returns the parent of [node], ignoring all LetCont nodes. | |
| 57 InteriorNode getEffectiveParent(Expression node) { | |
| 58 while (true) { | |
| 59 Node parent = node.parent; | |
| 60 if (parent is LetCont) { | |
| 61 node = parent; | |
| 62 } else { | |
| 63 return parent; | |
| 64 } | |
| 65 } | |
| 66 } | |
| 67 | |
| 68 void rewriteBranch(Branch branch) { | |
| 69 InteriorNode parent = getEffectiveParent(branch); | |
| 70 if (parent is! Continuation) return; | |
| 71 Continuation branchCont = parent; | |
| 72 | |
| 73 // Other optimizations take care of single-use continuations. | |
| 74 if (!branchCont.hasMultipleUses) return; | |
| 75 | |
| 76 // It might be beneficial to rewrite calls to recursive continuations, | |
| 77 // but we currently do not support this. | |
| 78 if (branchCont.isRecursive) return; | |
| 79 | |
| 80 // Check that the branching condition is a parameter on the | |
| 81 // enclosing continuation. | |
| 82 // Note: Do not use the parent pointer for this check, because parameters | |
| 83 // are temporarily shared between different continuations during this pass. | |
| 84 Primitive condition = branch.condition; | |
| 85 int parameterIndex = branchCont.parameters.indexOf(condition); | |
| 86 if (parameterIndex == -1) return; | |
| 87 | |
| 88 // Check that all callers hit a fixed branch, and count the number | |
| 89 // of times each branch is hit. | |
| 90 // We know all callers are InvokeContinuations because they are the only | |
| 91 // valid uses of a multi-use continuation. | |
| 92 int trueHits = 0, falseHits = 0; | |
| 93 InvokeContinuation trueCall, falseCall; | |
| 94 for (Reference ref = branchCont.firstRef; ref != null; ref = ref.next) { | |
| 95 InvokeContinuation invoke = ref.parent; | |
| 96 Primitive argument = invoke.argument(parameterIndex); | |
| 97 if (argument is! Constant) return; // Branching condition is unknown. | |
| 98 Constant constant = argument; | |
| 99 if (isTruthyConstant(constant.value, strict: branch.isStrictCheck)) { | |
| 100 ++trueHits; | |
| 101 trueCall = invoke; | |
| 102 } else { | |
| 103 ++falseHits; | |
| 104 falseCall = invoke; | |
| 105 } | |
| 106 } | |
| 107 | |
| 108 // The optimization is now known to be safe, but it only pays off if | |
| 109 // one of the callers can inline its target, since otherwise we end up | |
| 110 // replacing a boolean variable with a labeled break. | |
| 111 // TODO(asgerf): The labeled break might be better? Evaluate. | |
| 112 if (!(trueHits == 1 && !trueCall.isEscapingTry || | |
| 113 falseHits == 1 && !falseCall.isEscapingTry)) { | |
| 114 return; | |
| 115 } | |
| 116 | |
| 117 // Lift any continuations bound inside branchCont so they are in scope at | |
| 118 // the call sites. When lifting, the parameters of branchCont fall out of | |
| 119 // scope, so they are added as parameters on each lifted continuation. | |
| 120 // Schematically: | |
| 121 // | |
| 122 // (LetCont (branchCont (x1, x2, x3) = | |
| 123 // (LetCont (innerCont (y) = ...) in | |
| 124 // [... innerCont(y') ...])) | |
| 125 // | |
| 126 // => | |
| 127 // | |
| 128 // (LetCont (innerCont (y, x1, x2, x3) = ...) in | |
| 129 // (LetCont (branchCont (x1, x2, x3) = | |
| 130 // [... innerCont(y', x1, x2, x3) ...]) | |
| 131 // | |
| 132 // Parameter objects become shared between branchCont and the lifted | |
| 133 // continuations. [AlphaRenamer] will clean up at the end of this pass. | |
| 134 LetCont outerLetCont = branchCont.parent; | |
| 135 while (branchCont.body is LetCont) { | |
| 136 LetCont innerLetCont = branchCont.body; | |
| 137 for (Continuation innerCont in innerLetCont.continuations) { | |
| 138 innerCont.parameters.addAll(branchCont.parameters); | |
| 139 for (Reference ref = innerCont.firstRef; ref != null; ref = ref.next) { | |
| 140 Expression use = ref.parent; | |
| 141 if (use is InvokeContinuation) { | |
| 142 for (Parameter param in branchCont.parameters) { | |
| 143 use.argumentRefs | |
| 144 .add(new Reference<Primitive>(param)..parent = use); | |
| 145 } | |
| 146 } else { | |
| 147 // The branch will be eliminated, so don't worry about updating it. | |
| 148 assert(use == branch); | |
| 149 } | |
| 150 } | |
| 151 } | |
| 152 innerLetCont.remove(); | |
| 153 innerLetCont.insertAbove(outerLetCont); | |
| 154 } | |
| 155 | |
| 156 assert(branchCont.body == branch); | |
| 157 | |
| 158 Continuation trueCont = branch.trueContinuation; | |
| 159 Continuation falseCont = branch.falseContinuation; | |
| 160 | |
| 161 assert(branchCont != trueCont); | |
| 162 assert(branchCont != falseCont); | |
| 163 | |
| 164 // Rewrite every invocation of branchCont to call either the true or false | |
| 165 // branch directly. Since these were lifted out above branchCont, they are | |
| 166 // now in scope. | |
| 167 // Since trueCont and falseCont were branch targets, they originally | |
| 168 // had no parameters, and so after the lifting, their parameters are | |
| 169 // exactly the same as those accepted by branchCont. | |
| 170 while (branchCont.firstRef != null) { | |
| 171 Reference reference = branchCont.firstRef; | |
| 172 InvokeContinuation invoke = branchCont.firstRef.parent; | |
| 173 Constant condition = invoke.argument(parameterIndex); | |
| 174 if (isTruthyConstant(condition.value, strict: branch.isStrictCheck)) { | |
| 175 invoke.continuationRef.changeTo(trueCont); | |
| 176 } else { | |
| 177 invoke.continuationRef.changeTo(falseCont); | |
| 178 } | |
| 179 assert(branchCont.firstRef != reference); | |
| 180 } | |
| 181 | |
| 182 // Remove the now-unused branchCont continuation. | |
| 183 assert(branchCont.hasNoUses); | |
| 184 branch.trueContinuationRef.unlink(); | |
| 185 branch.falseContinuationRef.unlink(); | |
| 186 outerLetCont.continuations.remove(branchCont); | |
| 187 if (outerLetCont.continuations.isEmpty) { | |
| 188 outerLetCont.remove(); | |
| 189 } | |
| 190 | |
| 191 // We may have created new redundant join points in the two branches. | |
| 192 enqueueContinuation(trueCont); | |
| 193 enqueueContinuation(falseCont); | |
| 194 } | |
| 195 | |
| 196 void enqueueContinuation(Continuation cont) { | |
| 197 Expression body = getEffectiveBody(cont); | |
| 198 if (body is Branch) { | |
| 199 workSet.add(body); | |
| 200 } | |
| 201 } | |
| 202 } | |
| 203 | |
| 204 /// Ensures parameter objects are not shared between different continuations, | |
| 205 /// akin to alpha-renaming variables so every variable is named uniquely. | |
| 206 /// For example: | |
| 207 /// | |
| 208 /// LetCont (k1 x = (return x)) in | |
| 209 /// LetCont (k2 x = (InvokeContinuation k3 x)) in ... | |
| 210 /// => | |
| 211 /// LetCont (k1 x = (return x)) in | |
| 212 /// LetCont (k2 x' = (InvokeContinuation k3 x')) in ... | |
| 213 /// | |
| 214 /// After lifting LetConts in the main pass above, parameter objects can have | |
| 215 /// multiple bindings. Each reference implicitly refers to the binding that | |
| 216 /// is currently in scope. | |
| 217 /// | |
| 218 /// This returns the IR to its normal form after redundant joins have been | |
| 219 /// eliminated. | |
| 220 class AlphaRenamer extends TrampolineRecursiveVisitor { | |
| 221 Map<Parameter, Parameter> renaming = <Parameter, Parameter>{}; | |
| 222 | |
| 223 processContinuation(Continuation cont) { | |
| 224 if (cont.isReturnContinuation) return; | |
| 225 | |
| 226 List<Parameter> shadowedKeys = <Parameter>[]; | |
| 227 List<Parameter> shadowedValues = <Parameter>[]; | |
| 228 | |
| 229 // Create new parameters and update the environment. | |
| 230 for (int i = 0; i < cont.parameters.length; ++i) { | |
| 231 Parameter param = cont.parameters[i]; | |
| 232 shadowedKeys.add(param); | |
| 233 shadowedValues.add(renaming.remove(param)); | |
| 234 // If the parameter appears to belong to another continuation, | |
| 235 // create a new parameter object for this continuation. | |
| 236 if (param.parent != cont) { | |
| 237 Parameter newParam = new Parameter(param.hint); | |
| 238 newParam.type = param.type; | |
| 239 renaming[param] = newParam; | |
| 240 cont.parameters[i] = newParam; | |
| 241 newParam.parent = cont; | |
| 242 } | |
| 243 } | |
| 244 | |
| 245 pushAction(() { | |
| 246 // Restore the original environment. | |
| 247 for (int i = 0; i < cont.parameters.length; ++i) { | |
| 248 renaming.remove(cont.parameters[i]); | |
| 249 if (shadowedValues[i] != null) { | |
| 250 renaming[shadowedKeys[i]] = shadowedValues[i]; | |
| 251 } | |
| 252 } | |
| 253 }); | |
| 254 } | |
| 255 | |
| 256 processReference(Reference ref) { | |
| 257 Parameter target = renaming[ref.definition]; | |
| 258 if (target != null) { | |
| 259 ref.changeTo(target); | |
| 260 } | |
| 261 } | |
| 262 } | |
| OLD | NEW |
|---|
Chromium Code Reviews
