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 |