| 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 '../dart2jslib.dart' as dart2js; |
| 8 import '../dart_types.dart'; | 8 import '../dart_types.dart'; |
| 9 import '../elements/elements.dart'; | 9 import '../elements/elements.dart'; |
| 10 import '../cps_ir/cps_ir_nodes.dart' as cps_ir; | 10 import '../cps_ir/cps_ir_nodes.dart' as cps_ir; |
| (...skipping 49 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 60 /// A stack of singly-used labels that can be safely inlined at their use | 60 /// A stack of singly-used labels that can be safely inlined at their use |
| 61 /// site. | 61 /// site. |
| 62 /// | 62 /// |
| 63 /// Code for continuations with exactly one use is inlined at the use site. | 63 /// Code for continuations with exactly one use is inlined at the use site. |
| 64 /// This is not safe if the code is moved inside the scope of an exception | 64 /// This is not safe if the code is moved inside the scope of an exception |
| 65 /// handler (i.e., into a try block). We keep a stack of singly-referenced | 65 /// handler (i.e., into a try block). We keep a stack of singly-referenced |
| 66 /// continuations that are in scope without crossing a binding for a handler. | 66 /// continuations that are in scope without crossing a binding for a handler. |
| 67 List<cps_ir.Continuation> safeForInlining = <cps_ir.Continuation>[]; | 67 List<cps_ir.Continuation> safeForInlining = <cps_ir.Continuation>[]; |
| 68 | 68 |
| 69 ExecutableElement currentElement; | 69 ExecutableElement currentElement; |
| 70 /// The 'this' Parameter for currentElement or the enclosing method. | |
| 71 cps_ir.Parameter thisParameter; | |
| 72 cps_ir.Continuation returnContinuation; | 70 cps_ir.Continuation returnContinuation; |
| 73 | 71 |
| 74 Builder parent; | 72 Builder parent; |
| 75 | 73 |
| 76 Builder(this.internalError, [this.parent]); | 74 Builder(this.internalError, [this.parent]); |
| 77 | 75 |
| 78 Builder createInnerBuilder() { | 76 Builder createInnerBuilder() { |
| 79 return new Builder(internalError, this); | 77 return new Builder(internalError, this); |
| 80 } | 78 } |
| 81 | 79 |
| (...skipping 33 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 115 while (variables.length <= primitive.registerIndex) { | 113 while (variables.length <= primitive.registerIndex) { |
| 116 variables.add(new Variable(currentElement, primitive.hint)); | 114 variables.add(new Variable(currentElement, primitive.hint)); |
| 117 } | 115 } |
| 118 return variables[primitive.registerIndex]; | 116 return variables[primitive.registerIndex]; |
| 119 } | 117 } |
| 120 | 118 |
| 121 /// Obtains a reference to the tree Variable corresponding to the IR primitive | 119 /// Obtains a reference to the tree Variable corresponding to the IR primitive |
| 122 /// referred to by [reference]. | 120 /// referred to by [reference]. |
| 123 /// This increments the reference count for the given variable, so the | 121 /// This increments the reference count for the given variable, so the |
| 124 /// returned expression must be used in the tree. | 122 /// returned expression must be used in the tree. |
| 125 Expression getVariableUse(cps_ir.Reference<cps_ir.Primitive> reference) { | 123 VariableUse getVariableUse(cps_ir.Reference<cps_ir.Primitive> reference) { |
| 126 if (thisParameter != null && reference.definition == thisParameter) { | |
| 127 return new This(); | |
| 128 } | |
| 129 Variable variable = getVariable(reference.definition); | 124 Variable variable = getVariable(reference.definition); |
| 130 if (variable == null) { | 125 if (variable == null) { |
| 131 // Note: this may fail because you forgot to implement a visit-function | 126 // Note: this may fail because you forgot to implement a visit-function |
| 132 // in the RegisterAllocator. | 127 // in the RegisterAllocator. |
| 133 internalError( | 128 internalError( |
| 134 CURRENT_ELEMENT_SPANNABLE, | 129 CURRENT_ELEMENT_SPANNABLE, |
| 135 "Reference to ${reference.definition} has no register"); | 130 "Reference to ${reference.definition} has no register"); |
| 136 } | 131 } |
| 137 return new VariableUse(variable); | 132 return new VariableUse(variable); |
| 138 } | 133 } |
| (...skipping 29 matching lines...) Expand all Loading... |
| 168 Variable addFunctionParameter(cps_ir.Definition variable) { | 163 Variable addFunctionParameter(cps_ir.Definition variable) { |
| 169 if (variable is cps_ir.Parameter) { | 164 if (variable is cps_ir.Parameter) { |
| 170 return getVariable(variable); | 165 return getVariable(variable); |
| 171 } else { | 166 } else { |
| 172 return addMutableVariable(variable as cps_ir.MutableVariable); | 167 return addMutableVariable(variable as cps_ir.MutableVariable); |
| 173 } | 168 } |
| 174 } | 169 } |
| 175 | 170 |
| 176 FunctionDefinition buildFunction(cps_ir.FunctionDefinition node) { | 171 FunctionDefinition buildFunction(cps_ir.FunctionDefinition node) { |
| 177 currentElement = node.element; | 172 currentElement = node.element; |
| 178 if (parent != null) { | |
| 179 // Local function's 'this' refers to enclosing method's 'this' | |
| 180 thisParameter = parent.thisParameter; | |
| 181 } else { | |
| 182 thisParameter = node.thisParameter; | |
| 183 } | |
| 184 List<Variable> parameters = | 173 List<Variable> parameters = |
| 185 node.parameters.map(addFunctionParameter).toList(); | 174 node.parameters.map(addFunctionParameter).toList(); |
| 186 Statement body; | 175 Statement body; |
| 187 if (!node.isAbstract) { | 176 if (!node.isAbstract) { |
| 188 returnContinuation = node.body.returnContinuation; | 177 returnContinuation = node.body.returnContinuation; |
| 189 phiTempVar = new Variable(node.element, null); | 178 phiTempVar = new Variable(node.element, null); |
| 190 body = visit(node.body); | 179 body = visit(node.body); |
| 191 } | 180 } |
| 192 | 181 |
| 193 return new FunctionDefinition(node.element, parameters, | 182 return new FunctionDefinition(node.element, parameters, |
| 194 body, node.localConstants, node.defaultParameterValues); | 183 body, node.localConstants, node.defaultParameterValues); |
| 195 } | 184 } |
| 196 | 185 |
| 197 ConstructorDefinition buildConstructor(cps_ir.ConstructorDefinition node) { | 186 ConstructorDefinition buildConstructor(cps_ir.ConstructorDefinition node) { |
| 198 currentElement = node.element; | 187 currentElement = node.element; |
| 199 thisParameter = node.thisParameter; | |
| 200 List<Variable> parameters = | 188 List<Variable> parameters = |
| 201 node.parameters.map(addFunctionParameter).toList(); | 189 node.parameters.map(addFunctionParameter).toList(); |
| 202 List<Initializer> initializers; | 190 List<Initializer> initializers; |
| 203 Statement body; | 191 Statement body; |
| 204 if (!node.isAbstract) { | 192 if (!node.isAbstract) { |
| 205 initializers = node.initializers.map(visit).toList(); | 193 initializers = node.initializers.map(visit).toList(); |
| 206 returnContinuation = node.body.returnContinuation; | 194 returnContinuation = node.body.returnContinuation; |
| 207 | 195 |
| 208 phiTempVar = new Variable(node.element, null); | 196 phiTempVar = new Variable(node.element, null); |
| 209 body = visit(node.body); | 197 body = visit(node.body); |
| (...skipping 14 matching lines...) Expand all Loading... |
| 224 return new List<Expression>.generate(args.length, | 212 return new List<Expression>.generate(args.length, |
| 225 (int index) => getVariableUse(args[index]), | 213 (int index) => getVariableUse(args[index]), |
| 226 growable: false); | 214 growable: false); |
| 227 } | 215 } |
| 228 | 216 |
| 229 /// Returns the list of variables corresponding to the arguments to a join | 217 /// Returns the list of variables corresponding to the arguments to a join |
| 230 /// continuation. | 218 /// continuation. |
| 231 /// | 219 /// |
| 232 /// The `readCount` of these variables will not be incremented. Instead, | 220 /// The `readCount` of these variables will not be incremented. Instead, |
| 233 /// [buildPhiAssignments] will handle the increment, if necessary. | 221 /// [buildPhiAssignments] will handle the increment, if necessary. |
| 234 /* List<Variable> translatePhiArguments(List<cps_ir.Reference> args) { | 222 List<Variable> translatePhiArguments(List<cps_ir.Reference> args) { |
| 235 return new List<Variable>.generate(args.length, | 223 return new List<Variable>.generate(args.length, |
| 236 (int index) => getVariable(args[index].definition), | 224 (int index) => getVariable(args[index].definition), |
| 237 growable: false); | 225 growable: false); |
| 238 }*/ | 226 } |
| 239 | 227 |
| 240 Statement buildContinuationAssignment( | 228 Statement buildContinuationAssignment( |
| 241 cps_ir.Parameter parameter, | 229 cps_ir.Parameter parameter, |
| 242 Expression argument, | 230 Expression argument, |
| 243 Statement buildRest()) { | 231 Statement buildRest()) { |
| 244 Variable variable = getVariable(parameter); | 232 Variable variable = getVariable(parameter); |
| 245 Statement assignment; | 233 Statement assignment; |
| 246 if (variable == null) { | 234 if (variable == null) { |
| 247 assignment = new ExpressionStatement(argument, null); | 235 assignment = new ExpressionStatement(argument, null); |
| 248 } else { | 236 } else { |
| 249 assignment = new Assign(variable, argument, null); | 237 assignment = new Assign(variable, argument, null); |
| 250 } | 238 } |
| 251 assignment.next = buildRest(); | 239 assignment.next = buildRest(); |
| 252 return assignment; | 240 return assignment; |
| 253 } | 241 } |
| 254 | 242 |
| 255 /// Simultaneously assigns each argument to the corresponding parameter, | 243 /// Simultaneously assigns each argument to the corresponding parameter, |
| 256 /// then continues at the statement created by [buildRest]. | 244 /// then continues at the statement created by [buildRest]. |
| 257 Statement buildPhiAssignments( | 245 Statement buildPhiAssignments( |
| 258 List<cps_ir.Parameter> parameters, | 246 List<cps_ir.Parameter> parameters, |
| 259 List<Expression> arguments, | 247 List<Variable> arguments, |
| 260 Statement buildRest()) { | 248 Statement buildRest()) { |
| 261 assert(parameters.length == arguments.length); | 249 assert(parameters.length == arguments.length); |
| 262 // We want a parallel assignment to all parameters simultaneously. | 250 // We want a parallel assignment to all parameters simultaneously. |
| 263 // Since we do not have parallel assignments in dart_tree, we must linearize | 251 // Since we do not have parallel assignments in dart_tree, we must linearize |
| 264 // the assignments without attempting to read a previously-overwritten | 252 // the assignments without attempting to read a previously-overwritten |
| 265 // value. For example {x,y = y,x} cannot be linearized to {x = y; y = x}, | 253 // value. For example {x,y = y,x} cannot be linearized to {x = y; y = x}, |
| 266 // for this we must introduce a temporary variable: {t = x; x = y; y = t}. | 254 // for this we must introduce a temporary variable: {t = x; x = y; y = t}. |
| 267 | 255 |
| 268 // [rightHand] is the inverse of [arguments], that is, it maps variables | 256 // [rightHand] is the inverse of [arguments], that is, it maps variables |
| 269 // to the assignments on which is occurs as the right-hand side. | 257 // to the assignments on which is occurs as the right-hand side. |
| 270 Map<Variable, List<int>> rightHand = <Variable, List<int>>{}; | 258 Map<Variable, List<int>> rightHand = <Variable, List<int>>{}; |
| 271 for (int i = 0; i < parameters.length; i++) { | 259 for (int i = 0; i < parameters.length; i++) { |
| 272 Variable param = getVariable(parameters[i]); | 260 Variable param = getVariable(parameters[i]); |
| 273 Expression arg = arguments[i]; | 261 Variable arg = arguments[i]; |
| 274 if (arg is VariableUse) { | 262 if (param == null || param == arg) { |
| 275 if (param == null || param == arg.variable) { | 263 continue; // No assignment necessary. |
| 276 // No assignment necessary. | 264 } |
| 277 --arg.variable.readCount; | 265 List<int> list = rightHand[arg]; |
| 278 continue; | 266 if (list == null) { |
| 279 } | 267 rightHand[arg] = list = <int>[]; |
| 280 // v1 = v0 | 268 } |
| 281 List<int> list = rightHand[arg.variable]; | 269 list.add(i); |
| 282 if (list == null) { | 270 } |
| 283 rightHand[arg.variable] = list = <int>[]; | 271 |
| 284 } | 272 Statement first, current; |
| 285 list.add(i); | 273 void addAssignment(Variable dst, Variable src) { |
| 274 if (first == null) { |
| 275 first = current = new Assign(dst, new VariableUse(src), null); |
| 286 } else { | 276 } else { |
| 287 // v1 = this; | 277 current = current.next = new Assign(dst, new VariableUse(src), null); |
| 288 } | 278 } |
| 289 } | 279 } |
| 290 | 280 |
| 291 Statement first, current; | 281 List<Variable> assignmentSrc = new List<Variable>(parameters.length); |
| 292 void addAssignment(Variable dst, Expression src) { | 282 List<bool> done = new List<bool>(parameters.length); |
| 293 if (first == null) { | |
| 294 first = current = new Assign(dst, src, null); | |
| 295 } else { | |
| 296 current = current.next = new Assign(dst, src, null); | |
| 297 } | |
| 298 } | |
| 299 | |
| 300 List<Expression> assignmentSrc = new List<Expression>(parameters.length); | |
| 301 List<bool> done = new List<bool>.filled(parameters.length, false); | |
| 302 void visitAssignment(int i) { | 283 void visitAssignment(int i) { |
| 303 if (done[i]) { | 284 if (done[i] == true) { |
| 304 return; | 285 return; |
| 305 } | 286 } |
| 306 Variable param = getVariable(parameters[i]); | 287 Variable param = getVariable(parameters[i]); |
| 307 Expression arg = arguments[i]; | 288 Variable arg = arguments[i]; |
| 308 if (param == null || (arg is VariableUse && param == arg.variable)) { | 289 if (param == null || param == arg) { |
| 309 return; // No assignment necessary. | 290 return; // No assignment necessary. |
| 310 } | 291 } |
| 311 if (assignmentSrc[i] != null) { | 292 if (assignmentSrc[i] != null) { |
| 312 // Cycle found; store argument in a temporary variable. | 293 // Cycle found; store argument in a temporary variable. |
| 313 // The temporary will then be used as right-hand side when the | 294 // The temporary will then be used as right-hand side when the |
| 314 // assignment gets added. | 295 // assignment gets added. |
| 315 VariableUse source = assignmentSrc[i]; | 296 if (assignmentSrc[i] != phiTempVar) { // Only move to temporary once. |
| 316 if (source.variable != phiTempVar) { // Only move to temporary once. | 297 assignmentSrc[i] = phiTempVar; |
| 317 assignmentSrc[i] = new VariableUse(phiTempVar); | |
| 318 addAssignment(phiTempVar, arg); | 298 addAssignment(phiTempVar, arg); |
| 319 } | 299 } |
| 320 return; | 300 return; |
| 321 } | 301 } |
| 322 assignmentSrc[i] = arg; | 302 assignmentSrc[i] = arg; |
| 323 List<int> paramUses = rightHand[param]; | 303 List<int> paramUses = rightHand[param]; |
| 324 if (paramUses != null) { | 304 if (paramUses != null) { |
| 325 for (int useIndex in paramUses) { | 305 for (int useIndex in paramUses) { |
| 326 visitAssignment(useIndex); | 306 visitAssignment(useIndex); |
| 327 } | 307 } |
| 328 } | 308 } |
| 329 addAssignment(param, assignmentSrc[i]); | 309 addAssignment(param, assignmentSrc[i]); |
| 330 done[i] = true; | 310 done[i] = true; |
| 331 } | 311 } |
| 332 | 312 |
| 333 for (int i = 0; i < parameters.length; i++) { | 313 for (int i = 0; i < parameters.length; i++) { |
| 334 if (!done[i]) { | 314 if (done[i] == null) { |
| 335 visitAssignment(i); | 315 visitAssignment(i); |
| 336 } | 316 } |
| 337 } | 317 } |
| 338 | 318 |
| 339 if (first == null) { | 319 if (first == null) { |
| 340 first = buildRest(); | 320 first = buildRest(); |
| 341 } else { | 321 } else { |
| 342 current.next = buildRest(); | 322 current.next = buildRest(); |
| 343 } | 323 } |
| 344 return first; | 324 return first; |
| (...skipping 194 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 539 // Invocations of the return continuation are translated to returns. | 519 // Invocations of the return continuation are translated to returns. |
| 540 // Other continuation invocations are replaced with assignments of the | 520 // Other continuation invocations are replaced with assignments of the |
| 541 // arguments to formal parameter variables, followed by the body if | 521 // arguments to formal parameter variables, followed by the body if |
| 542 // the continuation is singly reference or a break if it is multiply | 522 // the continuation is singly reference or a break if it is multiply |
| 543 // referenced. | 523 // referenced. |
| 544 cps_ir.Continuation cont = node.continuation.definition; | 524 cps_ir.Continuation cont = node.continuation.definition; |
| 545 if (cont == returnContinuation) { | 525 if (cont == returnContinuation) { |
| 546 assert(node.arguments.length == 1); | 526 assert(node.arguments.length == 1); |
| 547 return new Return(getVariableUse(node.arguments.single)); | 527 return new Return(getVariableUse(node.arguments.single)); |
| 548 } else { | 528 } else { |
| 549 List<Expression> arguments = translateArguments(node.arguments); | 529 List<Variable> arguments = translatePhiArguments(node.arguments); |
| 550 return buildPhiAssignments(cont.parameters, arguments, | 530 return buildPhiAssignments(cont.parameters, arguments, |
| 551 () { | 531 () { |
| 552 // Translate invocations of recursive and non-recursive | 532 // Translate invocations of recursive and non-recursive |
| 553 // continuations differently. | 533 // continuations differently. |
| 554 // * Non-recursive continuations | 534 // * Non-recursive continuations |
| 555 // - If there is one use, translate the continuation body | 535 // - If there is one use, translate the continuation body |
| 556 // inline at the invocation site. | 536 // inline at the invocation site. |
| 557 // - If there are multiple uses, translate to Break. | 537 // - If there are multiple uses, translate to Break. |
| 558 // * Recursive continuations | 538 // * Recursive continuations |
| 559 // - There is a single non-recursive invocation. Translate | 539 // - There is a single non-recursive invocation. Translate |
| (...skipping 28 matching lines...) Expand all Loading... |
| 588 assert(cont.parameters.isEmpty); | 568 assert(cont.parameters.isEmpty); |
| 589 elseStatement = | 569 elseStatement = |
| 590 cont.hasExactlyOneUse ? visit(cont.body) : new Break(labels[cont]); | 570 cont.hasExactlyOneUse ? visit(cont.body) : new Break(labels[cont]); |
| 591 return new If(condition, thenStatement, elseStatement); | 571 return new If(condition, thenStatement, elseStatement); |
| 592 } | 572 } |
| 593 | 573 |
| 594 Expression visitConstant(cps_ir.Constant node) { | 574 Expression visitConstant(cps_ir.Constant node) { |
| 595 return new Constant(node.expression); | 575 return new Constant(node.expression); |
| 596 } | 576 } |
| 597 | 577 |
| 578 Expression visitThis(cps_ir.This node) { |
| 579 return new This(); |
| 580 } |
| 581 |
| 598 Expression visitReifyTypeVar(cps_ir.ReifyTypeVar node) { | 582 Expression visitReifyTypeVar(cps_ir.ReifyTypeVar node) { |
| 599 return new ReifyTypeVar(node.typeVariable); | 583 return new ReifyTypeVar(node.typeVariable); |
| 600 } | 584 } |
| 601 | 585 |
| 602 Expression visitLiteralList(cps_ir.LiteralList node) { | 586 Expression visitLiteralList(cps_ir.LiteralList node) { |
| 603 return new LiteralList( | 587 return new LiteralList( |
| 604 node.type, | 588 node.type, |
| 605 translateArguments(node.values)); | 589 translateArguments(node.values)); |
| 606 } | 590 } |
| 607 | 591 |
| (...skipping 48 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 656 } | 640 } |
| 657 | 641 |
| 658 Expression visitReifyRuntimeType(cps_ir.ReifyRuntimeType node) { | 642 Expression visitReifyRuntimeType(cps_ir.ReifyRuntimeType node) { |
| 659 return new ReifyRuntimeType(getVariableUse(node.value)); | 643 return new ReifyRuntimeType(getVariableUse(node.value)); |
| 660 } | 644 } |
| 661 | 645 |
| 662 Expression visitReadTypeVariable(cps_ir.ReadTypeVariable node) { | 646 Expression visitReadTypeVariable(cps_ir.ReadTypeVariable node) { |
| 663 return new ReadTypeVariable(node.variable, getVariableUse(node.target)); | 647 return new ReadTypeVariable(node.variable, getVariableUse(node.target)); |
| 664 } | 648 } |
| 665 } | 649 } |
| OLD | NEW |