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 |