| OLD | NEW |
| 1 // Copyright (c) 2014, the Dart project authors. Please see the AUTHORS file | 1 // Copyright (c) 2014, 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 tree_ir.optimization.loop_rewriter; | 5 library tree_ir.optimization.loop_rewriter; |
| 6 | 6 |
| 7 import 'optimization.dart' show Pass; | 7 import 'optimization.dart' show Pass; |
| 8 import '../tree_ir_nodes.dart'; | 8 import '../tree_ir_nodes.dart'; |
| 9 | 9 |
| 10 /// Rewrites [WhileTrue] statements into [For] statements. | 10 /// Rewrites [WhileTrue] statements into [For] statements. |
| (...skipping 34 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 45 /// L: | 45 /// L: |
| 46 /// while (E) { | 46 /// while (E) { |
| 47 /// S1 | 47 /// S1 |
| 48 /// }; | 48 /// }; |
| 49 /// S2 | 49 /// S2 |
| 50 /// | 50 /// |
| 51 /// A similar transformation is used when S2 occurs in the 'then' position. | 51 /// A similar transformation is used when S2 occurs in the 'then' position. |
| 52 /// | 52 /// |
| 53 /// Note that the pattern above needs no iteration since nested ifs have been | 53 /// Note that the pattern above needs no iteration since nested ifs have been |
| 54 /// collapsed previously in the [StatementRewriter] phase. | 54 /// collapsed previously in the [StatementRewriter] phase. |
| 55 /// | 55 /// |
| 56 /// | 56 /// |
| 57 /// PULL INTO UPDATE EXPRESSION: | 57 /// PULL INTO UPDATE EXPRESSION: |
| 58 /// | 58 /// |
| 59 /// Assignment expressions before the unique continue to a [whileCondition] are | 59 /// Assignment expressions before the unique continue to a [whileCondition] are |
| 60 /// pulled into the updates for the loop. | 60 /// pulled into the updates for the loop. |
| 61 /// | 61 /// |
| 62 /// L: | 62 /// L: |
| 63 /// for (; condition; updates) { | 63 /// for (; condition; updates) { |
| 64 /// S [ x = E; continue L ] | 64 /// S [ x = E; continue L ] |
| 65 /// } | 65 /// } |
| 66 /// ==> | 66 /// ==> |
| 67 /// L: | 67 /// L: |
| 68 /// for (; condition; updates, x = E) { | 68 /// for (; condition; updates, x = E) { |
| 69 /// S [ continue L ] | 69 /// S [ continue L ] |
| 70 /// } | 70 /// } |
| 71 /// | 71 /// |
| 72 /// The decision to only pull in assignments is a heuristic to balance | 72 /// The decision to only pull in assignments is a heuristic to balance |
| 73 /// readability and stack trace usability versus the modest code size | 73 /// readability and stack trace usability versus the modest code size |
| 74 /// reduction one might get by aggressively moving expressions into the | 74 /// reduction one might get by aggressively moving expressions into the |
| 75 /// updates. | 75 /// updates. |
| 76 class LoopRewriter extends RecursiveTransformer | 76 class LoopRewriter extends RecursiveTransformer |
| 77 implements Pass { | 77 implements Pass { |
| 78 String get passName => 'Loop rewriter'; | 78 String get passName => 'Loop rewriter'; |
| 79 | 79 |
| 80 Set<Label> usedContinueLabels = new Set<Label>(); | 80 Set<Label> usedContinueLabels = new Set<Label>(); |
| 81 | 81 |
| 82 /// Maps loop labels to a list, if that loop can accept update expressions. | 82 /// Maps loop labels to a list, if that loop can accept update expressions. |
| 83 /// The list will then be populated while traversing the body of that loop. | 83 /// The list will then be populated while traversing the body of that loop. |
| 84 /// If a loop is not in the map, update expressions cannot be hoisted there. | 84 /// If a loop is not in the map, update expressions cannot be hoisted there. |
| 85 Map<Label, List<Expression>> updateExpressions = <Label, List<Expression>>{}; | 85 Map<Label, List<Expression>> updateExpressions = <Label, List<Expression>>{}; |
| 86 | 86 |
| 87 void rewrite(FunctionDefinition root) { | 87 void rewrite(FunctionDefinition root) { |
| 88 root.body = visitStatement(root.body); | 88 root.body = visitStatement(root.body); |
| 89 } | 89 } |
| 90 | 90 |
| 91 @override | |
| 92 void visitInnerFunction(FunctionDefinition node) { | |
| 93 node.body = new LoopRewriter().visitStatement(node.body); | |
| 94 } | |
| 95 | |
| 96 Statement visitContinue(Continue node) { | 91 Statement visitContinue(Continue node) { |
| 97 usedContinueLabels.add(node.target); | 92 usedContinueLabels.add(node.target); |
| 98 return node; | 93 return node; |
| 99 } | 94 } |
| 100 | 95 |
| 101 Statement visitWhileTrue(WhileTrue node) { | 96 Statement visitWhileTrue(WhileTrue node) { |
| 102 assert(!usedContinueLabels.contains(node.label)); | 97 assert(!usedContinueLabels.contains(node.label)); |
| 103 | 98 |
| 104 // Pull labeled statements outside the loop when possible. | 99 // Pull labeled statements outside the loop when possible. |
| 105 // [head] and [tail] are the first and last labeled statements that were | 100 // [head] and [tail] are the first and last labeled statements that were |
| (...skipping 86 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 192 } else { | 187 } else { |
| 193 return next; | 188 return next; |
| 194 } | 189 } |
| 195 } | 190 } |
| 196 } | 191 } |
| 197 // The expression statements could not be pulled into a loop update. | 192 // The expression statements could not be pulled into a loop update. |
| 198 node.next = next; | 193 node.next = next; |
| 199 return statements.first; | 194 return statements.first; |
| 200 } | 195 } |
| 201 } | 196 } |
| OLD | NEW |