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

Side by Side Diff: pkg/compiler/lib/src/tree_ir/tree_ir_builder.dart

Issue 1251083002: dart2js cps: Avoid deep recursion using trampolines and basic blocks. (Closed) Base URL: git@github.com:dart-lang/sdk.git@master
Patch Set: Fix a comment Created 5 years, 5 months 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
OLDNEW
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 tree_ir_builder; 5 library tree_ir_builder;
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 '../cps_ir/cps_ir_nodes.dart' as cps_ir; 9 import '../cps_ir/cps_ir_nodes.dart' as cps_ir;
10 import '../util/util.dart' show CURRENT_ELEMENT_SPANNABLE; 10 import '../util/util.dart' show CURRENT_ELEMENT_SPANNABLE;
11 import 'tree_ir_nodes.dart'; 11 import 'tree_ir_nodes.dart';
12 12
13 typedef Statement NodeCallback(Statement next);
14
13 /** 15 /**
14 * Builder translates from CPS-based IR to direct-style Tree. 16 * Builder translates from CPS-based IR to direct-style Tree.
15 * 17 *
16 * A call `Invoke(fun, cont, args)`, where cont is a singly-referenced 18 * A call `Invoke(fun, cont, args)`, where cont is a singly-referenced
17 * non-exit continuation `Cont(v, body)` is translated into a direct-style call 19 * non-exit continuation `Cont(v, body)` is translated into a direct-style call
18 * whose value is bound in the continuation body: 20 * whose value is bound in the continuation body:
19 * 21 *
20 * `LetVal(v, Invoke(fun, args), body)` 22 * `LetVal(v, Invoke(fun, args), body)`
21 * 23 *
22 * and the continuation definition is eliminated. A similar translation is 24 * and the continuation definition is eliminated. A similar translation is
(...skipping 12 matching lines...) Expand all
35 * `LetLabel(L, v, body)` 37 * `LetLabel(L, v, body)`
36 * 38 *
37 * Block arguments are later replaced with data flow during the Tree-to-Tree 39 * Block arguments are later replaced with data flow during the Tree-to-Tree
38 * translation out of SSA. Jumps are eliminated during the Tree-to-Tree 40 * translation out of SSA. Jumps are eliminated during the Tree-to-Tree
39 * control-flow recognition. 41 * control-flow recognition.
40 * 42 *
41 * Otherwise, the output of Builder looks very much like the input. In 43 * Otherwise, the output of Builder looks very much like the input. In
42 * particular, intermediate values and blocks used for local control flow are 44 * particular, intermediate values and blocks used for local control flow are
43 * still all named. 45 * still all named.
44 */ 46 */
45 class Builder implements cps_ir.Visitor<Node> { 47 class Builder implements cps_ir.Visitor {
karlklose 2015/07/22 14:08:06 Maybe you add a comment of the form class Builde
asgerf 2015/07/22 14:32:25 Done.
46 final dart2js.InternalErrorFunction internalError; 48 final dart2js.InternalErrorFunction internalError;
47 49
48 final Map<cps_ir.Primitive, Variable> primitive2variable = 50 final Map<cps_ir.Primitive, Variable> primitive2variable =
49 <cps_ir.Primitive, Variable>{}; 51 <cps_ir.Primitive, Variable>{};
50 final Map<cps_ir.MutableVariable, Variable> mutable2variable = 52 final Map<cps_ir.MutableVariable, Variable> mutable2variable =
51 <cps_ir.MutableVariable, Variable>{}; 53 <cps_ir.MutableVariable, Variable>{};
52 54
53 // Continuations with more than one use are replaced with Tree labels. This 55 // Continuations with more than one use are replaced with Tree labels. This
54 // is the mapping from continuations to labels. 56 // is the mapping from continuations to labels.
55 final Map<cps_ir.Continuation, Label> labels = <cps_ir.Continuation, Label>{}; 57 final Map<cps_ir.Continuation, Label> labels = <cps_ir.Continuation, Label>{};
(...skipping 46 matching lines...) Expand 10 before | Expand all | Expand 10 after
102 /// referred to by [reference]. 104 /// referred to by [reference].
103 /// This increments the reference count for the given variable, so the 105 /// This increments the reference count for the given variable, so the
104 /// returned expression must be used in the tree. 106 /// returned expression must be used in the tree.
105 Expression getVariableUse(cps_ir.Reference<cps_ir.Primitive> reference) { 107 Expression getVariableUse(cps_ir.Reference<cps_ir.Primitive> reference) {
106 if (thisParameter != null && reference.definition == thisParameter) { 108 if (thisParameter != null && reference.definition == thisParameter) {
107 return new This(); 109 return new This();
108 } 110 }
109 return new VariableUse(getVariable(reference.definition)); 111 return new VariableUse(getVariable(reference.definition));
110 } 112 }
111 113
114 Label getLabel(cps_ir.Continuation cont) {
115 return labels.putIfAbsent(cont, () => new Label());
116 }
117
112 Variable addFunctionParameter(cps_ir.Definition variable) { 118 Variable addFunctionParameter(cps_ir.Definition variable) {
113 if (variable is cps_ir.Parameter) { 119 if (variable is cps_ir.Parameter) {
114 return getVariable(variable); 120 return getVariable(variable);
115 } else { 121 } else {
116 return addMutableVariable(variable as cps_ir.MutableVariable) 122 return addMutableVariable(variable as cps_ir.MutableVariable)
117 ..isCaptured = true; 123 ..isCaptured = true;
118 } 124 }
119 } 125 }
120 126
121 FunctionDefinition buildFunction(cps_ir.FunctionDefinition node) { 127 FunctionDefinition buildFunction(cps_ir.FunctionDefinition node) {
122 currentElement = node.element; 128 currentElement = node.element;
123 if (parent != null) { 129 if (parent != null) {
124 // Local function's 'this' refers to enclosing method's 'this' 130 // Local function's 'this' refers to enclosing method's 'this'
125 thisParameter = parent.thisParameter; 131 thisParameter = parent.thisParameter;
126 } else { 132 } else {
127 thisParameter = node.thisParameter; 133 thisParameter = node.thisParameter;
128 } 134 }
129 List<Variable> parameters = 135 List<Variable> parameters =
130 node.parameters.map(addFunctionParameter).toList(); 136 node.parameters.map(addFunctionParameter).toList();
131 returnContinuation = node.returnContinuation; 137 returnContinuation = node.returnContinuation;
132 phiTempVar = new Variable(node.element, null); 138 phiTempVar = new Variable(node.element, null);
133 Statement body = visit(node.body); 139 Statement body = translateExpression(node.body);
134 return new FunctionDefinition(node.element, parameters, body); 140 return new FunctionDefinition(node.element, parameters, body);
135 } 141 }
136 142
137 /// Returns a list of variables corresponding to the arguments to a method 143 /// Returns a list of variables corresponding to the arguments to a method
138 /// call or similar construct. 144 /// call or similar construct.
139 /// 145 ///
140 /// The `readCount` for these variables will be incremented. 146 /// The `readCount` for these variables will be incremented.
141 /// 147 ///
142 /// The list will be typed as a list of [Expression] to allow inplace updates 148 /// The list will be typed as a list of [Expression] to allow inplace updates
143 /// on the list during the rewrite phases. 149 /// on the list during the rewrite phases.
(...skipping 101 matching lines...) Expand 10 before | Expand all | Expand 10 after
245 } 251 }
246 252
247 if (first == null) { 253 if (first == null) {
248 first = buildRest(); 254 first = buildRest();
249 } else { 255 } else {
250 current.next = buildRest(); 256 current.next = buildRest();
251 } 257 }
252 return first; 258 return first;
253 } 259 }
254 260
255 visit(cps_ir.Node node) => node.accept(this); 261 visit(cps_ir.Node node) => throw 'Use translateXXX instead of visit';
256 262
257 unexpectedNode(cps_ir.Node node) { 263 /// Translates a CPS expression into a tree statement.
258 internalError(CURRENT_ELEMENT_SPANNABLE, 'Unexpected IR node: $node'); 264 ///
265 /// To avoid deep recursion, we traverse each basic blocks without
266 /// recursion.
267 ///
268 /// Non-tail expressions evaluate to a callback to be invoked once the
269 /// successor statement has been constructed. These callbacks are stored
270 /// in a stack until the block's tail expression has been translated.
271 Statement translateExpression(cps_ir.Expression node) {
272 // TODO(asgerf): Use a function typedef.
karlklose 2015/07/22 14:08:06 A typedef different from NodeCallback?
asgerf 2015/07/22 14:32:25 Oops, I forgot to remove this after resolving it.
273 List<NodeCallback> stack = <NodeCallback>[];
274 while (node is! cps_ir.TailExpression) {
275 stack.add(node.accept(this));
276 node = node.next;
277 }
278 Statement result = node.accept(this); // Translate the tail expression.
279 for (NodeCallback fun in stack.reversed) {
karlklose 2015/07/22 14:08:06 Maybe a Link<NodeCallback> would work better for t
asgerf 2015/07/22 14:32:25 I don't think linked lists are faster.
karlklose 2015/07/23 06:55:54 Not necessarily faster, but you can build the stac
280 result = fun(result);
281 }
282 return result;
259 } 283 }
260 284
261 Expression visitSetField(cps_ir.SetField node) { 285 /// Translates a CPS primitive to a tree expression.
262 return new SetField(getVariableUse(node.object), 286 ///
263 node.field, 287 /// This simply calls the visit method for the primitive.
264 getVariableUse(node.value)); 288 Expression translatePrimitive(cps_ir.Primitive prim) {
265 } 289 return prim.accept(this);
266
267 Expression visitInterceptor(cps_ir.Interceptor node) {
268 return new Interceptor(getVariableUse(node.input), node.interceptedClasses);
269 } 290 }
270 291
271 Expression visitCreateInstance(cps_ir.CreateInstance node) { 292 /// Translates a condition to a tree expression.
272 return new CreateInstance( 293 Expression translateCondition(cps_ir.Condition condition) {
273 node.classElement, 294 cps_ir.IsTrue isTrue = condition;
274 translateArguments(node.arguments), 295 return getVariableUse(isTrue.value);
275 translateArguments(node.typeInformation),
276 node.sourceInformation);
277 } 296 }
278 297
279 Expression visitGetField(cps_ir.GetField node) { 298 /************************ INTERIOR EXPRESSIONS ************************/
280 return new GetField(getVariableUse(node.object), node.field, 299 //
281 objectIsNotNull: node.objectIsNotNull); 300 // Visit methods for interior expressions must return a function:
301 //
302 // (Statement next) => <result statement>
303 //
304
305 NodeCallback visitLetPrim(cps_ir.LetPrim node) => (Statement next) {
306 Variable variable = getVariable(node.primitive);
307 Expression value = translatePrimitive(node.primitive);
308 if (node.primitive.hasAtLeastOneUse) {
309 return Assign.makeStatement(variable, value, next);
310 } else {
311 return new ExpressionStatement(value, next);
312 }
313 };
314
315 // Continuations are bound at the same level, but they have to be
316 // translated as if nested. This is because the body can invoke any
317 // of them from anywhere, so it must be nested inside all of them.
318 //
319 // The continuation bodies are not always translated directly here because
320 // they may have been already translated:
321 // * For singly-used continuations, the continuation's body is
322 // translated at the site of the continuation invocation.
323 // * For recursive continuations, there is a single non-recursive
324 // invocation. The continuation's body is translated at the site
325 // of the non-recursive continuation invocation.
326 // See visitInvokeContinuation for the implementation.
floitsch 2015/07/22 14:21:42 make this a link.
asgerf 2015/07/22 14:32:25 Done.
327 NodeCallback visitLetCont(cps_ir.LetCont node) => (Statement next) {
328 for (cps_ir.Continuation continuation in node.continuations) {
329 // This happens after the body of the LetCont has been translated.
330 // Labels are created on-demand if the continuation could not be inlined,
331 // so the existence of the label indicates if a labeled statement should
332 // be emitted.
333 Label label = labels[continuation];
334 if (label != null && !continuation.isRecursive) {
335 // Recursively build the body. We only do this for join continuations,
336 // so we should not risk overly deep recursion.
337 next = new LabeledStatement(
338 label,
339 next,
340 translateExpression(continuation.body));
341 }
342 }
343 return next;
344 };
345
346 NodeCallback visitLetHandler(cps_ir.LetHandler node) => (Statement next) {
347 List<Variable> catchParameters =
348 node.handler.parameters.map(getVariable).toList();
349 Statement catchBody = translateExpression(node.handler.body);
350 return new Try(next, catchParameters, catchBody);
351 };
352
353 NodeCallback visitLetMutable(cps_ir.LetMutable node) {
354 Variable variable = addMutableVariable(node.variable);
355 Expression value = getVariableUse(node.value);
356 return (Statement next) => Assign.makeStatement(variable, value, next);
282 } 357 }
283 358
284 Expression visitCreateBox(cps_ir.CreateBox node) { 359
285 return new CreateBox(); 360 /************************ CALL EXPRESSIONS ************************/
361 //
362 // Visit methods for call expressions must return a function:
363 //
364 // (Statement next) => <result statement>
365 //
366 // The result statement must include an assignment to the continuation
367 // parameter, if the parameter is used.
368 //
369
370 NodeCallback makeCallExpression(cps_ir.CallExpression call,
371 Expression expression) {
372 return (Statement next) {
373 cps_ir.Parameter result = call.continuation.definition.parameters.single;
374 if (result.hasAtLeastOneUse) {
375 return Assign.makeStatement(getVariable(result), expression, next);
376 } else {
377 return new ExpressionStatement(expression, next);
378 }
379 };
286 } 380 }
287 381
288 visitCreateInvocationMirror(cps_ir.CreateInvocationMirror node) { 382 NodeCallback visitInvokeStatic(cps_ir.InvokeStatic node) {
289 return new CreateInvocationMirror(
290 node.selector,
291 translateArguments(node.arguments));
292 }
293
294 // Executable definitions are not visited directly. They have 'build'
295 // functions as entry points.
296 visitFunctionDefinition(cps_ir.FunctionDefinition node) {
297 return unexpectedNode(node);
298 }
299
300 Statement visitLetPrim(cps_ir.LetPrim node) {
301 Variable variable = getVariable(node.primitive);
302 Expression value = visit(node.primitive);
303 if (node.primitive.hasAtLeastOneUse) {
304 return Assign.makeStatement(variable, value, visit(node.body));
305 } else {
306 return new ExpressionStatement(value, visit(node.body));
307 }
308 }
309
310 Statement visitLetCont(cps_ir.LetCont node) {
311 // Introduce labels for continuations that need them.
312 for (cps_ir.Continuation continuation in node.continuations) {
313 if (continuation.hasMultipleUses || continuation.isRecursive) {
314 labels[continuation] = new Label();
315 }
316 }
317 Statement body = visit(node.body);
318 // Continuations are bound at the same level, but they have to be
319 // translated as if nested. This is because the body can invoke any
320 // of them from anywhere, so it must be nested inside all of them.
321 //
322 // The continuation bodies are not always translated directly here because
323 // they may have been already translated:
324 // * For singly-used continuations, the continuation's body is
325 // translated at the site of the continuation invocation.
326 // * For recursive continuations, there is a single non-recursive
327 // invocation. The continuation's body is translated at the site
328 // of the non-recursive continuation invocation.
329 // See visitInvokeContinuation for the implementation.
330 Statement current = body;
331 for (cps_ir.Continuation continuation in node.continuations.reversed) {
332 Label label = labels[continuation];
333 if (label != null && !continuation.isRecursive) {
334 current =
335 new LabeledStatement(label, current, visit(continuation.body));
336 }
337 }
338 return current;
339 }
340
341 Statement visitLetHandler(cps_ir.LetHandler node) {
342 Statement tryBody = visit(node.body);
343 List<Variable> catchParameters =
344 node.handler.parameters.map(getVariable).toList();
345 Statement catchBody = visit(node.handler.body);
346 return new Try(tryBody, catchParameters, catchBody);
347 }
348
349 Statement visitInvokeStatic(cps_ir.InvokeStatic node) {
350 // Calls are translated to direct style.
351 List<Expression> arguments = translateArguments(node.arguments); 383 List<Expression> arguments = translateArguments(node.arguments);
352 Expression invoke = new InvokeStatic(node.target, node.selector, arguments, 384 Expression invoke = new InvokeStatic(node.target, node.selector, arguments,
353 node.sourceInformation); 385 node.sourceInformation);
354 return continueWithExpression(node.continuation, invoke); 386 return makeCallExpression(node, invoke);
355 } 387 }
356 388
357 Statement visitInvokeMethod(cps_ir.InvokeMethod node) { 389 NodeCallback visitInvokeMethod(cps_ir.InvokeMethod node) {
358 InvokeMethod invoke = new InvokeMethod( 390 InvokeMethod invoke = new InvokeMethod(
359 getVariableUse(node.receiver), 391 getVariableUse(node.receiver),
360 node.selector, 392 node.selector,
361 node.mask, 393 node.mask,
362 translateArguments(node.arguments), 394 translateArguments(node.arguments),
363 node.sourceInformation); 395 node.sourceInformation);
364 invoke.receiverIsNotNull = node.receiverIsNotNull; 396 invoke.receiverIsNotNull = node.receiverIsNotNull;
365 return continueWithExpression(node.continuation, invoke); 397 return makeCallExpression(node, invoke);
366 } 398 }
367 399
368 Statement visitInvokeMethodDirectly(cps_ir.InvokeMethodDirectly node) { 400 NodeCallback visitInvokeMethodDirectly(cps_ir.InvokeMethodDirectly node) {
369 Expression receiver = getVariableUse(node.receiver); 401 Expression receiver = getVariableUse(node.receiver);
370 List<Expression> arguments = translateArguments(node.arguments); 402 List<Expression> arguments = translateArguments(node.arguments);
371 Expression invoke = new InvokeMethodDirectly(receiver, node.target, 403 Expression invoke = new InvokeMethodDirectly(receiver, node.target,
372 node.selector, arguments, node.sourceInformation); 404 node.selector, arguments, node.sourceInformation);
373 return continueWithExpression(node.continuation, invoke); 405 return makeCallExpression(node, invoke);
374 } 406 }
375 407
408 NodeCallback visitTypeCast(cps_ir.TypeCast node) {
409 Expression value = getVariableUse(node.value);
410 List<Expression> typeArgs = translateArguments(node.typeArguments);
411 Expression expression =
412 new TypeOperator(value, node.type, typeArgs, isTypeTest: false);
413 return makeCallExpression(node, expression);
414 }
415
416 NodeCallback visitInvokeConstructor(cps_ir.InvokeConstructor node) {
417 List<Expression> arguments = translateArguments(node.arguments);
418 Expression invoke = new InvokeConstructor(
419 node.type,
420 node.target,
421 node.selector,
422 arguments,
423 node.sourceInformation);
424 return makeCallExpression(node, invoke);
425 }
426
427 NodeCallback visitForeignCode(cps_ir.ForeignCode node) {
428 if (node.codeTemplate.isExpression) {
429 Expression foreignCode = new ForeignExpression(
430 node.codeTemplate,
431 node.type,
432 node.arguments.map(getVariableUse).toList(growable: false),
433 node.nativeBehavior,
434 node.dependency);
435 return makeCallExpression(node, foreignCode);
436 } else {
437 return (Statement next) {
438 assert(next is Unreachable); // We are not using the `next` statement.
439 return new ForeignStatement(
440 node.codeTemplate,
441 node.type,
442 node.arguments.map(getVariableUse).toList(growable: false),
443 node.nativeBehavior,
444 node.dependency);
445 };
446 }
447 }
448
449 NodeCallback visitGetLazyStatic(cps_ir.GetLazyStatic node) {
450 // In the tree IR, GetStatic handles lazy fields because we do not need
451 // as fine-grained control over side effects.
452 GetStatic value = new GetStatic(node.element, node.sourceInformation);
453 return makeCallExpression(node, value);
454 }
455
456
457 /************************** TAIL EXPRESSIONS **************************/
458 //
459 // Visit methods for tail expressions must return a statement directly
460 // (not a function like interior and call expressions).
461
376 Statement visitThrow(cps_ir.Throw node) { 462 Statement visitThrow(cps_ir.Throw node) {
377 Expression value = getVariableUse(node.value); 463 Expression value = getVariableUse(node.value);
378 return new Throw(value); 464 return new Throw(value);
379 } 465 }
380 466
381 Statement visitRethrow(cps_ir.Rethrow node) { 467 Statement visitRethrow(cps_ir.Rethrow node) {
382 return new Rethrow(); 468 return new Rethrow();
383 } 469 }
384 470
385 Statement visitUnreachable(cps_ir.Unreachable node) { 471 Statement visitUnreachable(cps_ir.Unreachable node) {
386 return new Unreachable(); 472 return new Unreachable();
387 } 473 }
388 474
389 Statement continueWithExpression(cps_ir.Reference continuation,
390 Expression expression) {
391 cps_ir.Continuation cont = continuation.definition;
392 if (cont == returnContinuation) {
393 return new Return(expression);
394 } else {
395 assert(cont.parameters.length == 1);
396 Function nextBuilder = cont.hasExactlyOneUse ?
397 () => visit(cont.body) : () => new Break(labels[cont]);
398 return buildContinuationAssignment(cont.parameters.single, expression,
399 nextBuilder);
400 }
401 }
402
403 Statement visitLetMutable(cps_ir.LetMutable node) {
404 Variable variable = addMutableVariable(node.variable);
405 Expression value = getVariableUse(node.value);
406 Statement body = visit(node.body);
407 return Assign.makeStatement(variable, value, body);
408 }
409
410 Expression visitGetMutable(cps_ir.GetMutable node) {
411 return getMutableVariableUse(node.variable);
412 }
413
414 Expression visitSetMutable(cps_ir.SetMutable node) {
415 Variable variable = getMutableVariable(node.variable.definition);
416 Expression value = getVariableUse(node.value);
417 return new Assign(variable, value);
418 }
419
420 Statement visitTypeCast(cps_ir.TypeCast node) {
421 Expression value = getVariableUse(node.value);
422 List<Expression> typeArgs = translateArguments(node.typeArguments);
423 Expression expression =
424 new TypeOperator(value, node.type, typeArgs, isTypeTest: false);
425 return continueWithExpression(node.continuation, expression);
426 }
427
428 Expression visitTypeTest(cps_ir.TypeTest node) {
429 Expression value = getVariableUse(node.value);
430 List<Expression> typeArgs = translateArguments(node.typeArguments);
431 return new TypeOperator(value, node.type, typeArgs, isTypeTest: true);
432 }
433
434 Statement visitInvokeConstructor(cps_ir.InvokeConstructor node) {
435 List<Expression> arguments = translateArguments(node.arguments);
436 Expression invoke = new InvokeConstructor(
437 node.type,
438 node.target,
439 node.selector,
440 arguments,
441 node.sourceInformation);
442 return continueWithExpression(node.continuation, invoke);
443 }
444
445 Statement visitInvokeContinuation(cps_ir.InvokeContinuation node) { 475 Statement visitInvokeContinuation(cps_ir.InvokeContinuation node) {
446 // Invocations of the return continuation are translated to returns. 476 // Invocations of the return continuation are translated to returns.
447 // Other continuation invocations are replaced with assignments of the 477 // Other continuation invocations are replaced with assignments of the
448 // arguments to formal parameter variables, followed by the body if 478 // arguments to formal parameter variables, followed by the body if
449 // the continuation is singly reference or a break if it is multiply 479 // the continuation is singly reference or a break if it is multiply
450 // referenced. 480 // referenced.
451 cps_ir.Continuation cont = node.continuation.definition; 481 cps_ir.Continuation cont = node.continuation.definition;
452 if (cont == returnContinuation) { 482 if (cont == returnContinuation) {
453 assert(node.arguments.length == 1); 483 assert(node.arguments.length == 1);
454 return new Return(getVariableUse(node.arguments.single), 484 return new Return(getVariableUse(node.arguments.single),
455 sourceInformation: node.sourceInformation); 485 sourceInformation: node.sourceInformation);
456 } else { 486 } else {
457 List<Expression> arguments = translateArguments(node.arguments); 487 List<Expression> arguments = translateArguments(node.arguments);
458 return buildPhiAssignments(cont.parameters, arguments, 488 return buildPhiAssignments(cont.parameters, arguments,
459 () { 489 () {
460 // Translate invocations of recursive and non-recursive 490 // Translate invocations of recursive and non-recursive
461 // continuations differently. 491 // continuations differently.
462 // * Non-recursive continuations 492 // * Non-recursive continuations
463 // - If there is one use, translate the continuation body 493 // - If there is one use, translate the continuation body
464 // inline at the invocation site. 494 // inline at the invocation site.
465 // - If there are multiple uses, translate to Break. 495 // - If there are multiple uses, translate to Break.
466 // * Recursive continuations 496 // * Recursive continuations
467 // - There is a single non-recursive invocation. Translate 497 // - There is a single non-recursive invocation. Translate
468 // the continuation body inline as a labeled loop at the 498 // the continuation body inline as a labeled loop at the
469 // invocation site. 499 // invocation site.
470 // - Translate the recursive invocations to Continue. 500 // - Translate the recursive invocations to Continue.
471 if (cont.isRecursive) { 501 if (cont.isRecursive) {
472 return node.isRecursive 502 return node.isRecursive
473 ? new Continue(labels[cont]) 503 ? new Continue(getLabel(cont))
474 : new WhileTrue(labels[cont], visit(cont.body)); 504 : new WhileTrue(getLabel(cont),
505 translateExpression(cont.body));
475 } else { 506 } else {
476 if (cont.hasExactlyOneUse) { 507 return cont.hasExactlyOneUse && !node.isEscapingTry
477 if (!node.isEscapingTry) { 508 ? translateExpression(cont.body)
478 return visit(cont.body); 509 : new Break(getLabel(cont));
479 }
480 labels[cont] = new Label();
481 }
482 return new Break(labels[cont]);
483 } 510 }
484 }); 511 });
485 } 512 }
486 } 513 }
487 514
488 Statement visitBranch(cps_ir.Branch node) { 515 Statement visitBranch(cps_ir.Branch node) {
489 Expression condition = visit(node.condition); 516 Expression condition = translateCondition(node.condition);
490 Statement thenStatement, elseStatement; 517 Statement thenStatement, elseStatement;
491 cps_ir.Continuation cont = node.trueContinuation.definition; 518 cps_ir.Continuation cont = node.trueContinuation.definition;
492 assert(cont.parameters.isEmpty); 519 assert(cont.parameters.isEmpty);
493 thenStatement = 520 thenStatement = cont.hasExactlyOneUse
494 cont.hasExactlyOneUse ? visit(cont.body) : new Break(labels[cont]); 521 ? translateExpression(cont.body)
522 : new Break(labels[cont]);
495 cont = node.falseContinuation.definition; 523 cont = node.falseContinuation.definition;
496 assert(cont.parameters.isEmpty); 524 assert(cont.parameters.isEmpty);
497 elseStatement = 525 elseStatement = cont.hasExactlyOneUse
498 cont.hasExactlyOneUse ? visit(cont.body) : new Break(labels[cont]); 526 ? translateExpression(cont.body)
527 : new Break(labels[cont]);
499 return new If(condition, thenStatement, elseStatement); 528 return new If(condition, thenStatement, elseStatement);
500 } 529 }
501 530
531
532 /************************** PRIMITIVES **************************/
533 //
534 // Visit methods for primitives must return an expression.
535 //
536
537 Expression visitSetField(cps_ir.SetField node) {
538 return new SetField(getVariableUse(node.object),
539 node.field,
540 getVariableUse(node.value));
541 }
542
543 Expression visitInterceptor(cps_ir.Interceptor node) {
544 return new Interceptor(getVariableUse(node.input), node.interceptedClasses);
545 }
546
547 Expression visitCreateInstance(cps_ir.CreateInstance node) {
548 return new CreateInstance(
549 node.classElement,
550 translateArguments(node.arguments),
551 translateArguments(node.typeInformation),
552 node.sourceInformation);
553 }
554
555 Expression visitGetField(cps_ir.GetField node) {
556 return new GetField(getVariableUse(node.object), node.field,
557 objectIsNotNull: node.objectIsNotNull);
558 }
559
560 Expression visitCreateBox(cps_ir.CreateBox node) {
561 return new CreateBox();
562 }
563
564 Expression visitCreateInvocationMirror(cps_ir.CreateInvocationMirror node) {
565 return new CreateInvocationMirror(
566 node.selector,
567 translateArguments(node.arguments));
568 }
569
570 Expression visitGetMutable(cps_ir.GetMutable node) {
571 return getMutableVariableUse(node.variable);
572 }
573
574 Expression visitSetMutable(cps_ir.SetMutable node) {
575 Variable variable = getMutableVariable(node.variable.definition);
576 Expression value = getVariableUse(node.value);
577 return new Assign(variable, value);
578 }
579
502 Expression visitConstant(cps_ir.Constant node) { 580 Expression visitConstant(cps_ir.Constant node) {
503 return new Constant(node.value, sourceInformation: node.sourceInformation); 581 return new Constant(node.value, sourceInformation: node.sourceInformation);
504 } 582 }
505 583
506 Expression visitLiteralList(cps_ir.LiteralList node) { 584 Expression visitLiteralList(cps_ir.LiteralList node) {
507 return new LiteralList( 585 return new LiteralList(
508 node.type, 586 node.type,
509 translateArguments(node.values)); 587 translateArguments(node.values));
510 } 588 }
511 589
(...skipping 10 matching lines...) Expand all
522 600
523 FunctionDefinition makeSubFunction(cps_ir.FunctionDefinition function) { 601 FunctionDefinition makeSubFunction(cps_ir.FunctionDefinition function) {
524 return createInnerBuilder().buildFunction(function); 602 return createInnerBuilder().buildFunction(function);
525 } 603 }
526 604
527 Expression visitCreateFunction(cps_ir.CreateFunction node) { 605 Expression visitCreateFunction(cps_ir.CreateFunction node) {
528 FunctionDefinition def = makeSubFunction(node.definition); 606 FunctionDefinition def = makeSubFunction(node.definition);
529 return new FunctionExpression(def); 607 return new FunctionExpression(def);
530 } 608 }
531 609
532 visitParameter(cps_ir.Parameter node) {
533 // Continuation parameters are not visited (continuations themselves are
534 // not visited yet).
535 unexpectedNode(node);
536 }
537
538 visitContinuation(cps_ir.Continuation node) {
539 // Until continuations with multiple uses are supported, they are not
540 // visited.
541 unexpectedNode(node);
542 }
543
544 visitMutableVariable(cps_ir.MutableVariable node) {
545 // These occur as parameters or bound by LetMutable. They are not visited
546 // directly.
547 unexpectedNode(node);
548 }
549
550 Expression visitIsTrue(cps_ir.IsTrue node) {
551 return getVariableUse(node.value);
552 }
553
554 Expression visitReifyRuntimeType(cps_ir.ReifyRuntimeType node) { 610 Expression visitReifyRuntimeType(cps_ir.ReifyRuntimeType node) {
555 return new ReifyRuntimeType( 611 return new ReifyRuntimeType(
556 getVariableUse(node.value), node.sourceInformation); 612 getVariableUse(node.value), node.sourceInformation);
557 } 613 }
558 614
559 Expression visitReadTypeVariable(cps_ir.ReadTypeVariable node) { 615 Expression visitReadTypeVariable(cps_ir.ReadTypeVariable node) {
560 return new ReadTypeVariable( 616 return new ReadTypeVariable(
561 node.variable, 617 node.variable,
562 getVariableUse(node.target), 618 getVariableUse(node.target),
563 node.sourceInformation); 619 node.sourceInformation);
564 } 620 }
565 621
566 @override 622 Expression visitTypeExpression(cps_ir.TypeExpression node) {
567 Node visitTypeExpression(cps_ir.TypeExpression node) {
568 return new TypeExpression( 623 return new TypeExpression(
569 node.dartType, 624 node.dartType,
570 node.arguments.map(getVariableUse).toList()); 625 node.arguments.map(getVariableUse).toList());
571 } 626 }
572 627
628 Expression visitTypeTest(cps_ir.TypeTest node) {
629 Expression value = getVariableUse(node.value);
630 List<Expression> typeArgs = translateArguments(node.typeArguments);
631 return new TypeOperator(value, node.type, typeArgs, isTypeTest: true);
632 }
633
573 Expression visitGetStatic(cps_ir.GetStatic node) { 634 Expression visitGetStatic(cps_ir.GetStatic node) {
574 return new GetStatic(node.element, node.sourceInformation); 635 return new GetStatic(node.element, node.sourceInformation);
575 } 636 }
576 637
577 Statement visitGetLazyStatic(cps_ir.GetLazyStatic node) {
578 // In the tree IR, GetStatic handles lazy fields because tree
579 // expressions are allowed to have side effects.
580 GetStatic value = new GetStatic(node.element, node.sourceInformation);
581 return continueWithExpression(node.continuation, value);
582 }
583
584 Expression visitSetStatic(cps_ir.SetStatic node) { 638 Expression visitSetStatic(cps_ir.SetStatic node) {
585 return new SetStatic( 639 return new SetStatic(
586 node.element, 640 node.element,
587 getVariableUse(node.value), 641 getVariableUse(node.value),
588 node.sourceInformation); 642 node.sourceInformation);
589 } 643 }
590 644
591 Expression visitApplyBuiltinOperator(cps_ir.ApplyBuiltinOperator node) { 645 Expression visitApplyBuiltinOperator(cps_ir.ApplyBuiltinOperator node) {
592 if (node.operator == BuiltinOperator.IsFalsy) { 646 if (node.operator == BuiltinOperator.IsFalsy) {
593 return new Not(getVariableUse(node.arguments.single)); 647 return new Not(getVariableUse(node.arguments.single));
594 } 648 }
595 return new ApplyBuiltinOperator(node.operator, 649 return new ApplyBuiltinOperator(node.operator,
596 translateArguments(node.arguments)); 650 translateArguments(node.arguments));
597 } 651 }
598 652
599 Statement visitForeignCode(cps_ir.ForeignCode node) {
600 if (node.codeTemplate.isExpression) {
601 Expression foreignCode = new ForeignExpression(
602 node.codeTemplate,
603 node.type,
604 node.arguments.map(getVariableUse).toList(growable: false),
605 node.nativeBehavior,
606 node.dependency);
607 return continueWithExpression(node.continuation, foreignCode);
608 } else {
609 assert(node.continuation.definition.body is cps_ir.Unreachable);
610 return new ForeignStatement(
611 node.codeTemplate,
612 node.type,
613 node.arguments.map(getVariableUse).toList(growable: false),
614 node.nativeBehavior,
615 node.dependency);
616 }
617 }
618
619 Expression visitGetLength(cps_ir.GetLength node) { 653 Expression visitGetLength(cps_ir.GetLength node) {
620 return new GetLength(getVariableUse(node.object)); 654 return new GetLength(getVariableUse(node.object));
621 } 655 }
622 656
623 Expression visitGetIndex(cps_ir.GetIndex node) { 657 Expression visitGetIndex(cps_ir.GetIndex node) {
624 return new GetIndex(getVariableUse(node.object), 658 return new GetIndex(getVariableUse(node.object),
625 getVariableUse(node.index)); 659 getVariableUse(node.index));
626 } 660 }
627 661
628 Expression visitSetIndex(cps_ir.SetIndex node) { 662 Expression visitSetIndex(cps_ir.SetIndex node) {
629 return new SetIndex(getVariableUse(node.object), 663 return new SetIndex(getVariableUse(node.object),
630 getVariableUse(node.index), 664 getVariableUse(node.index),
631 getVariableUse(node.value)); 665 getVariableUse(node.value));
632 } 666 }
667
668 /********** UNUSED VISIT METHODS *************/
669
670 unexpectedNode(cps_ir.Node node) {
671 internalError(CURRENT_ELEMENT_SPANNABLE, 'Unexpected IR node: $node');
672 }
673
674 visitFunctionDefinition(cps_ir.FunctionDefinition node) {
675 unexpectedNode(node);
676 }
677 visitParameter(cps_ir.Parameter node) => unexpectedNode(node);
678 visitContinuation(cps_ir.Continuation node) => unexpectedNode(node);
679 visitMutableVariable(cps_ir.MutableVariable node) => unexpectedNode(node);
680 visitIsTrue(cps_ir.IsTrue node) => unexpectedNode(node);
633 } 681 }
634 682
OLDNEW

Powered by Google App Engine
This is Rietveld 408576698