| OLD | NEW |
| 1 // Copyright (c) 2014, the Dart project authors. Please see the AUTHORS file | 1 // Copyright (c) 2014, the Dart project authors. Please see the AUTHORS file |
| 2 // for details. All rights reserved. Use of this source code is governed by a | 2 // for details. All rights reserved. Use of this source code is governed by a |
| 3 // BSD-style license that can be found in the LICENSE file. | 3 // BSD-style license that can be found in the LICENSE file. |
| 4 | 4 |
| 5 library dart2js.cps_ir.shrinking_reductions; | 5 library dart2js.cps_ir.shrinking_reductions; |
| 6 | 6 |
| 7 import 'cps_ir_nodes.dart'; | 7 import 'cps_ir_nodes.dart'; |
| 8 import 'optimizers.dart'; | 8 import 'optimizers.dart'; |
| 9 | 9 |
| 10 /** | 10 /** |
| (...skipping 185 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 196 InvokeContinuation invoke = cont.firstRef.parent; | 196 InvokeContinuation invoke = cont.firstRef.parent; |
| 197 InteriorNode invokeParent = invoke.parent; | 197 InteriorNode invokeParent = invoke.parent; |
| 198 Expression body = cont.body; | 198 Expression body = cont.body; |
| 199 | 199 |
| 200 // Replace the invocation with the continuation body. | 200 // Replace the invocation with the continuation body. |
| 201 invokeParent.body = body; | 201 invokeParent.body = body; |
| 202 body.parent = invokeParent; | 202 body.parent = invokeParent; |
| 203 cont.body = null; | 203 cont.body = null; |
| 204 | 204 |
| 205 // Substitute the invocation argument for the continuation parameter. | 205 // Substitute the invocation argument for the continuation parameter. |
| 206 for (int i = 0; i < invoke.arguments.length; i++) { | 206 for (int i = 0; i < invoke.argumentRefs.length; i++) { |
| 207 Parameter param = cont.parameters[i]; | 207 Parameter param = cont.parameters[i]; |
| 208 Primitive argument = invoke.arguments[i].definition; | 208 Primitive argument = invoke.argument(i); |
| 209 param.replaceUsesWith(argument); | 209 param.replaceUsesWith(argument); |
| 210 argument.useElementAsHint(param.hint); | 210 argument.useElementAsHint(param.hint); |
| 211 _checkConstantBranchCondition(argument); | 211 _checkConstantBranchCondition(argument); |
| 212 } | 212 } |
| 213 | 213 |
| 214 // Remove the continuation after inlining it so we can check for eta redexes | 214 // Remove the continuation after inlining it so we can check for eta redexes |
| 215 // which may arise after removing the LetCont. | 215 // which may arise after removing the LetCont. |
| 216 _removeContinuation(cont); | 216 _removeContinuation(cont); |
| 217 | 217 |
| 218 // Perform bookkeeping on substituted body and scan for new redexes. | 218 // Perform bookkeeping on substituted body and scan for new redexes. |
| (...skipping 17 matching lines...) Expand all Loading... |
| 236 // letcont k1 x1 = k0 x1 in E1 | 236 // letcont k1 x1 = k0 x1 in E1 |
| 237 if (!_isEtaCont(task.node)) { | 237 if (!_isEtaCont(task.node)) { |
| 238 return; | 238 return; |
| 239 } | 239 } |
| 240 | 240 |
| 241 // Remove the continuation. | 241 // Remove the continuation. |
| 242 Continuation cont = task.node; | 242 Continuation cont = task.node; |
| 243 _removeContinuation(cont); | 243 _removeContinuation(cont); |
| 244 | 244 |
| 245 InvokeContinuation invoke = cont.body; | 245 InvokeContinuation invoke = cont.body; |
| 246 Continuation wrappedCont = invoke.continuation.definition; | 246 Continuation wrappedCont = invoke.continuation; |
| 247 | 247 |
| 248 for (int i = 0; i < cont.parameters.length; ++i) { | 248 for (int i = 0; i < cont.parameters.length; ++i) { |
| 249 wrappedCont.parameters[i].useElementAsHint(cont.parameters[i].hint); | 249 wrappedCont.parameters[i].useElementAsHint(cont.parameters[i].hint); |
| 250 } | 250 } |
| 251 | 251 |
| 252 // If the invocation of wrappedCont is escaping, then all invocations of | 252 // If the invocation of wrappedCont is escaping, then all invocations of |
| 253 // cont will be as well, after the reduction. | 253 // cont will be as well, after the reduction. |
| 254 if (invoke.isEscapingTry) { | 254 if (invoke.isEscapingTry) { |
| 255 Reference current = cont.firstRef; | 255 Reference current = cont.firstRef; |
| 256 while (current != null) { | 256 while (current != null) { |
| (...skipping 16 matching lines...) Expand all Loading... |
| 273 // Perform bookkeeping on removed body and scan for new redexes. | 273 // Perform bookkeeping on removed body and scan for new redexes. |
| 274 new _RemovalVisitor(_worklist).visit(cont); | 274 new _RemovalVisitor(_worklist).visit(cont); |
| 275 } | 275 } |
| 276 | 276 |
| 277 void _reduceBranch(_ReductionTask task) { | 277 void _reduceBranch(_ReductionTask task) { |
| 278 Branch branch = task.node; | 278 Branch branch = task.node; |
| 279 // Replace Branch with InvokeContinuation of one of the targets. When the | 279 // Replace Branch with InvokeContinuation of one of the targets. When the |
| 280 // branch is deleted the other target becomes unreferenced and the chosen | 280 // branch is deleted the other target becomes unreferenced and the chosen |
| 281 // target becomes available for eta-cont and further reductions. | 281 // target becomes available for eta-cont and further reductions. |
| 282 Continuation target; | 282 Continuation target; |
| 283 Primitive condition = branch.condition.definition; | 283 Primitive condition = branch.condition; |
| 284 if (condition is Constant) { | 284 if (condition is Constant) { |
| 285 target = isTruthyConstant(condition.value, strict: branch.isStrictCheck) | 285 target = isTruthyConstant(condition.value, strict: branch.isStrictCheck) |
| 286 ? branch.trueContinuation.definition | 286 ? branch.trueContinuation |
| 287 : branch.falseContinuation.definition; | 287 : branch.falseContinuation; |
| 288 } else if (_isBranchTargetOfUselessIf(branch.trueContinuation.definition)) { | 288 } else if (_isBranchTargetOfUselessIf(branch.trueContinuation)) { |
| 289 target = branch.trueContinuation.definition; | 289 target = branch.trueContinuation; |
| 290 } else { | 290 } else { |
| 291 return; | 291 return; |
| 292 } | 292 } |
| 293 | 293 |
| 294 InvokeContinuation invoke = new InvokeContinuation( | 294 InvokeContinuation invoke = new InvokeContinuation( |
| 295 target, <Primitive>[] | 295 target, <Primitive>[] |
| 296 // TODO(sra): Add sourceInformation. | 296 // TODO(sra): Add sourceInformation. |
| 297 /*, sourceInformation: branch.sourceInformation*/); | 297 /*, sourceInformation: branch.sourceInformation*/); |
| 298 branch.parent.body = invoke; | 298 branch.parent.body = invoke; |
| 299 invoke.parent = branch.parent; | 299 invoke.parent = branch.parent; |
| (...skipping 24 matching lines...) Expand all Loading... |
| 324 | 324 |
| 325 Continuation continuation = parameter.parent; | 325 Continuation continuation = parameter.parent; |
| 326 int index = continuation.parameters.indexOf(parameter); | 326 int index = continuation.parameters.indexOf(parameter); |
| 327 assert(index != -1); | 327 assert(index != -1); |
| 328 continuation.parameters.removeAt(index); | 328 continuation.parameters.removeAt(index); |
| 329 parameter.parent = null; // Mark as removed. | 329 parameter.parent = null; // Mark as removed. |
| 330 | 330 |
| 331 // Remove the index'th argument from each invocation. | 331 // Remove the index'th argument from each invocation. |
| 332 for (Reference ref = continuation.firstRef; ref != null; ref = ref.next) { | 332 for (Reference ref = continuation.firstRef; ref != null; ref = ref.next) { |
| 333 InvokeContinuation invoke = ref.parent; | 333 InvokeContinuation invoke = ref.parent; |
| 334 Reference<Primitive> argument = invoke.arguments[index]; | 334 Reference<Primitive> argument = invoke.argumentRefs[index]; |
| 335 argument.unlink(); | 335 argument.unlink(); |
| 336 invoke.arguments.removeAt(index); | 336 invoke.argumentRefs.removeAt(index); |
| 337 // Removing an argument can create a dead primitive or an eta-redex | 337 // Removing an argument can create a dead primitive or an eta-redex |
| 338 // in case the parent is a continuation that now has matching parameters. | 338 // in case the parent is a continuation that now has matching parameters. |
| 339 _checkDeadPrimitive(argument.definition); | 339 _checkDeadPrimitive(argument.definition); |
| 340 if (invoke.parent is Continuation) { | 340 if (invoke.parent is Continuation) { |
| 341 _checkEtaCont(invoke.parent); | 341 _checkEtaCont(invoke.parent); |
| 342 _checkUselessBranchTarget(invoke.parent); | 342 _checkUselessBranchTarget(invoke.parent); |
| 343 } | 343 } |
| 344 } | 344 } |
| 345 | 345 |
| 346 // Removing an unused parameter can create an eta-redex, in case the | 346 // Removing an unused parameter can create an eta-redex, in case the |
| (...skipping 95 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 442 /// Returns true iff the continuation consists of a continuation | 442 /// Returns true iff the continuation consists of a continuation |
| 443 /// invocation, passing on all parameters. Special cases exist (see below). | 443 /// invocation, passing on all parameters. Special cases exist (see below). |
| 444 bool _isEtaCont(Continuation cont) { | 444 bool _isEtaCont(Continuation cont) { |
| 445 if (_isRemoved(cont)) return false; | 445 if (_isRemoved(cont)) return false; |
| 446 | 446 |
| 447 if (!cont.isJoinContinuation || cont.body is! InvokeContinuation) { | 447 if (!cont.isJoinContinuation || cont.body is! InvokeContinuation) { |
| 448 return false; | 448 return false; |
| 449 } | 449 } |
| 450 | 450 |
| 451 InvokeContinuation invoke = cont.body; | 451 InvokeContinuation invoke = cont.body; |
| 452 Continuation invokedCont = invoke.continuation.definition; | 452 Continuation invokedCont = invoke.continuation; |
| 453 | 453 |
| 454 // Do not eta-reduce return join-points since the direct-style code is worse | 454 // Do not eta-reduce return join-points since the direct-style code is worse |
| 455 // in the common case (i.e. returns are moved inside `if` branches). | 455 // in the common case (i.e. returns are moved inside `if` branches). |
| 456 if (invokedCont.isReturnContinuation) { | 456 if (invokedCont.isReturnContinuation) { |
| 457 return false; | 457 return false; |
| 458 } | 458 } |
| 459 | 459 |
| 460 // Translation to direct style generates different statements for recursive | 460 // Translation to direct style generates different statements for recursive |
| 461 // and non-recursive invokes. It should still be possible to apply eta-cont if | 461 // and non-recursive invokes. It should still be possible to apply eta-cont if |
| 462 // this is not a self-invocation. | 462 // this is not a self-invocation. |
| (...skipping 17 matching lines...) Expand all Loading... |
| 480 // | 480 // |
| 481 // let cont k1(x1) = k0(x0, x1) in E -eta-> E' | 481 // let cont k1(x1) = k0(x0, x1) in E -eta-> E' |
| 482 // where E' has k0(x0, v) substituted for each k1(v). | 482 // where E' has k0(x0, v) substituted for each k1(v). |
| 483 // | 483 // |
| 484 // HOWEVER, adding continuation parameters is unlikely to be an optimization | 484 // HOWEVER, adding continuation parameters is unlikely to be an optimization |
| 485 // since it duplicates assignments used in direct-style to implement parameter | 485 // since it duplicates assignments used in direct-style to implement parameter |
| 486 // passing. | 486 // passing. |
| 487 // | 487 // |
| 488 // TODO(kmillikin): find real occurrences of these patterns, and see if they | 488 // TODO(kmillikin): find real occurrences of these patterns, and see if they |
| 489 // can be optimized. | 489 // can be optimized. |
| 490 if (cont.parameters.length != invoke.arguments.length) { | 490 if (cont.parameters.length != invoke.argumentRefs.length) { |
| 491 return false; | 491 return false; |
| 492 } | 492 } |
| 493 | 493 |
| 494 // TODO(jgruber): Linear in the parameter count. Can be improved to near | 494 // TODO(jgruber): Linear in the parameter count. Can be improved to near |
| 495 // constant time by using union-find data structure. | 495 // constant time by using union-find data structure. |
| 496 for (int i = 0; i < cont.parameters.length; i++) { | 496 for (int i = 0; i < cont.parameters.length; i++) { |
| 497 if (invoke.arguments[i].definition != cont.parameters[i]) { | 497 if (invoke.argument(i) != cont.parameters[i]) { |
| 498 return false; | 498 return false; |
| 499 } | 499 } |
| 500 } | 500 } |
| 501 | 501 |
| 502 return true; | 502 return true; |
| 503 } | 503 } |
| 504 | 504 |
| 505 Expression _unfoldDeadRefinements(Expression node) { | 505 Expression _unfoldDeadRefinements(Expression node) { |
| 506 while (node is LetPrim) { | 506 while (node is LetPrim) { |
| 507 LetPrim let = node; | 507 LetPrim let = node; |
| 508 Primitive prim = let.primitive; | 508 Primitive prim = let.primitive; |
| 509 if (prim.hasAtLeastOneUse || prim is! Refinement) return node; | 509 if (prim.hasAtLeastOneUse || prim is! Refinement) return node; |
| 510 node = node.next; | 510 node = node.next; |
| 511 } | 511 } |
| 512 return node; | 512 return node; |
| 513 } | 513 } |
| 514 | 514 |
| 515 bool _isBranchRedex(Branch branch) { | 515 bool _isBranchRedex(Branch branch) { |
| 516 return _isUselessIf(branch) || branch.condition.definition is Constant; | 516 return _isUselessIf(branch) || branch.condition is Constant; |
| 517 } | 517 } |
| 518 | 518 |
| 519 bool _isBranchTargetOfUselessIf(Continuation cont) { | 519 bool _isBranchTargetOfUselessIf(Continuation cont) { |
| 520 // A useless-if has an empty then and else branch, e.g. `if (cond);`. | 520 // A useless-if has an empty then and else branch, e.g. `if (cond);`. |
| 521 // | 521 // |
| 522 // Detect T or F in | 522 // Detect T or F in |
| 523 // | 523 // |
| 524 // let cont Join() = ... | 524 // let cont Join() = ... |
| 525 // in let cont T() = Join() | 525 // in let cont T() = Join() |
| 526 // F() = Join() | 526 // F() = Join() |
| 527 // in branch condition T F | 527 // in branch condition T F |
| 528 // | 528 // |
| 529 if (!cont.hasExactlyOneUse) return false; | 529 if (!cont.hasExactlyOneUse) return false; |
| 530 Node use = cont.firstRef.parent; | 530 Node use = cont.firstRef.parent; |
| 531 if (use is! Branch) return false; | 531 if (use is! Branch) return false; |
| 532 return _isUselessIf(use); | 532 return _isUselessIf(use); |
| 533 } | 533 } |
| 534 | 534 |
| 535 bool _isUselessIf(Branch branch) { | 535 bool _isUselessIf(Branch branch) { |
| 536 Continuation trueCont = branch.trueContinuation.definition; | 536 Continuation trueCont = branch.trueContinuation; |
| 537 Expression trueBody = _unfoldDeadRefinements(trueCont.body); | 537 Expression trueBody = _unfoldDeadRefinements(trueCont.body); |
| 538 if (trueBody is! InvokeContinuation) return false; | 538 if (trueBody is! InvokeContinuation) return false; |
| 539 Continuation falseCont = branch.falseContinuation.definition; | 539 Continuation falseCont = branch.falseContinuation; |
| 540 Expression falseBody = _unfoldDeadRefinements(falseCont.body); | 540 Expression falseBody = _unfoldDeadRefinements(falseCont.body); |
| 541 if (falseBody is! InvokeContinuation) return false; | 541 if (falseBody is! InvokeContinuation) return false; |
| 542 InvokeContinuation trueInvoke = trueBody; | 542 InvokeContinuation trueInvoke = trueBody; |
| 543 InvokeContinuation falseInvoke = falseBody; | 543 InvokeContinuation falseInvoke = falseBody; |
| 544 if (trueInvoke.continuation.definition != | 544 if (trueInvoke.continuation != |
| 545 falseInvoke.continuation.definition) { | 545 falseInvoke.continuation) { |
| 546 return false; | 546 return false; |
| 547 } | 547 } |
| 548 // Matching zero arguments should be adequate, since isomorphic true and false | 548 // Matching zero arguments should be adequate, since isomorphic true and false |
| 549 // invocations should result in redundant phis which are removed elsewhere. | 549 // invocations should result in redundant phis which are removed elsewhere. |
| 550 // | 550 // |
| 551 // Note that the argument lists are not necessarily the same length here, | 551 // Note that the argument lists are not necessarily the same length here, |
| 552 // because we could be looking for new redexes in the middle of performing a | 552 // because we could be looking for new redexes in the middle of performing a |
| 553 // dead parameter reduction, where some but not all of the invocations have | 553 // dead parameter reduction, where some but not all of the invocations have |
| 554 // been rewritten. In that case, we will find the redex (once) after both | 554 // been rewritten. In that case, we will find the redex (once) after both |
| 555 // of these invocations have been rewritten. | 555 // of these invocations have been rewritten. |
| 556 return trueInvoke.arguments.isEmpty && falseInvoke.arguments.isEmpty; | 556 return trueInvoke.argumentRefs.isEmpty && falseInvoke.argumentRefs.isEmpty; |
| 557 } | 557 } |
| 558 | 558 |
| 559 bool _isDeadParameter(Parameter parameter) { | 559 bool _isDeadParameter(Parameter parameter) { |
| 560 if (_isParameterRemoved(parameter)) return false; | 560 if (_isParameterRemoved(parameter)) return false; |
| 561 | 561 |
| 562 // We cannot remove function parameters as an intraprocedural optimization. | 562 // We cannot remove function parameters as an intraprocedural optimization. |
| 563 if (parameter.parent is! Continuation || parameter.hasAtLeastOneUse) { | 563 if (parameter.parent is! Continuation || parameter.hasAtLeastOneUse) { |
| 564 return false; | 564 return false; |
| 565 } | 565 } |
| 566 | 566 |
| (...skipping 139 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 706 assert(node is Continuation || node is LetPrim || node is Parameter || | 706 assert(node is Continuation || node is LetPrim || node is Parameter || |
| 707 node is Branch); | 707 node is Branch); |
| 708 } | 708 } |
| 709 | 709 |
| 710 bool operator==(_ReductionTask that) { | 710 bool operator==(_ReductionTask that) { |
| 711 return (that.kind == this.kind && that.node == this.node); | 711 return (that.kind == this.kind && that.node == this.node); |
| 712 } | 712 } |
| 713 | 713 |
| 714 String toString() => "$kind: $node"; | 714 String toString() => "$kind: $node"; |
| 715 } | 715 } |
| OLD | NEW |