Chromium Code Reviews
chromiumcodereview-hr@appspot.gserviceaccount.com (chromiumcodereview-hr) | Please choose your nickname with Settings | Help | Chromium Project | Gerrit Changes | Sign out
(169)

Side by Side Diff: pkg/compiler/lib/src/dart_backend/copy_propagator.dart

Issue 693183006: Revert "Move dart2js from sdk/lib/_internal/compiler to pkg/compiler" (Closed) Base URL: https://dart.googlecode.com/svn/branches/bleeding_edge/dart
Patch Set: Created 6 years, 1 month ago
Use n/p to move between diff chunks; N/P to move between comments. Draft comments are only viewable by you.
Jump to:
View unified diff | Download patch | Annotate | Revision Log
OLDNEW
(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 copy_propagator;
6
7 import '../elements/elements.dart';
8 import 'tree_ir_nodes.dart';
9
10 /// Eliminates moving assignments, such as w := v, by assigning directly to w
11 /// at the definition of v.
12 ///
13 /// This compensates for suboptimal register allocation, and merges closure
14 /// variables with local temporaries that were left behind when translating
15 /// out of CPS (where closure variables live in a separate space).
16 class CopyPropagator extends RecursiveVisitor {
17
18 /// After visitStatement returns, [move] maps a variable v to an
19 /// assignment A of form w := v, under the following conditions:
20 /// - there are no uses of w before A
21 /// - A is the only use of v
22 Map<Variable, Assign> move = <Variable, Assign>{};
23
24 /// Like [move], except w is the key instead of v.
25 Map<Variable, Assign> inverseMove = <Variable, Assign>{};
26
27 /// The function currently being rewritten.
28 FunctionElement functionElement;
29
30 void rewrite(FunctionDefinition function) {
31 if (function.isAbstract) return;
32
33 functionElement = function.element;
34 visitFunctionDefinition(function);
35 }
36
37 void visitFunctionDefinition(FunctionDefinition function) {
38 assert(functionElement == function.element);
39 function.body = visitStatement(function.body);
40
41 // Try to propagate moving assignments into function parameters.
42 // For example:
43 // foo(x) {
44 // var v1 = x;
45 // BODY
46 // }
47 // ==>
48 // foo(v1) {
49 // BODY
50 // }
51
52 // Variables must not occur more than once in the parameter list, so
53 // invalidate all moving assignments that would propagate a parameter
54 // into another parameter. For example:
55 // foo(x,y) {
56 // y = x;
57 // BODY
58 // }
59 // Cannot declare function as foo(x,x)!
60 function.parameters.forEach(visitVariable);
61
62 // Now do the propagation.
63 for (int i=0; i<function.parameters.length; i++) {
64 Variable param = function.parameters[i];
65 Variable replacement = copyPropagateVariable(param);
66 replacement.element = param.element; // Preserve parameter name.
67 function.parameters[i] = replacement;
68 }
69 }
70
71 Statement visitBasicBlock(Statement node) {
72 node = visitStatement(node);
73 move.clear();
74 inverseMove.clear();
75 return node;
76 }
77
78 void visitVariable(Variable variable) {
79 // We have found a use of w.
80 // Remove assignments of form w := v from the move maps.
81 Assign movingAssignment = inverseMove.remove(variable);
82 if (movingAssignment != null) {
83 move.remove(movingAssignment.definition);
84 }
85 }
86
87 /**
88 * Called when a definition of [v] is encountered.
89 * Attempts to propagate the assignment through a moving assignment.
90 * Returns the variable to be assigned into, defaulting to [v] itself if
91 * no optimization could be performed.
92 */
93 Variable copyPropagateVariable(Variable v) {
94 Assign movingAssign = move[v];
95 if (movingAssign != null) {
96 // We found the pattern:
97 // v := EXPR
98 // BLOCK (does not use w)
99 // w := v (only use of v)
100 //
101 // Rewrite to:
102 // w := EXPR
103 // BLOCK
104 // w := w (to be removed later)
105 Variable w = movingAssign.variable;
106
107 // Make w := w.
108 // We can't remove the statement from here because we don't have
109 // parent pointers. So just make it a no-op so it can be removed later.
110 movingAssign.definition = w;
111
112 // The intermediate variable 'v' should now be orphaned, so don't bother
113 // updating its read/write counters.
114 // Due to the nop trick, the variable 'w' now has one additional read
115 // and write.
116 ++w.writeCount;
117 ++w.readCount;
118
119 // Make w := EXPR
120 return w;
121 }
122 return v;
123 }
124
125 Statement visitAssign(Assign node) {
126 node.next = visitStatement(node.next);
127 node.variable = copyPropagateVariable(node.variable);
128 visitExpression(node.definition);
129 visitVariable(node.variable);
130
131 // If this is a moving assignment w := v, with this being the only use of v,
132 // try to propagate it backwards. Do not propagate assignments where w
133 // is from an outer function scope.
134 if (node.definition is Variable) {
135 Variable def = node.definition;
136 if (def.readCount == 1 &&
137 node.variable.host.element == functionElement) {
138 move[node.definition] = node;
139 inverseMove[node.variable] = node;
140 }
141 }
142
143 return node;
144 }
145
146 Statement visitLabeledStatement(LabeledStatement node) {
147 node.next = visitBasicBlock(node.next);
148 node.body = visitStatement(node.body);
149 return node;
150 }
151
152 Statement visitReturn(Return node) {
153 visitExpression(node.value);
154 return node;
155 }
156
157 Statement visitBreak(Break node) {
158 return node;
159 }
160
161 Statement visitContinue(Continue node) {
162 return node;
163 }
164
165 Statement visitIf(If node) {
166 visitExpression(node.condition);
167 node.thenStatement = visitBasicBlock(node.thenStatement);
168 node.elseStatement = visitBasicBlock(node.elseStatement);
169 return node;
170 }
171
172 Statement visitWhileTrue(WhileTrue node) {
173 node.body = visitBasicBlock(node.body);
174 return node;
175 }
176
177 Statement visitWhileCondition(WhileCondition node) {
178 throw "WhileCondition before LoopRewriter";
179 }
180
181 Statement visitFunctionDeclaration(FunctionDeclaration node) {
182 // Unlike var declarations, function declarations are not hoisted, so we
183 // can't do copy propagation of the variable.
184 new CopyPropagator().rewrite(node.definition);
185 node.next = visitStatement(node.next);
186 return node;
187 }
188
189 Statement visitExpressionStatement(ExpressionStatement node) {
190 node.next = visitStatement(node.next);
191 visitExpression(node.expression);
192 return node;
193 }
194
195 void visitFunctionExpression(FunctionExpression node) {
196 new CopyPropagator().rewrite(node.definition);
197 }
198
199 }
OLDNEW

Powered by Google App Engine
This is Rietveld 408576698