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

Side by Side Diff: pkg/compiler/lib/src/cps_ir/shrinking_reductions.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
« no previous file with comments | « pkg/compiler/lib/src/cps_ir/redundant_phi.dart ('k') | pkg/compiler/lib/src/dart2js.dart » ('j') | no next file with comments »
Toggle Intra-line Diffs ('i') | Expand Comments ('e') | Collapse Comments ('c') | Show Comments Hide Comments ('s')
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 part of dart2js.optimizers;
6
7 /**
8 * [[ShrinkingReducer]] applies shrinking reductions to CPS terms as described
9 * in 'Compiling with Continuations, Continued' by Andrew Kennedy.
10 */
11 class ShrinkingReducer implements Pass {
12 _RedexVisitor _redexVisitor;
13 Set<_ReductionTask> _worklist;
14
15 static final _DeletedNode _DELETED = new _DeletedNode();
16
17 /// Applies shrinking reductions to root, mutating root in the process.
18 void rewrite(FunctionDefinition root) {
19 if (root.isAbstract) return;
20
21 _worklist = new Set<_ReductionTask>();
22 _redexVisitor = new _RedexVisitor(_worklist);
23
24 // Set all parent pointers.
25 new _ParentVisitor().visit(root);
26
27 // Sweep over the term, collecting redexes into the worklist.
28 _redexVisitor.visitFunctionDefinition(root);
29
30 // Process the worklist.
31 while (_worklist.isNotEmpty) {
32 _ReductionTask task = _worklist.first;
33 _worklist.remove(task);
34 _processTask(task);
35 }
36 }
37
38 /// Removes the given node from the CPS graph, replacing it with its body
39 /// and marking it as deleted. The node's parent must be a [[InteriorNode]].
40 void _removeNode(InteriorNode node) {
41 Node body = node.body;
42 InteriorNode parent = node.parent;
43 assert(parent.body == node);
44
45 body.parent = parent;
46 parent.body = body;
47 node.parent = _DELETED;
48 }
49
50 void _processTask(_ReductionTask task) {
51 // Lazily skip tasks for deleted nodes.
52 if (task.node.parent == _DELETED) {
53 return;
54 }
55
56 switch (task.kind) {
57 case _ReductionKind.DEAD_VAL:
58 _reduceDeadVal(task);
59 break;
60 case _ReductionKind.DEAD_CONT:
61 _reduceDeadCont(task);
62 break;
63 case _ReductionKind.BETA_CONT_LIN:
64 _reduceBetaContLin(task);
65 break;
66 case _ReductionKind.ETA_CONT:
67 _reduceEtaCont(task);
68 break;
69 default:
70 assert(false);
71 }
72 }
73
74 /// Applies the dead-val reduction:
75 /// letprim x = V in E -> E (x not free in E).
76 void _reduceDeadVal(_ReductionTask task) {
77 assert(_isDeadVal(task.node));
78
79 // Remove dead primitive.
80 LetPrim letPrim = task.node;;
81 _removeNode(letPrim);
82
83 // Perform bookkeeping on removed body and scan for new redexes.
84 new _RemovalRedexVisitor(_worklist).visit(letPrim.primitive);
85 }
86
87 /// Applies the dead-cont reduction:
88 /// letcont k x = E0 in E1 -> E1 (k not free in E1).
89 void _reduceDeadCont(_ReductionTask task) {
90 assert(_isDeadCont(task.node));
91
92 // Remove dead continuation.
93 LetCont letCont = task.node;
94 _removeNode(letCont);
95
96 // Perform bookkeeping on removed body and scan for new redexes.
97 new _RemovalRedexVisitor(_worklist).visit(letCont.continuation);
98 }
99
100 /// Applies the beta-cont-lin reduction:
101 /// letcont k x = E0 in E1[k y] -> E1[E0[y/x]] (k not free in E1).
102 void _reduceBetaContLin(_ReductionTask task) {
103 // Might have been mutated, recheck if reduction is still valid.
104 // In the following example, the beta-cont-lin reduction of k0 could have
105 // been invalidated by removal of the dead continuation k1:
106 //
107 // letcont k0 x0 = E0 in
108 // letcont k1 x1 = k0 x1 in
109 // return x2
110 if (!_isBetaContLin(task.node)) {
111 return;
112 }
113
114 // Remove the continuation.
115 LetCont letCont = task.node;
116 Continuation cont = letCont.continuation;
117 _removeNode(letCont);
118
119 // Replace its invocation with the continuation body.
120 InvokeContinuation invoke = cont.firstRef.parent;
121 InteriorNode invokeParent = invoke.parent;
122
123 cont.body.parent = invokeParent;
124 invokeParent.body = cont.body;
125
126 // Substitute the invocation argument for the continuation parameter.
127 for (int i = 0; i < invoke.arguments.length; i++) {
128 Reference argRef = invoke.arguments[i];
129 argRef.definition.substituteFor(cont.parameters[i]);
130 }
131
132 // Perform bookkeeping on removed body and scan for new redexes.
133 new _RemovalRedexVisitor(_worklist).visit(invoke);
134 }
135
136 /// Applies the eta-cont reduction:
137 /// letcont k x = j x in E -> E[j/k].
138 /// If k is unused, degenerates to dead-cont.
139 void _reduceEtaCont(_ReductionTask task) {
140 // Might have been mutated, recheck if reduction is still valid.
141 // In the following example, the eta-cont reduction of k1 could have been
142 // invalidated by an earlier beta-cont-lin reduction of k0.
143 //
144 // letcont k0 x0 = E0 in
145 // letcont k1 x1 = k0 x1 in E1
146 if (!_isEtaCont(task.node)) {
147 return;
148 }
149
150 // Remove the continuation.
151 LetCont letCont = task.node;
152 Continuation cont = letCont.continuation;
153 _removeNode(letCont);
154
155 InvokeContinuation invoke = cont.body;
156 Continuation wrappedCont = invoke.continuation.definition;
157
158 // Replace all occurrences with the wrapped continuation.
159 wrappedCont.substituteFor(cont);
160
161 // Perform bookkeeping on removed body and scan for new redexes.
162 new _RemovalRedexVisitor(_worklist).visit(cont);
163 }
164 }
165
166 /// Returns true iff the bound primitive is unused.
167 bool _isDeadVal(LetPrim node) => !node.primitive.hasAtLeastOneUse;
168
169 /// Returns true iff the bound continuation is unused.
170 bool _isDeadCont(LetCont node) => !node.continuation.hasAtLeastOneUse;
171
172 /// Returns true iff the bound continuation is used exactly once, and that
173 /// use is as the receiver of a continuation invocation.
174 bool _isBetaContLin(LetCont node) {
175 Continuation cont = node.continuation;
176 if (!cont.hasExactlyOneUse) {
177 return false;
178 }
179
180 if (cont.firstRef.parent is InvokeContinuation) {
181 InvokeContinuation invoke = cont.firstRef.parent;
182 return (cont == invoke.continuation.definition);
183 }
184
185 return false;
186
187 }
188
189 /// Returns true iff the bound continuation consists of a continuation
190 /// invocation, passing on all parameters. Special cases exist (see below).
191 bool _isEtaCont(LetCont node) {
192 Continuation cont = node.continuation;
193 if (!(cont.body is InvokeContinuation)) {
194 return false;
195 }
196
197 InvokeContinuation invoke = cont.body;
198 Continuation invokedCont = invoke.continuation.definition;
199
200 // Do not eta-reduce return join-points since the resulting code is worse
201 // in the common case (i.e. returns are moved inside `if` branches).
202 if (invokedCont.isReturnContinuation) {
203 return false;
204 }
205
206 // Translation to direct style generates different statements for recursive
207 // and non-recursive invokes. It should be possible to apply eta-cont, but
208 // higher order continuations require escape analysis, left as a possibility
209 // for future improvements.
210 if (invoke.isRecursive) {
211 return false;
212 }
213
214 if (cont.parameters.length != invoke.arguments.length) {
215 return false;
216 }
217
218 // TODO(jgruber): Linear in the parameter count. Can be improved to near
219 // constant time by using union-find data structure.
220 for (int i = 0; i < cont.parameters.length; i++) {
221 if (invoke.arguments[i].definition != cont.parameters[i]) {
222 return false;
223 }
224 }
225
226 return true;
227 }
228
229 /// Traverses a term and adds any found redexes to the worklist.
230 class _RedexVisitor extends RecursiveVisitor {
231 final Set<_ReductionTask> worklist;
232
233 _RedexVisitor(this.worklist);
234
235 void processLetPrim(LetPrim node) {
236 if (node.parent == ShrinkingReducer._DELETED) {
237 return;
238 } else if (_isDeadVal(node)) {
239 worklist.add(new _ReductionTask(_ReductionKind.DEAD_VAL, node));
240 }
241 }
242
243 void processLetCont(LetCont node) {
244 if (node.parent == ShrinkingReducer._DELETED) {
245 return;
246 } else if (_isDeadCont(node)) {
247 worklist.add(new _ReductionTask(_ReductionKind.DEAD_CONT, node));
248 } else if (_isEtaCont(node)) {
249 worklist.add(new _ReductionTask(_ReductionKind.ETA_CONT, node));
250 } else if (_isBetaContLin(node)){
251 worklist.add(new _ReductionTask(_ReductionKind.BETA_CONT_LIN, node));
252 }
253 }
254 }
255
256 /// Traverses a deleted CPS term, marking existing tasks associated with a node
257 /// within the term as deleted (which causes them to be skipped lazily when
258 /// popped from the worklist), and adding newly created redexes to the worklist.
259 class _RemovalRedexVisitor extends _RedexVisitor {
260 _RemovalRedexVisitor(Set<_ReductionTask> worklist) : super(worklist);
261
262 void processLetPrim(LetPrim node) {
263 node.parent = ShrinkingReducer._DELETED;
264 }
265
266 void processLetCont(LetCont node) {
267 node.parent = ShrinkingReducer._DELETED;
268 }
269
270 void processReference(Reference reference) {
271 reference.unlink();
272
273 if (reference.definition is Primitive) {
274 Primitive primitive = reference.definition;
275 Node parent = primitive.parent;
276 if (parent is LetPrim && _isDeadVal(parent)) {
277 worklist.add(new _ReductionTask(_ReductionKind.DEAD_VAL, parent));
278 }
279 } else if (reference.definition is Continuation) {
280 Continuation cont = reference.definition;
281 if (cont.isRecursive && cont.hasAtMostOneUse) {
282 // Convert recursive to nonrecursive continuations.
283 // If the continuation is still in use, it is either dead and will be
284 // removed, or it is called nonrecursively outside its body.
285 cont.isRecursive = false;
286 }
287 Node parent = cont.parent;
288 if (parent is LetCont && _isDeadCont(parent)) {
289 worklist.add(new _ReductionTask(_ReductionKind.DEAD_CONT, parent));
290 }
291 }
292 }
293 }
294
295 /// Traverses the CPS term and sets node.parent for each visited node.
296 class _ParentVisitor extends RecursiveVisitor {
297
298 processFunctionDefinition(FunctionDefinition node) {
299 node.body.parent = node;
300 node.parameters.forEach((Parameter p) => p.parent = node);
301 }
302
303 // Expressions.
304
305 processLetPrim(LetPrim node) {
306 node.primitive.parent = node;
307 node.body.parent = node;
308 }
309
310 processLetCont(LetCont node) {
311 node.continuation.parent = node;
312 node.body.parent = node;
313 }
314
315 processInvokeStatic(InvokeStatic node) {
316 node.continuation.parent = node;
317 node.arguments.forEach((Reference ref) => ref.parent = node);
318 }
319
320 processInvokeContinuation(InvokeContinuation node) {
321 node.continuation.parent = node;
322 node.arguments.forEach((Reference ref) => ref.parent = node);
323 }
324
325 processInvokeMethod(InvokeMethod node) {
326 node.receiver.parent = node;
327 node.continuation.parent = node;
328 node.arguments.forEach((Reference ref) => ref.parent = node);
329 }
330
331 processInvokeSuperMethod(InvokeSuperMethod node) {
332 node.continuation.parent = node;
333 node.arguments.forEach((Reference ref) => ref.parent = node);
334 }
335
336 processInvokeConstructor(InvokeConstructor node) {
337 node.continuation.parent = node;
338 node.arguments.forEach((Reference ref) => ref.parent = node);
339 }
340
341 processConcatenateStrings(ConcatenateStrings node) {
342 node.continuation.parent = node;
343 node.arguments.forEach((Reference ref) => ref.parent = node);
344 }
345
346 processBranch(Branch node) {
347 node.condition.parent = node;
348 node.trueContinuation.parent = node;
349 node.falseContinuation.parent = node;
350 }
351
352 processTypeOperator(TypeOperator node) {
353 node.continuation.parent = node;
354 node.receiver.parent = node;
355 }
356
357 processSetClosureVariable(SetClosureVariable node) {
358 node.body.parent = node;
359 node.value.parent = node;
360 }
361
362 processDeclareFunction(DeclareFunction node) {
363 node.definition.parent = node;
364 node.body.parent = node;
365 }
366
367 // Definitions.
368
369 processLiteralList(LiteralList node) {
370 node.values.forEach((Reference ref) => ref.parent = node);
371 }
372
373 processLiteralMap(LiteralMap node) {
374 node.entries.forEach((LiteralMapEntry entry) {
375 entry.key.parent = node;
376 entry.value.parent = node;
377 });
378 }
379
380 processCreateFunction(CreateFunction node) {
381 node.definition.parent = node;
382 }
383
384 processContinuation(Continuation node) {
385 node.body.parent = node;
386 node.parameters.forEach((Parameter param) => param.parent = node);
387 }
388
389 // Conditions.
390
391 processIsTrue(IsTrue node) {
392 node.value.parent = node;
393 }
394 }
395
396 class _ReductionKind {
397 final String name;
398 final int hashCode;
399
400 const _ReductionKind(this.name, this.hashCode);
401
402 static const _ReductionKind DEAD_VAL = const _ReductionKind('dead-val', 0);
403 static const _ReductionKind DEAD_CONT = const _ReductionKind('dead-cont', 1);
404 static const _ReductionKind BETA_CONT_LIN =
405 const _ReductionKind('beta-cont-lin', 2);
406 static const _ReductionKind ETA_CONT = const _ReductionKind('eta-cont', 3);
407
408 String toString() => name;
409 }
410
411 /// Represents a reduction task on the worklist. Implements both hashCode and
412 /// operator== since instantiations are used as Set elements.
413 class _ReductionTask {
414 final _ReductionKind kind;
415 final Node node;
416
417 int get hashCode {
418 assert(kind.hashCode < (1 << 2));
419 return (node.hashCode << 2) | kind.hashCode;
420 }
421
422 _ReductionTask(this.kind, this.node) {
423 // If new node types are added, they must be marked as deleted in
424 // [[_RemovalRedexVisitor]].
425 assert(node is LetCont || node is LetPrim);
426 }
427
428 bool operator==(_ReductionTask that) {
429 return (that.kind == this.kind && that.node == this.node);
430 }
431
432 String toString() => "$kind: $node";
433 }
434
435 /// A dummy class used solely to mark nodes as deleted once they are removed
436 /// from a term.
437 class _DeletedNode extends Node {
438 accept(_) => null;
439 }
OLDNEW
« no previous file with comments | « pkg/compiler/lib/src/cps_ir/redundant_phi.dart ('k') | pkg/compiler/lib/src/dart2js.dart » ('j') | no next file with comments »

Powered by Google App Engine
This is Rietveld 408576698