| 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 |