| OLD | NEW |
| 1 // Copyright (c) 2015, the Dart project authors. Please see the AUTHORS file | 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 | 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. | 3 // BSD-style license that can be found in the LICENSE file. |
| 4 | 4 |
| 5 library dart2js.cps_ir.redundant_join_elimination; | 5 library dart2js.cps_ir.redundant_join_elimination; |
| 6 | 6 |
| 7 import 'cps_ir_nodes.dart'; | 7 import 'cps_ir_nodes.dart'; |
| 8 import 'optimizers.dart'; | 8 import 'optimizers.dart'; |
| 9 | 9 |
| 10 /// Eliminates redundant join points. | 10 /// Eliminates redundant join points. |
| 11 /// | 11 /// |
| 12 /// A redundant join point is a continuation that immediately branches | 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 | 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 | 14 /// at every invocation. Each invocation is redirected to jump directly |
| 15 /// to the branch target. | 15 /// to the branch target. |
| 16 /// | 16 /// |
| 17 /// Internally in this pass, parameters are treated as names with lexical | 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 | 18 /// scoping, and a given parameter "name" may be declared by more than |
| 19 /// one continuation. The reference chains for parameters are therefore | 19 /// one continuation. The reference chains for parameters are therefore |
| 20 /// meaningless during this pass, until repaired by [AlphaRenamer] at | 20 /// meaningless during this pass, until repaired by [AlphaRenamer] at |
| 21 /// the end. | 21 /// the end. |
| 22 class RedundantJoinEliminator extends TrampolineRecursiveVisitor | 22 class RedundantJoinEliminator extends TrampolineRecursiveVisitor |
| 23 implements Pass { | 23 implements Pass { |
| 24 String get passName => 'Redundant join elimination'; | 24 String get passName => 'Redundant join elimination'; |
| 25 | 25 |
| 26 final Set<Branch> workSet = new Set<Branch>(); | 26 final Set<Branch> workSet = new Set<Branch>(); |
| 27 | 27 |
| 28 void rewrite(FunctionDefinition node) { | 28 void rewrite(FunctionDefinition node) { |
| 29 visit(node); | 29 visit(node); |
| 30 | 30 |
| 31 while (workSet.isNotEmpty) { | 31 while (workSet.isNotEmpty) { |
| 32 Branch branch = workSet.first; | 32 Branch branch = workSet.first; |
| 33 workSet.remove(branch); | 33 workSet.remove(branch); |
| (...skipping 69 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 103 ++falseHits; | 103 ++falseHits; |
| 104 falseCall = invoke; | 104 falseCall = invoke; |
| 105 } | 105 } |
| 106 } | 106 } |
| 107 | 107 |
| 108 // The optimization is now known to be safe, but it only pays off if | 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 | 109 // one of the callers can inline its target, since otherwise we end up |
| 110 // replacing a boolean variable with a labeled break. | 110 // replacing a boolean variable with a labeled break. |
| 111 // TODO(asgerf): The labeled break might be better? Evaluate. | 111 // TODO(asgerf): The labeled break might be better? Evaluate. |
| 112 if (!(trueHits == 1 && !trueCall.isEscapingTry || | 112 if (!(trueHits == 1 && !trueCall.isEscapingTry || |
| 113 falseHits == 1 && !falseCall.isEscapingTry)) { | 113 falseHits == 1 && !falseCall.isEscapingTry)) { |
| 114 return; | 114 return; |
| 115 } | 115 } |
| 116 | 116 |
| 117 // Lift any continuations bound inside branchCont so they are in scope at | 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 | 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. | 119 // scope, so they are added as parameters on each lifted continuation. |
| 120 // Schematically: | 120 // Schematically: |
| 121 // | 121 // |
| 122 // (LetCont (branchCont (x1, x2, x3) = | 122 // (LetCont (branchCont (x1, x2, x3) = |
| 123 // (LetCont (innerCont (y) = ...) in | 123 // (LetCont (innerCont (y) = ...) in |
| 124 // [... innerCont(y') ...])) | 124 // [... innerCont(y') ...])) |
| 125 // | 125 // |
| 126 // => | 126 // => |
| 127 // | 127 // |
| 128 // (LetCont (innerCont (y, x1, x2, x3) = ...) in | 128 // (LetCont (innerCont (y, x1, x2, x3) = ...) in |
| 129 // (LetCont (branchCont (x1, x2, x3) = | 129 // (LetCont (branchCont (x1, x2, x3) = |
| 130 // [... innerCont(y', x1, x2, x3) ...]) | 130 // [... innerCont(y', x1, x2, x3) ...]) |
| 131 // | 131 // |
| 132 // Parameter objects become shared between branchCont and the lifted | 132 // Parameter objects become shared between branchCont and the lifted |
| 133 // continuations. [AlphaRenamer] will clean up at the end of this pass. | 133 // continuations. [AlphaRenamer] will clean up at the end of this pass. |
| 134 LetCont outerLetCont = branchCont.parent; | 134 LetCont outerLetCont = branchCont.parent; |
| 135 while (branchCont.body is LetCont) { | 135 while (branchCont.body is LetCont) { |
| 136 LetCont innerLetCont = branchCont.body; | 136 LetCont innerLetCont = branchCont.body; |
| 137 for (Continuation innerCont in innerLetCont.continuations) { | 137 for (Continuation innerCont in innerLetCont.continuations) { |
| 138 innerCont.parameters.addAll(branchCont.parameters); | 138 innerCont.parameters.addAll(branchCont.parameters); |
| 139 for (Reference ref = innerCont.firstRef; ref != null; ref = ref.next) { | 139 for (Reference ref = innerCont.firstRef; ref != null; ref = ref.next) { |
| 140 Expression use = ref.parent; | 140 Expression use = ref.parent; |
| 141 if (use is InvokeContinuation) { | 141 if (use is InvokeContinuation) { |
| 142 for (Parameter param in branchCont.parameters) { | 142 for (Parameter param in branchCont.parameters) { |
| 143 use.argumentRefs.add( | 143 use.argumentRefs |
| 144 new Reference<Primitive>(param)..parent = use); | 144 .add(new Reference<Primitive>(param)..parent = use); |
| 145 } | 145 } |
| 146 } else { | 146 } else { |
| 147 // The branch will be eliminated, so don't worry about updating it. | 147 // The branch will be eliminated, so don't worry about updating it. |
| 148 assert(use == branch); | 148 assert(use == branch); |
| 149 } | 149 } |
| 150 } | 150 } |
| 151 } | 151 } |
| 152 innerLetCont.remove(); | 152 innerLetCont.remove(); |
| 153 innerLetCont.insertAbove(outerLetCont); | 153 innerLetCont.insertAbove(outerLetCont); |
| 154 } | 154 } |
| (...skipping 98 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 253 }); | 253 }); |
| 254 } | 254 } |
| 255 | 255 |
| 256 processReference(Reference ref) { | 256 processReference(Reference ref) { |
| 257 Parameter target = renaming[ref.definition]; | 257 Parameter target = renaming[ref.definition]; |
| 258 if (target != null) { | 258 if (target != null) { |
| 259 ref.changeTo(target); | 259 ref.changeTo(target); |
| 260 } | 260 } |
| 261 } | 261 } |
| 262 } | 262 } |
| OLD | NEW |