| OLD | NEW |
|---|
| (Empty) |
| 1 // Copyright (c) 2013, 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 dart2js.ir_builder; | |
| 6 | |
| 7 import '../constants/expressions.dart'; | |
| 8 import '../constants/values.dart' show PrimitiveConstantValue; | |
| 9 import '../dart_backend/dart_backend.dart' show DartBackend; | |
| 10 import '../dart_types.dart'; | |
| 11 import '../dart2jslib.dart'; | |
| 12 import '../elements/elements.dart'; | |
| 13 import '../source_file.dart'; | |
| 14 import '../tree/tree.dart' as ast; | |
| 15 import '../scanner/scannerlib.dart' show Token, isUserDefinableOperator; | |
| 16 import '../universe/universe.dart' show SelectorKind; | |
| 17 import 'cps_ir_nodes.dart' as ir; | |
| 18 | |
| 19 part 'cps_ir_builder_visitor.dart'; | |
| 20 | |
| 21 /// A mapping from variable elements to their compile-time values. | |
| 22 /// | |
| 23 /// Map elements denoted by parameters and local variables to the | |
| 24 /// [ir.Primitive] that is their value. Parameters and locals are | |
| 25 /// assigned indexes which can be used to refer to them. | |
| 26 class Environment { | |
| 27 /// A map from elements to their environment index. | |
| 28 final Map<Element, int> variable2index; | |
| 29 | |
| 30 /// A reverse map from environment indexes to the variable. | |
| 31 final List<Element> index2variable; | |
| 32 | |
| 33 /// A map from environment indexes to their value. | |
| 34 final List<ir.Primitive> index2value; | |
| 35 | |
| 36 Environment.empty() | |
| 37 : variable2index = <Element, int>{}, | |
| 38 index2variable = <Element>[], | |
| 39 index2value = <ir.Primitive>[]; | |
| 40 | |
| 41 /// Construct an environment that is a copy of another one. | |
| 42 /// | |
| 43 /// The mapping from elements to indexes is shared, not copied. | |
| 44 Environment.from(Environment other) | |
| 45 : variable2index = other.variable2index, | |
| 46 index2variable = new List<Element>.from(other.index2variable), | |
| 47 index2value = new List<ir.Primitive>.from(other.index2value); | |
| 48 | |
| 49 get length => index2variable.length; | |
| 50 | |
| 51 ir.Primitive operator [](int index) => index2value[index]; | |
| 52 | |
| 53 void extend(Element element, ir.Primitive value) { | |
| 54 // Assert that the name is not already in the environment. `null` is used | |
| 55 // as the name of anonymous variables. Because the variable2index map is | |
| 56 // shared, `null` can already occur. This is safe because such variables | |
| 57 // are not looked up by name. | |
| 58 // | |
| 59 // TODO(kmillikin): This is still kind of fishy. Refactor to not share | |
| 60 // name maps or else garbage collect unneeded names. | |
| 61 assert(element == null || !variable2index.containsKey(element)); | |
| 62 variable2index[element] = index2variable.length; | |
| 63 index2variable.add(element); | |
| 64 index2value.add(value); | |
| 65 } | |
| 66 | |
| 67 ir.Primitive lookup(Element element) { | |
| 68 assert(!element.isConst); | |
| 69 assert(invariant(element, variable2index.containsKey(element), | |
| 70 message: "Unknown variable: $element.")); | |
| 71 return index2value[variable2index[element]]; | |
| 72 } | |
| 73 | |
| 74 void update(Element element, ir.Primitive value) { | |
| 75 index2value[variable2index[element]] = value; | |
| 76 } | |
| 77 | |
| 78 /// Verify that the variable2index and index2variable maps agree up to the | |
| 79 /// index [length] exclusive. | |
| 80 bool sameDomain(int length, Environment other) { | |
| 81 assert(this.length >= length); | |
| 82 assert(other.length >= length); | |
| 83 for (int i = 0; i < length; ++i) { | |
| 84 // An index maps to the same variable in both environments. | |
| 85 Element variable = index2variable[i]; | |
| 86 if (variable != other.index2variable[i]) return false; | |
| 87 | |
| 88 // The variable maps to the same index in both environments. | |
| 89 int index = variable2index[variable]; | |
| 90 if (index == null || index != other.variable2index[variable]) { | |
| 91 return false; | |
| 92 } | |
| 93 } | |
| 94 return true; | |
| 95 } | |
| 96 } | |
| 97 | |
| 98 /// A class to collect breaks or continues. | |
| 99 /// | |
| 100 /// When visiting a potential target of breaks or continues, any breaks or | |
| 101 /// continues are collected by a JumpCollector and processed later, on demand. | |
| 102 /// The site of the break or continue is represented by a continuation | |
| 103 /// invocation that will have its target and arguments filled in later. | |
| 104 /// | |
| 105 /// The environment of the builder at that point is captured and should not | |
| 106 /// be subsequently mutated until the jump is resolved. | |
| 107 class JumpCollector { | |
| 108 final JumpTarget target; | |
| 109 final List<ir.InvokeContinuation> _invocations = <ir.InvokeContinuation>[]; | |
| 110 final List<Environment> _environments = <Environment>[]; | |
| 111 | |
| 112 JumpCollector(this.target); | |
| 113 | |
| 114 bool get isEmpty => _invocations.isEmpty; | |
| 115 int get length => _invocations.length; | |
| 116 List<ir.InvokeContinuation> get invocations => _invocations; | |
| 117 List<Environment> get environments => _environments; | |
| 118 | |
| 119 void addJump(IrBuilder builder) { | |
| 120 ir.InvokeContinuation invoke = new ir.InvokeContinuation.uninitialized(); | |
| 121 builder.add(invoke); | |
| 122 _invocations.add(invoke); | |
| 123 _environments.add(builder.environment); | |
| 124 builder._current = null; | |
| 125 // TODO(kmillikin): Can we set builder.environment to null to make it | |
| 126 // less likely to mutate it? | |
| 127 } | |
| 128 } | |
| 129 | |
| 130 /// Function for building a node in the context of the current builder. | |
| 131 typedef ir.Node BuildFunction(node); | |
| 132 | |
| 133 /// Function for building nodes in the context of the provided [builder]. | |
| 134 typedef ir.Node SubbuildFunction(IrBuilder builder); | |
| 135 | |
| 136 /// Mixin that provides encapsulated access to nested builders. | |
| 137 abstract class IrBuilderMixin<N> { | |
| 138 IrBuilder _irBuilder; | |
| 139 | |
| 140 /// Execute [f] with [builder] as the current builder. | |
| 141 withBuilder(IrBuilder builder, f()) { | |
| 142 assert(builder != null); | |
| 143 IrBuilder prev = _irBuilder; | |
| 144 _irBuilder = builder; | |
| 145 var result = f(); | |
| 146 _irBuilder = prev; | |
| 147 return result; | |
| 148 } | |
| 149 | |
| 150 /// The current builder. | |
| 151 IrBuilder get irBuilder { | |
| 152 assert(_irBuilder != null); | |
| 153 return _irBuilder; | |
| 154 } | |
| 155 | |
| 156 /// Visits the [node]. | |
| 157 ir.Primitive visit(N node); | |
| 158 | |
| 159 /// Builds and returns the [ir.Node] for [node] or returns `null` if | |
| 160 /// [node] is `null`. | |
| 161 ir.Node build(N node) => node != null ? visit(node) : null; | |
| 162 | |
| 163 /// Returns a closure that takes an [IrBuilder] and builds [node] in its | |
| 164 /// context using [build]. | |
| 165 SubbuildFunction subbuild(N node) { | |
| 166 return (IrBuilder builder) => withBuilder(builder, () => build(node)); | |
| 167 } | |
| 168 | |
| 169 /// Returns a closure that takes an [IrBuilder] and builds the sequence of | |
| 170 /// [nodes] in its context using [build]. | |
| 171 // TODO(johnniwinther): Type [nodes] as `Iterable<N>` when `NodeList` uses | |
| 172 // `List` instead of `Link`. | |
| 173 SubbuildFunction subbuildSequence(/*Iterable<N>*/ nodes) { | |
| 174 return (IrBuilder builder) { | |
| 175 return withBuilder(builder, () => builder.buildSequence(nodes, build)); | |
| 176 }; | |
| 177 } | |
| 178 } | |
| 179 | |
| 180 /// Shared state between nested builders. | |
| 181 class IrBuilderSharedState { | |
| 182 final ConstantSystem constantSystem; | |
| 183 | |
| 184 /// A stack of collectors for breaks. | |
| 185 final List<JumpCollector> breakCollectors = <JumpCollector>[]; | |
| 186 | |
| 187 /// A stack of collectors for continues. | |
| 188 final List<JumpCollector> continueCollectors = <JumpCollector>[]; | |
| 189 | |
| 190 final List<ConstDeclaration> localConstants = <ConstDeclaration>[]; | |
| 191 | |
| 192 final Iterable<Entity> closureLocals; | |
| 193 | |
| 194 final FunctionElement currentFunction; | |
| 195 | |
| 196 final ir.Continuation returnContinuation = new ir.Continuation.retrn(); | |
| 197 | |
| 198 IrBuilderSharedState(this.constantSystem, | |
| 199 this.currentFunction, | |
| 200 this.closureLocals); | |
| 201 } | |
| 202 | |
| 203 /// A factory for building the cps IR. | |
| 204 class IrBuilder { | |
| 205 // TODO(johnniwinther): Make these field final and remove the default values | |
| 206 // when [IrBuilder] is a property of [IrBuilderVisitor] instead of a mixin. | |
| 207 | |
| 208 final List<ir.Parameter> _parameters = <ir.Parameter>[]; | |
| 209 | |
| 210 final IrBuilderSharedState state; | |
| 211 | |
| 212 /// A map from variable indexes to their values. | |
| 213 Environment environment; | |
| 214 | |
| 215 // The IR builder maintains a context, which is an expression with a hole in | |
| 216 // it. The hole represents the focus where new expressions can be added. | |
| 217 // The context is implemented by 'root' which is the root of the expression | |
| 218 // and 'current' which is the expression that immediately contains the hole. | |
| 219 // Not all expressions have a hole (e.g., invocations, which always occur in | |
| 220 // tail position, do not have a hole). Expressions with a hole have a plug | |
| 221 // method. | |
| 222 // | |
| 223 // Conceptually, visiting a statement takes a context as input and returns | |
| 224 // either a new context or else an expression without a hole if all | |
| 225 // control-flow paths through the statement have exited. An expression | |
| 226 // without a hole is represented by a (root, current) pair where root is the | |
| 227 // expression and current is null. | |
| 228 // | |
| 229 // Conceptually again, visiting an expression takes a context as input and | |
| 230 // returns either a pair of a new context and a definition denoting | |
| 231 // the expression's value, or else an expression without a hole if all | |
| 232 // control-flow paths through the expression have exited. | |
| 233 // | |
| 234 // We do not pass contexts as arguments or return them. Rather we use the | |
| 235 // current context (root, current) as the visitor state and mutate current. | |
| 236 // Visiting a statement returns null; visiting an expression returns the | |
| 237 // primitive denoting its value. | |
| 238 | |
| 239 ir.Expression _root = null; | |
| 240 ir.Expression _current = null; | |
| 241 | |
| 242 IrBuilder(ConstantSystem constantSystem, | |
| 243 FunctionElement currentFunction, | |
| 244 Iterable<Entity> closureLocals) | |
| 245 : this.state = new IrBuilderSharedState( | |
| 246 constantSystem, currentFunction, closureLocals), | |
| 247 this.environment = new Environment.empty(); | |
| 248 | |
| 249 /// Construct a delimited visitor for visiting a subtree. | |
| 250 /// | |
| 251 /// The delimited visitor has its own compile-time environment mapping | |
| 252 /// local variables to their values, which is initially a copy of the parent | |
| 253 /// environment. It has its own context for building an IR expression, so | |
| 254 /// the built expression is not plugged into the parent's context. | |
| 255 IrBuilder.delimited(IrBuilder parent) | |
| 256 : this.state = parent.state, | |
| 257 this.environment = new Environment.from(parent.environment); | |
| 258 | |
| 259 /// Construct a visitor for a recursive continuation. | |
| 260 /// | |
| 261 /// The recursive continuation builder has fresh parameters (i.e. SSA phis) | |
| 262 /// for all the local variables in the parent, because the invocation sites | |
| 263 /// of the continuation are not all known when the builder is created. The | |
| 264 /// recursive invocations will be passed values for all the local variables, | |
| 265 /// which may be eliminated later if they are redundant---if they take on | |
| 266 /// the same value at all invocation sites. | |
| 267 IrBuilder.recursive(IrBuilder parent) | |
| 268 : this.state = parent.state, | |
| 269 this.environment = new Environment.empty() { | |
| 270 parent.environment.index2variable.forEach(createParameter); | |
| 271 } | |
| 272 | |
| 273 | |
| 274 bool get isOpen => _root == null || _current != null; | |
| 275 | |
| 276 /// True if [element] is a local variable, local function, or parameter that | |
| 277 /// is accessed from an inner function. Recursive self-references in a local | |
| 278 /// function count as closure accesses. | |
| 279 /// | |
| 280 /// If `true`, [element] is a [LocalElement]. | |
| 281 bool isClosureVariable(Element element) { | |
| 282 return state.closureLocals.contains(element); | |
| 283 } | |
| 284 | |
| 285 /// Create a parameter for [parameterElement] and add it to the current | |
| 286 /// environment. | |
| 287 /// | |
| 288 /// [isClosureVariable] marks whether [parameterElement] is accessed from an | |
| 289 /// inner function. | |
| 290 void createParameter(LocalElement parameterElement) { | |
| 291 ir.Parameter parameter = new ir.Parameter(parameterElement); | |
| 292 _parameters.add(parameter); | |
| 293 if (isClosureVariable(parameterElement)) { | |
| 294 add(new ir.SetClosureVariable(parameterElement, parameter)); | |
| 295 } else { | |
| 296 environment.extend(parameterElement, parameter); | |
| 297 } | |
| 298 } | |
| 299 | |
| 300 /// Add the constant [variableElement] to the environment with [value] as its | |
| 301 /// constant value. | |
| 302 void declareLocalConstant(LocalVariableElement variableElement, | |
| 303 ConstantExpression value) { | |
| 304 state.localConstants.add(new ConstDeclaration(variableElement, value)); | |
| 305 } | |
| 306 | |
| 307 /// Add [variableElement] to the environment with [initialValue] as its | |
| 308 /// initial value. | |
| 309 /// | |
| 310 /// [isClosureVariable] marks whether [variableElement] is accessed from an | |
| 311 /// inner function. | |
| 312 void declareLocalVariable(LocalVariableElement variableElement, | |
| 313 {ir.Primitive initialValue}) { | |
| 314 assert(isOpen); | |
| 315 if (initialValue == null) { | |
| 316 // TODO(kmillikin): Consider pooling constants. | |
| 317 // The initial value is null. | |
| 318 initialValue = buildNullLiteral(); | |
| 319 } | |
| 320 if (isClosureVariable(variableElement)) { | |
| 321 add(new ir.SetClosureVariable(variableElement, | |
| 322 initialValue, | |
| 323 isDeclaration: true)); | |
| 324 } else { | |
| 325 // In case a primitive was introduced for the initializer expression, | |
| 326 // use this variable element to help derive a good name for it. | |
| 327 initialValue.useElementAsHint(variableElement); | |
| 328 environment.extend(variableElement, initialValue); | |
| 329 } | |
| 330 } | |
| 331 | |
| 332 // Plug an expression into the 'hole' in the context being accumulated. The | |
| 333 // empty context (just a hole) is represented by root (and current) being | |
| 334 // null. Since the hole in the current context is filled by this function, | |
| 335 // the new hole must be in the newly added expression---which becomes the | |
| 336 // new value of current. | |
| 337 void add(ir.Expression expr) { | |
| 338 assert(isOpen); | |
| 339 if (_root == null) { | |
| 340 _root = _current = expr; | |
| 341 } else { | |
| 342 _current = _current.plug(expr); | |
| 343 } | |
| 344 } | |
| 345 | |
| 346 ir.Primitive _continueWithExpression(ir.Expression build(ir.Continuation k)) { | |
| 347 ir.Parameter v = new ir.Parameter(null); | |
| 348 ir.Continuation k = new ir.Continuation([v]); | |
| 349 ir.Expression expression = build(k); | |
| 350 add(new ir.LetCont(k, expression)); | |
| 351 return v; | |
| 352 } | |
| 353 | |
| 354 ir.Primitive _buildInvokeStatic(Element element, | |
| 355 Selector selector, | |
| 356 List<ir.Definition> arguments) { | |
| 357 assert(isOpen); | |
| 358 return _continueWithExpression( | |
| 359 (k) => new ir.InvokeStatic(element, selector, k, arguments)); | |
| 360 } | |
| 361 | |
| 362 ir.Primitive _buildInvokeSuper(Selector selector, | |
| 363 List<ir.Definition> arguments) { | |
| 364 assert(isOpen); | |
| 365 return _continueWithExpression( | |
| 366 (k) => new ir.InvokeSuperMethod(selector, k, arguments)); | |
| 367 } | |
| 368 | |
| 369 ir.Primitive _buildInvokeDynamic(ir.Primitive receiver, | |
| 370 Selector selector, | |
| 371 List<ir.Definition> arguments) { | |
| 372 assert(isOpen); | |
| 373 return _continueWithExpression( | |
| 374 (k) => new ir.InvokeMethod(receiver, selector, k, arguments)); | |
| 375 } | |
| 376 | |
| 377 | |
| 378 /// Create a constant literal from [constant]. | |
| 379 ir.Constant buildConstantLiteral(ConstantExpression constant) { | |
| 380 assert(isOpen); | |
| 381 ir.Constant prim = new ir.Constant(constant); | |
| 382 add(new ir.LetPrim(prim)); | |
| 383 return prim; | |
| 384 } | |
| 385 | |
| 386 // Helper for building primitive literals. | |
| 387 ir.Constant _buildPrimitiveConstant(PrimitiveConstantValue constant) { | |
| 388 return buildConstantLiteral(new PrimitiveConstantExpression(constant)); | |
| 389 } | |
| 390 | |
| 391 /// Create an integer literal. | |
| 392 ir.Constant buildIntegerLiteral(int value) { | |
| 393 return _buildPrimitiveConstant(state.constantSystem.createInt(value)); | |
| 394 } | |
| 395 | |
| 396 /// Create an double literal. | |
| 397 ir.Constant buildDoubleLiteral(double value) { | |
| 398 return _buildPrimitiveConstant(state.constantSystem.createDouble(value)); | |
| 399 } | |
| 400 | |
| 401 /// Create an bool literal. | |
| 402 ir.Constant buildBooleanLiteral(bool value) { | |
| 403 return _buildPrimitiveConstant(state.constantSystem.createBool(value)); | |
| 404 } | |
| 405 | |
| 406 /// Create an null literal. | |
| 407 ir.Constant buildNullLiteral() { | |
| 408 return _buildPrimitiveConstant(state.constantSystem.createNull()); | |
| 409 } | |
| 410 | |
| 411 /// Create a string literal. | |
| 412 ir.Constant buildStringLiteral(String value) { | |
| 413 return _buildPrimitiveConstant( | |
| 414 state.constantSystem.createString(new ast.DartString.literal(value))); | |
| 415 } | |
| 416 | |
| 417 /// Creates a non-constant list literal of the provided [type] and with the | |
| 418 /// provided [values]. | |
| 419 ir.Primitive buildListLiteral(InterfaceType type, | |
| 420 Iterable<ir.Primitive> values) { | |
| 421 assert(isOpen); | |
| 422 ir.Primitive result = new ir.LiteralList(type, values); | |
| 423 add(new ir.LetPrim(result)); | |
| 424 return result; | |
| 425 } | |
| 426 | |
| 427 /// Creates a non-constant map literal of the provided [type] and with the | |
| 428 /// entries build from the [keys] and [values] using [build]. | |
| 429 ir.Primitive buildMapLiteral(InterfaceType type, | |
| 430 Iterable keys, | |
| 431 Iterable values, | |
| 432 BuildFunction build) { | |
| 433 assert(isOpen); | |
| 434 List<ir.LiteralMapEntry> entries = <ir.LiteralMapEntry>[]; | |
| 435 Iterator key = keys.iterator; | |
| 436 Iterator value = values.iterator; | |
| 437 while (key.moveNext() && value.moveNext()) { | |
| 438 entries.add(new ir.LiteralMapEntry( | |
| 439 build(key.current), build(value.current))); | |
| 440 } | |
| 441 assert(!key.moveNext() && !value.moveNext()); | |
| 442 ir.Primitive result = new ir.LiteralMap(type, entries); | |
| 443 add(new ir.LetPrim(result)); | |
| 444 return result; | |
| 445 } | |
| 446 | |
| 447 /// Creates a conditional expression with the provided [condition] where the | |
| 448 /// then and else expression are created through the [buildThenExpression] and | |
| 449 /// [buildElseExpression] functions, respectively. | |
| 450 ir.Primitive buildConditional( | |
| 451 ir.Primitive condition, | |
| 452 ir.Primitive buildThenExpression(IrBuilder builder), | |
| 453 ir.Primitive buildElseExpression(IrBuilder builder)) { | |
| 454 | |
| 455 assert(isOpen); | |
| 456 | |
| 457 // The then and else expressions are delimited. | |
| 458 IrBuilder thenBuilder = new IrBuilder.delimited(this); | |
| 459 IrBuilder elseBuilder = new IrBuilder.delimited(this); | |
| 460 ir.Primitive thenValue = buildThenExpression(thenBuilder); | |
| 461 ir.Primitive elseValue = buildElseExpression(elseBuilder); | |
| 462 | |
| 463 // Treat the values of the subexpressions as named values in the | |
| 464 // environment, so they will be treated as arguments to the join-point | |
| 465 // continuation. | |
| 466 assert(environment.length == thenBuilder.environment.length); | |
| 467 assert(environment.length == elseBuilder.environment.length); | |
| 468 thenBuilder.environment.extend(null, thenValue); | |
| 469 elseBuilder.environment.extend(null, elseValue); | |
| 470 JumpCollector jumps = new JumpCollector(null); | |
| 471 jumps.addJump(thenBuilder); | |
| 472 jumps.addJump(elseBuilder); | |
| 473 ir.Continuation joinContinuation = | |
| 474 createJoin(environment.length + 1, jumps); | |
| 475 | |
| 476 // Build the term | |
| 477 // let cont join(x, ..., result) = [] in | |
| 478 // let cont then() = [[thenPart]]; join(v, ...) in | |
| 479 // let cont else() = [[elsePart]]; join(v, ...) in | |
| 480 // if condition (then, else) | |
| 481 ir.Continuation thenContinuation = new ir.Continuation([]); | |
| 482 ir.Continuation elseContinuation = new ir.Continuation([]); | |
| 483 thenContinuation.body = thenBuilder._root; | |
| 484 elseContinuation.body = elseBuilder._root; | |
| 485 add(new ir.LetCont(joinContinuation, | |
| 486 new ir.LetCont(thenContinuation, | |
| 487 new ir.LetCont(elseContinuation, | |
| 488 new ir.Branch(new ir.IsTrue(condition), | |
| 489 thenContinuation, | |
| 490 elseContinuation))))); | |
| 491 return (thenValue == elseValue) | |
| 492 ? thenValue | |
| 493 : joinContinuation.parameters.last; | |
| 494 | |
| 495 } | |
| 496 | |
| 497 /** | |
| 498 * Add an explicit `return null` for functions that don't have a return | |
| 499 * statement on each branch. This includes functions with an empty body, | |
| 500 * such as `foo(){ }`. | |
| 501 */ | |
| 502 void _ensureReturn() { | |
| 503 if (!isOpen) return; | |
| 504 ir.Constant constant = buildNullLiteral(); | |
| 505 add(new ir.InvokeContinuation(state.returnContinuation, [constant])); | |
| 506 _current = null; | |
| 507 } | |
| 508 | |
| 509 /// Create a [ir.FunctionDefinition] for [element] using [_root] as the body. | |
| 510 /// | |
| 511 /// Parameters must be created before the construction of the body using | |
| 512 /// [createParameter]. | |
| 513 ir.FunctionDefinition buildFunctionDefinition( | |
| 514 FunctionElement element, | |
| 515 List<ConstantExpression> defaults) { | |
| 516 if (!element.isAbstract) { | |
| 517 _ensureReturn(); | |
| 518 return new ir.FunctionDefinition( | |
| 519 element, state.returnContinuation, _parameters, _root, | |
| 520 state.localConstants, defaults); | |
| 521 } else { | |
| 522 assert(invariant(element, _root == null, | |
| 523 message: "Non-empty body for abstract method $element: $_root")); | |
| 524 assert(invariant(element, state.localConstants.isEmpty, | |
| 525 message: "Local constants for abstract method $element: " | |
| 526 "${state.localConstants}")); | |
| 527 return new ir.FunctionDefinition.abstract( | |
| 528 element, _parameters, defaults); | |
| 529 } | |
| 530 } | |
| 531 | |
| 532 | |
| 533 /// Create a super invocation where the method name and the argument structure | |
| 534 /// are defined by [selector] and the argument values are defined by | |
| 535 /// [arguments]. | |
| 536 ir.Primitive buildSuperInvocation(Selector selector, | |
| 537 List<ir.Definition> arguments) { | |
| 538 return _buildInvokeSuper(selector, arguments); | |
| 539 } | |
| 540 | |
| 541 /// Create a getter invocation on the super class where the getter name is | |
| 542 /// defined by [selector]. | |
| 543 ir.Primitive buildSuperGet(Selector selector) { | |
| 544 assert(selector.isGetter); | |
| 545 return _buildInvokeSuper(selector, const <ir.Definition>[]); | |
| 546 } | |
| 547 | |
| 548 /// Create a setter invocation on the super class where the setter name and | |
| 549 /// argument are defined by [selector] and [value], respectively. | |
| 550 ir.Primitive buildSuperSet(Selector selector, ir.Primitive value) { | |
| 551 assert(selector.isSetter); | |
| 552 _buildInvokeSuper(selector, <ir.Definition>[value]); | |
| 553 return value; | |
| 554 } | |
| 555 | |
| 556 /// Create an index set invocation on the super class with the provided | |
| 557 /// [index] and [value]. | |
| 558 ir.Primitive buildSuperIndexSet(ir.Primitive index, | |
| 559 ir.Primitive value) { | |
| 560 _buildInvokeSuper(new Selector.indexSet(), <ir.Definition>[index, value]); | |
| 561 return value; | |
| 562 } | |
| 563 | |
| 564 /// Create a dynamic invocation on [receiver] where the method name and | |
| 565 /// argument structure are defined by [selector] and the argument values are | |
| 566 /// defined by [arguments]. | |
| 567 ir.Primitive buildDynamicInvocation(ir.Definition receiver, | |
| 568 Selector selector, | |
| 569 List<ir.Definition> arguments) { | |
| 570 return _buildInvokeDynamic(receiver, selector, arguments); | |
| 571 } | |
| 572 | |
| 573 /// Create a dynamic getter invocation on [receiver] where the getter name is | |
| 574 /// defined by [selector]. | |
| 575 ir.Primitive buildDynamicGet(ir.Primitive receiver, Selector selector) { | |
| 576 assert(selector.isGetter); | |
| 577 return _buildInvokeDynamic(receiver, selector, const <ir.Definition>[]); | |
| 578 } | |
| 579 | |
| 580 /// Create a dynamic setter invocation on [receiver] where the setter name and | |
| 581 /// argument are defined by [selector] and [value], respectively. | |
| 582 ir.Primitive buildDynamicSet(ir.Primitive receiver, | |
| 583 Selector selector, | |
| 584 ir.Primitive value) { | |
| 585 assert(selector.isSetter); | |
| 586 _buildInvokeDynamic(receiver, selector, <ir.Definition>[value]); | |
| 587 return value; | |
| 588 } | |
| 589 | |
| 590 /// Create a dynamic index set invocation on [receiver] with the provided | |
| 591 /// [index] and [value]. | |
| 592 ir.Primitive buildDynamicIndexSet(ir.Primitive receiver, | |
| 593 ir.Primitive index, | |
| 594 ir.Primitive value) { | |
| 595 _buildInvokeDynamic( | |
| 596 receiver, new Selector.indexSet(), <ir.Definition>[index, value]); | |
| 597 return value; | |
| 598 } | |
| 599 | |
| 600 /// Create a static invocation of [element] where argument structure is | |
| 601 /// defined by [selector] and the argument values are defined by [arguments]. | |
| 602 ir.Primitive buildStaticInvocation(Element element, | |
| 603 Selector selector, | |
| 604 List<ir.Definition> arguments) { | |
| 605 return _buildInvokeStatic(element, selector, arguments); | |
| 606 } | |
| 607 | |
| 608 /// Create a static getter invocation of [element] where the getter name is | |
| 609 /// defined by [selector]. | |
| 610 ir.Primitive buildStaticGet(Element element, Selector selector) { | |
| 611 assert(selector.isGetter); | |
| 612 return _buildInvokeStatic(element, selector, const <ir.Definition>[]); | |
| 613 } | |
| 614 | |
| 615 /// Create a static setter invocation of [element] where the setter name and | |
| 616 /// argument are defined by [selector] and [value], respectively. | |
| 617 ir.Primitive buildStaticSet(Element element, | |
| 618 Selector selector, | |
| 619 ir.Primitive value) { | |
| 620 assert(selector.isSetter); | |
| 621 _buildInvokeStatic(element, selector, <ir.Definition>[value]); | |
| 622 return value; | |
| 623 } | |
| 624 | |
| 625 /// Create a constructor invocation of [element] on [type] where the | |
| 626 /// constructor name and argument structure are defined by [selector] and the | |
| 627 /// argument values are defined by [arguments]. | |
| 628 ir.Primitive buildConstructorInvocation(FunctionElement element, | |
| 629 Selector selector, | |
| 630 DartType type, | |
| 631 List<ir.Definition> arguments) { | |
| 632 assert(isOpen); | |
| 633 return _continueWithExpression( | |
| 634 (k) => new ir.InvokeConstructor(type, element, selector, k, arguments)); | |
| 635 } | |
| 636 | |
| 637 /// Create a string concatenation of the [arguments]. | |
| 638 ir.Primitive buildStringConcatenation(List<ir.Definition> arguments) { | |
| 639 assert(isOpen); | |
| 640 return _continueWithExpression( | |
| 641 (k) => new ir.ConcatenateStrings(k, arguments)); | |
| 642 } | |
| 643 | |
| 644 /// Create a read access of [local]. | |
| 645 ir.Primitive buildLocalGet(LocalElement local) { | |
| 646 assert(isOpen); | |
| 647 if (isClosureVariable(local)) { | |
| 648 ir.Primitive result = new ir.GetClosureVariable(local); | |
| 649 add(new ir.LetPrim(result)); | |
| 650 return result; | |
| 651 } else { | |
| 652 return environment.lookup(local); | |
| 653 } | |
| 654 } | |
| 655 | |
| 656 /// Create a write access to [local] with the provided [value]. | |
| 657 ir.Primitive buildLocalSet(LocalElement local, ir.Primitive value) { | |
| 658 assert(isOpen); | |
| 659 if (isClosureVariable(local)) { | |
| 660 add(new ir.SetClosureVariable(local, value)); | |
| 661 } else { | |
| 662 value.useElementAsHint(local); | |
| 663 environment.update(local, value); | |
| 664 } | |
| 665 return value; | |
| 666 } | |
| 667 | |
| 668 /// Creates an if-then-else statement with the provided [condition] where the | |
| 669 /// then and else branches are created through the [buildThenPart] and | |
| 670 /// [buildElsePart] functions, respectively. | |
| 671 /// | |
| 672 /// An if-then statement is created if [buildElsePart] is a no-op. | |
| 673 // TODO(johnniwinther): Unify implementation with [buildConditional] and | |
| 674 // [_buildLogicalOperator]. | |
| 675 void buildIf(ir.Primitive condition, | |
| 676 void buildThenPart(IrBuilder builder), | |
| 677 void buildElsePart(IrBuilder builder)) { | |
| 678 assert(isOpen); | |
| 679 | |
| 680 // The then and else parts are delimited. | |
| 681 IrBuilder thenBuilder = new IrBuilder.delimited(this); | |
| 682 IrBuilder elseBuilder = new IrBuilder.delimited(this); | |
| 683 buildThenPart(thenBuilder); | |
| 684 buildElsePart(elseBuilder); | |
| 685 | |
| 686 // Build the term | |
| 687 // (Result =) let cont then() = [[thenPart]] in | |
| 688 // let cont else() = [[elsePart]] in | |
| 689 // if condition (then, else) | |
| 690 ir.Continuation thenContinuation = new ir.Continuation([]); | |
| 691 ir.Continuation elseContinuation = new ir.Continuation([]); | |
| 692 ir.Expression letElse = | |
| 693 new ir.LetCont(elseContinuation, | |
| 694 new ir.Branch(new ir.IsTrue(condition), | |
| 695 thenContinuation, | |
| 696 elseContinuation)); | |
| 697 ir.Expression letThen = new ir.LetCont(thenContinuation, letElse); | |
| 698 ir.Expression result = letThen; | |
| 699 | |
| 700 ir.Continuation joinContinuation; // Null if there is no join. | |
| 701 if (thenBuilder.isOpen && elseBuilder.isOpen) { | |
| 702 // There is a join-point continuation. Build the term | |
| 703 // 'let cont join(x, ...) = [] in Result' and plug invocations of the | |
| 704 // join-point continuation into the then and else continuations. | |
| 705 JumpCollector jumps = new JumpCollector(null); | |
| 706 jumps.addJump(thenBuilder); | |
| 707 jumps.addJump(elseBuilder); | |
| 708 joinContinuation = createJoin(environment.length, jumps); | |
| 709 result = new ir.LetCont(joinContinuation, result); | |
| 710 } | |
| 711 | |
| 712 // The then or else term root could be null, but not both. If there is | |
| 713 // a join then an InvokeContinuation was just added to both of them. If | |
| 714 // there is no join, then at least one of them is closed and thus has a | |
| 715 // non-null root by the definition of the predicate isClosed. In the | |
| 716 // case that one of them is null, it must be the only one that is open | |
| 717 // and thus contains the new hole in the context. This case is handled | |
| 718 // after the branch is plugged into the current hole. | |
| 719 thenContinuation.body = thenBuilder._root; | |
| 720 elseContinuation.body = elseBuilder._root; | |
| 721 | |
| 722 add(result); | |
| 723 if (joinContinuation == null) { | |
| 724 // At least one subexpression is closed. | |
| 725 if (thenBuilder.isOpen) { | |
| 726 _current = | |
| 727 (thenBuilder._root == null) ? letThen : thenBuilder._current; | |
| 728 environment = thenBuilder.environment; | |
| 729 } else if (elseBuilder.isOpen) { | |
| 730 _current = | |
| 731 (elseBuilder._root == null) ? letElse : elseBuilder._current; | |
| 732 environment = elseBuilder.environment; | |
| 733 } else { | |
| 734 _current = null; | |
| 735 } | |
| 736 } | |
| 737 } | |
| 738 | |
| 739 /// Invoke a join-point continuation that contains arguments for all local | |
| 740 /// variables. | |
| 741 /// | |
| 742 /// Given the continuation and a list of uninitialized invocations, fill | |
| 743 /// in each invocation with the continuation and appropriate arguments. | |
| 744 void invokeFullJoin(ir.Continuation join, | |
| 745 JumpCollector jumps, | |
| 746 {recursive: false}) { | |
| 747 join.isRecursive = recursive; | |
| 748 for (int i = 0; i < jumps.length; ++i) { | |
| 749 Environment currentEnvironment = jumps.environments[i]; | |
| 750 ir.InvokeContinuation invoke = jumps.invocations[i]; | |
| 751 invoke.continuation = new ir.Reference(join); | |
| 752 invoke.arguments = new List<ir.Reference>.generate( | |
| 753 join.parameters.length, | |
| 754 (i) => new ir.Reference(currentEnvironment[i])); | |
| 755 invoke.isRecursive = recursive; | |
| 756 } | |
| 757 } | |
| 758 | |
| 759 /// Creates a for loop in which the initializer, condition, body, update are | |
| 760 /// created by [buildInitializer], [buildCondition], [buildBody] and | |
| 761 /// [buildUpdate], respectively. | |
| 762 /// | |
| 763 /// The jump [target] is used to identify which `break` and `continue` | |
| 764 /// statements that have this `for` statement as their target. | |
| 765 void buildFor({SubbuildFunction buildInitializer, | |
| 766 SubbuildFunction buildCondition, | |
| 767 SubbuildFunction buildBody, | |
| 768 SubbuildFunction buildUpdate, | |
| 769 JumpTarget target}) { | |
| 770 assert(isOpen); | |
| 771 | |
| 772 // For loops use four named continuations: the entry to the condition, | |
| 773 // the entry to the body, the loop exit, and the loop successor (break). | |
| 774 // The CPS translation of | |
| 775 // [[for (initializer; condition; update) body; successor]] is: | |
| 776 // | |
| 777 // [[initializer]]; | |
| 778 // let cont loop(x, ...) = | |
| 779 // let prim cond = [[condition]] in | |
| 780 // let cont break() = [[successor]] in | |
| 781 // let cont exit() = break(v, ...) in | |
| 782 // let cont body() = | |
| 783 // let cont continue(x, ...) = [[update]]; loop(v, ...) in | |
| 784 // [[body]]; continue(v, ...) in | |
| 785 // branch cond (body, exit) in | |
| 786 // loop(v, ...) | |
| 787 // | |
| 788 // If there are no breaks in the body, the break continuation is inlined | |
| 789 // in the exit continuation (i.e., the translation of the successor | |
| 790 // statement occurs in the exit continuation). If there is only one | |
| 791 // invocation of the continue continuation (i.e., no continues in the | |
| 792 // body), the continue continuation is inlined in the body. | |
| 793 | |
| 794 buildInitializer(this); | |
| 795 | |
| 796 IrBuilder condBuilder = new IrBuilder.recursive(this); | |
| 797 ir.Primitive condition = buildCondition(condBuilder); | |
| 798 if (condition == null) { | |
| 799 // If the condition is empty then the body is entered unconditionally. | |
| 800 condition = condBuilder.buildBooleanLiteral(true); | |
| 801 } | |
| 802 | |
| 803 JumpCollector breakCollector = new JumpCollector(target); | |
| 804 JumpCollector continueCollector = new JumpCollector(target); | |
| 805 state.breakCollectors.add(breakCollector); | |
| 806 state.continueCollectors.add(continueCollector); | |
| 807 | |
| 808 IrBuilder bodyBuilder = new IrBuilder.delimited(condBuilder); | |
| 809 buildBody(bodyBuilder); | |
| 810 assert(state.breakCollectors.last == breakCollector); | |
| 811 assert(state.continueCollectors.last == continueCollector); | |
| 812 state.breakCollectors.removeLast(); | |
| 813 state.continueCollectors.removeLast(); | |
| 814 | |
| 815 // The binding of the continue continuation should occur as late as | |
| 816 // possible, that is, at the nearest common ancestor of all the continue | |
| 817 // sites in the body. However, that is difficult to compute here, so it | |
| 818 // is instead placed just outside the body of the body continuation. | |
| 819 bool hasContinues = !continueCollector.isEmpty; | |
| 820 IrBuilder updateBuilder = hasContinues | |
| 821 ? new IrBuilder.recursive(condBuilder) | |
| 822 : bodyBuilder; | |
| 823 buildUpdate(updateBuilder); | |
| 824 | |
| 825 // Create body entry and loop exit continuations and a branch to them. | |
| 826 ir.Continuation bodyContinuation = new ir.Continuation([]); | |
| 827 ir.Continuation exitContinuation = new ir.Continuation([]); | |
| 828 ir.LetCont branch = | |
| 829 new ir.LetCont(exitContinuation, | |
| 830 new ir.LetCont(bodyContinuation, | |
| 831 new ir.Branch(new ir.IsTrue(condition), | |
| 832 bodyContinuation, | |
| 833 exitContinuation))); | |
| 834 // If there are breaks in the body, then there must be a join-point | |
| 835 // continuation for the normal exit and the breaks. | |
| 836 bool hasBreaks = !breakCollector.isEmpty; | |
| 837 ir.LetCont letJoin; | |
| 838 if (hasBreaks) { | |
| 839 letJoin = new ir.LetCont(null, branch); | |
| 840 condBuilder.add(letJoin); | |
| 841 condBuilder._current = branch; | |
| 842 } else { | |
| 843 condBuilder.add(branch); | |
| 844 } | |
| 845 ir.Continuation continueContinuation; | |
| 846 if (hasContinues) { | |
| 847 // If there are continues in the body, we need a named continue | |
| 848 // continuation as a join point. | |
| 849 continueContinuation = new ir.Continuation(updateBuilder._parameters); | |
| 850 if (bodyBuilder.isOpen) continueCollector.addJump(bodyBuilder); | |
| 851 invokeFullJoin(continueContinuation, continueCollector); | |
| 852 } | |
| 853 ir.Continuation loopContinuation = | |
| 854 new ir.Continuation(condBuilder._parameters); | |
| 855 if (updateBuilder.isOpen) { | |
| 856 JumpCollector backEdges = new JumpCollector(null); | |
| 857 backEdges.addJump(updateBuilder); | |
| 858 invokeFullJoin(loopContinuation, backEdges, recursive: true); | |
| 859 } | |
| 860 | |
| 861 // Fill in the body and possible continue continuation bodies. Do this | |
| 862 // only after it is guaranteed that they are not empty. | |
| 863 if (hasContinues) { | |
| 864 continueContinuation.body = updateBuilder._root; | |
| 865 bodyContinuation.body = | |
| 866 new ir.LetCont(continueContinuation, bodyBuilder._root); | |
| 867 } else { | |
| 868 bodyContinuation.body = bodyBuilder._root; | |
| 869 } | |
| 870 | |
| 871 loopContinuation.body = condBuilder._root; | |
| 872 add(new ir.LetCont(loopContinuation, | |
| 873 new ir.InvokeContinuation(loopContinuation, | |
| 874 environment.index2value))); | |
| 875 if (hasBreaks) { | |
| 876 _current = branch; | |
| 877 environment = condBuilder.environment; | |
| 878 breakCollector.addJump(this); | |
| 879 letJoin.continuation = createJoin(environment.length, breakCollector); | |
| 880 _current = letJoin; | |
| 881 } else { | |
| 882 _current = condBuilder._current; | |
| 883 environment = condBuilder.environment; | |
| 884 } | |
| 885 } | |
| 886 | |
| 887 /// Creates a for-in loop, `for (v in e) b`. | |
| 888 /// | |
| 889 /// [buildExpression] creates the expression, `e`. The variable, `v`, can | |
| 890 /// take one of three forms: | |
| 891 /// 1) `v` can be declared within the for-in statement, like in | |
| 892 /// `for (var v in e)`, in which case, [buildVariableDeclaration] | |
| 893 /// creates its declaration and [variableElement] is the element for | |
| 894 /// the declared variable, | |
| 895 /// 2) `v` is predeclared statically known variable, that is top-level, | |
| 896 /// static, or local variable, in which case [variableElement] is the | |
| 897 /// variable element, and [variableSelector] defines its write access, | |
| 898 /// 3) `v` is an instance variable in which case [variableSelector] | |
| 899 /// defines its write access. | |
| 900 /// [buildBody] creates the body, `b`, of the loop. The jump [target] is used | |
| 901 /// to identify which `break` and `continue` statements that have this for-in | |
| 902 /// statement as their target. | |
| 903 void buildForIn({SubbuildFunction buildExpression, | |
| 904 SubbuildFunction buildVariableDeclaration, | |
| 905 Element variableElement, | |
| 906 Selector variableSelector, | |
| 907 SubbuildFunction buildBody, | |
| 908 JumpTarget target}) { | |
| 909 // The for-in loop | |
| 910 // | |
| 911 // for (a in e) s; | |
| 912 // | |
| 913 // Is compiled analogously to: | |
| 914 // | |
| 915 // a = e.iterator; | |
| 916 // while (a.moveNext()) { | |
| 917 // var n0 = a.current; | |
| 918 // s; | |
| 919 // } | |
| 920 | |
| 921 // The condition and body are delimited. | |
| 922 IrBuilder condBuilder = new IrBuilder.recursive(this); | |
| 923 | |
| 924 ir.Primitive expressionReceiver = buildExpression(this); | |
| 925 List<ir.Primitive> emptyArguments = new List<ir.Primitive>(); | |
| 926 | |
| 927 ir.Parameter iterator = new ir.Parameter(null); | |
| 928 ir.Continuation iteratorInvoked = new ir.Continuation([iterator]); | |
| 929 add(new ir.LetCont(iteratorInvoked, | |
| 930 new ir.InvokeMethod(expressionReceiver, | |
| 931 new Selector.getter("iterator", null), iteratorInvoked, | |
| 932 emptyArguments))); | |
| 933 | |
| 934 ir.Parameter condition = new ir.Parameter(null); | |
| 935 ir.Continuation moveNextInvoked = new ir.Continuation([condition]); | |
| 936 condBuilder.add(new ir.LetCont(moveNextInvoked, | |
| 937 new ir.InvokeMethod(iterator, | |
| 938 new Selector.call("moveNext", null, 0), | |
| 939 moveNextInvoked, emptyArguments))); | |
| 940 | |
| 941 JumpCollector breakCollector = new JumpCollector(target); | |
| 942 JumpCollector continueCollector = new JumpCollector(target); | |
| 943 state.breakCollectors.add(breakCollector); | |
| 944 state.continueCollectors.add(continueCollector); | |
| 945 | |
| 946 IrBuilder bodyBuilder = new IrBuilder.delimited(condBuilder); | |
| 947 if (buildVariableDeclaration != null) { | |
| 948 buildVariableDeclaration(bodyBuilder); | |
| 949 } | |
| 950 | |
| 951 ir.Parameter currentValue = new ir.Parameter(null); | |
| 952 ir.Continuation currentInvoked = new ir.Continuation([currentValue]); | |
| 953 bodyBuilder.add(new ir.LetCont(currentInvoked, | |
| 954 new ir.InvokeMethod(iterator, new Selector.getter("current", null), | |
| 955 currentInvoked, emptyArguments))); | |
| 956 if (Elements.isLocal(variableElement)) { | |
| 957 bodyBuilder.buildLocalSet(variableElement, currentValue); | |
| 958 } else if (Elements.isStaticOrTopLevel(variableElement)) { | |
| 959 bodyBuilder.buildStaticSet( | |
| 960 variableElement, variableSelector, currentValue); | |
| 961 } else { | |
| 962 ir.Primitive receiver = bodyBuilder.buildThis(); | |
| 963 bodyBuilder.buildDynamicSet(receiver, variableSelector, currentValue); | |
| 964 } | |
| 965 | |
| 966 buildBody(bodyBuilder); | |
| 967 assert(state.breakCollectors.last == breakCollector); | |
| 968 assert(state.continueCollectors.last == continueCollector); | |
| 969 state.breakCollectors.removeLast(); | |
| 970 state.continueCollectors.removeLast(); | |
| 971 | |
| 972 // Create body entry and loop exit continuations and a branch to them. | |
| 973 ir.Continuation bodyContinuation = new ir.Continuation([]); | |
| 974 ir.Continuation exitContinuation = new ir.Continuation([]); | |
| 975 ir.LetCont branch = | |
| 976 new ir.LetCont(exitContinuation, | |
| 977 new ir.LetCont(bodyContinuation, | |
| 978 new ir.Branch(new ir.IsTrue(condition), | |
| 979 bodyContinuation, | |
| 980 exitContinuation))); | |
| 981 // If there are breaks in the body, then there must be a join-point | |
| 982 // continuation for the normal exit and the breaks. | |
| 983 bool hasBreaks = !breakCollector.isEmpty; | |
| 984 ir.LetCont letJoin; | |
| 985 if (hasBreaks) { | |
| 986 letJoin = new ir.LetCont(null, branch); | |
| 987 condBuilder.add(letJoin); | |
| 988 condBuilder._current = branch; | |
| 989 } else { | |
| 990 condBuilder.add(branch); | |
| 991 } | |
| 992 ir.Continuation loopContinuation = | |
| 993 new ir.Continuation(condBuilder._parameters); | |
| 994 if (bodyBuilder.isOpen) continueCollector.addJump(bodyBuilder); | |
| 995 invokeFullJoin( | |
| 996 loopContinuation, continueCollector, recursive: true); | |
| 997 bodyContinuation.body = bodyBuilder._root; | |
| 998 | |
| 999 loopContinuation.body = condBuilder._root; | |
| 1000 add(new ir.LetCont(loopContinuation, | |
| 1001 new ir.InvokeContinuation(loopContinuation, | |
| 1002 environment.index2value))); | |
| 1003 if (hasBreaks) { | |
| 1004 _current = branch; | |
| 1005 environment = condBuilder.environment; | |
| 1006 breakCollector.addJump(this); | |
| 1007 letJoin.continuation = createJoin(environment.length, breakCollector); | |
| 1008 _current = letJoin; | |
| 1009 } else { | |
| 1010 _current = condBuilder._current; | |
| 1011 environment = condBuilder.environment; | |
| 1012 } | |
| 1013 } | |
| 1014 | |
| 1015 /// Creates a while loop in which the condition and body are created by | |
| 1016 /// [buildCondition] and [buildBody], respectively. | |
| 1017 /// | |
| 1018 /// The jump [target] is used to identify which `break` and `continue` | |
| 1019 /// statements that have this `while` statement as their target. | |
| 1020 void buildWhile({SubbuildFunction buildCondition, | |
| 1021 SubbuildFunction buildBody, | |
| 1022 JumpTarget target}) { | |
| 1023 assert(isOpen); | |
| 1024 // While loops use four named continuations: the entry to the body, the | |
| 1025 // loop exit, the loop back edge (continue), and the loop exit (break). | |
| 1026 // The CPS translation of [[while (condition) body; successor]] is: | |
| 1027 // | |
| 1028 // let cont continue(x, ...) = | |
| 1029 // let prim cond = [[condition]] in | |
| 1030 // let cont break() = [[successor]] in | |
| 1031 // let cont exit() = break(v, ...) in | |
| 1032 // let cont body() = [[body]]; continue(v, ...) in | |
| 1033 // branch cond (body, exit) in | |
| 1034 // continue(v, ...) | |
| 1035 // | |
| 1036 // If there are no breaks in the body, the break continuation is inlined | |
| 1037 // in the exit continuation (i.e., the translation of the successor | |
| 1038 // statement occurs in the exit continuation). | |
| 1039 | |
| 1040 // The condition and body are delimited. | |
| 1041 IrBuilder condBuilder = new IrBuilder.recursive(this); | |
| 1042 ir.Primitive condition = buildCondition(condBuilder); | |
| 1043 | |
| 1044 JumpCollector breakCollector = new JumpCollector(target); | |
| 1045 JumpCollector continueCollector = new JumpCollector(target); | |
| 1046 state.breakCollectors.add(breakCollector); | |
| 1047 state.continueCollectors.add(continueCollector); | |
| 1048 | |
| 1049 IrBuilder bodyBuilder = new IrBuilder.delimited(condBuilder); | |
| 1050 buildBody(bodyBuilder); | |
| 1051 assert(state.breakCollectors.last == breakCollector); | |
| 1052 assert(state.continueCollectors.last == continueCollector); | |
| 1053 state.breakCollectors.removeLast(); | |
| 1054 state.continueCollectors.removeLast(); | |
| 1055 | |
| 1056 // Create body entry and loop exit continuations and a branch to them. | |
| 1057 ir.Continuation bodyContinuation = new ir.Continuation([]); | |
| 1058 ir.Continuation exitContinuation = new ir.Continuation([]); | |
| 1059 ir.LetCont branch = | |
| 1060 new ir.LetCont(exitContinuation, | |
| 1061 new ir.LetCont(bodyContinuation, | |
| 1062 new ir.Branch(new ir.IsTrue(condition), | |
| 1063 bodyContinuation, | |
| 1064 exitContinuation))); | |
| 1065 // If there are breaks in the body, then there must be a join-point | |
| 1066 // continuation for the normal exit and the breaks. | |
| 1067 bool hasBreaks = !breakCollector.isEmpty; | |
| 1068 ir.LetCont letJoin; | |
| 1069 if (hasBreaks) { | |
| 1070 letJoin = new ir.LetCont(null, branch); | |
| 1071 condBuilder.add(letJoin); | |
| 1072 condBuilder._current = branch; | |
| 1073 } else { | |
| 1074 condBuilder.add(branch); | |
| 1075 } | |
| 1076 ir.Continuation loopContinuation = | |
| 1077 new ir.Continuation(condBuilder._parameters); | |
| 1078 if (bodyBuilder.isOpen) continueCollector.addJump(bodyBuilder); | |
| 1079 invokeFullJoin(loopContinuation, continueCollector, recursive: true); | |
| 1080 bodyContinuation.body = bodyBuilder._root; | |
| 1081 | |
| 1082 loopContinuation.body = condBuilder._root; | |
| 1083 add(new ir.LetCont(loopContinuation, | |
| 1084 new ir.InvokeContinuation(loopContinuation, | |
| 1085 environment.index2value))); | |
| 1086 if (hasBreaks) { | |
| 1087 _current = branch; | |
| 1088 environment = condBuilder.environment; | |
| 1089 breakCollector.addJump(this); | |
| 1090 letJoin.continuation = createJoin(environment.length, breakCollector); | |
| 1091 _current = letJoin; | |
| 1092 } else { | |
| 1093 _current = condBuilder._current; | |
| 1094 environment = condBuilder.environment; | |
| 1095 } | |
| 1096 } | |
| 1097 | |
| 1098 /// Create a return statement `return value;` or `return;` if [value] is | |
| 1099 /// null. | |
| 1100 void buildReturn([ir.Primitive value]) { | |
| 1101 // Build(Return(e), C) = C'[InvokeContinuation(return, x)] | |
| 1102 // where (C', x) = Build(e, C) | |
| 1103 // | |
| 1104 // Return without a subexpression is translated as if it were return null. | |
| 1105 assert(isOpen); | |
| 1106 if (value == null) { | |
| 1107 value = buildNullLiteral(); | |
| 1108 } | |
| 1109 add(new ir.InvokeContinuation(state.returnContinuation, [value])); | |
| 1110 _current = null; | |
| 1111 } | |
| 1112 | |
| 1113 /// Create a blocks of [statements] by applying [build] to all reachable | |
| 1114 /// statements. The first statement is assumed to be reachable. | |
| 1115 // TODO(johnniwinther): Type [statements] as `Iterable` when `NodeList` uses | |
| 1116 // `List` instead of `Link`. | |
| 1117 void buildBlock(var statements, BuildFunction build) { | |
| 1118 // Build(Block(stamements), C) = C' | |
| 1119 // where C' = statements.fold(Build, C) | |
| 1120 assert(isOpen); | |
| 1121 return buildSequence(statements, build); | |
| 1122 } | |
| 1123 | |
| 1124 /// Creates a sequence of [nodes] by applying [build] to all reachable nodes. | |
| 1125 /// | |
| 1126 /// The first node in the sequence does not need to be reachable. | |
| 1127 // TODO(johnniwinther): Type [nodes] as `Iterable` when `NodeList` uses | |
| 1128 // `List` instead of `Link`. | |
| 1129 void buildSequence(var nodes, BuildFunction build) { | |
| 1130 for (var node in nodes) { | |
| 1131 if (!isOpen) return; | |
| 1132 build(node); | |
| 1133 } | |
| 1134 } | |
| 1135 | |
| 1136 | |
| 1137 // Build(BreakStatement L, C) = C[InvokeContinuation(...)] | |
| 1138 // | |
| 1139 // The continuation and arguments are filled in later after translating | |
| 1140 // the body containing the break. | |
| 1141 bool buildBreak(JumpTarget target) { | |
| 1142 return buildJumpInternal(target, state.breakCollectors); | |
| 1143 } | |
| 1144 | |
| 1145 // Build(ContinueStatement L, C) = C[InvokeContinuation(...)] | |
| 1146 // | |
| 1147 // The continuation and arguments are filled in later after translating | |
| 1148 // the body containing the continue. | |
| 1149 bool buildContinue(JumpTarget target) { | |
| 1150 return buildJumpInternal(target, state.continueCollectors); | |
| 1151 } | |
| 1152 | |
| 1153 bool buildJumpInternal(JumpTarget target, | |
| 1154 Iterable<JumpCollector> collectors) { | |
| 1155 assert(isOpen); | |
| 1156 for (JumpCollector collector in collectors) { | |
| 1157 if (target == collector.target) { | |
| 1158 collector.addJump(this); | |
| 1159 return true; | |
| 1160 } | |
| 1161 } | |
| 1162 return false; | |
| 1163 } | |
| 1164 | |
| 1165 /// Create a negation of [condition]. | |
| 1166 ir.Primitive buildNegation(ir.Primitive condition) { | |
| 1167 // ! e is translated as e ? false : true | |
| 1168 | |
| 1169 // Add a continuation parameter for the result of the expression. | |
| 1170 ir.Parameter resultParameter = new ir.Parameter(null); | |
| 1171 | |
| 1172 ir.Continuation joinContinuation = new ir.Continuation([resultParameter]); | |
| 1173 ir.Continuation thenContinuation = new ir.Continuation([]); | |
| 1174 ir.Continuation elseContinuation = new ir.Continuation([]); | |
| 1175 | |
| 1176 ir.Constant makeBoolConstant(bool value) { | |
| 1177 return new ir.Constant(new PrimitiveConstantExpression( | |
| 1178 state.constantSystem.createBool(value))); | |
| 1179 } | |
| 1180 | |
| 1181 ir.Constant trueConstant = makeBoolConstant(true); | |
| 1182 ir.Constant falseConstant = makeBoolConstant(false); | |
| 1183 | |
| 1184 thenContinuation.body = new ir.LetPrim(falseConstant) | |
| 1185 ..plug(new ir.InvokeContinuation(joinContinuation, [falseConstant])); | |
| 1186 elseContinuation.body = new ir.LetPrim(trueConstant) | |
| 1187 ..plug(new ir.InvokeContinuation(joinContinuation, [trueConstant])); | |
| 1188 | |
| 1189 add(new ir.LetCont(joinContinuation, | |
| 1190 new ir.LetCont(thenContinuation, | |
| 1191 new ir.LetCont(elseContinuation, | |
| 1192 new ir.Branch(new ir.IsTrue(condition), | |
| 1193 thenContinuation, | |
| 1194 elseContinuation))))); | |
| 1195 return resultParameter; | |
| 1196 } | |
| 1197 | |
| 1198 /// Creates a type test or type cast of [receiver] against [type]. | |
| 1199 /// | |
| 1200 /// Set [isTypeTest] to `true` to create a type test and furthermore set | |
| 1201 /// [isNotCheck] to `true` to create a negated type test. | |
| 1202 ir.Primitive buildTypeOperator(ir.Primitive receiver, | |
| 1203 DartType type, | |
| 1204 {bool isTypeTest: false, | |
| 1205 bool isNotCheck: false}) { | |
| 1206 assert(isOpen); | |
| 1207 assert(isTypeTest != null); | |
| 1208 assert(!isNotCheck || isTypeTest); | |
| 1209 ir.Primitive check = _continueWithExpression( | |
| 1210 (k) => new ir.TypeOperator(receiver, type, k, isTypeTest: isTypeTest)); | |
| 1211 return isNotCheck ? buildNegation(check) : check; | |
| 1212 | |
| 1213 } | |
| 1214 | |
| 1215 /// Create a lazy and/or expression. [leftValue] is the value of the left | |
| 1216 /// operand and [buildRightValue] is called to process the value of the right | |
| 1217 /// operand in the context of its own [IrBuilder]. | |
| 1218 ir.Primitive buildLogicalOperator( | |
| 1219 ir.Primitive leftValue, | |
| 1220 ir.Primitive buildRightValue(IrBuilder builder), | |
| 1221 {bool isLazyOr: false}) { | |
| 1222 // e0 && e1 is translated as if e0 ? (e1 == true) : false. | |
| 1223 // e0 || e1 is translated as if e0 ? true : (e1 == true). | |
| 1224 // The translation must convert both e0 and e1 to booleans and handle | |
| 1225 // local variable assignments in e1. | |
| 1226 | |
| 1227 IrBuilder rightBuilder = new IrBuilder.delimited(this); | |
| 1228 ir.Primitive rightValue = buildRightValue(rightBuilder); | |
| 1229 // A dummy empty target for the branch on the left subexpression branch. | |
| 1230 // This enables using the same infrastructure for join-point continuations | |
| 1231 // as in visitIf and visitConditional. It will hold a definition of the | |
| 1232 // appropriate constant and an invocation of the join-point continuation. | |
| 1233 IrBuilder emptyBuilder = new IrBuilder.delimited(this); | |
| 1234 // Dummy empty targets for right true and right false. They hold | |
| 1235 // definitions of the appropriate constant and an invocation of the | |
| 1236 // join-point continuation. | |
| 1237 IrBuilder rightTrueBuilder = new IrBuilder.delimited(rightBuilder); | |
| 1238 IrBuilder rightFalseBuilder = new IrBuilder.delimited(rightBuilder); | |
| 1239 | |
| 1240 // If we don't evaluate the right subexpression, the value of the whole | |
| 1241 // expression is this constant. | |
| 1242 ir.Constant leftBool = emptyBuilder.buildBooleanLiteral(isLazyOr); | |
| 1243 // If we do evaluate the right subexpression, the value of the expression | |
| 1244 // is a true or false constant. | |
| 1245 ir.Constant rightTrue = rightTrueBuilder.buildBooleanLiteral(true); | |
| 1246 ir.Constant rightFalse = rightFalseBuilder.buildBooleanLiteral(false); | |
| 1247 | |
| 1248 // Treat the result values as named values in the environment, so they | |
| 1249 // will be treated as arguments to the join-point continuation. | |
| 1250 assert(environment.length == emptyBuilder.environment.length); | |
| 1251 assert(environment.length == rightTrueBuilder.environment.length); | |
| 1252 assert(environment.length == rightFalseBuilder.environment.length); | |
| 1253 emptyBuilder.environment.extend(null, leftBool); | |
| 1254 rightTrueBuilder.environment.extend(null, rightTrue); | |
| 1255 rightFalseBuilder.environment.extend(null, rightFalse); | |
| 1256 | |
| 1257 // Wire up two continuations for the left subexpression, two continuations | |
| 1258 // for the right subexpression, and a three-way join continuation. | |
| 1259 JumpCollector jumps = new JumpCollector(null); | |
| 1260 jumps.addJump(emptyBuilder); | |
| 1261 jumps.addJump(rightTrueBuilder); | |
| 1262 jumps.addJump(rightFalseBuilder); | |
| 1263 ir.Continuation joinContinuation = | |
| 1264 createJoin(environment.length + 1, jumps); | |
| 1265 ir.Continuation leftTrueContinuation = new ir.Continuation([]); | |
| 1266 ir.Continuation leftFalseContinuation = new ir.Continuation([]); | |
| 1267 ir.Continuation rightTrueContinuation = new ir.Continuation([]); | |
| 1268 ir.Continuation rightFalseContinuation = new ir.Continuation([]); | |
| 1269 rightTrueContinuation.body = rightTrueBuilder._root; | |
| 1270 rightFalseContinuation.body = rightFalseBuilder._root; | |
| 1271 // The right subexpression has two continuations. | |
| 1272 rightBuilder.add( | |
| 1273 new ir.LetCont(rightTrueContinuation, | |
| 1274 new ir.LetCont(rightFalseContinuation, | |
| 1275 new ir.Branch(new ir.IsTrue(rightValue), | |
| 1276 rightTrueContinuation, | |
| 1277 rightFalseContinuation)))); | |
| 1278 // Depending on the operator, the left subexpression's continuations are | |
| 1279 // either the right subexpression or an invocation of the join-point | |
| 1280 // continuation. | |
| 1281 if (isLazyOr) { | |
| 1282 leftTrueContinuation.body = emptyBuilder._root; | |
| 1283 leftFalseContinuation.body = rightBuilder._root; | |
| 1284 } else { | |
| 1285 leftTrueContinuation.body = rightBuilder._root; | |
| 1286 leftFalseContinuation.body = emptyBuilder._root; | |
| 1287 } | |
| 1288 | |
| 1289 add(new ir.LetCont(joinContinuation, | |
| 1290 new ir.LetCont(leftTrueContinuation, | |
| 1291 new ir.LetCont(leftFalseContinuation, | |
| 1292 new ir.Branch(new ir.IsTrue(leftValue), | |
| 1293 leftTrueContinuation, | |
| 1294 leftFalseContinuation))))); | |
| 1295 // There is always a join parameter for the result value, because it | |
| 1296 // is different on at least two paths. | |
| 1297 return joinContinuation.parameters.last; | |
| 1298 } | |
| 1299 | |
| 1300 /// Creates an access to `this`. | |
| 1301 ir.Primitive buildThis() { | |
| 1302 assert(isOpen); | |
| 1303 ir.Primitive result = new ir.This(); | |
| 1304 add(new ir.LetPrim(result)); | |
| 1305 return result; | |
| 1306 } | |
| 1307 | |
| 1308 /// Create a non-recursive join-point continuation. | |
| 1309 /// | |
| 1310 /// Given the environment length at the join point and a list of | |
| 1311 /// jumps that should reach the join point, create a join-point | |
| 1312 /// continuation. The join-point continuation has a parameter for each | |
| 1313 /// variable that has different values reaching on different paths. | |
| 1314 /// | |
| 1315 /// The jumps are uninitialized [ir.InvokeContinuation] expressions. | |
| 1316 /// They are filled in with the target continuation and appropriate | |
| 1317 /// arguments. | |
| 1318 /// | |
| 1319 /// As a side effect, the environment of this builder is updated to include | |
| 1320 /// the join-point continuation parameters. | |
| 1321 ir.Continuation createJoin(int environmentLength, JumpCollector jumps) { | |
| 1322 assert(jumps.length >= 2); | |
| 1323 | |
| 1324 // Compute which values are identical on all paths reaching the join. | |
| 1325 // Handle the common case of a pair of contexts efficiently. | |
| 1326 Environment first = jumps.environments[0]; | |
| 1327 Environment second = jumps.environments[1]; | |
| 1328 assert(environmentLength <= first.length); | |
| 1329 assert(environmentLength <= second.length); | |
| 1330 assert(first.sameDomain(environmentLength, second)); | |
| 1331 // A running count of the join-point parameters. | |
| 1332 int parameterCount = 0; | |
| 1333 // The null elements of common correspond to required parameters of the | |
| 1334 // join-point continuation. | |
| 1335 List<ir.Primitive> common = | |
| 1336 new List<ir.Primitive>.generate(environmentLength, | |
| 1337 (i) { | |
| 1338 ir.Primitive candidate = first[i]; | |
| 1339 if (second[i] == candidate) { | |
| 1340 return candidate; | |
| 1341 } else { | |
| 1342 ++parameterCount; | |
| 1343 return null; | |
| 1344 } | |
| 1345 }); | |
| 1346 // If there is already a parameter for each variable, the other | |
| 1347 // environments do not need to be considered. | |
| 1348 if (parameterCount < environmentLength) { | |
| 1349 for (int i = 0; i < environmentLength; ++i) { | |
| 1350 ir.Primitive candidate = common[i]; | |
| 1351 if (candidate == null) continue; | |
| 1352 for (Environment current in jumps.environments.skip(2)) { | |
| 1353 assert(environmentLength <= current.length); | |
| 1354 assert(first.sameDomain(environmentLength, current)); | |
| 1355 if (candidate != current[i]) { | |
| 1356 common[i] = null; | |
| 1357 ++parameterCount; | |
| 1358 break; | |
| 1359 } | |
| 1360 } | |
| 1361 if (parameterCount >= environmentLength) break; | |
| 1362 } | |
| 1363 } | |
| 1364 | |
| 1365 // Create the join point continuation. | |
| 1366 List<ir.Parameter> parameters = <ir.Parameter>[]; | |
| 1367 parameters.length = parameterCount; | |
| 1368 int index = 0; | |
| 1369 for (int i = 0; i < environmentLength; ++i) { | |
| 1370 if (common[i] == null) { | |
| 1371 parameters[index++] = new ir.Parameter(first.index2variable[i]); | |
| 1372 } | |
| 1373 } | |
| 1374 assert(index == parameterCount); | |
| 1375 ir.Continuation join = new ir.Continuation(parameters); | |
| 1376 | |
| 1377 // Fill in all the continuation invocations. | |
| 1378 for (int i = 0; i < jumps.length; ++i) { | |
| 1379 Environment currentEnvironment = jumps.environments[i]; | |
| 1380 ir.InvokeContinuation invoke = jumps.invocations[i]; | |
| 1381 // Sharing this.environment with one of the invocations will not do | |
| 1382 // the right thing (this.environment has already been mutated). | |
| 1383 List<ir.Reference> arguments = <ir.Reference>[]; | |
| 1384 arguments.length = parameterCount; | |
| 1385 int index = 0; | |
| 1386 for (int i = 0; i < environmentLength; ++i) { | |
| 1387 if (common[i] == null) { | |
| 1388 arguments[index++] = new ir.Reference(currentEnvironment[i]); | |
| 1389 } | |
| 1390 } | |
| 1391 invoke.continuation = new ir.Reference(join); | |
| 1392 invoke.arguments = arguments; | |
| 1393 } | |
| 1394 | |
| 1395 // Mutate this.environment to be the environment at the join point. Do | |
| 1396 // this after adding the continuation invocations, because this.environment | |
| 1397 // might be collected by the jump collector and so the old environment | |
| 1398 // values are needed for the continuation invocation. | |
| 1399 // | |
| 1400 // Iterate to environment.length because environmentLength includes values | |
| 1401 // outside the environment which are 'phantom' variables used for the | |
| 1402 // values of expressions like &&, ||, and ?:. | |
| 1403 index = 0; | |
| 1404 for (int i = 0; i < environment.length; ++i) { | |
| 1405 if (common[i] == null) { | |
| 1406 environment.index2value[i] = parameters[index++]; | |
| 1407 } | |
| 1408 } | |
| 1409 | |
| 1410 return join; | |
| 1411 } | |
| 1412 } | |
| 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