| 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 nodes in the context of the provided [builder]. | |
| 131 typedef ir.Node SubbuildFunction(IrBuilder builder); | |
| 132 | |
| 133 /// Mixin that provides encapsulated access to nested builders. | |
| 134 abstract class IrBuilderMixin<N> { | |
| 135 IrBuilder _irBuilder; | |
| 136 | |
| 137 /// Execute [f] with [builder] as the current builder. | |
| 138 withBuilder(IrBuilder builder, f()) { | |
| 139 assert(builder != null); | |
| 140 IrBuilder prev = _irBuilder; | |
| 141 _irBuilder = builder; | |
| 142 var result = f(); | |
| 143 _irBuilder = prev; | |
| 144 return result; | |
| 145 } | |
| 146 | |
| 147 /// The current builder. | |
| 148 IrBuilder get irBuilder { | |
| 149 assert(_irBuilder != null); | |
| 150 return _irBuilder; | |
| 151 } | |
| 152 | |
| 153 /// Visits the [node]. | |
| 154 ir.Primitive visit(N node); | |
| 155 | |
| 156 /// Builds and returns the [ir.Node] for [node] or returns `null` if | |
| 157 /// [node] is `null`. | |
| 158 ir.Node build(N node) => node != null ? visit(node) : null; | |
| 159 | |
| 160 /// Returns a closure that takes an [IrBuilder] and builds [node] in its | |
| 161 /// context using [build]. | |
| 162 SubbuildFunction subbuild(N node) { | |
| 163 return (IrBuilder builder) => withBuilder(builder, () => build(node)); | |
| 164 } | |
| 165 } | |
| 166 | |
| 167 /// Shared state between nested builders. | |
| 168 class IrBuilderSharedState { | |
| 169 final ConstantSystem constantSystem; | |
| 170 | |
| 171 /// A stack of collectors for breaks. | |
| 172 final List<JumpCollector> breakCollectors = <JumpCollector>[]; | |
| 173 | |
| 174 /// A stack of collectors for continues. | |
| 175 final List<JumpCollector> continueCollectors = <JumpCollector>[]; | |
| 176 | |
| 177 final List<ConstDeclaration> localConstants = <ConstDeclaration>[]; | |
| 178 | |
| 179 final Iterable<Entity> closureLocals; | |
| 180 | |
| 181 final FunctionElement currentFunction; | |
| 182 | |
| 183 final ir.Continuation returnContinuation = new ir.Continuation.retrn(); | |
| 184 | |
| 185 IrBuilderSharedState(this.constantSystem, | |
| 186 this.currentFunction, | |
| 187 this.closureLocals); | |
| 188 } | |
| 189 | |
| 190 /// A factory for building the cps IR. | |
| 191 class IrBuilder { | |
| 192 // TODO(johnniwinther): Make these field final and remove the default values | |
| 193 // when [IrBuilder] is a property of [IrBuilderVisitor] instead of a mixin. | |
| 194 | |
| 195 final List<ir.Parameter> _parameters = <ir.Parameter>[]; | |
| 196 | |
| 197 final IrBuilderSharedState state; | |
| 198 | |
| 199 /// A map from variable indexes to their values. | |
| 200 Environment environment; | |
| 201 | |
| 202 // The IR builder maintains a context, which is an expression with a hole in | |
| 203 // it. The hole represents the focus where new expressions can be added. | |
| 204 // The context is implemented by 'root' which is the root of the expression | |
| 205 // and 'current' which is the expression that immediately contains the hole. | |
| 206 // Not all expressions have a hole (e.g., invocations, which always occur in | |
| 207 // tail position, do not have a hole). Expressions with a hole have a plug | |
| 208 // method. | |
| 209 // | |
| 210 // Conceptually, visiting a statement takes a context as input and returns | |
| 211 // either a new context or else an expression without a hole if all | |
| 212 // control-flow paths through the statement have exited. An expression | |
| 213 // without a hole is represented by a (root, current) pair where root is the | |
| 214 // expression and current is null. | |
| 215 // | |
| 216 // Conceptually again, visiting an expression takes a context as input and | |
| 217 // returns either a pair of a new context and a definition denoting | |
| 218 // the expression's value, or else an expression without a hole if all | |
| 219 // control-flow paths through the expression have exited. | |
| 220 // | |
| 221 // We do not pass contexts as arguments or return them. Rather we use the | |
| 222 // current context (root, current) as the visitor state and mutate current. | |
| 223 // Visiting a statement returns null; visiting an expression returns the | |
| 224 // primitive denoting its value. | |
| 225 | |
| 226 ir.Expression _root = null; | |
| 227 ir.Expression _current = null; | |
| 228 | |
| 229 IrBuilder(ConstantSystem constantSystem, | |
| 230 FunctionElement currentFunction, | |
| 231 Iterable<Entity> closureLocals) | |
| 232 : this.state = new IrBuilderSharedState( | |
| 233 constantSystem, currentFunction, closureLocals), | |
| 234 this.environment = new Environment.empty(); | |
| 235 | |
| 236 /// Construct a delimited visitor for visiting a subtree. | |
| 237 /// | |
| 238 /// The delimited visitor has its own compile-time environment mapping | |
| 239 /// local variables to their values, which is initially a copy of the parent | |
| 240 /// environment. It has its own context for building an IR expression, so | |
| 241 /// the built expression is not plugged into the parent's context. | |
| 242 IrBuilder.delimited(IrBuilder parent) | |
| 243 : this.state = parent.state, | |
| 244 this.environment = new Environment.from(parent.environment); | |
| 245 | |
| 246 /// Construct a visitor for a recursive continuation. | |
| 247 /// | |
| 248 /// The recursive continuation builder has fresh parameters (i.e. SSA phis) | |
| 249 /// for all the local variables in the parent, because the invocation sites | |
| 250 /// of the continuation are not all known when the builder is created. The | |
| 251 /// recursive invocations will be passed values for all the local variables, | |
| 252 /// which may be eliminated later if they are redundant---if they take on | |
| 253 /// the same value at all invocation sites. | |
| 254 IrBuilder.recursive(IrBuilder parent) | |
| 255 : this.state = parent.state, | |
| 256 this.environment = new Environment.empty() { | |
| 257 parent.environment.index2variable.forEach(createParameter); | |
| 258 } | |
| 259 | |
| 260 | |
| 261 bool get isOpen => _root == null || _current != null; | |
| 262 | |
| 263 /// Create a parameter for [parameterElement] and add it to the current | |
| 264 /// environment. | |
| 265 /// | |
| 266 /// [isClosureVariable] marks whether [parameterElement] is accessed from an | |
| 267 /// inner function. | |
| 268 void createParameter(LocalElement parameterElement, | |
| 269 {bool isClosureVariable: false}) { | |
| 270 ir.Parameter parameter = new ir.Parameter(parameterElement); | |
| 271 _parameters.add(parameter); | |
| 272 if (isClosureVariable) { | |
| 273 add(new ir.SetClosureVariable(parameterElement, parameter)); | |
| 274 } else { | |
| 275 environment.extend(parameterElement, parameter); | |
| 276 } | |
| 277 } | |
| 278 | |
| 279 /// Add the constant [variableElement] to the environment with [value] as its | |
| 280 /// constant value. | |
| 281 void declareLocalConstant(LocalVariableElement variableElement, | |
| 282 ConstantExpression value) { | |
| 283 state.localConstants.add(new ConstDeclaration(variableElement, value)); | |
| 284 } | |
| 285 | |
| 286 /// Add [variableElement] to the environment with [initialValue] as its | |
| 287 /// initial value. | |
| 288 /// | |
| 289 /// [isClosureVariable] marks whether [variableElement] is accessed from an | |
| 290 /// inner function. | |
| 291 void declareLocalVariable(LocalVariableElement variableElement, | |
| 292 {ir.Primitive initialValue, | |
| 293 bool isClosureVariable: false}) { | |
| 294 assert(isOpen); | |
| 295 if (initialValue == null) { | |
| 296 // TODO(kmillikin): Consider pooling constants. | |
| 297 // The initial value is null. | |
| 298 initialValue = buildNullLiteral(); | |
| 299 } | |
| 300 if (isClosureVariable) { | |
| 301 add(new ir.SetClosureVariable(variableElement, | |
| 302 initialValue, | |
| 303 isDeclaration: true)); | |
| 304 } else { | |
| 305 // In case a primitive was introduced for the initializer expression, | |
| 306 // use this variable element to help derive a good name for it. | |
| 307 initialValue.useElementAsHint(variableElement); | |
| 308 environment.extend(variableElement, initialValue); | |
| 309 } | |
| 310 } | |
| 311 | |
| 312 // Plug an expression into the 'hole' in the context being accumulated. The | |
| 313 // empty context (just a hole) is represented by root (and current) being | |
| 314 // null. Since the hole in the current context is filled by this function, | |
| 315 // the new hole must be in the newly added expression---which becomes the | |
| 316 // new value of current. | |
| 317 void add(ir.Expression expr) { | |
| 318 assert(isOpen); | |
| 319 if (_root == null) { | |
| 320 _root = _current = expr; | |
| 321 } else { | |
| 322 _current = _current.plug(expr); | |
| 323 } | |
| 324 } | |
| 325 | |
| 326 ir.Primitive continueWithExpression(ir.Expression build(ir.Continuation k)) { | |
| 327 ir.Parameter v = new ir.Parameter(null); | |
| 328 ir.Continuation k = new ir.Continuation([v]); | |
| 329 ir.Expression expression = build(k); | |
| 330 add(new ir.LetCont(k, expression)); | |
| 331 return v; | |
| 332 } | |
| 333 | |
| 334 /// Create a constant literal from [constant]. | |
| 335 ir.Constant buildConstantLiteral(ConstantExpression constant) { | |
| 336 assert(isOpen); | |
| 337 ir.Constant prim = new ir.Constant(constant); | |
| 338 add(new ir.LetPrim(prim)); | |
| 339 return prim; | |
| 340 } | |
| 341 | |
| 342 // Helper for building primitive literals. | |
| 343 ir.Constant _buildPrimitiveConstant(PrimitiveConstantValue constant) { | |
| 344 return buildConstantLiteral(new PrimitiveConstantExpression(constant)); | |
| 345 } | |
| 346 | |
| 347 /// Create an integer literal. | |
| 348 ir.Constant buildIntegerLiteral(int value) { | |
| 349 return _buildPrimitiveConstant(state.constantSystem.createInt(value)); | |
| 350 } | |
| 351 | |
| 352 /// Create an double literal. | |
| 353 ir.Constant buildDoubleLiteral(double value) { | |
| 354 return _buildPrimitiveConstant(state.constantSystem.createDouble(value)); | |
| 355 } | |
| 356 | |
| 357 /// Create an bool literal. | |
| 358 ir.Constant buildBooleanLiteral(bool value) { | |
| 359 return _buildPrimitiveConstant(state.constantSystem.createBool(value)); | |
| 360 } | |
| 361 | |
| 362 /// Create an null literal. | |
| 363 ir.Constant buildNullLiteral() { | |
| 364 return _buildPrimitiveConstant(state.constantSystem.createNull()); | |
| 365 } | |
| 366 | |
| 367 /// Create a string literal. | |
| 368 ir.Constant buildStringLiteral(String value) { | |
| 369 return _buildPrimitiveConstant( | |
| 370 state.constantSystem.createString(new ast.DartString.literal(value))); | |
| 371 } | |
| 372 | |
| 373 /// Creates a conditional expression with the provided [condition] where the | |
| 374 /// then and else expression are created through the [buildThenExpression] and | |
| 375 /// [buildElseExpression] functions, respectively. | |
| 376 ir.Primitive buildConditional( | |
| 377 ir.Primitive condition, | |
| 378 ir.Primitive buildThenExpression(IrBuilder builder), | |
| 379 ir.Primitive buildElseExpression(IrBuilder builder)) { | |
| 380 | |
| 381 assert(isOpen); | |
| 382 | |
| 383 // The then and else expressions are delimited. | |
| 384 IrBuilder thenBuilder = new IrBuilder.delimited(this); | |
| 385 IrBuilder elseBuilder = new IrBuilder.delimited(this); | |
| 386 ir.Primitive thenValue = buildThenExpression(thenBuilder); | |
| 387 ir.Primitive elseValue = buildElseExpression(elseBuilder); | |
| 388 | |
| 389 // Treat the values of the subexpressions as named values in the | |
| 390 // environment, so they will be treated as arguments to the join-point | |
| 391 // continuation. | |
| 392 assert(environment.length == thenBuilder.environment.length); | |
| 393 assert(environment.length == elseBuilder.environment.length); | |
| 394 thenBuilder.environment.extend(null, thenValue); | |
| 395 elseBuilder.environment.extend(null, elseValue); | |
| 396 JumpCollector jumps = new JumpCollector(null); | |
| 397 jumps.addJump(thenBuilder); | |
| 398 jumps.addJump(elseBuilder); | |
| 399 ir.Continuation joinContinuation = | |
| 400 createJoin(environment.length + 1, jumps); | |
| 401 | |
| 402 // Build the term | |
| 403 // let cont join(x, ..., result) = [] in | |
| 404 // let cont then() = [[thenPart]]; join(v, ...) in | |
| 405 // let cont else() = [[elsePart]]; join(v, ...) in | |
| 406 // if condition (then, else) | |
| 407 ir.Continuation thenContinuation = new ir.Continuation([]); | |
| 408 ir.Continuation elseContinuation = new ir.Continuation([]); | |
| 409 thenContinuation.body = thenBuilder._root; | |
| 410 elseContinuation.body = elseBuilder._root; | |
| 411 add(new ir.LetCont(joinContinuation, | |
| 412 new ir.LetCont(thenContinuation, | |
| 413 new ir.LetCont(elseContinuation, | |
| 414 new ir.Branch(new ir.IsTrue(condition), | |
| 415 thenContinuation, | |
| 416 elseContinuation))))); | |
| 417 return (thenValue == elseValue) | |
| 418 ? thenValue | |
| 419 : joinContinuation.parameters.last; | |
| 420 | |
| 421 } | |
| 422 | |
| 423 /// Create a get access of [local]. | |
| 424 ir.Primitive buildLocalGet(Element local) { | |
| 425 assert(isOpen); | |
| 426 return environment.lookup(local); | |
| 427 } | |
| 428 | |
| 429 /// Create a get access of the static [element]. | |
| 430 ir.Primitive buildStaticGet(Element element, Selector selector) { | |
| 431 assert(isOpen); | |
| 432 assert(selector.isGetter); | |
| 433 return continueWithExpression( | |
| 434 (k) => new ir.InvokeStatic( | |
| 435 element, selector, k, const <ir.Definition>[])); | |
| 436 } | |
| 437 | |
| 438 /// Create a dynamic get access on [receiver] where the property is defined | |
| 439 /// by the getter [selector]. | |
| 440 ir.Primitive buildDynamicGet(ir.Primitive receiver, Selector selector) { | |
| 441 assert(isOpen); | |
| 442 assert(selector.isGetter); | |
| 443 return continueWithExpression( | |
| 444 (k) => new ir.InvokeMethod( | |
| 445 receiver, selector, k, const <ir.Definition>[])); | |
| 446 } | |
| 447 | |
| 448 /** | |
| 449 * Add an explicit `return null` for functions that don't have a return | |
| 450 * statement on each branch. This includes functions with an empty body, | |
| 451 * such as `foo(){ }`. | |
| 452 */ | |
| 453 void ensureReturn() { | |
| 454 if (!isOpen) return; | |
| 455 ir.Constant constant = buildNullLiteral(); | |
| 456 add(new ir.InvokeContinuation(state.returnContinuation, [constant])); | |
| 457 _current = null; | |
| 458 } | |
| 459 | |
| 460 /// Create a [ir.FunctionDefinition] for [element] using [_root] as the body. | |
| 461 /// | |
| 462 /// Parameters must be created before the construction of the body using | |
| 463 /// [createParameter]. | |
| 464 ir.FunctionDefinition buildFunctionDefinition( | |
| 465 FunctionElement element, | |
| 466 List<ConstantExpression> defaults) { | |
| 467 if (!element.isAbstract) { | |
| 468 ensureReturn(); | |
| 469 return new ir.FunctionDefinition( | |
| 470 element, state.returnContinuation, _parameters, _root, | |
| 471 state.localConstants, defaults); | |
| 472 } else { | |
| 473 assert(invariant(element, _root == null, | |
| 474 message: "Non-empty body for abstract method $element: $_root")); | |
| 475 assert(invariant(element, state.localConstants.isEmpty, | |
| 476 message: "Local constants for abstract method $element: " | |
| 477 "${state.localConstants}")); | |
| 478 return new ir.FunctionDefinition.abstract( | |
| 479 element, _parameters, defaults); | |
| 480 } | |
| 481 } | |
| 482 | |
| 483 | |
| 484 /// Create a super invocation with method name and arguments structure defined | |
| 485 /// by [selector] and argument values defined by [arguments]. | |
| 486 ir.Primitive buildSuperInvocation(Selector selector, | |
| 487 List<ir.Definition> arguments) { | |
| 488 assert(isOpen); | |
| 489 return continueWithExpression( | |
| 490 (k) => new ir.InvokeSuperMethod(selector, k, arguments)); | |
| 491 | |
| 492 } | |
| 493 | |
| 494 /// Create a dynamic invocation on [receiver] with method name and arguments | |
| 495 /// structure defined by [selector] and argument values defined by | |
| 496 /// [arguments]. | |
| 497 ir.Primitive buildDynamicInvocation(ir.Definition receiver, | |
| 498 Selector selector, | |
| 499 List<ir.Definition> arguments) { | |
| 500 assert(isOpen); | |
| 501 return continueWithExpression( | |
| 502 (k) => new ir.InvokeMethod(receiver, selector, k, arguments)); | |
| 503 } | |
| 504 | |
| 505 /// Create a static invocation of [element] with arguments structure defined | |
| 506 /// by [selector] and argument values defined by [arguments]. | |
| 507 ir.Primitive buildStaticInvocation(Element element, | |
| 508 Selector selector, | |
| 509 List<ir.Definition> arguments) { | |
| 510 return continueWithExpression( | |
| 511 (k) => new ir.InvokeStatic(element, selector, k, arguments)); | |
| 512 } | |
| 513 | |
| 514 /// Creates an if-then-else statement with the provided [condition] where the | |
| 515 /// then and else branches are created through the [buildThenPart] and | |
| 516 /// [buildElsePart] functions, respectively. | |
| 517 /// | |
| 518 /// An if-then statement is created if [buildElsePart] is a no-op. | |
| 519 // TODO(johnniwinther): Unify implementation with [buildConditional] and | |
| 520 // [_buildLogicalOperator]. | |
| 521 void buildIf(ir.Primitive condition, | |
| 522 void buildThenPart(IrBuilder builder), | |
| 523 void buildElsePart(IrBuilder builder)) { | |
| 524 assert(isOpen); | |
| 525 | |
| 526 // The then and else parts are delimited. | |
| 527 IrBuilder thenBuilder = new IrBuilder.delimited(this); | |
| 528 IrBuilder elseBuilder = new IrBuilder.delimited(this); | |
| 529 buildThenPart(thenBuilder); | |
| 530 buildElsePart(elseBuilder); | |
| 531 | |
| 532 // Build the term | |
| 533 // (Result =) let cont then() = [[thenPart]] in | |
| 534 // let cont else() = [[elsePart]] in | |
| 535 // if condition (then, else) | |
| 536 ir.Continuation thenContinuation = new ir.Continuation([]); | |
| 537 ir.Continuation elseContinuation = new ir.Continuation([]); | |
| 538 ir.Expression letElse = | |
| 539 new ir.LetCont(elseContinuation, | |
| 540 new ir.Branch(new ir.IsTrue(condition), | |
| 541 thenContinuation, | |
| 542 elseContinuation)); | |
| 543 ir.Expression letThen = new ir.LetCont(thenContinuation, letElse); | |
| 544 ir.Expression result = letThen; | |
| 545 | |
| 546 ir.Continuation joinContinuation; // Null if there is no join. | |
| 547 if (thenBuilder.isOpen && elseBuilder.isOpen) { | |
| 548 // There is a join-point continuation. Build the term | |
| 549 // 'let cont join(x, ...) = [] in Result' and plug invocations of the | |
| 550 // join-point continuation into the then and else continuations. | |
| 551 JumpCollector jumps = new JumpCollector(null); | |
| 552 jumps.addJump(thenBuilder); | |
| 553 jumps.addJump(elseBuilder); | |
| 554 joinContinuation = createJoin(environment.length, jumps); | |
| 555 result = new ir.LetCont(joinContinuation, result); | |
| 556 } | |
| 557 | |
| 558 // The then or else term root could be null, but not both. If there is | |
| 559 // a join then an InvokeContinuation was just added to both of them. If | |
| 560 // there is no join, then at least one of them is closed and thus has a | |
| 561 // non-null root by the definition of the predicate isClosed. In the | |
| 562 // case that one of them is null, it must be the only one that is open | |
| 563 // and thus contains the new hole in the context. This case is handled | |
| 564 // after the branch is plugged into the current hole. | |
| 565 thenContinuation.body = thenBuilder._root; | |
| 566 elseContinuation.body = elseBuilder._root; | |
| 567 | |
| 568 add(result); | |
| 569 if (joinContinuation == null) { | |
| 570 // At least one subexpression is closed. | |
| 571 if (thenBuilder.isOpen) { | |
| 572 _current = | |
| 573 (thenBuilder._root == null) ? letThen : thenBuilder._current; | |
| 574 environment = thenBuilder.environment; | |
| 575 } else if (elseBuilder.isOpen) { | |
| 576 _current = | |
| 577 (elseBuilder._root == null) ? letElse : elseBuilder._current; | |
| 578 environment = elseBuilder.environment; | |
| 579 } else { | |
| 580 _current = null; | |
| 581 } | |
| 582 } | |
| 583 } | |
| 584 | |
| 585 /// Create a return statement `return value;` or `return;` if [value] is | |
| 586 /// null. | |
| 587 void buildReturn([ir.Primitive value]) { | |
| 588 // Build(Return(e), C) = C'[InvokeContinuation(return, x)] | |
| 589 // where (C', x) = Build(e, C) | |
| 590 // | |
| 591 // Return without a subexpression is translated as if it were return null. | |
| 592 assert(isOpen); | |
| 593 if (value == null) { | |
| 594 value = buildNullLiteral(); | |
| 595 } | |
| 596 add(new ir.InvokeContinuation(state.returnContinuation, [value])); | |
| 597 _current = null; | |
| 598 } | |
| 599 | |
| 600 /// Create a blocks of [statements] by applying [build] to all reachable | |
| 601 /// statements. | |
| 602 // TODO(johnniwinther): Type [statements] as `Iterable` when `NodeList` uses | |
| 603 // `List` instead of `Link`. | |
| 604 void buildBlock(var statements, build(statement)) { | |
| 605 // Build(Block(stamements), C) = C' | |
| 606 // where C' = statements.fold(Build, C) | |
| 607 assert(isOpen); | |
| 608 for (var statement in statements) { | |
| 609 build(statement); | |
| 610 if (!isOpen) return; | |
| 611 } | |
| 612 } | |
| 613 | |
| 614 | |
| 615 // Build(BreakStatement L, C) = C[InvokeContinuation(...)] | |
| 616 // | |
| 617 // The continuation and arguments are filled in later after translating | |
| 618 // the body containing the break. | |
| 619 bool buildBreak(JumpTarget target) { | |
| 620 return buildJumpInternal(target, state.breakCollectors); | |
| 621 } | |
| 622 | |
| 623 // Build(ContinueStatement L, C) = C[InvokeContinuation(...)] | |
| 624 // | |
| 625 // The continuation and arguments are filled in later after translating | |
| 626 // the body containing the continue. | |
| 627 bool buildContinue(JumpTarget target) { | |
| 628 return buildJumpInternal(target, state.continueCollectors); | |
| 629 } | |
| 630 | |
| 631 bool buildJumpInternal(JumpTarget target, | |
| 632 Iterable<JumpCollector> collectors) { | |
| 633 assert(isOpen); | |
| 634 for (JumpCollector collector in collectors) { | |
| 635 if (target == collector.target) { | |
| 636 collector.addJump(this); | |
| 637 return true; | |
| 638 } | |
| 639 } | |
| 640 return false; | |
| 641 } | |
| 642 | |
| 643 /// Create a negation of [condition]. | |
| 644 ir.Primitive buildNegation(ir.Primitive condition) { | |
| 645 // ! e is translated as e ? false : true | |
| 646 | |
| 647 // Add a continuation parameter for the result of the expression. | |
| 648 ir.Parameter resultParameter = new ir.Parameter(null); | |
| 649 | |
| 650 ir.Continuation joinContinuation = new ir.Continuation([resultParameter]); | |
| 651 ir.Continuation thenContinuation = new ir.Continuation([]); | |
| 652 ir.Continuation elseContinuation = new ir.Continuation([]); | |
| 653 | |
| 654 ir.Constant makeBoolConstant(bool value) { | |
| 655 return new ir.Constant(new PrimitiveConstantExpression( | |
| 656 state.constantSystem.createBool(value))); | |
| 657 } | |
| 658 | |
| 659 ir.Constant trueConstant = makeBoolConstant(true); | |
| 660 ir.Constant falseConstant = makeBoolConstant(false); | |
| 661 | |
| 662 thenContinuation.body = new ir.LetPrim(falseConstant) | |
| 663 ..plug(new ir.InvokeContinuation(joinContinuation, [falseConstant])); | |
| 664 elseContinuation.body = new ir.LetPrim(trueConstant) | |
| 665 ..plug(new ir.InvokeContinuation(joinContinuation, [trueConstant])); | |
| 666 | |
| 667 add(new ir.LetCont(joinContinuation, | |
| 668 new ir.LetCont(thenContinuation, | |
| 669 new ir.LetCont(elseContinuation, | |
| 670 new ir.Branch(new ir.IsTrue(condition), | |
| 671 thenContinuation, | |
| 672 elseContinuation))))); | |
| 673 return resultParameter; | |
| 674 } | |
| 675 | |
| 676 /// Create a lazy and/or expression. [leftValue] is the value of the left | |
| 677 /// operand and [buildRightValue] is called to process the value of the right | |
| 678 /// operand in the context of its own [IrBuilder]. | |
| 679 ir.Primitive buildLogicalOperator( | |
| 680 ir.Primitive leftValue, | |
| 681 ir.Primitive buildRightValue(IrBuilder builder), | |
| 682 {bool isLazyOr: false}) { | |
| 683 // e0 && e1 is translated as if e0 ? (e1 == true) : false. | |
| 684 // e0 || e1 is translated as if e0 ? true : (e1 == true). | |
| 685 // The translation must convert both e0 and e1 to booleans and handle | |
| 686 // local variable assignments in e1. | |
| 687 | |
| 688 IrBuilder rightBuilder = new IrBuilder.delimited(this); | |
| 689 ir.Primitive rightValue = buildRightValue(rightBuilder); | |
| 690 // A dummy empty target for the branch on the left subexpression branch. | |
| 691 // This enables using the same infrastructure for join-point continuations | |
| 692 // as in visitIf and visitConditional. It will hold a definition of the | |
| 693 // appropriate constant and an invocation of the join-point continuation. | |
| 694 IrBuilder emptyBuilder = new IrBuilder.delimited(this); | |
| 695 // Dummy empty targets for right true and right false. They hold | |
| 696 // definitions of the appropriate constant and an invocation of the | |
| 697 // join-point continuation. | |
| 698 IrBuilder rightTrueBuilder = new IrBuilder.delimited(rightBuilder); | |
| 699 IrBuilder rightFalseBuilder = new IrBuilder.delimited(rightBuilder); | |
| 700 | |
| 701 // If we don't evaluate the right subexpression, the value of the whole | |
| 702 // expression is this constant. | |
| 703 ir.Constant leftBool = emptyBuilder.buildBooleanLiteral(isLazyOr); | |
| 704 // If we do evaluate the right subexpression, the value of the expression | |
| 705 // is a true or false constant. | |
| 706 ir.Constant rightTrue = rightTrueBuilder.buildBooleanLiteral(true); | |
| 707 ir.Constant rightFalse = rightFalseBuilder.buildBooleanLiteral(false); | |
| 708 | |
| 709 // Treat the result values as named values in the environment, so they | |
| 710 // will be treated as arguments to the join-point continuation. | |
| 711 assert(environment.length == emptyBuilder.environment.length); | |
| 712 assert(environment.length == rightTrueBuilder.environment.length); | |
| 713 assert(environment.length == rightFalseBuilder.environment.length); | |
| 714 emptyBuilder.environment.extend(null, leftBool); | |
| 715 rightTrueBuilder.environment.extend(null, rightTrue); | |
| 716 rightFalseBuilder.environment.extend(null, rightFalse); | |
| 717 | |
| 718 // Wire up two continuations for the left subexpression, two continuations | |
| 719 // for the right subexpression, and a three-way join continuation. | |
| 720 JumpCollector jumps = new JumpCollector(null); | |
| 721 jumps.addJump(emptyBuilder); | |
| 722 jumps.addJump(rightTrueBuilder); | |
| 723 jumps.addJump(rightFalseBuilder); | |
| 724 ir.Continuation joinContinuation = | |
| 725 createJoin(environment.length + 1, jumps); | |
| 726 ir.Continuation leftTrueContinuation = new ir.Continuation([]); | |
| 727 ir.Continuation leftFalseContinuation = new ir.Continuation([]); | |
| 728 ir.Continuation rightTrueContinuation = new ir.Continuation([]); | |
| 729 ir.Continuation rightFalseContinuation = new ir.Continuation([]); | |
| 730 rightTrueContinuation.body = rightTrueBuilder._root; | |
| 731 rightFalseContinuation.body = rightFalseBuilder._root; | |
| 732 // The right subexpression has two continuations. | |
| 733 rightBuilder.add( | |
| 734 new ir.LetCont(rightTrueContinuation, | |
| 735 new ir.LetCont(rightFalseContinuation, | |
| 736 new ir.Branch(new ir.IsTrue(rightValue), | |
| 737 rightTrueContinuation, | |
| 738 rightFalseContinuation)))); | |
| 739 // Depending on the operator, the left subexpression's continuations are | |
| 740 // either the right subexpression or an invocation of the join-point | |
| 741 // continuation. | |
| 742 if (isLazyOr) { | |
| 743 leftTrueContinuation.body = emptyBuilder._root; | |
| 744 leftFalseContinuation.body = rightBuilder._root; | |
| 745 } else { | |
| 746 leftTrueContinuation.body = rightBuilder._root; | |
| 747 leftFalseContinuation.body = emptyBuilder._root; | |
| 748 } | |
| 749 | |
| 750 add(new ir.LetCont(joinContinuation, | |
| 751 new ir.LetCont(leftTrueContinuation, | |
| 752 new ir.LetCont(leftFalseContinuation, | |
| 753 new ir.Branch(new ir.IsTrue(leftValue), | |
| 754 leftTrueContinuation, | |
| 755 leftFalseContinuation))))); | |
| 756 // There is always a join parameter for the result value, because it | |
| 757 // is different on at least two paths. | |
| 758 return joinContinuation.parameters.last; | |
| 759 } | |
| 760 | |
| 761 /// Create a non-recursive join-point continuation. | |
| 762 /// | |
| 763 /// Given the environment length at the join point and a list of | |
| 764 /// jumps that should reach the join point, create a join-point | |
| 765 /// continuation. The join-point continuation has a parameter for each | |
| 766 /// variable that has different values reaching on different paths. | |
| 767 /// | |
| 768 /// The jumps are uninitialized [ir.InvokeContinuation] expressions. | |
| 769 /// They are filled in with the target continuation and appropriate | |
| 770 /// arguments. | |
| 771 /// | |
| 772 /// As a side effect, the environment of this builder is updated to include | |
| 773 /// the join-point continuation parameters. | |
| 774 ir.Continuation createJoin(int environmentLength, JumpCollector jumps) { | |
| 775 assert(jumps.length >= 2); | |
| 776 | |
| 777 // Compute which values are identical on all paths reaching the join. | |
| 778 // Handle the common case of a pair of contexts efficiently. | |
| 779 Environment first = jumps.environments[0]; | |
| 780 Environment second = jumps.environments[1]; | |
| 781 assert(environmentLength <= first.length); | |
| 782 assert(environmentLength <= second.length); | |
| 783 assert(first.sameDomain(environmentLength, second)); | |
| 784 // A running count of the join-point parameters. | |
| 785 int parameterCount = 0; | |
| 786 // The null elements of common correspond to required parameters of the | |
| 787 // join-point continuation. | |
| 788 List<ir.Primitive> common = | |
| 789 new List<ir.Primitive>.generate(environmentLength, | |
| 790 (i) { | |
| 791 ir.Primitive candidate = first[i]; | |
| 792 if (second[i] == candidate) { | |
| 793 return candidate; | |
| 794 } else { | |
| 795 ++parameterCount; | |
| 796 return null; | |
| 797 } | |
| 798 }); | |
| 799 // If there is already a parameter for each variable, the other | |
| 800 // environments do not need to be considered. | |
| 801 if (parameterCount < environmentLength) { | |
| 802 for (int i = 0; i < environmentLength; ++i) { | |
| 803 ir.Primitive candidate = common[i]; | |
| 804 if (candidate == null) continue; | |
| 805 for (Environment current in jumps.environments.skip(2)) { | |
| 806 assert(environmentLength <= current.length); | |
| 807 assert(first.sameDomain(environmentLength, current)); | |
| 808 if (candidate != current[i]) { | |
| 809 common[i] = null; | |
| 810 ++parameterCount; | |
| 811 break; | |
| 812 } | |
| 813 } | |
| 814 if (parameterCount >= environmentLength) break; | |
| 815 } | |
| 816 } | |
| 817 | |
| 818 // Create the join point continuation. | |
| 819 List<ir.Parameter> parameters = <ir.Parameter>[]; | |
| 820 parameters.length = parameterCount; | |
| 821 int index = 0; | |
| 822 for (int i = 0; i < environmentLength; ++i) { | |
| 823 if (common[i] == null) { | |
| 824 parameters[index++] = new ir.Parameter(first.index2variable[i]); | |
| 825 } | |
| 826 } | |
| 827 assert(index == parameterCount); | |
| 828 ir.Continuation join = new ir.Continuation(parameters); | |
| 829 | |
| 830 // Fill in all the continuation invocations. | |
| 831 for (int i = 0; i < jumps.length; ++i) { | |
| 832 Environment currentEnvironment = jumps.environments[i]; | |
| 833 ir.InvokeContinuation invoke = jumps.invocations[i]; | |
| 834 // Sharing this.environment with one of the invocations will not do | |
| 835 // the right thing (this.environment has already been mutated). | |
| 836 List<ir.Reference> arguments = <ir.Reference>[]; | |
| 837 arguments.length = parameterCount; | |
| 838 int index = 0; | |
| 839 for (int i = 0; i < environmentLength; ++i) { | |
| 840 if (common[i] == null) { | |
| 841 arguments[index++] = new ir.Reference(currentEnvironment[i]); | |
| 842 } | |
| 843 } | |
| 844 invoke.continuation = new ir.Reference(join); | |
| 845 invoke.arguments = arguments; | |
| 846 } | |
| 847 | |
| 848 // Mutate this.environment to be the environment at the join point. Do | |
| 849 // this after adding the continuation invocations, because this.environment | |
| 850 // might be collected by the jump collector and so the old environment | |
| 851 // values are needed for the continuation invocation. | |
| 852 // | |
| 853 // Iterate to environment.length because environmentLength includes values | |
| 854 // outside the environment which are 'phantom' variables used for the | |
| 855 // values of expressions like &&, ||, and ?:. | |
| 856 index = 0; | |
| 857 for (int i = 0; i < environment.length; ++i) { | |
| 858 if (common[i] == null) { | |
| 859 environment.index2value[i] = parameters[index++]; | |
| 860 } | |
| 861 } | |
| 862 | |
| 863 return join; | |
| 864 } | |
| 865 } | |
| OLD | NEW |
|---|
Chromium Code Reviews
Issue 692513002:
Remove old dart2js code. (Closed)
Base URL: https://dart.googlecode.com/svn/branches/bleeding_edge/dart