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'; |
(...skipping 106 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
117 SignedVariable getLength(Primitive indexableObject, int effectNumber) { | 117 SignedVariable getLength(Primitive indexableObject, int effectNumber) { |
118 indexableObject = indexableObject.effectiveDefinition; | 118 indexableObject = indexableObject.effectiveDefinition; |
119 TypeMask type = indexableObject.type.nonNullable(); | 119 TypeMask type = indexableObject.type.nonNullable(); |
120 if (types.isDefinitelyFixedLengthIndexable(type)) { | 120 if (types.isDefinitelyFixedLengthIndexable(type)) { |
121 // Always use the same effect number if the length is immutable. | 121 // Always use the same effect number if the length is immutable. |
122 effectNumber = 0; | 122 effectNumber = 0; |
123 } | 123 } |
124 return lengthOf | 124 return lengthOf |
125 .putIfAbsent(indexableObject, () => <int, SignedVariable>{}) | 125 .putIfAbsent(indexableObject, () => <int, SignedVariable>{}) |
126 .putIfAbsent(effectNumber, () { | 126 .putIfAbsent(effectNumber, () { |
127 int length = types.getContainerLength(type); | 127 int length = types.getContainerLength(type); |
128 if (length != null) { | 128 if (length != null) { |
129 return octagon.makeVariable(length, length); | 129 return octagon.makeVariable(length, length); |
130 } else { | 130 } else { |
131 return octagon.makeVariable(0, MAX_UINT32); | 131 return octagon.makeVariable(0, MAX_UINT32); |
132 } | 132 } |
133 }); | 133 }); |
134 } | 134 } |
135 | 135 |
136 // ------------- CONSTRAINT HELPERS ----------------- | 136 // ------------- CONSTRAINT HELPERS ----------------- |
137 | 137 |
138 /// Puts the given constraint "in scope" by adding it to the octagon, and | 138 /// Puts the given constraint "in scope" by adding it to the octagon, and |
139 /// pushing a stack action that will remove it again. | 139 /// pushing a stack action that will remove it again. |
140 void applyConstraint(SignedVariable v1, SignedVariable v2, int k) { | 140 void applyConstraint(SignedVariable v1, SignedVariable v2, int k) { |
141 Constraint constraint = new Constraint(v1, v2, k); | 141 Constraint constraint = new Constraint(v1, v2, k); |
142 octagon.pushConstraint(constraint); | 142 octagon.pushConstraint(constraint); |
143 pushAction(() => octagon.popConstraint(constraint)); | 143 pushAction(() => octagon.popConstraint(constraint)); |
(...skipping 342 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
486 | 486 |
487 @override | 487 @override |
488 void visitGetLength(GetLength node) { | 488 void visitGetLength(GetLength node) { |
489 valueOf[node] = getLength(node.object, currentEffectNumber); | 489 valueOf[node] = getLength(node.object, currentEffectNumber); |
490 } | 490 } |
491 | 491 |
492 @override | 492 @override |
493 void visitBoundsCheck(BoundsCheck node) { | 493 void visitBoundsCheck(BoundsCheck node) { |
494 if (node.checks == BoundsCheck.NONE) return; | 494 if (node.checks == BoundsCheck.NONE) return; |
495 assert(node.indexRef != null); // Because there is at least one check. | 495 assert(node.indexRef != null); // Because there is at least one check. |
496 SignedVariable length = node.lengthRef == null | 496 SignedVariable length = |
497 ? null | 497 node.lengthRef == null ? null : getValue(node.length); |
498 : getValue(node.length); | |
499 SignedVariable index = getValue(node.index); | 498 SignedVariable index = getValue(node.index); |
500 if (node.hasUpperBoundCheck) { | 499 if (node.hasUpperBoundCheck) { |
501 if (isDefinitelyLessThan(index, length)) { | 500 if (isDefinitelyLessThan(index, length)) { |
502 node.checks &= ~BoundsCheck.UPPER_BOUND; | 501 node.checks &= ~BoundsCheck.UPPER_BOUND; |
503 } else { | 502 } else { |
504 makeLessThan(index, length); | 503 makeLessThan(index, length); |
505 } | 504 } |
506 } | 505 } |
507 if (node.hasLowerBoundCheck) { | 506 if (node.hasLowerBoundCheck) { |
508 if (isDefinitelyGreaterThanOrEqualToConstant(index, 0)) { | 507 if (isDefinitelyGreaterThanOrEqualToConstant(index, 0)) { |
509 node.checks &= ~BoundsCheck.LOWER_BOUND; | 508 node.checks &= ~BoundsCheck.LOWER_BOUND; |
510 } else { | 509 } else { |
511 makeGreaterThanOrEqualToConstant(index, 0); | 510 makeGreaterThanOrEqualToConstant(index, 0); |
512 } | 511 } |
513 } | 512 } |
514 if (node.hasEmptinessCheck) { | 513 if (node.hasEmptinessCheck) { |
515 if (isDefinitelyGreaterThanOrEqualToConstant(length, 1)) { | 514 if (isDefinitelyGreaterThanOrEqualToConstant(length, 1)) { |
516 node.checks &= ~BoundsCheck.EMPTINESS; | 515 node.checks &= ~BoundsCheck.EMPTINESS; |
517 } else { | 516 } else { |
518 makeGreaterThanOrEqualToConstant(length, 1); | 517 makeGreaterThanOrEqualToConstant(length, 1); |
519 } | 518 } |
520 } | 519 } |
521 if (!node.lengthUsedInCheck && node.lengthRef != null) { | 520 if (!node.lengthUsedInCheck && node.lengthRef != null) { |
522 node..lengthRef.unlink()..lengthRef = null; | 521 node |
| 522 ..lengthRef.unlink() |
| 523 ..lengthRef = null; |
523 } | 524 } |
524 if (node.checks == BoundsCheck.NONE) { | 525 if (node.checks == BoundsCheck.NONE) { |
525 // 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 |
526 // restrict code motion. But the index is no longer needed. | 527 // restrict code motion. But the index is no longer needed. |
527 node..indexRef.unlink()..indexRef = null; | 528 node |
| 529 ..indexRef.unlink() |
| 530 ..indexRef = null; |
528 } | 531 } |
529 } | 532 } |
530 | 533 |
531 void analyzeLoopEntry(InvokeContinuation node) { | 534 void analyzeLoopEntry(InvokeContinuation node) { |
532 foundLoop = true; | 535 foundLoop = true; |
533 Continuation cont = node.continuation; | 536 Continuation cont = node.continuation; |
534 if (isStrongLoopPass) { | 537 if (isStrongLoopPass) { |
535 for (int i = 0; i < node.argumentRefs.length; ++i) { | 538 for (int i = 0; i < node.argumentRefs.length; ++i) { |
536 Parameter param = cont.parameters[i]; | 539 Parameter param = cont.parameters[i]; |
537 if (!isInt(param)) continue; | 540 if (!isInt(param)) continue; |
(...skipping 160 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
698 } | 701 } |
699 return node.body; | 702 return node.body; |
700 } | 703 } |
701 } | 704 } |
702 | 705 |
703 /// Lattice representing the known (weak) monotonicity of a loop variable. | 706 /// Lattice representing the known (weak) monotonicity of a loop variable. |
704 /// | 707 /// |
705 /// The lattice bottom is represented by `null` and represents the case where | 708 /// The lattice bottom is represented by `null` and represents the case where |
706 /// the loop variable never changes value during the loop. | 709 /// the loop variable never changes value during the loop. |
707 enum Monotonicity { NotMonotone, Increasing, Decreasing, } | 710 enum Monotonicity { NotMonotone, Increasing, Decreasing, } |
OLD | NEW |