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 tree_ir_builder; | 5 library tree_ir_builder; |
6 | 6 |
7 import '../dart2jslib.dart' as dart2js; | 7 import '../diagnostics/invariant.dart' show |
| 8 InternalErrorFunction; |
| 9 import '../diagnostics/spannable.dart' show |
| 10 CURRENT_ELEMENT_SPANNABLE; |
8 import '../elements/elements.dart'; | 11 import '../elements/elements.dart'; |
9 import '../cps_ir/cps_ir_nodes.dart' as cps_ir; | 12 import '../cps_ir/cps_ir_nodes.dart' as cps_ir; |
10 import '../util/util.dart' show CURRENT_ELEMENT_SPANNABLE; | |
11 import 'tree_ir_nodes.dart'; | 13 import 'tree_ir_nodes.dart'; |
12 | 14 |
13 typedef Statement NodeCallback(Statement next); | 15 typedef Statement NodeCallback(Statement next); |
14 | 16 |
15 /** | 17 /** |
16 * Builder translates from CPS-based IR to direct-style Tree. | 18 * Builder translates from CPS-based IR to direct-style Tree. |
17 * | 19 * |
18 * A call `Invoke(fun, cont, args)`, where cont is a singly-referenced | 20 * A call `Invoke(fun, cont, args)`, where cont is a singly-referenced |
19 * non-exit continuation `Cont(v, body)` is translated into a direct-style call | 21 * non-exit continuation `Cont(v, body)` is translated into a direct-style call |
20 * whose value is bound in the continuation body: | 22 * whose value is bound in the continuation body: |
(...skipping 17 matching lines...) Expand all Loading... |
38 * | 40 * |
39 * Block arguments are later replaced with data flow during the Tree-to-Tree | 41 * Block arguments are later replaced with data flow during the Tree-to-Tree |
40 * translation out of SSA. Jumps are eliminated during the Tree-to-Tree | 42 * translation out of SSA. Jumps are eliminated during the Tree-to-Tree |
41 * control-flow recognition. | 43 * control-flow recognition. |
42 * | 44 * |
43 * Otherwise, the output of Builder looks very much like the input. In | 45 * Otherwise, the output of Builder looks very much like the input. In |
44 * particular, intermediate values and blocks used for local control flow are | 46 * particular, intermediate values and blocks used for local control flow are |
45 * still all named. | 47 * still all named. |
46 */ | 48 */ |
47 class Builder implements cps_ir.Visitor/*<NodeCallback|Node>*/ { | 49 class Builder implements cps_ir.Visitor/*<NodeCallback|Node>*/ { |
48 final dart2js.InternalErrorFunction internalError; | 50 final InternalErrorFunction internalError; |
49 | 51 |
50 final Map<cps_ir.Primitive, Variable> primitive2variable = | 52 final Map<cps_ir.Primitive, Variable> primitive2variable = |
51 <cps_ir.Primitive, Variable>{}; | 53 <cps_ir.Primitive, Variable>{}; |
52 final Map<cps_ir.MutableVariable, Variable> mutable2variable = | 54 final Map<cps_ir.MutableVariable, Variable> mutable2variable = |
53 <cps_ir.MutableVariable, Variable>{}; | 55 <cps_ir.MutableVariable, Variable>{}; |
54 | 56 |
55 // Continuations with more than one use are replaced with Tree labels. This | 57 // Continuations with more than one use are replaced with Tree labels. This |
56 // is the mapping from continuations to labels. | 58 // is the mapping from continuations to labels. |
57 final Map<cps_ir.Continuation, Label> labels = <cps_ir.Continuation, Label>{}; | 59 final Map<cps_ir.Continuation, Label> labels = <cps_ir.Continuation, Label>{}; |
58 | 60 |
(...skipping 182 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
241 first = buildRest(); | 243 first = buildRest(); |
242 } else { | 244 } else { |
243 current.next = buildRest(); | 245 current.next = buildRest(); |
244 } | 246 } |
245 return first; | 247 return first; |
246 } | 248 } |
247 | 249 |
248 visit(cps_ir.Node node) => throw 'Use translateXXX instead of visit'; | 250 visit(cps_ir.Node node) => throw 'Use translateXXX instead of visit'; |
249 | 251 |
250 /// Translates a CPS expression into a tree statement. | 252 /// Translates a CPS expression into a tree statement. |
251 /// | 253 /// |
252 /// To avoid deep recursion, we traverse each basic blocks without | 254 /// To avoid deep recursion, we traverse each basic blocks without |
253 /// recursion. | 255 /// recursion. |
254 /// | 256 /// |
255 /// Non-tail expressions evaluate to a callback to be invoked once the | 257 /// Non-tail expressions evaluate to a callback to be invoked once the |
256 /// successor statement has been constructed. These callbacks are stored | 258 /// successor statement has been constructed. These callbacks are stored |
257 /// in a stack until the block's tail expression has been translated. | 259 /// in a stack until the block's tail expression has been translated. |
258 Statement translateExpression(cps_ir.Expression node) { | 260 Statement translateExpression(cps_ir.Expression node) { |
259 List<NodeCallback> stack = <NodeCallback>[]; | 261 List<NodeCallback> stack = <NodeCallback>[]; |
260 while (node is! cps_ir.TailExpression) { | 262 while (node is! cps_ir.TailExpression) { |
261 stack.add(node.accept(this)); | 263 stack.add(node.accept(this)); |
262 node = node.next; | 264 node = node.next; |
263 } | 265 } |
264 Statement result = node.accept(this); // Translate the tail expression. | 266 Statement result = node.accept(this); // Translate the tail expression. |
265 for (NodeCallback fun in stack.reversed) { | 267 for (NodeCallback fun in stack.reversed) { |
266 result = fun(result); | 268 result = fun(result); |
267 } | 269 } |
268 return result; | 270 return result; |
269 } | 271 } |
270 | 272 |
271 /// Translates a CPS primitive to a tree expression. | 273 /// Translates a CPS primitive to a tree expression. |
272 /// | 274 /// |
273 /// This simply calls the visit method for the primitive. | 275 /// This simply calls the visit method for the primitive. |
274 Expression translatePrimitive(cps_ir.Primitive prim) { | 276 Expression translatePrimitive(cps_ir.Primitive prim) { |
275 return prim.accept(this); | 277 return prim.accept(this); |
276 } | 278 } |
277 | 279 |
278 /// Translates a condition to a tree expression. | 280 /// Translates a condition to a tree expression. |
279 Expression translateCondition(cps_ir.Condition condition) { | 281 Expression translateCondition(cps_ir.Condition condition) { |
280 cps_ir.IsTrue isTrue = condition; | 282 cps_ir.IsTrue isTrue = condition; |
281 return getVariableUse(isTrue.value); | 283 return getVariableUse(isTrue.value); |
282 } | 284 } |
(...skipping 31 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
314 for (cps_ir.Continuation continuation in node.continuations) { | 316 for (cps_ir.Continuation continuation in node.continuations) { |
315 // This happens after the body of the LetCont has been translated. | 317 // This happens after the body of the LetCont has been translated. |
316 // Labels are created on-demand if the continuation could not be inlined, | 318 // Labels are created on-demand if the continuation could not be inlined, |
317 // so the existence of the label indicates if a labeled statement should | 319 // so the existence of the label indicates if a labeled statement should |
318 // be emitted. | 320 // be emitted. |
319 Label label = labels[continuation]; | 321 Label label = labels[continuation]; |
320 if (label != null && !continuation.isRecursive) { | 322 if (label != null && !continuation.isRecursive) { |
321 // Recursively build the body. We only do this for join continuations, | 323 // Recursively build the body. We only do this for join continuations, |
322 // so we should not risk overly deep recursion. | 324 // so we should not risk overly deep recursion. |
323 next = new LabeledStatement( | 325 next = new LabeledStatement( |
324 label, | 326 label, |
325 next, | 327 next, |
326 translateExpression(continuation.body)); | 328 translateExpression(continuation.body)); |
327 } | 329 } |
328 } | 330 } |
329 return next; | 331 return next; |
330 }; | 332 }; |
331 | 333 |
332 NodeCallback visitLetHandler(cps_ir.LetHandler node) => (Statement next) { | 334 NodeCallback visitLetHandler(cps_ir.LetHandler node) => (Statement next) { |
333 List<Variable> catchParameters = | 335 List<Variable> catchParameters = |
334 node.handler.parameters.map(getVariable).toList(); | 336 node.handler.parameters.map(getVariable).toList(); |
335 Statement catchBody = translateExpression(node.handler.body); | 337 Statement catchBody = translateExpression(node.handler.body); |
(...skipping 144 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
480 // inline at the invocation site. | 482 // inline at the invocation site. |
481 // - If there are multiple uses, translate to Break. | 483 // - If there are multiple uses, translate to Break. |
482 // * Recursive continuations | 484 // * Recursive continuations |
483 // - There is a single non-recursive invocation. Translate | 485 // - There is a single non-recursive invocation. Translate |
484 // the continuation body inline as a labeled loop at the | 486 // the continuation body inline as a labeled loop at the |
485 // invocation site. | 487 // invocation site. |
486 // - Translate the recursive invocations to Continue. | 488 // - Translate the recursive invocations to Continue. |
487 if (cont.isRecursive) { | 489 if (cont.isRecursive) { |
488 return node.isRecursive | 490 return node.isRecursive |
489 ? new Continue(getLabel(cont)) | 491 ? new Continue(getLabel(cont)) |
490 : new WhileTrue(getLabel(cont), | 492 : new WhileTrue(getLabel(cont), |
491 translateExpression(cont.body)); | 493 translateExpression(cont.body)); |
492 } else { | 494 } else { |
493 return cont.hasExactlyOneUse && !node.isEscapingTry | 495 return cont.hasExactlyOneUse && !node.isEscapingTry |
494 ? translateExpression(cont.body) | 496 ? translateExpression(cont.body) |
495 : new Break(getLabel(cont)); | 497 : new Break(getLabel(cont)); |
496 } | 498 } |
497 }); | 499 }); |
498 } | 500 } |
499 } | 501 } |
500 | 502 |
501 Statement visitBranch(cps_ir.Branch node) { | 503 Statement visitBranch(cps_ir.Branch node) { |
502 Expression condition = translateCondition(node.condition); | 504 Expression condition = translateCondition(node.condition); |
503 Statement thenStatement, elseStatement; | 505 Statement thenStatement, elseStatement; |
504 cps_ir.Continuation cont = node.trueContinuation.definition; | 506 cps_ir.Continuation cont = node.trueContinuation.definition; |
505 assert(cont.parameters.isEmpty); | 507 assert(cont.parameters.isEmpty); |
506 thenStatement = cont.hasExactlyOneUse | 508 thenStatement = cont.hasExactlyOneUse |
507 ? translateExpression(cont.body) | 509 ? translateExpression(cont.body) |
508 : new Break(labels[cont]); | 510 : new Break(labels[cont]); |
509 cont = node.falseContinuation.definition; | 511 cont = node.falseContinuation.definition; |
510 assert(cont.parameters.isEmpty); | 512 assert(cont.parameters.isEmpty); |
511 elseStatement = cont.hasExactlyOneUse | 513 elseStatement = cont.hasExactlyOneUse |
512 ? translateExpression(cont.body) | 514 ? translateExpression(cont.body) |
513 : new Break(labels[cont]); | 515 : new Break(labels[cont]); |
514 return new If(condition, thenStatement, elseStatement); | 516 return new If(condition, thenStatement, elseStatement); |
515 } | 517 } |
516 | 518 |
517 | 519 |
518 /************************** PRIMITIVES **************************/ | 520 /************************** PRIMITIVES **************************/ |
519 // | 521 // |
520 // Visit methods for primitives must return an expression. | 522 // Visit methods for primitives must return an expression. |
521 // | 523 // |
522 | 524 |
523 Expression visitSetField(cps_ir.SetField node) { | 525 Expression visitSetField(cps_ir.SetField node) { |
524 return new SetField(getVariableUse(node.object), | 526 return new SetField(getVariableUse(node.object), |
525 node.field, | 527 node.field, |
526 getVariableUse(node.value)); | 528 getVariableUse(node.value)); |
527 } | 529 } |
528 | 530 |
529 Expression visitInterceptor(cps_ir.Interceptor node) { | 531 Expression visitInterceptor(cps_ir.Interceptor node) { |
530 return new Interceptor(getVariableUse(node.input), | 532 return new Interceptor(getVariableUse(node.input), |
531 node.interceptedClasses, | 533 node.interceptedClasses, |
532 node.sourceInformation); | 534 node.sourceInformation); |
533 } | 535 } |
534 | 536 |
535 Expression visitCreateInstance(cps_ir.CreateInstance node) { | 537 Expression visitCreateInstance(cps_ir.CreateInstance node) { |
536 return new CreateInstance( | 538 return new CreateInstance( |
537 node.classElement, | 539 node.classElement, |
538 translateArguments(node.arguments), | 540 translateArguments(node.arguments), |
539 translateArguments(node.typeInformation), | 541 translateArguments(node.typeInformation), |
540 node.sourceInformation); | 542 node.sourceInformation); |
(...skipping 126 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
667 | 669 |
668 visitFunctionDefinition(cps_ir.FunctionDefinition node) { | 670 visitFunctionDefinition(cps_ir.FunctionDefinition node) { |
669 unexpectedNode(node); | 671 unexpectedNode(node); |
670 } | 672 } |
671 visitParameter(cps_ir.Parameter node) => unexpectedNode(node); | 673 visitParameter(cps_ir.Parameter node) => unexpectedNode(node); |
672 visitContinuation(cps_ir.Continuation node) => unexpectedNode(node); | 674 visitContinuation(cps_ir.Continuation node) => unexpectedNode(node); |
673 visitMutableVariable(cps_ir.MutableVariable node) => unexpectedNode(node); | 675 visitMutableVariable(cps_ir.MutableVariable node) => unexpectedNode(node); |
674 visitIsTrue(cps_ir.IsTrue node) => unexpectedNode(node); | 676 visitIsTrue(cps_ir.IsTrue node) => unexpectedNode(node); |
675 } | 677 } |
676 | 678 |
OLD | NEW |