Chromium Code Reviews
chromiumcodereview-hr@appspot.gserviceaccount.com (chromiumcodereview-hr) | Please choose your nickname with Settings | Help | Chromium Project | Gerrit Changes | Sign out
(67)

Side by Side Diff: pkg/compiler/lib/src/cps_ir/shrinking_reductions.dart

Issue 1743283002: dart2js cps: Use definitions by default, not references. (Closed) Base URL: git@github.com:dart-lang/sdk.git@master
Patch Set: Fix long lines and use helpers that we already have Created 4 years, 9 months ago
Use n/p to move between diff chunks; N/P to move between comments. Draft comments are only viewable by you.
Jump to:
View unified diff | Download patch
OLDNEW
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
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
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
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
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
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
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
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 }
OLDNEW

Powered by Google App Engine
This is Rietveld 408576698