| OLD | NEW |
|---|
| (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 library tree_ir_builder; | |
| 6 | |
| 7 import '../dart2jslib.dart' as dart2js; | |
| 8 import '../dart_types.dart'; | |
| 9 import '../elements/elements.dart'; | |
| 10 import '../cps_ir/cps_ir_nodes.dart' as cps_ir; | |
| 11 import 'tree_ir_nodes.dart'; | |
| 12 | |
| 13 /** | |
| 14 * Builder translates from CPS-based IR to direct-style Tree. | |
| 15 * | |
| 16 * 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 | |
| 18 * whose value is bound in the continuation body: | |
| 19 * | |
| 20 * `LetVal(v, Invoke(fun, args), body)` | |
| 21 * | |
| 22 * and the continuation definition is eliminated. A similar translation is | |
| 23 * applied to continuation invocations where the continuation is | |
| 24 * singly-referenced, though such invocations should not appear in optimized | |
| 25 * IR. | |
| 26 * | |
| 27 * A call `Invoke(fun, cont, args)`, where cont is multiply referenced, is | |
| 28 * translated into a call followed by a jump with an argument: | |
| 29 * | |
| 30 * `Jump L(Invoke(fun, args))` | |
| 31 * | |
| 32 * and the continuation is translated into a named block that takes an | |
| 33 * argument: | |
| 34 * | |
| 35 * `LetLabel(L, v, body)` | |
| 36 * | |
| 37 * 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 | |
| 39 * control-flow recognition. | |
| 40 * | |
| 41 * Otherwise, the output of Builder looks very much like the input. In | |
| 42 * particular, intermediate values and blocks used for local control flow are | |
| 43 * still all named. | |
| 44 */ | |
| 45 class Builder extends cps_ir.Visitor<Node> { | |
| 46 final dart2js.Compiler compiler; | |
| 47 | |
| 48 /// Maps variable/parameter elements to the Tree variables that represent it. | |
| 49 final Map<Element, List<Variable>> element2variables = | |
| 50 <Element,List<Variable>>{}; | |
| 51 | |
| 52 /// Like [element2variables], except for closure variables. Closure variables | |
| 53 /// are not subject to SSA, so at most one variable is used per local. | |
| 54 final Map<Local, Variable> local2closure = <Local, Variable>{}; | |
| 55 | |
| 56 // Continuations with more than one use are replaced with Tree labels. This | |
| 57 // is the mapping from continuations to labels. | |
| 58 final Map<cps_ir.Continuation, Label> labels = <cps_ir.Continuation, Label>{}; | |
| 59 | |
| 60 FunctionDefinition function; | |
| 61 cps_ir.Continuation returnContinuation; | |
| 62 | |
| 63 Builder parent; | |
| 64 | |
| 65 Builder(this.compiler); | |
| 66 | |
| 67 Builder.inner(Builder parent) | |
| 68 : this.parent = parent, | |
| 69 compiler = parent.compiler; | |
| 70 | |
| 71 /// Variable used in [buildPhiAssignments] as a temporary when swapping | |
| 72 /// variables. | |
| 73 Variable phiTempVar; | |
| 74 | |
| 75 Variable getClosureVariable(Local local) { | |
| 76 if (local.executableContext != function.element) { | |
| 77 return parent.getClosureVariable(local); | |
| 78 } | |
| 79 Variable variable = local2closure[local]; | |
| 80 if (variable == null) { | |
| 81 variable = new Variable(function, local); | |
| 82 local2closure[local] = variable; | |
| 83 } | |
| 84 return variable; | |
| 85 } | |
| 86 | |
| 87 /// Obtains the variable representing the given primitive. Returns null for | |
| 88 /// primitives that have no reference and do not need a variable. | |
| 89 Variable getVariable(cps_ir.Primitive primitive) { | |
| 90 if (primitive.registerIndex == null) { | |
| 91 return null; // variable is unused | |
| 92 } | |
| 93 List<Variable> variables = element2variables[primitive.hint]; | |
| 94 if (variables == null) { | |
| 95 variables = <Variable>[]; | |
| 96 element2variables[primitive.hint] = variables; | |
| 97 } | |
| 98 while (variables.length <= primitive.registerIndex) { | |
| 99 variables.add(new Variable(function, primitive.hint)); | |
| 100 } | |
| 101 return variables[primitive.registerIndex]; | |
| 102 } | |
| 103 | |
| 104 /// Obtains a reference to the tree Variable corresponding to the IR primitive | |
| 105 /// referred to by [reference]. | |
| 106 /// This increments the reference count for the given variable, so the | |
| 107 /// returned expression must be used in the tree. | |
| 108 Expression getVariableReference(cps_ir.Reference reference) { | |
| 109 Variable variable = getVariable(reference.definition); | |
| 110 if (variable == null) { | |
| 111 compiler.internalError( | |
| 112 compiler.currentElement, | |
| 113 "Reference to ${reference.definition} has no register"); | |
| 114 } | |
| 115 ++variable.readCount; | |
| 116 return variable; | |
| 117 } | |
| 118 | |
| 119 FunctionDefinition build(cps_ir.FunctionDefinition node) { | |
| 120 visit(node); | |
| 121 return function; | |
| 122 } | |
| 123 | |
| 124 List<Expression> translateArguments(List<cps_ir.Reference> args) { | |
| 125 return new List<Expression>.generate(args.length, | |
| 126 (int index) => getVariableReference(args[index])); | |
| 127 } | |
| 128 | |
| 129 List<Variable> translatePhiArguments(List<cps_ir.Reference> args) { | |
| 130 return new List<Variable>.generate(args.length, | |
| 131 (int index) => getVariableReference(args[index])); | |
| 132 } | |
| 133 | |
| 134 Statement buildContinuationAssignment( | |
| 135 cps_ir.Parameter parameter, | |
| 136 Expression argument, | |
| 137 Statement buildRest()) { | |
| 138 Variable variable = getVariable(parameter); | |
| 139 Statement assignment; | |
| 140 if (variable == null) { | |
| 141 assignment = new ExpressionStatement(argument, null); | |
| 142 } else { | |
| 143 assignment = new Assign(variable, argument, null); | |
| 144 } | |
| 145 assignment.next = buildRest(); | |
| 146 return assignment; | |
| 147 } | |
| 148 | |
| 149 /// Simultaneously assigns each argument to the corresponding parameter, | |
| 150 /// then continues at the statement created by [buildRest]. | |
| 151 Statement buildPhiAssignments( | |
| 152 List<cps_ir.Parameter> parameters, | |
| 153 List<Variable> arguments, | |
| 154 Statement buildRest()) { | |
| 155 assert(parameters.length == arguments.length); | |
| 156 // We want a parallel assignment to all parameters simultaneously. | |
| 157 // Since we do not have parallel assignments in dart_tree, we must linearize | |
| 158 // the assignments without attempting to read a previously-overwritten | |
| 159 // value. For example {x,y = y,x} cannot be linearized to {x = y; y = x}, | |
| 160 // for this we must introduce a temporary variable: {t = x; x = y; y = t}. | |
| 161 | |
| 162 // [rightHand] is the inverse of [arguments], that is, it maps variables | |
| 163 // to the assignments on which is occurs as the right-hand side. | |
| 164 Map<Variable, List<int>> rightHand = <Variable, List<int>>{}; | |
| 165 for (int i = 0; i < parameters.length; i++) { | |
| 166 Variable param = getVariable(parameters[i]); | |
| 167 Variable arg = arguments[i]; | |
| 168 if (param == null || param == arg) { | |
| 169 continue; // No assignment necessary. | |
| 170 } | |
| 171 List<int> list = rightHand[arg]; | |
| 172 if (list == null) { | |
| 173 rightHand[arg] = list = <int>[]; | |
| 174 } | |
| 175 list.add(i); | |
| 176 } | |
| 177 | |
| 178 Statement first, current; | |
| 179 void addAssignment(Variable dst, Variable src) { | |
| 180 if (first == null) { | |
| 181 first = current = new Assign(dst, src, null); | |
| 182 } else { | |
| 183 current = current.next = new Assign(dst, src, null); | |
| 184 } | |
| 185 } | |
| 186 | |
| 187 List<Variable> assignmentSrc = new List<Variable>(parameters.length); | |
| 188 List<bool> done = new List<bool>(parameters.length); | |
| 189 void visitAssignment(int i) { | |
| 190 if (done[i] == true) { | |
| 191 return; | |
| 192 } | |
| 193 Variable param = getVariable(parameters[i]); | |
| 194 Variable arg = arguments[i]; | |
| 195 if (param == null || param == arg) { | |
| 196 return; // No assignment necessary. | |
| 197 } | |
| 198 if (assignmentSrc[i] != null) { | |
| 199 // Cycle found; store argument in a temporary variable. | |
| 200 // The temporary will then be used as right-hand side when the | |
| 201 // assignment gets added. | |
| 202 if (assignmentSrc[i] != phiTempVar) { // Only move to temporary once. | |
| 203 assignmentSrc[i] = phiTempVar; | |
| 204 addAssignment(phiTempVar, arg); | |
| 205 } | |
| 206 return; | |
| 207 } | |
| 208 assignmentSrc[i] = arg; | |
| 209 List<int> paramUses = rightHand[param]; | |
| 210 if (paramUses != null) { | |
| 211 for (int useIndex in paramUses) { | |
| 212 visitAssignment(useIndex); | |
| 213 } | |
| 214 } | |
| 215 addAssignment(param, assignmentSrc[i]); | |
| 216 done[i] = true; | |
| 217 } | |
| 218 | |
| 219 for (int i = 0; i < parameters.length; i++) { | |
| 220 if (done[i] == null) { | |
| 221 visitAssignment(i); | |
| 222 } | |
| 223 } | |
| 224 | |
| 225 if (first == null) { | |
| 226 first = buildRest(); | |
| 227 } else { | |
| 228 current.next = buildRest(); | |
| 229 } | |
| 230 return first; | |
| 231 } | |
| 232 | |
| 233 visitNode(cps_ir.Node node) => throw "Unhandled node: $node"; | |
| 234 | |
| 235 Expression visitFunctionDefinition(cps_ir.FunctionDefinition node) { | |
| 236 List<Variable> parameters = <Variable>[]; | |
| 237 function = new FunctionDefinition(node.element, parameters, | |
| 238 null, node.localConstants, node.defaultParameterValues); | |
| 239 returnContinuation = node.returnContinuation; | |
| 240 for (cps_ir.Parameter p in node.parameters) { | |
| 241 Variable parameter = getVariable(p); | |
| 242 assert(parameter != null); | |
| 243 ++parameter.writeCount; // Being a parameter counts as a write. | |
| 244 parameters.add(parameter); | |
| 245 } | |
| 246 if (!node.isAbstract) { | |
| 247 phiTempVar = new Variable(function, null); | |
| 248 function.body = visit(node.body); | |
| 249 } | |
| 250 return null; | |
| 251 } | |
| 252 | |
| 253 Statement visitLetPrim(cps_ir.LetPrim node) { | |
| 254 Variable variable = getVariable(node.primitive); | |
| 255 | |
| 256 // Don't translate unused primitives. | |
| 257 if (variable == null) return visit(node.body); | |
| 258 | |
| 259 Node definition = visit(node.primitive); | |
| 260 | |
| 261 // visitPrimitive returns a Statement without successor if it cannot occur | |
| 262 // in expression context (currently only the case for FunctionDeclarations). | |
| 263 if (definition is Statement) { | |
| 264 definition.next = visit(node.body); | |
| 265 return definition; | |
| 266 } else { | |
| 267 return new Assign(variable, definition, visit(node.body)); | |
| 268 } | |
| 269 } | |
| 270 | |
| 271 Statement visitLetCont(cps_ir.LetCont node) { | |
| 272 Label label; | |
| 273 if (node.continuation.hasMultipleUses) { | |
| 274 label = new Label(); | |
| 275 labels[node.continuation] = label; | |
| 276 } | |
| 277 Statement body = visit(node.body); | |
| 278 // The continuation's body is not always translated directly here because | |
| 279 // it may have been already translated: | |
| 280 // * For singly-used continuations, the continuation's body is | |
| 281 // translated at the site of the continuation invocation. | |
| 282 // * For recursive continuations, there is a single non-recursive | |
| 283 // invocation. The continuation's body is translated at the site | |
| 284 // of the non-recursive continuation invocation. | |
| 285 // See visitInvokeContinuation for the implementation. | |
| 286 if (label == null || node.continuation.isRecursive) return body; | |
| 287 return new LabeledStatement(label, body, visit(node.continuation.body)); | |
| 288 } | |
| 289 | |
| 290 Statement visitInvokeStatic(cps_ir.InvokeStatic node) { | |
| 291 // Calls are translated to direct style. | |
| 292 List<Expression> arguments = translateArguments(node.arguments); | |
| 293 Expression invoke = new InvokeStatic(node.target, node.selector, arguments); | |
| 294 return continueWithExpression(node.continuation, invoke); | |
| 295 } | |
| 296 | |
| 297 Statement visitInvokeMethod(cps_ir.InvokeMethod node) { | |
| 298 Expression receiver = getVariableReference(node.receiver); | |
| 299 List<Expression> arguments = translateArguments(node.arguments); | |
| 300 Expression invoke = new InvokeMethod(receiver, node.selector, arguments); | |
| 301 return continueWithExpression(node.continuation, invoke); | |
| 302 } | |
| 303 | |
| 304 Statement visitInvokeSuperMethod(cps_ir.InvokeSuperMethod node) { | |
| 305 List<Expression> arguments = translateArguments(node.arguments); | |
| 306 Expression invoke = new InvokeSuperMethod(node.selector, arguments); | |
| 307 return continueWithExpression(node.continuation, invoke); | |
| 308 } | |
| 309 | |
| 310 Statement visitConcatenateStrings(cps_ir.ConcatenateStrings node) { | |
| 311 List<Expression> arguments = translateArguments(node.arguments); | |
| 312 Expression concat = new ConcatenateStrings(arguments); | |
| 313 return continueWithExpression(node.continuation, concat); | |
| 314 } | |
| 315 | |
| 316 Statement continueWithExpression(cps_ir.Reference continuation, | |
| 317 Expression expression) { | |
| 318 cps_ir.Continuation cont = continuation.definition; | |
| 319 if (cont == returnContinuation) { | |
| 320 return new Return(expression); | |
| 321 } else { | |
| 322 assert(cont.parameters.length == 1); | |
| 323 Function nextBuilder = cont.hasExactlyOneUse ? | |
| 324 () => visit(cont.body) : () => new Break(labels[cont]); | |
| 325 return buildContinuationAssignment(cont.parameters.single, expression, | |
| 326 nextBuilder); | |
| 327 } | |
| 328 } | |
| 329 | |
| 330 Expression visitGetClosureVariable(cps_ir.GetClosureVariable node) { | |
| 331 return getClosureVariable(node.variable); | |
| 332 } | |
| 333 | |
| 334 Statement visitSetClosureVariable(cps_ir.SetClosureVariable node) { | |
| 335 Variable variable = getClosureVariable(node.variable); | |
| 336 Expression value = getVariableReference(node.value); | |
| 337 return new Assign(variable, value, visit(node.body), | |
| 338 isDeclaration: node.isDeclaration); | |
| 339 } | |
| 340 | |
| 341 Statement visitDeclareFunction(cps_ir.DeclareFunction node) { | |
| 342 Variable variable = getClosureVariable(node.variable); | |
| 343 FunctionDefinition function = makeSubFunction(node.definition); | |
| 344 return new FunctionDeclaration(variable, function, visit(node.body)); | |
| 345 } | |
| 346 | |
| 347 Statement visitTypeOperator(cps_ir.TypeOperator node) { | |
| 348 Expression receiver = getVariableReference(node.receiver); | |
| 349 Expression concat = | |
| 350 new TypeOperator(receiver, node.type, isTypeTest: node.isTypeTest); | |
| 351 return continueWithExpression(node.continuation, concat); | |
| 352 } | |
| 353 | |
| 354 Statement visitInvokeConstructor(cps_ir.InvokeConstructor node) { | |
| 355 List<Expression> arguments = translateArguments(node.arguments); | |
| 356 Expression invoke = | |
| 357 new InvokeConstructor(node.type, node.target, node.selector, arguments); | |
| 358 return continueWithExpression(node.continuation, invoke); | |
| 359 } | |
| 360 | |
| 361 Statement visitInvokeContinuation(cps_ir.InvokeContinuation node) { | |
| 362 // Invocations of the return continuation are translated to returns. | |
| 363 // Other continuation invocations are replaced with assignments of the | |
| 364 // arguments to formal parameter variables, followed by the body if | |
| 365 // the continuation is singly reference or a break if it is multiply | |
| 366 // referenced. | |
| 367 cps_ir.Continuation cont = node.continuation.definition; | |
| 368 if (cont == returnContinuation) { | |
| 369 assert(node.arguments.length == 1); | |
| 370 return new Return(getVariableReference(node.arguments.single)); | |
| 371 } else { | |
| 372 List<Expression> arguments = translatePhiArguments(node.arguments); | |
| 373 return buildPhiAssignments(cont.parameters, arguments, | |
| 374 () { | |
| 375 // Translate invocations of recursive and non-recursive | |
| 376 // continuations differently. | |
| 377 // * Non-recursive continuations | |
| 378 // - If there is one use, translate the continuation body | |
| 379 // inline at the invocation site. | |
| 380 // - If there are multiple uses, translate to Break. | |
| 381 // * Recursive continuations | |
| 382 // - There is a single non-recursive invocation. Translate | |
| 383 // the continuation body inline as a labeled loop at the | |
| 384 // invocation site. | |
| 385 // - Translate the recursive invocations to Continue. | |
| 386 if (cont.isRecursive) { | |
| 387 return node.isRecursive | |
| 388 ? new Continue(labels[cont]) | |
| 389 : new WhileTrue(labels[cont], visit(cont.body)); | |
| 390 } else { | |
| 391 return cont.hasExactlyOneUse | |
| 392 ? visit(cont.body) | |
| 393 : new Break(labels[cont]); | |
| 394 } | |
| 395 }); | |
| 396 } | |
| 397 } | |
| 398 | |
| 399 Statement visitBranch(cps_ir.Branch node) { | |
| 400 Expression condition = visit(node.condition); | |
| 401 Statement thenStatement, elseStatement; | |
| 402 cps_ir.Continuation cont = node.trueContinuation.definition; | |
| 403 assert(cont.parameters.isEmpty); | |
| 404 thenStatement = | |
| 405 cont.hasExactlyOneUse ? visit(cont.body) : new Break(labels[cont]); | |
| 406 cont = node.falseContinuation.definition; | |
| 407 assert(cont.parameters.isEmpty); | |
| 408 elseStatement = | |
| 409 cont.hasExactlyOneUse ? visit(cont.body) : new Break(labels[cont]); | |
| 410 return new If(condition, thenStatement, elseStatement); | |
| 411 } | |
| 412 | |
| 413 Expression visitConstant(cps_ir.Constant node) { | |
| 414 return new Constant(node.expression); | |
| 415 } | |
| 416 | |
| 417 Expression visitThis(cps_ir.This node) { | |
| 418 return new This(); | |
| 419 } | |
| 420 | |
| 421 Expression visitReifyTypeVar(cps_ir.ReifyTypeVar node) { | |
| 422 return new ReifyTypeVar(node.typeVariable); | |
| 423 } | |
| 424 | |
| 425 Expression visitLiteralList(cps_ir.LiteralList node) { | |
| 426 return new LiteralList( | |
| 427 node.type, | |
| 428 translateArguments(node.values)); | |
| 429 } | |
| 430 | |
| 431 Expression visitLiteralMap(cps_ir.LiteralMap node) { | |
| 432 return new LiteralMap( | |
| 433 node.type, | |
| 434 new List<LiteralMapEntry>.generate(node.entries.length, (int index) { | |
| 435 return new LiteralMapEntry( | |
| 436 getVariableReference(node.entries[index].key), | |
| 437 getVariableReference(node.entries[index].value)); | |
| 438 }) | |
| 439 ); | |
| 440 } | |
| 441 | |
| 442 FunctionDefinition makeSubFunction(cps_ir.FunctionDefinition function) { | |
| 443 return new Builder.inner(this).build(function); | |
| 444 } | |
| 445 | |
| 446 Node visitCreateFunction(cps_ir.CreateFunction node) { | |
| 447 FunctionDefinition def = makeSubFunction(node.definition); | |
| 448 FunctionType type = node.definition.element.type; | |
| 449 bool hasReturnType = !type.returnType.treatAsDynamic; | |
| 450 if (hasReturnType) { | |
| 451 // This function cannot occur in expression context. | |
| 452 // The successor will be filled in by visitLetPrim. | |
| 453 return new FunctionDeclaration(getVariable(node), def, null); | |
| 454 } else { | |
| 455 return new FunctionExpression(def); | |
| 456 } | |
| 457 } | |
| 458 | |
| 459 Expression visitParameter(cps_ir.Parameter node) { | |
| 460 // Continuation parameters are not visited (continuations themselves are | |
| 461 // not visited yet). | |
| 462 compiler.internalError(compiler.currentElement, 'Unexpected IR node.'); | |
| 463 return null; | |
| 464 } | |
| 465 | |
| 466 Expression visitContinuation(cps_ir.Continuation node) { | |
| 467 // Until continuations with multiple uses are supported, they are not | |
| 468 // visited. | |
| 469 compiler.internalError(compiler.currentElement, 'Unexpected IR node.'); | |
| 470 return null; | |
| 471 } | |
| 472 | |
| 473 Expression visitIsTrue(cps_ir.IsTrue node) { | |
| 474 return getVariableReference(node.value); | |
| 475 } | |
| 476 } | |
| 477 | |
| OLD | NEW |
|---|
Chromium Code Reviews
Issue 694353007:
Move dart2js from sdk/lib/_internal/compiler to pkg/compiler (Closed)
Base URL: https://dart.googlecode.com/svn/branches/bleeding_edge/dart