| OLD | NEW |
| 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'; |
| 11 import 'cps_fragment.dart'; | 11 import 'cps_fragment.dart'; |
| 12 import 'type_mask_system.dart'; | 12 import 'type_mask_system.dart'; |
| 13 import '../types/types.dart'; | 13 import '../types/types.dart'; |
| 14 import '../world.dart'; | 14 import '../world.dart'; |
| 15 import '../elements/elements.dart'; | 15 import '../elements/elements.dart'; |
| 16 import 'loop_effects.dart'; | 16 import 'loop_effects.dart'; |
| 17 import 'effects.dart'; | |
| 18 | 17 |
| 19 /// Eliminates bounds checks when they can be proven safe. | 18 /// Eliminates bounds checks when they can be proven safe. |
| 20 /// | 19 /// |
| 21 /// In general, this pass will try to eliminate any branch with arithmetic | 20 /// In general, this pass will try to eliminate any branch with arithmetic |
| 22 /// in the condition, i.e. `x < y`, `x <= y`, `x == y` etc. | 21 /// in the condition, i.e. `x < y`, `x <= y`, `x == y` etc. |
| 23 /// | 22 /// |
| 24 /// The analysis uses an [Octagon] abstract domain. Unlike traditional octagon | 23 /// The analysis uses an [Octagon] abstract domain. Unlike traditional octagon |
| 25 /// analyzers, we do not use a closed matrix representation, but just maintain | 24 /// analyzers, we do not use a closed matrix representation, but just maintain |
| 26 /// a bucket of constraints. Constraints can therefore be added and removed | 25 /// a bucket of constraints. Constraints can therefore be added and removed |
| 27 /// on-the-fly without significant overhead. | 26 /// on-the-fly without significant overhead. |
| (...skipping 514 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 542 if (mono == null) { | 541 if (mono == null) { |
| 543 // Value never changes. This is extremely uncommon. | 542 // Value never changes. This is extremely uncommon. |
| 544 param.replaceUsesWith(initialValue); | 543 param.replaceUsesWith(initialValue); |
| 545 } else if (mono == Monotonicity.Increasing) { | 544 } else if (mono == Monotonicity.Increasing) { |
| 546 makeGreaterThanOrEqual(getValue(param), initialVariable); | 545 makeGreaterThanOrEqual(getValue(param), initialVariable); |
| 547 } else if (mono == Monotonicity.Decreasing) { | 546 } else if (mono == Monotonicity.Decreasing) { |
| 548 makeLessThanOrEqual(getValue(param), initialVariable); | 547 makeLessThanOrEqual(getValue(param), initialVariable); |
| 549 } | 548 } |
| 550 } | 549 } |
| 551 } | 550 } |
| 552 if (loopEffects.changesIndexableLength(cont)) { | 551 if (loopEffects.loopChangesLength(cont)) { |
| 553 currentEffectNumber = effectNumberAt[cont] = makeNewEffect(); | 552 currentEffectNumber = effectNumberAt[cont] = makeNewEffect(); |
| 554 } | 553 } |
| 555 push(cont); | 554 push(cont); |
| 556 } | 555 } |
| 557 | 556 |
| 558 void analyzeLoopContinue(InvokeContinuation node) { | 557 void analyzeLoopContinue(InvokeContinuation node) { |
| 559 Continuation cont = node.continuation.definition; | 558 Continuation cont = node.continuation.definition; |
| 560 | 559 |
| 561 // During the strong loop phase, there is no need to compute monotonicity, | 560 // 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 | 561 // and we already put bounds on the loop variables when we went into the |
| (...skipping 44 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 607 } else if (effect != currentEffectNumber && effect != NEW_EFFECT) { | 606 } else if (effect != currentEffectNumber && effect != NEW_EFFECT) { |
| 608 effectNumberAt[cont] = NEW_EFFECT; | 607 effectNumberAt[cont] = NEW_EFFECT; |
| 609 } | 608 } |
| 610 // TODO(asgerf): Compute join for parameters to increase precision? | 609 // TODO(asgerf): Compute join for parameters to increase precision? |
| 611 } | 610 } |
| 612 } | 611 } |
| 613 | 612 |
| 614 // ---------------- PRIMITIVES -------------------- | 613 // ---------------- PRIMITIVES -------------------- |
| 615 | 614 |
| 616 @override | 615 @override |
| 617 Expression traverseLetPrim(LetPrim node) { | |
| 618 visit(node.primitive); | |
| 619 // visitApplyBuiltinMethod updates the effect number. | |
| 620 if (node.primitive is! ApplyBuiltinMethod) { | |
| 621 if (node.primitive.effects & Effects.changesIndexableLength != 0) { | |
| 622 currentEffectNumber = makeNewEffect(); | |
| 623 } | |
| 624 } | |
| 625 return node.body; | |
| 626 } | |
| 627 | |
| 628 @override | |
| 629 void visitInvokeMethod(InvokeMethod node) { | 616 void visitInvokeMethod(InvokeMethod node) { |
| 630 if (node.selector.isGetter && node.selector.name == 'length') { | 617 if (node.selector.isGetter && node.selector.name == 'length') { |
| 631 // If the receiver type is not known to be indexable, the length call | 618 // If the receiver type is not known to be indexable, the length call |
| 632 // was not rewritten to GetLength. But if we can prove that the call only | 619 // was not rewritten to GetLength. But if we can prove that the call only |
| 633 // succeeds for indexables, we can trust that it returns the length. | 620 // succeeds for indexables, we can trust that it returns the length. |
| 634 TypeMask successType = | 621 TypeMask successType = |
| 635 types.receiverTypeFor(node.selector, node.dartReceiver.type); | 622 types.receiverTypeFor(node.selector, node.dartReceiver.type); |
| 636 if (types.isDefinitelyIndexable(successType)) { | 623 if (types.isDefinitelyIndexable(successType)) { |
| 637 valueOf[node] = getLength(node.dartReceiver, currentEffectNumber); | 624 valueOf[node] = getLength(node.dartReceiver, currentEffectNumber); |
| 638 } | 625 } |
| 639 } | 626 } |
| 627 // TODO(asgerf): What we really need is a "changes length" side effect flag. |
| 628 if (world |
| 629 .getSideEffectsOfSelector(node.selector, node.mask) |
| 630 .changesIndex()) { |
| 631 currentEffectNumber = makeNewEffect(); |
| 632 } |
| 640 } | 633 } |
| 641 | 634 |
| 642 @override | 635 @override |
| 636 void visitInvokeStatic(InvokeStatic node) { |
| 637 if (world.getSideEffectsOfElement(node.target).changesIndex()) { |
| 638 currentEffectNumber = makeNewEffect(); |
| 639 } |
| 640 } |
| 641 |
| 642 @override |
| 643 void visitInvokeMethodDirectly(InvokeMethodDirectly node) { |
| 644 FunctionElement target = node.target; |
| 645 if (target is ConstructorBodyElement) { |
| 646 ConstructorBodyElement body = target; |
| 647 target = body.constructor; |
| 648 } |
| 649 if (world.getSideEffectsOfElement(target).changesIndex()) { |
| 650 currentEffectNumber = makeNewEffect(); |
| 651 } |
| 652 } |
| 653 |
| 654 @override |
| 655 void visitInvokeConstructor(InvokeConstructor node) { |
| 656 if (world.getSideEffectsOfElement(node.target).changesIndex()) { |
| 657 currentEffectNumber = makeNewEffect(); |
| 658 } |
| 659 } |
| 660 |
| 661 @override |
| 662 void visitTypeCast(TypeCast node) { |
| 663 } |
| 664 |
| 665 @override |
| 666 void visitGetLazyStatic(GetLazyStatic node) { |
| 667 // TODO(asgerf): How do we get the side effects of a lazy field initializer? |
| 668 currentEffectNumber = makeNewEffect(); |
| 669 } |
| 670 |
| 671 @override |
| 672 void visitForeignCode(ForeignCode node) { |
| 673 if (node.nativeBehavior.sideEffects.changesIndex()) { |
| 674 currentEffectNumber = makeNewEffect(); |
| 675 } |
| 676 } |
| 677 |
| 678 @override |
| 679 void visitAwait(Await node) { |
| 680 currentEffectNumber = makeNewEffect(); |
| 681 } |
| 682 |
| 683 @override |
| 684 void visitYield(Yield node) { |
| 685 currentEffectNumber = makeNewEffect(); |
| 686 } |
| 687 |
| 688 @override |
| 643 void visitApplyBuiltinMethod(ApplyBuiltinMethod node) { | 689 void visitApplyBuiltinMethod(ApplyBuiltinMethod node) { |
| 644 Primitive receiver = node.receiver.definition; | 690 Primitive receiver = node.receiver.definition; |
| 645 int effectBefore = currentEffectNumber; | 691 int effectBefore = currentEffectNumber; |
| 646 currentEffectNumber = makeNewEffect(); | 692 currentEffectNumber = makeNewEffect(); |
| 647 int effectAfter = currentEffectNumber; | 693 int effectAfter = currentEffectNumber; |
| 648 SignedVariable lengthBefore = getLength(receiver, effectBefore); | 694 SignedVariable lengthBefore = getLength(receiver, effectBefore); |
| 649 SignedVariable lengthAfter = getLength(receiver, effectAfter); | 695 SignedVariable lengthAfter = getLength(receiver, effectAfter); |
| 650 switch (node.method) { | 696 switch (node.method) { |
| 651 case BuiltinMethod.Push: | 697 case BuiltinMethod.Push: |
| 652 // after = before + count | 698 // after = before + count |
| (...skipping 46 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 699 } | 745 } |
| 700 return node.body; | 746 return node.body; |
| 701 } | 747 } |
| 702 } | 748 } |
| 703 | 749 |
| 704 /// Lattice representing the known (weak) monotonicity of a loop variable. | 750 /// Lattice representing the known (weak) monotonicity of a loop variable. |
| 705 /// | 751 /// |
| 706 /// The lattice bottom is represented by `null` and represents the case where | 752 /// The lattice bottom is represented by `null` and represents the case where |
| 707 /// the loop variable never changes value during the loop. | 753 /// the loop variable never changes value during the loop. |
| 708 enum Monotonicity { NotMonotone, Increasing, Decreasing, } | 754 enum Monotonicity { NotMonotone, Increasing, Decreasing, } |
| OLD | NEW |