| 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 part of tree_ir.optimization; | 5 part of tree_ir.optimization; |
| 6 | 6 |
| 7 /** | 7 /** |
| 8 * Performs the following transformations on the tree: | 8 * Performs the following transformations on the tree: |
| 9 * - Assignment propagation | 9 * - Assignment propagation |
| 10 * - If-to-conditional conversion | 10 * - If-to-conditional conversion |
| (...skipping 165 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 176 | 176 |
| 177 // Propagate a variable's definition to its use site if: | 177 // Propagate a variable's definition to its use site if: |
| 178 // 1. It has a single use, to avoid code growth and potential duplication | 178 // 1. It has a single use, to avoid code growth and potential duplication |
| 179 // of side effects, AND | 179 // of side effects, AND |
| 180 // 2. It was the most recent expression evaluated so that we do not | 180 // 2. It was the most recent expression evaluated so that we do not |
| 181 // reorder expressions with side effects. | 181 // reorder expressions with side effects. |
| 182 if (!environment.isEmpty && | 182 if (!environment.isEmpty && |
| 183 environment.last.variable == node.variable && | 183 environment.last.variable == node.variable && |
| 184 node.variable.readCount == 1) { | 184 node.variable.readCount == 1) { |
| 185 --node.variable.readCount; | 185 --node.variable.readCount; |
| 186 return visitExpression(environment.removeLast().definition); | 186 return visitExpression(environment.removeLast().value); |
| 187 } | 187 } |
| 188 | 188 |
| 189 // If the definition could not be propagated, leave the variable use. | 189 // If the definition could not be propagated, leave the variable use. |
| 190 return node; | 190 return node; |
| 191 } | 191 } |
| 192 | 192 |
| 193 /// Returns true if [exp] has no side effects and has a constant value within | 193 /// Returns true if [exp] has no side effects and has a constant value within |
| 194 /// any given activation of the enclosing method. | 194 /// any given activation of the enclosing method. |
| 195 bool isEffectivelyConstant(Expression exp) { | 195 bool isEffectivelyConstant(Expression exp) { |
| 196 // TODO(asgerf): Can be made more aggressive e.g. by checking conditional | 196 // TODO(asgerf): Can be made more aggressive e.g. by checking conditional |
| 197 // expressions recursively. Determine if that is a valuable optimization | 197 // expressions recursively. Determine if that is a valuable optimization |
| 198 // and/or if it is better handled at the CPS level. | 198 // and/or if it is better handled at the CPS level. |
| 199 return exp is Constant || | 199 return exp is Constant || |
| 200 exp is This || | 200 exp is This || |
| 201 exp is ReifyTypeVar || | 201 exp is ReifyTypeVar || |
| 202 exp is VariableUse && constantEnvironment.containsKey(exp.variable); | 202 exp is VariableUse && constantEnvironment.containsKey(exp.variable); |
| 203 } | 203 } |
| 204 | 204 |
| 205 Statement visitAssign(Assign node) { | 205 Statement visitAssign(Assign node) { |
| 206 if (isEffectivelyConstant(node.definition) && | 206 if (isEffectivelyConstant(node.value) && |
| 207 node.variable.writeCount == 1) { | 207 node.variable.writeCount == 1) { |
| 208 // Handle constant assignments specially. | 208 // Handle constant assignments specially. |
| 209 // They are always safe to propagate (though we should avoid duplication). | 209 // They are always safe to propagate (though we should avoid duplication). |
| 210 // Moreover, they should not prevent other expressions from propagating. | 210 // Moreover, they should not prevent other expressions from propagating. |
| 211 if (node.variable.readCount <= 1) { | 211 if (node.variable.readCount <= 1) { |
| 212 // A single-use constant should always be propagted to its use site. | 212 // A single-use constant should always be propagted to its use site. |
| 213 constantEnvironment[node.variable] = visitExpression(node.definition); | 213 constantEnvironment[node.variable] = visitExpression(node.value); |
| 214 --node.variable.writeCount; | 214 --node.variable.writeCount; |
| 215 return visitStatement(node.next); | 215 return visitStatement(node.next); |
| 216 } else { | 216 } else { |
| 217 // With more than one use, we cannot propagate the constant. | 217 // With more than one use, we cannot propagate the constant. |
| 218 // Visit the following statement without polluting [environment] so | 218 // Visit the following statement without polluting [environment] so |
| 219 // that any preceding non-constant assignments might still propagate. | 219 // that any preceding non-constant assignments might still propagate. |
| 220 node.next = visitStatement(node.next); | 220 node.next = visitStatement(node.next); |
| 221 node.definition = visitExpression(node.definition); | 221 node.value = visitExpression(node.value); |
| 222 return node; | 222 return node; |
| 223 } | 223 } |
| 224 } else { | 224 } else { |
| 225 // Try to propagate assignment, and block previous assignment until this | 225 // Try to propagate assignment, and block previous assignment until this |
| 226 // has propagated. | 226 // has propagated. |
| 227 environment.add(node); | 227 environment.add(node); |
| 228 Statement next = visitStatement(node.next); | 228 Statement next = visitStatement(node.next); |
| 229 if (!environment.isEmpty && environment.last == node) { | 229 if (!environment.isEmpty && environment.last == node) { |
| 230 // The definition could not be propagated. Residualize the let binding. | 230 // The definition could not be propagated. Residualize the let binding. |
| 231 node.next = next; | 231 node.next = next; |
| 232 environment.removeLast(); | 232 environment.removeLast(); |
| 233 node.definition = visitExpression(node.definition); | 233 node.value = visitExpression(node.value); |
| 234 return node; | 234 return node; |
| 235 } | 235 } |
| 236 assert(!environment.contains(node)); | 236 assert(!environment.contains(node)); |
| 237 --node.variable.writeCount; // This assignment was removed. | 237 --node.variable.writeCount; // This assignment was removed. |
| 238 return next; | 238 return next; |
| 239 } | 239 } |
| 240 } | 240 } |
| 241 | 241 |
| 242 Expression visitInvokeStatic(InvokeStatic node) { | 242 Expression visitInvokeStatic(InvokeStatic node) { |
| 243 // Process arguments right-to-left, the opposite of evaluation order. | 243 // Process arguments right-to-left, the opposite of evaluation order. |
| (...skipping 287 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 531 return new Return(combine(s.value, t.value)); | 531 return new Return(combine(s.value, t.value)); |
| 532 } | 532 } |
| 533 if (s is Assign && t is Assign && s.variable == t.variable) { | 533 if (s is Assign && t is Assign && s.variable == t.variable) { |
| 534 Statement next = combineStatements(s.next, t.next); | 534 Statement next = combineStatements(s.next, t.next); |
| 535 if (next != null) { | 535 if (next != null) { |
| 536 // Destroy both original assignments to the variable. | 536 // Destroy both original assignments to the variable. |
| 537 --s.variable.writeCount; | 537 --s.variable.writeCount; |
| 538 --t.variable.writeCount; | 538 --t.variable.writeCount; |
| 539 // The Assign constructor will increment the reference count again. | 539 // The Assign constructor will increment the reference count again. |
| 540 return new Assign(s.variable, | 540 return new Assign(s.variable, |
| 541 combine(s.definition, t.definition), | 541 combine(s.value, t.value), |
| 542 next); | 542 next); |
| 543 } | 543 } |
| 544 } | 544 } |
| 545 if (s is ExpressionStatement && t is ExpressionStatement) { | 545 if (s is ExpressionStatement && t is ExpressionStatement) { |
| 546 Statement next = combineStatements(s.next, t.next); | 546 Statement next = combineStatements(s.next, t.next); |
| 547 if (next != null) { | 547 if (next != null) { |
| 548 return new ExpressionStatement(combine(s.expression, t.expression), | 548 return new ExpressionStatement(combine(s.expression, t.expression), |
| 549 next); | 549 next); |
| 550 } | 550 } |
| 551 } | 551 } |
| (...skipping 115 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 667 } | 667 } |
| 668 | 668 |
| 669 Expression makeCondition(Expression e, bool polarity) { | 669 Expression makeCondition(Expression e, bool polarity) { |
| 670 return polarity ? e : new Not(e); | 670 return polarity ? e : new Not(e); |
| 671 } | 671 } |
| 672 | 672 |
| 673 Statement getBranch(If node, bool polarity) { | 673 Statement getBranch(If node, bool polarity) { |
| 674 return polarity ? node.thenStatement : node.elseStatement; | 674 return polarity ? node.thenStatement : node.elseStatement; |
| 675 } | 675 } |
| 676 } | 676 } |
| OLD | NEW |