OLD | NEW |
1 library dart2js.cps_ir.loop_invariant_branch; | 1 library dart2js.cps_ir.loop_invariant_branch; |
2 | 2 |
3 import 'cps_ir_nodes.dart'; | 3 import 'cps_ir_nodes.dart'; |
4 import 'optimizers.dart'; | 4 import 'optimizers.dart'; |
5 import 'loop_hierarchy.dart'; | 5 import 'loop_hierarchy.dart'; |
6 import 'cps_fragment.dart'; | 6 import 'cps_fragment.dart'; |
7 import 'redundant_join.dart' show AlphaRenamer; | 7 import 'redundant_join.dart' show AlphaRenamer; |
8 | 8 |
9 /// Hoists branches out of loops, where: | 9 /// Hoists branches out of loops, where: |
10 /// - the branch is at the entry point of a loop | 10 /// - the branch is at the entry point of a loop |
(...skipping 103 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
114 /// let inner(y, x1, x2, x3) = BODY | 114 /// let inner(y, x1, x2, x3) = BODY |
115 /// let outer(x1, x2, x3) = | 115 /// let outer(x1, x2, x3) = |
116 /// [ .. inner(y', x1, x2, x3) .. ] | 116 /// [ .. inner(y', x1, x2, x3) .. ] |
117 /// | 117 /// |
118 void appendParameters(Continuation cont, List<Parameter> parameters) { | 118 void appendParameters(Continuation cont, List<Parameter> parameters) { |
119 cont.parameters.addAll(parameters); | 119 cont.parameters.addAll(parameters); |
120 for (Reference ref = cont.firstRef; ref != null; ref = ref.next) { | 120 for (Reference ref = cont.firstRef; ref != null; ref = ref.next) { |
121 Node use = ref.parent; | 121 Node use = ref.parent; |
122 if (use is InvokeContinuation) { | 122 if (use is InvokeContinuation) { |
123 for (Parameter loopParam in parameters) { | 123 for (Parameter loopParam in parameters) { |
124 use.argumentRefs.add(new Reference<Primitive>(loopParam)..parent = use
); | 124 use.argumentRefs |
| 125 .add(new Reference<Primitive>(loopParam)..parent = use); |
125 } | 126 } |
126 } | 127 } |
127 } | 128 } |
128 } | 129 } |
129 | 130 |
130 bool tryHoistEntryCheck(Continuation loop) { | 131 bool tryHoistEntryCheck(Continuation loop) { |
131 // Check if this is a loop starting with a branch. | 132 // Check if this is a loop starting with a branch. |
132 Expression body = getEffectiveBody(loop.body); | 133 Expression body = getEffectiveBody(loop.body); |
133 if (body is! Branch) return false; | 134 if (body is! Branch) return false; |
134 Branch branch = body; | 135 Branch branch = body; |
135 | 136 |
136 // Is the condition loop invariant? | 137 // Is the condition loop invariant? |
137 Primitive condition = branch.condition; | 138 Primitive condition = branch.condition; |
138 if (loopHeaderFor[condition] == loop) return false; | 139 if (loopHeaderFor[condition] == loop) return false; |
139 | 140 |
140 Continuation trueCont = branch.trueContinuation; | 141 Continuation trueCont = branch.trueContinuation; |
141 Continuation falseCont = branch.falseContinuation; | 142 Continuation falseCont = branch.falseContinuation; |
142 Continuation hoistedCase; // The branch to hoist. | 143 Continuation hoistedCase; // The branch to hoist. |
143 Continuation loopCase; // The branch that is part of the loop. | 144 Continuation loopCase; // The branch that is part of the loop. |
144 | 145 |
145 // Check that one branch is part of the loop, and the other is an exit. | 146 // Check that one branch is part of the loop, and the other is an exit. |
146 if (loopHierarchy.getLoopHeader(trueCont) != loop && | 147 if (loopHierarchy.getLoopHeader(trueCont) != loop && |
147 loopHierarchy.getLoopHeader(falseCont) == loop) { | 148 loopHierarchy.getLoopHeader(falseCont) == loop) { |
148 hoistedCase = trueCont; | 149 hoistedCase = trueCont; |
149 loopCase = falseCont; | 150 loopCase = falseCont; |
150 } else if (loopHierarchy.getLoopHeader(falseCont) != loop && | 151 } else if (loopHierarchy.getLoopHeader(falseCont) != loop && |
151 loopHierarchy.getLoopHeader(trueCont) == loop) { | 152 loopHierarchy.getLoopHeader(trueCont) == loop) { |
152 hoistedCase = falseCont; | 153 hoistedCase = falseCont; |
153 loopCase = trueCont; | 154 loopCase = trueCont; |
154 } else { | 155 } else { |
155 return false; | 156 return false; |
156 } | 157 } |
157 | 158 |
158 // Hoist non-loop continuations out of the loop. | 159 // Hoist non-loop continuations out of the loop. |
159 // The hoisted branch can reference other continuations bound in the loop, | 160 // The hoisted branch can reference other continuations bound in the loop, |
160 // so to stay in scope, those need to be hoisted as well. | 161 // so to stay in scope, those need to be hoisted as well. |
161 // | 162 // |
(...skipping 42 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
204 // ==> | 205 // ==> |
205 // | 206 // |
206 // let newTrue() = hoistCase(i) | 207 // let newTrue() = hoistCase(i) |
207 // let newFalse() = | 208 // let newFalse() = |
208 // let loop(x) = | 209 // let loop(x) = |
209 // let loopCase() = LOOP | 210 // let loopCase() = LOOP |
210 // branch b hoistCase loopCase | 211 // branch b hoistCase loopCase |
211 // branch b newTrue newFalse | 212 // branch b newTrue newFalse |
212 // | 213 // |
213 InvokeContinuation loopEntry = loopBinding.body; | 214 InvokeContinuation loopEntry = loopBinding.body; |
214 List<Primitive> loopArgs = | 215 List<Primitive> loopArgs = loopEntry.arguments.toList(); |
215 loopEntry.arguments.toList(); | |
216 CpsFragment cps = new CpsFragment(); | 216 CpsFragment cps = new CpsFragment(); |
217 cps.branch(condition, | 217 cps |
218 strict: branch.isStrictCheck, | 218 .branch(condition, |
219 negate: hoistedCase == falseCont) | 219 strict: branch.isStrictCheck, negate: hoistedCase == falseCont) |
220 .invokeContinuation(hoistedCase, loopArgs); | 220 .invokeContinuation(hoistedCase, loopArgs); |
221 | 221 |
222 // The continuations created in the fragment need to have their loop header | 222 // The continuations created in the fragment need to have their loop header |
223 // set so the loop hierarchy remains intact | 223 // set so the loop hierarchy remains intact |
224 loopHierarchy.update(cps, | 224 loopHierarchy.update(cps, |
225 exitLoop: loopHierarchy.getEnclosingLoop(loop), | 225 exitLoop: loopHierarchy.getEnclosingLoop(loop), |
226 catchLoop: catchLoopFor[loop]); | 226 catchLoop: catchLoopFor[loop]); |
227 | 227 |
228 // Insert above the loop. This will put the loop itself in a branch. | 228 // Insert above the loop. This will put the loop itself in a branch. |
229 cps.insertAbove(loopBinding); | 229 cps.insertAbove(loopBinding); |
230 | 230 |
(...skipping 12 matching lines...) Expand all Loading... |
243 // in loop(i) | 243 // in loop(i) |
244 // | 244 // |
245 destroyAndReplace(branch, new InvokeContinuation(loopCase, [])); | 245 destroyAndReplace(branch, new InvokeContinuation(loopCase, [])); |
246 | 246 |
247 // Record that at least one branch was hoisted to trigger alpha renaming. | 247 // Record that at least one branch was hoisted to trigger alpha renaming. |
248 wasHoisted = true; | 248 wasHoisted = true; |
249 | 249 |
250 return true; | 250 return true; |
251 } | 251 } |
252 } | 252 } |
OLD | NEW |