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 dart_tree; | 5 library dart_tree; |
6 | 6 |
7 import '../dart2jslib.dart' as dart2js; | 7 import '../dart2jslib.dart' as dart2js; |
8 import '../elements/elements.dart'; | 8 import '../elements/elements.dart'; |
9 import '../universe/universe.dart'; | 9 import '../universe/universe.dart'; |
10 import '../ir/ir_nodes.dart' as ir; | 10 import '../ir/ir_nodes.dart' as ir; |
(...skipping 404 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
415 } | 415 } |
416 | 416 |
417 /** | 417 /** |
418 * An assignments of an [Expression] to a [Variable]. | 418 * An assignments of an [Expression] to a [Variable]. |
419 * | 419 * |
420 * In contrast to the CPS-based IR, non-primitive expressions can be assigned | 420 * In contrast to the CPS-based IR, non-primitive expressions can be assigned |
421 * to variables. | 421 * to variables. |
422 */ | 422 */ |
423 class Assign extends Statement { | 423 class Assign extends Statement { |
424 Statement next; | 424 Statement next; |
425 final Variable variable; | 425 Variable variable; |
426 Expression definition; | 426 Expression definition; |
427 | 427 |
428 /// If true, this declares a new copy of the closure variable. | 428 /// If true, this declares a new copy of the closure variable. |
429 /// The consequences are similar to [ir.SetClosureVariable]. | 429 /// The consequences are similar to [ir.SetClosureVariable]. |
430 /// All uses of the variable must be nested inside the [next] statement. | 430 /// All uses of the variable must be nested inside the [next] statement. |
431 bool isDeclaration; | 431 bool isDeclaration; |
432 | 432 |
433 Assign(this.variable, this.definition, this.next, | 433 Assign(this.variable, this.definition, this.next, |
434 { this.isDeclaration: false }) { | 434 { this.isDeclaration: false }) { |
435 variable.writeCount++; | 435 variable.writeCount++; |
(...skipping 667 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
1103 // visited. | 1103 // visited. |
1104 compiler.internalError(compiler.currentElement, 'Unexpected IR node.'); | 1104 compiler.internalError(compiler.currentElement, 'Unexpected IR node.'); |
1105 return null; | 1105 return null; |
1106 } | 1106 } |
1107 | 1107 |
1108 Expression visitIsTrue(ir.IsTrue node) { | 1108 Expression visitIsTrue(ir.IsTrue node) { |
1109 return getVariableReference(node.value); | 1109 return getVariableReference(node.value); |
1110 } | 1110 } |
1111 } | 1111 } |
1112 | 1112 |
1113 /// Eliminates redundant variables and assignments that occur immediately after | |
1114 /// parameters are declared or after a function declaration. | |
1115 /// | |
1116 /// These patterns arise when translating out of CPS where closure variables | |
1117 /// live in a separate space. Since function parameters are IR primitives they | |
1118 /// must be moved into a separate closure variable for inner functions to access | |
1119 /// them. For example: | |
1120 /// | |
1121 /// foo(x) { | |
1122 /// let v1 = ref x in BODY | |
1123 /// } | |
1124 /// ==> (dart_tree Builder) | |
1125 /// foo(x) { | |
1126 /// var v1 = x; | |
1127 /// BODY.. | |
1128 /// } | |
1129 /// | |
1130 /// This phase attempts to merge v1 and x in the example above. | |
1131 /// A similar pattern can occur for local function declarations that are used | |
1132 /// from closures. | |
1133 class CopyPropagateClosureVariables extends RecursiveVisitor { | |
1134 | |
1135 void rewrite(FunctionDefinition definition) { | |
1136 visitFunctionDefinition(definition); | |
1137 } | |
1138 | |
1139 /// Performs the rewrite: | |
1140 /// | |
1141 /// foo(x) { var v0 = x; S } | |
1142 /// ==> (move v0 into parameter) | |
1143 /// foo(v0) { S } | |
1144 /// ==> (change the name of v0 to be x, so we preserve the parameter name) | |
1145 /// foo(x) { S[v0\x] } | |
1146 /// | |
1147 /// Condition: x cannot be used anywhere else. | |
1148 visitFunctionDefinition(FunctionDefinition definition) { | |
1149 while (definition.body is Assign) { | |
1150 Assign assign = definition.body; | |
1151 if (assign.definition is! Variable) break; | |
1152 | |
1153 Variable rightHand = assign.definition; | |
1154 if (rightHand.readCount != 1) break; | |
1155 | |
1156 int paramIndex = definition.parameters.indexOf(rightHand); | |
1157 if (paramIndex == -1) break; | |
1158 | |
1159 // A variable may not occur as a parameter more than once. | |
1160 if (definition.parameters.contains(assign.variable)) break; | |
1161 | |
1162 definition.parameters[paramIndex] = assign.variable; | |
1163 assign.variable.element = rightHand.element; | |
1164 definition.body = assign.next; | |
1165 } | |
1166 | |
1167 visitStatement(definition.body); // Visit nested function definitions. | |
1168 } | |
1169 | |
1170 /// Performs the rewrite: | |
1171 /// | |
1172 /// int v0() { S } | |
1173 /// foo = v0; | |
1174 /// ==> | |
1175 /// int foo() { S } | |
1176 /// | |
1177 /// Condition: v0 cannot be used anywhere else. | |
1178 visitFunctionDeclaration(FunctionDeclaration node) { | |
1179 Statement next = node.next; | |
1180 if (next is Assign && | |
1181 next.definition == node.variable && | |
1182 node.variable.readCount == 1 && | |
1183 next.variable.writeCount == 1) { | |
1184 node.variable = next.variable; | |
1185 node.next = next.next; | |
1186 } | |
1187 super.visitFunctionDeclaration(node); | |
1188 } | |
1189 | |
1190 } | |
1191 | 1113 |
1192 /** | 1114 /** |
1193 * Performs the following transformations on the tree: | 1115 * Performs the following transformations on the tree: |
1194 * - Assignment propagation | 1116 * - Assignment propagation |
1195 * - If-to-conditional conversion | 1117 * - If-to-conditional conversion |
1196 * - Flatten nested ifs | 1118 * - Flatten nested ifs |
1197 * - Break inlining | 1119 * - Break inlining |
1198 * - Redirect breaks | 1120 * - Redirect breaks |
1199 * | 1121 * |
1200 * The above transformations all eliminate statements from the tree, and may | 1122 * The above transformations all eliminate statements from the tree, and may |
(...skipping 525 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
1726 | 1648 |
1727 Expression makeCondition(Expression e, bool polarity) { | 1649 Expression makeCondition(Expression e, bool polarity) { |
1728 return polarity ? e : new Not(e); | 1650 return polarity ? e : new Not(e); |
1729 } | 1651 } |
1730 | 1652 |
1731 Statement getBranch(If node, bool polarity) { | 1653 Statement getBranch(If node, bool polarity) { |
1732 return polarity ? node.thenStatement : node.elseStatement; | 1654 return polarity ? node.thenStatement : node.elseStatement; |
1733 } | 1655 } |
1734 } | 1656 } |
1735 | 1657 |
| 1658 /// Eliminates moving assignments, such as w := v, by assigning directly to w |
| 1659 /// at the definition of v. |
| 1660 /// |
| 1661 /// This compensates for suboptimal register allocation, and merges closure |
| 1662 /// variables with local temporaries that were left behind when translating |
| 1663 /// out of CPS (where closure variables live in a separate space). |
| 1664 class CopyPropagator extends RecursiveVisitor { |
| 1665 |
| 1666 /// After visitStatement returns, [move] maps a variable v to an |
| 1667 /// assignment A of form w := v, under the following conditions: |
| 1668 /// - there are no uses of w before A |
| 1669 /// - A is the only use of v |
| 1670 Map<Variable, Assign> move = <Variable, Assign>{}; |
| 1671 |
| 1672 /// Like [move], except w is the key instead of v. |
| 1673 Map<Variable, Assign> inverseMove = <Variable, Assign>{}; |
| 1674 |
| 1675 void rewrite(FunctionDefinition function) { |
| 1676 visitFunctionDefinition(function); |
| 1677 } |
| 1678 |
| 1679 void visitFunctionDefinition(FunctionDefinition function) { |
| 1680 function.body = visitStatement(function.body); |
| 1681 |
| 1682 // Try to propagate moving assignments into function parameters. |
| 1683 // For example: |
| 1684 // foo(x) { |
| 1685 // var v1 = x; |
| 1686 // BODY |
| 1687 // } |
| 1688 // ==> |
| 1689 // foo(v1) { |
| 1690 // BODY |
| 1691 // } |
| 1692 |
| 1693 // Variables must not occur more than once in the parameter list, so |
| 1694 // invalidate all moving assignments that would propagate a parameter |
| 1695 // into another parameter. For example: |
| 1696 // foo(x,y) { |
| 1697 // y = x; |
| 1698 // BODY |
| 1699 // } |
| 1700 // Cannot declare function as foo(x,x)! |
| 1701 function.parameters.forEach(visitVariable); |
| 1702 |
| 1703 // Now do the propagation. |
| 1704 for (int i=0; i<function.parameters.length; i++) { |
| 1705 Variable param = function.parameters[i]; |
| 1706 Variable replacement = copyPropagateVariable(param); |
| 1707 replacement.element = param.element; // Preserve parameter name. |
| 1708 function.parameters[i] = replacement; |
| 1709 } |
| 1710 } |
| 1711 |
| 1712 Statement visitBasicBlock(Statement node) { |
| 1713 node = visitStatement(node); |
| 1714 move.clear(); |
| 1715 inverseMove.clear(); |
| 1716 return node; |
| 1717 } |
| 1718 |
| 1719 void visitVariable(Variable variable) { |
| 1720 // We have found a use of w. |
| 1721 // Remove assignments of form w := v from the move maps. |
| 1722 Assign movingAssignment = inverseMove.remove(variable); |
| 1723 if (movingAssignment != null) { |
| 1724 move.remove(movingAssignment.definition); |
| 1725 } |
| 1726 } |
| 1727 |
| 1728 /** |
| 1729 * Called when a definition of [v] is encountered. |
| 1730 * Attempts to propagate the assignment through a moving assignment. |
| 1731 * Returns the variable to be assigned into, defaulting to [v] itself if |
| 1732 * no optimization could be performed. |
| 1733 */ |
| 1734 Variable copyPropagateVariable(Variable v) { |
| 1735 Assign movingAssign = move[v]; |
| 1736 if (movingAssign != null) { |
| 1737 // We found the pattern: |
| 1738 // v := EXPR |
| 1739 // BLOCK (does not use w) |
| 1740 // w := v (only use of v) |
| 1741 // |
| 1742 // Rewrite to: |
| 1743 // w := EXPR |
| 1744 // BLOCK |
| 1745 // w := w (to be removed later) |
| 1746 Variable w = movingAssign.variable; |
| 1747 |
| 1748 // Make w := w. |
| 1749 // We can't remove the statement from here because we don't have |
| 1750 // parent pointers. So just make it a no-op so it can be removed later. |
| 1751 movingAssign.definition = w; |
| 1752 |
| 1753 // The intermediate variable 'v' should now be orphaned, so don't bother |
| 1754 // updating its read/write counters. |
| 1755 // Due to the nop trick, the variable 'w' now has one additional read |
| 1756 // and write. |
| 1757 ++w.writeCount; |
| 1758 ++w.readCount; |
| 1759 |
| 1760 // Make w := EXPR |
| 1761 return w; |
| 1762 } |
| 1763 return v; |
| 1764 } |
| 1765 |
| 1766 Statement visitAssign(Assign node) { |
| 1767 node.next = visitStatement(node.next); |
| 1768 node.variable = copyPropagateVariable(node.variable); |
| 1769 visitExpression(node.definition); |
| 1770 visitVariable(node.variable); |
| 1771 |
| 1772 // If this is a moving assignment w := v, with this being the only use of v, |
| 1773 // try to propagate it backwards. |
| 1774 if (node.definition is Variable) { |
| 1775 Variable def = node.definition; |
| 1776 if (def.readCount == 1) { |
| 1777 move[node.definition] = node; |
| 1778 inverseMove[node.variable] = node; |
| 1779 } |
| 1780 } |
| 1781 |
| 1782 return node; |
| 1783 } |
| 1784 |
| 1785 Statement visitLabeledStatement(LabeledStatement node) { |
| 1786 node.next = visitBasicBlock(node.next); |
| 1787 node.body = visitStatement(node.body); |
| 1788 return node; |
| 1789 } |
| 1790 |
| 1791 Statement visitReturn(Return node) { |
| 1792 visitExpression(node.value); |
| 1793 return node; |
| 1794 } |
| 1795 |
| 1796 Statement visitBreak(Break node) { |
| 1797 return node; |
| 1798 } |
| 1799 |
| 1800 Statement visitContinue(Continue node) { |
| 1801 return node; |
| 1802 } |
| 1803 |
| 1804 Statement visitIf(If node) { |
| 1805 visitExpression(node.condition); |
| 1806 node.thenStatement = visitBasicBlock(node.thenStatement); |
| 1807 node.elseStatement = visitBasicBlock(node.elseStatement); |
| 1808 return node; |
| 1809 } |
| 1810 |
| 1811 Statement visitWhileTrue(WhileTrue node) { |
| 1812 node.body = visitBasicBlock(node.body); |
| 1813 return node; |
| 1814 } |
| 1815 |
| 1816 Statement visitWhileCondition(WhileCondition node) { |
| 1817 throw "WhileCondition before LoopRewriter"; |
| 1818 } |
| 1819 |
| 1820 Statement visitFunctionDeclaration(FunctionDeclaration node) { |
| 1821 new CopyPropagator().visitFunctionDefinition(node.definition); |
| 1822 node.next = visitStatement(node.next); |
| 1823 node.variable = copyPropagateVariable(node.variable); |
| 1824 return node; |
| 1825 } |
| 1826 |
| 1827 Statement visitExpressionStatement(ExpressionStatement node) { |
| 1828 visitExpression(node.expression); |
| 1829 node.next = visitStatement(node.next); |
| 1830 return node; |
| 1831 } |
| 1832 |
| 1833 void visitFunctionExpression(FunctionExpression node) { |
| 1834 new CopyPropagator().visitFunctionDefinition(node.definition); |
| 1835 } |
| 1836 |
| 1837 } |
| 1838 |
1736 /// Rewrites [WhileTrue] statements with an [If] body into a [WhileCondition], | 1839 /// Rewrites [WhileTrue] statements with an [If] body into a [WhileCondition], |
1737 /// in situations where only one of the branches contains a [Continue] to the | 1840 /// in situations where only one of the branches contains a [Continue] to the |
1738 /// loop. Schematically: | 1841 /// loop. Schematically: |
1739 /// | 1842 /// |
1740 /// L: | 1843 /// L: |
1741 /// while (true) { | 1844 /// while (true) { |
1742 /// if (E) { | 1845 /// if (E) { |
1743 /// S1 (has references to L) | 1846 /// S1 (has references to L) |
1744 /// } else { | 1847 /// } else { |
1745 /// S2 (has no references to L) | 1848 /// S2 (has no references to L) |
(...skipping 18 matching lines...) Expand all Loading... |
1764 function.body = visitStatement(function.body); | 1867 function.body = visitStatement(function.body); |
1765 } | 1868 } |
1766 | 1869 |
1767 Statement visitLabeledStatement(LabeledStatement node) { | 1870 Statement visitLabeledStatement(LabeledStatement node) { |
1768 node.body = visitStatement(node.body); | 1871 node.body = visitStatement(node.body); |
1769 node.next = visitStatement(node.next); | 1872 node.next = visitStatement(node.next); |
1770 return node; | 1873 return node; |
1771 } | 1874 } |
1772 | 1875 |
1773 Statement visitAssign(Assign node) { | 1876 Statement visitAssign(Assign node) { |
| 1877 // Clean up redundant assignments left behind in the previous phase. |
| 1878 if (node.variable == node.definition) { |
| 1879 --node.variable.readCount; |
| 1880 --node.variable.writeCount; |
| 1881 return visitStatement(node.next); |
| 1882 } |
1774 visitExpression(node.definition); | 1883 visitExpression(node.definition); |
1775 node.next = visitStatement(node.next); | 1884 node.next = visitStatement(node.next); |
1776 return node; | 1885 return node; |
1777 } | 1886 } |
1778 | 1887 |
1779 Statement visitReturn(Return node) { | 1888 Statement visitReturn(Return node) { |
1780 visitExpression(node.value); | 1889 visitExpression(node.value); |
1781 return node; | 1890 return node; |
1782 } | 1891 } |
1783 | 1892 |
(...skipping 504 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
2288 } | 2397 } |
2289 | 2398 |
2290 /// Destructively updates each entry of [l] with the result of visiting it. | 2399 /// Destructively updates each entry of [l] with the result of visiting it. |
2291 void _rewriteList(List<Expression> l) { | 2400 void _rewriteList(List<Expression> l) { |
2292 for (int i = 0; i < l.length; i++) { | 2401 for (int i = 0; i < l.length; i++) { |
2293 l[i] = visitExpression(l[i]); | 2402 l[i] = visitExpression(l[i]); |
2294 } | 2403 } |
2295 } | 2404 } |
2296 } | 2405 } |
2297 | 2406 |
OLD | NEW |