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

Side by Side Diff: pkg/compiler/lib/src/cps_ir/bounds_checker.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) 2015, the Dart project authors. Please see the AUTHORS file 1 // Copyright (c) 2015, 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.bounds_checker; 5 library dart2js.cps_ir.bounds_checker;
6 6
7 import 'cps_ir_nodes.dart'; 7 import 'cps_ir_nodes.dart';
8 import 'optimizers.dart' show Pass; 8 import 'optimizers.dart' show Pass;
9 import 'octagon.dart'; 9 import 'octagon.dart';
10 import '../constants/values.dart'; 10 import '../constants/values.dart';
(...skipping 251 matching lines...) Expand 10 before | Expand all | Expand 10 after
262 262
263 bool isDefinitelyGreaterThanOrEqualToConstant(SignedVariable v1, int value) { 263 bool isDefinitelyGreaterThanOrEqualToConstant(SignedVariable v1, int value) {
264 // v1 >= value <==> -v1 - v1 <= -2 * value 264 // v1 >= value <==> -v1 - v1 <= -2 * value
265 return testConstraint(v1.negated, v1.negated, -2 * value); 265 return testConstraint(v1.negated, v1.negated, -2 * value);
266 } 266 }
267 267
268 // ------------- TAIL EXPRESSIONS ----------------- 268 // ------------- TAIL EXPRESSIONS -----------------
269 269
270 @override 270 @override
271 void visitBranch(Branch node) { 271 void visitBranch(Branch node) {
272 Primitive condition = node.condition.definition; 272 Primitive condition = node.condition;
273 Continuation trueCont = node.trueContinuation.definition; 273 Continuation trueCont = node.trueContinuation;
274 Continuation falseCont = node.falseContinuation.definition; 274 Continuation falseCont = node.falseContinuation;
275 effectNumberAt[trueCont] = currentEffectNumber; 275 effectNumberAt[trueCont] = currentEffectNumber;
276 effectNumberAt[falseCont] = currentEffectNumber; 276 effectNumberAt[falseCont] = currentEffectNumber;
277 pushAction(() { 277 pushAction(() {
278 // If the branching condition is known statically, either or both of the 278 // If the branching condition is known statically, either or both of the
279 // branch continuations will be replaced by Unreachable. Clean up the 279 // branch continuations will be replaced by Unreachable. Clean up the
280 // branch afterwards. 280 // branch afterwards.
281 if (trueCont.body is Unreachable && falseCont.body is Unreachable) { 281 if (trueCont.body is Unreachable && falseCont.body is Unreachable) {
282 destroyAndReplace(node, new Unreachable()); 282 destroyAndReplace(node, new Unreachable());
283 } else if (trueCont.body is Unreachable) { 283 } else if (trueCont.body is Unreachable) {
284 destroyAndReplace( 284 destroyAndReplace(
285 node, new InvokeContinuation(falseCont, <Parameter>[])); 285 node, new InvokeContinuation(falseCont, <Parameter>[]));
286 } else if (falseCont.body is Unreachable) { 286 } else if (falseCont.body is Unreachable) {
287 destroyAndReplace( 287 destroyAndReplace(
288 node, new InvokeContinuation(trueCont, <Parameter>[])); 288 node, new InvokeContinuation(trueCont, <Parameter>[]));
289 } 289 }
290 }); 290 });
291 void pushTrue(makeConstraint()) { 291 void pushTrue(makeConstraint()) {
292 pushAction(() { 292 pushAction(() {
293 makeConstraint(); 293 makeConstraint();
294 push(trueCont); 294 push(trueCont);
295 }); 295 });
296 } 296 }
297 void pushFalse(makeConstraint()) { 297 void pushFalse(makeConstraint()) {
298 pushAction(() { 298 pushAction(() {
299 makeConstraint(); 299 makeConstraint();
300 push(falseCont); 300 push(falseCont);
301 }); 301 });
302 } 302 }
303 if (condition is ApplyBuiltinOperator && 303 if (condition is ApplyBuiltinOperator &&
304 condition.arguments.length == 2 && 304 condition.argumentRefs.length == 2 &&
305 isInt(condition.arguments[0].definition) && 305 isInt(condition.argument(0)) &&
306 isInt(condition.arguments[1].definition)) { 306 isInt(condition.argument(1))) {
307 SignedVariable v1 = getValue(condition.arguments[0].definition); 307 SignedVariable v1 = getValue(condition.argument(0));
308 SignedVariable v2 = getValue(condition.arguments[1].definition); 308 SignedVariable v2 = getValue(condition.argument(1));
309 switch (condition.operator) { 309 switch (condition.operator) {
310 case BuiltinOperator.NumLe: 310 case BuiltinOperator.NumLe:
311 pushTrue(() => makeLessThanOrEqual(v1, v2)); 311 pushTrue(() => makeLessThanOrEqual(v1, v2));
312 pushFalse(() => makeGreaterThan(v1, v2)); 312 pushFalse(() => makeGreaterThan(v1, v2));
313 return; 313 return;
314 case BuiltinOperator.NumLt: 314 case BuiltinOperator.NumLt:
315 pushTrue(() => makeLessThan(v1, v2)); 315 pushTrue(() => makeLessThan(v1, v2));
316 pushFalse(() => makeGreaterThanOrEqual(v1, v2)); 316 pushFalse(() => makeGreaterThanOrEqual(v1, v2));
317 return; 317 return;
318 case BuiltinOperator.NumGe: 318 case BuiltinOperator.NumGe:
(...skipping 26 matching lines...) Expand all
345 // constraints that reference it. 345 // constraints that reference it.
346 if (node.value.isInt) { 346 if (node.value.isInt) {
347 IntConstantValue constant = node.value; 347 IntConstantValue constant = node.value;
348 makeConstant(getValue(node), constant.primitiveValue); 348 makeConstant(getValue(node), constant.primitiveValue);
349 } 349 }
350 } 350 }
351 351
352 @override 352 @override
353 void visitApplyBuiltinOperator(ApplyBuiltinOperator node) { 353 void visitApplyBuiltinOperator(ApplyBuiltinOperator node) {
354 if (!isInt(node)) return; 354 if (!isInt(node)) return;
355 if (node.arguments.length == 1) { 355 if (node.argumentRefs.length == 1) {
356 applyUnaryOperator(node); 356 applyUnaryOperator(node);
357 } else if (node.arguments.length == 2) { 357 } else if (node.argumentRefs.length == 2) {
358 applyBinaryOperator(node); 358 applyBinaryOperator(node);
359 } 359 }
360 } 360 }
361 361
362 void applyBinaryOperator(ApplyBuiltinOperator node) { 362 void applyBinaryOperator(ApplyBuiltinOperator node) {
363 Primitive left = node.arguments[0].definition; 363 Primitive left = node.argument(0);
364 Primitive right = node.arguments[1].definition; 364 Primitive right = node.argument(1);
365 if (!isInt(left) || !isInt(right)) { 365 if (!isInt(left) || !isInt(right)) {
366 return; 366 return;
367 } 367 }
368 SignedVariable leftVar = getValue(left); 368 SignedVariable leftVar = getValue(left);
369 SignedVariable rightVar = getValue(right); 369 SignedVariable rightVar = getValue(right);
370 SignedVariable result = getValue(node); 370 SignedVariable result = getValue(node);
371 switch (node.operator) { 371 switch (node.operator) {
372 case BuiltinOperator.NumAdd: 372 case BuiltinOperator.NumAdd:
373 int leftConst = getIntConstant(left); 373 int leftConst = getIntConstant(left);
374 if (leftConst != null) { 374 if (leftConst != null) {
(...skipping 80 matching lines...) Expand 10 before | Expand all | Expand 10 after
455 if (isUInt32(right)) { 455 if (isUInt32(right)) {
456 makeLessThanOrEqual(result, rightVar); 456 makeLessThanOrEqual(result, rightVar);
457 } 457 }
458 break; 458 break;
459 459
460 default: 460 default:
461 } 461 }
462 } 462 }
463 463
464 void applyUnaryOperator(ApplyBuiltinOperator node) { 464 void applyUnaryOperator(ApplyBuiltinOperator node) {
465 Primitive argument = node.arguments[0].definition; 465 Primitive argument = node.argument(0);
466 if (!isInt(argument)) return; 466 if (!isInt(argument)) return;
467 if (node.operator == BuiltinOperator.NumNegate) { 467 if (node.operator == BuiltinOperator.NumNegate) {
468 valueOf[node] = getValue(argument).negated; 468 valueOf[node] = getValue(argument).negated;
469 } 469 }
470 } 470 }
471 471
472 int getIntConstant(Primitive prim) { 472 int getIntConstant(Primitive prim) {
473 if (prim is Constant && prim.value.isInt) { 473 if (prim is Constant && prim.value.isInt) {
474 IntConstantValue constant = prim.value; 474 IntConstantValue constant = prim.value;
475 return constant.primitiveValue; 475 return constant.primitiveValue;
476 } 476 }
477 return null; 477 return null;
478 } 478 }
479 479
480 @override 480 @override
481 void visitRefinement(Refinement node) { 481 void visitRefinement(Refinement node) {
482 // In general we should get the container length of the refined type and 482 // In general we should get the container length of the refined type and
483 // add a constraint if we know the length after the refinement. 483 // add a constraint if we know the length after the refinement.
484 // However, our current type system removes container information when a 484 // However, our current type system removes container information when a
485 // type becomes part of a union, so this cannot happen. 485 // type becomes part of a union, so this cannot happen.
486 } 486 }
487 487
488 @override 488 @override
489 void visitGetLength(GetLength node) { 489 void visitGetLength(GetLength node) {
490 valueOf[node] = getLength(node.object.definition, currentEffectNumber); 490 valueOf[node] = getLength(node.object, currentEffectNumber);
491 } 491 }
492 492
493 @override 493 @override
494 void visitBoundsCheck(BoundsCheck node) { 494 void visitBoundsCheck(BoundsCheck node) {
495 if (node.checks == BoundsCheck.NONE) return; 495 if (node.checks == BoundsCheck.NONE) return;
496 assert(node.index != null); // Because there is at least one check. 496 assert(node.indexRef != null); // Because there is at least one check.
497 SignedVariable length = node.length == null 497 SignedVariable length = node.lengthRef == null
498 ? null 498 ? null
499 : getValue(node.length.definition); 499 : getValue(node.length);
500 SignedVariable index = getValue(node.index.definition); 500 SignedVariable index = getValue(node.index);
501 if (node.hasUpperBoundCheck) { 501 if (node.hasUpperBoundCheck) {
502 if (isDefinitelyLessThan(index, length)) { 502 if (isDefinitelyLessThan(index, length)) {
503 node.checks &= ~BoundsCheck.UPPER_BOUND; 503 node.checks &= ~BoundsCheck.UPPER_BOUND;
504 } else { 504 } else {
505 makeLessThan(index, length); 505 makeLessThan(index, length);
506 } 506 }
507 } 507 }
508 if (node.hasLowerBoundCheck) { 508 if (node.hasLowerBoundCheck) {
509 if (isDefinitelyGreaterThanOrEqualToConstant(index, 0)) { 509 if (isDefinitelyGreaterThanOrEqualToConstant(index, 0)) {
510 node.checks &= ~BoundsCheck.LOWER_BOUND; 510 node.checks &= ~BoundsCheck.LOWER_BOUND;
511 } else { 511 } else {
512 makeGreaterThanOrEqualToConstant(index, 0); 512 makeGreaterThanOrEqualToConstant(index, 0);
513 } 513 }
514 } 514 }
515 if (node.hasEmptinessCheck) { 515 if (node.hasEmptinessCheck) {
516 if (isDefinitelyGreaterThanOrEqualToConstant(length, 1)) { 516 if (isDefinitelyGreaterThanOrEqualToConstant(length, 1)) {
517 node.checks &= ~BoundsCheck.EMPTINESS; 517 node.checks &= ~BoundsCheck.EMPTINESS;
518 } else { 518 } else {
519 makeGreaterThanOrEqualToConstant(length, 1); 519 makeGreaterThanOrEqualToConstant(length, 1);
520 } 520 }
521 } 521 }
522 if (!node.lengthUsedInCheck && node.length != null) { 522 if (!node.lengthUsedInCheck && node.lengthRef != null) {
523 node..length.unlink()..length = null; 523 node..lengthRef.unlink()..lengthRef = null;
524 } 524 }
525 if (node.checks == BoundsCheck.NONE) { 525 if (node.checks == BoundsCheck.NONE) {
526 // We can't remove the bounds check node because it may still be used to 526 // We can't remove the bounds check node because it may still be used to
527 // restrict code motion. But the index is no longer needed. 527 // restrict code motion. But the index is no longer needed.
528 node..index.unlink()..index = null; 528 node..indexRef.unlink()..indexRef = null;
529 } 529 }
530 } 530 }
531 531
532 void analyzeLoopEntry(InvokeContinuation node) { 532 void analyzeLoopEntry(InvokeContinuation node) {
533 foundLoop = true; 533 foundLoop = true;
534 Continuation cont = node.continuation.definition; 534 Continuation cont = node.continuation;
535 if (isStrongLoopPass) { 535 if (isStrongLoopPass) {
536 for (int i = 0; i < node.arguments.length; ++i) { 536 for (int i = 0; i < node.argumentRefs.length; ++i) {
537 Parameter param = cont.parameters[i]; 537 Parameter param = cont.parameters[i];
538 if (!isInt(param)) continue; 538 if (!isInt(param)) continue;
539 Primitive initialValue = node.arguments[i].definition; 539 Primitive initialValue = node.argument(i);
540 SignedVariable initialVariable = getValue(initialValue); 540 SignedVariable initialVariable = getValue(initialValue);
541 Monotonicity mono = monotonicity[param]; 541 Monotonicity mono = monotonicity[param];
542 if (mono == null) { 542 if (mono == null) {
543 // Value never changes. This is extremely uncommon. 543 // Value never changes. This is extremely uncommon.
544 param.replaceUsesWith(initialValue); 544 param.replaceUsesWith(initialValue);
545 } else if (mono == Monotonicity.Increasing) { 545 } else if (mono == Monotonicity.Increasing) {
546 makeGreaterThanOrEqual(getValue(param), initialVariable); 546 makeGreaterThanOrEqual(getValue(param), initialVariable);
547 } else if (mono == Monotonicity.Decreasing) { 547 } else if (mono == Monotonicity.Decreasing) {
548 makeLessThanOrEqual(getValue(param), initialVariable); 548 makeLessThanOrEqual(getValue(param), initialVariable);
549 } 549 }
550 } 550 }
551 } 551 }
552 if (loopEffects.changesIndexableLength(cont)) { 552 if (loopEffects.changesIndexableLength(cont)) {
553 currentEffectNumber = effectNumberAt[cont] = makeNewEffect(); 553 currentEffectNumber = effectNumberAt[cont] = makeNewEffect();
554 } 554 }
555 push(cont); 555 push(cont);
556 } 556 }
557 557
558 void analyzeLoopContinue(InvokeContinuation node) { 558 void analyzeLoopContinue(InvokeContinuation node) {
559 Continuation cont = node.continuation.definition; 559 Continuation cont = node.continuation;
560 560
561 // During the strong loop phase, there is no need to compute monotonicity, 561 // During the strong loop phase, there is no need to compute monotonicity,
562 // and we already put bounds on the loop variables when we went into the 562 // and we already put bounds on the loop variables when we went into the
563 // loop. 563 // loop.
564 if (isStrongLoopPass) return; 564 if (isStrongLoopPass) return;
565 565
566 // For each loop parameter, try to prove that the new value is definitely 566 // For each loop parameter, try to prove that the new value is definitely
567 // less/greater than its old value. When we fail to prove this, update the 567 // less/greater than its old value. When we fail to prove this, update the
568 // monotonicity flag accordingly. 568 // monotonicity flag accordingly.
569 for (int i = 0; i < node.arguments.length; ++i) { 569 for (int i = 0; i < node.argumentRefs.length; ++i) {
570 Parameter param = cont.parameters[i]; 570 Parameter param = cont.parameters[i];
571 if (!isInt(param)) continue; 571 if (!isInt(param)) continue;
572 SignedVariable arg = getValue(node.arguments[i].definition); 572 SignedVariable arg = getValue(node.argument(i));
573 SignedVariable paramVar = getValue(param); 573 SignedVariable paramVar = getValue(param);
574 if (!isDefinitelyLessThanOrEqualTo(arg, paramVar)) { 574 if (!isDefinitelyLessThanOrEqualTo(arg, paramVar)) {
575 // We couldn't prove that the value does not increase, so assume 575 // We couldn't prove that the value does not increase, so assume
576 // henceforth that it might be increasing. 576 // henceforth that it might be increasing.
577 markMonotonicity(cont.parameters[i], Monotonicity.Increasing); 577 markMonotonicity(cont.parameters[i], Monotonicity.Increasing);
578 } 578 }
579 if (!isDefinitelyGreaterThanOrEqualTo(arg, paramVar)) { 579 if (!isDefinitelyGreaterThanOrEqualTo(arg, paramVar)) {
580 // We couldn't prove that the value does not decrease, so assume 580 // We couldn't prove that the value does not decrease, so assume
581 // henceforth that it might be decreasing. 581 // henceforth that it might be decreasing.
582 markMonotonicity(cont.parameters[i], Monotonicity.Decreasing); 582 markMonotonicity(cont.parameters[i], Monotonicity.Decreasing);
583 } 583 }
584 } 584 }
585 } 585 }
586 586
587 void markMonotonicity(Parameter param, Monotonicity mono) { 587 void markMonotonicity(Parameter param, Monotonicity mono) {
588 Monotonicity current = monotonicity[param]; 588 Monotonicity current = monotonicity[param];
589 if (current == null) { 589 if (current == null) {
590 monotonicity[param] = mono; 590 monotonicity[param] = mono;
591 } else if (current != mono) { 591 } else if (current != mono) {
592 monotonicity[param] = Monotonicity.NotMonotone; 592 monotonicity[param] = Monotonicity.NotMonotone;
593 } 593 }
594 } 594 }
595 595
596 @override 596 @override
597 void visitInvokeContinuation(InvokeContinuation node) { 597 void visitInvokeContinuation(InvokeContinuation node) {
598 Continuation cont = node.continuation.definition; 598 Continuation cont = node.continuation;
599 if (node.isRecursive) { 599 if (node.isRecursive) {
600 analyzeLoopContinue(node); 600 analyzeLoopContinue(node);
601 } else if (cont.isRecursive) { 601 } else if (cont.isRecursive) {
602 analyzeLoopEntry(node); 602 analyzeLoopEntry(node);
603 } else { 603 } else {
604 int effect = effectNumberAt[cont]; 604 int effect = effectNumberAt[cont];
605 if (effect == null) { 605 if (effect == null) {
606 effectNumberAt[cont] = currentEffectNumber; 606 effectNumberAt[cont] = currentEffectNumber;
607 } else if (effect != currentEffectNumber && effect != NEW_EFFECT) { 607 } else if (effect != currentEffectNumber && effect != NEW_EFFECT) {
608 effectNumberAt[cont] = NEW_EFFECT; 608 effectNumberAt[cont] = NEW_EFFECT;
(...skipping 25 matching lines...) Expand all
634 TypeMask successType = 634 TypeMask successType =
635 types.receiverTypeFor(node.selector, node.dartReceiver.type); 635 types.receiverTypeFor(node.selector, node.dartReceiver.type);
636 if (types.isDefinitelyIndexable(successType)) { 636 if (types.isDefinitelyIndexable(successType)) {
637 valueOf[node] = getLength(node.dartReceiver, currentEffectNumber); 637 valueOf[node] = getLength(node.dartReceiver, currentEffectNumber);
638 } 638 }
639 } 639 }
640 } 640 }
641 641
642 @override 642 @override
643 void visitApplyBuiltinMethod(ApplyBuiltinMethod node) { 643 void visitApplyBuiltinMethod(ApplyBuiltinMethod node) {
644 Primitive receiver = node.receiver.definition; 644 Primitive receiver = node.receiver;
645 int effectBefore = currentEffectNumber; 645 int effectBefore = currentEffectNumber;
646 currentEffectNumber = makeNewEffect(); 646 currentEffectNumber = makeNewEffect();
647 int effectAfter = currentEffectNumber; 647 int effectAfter = currentEffectNumber;
648 SignedVariable lengthBefore = getLength(receiver, effectBefore); 648 SignedVariable lengthBefore = getLength(receiver, effectBefore);
649 SignedVariable lengthAfter = getLength(receiver, effectAfter); 649 SignedVariable lengthAfter = getLength(receiver, effectAfter);
650 switch (node.method) { 650 switch (node.method) {
651 case BuiltinMethod.Push: 651 case BuiltinMethod.Push:
652 // after = before + count 652 // after = before + count
653 int count = node.arguments.length; 653 int count = node.argumentRefs.length;
654 makeExactSum(lengthAfter, lengthBefore, count); 654 makeExactSum(lengthAfter, lengthBefore, count);
655 break; 655 break;
656 656
657 case BuiltinMethod.Pop: 657 case BuiltinMethod.Pop:
658 // after = before - 1 658 // after = before - 1
659 makeExactSum(lengthAfter, lengthBefore, -1); 659 makeExactSum(lengthAfter, lengthBefore, -1);
660 break; 660 break;
661 661
662 case BuiltinMethod.SetLength: 662 case BuiltinMethod.SetLength:
663 makeEqual(lengthAfter, getValue(node.arguments[0].definition)); 663 makeEqual(lengthAfter, getValue(node.argument(0)));
664 break; 664 break;
665 } 665 }
666 } 666 }
667 667
668 @override 668 @override
669 void visitLiteralList(LiteralList node) { 669 void visitLiteralList(LiteralList node) {
670 makeConstant(getLength(node, currentEffectNumber), node.values.length); 670 makeConstant(getLength(node, currentEffectNumber), node.valueRefs.length);
671 } 671 }
672 672
673 // ---------------- INTERIOR EXPRESSIONS -------------------- 673 // ---------------- INTERIOR EXPRESSIONS --------------------
674 674
675 @override 675 @override
676 Expression traverseContinuation(Continuation cont) { 676 Expression traverseContinuation(Continuation cont) {
677 if (octagon.isUnsolvable) { 677 if (octagon.isUnsolvable) {
678 destroyAndReplace(cont.body, new Unreachable()); 678 destroyAndReplace(cont.body, new Unreachable());
679 } else { 679 } else {
680 int effect = effectNumberAt[cont]; 680 int effect = effectNumberAt[cont];
(...skipping 18 matching lines...) Expand all
699 } 699 }
700 return node.body; 700 return node.body;
701 } 701 }
702 } 702 }
703 703
704 /// Lattice representing the known (weak) monotonicity of a loop variable. 704 /// Lattice representing the known (weak) monotonicity of a loop variable.
705 /// 705 ///
706 /// The lattice bottom is represented by `null` and represents the case where 706 /// The lattice bottom is represented by `null` and represents the case where
707 /// the loop variable never changes value during the loop. 707 /// the loop variable never changes value during the loop.
708 enum Monotonicity { NotMonotone, Increasing, Decreasing, } 708 enum Monotonicity { NotMonotone, Increasing, Decreasing, }
OLDNEW

Powered by Google App Engine
This is Rietveld 408576698