| OLD | NEW |
|---|
| (Empty) |
| 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 | |
| 3 // BSD-style license that can be found in the LICENSE file. | |
| 4 | |
| 5 library tree_ir.optimization.loop_rewriter; | |
| 6 | |
| 7 import '../tree_ir_nodes.dart'; | |
| 8 import 'optimization.dart' show Pass; | |
| 9 | |
| 10 /// Rewrites [WhileTrue] statements into [For] statements. | |
| 11 /// | |
| 12 /// Before this phase, loops usually contain a lot of "exit code", that is, | |
| 13 /// code that happens at a point where a [Continue] can no longer be reached, | |
| 14 /// and is therefore not really part of the loop. | |
| 15 /// Exit code is moved down after the loop using the following rewrites rules: | |
| 16 /// | |
| 17 /// EXTRACT LABELED STATEMENT: | |
| 18 /// | |
| 19 /// L: | |
| 20 /// while (true) { | |
| 21 /// L2: { | |
| 22 /// S1 (has references to L) | |
| 23 /// } | |
| 24 /// S2 (has no references to L) | |
| 25 /// } | |
| 26 /// | |
| 27 /// ==> | |
| 28 /// | |
| 29 /// L2: { | |
| 30 /// L: while (true) S1 | |
| 31 /// } | |
| 32 /// S2 | |
| 33 /// | |
| 34 /// INTRODUCE CONDITIONAL LOOP: | |
| 35 /// | |
| 36 /// L: | |
| 37 /// while (true) { | |
| 38 /// if (E) { | |
| 39 /// S1 (has references to L) | |
| 40 /// } else { | |
| 41 /// S2 (has no references to L) | |
| 42 /// } | |
| 43 /// } | |
| 44 /// ==> | |
| 45 /// L: | |
| 46 /// while (E) { | |
| 47 /// S1 | |
| 48 /// }; | |
| 49 /// S2 | |
| 50 /// | |
| 51 /// A similar transformation is used when S2 occurs in the 'then' position. | |
| 52 /// | |
| 53 /// Note that the pattern above needs no iteration since nested ifs have been | |
| 54 /// collapsed previously in the [StatementRewriter] phase. | |
| 55 /// | |
| 56 /// | |
| 57 /// PULL INTO UPDATE EXPRESSION: | |
| 58 /// | |
| 59 /// Assignment expressions before the unique continue to a [whileCondition] are | |
| 60 /// pulled into the updates for the loop. | |
| 61 /// | |
| 62 /// L: | |
| 63 /// for (; condition; updates) { | |
| 64 /// S [ x = E; continue L ] | |
| 65 /// } | |
| 66 /// ==> | |
| 67 /// L: | |
| 68 /// for (; condition; updates, x = E) { | |
| 69 /// S [ continue L ] | |
| 70 /// } | |
| 71 /// | |
| 72 /// The decision to only pull in assignments is a heuristic to balance | |
| 73 /// readability and stack trace usability versus the modest code size | |
| 74 /// reduction one might get by aggressively moving expressions into the | |
| 75 /// updates. | |
| 76 class LoopRewriter extends RecursiveTransformer implements Pass { | |
| 77 String get passName => 'Loop rewriter'; | |
| 78 | |
| 79 Set<Label> usedContinueLabels = new Set<Label>(); | |
| 80 | |
| 81 /// Maps loop labels to a list, if that loop can accept update expressions. | |
| 82 /// The list will then be populated while traversing the body of that loop. | |
| 83 /// If a loop is not in the map, update expressions cannot be hoisted there. | |
| 84 Map<Label, List<Expression>> updateExpressions = <Label, List<Expression>>{}; | |
| 85 | |
| 86 void rewrite(FunctionDefinition root) { | |
| 87 root.body = visitStatement(root.body); | |
| 88 } | |
| 89 | |
| 90 Statement visitContinue(Continue node) { | |
| 91 usedContinueLabels.add(node.target); | |
| 92 return node; | |
| 93 } | |
| 94 | |
| 95 Statement visitWhileTrue(WhileTrue node) { | |
| 96 assert(!usedContinueLabels.contains(node.label)); | |
| 97 | |
| 98 // Pull labeled statements outside the loop when possible. | |
| 99 // [head] and [tail] are the first and last labeled statements that were | |
| 100 // pulled out, and null when none have been pulled out. | |
| 101 LabeledStatement head, tail; | |
| 102 while (node.body is LabeledStatement) { | |
| 103 LabeledStatement inner = node.body; | |
| 104 inner.next = visitStatement(inner.next); | |
| 105 bool nextHasContinue = usedContinueLabels.remove(node.label); | |
| 106 if (nextHasContinue) break; | |
| 107 node.body = inner.body; | |
| 108 inner.body = node; | |
| 109 if (head == null) { | |
| 110 head = tail = inner; | |
| 111 } else { | |
| 112 tail.body = inner; | |
| 113 tail = inner; | |
| 114 } | |
| 115 } | |
| 116 | |
| 117 // Rewrite while(true) to for(; condition; updates). | |
| 118 Statement loop = node; | |
| 119 if (node.body is If) { | |
| 120 If body = node.body; | |
| 121 updateExpressions[node.label] = <Expression>[]; | |
| 122 body.thenStatement = visitStatement(body.thenStatement); | |
| 123 bool thenHasContinue = usedContinueLabels.remove(node.label); | |
| 124 body.elseStatement = visitStatement(body.elseStatement); | |
| 125 bool elseHasContinue = usedContinueLabels.remove(node.label); | |
| 126 if (thenHasContinue && !elseHasContinue) { | |
| 127 node.label.binding = null; // Prepare to rebind the label. | |
| 128 loop = new For( | |
| 129 node.label, | |
| 130 body.condition, | |
| 131 updateExpressions[node.label], | |
| 132 body.thenStatement, | |
| 133 body.elseStatement); | |
| 134 } else if (!thenHasContinue && elseHasContinue) { | |
| 135 node.label.binding = null; | |
| 136 loop = new For( | |
| 137 node.label, | |
| 138 new Not(body.condition), | |
| 139 updateExpressions[node.label], | |
| 140 body.elseStatement, | |
| 141 body.thenStatement); | |
| 142 } | |
| 143 } else if (node.body is LabeledStatement) { | |
| 144 // If the body is a labeled statement, its .next has already been visited. | |
| 145 LabeledStatement body = node.body; | |
| 146 body.body = visitStatement(body.body); | |
| 147 usedContinueLabels.remove(node.label); | |
| 148 } else { | |
| 149 node.body = visitStatement(node.body); | |
| 150 usedContinueLabels.remove(node.label); | |
| 151 } | |
| 152 | |
| 153 if (head == null) return loop; | |
| 154 tail.body = loop; | |
| 155 return head; | |
| 156 } | |
| 157 | |
| 158 Statement visitExpressionStatement(ExpressionStatement node) { | |
| 159 if (updateExpressions.isEmpty) { | |
| 160 // Avoid allocating a list if there is no loop. | |
| 161 return super.visitExpressionStatement(node); | |
| 162 } | |
| 163 List<ExpressionStatement> statements = <ExpressionStatement>[]; | |
| 164 while (node.next is ExpressionStatement) { | |
| 165 statements.add(node); | |
| 166 node = node.next; | |
| 167 } | |
| 168 statements.add(node); | |
| 169 Statement next = visitStatement(node.next); | |
| 170 if (next is Continue && next.target.useCount == 1) { | |
| 171 List<Expression> updates = updateExpressions[next.target]; | |
| 172 if (updates != null) { | |
| 173 // Pull expressions before the continue into the for loop update. | |
| 174 // As a heuristic, we only pull in assignment expressions. | |
| 175 // Determine the index of the first assignment to pull in. | |
| 176 int index = statements.length; | |
| 177 while (index > 0 && statements[index - 1].expression is Assign) { | |
| 178 --index; | |
| 179 } | |
| 180 for (ExpressionStatement stmt in statements.skip(index)) { | |
| 181 updates.add(stmt.expression); | |
| 182 } | |
| 183 if (index > 0) { | |
| 184 statements[index - 1].next = next; | |
| 185 return statements.first; | |
| 186 } else { | |
| 187 return next; | |
| 188 } | |
| 189 } | |
| 190 } | |
| 191 // The expression statements could not be pulled into a loop update. | |
| 192 node.next = next; | |
| 193 return statements.first; | |
| 194 } | |
| 195 } | |
| OLD | NEW |
|---|
Chromium Code Reviews
