| 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 #include "vm/flow_graph_range_analysis.h" | 5 #include "vm/flow_graph_range_analysis.h" |
| 6 | 6 |
| 7 #include "vm/bit_vector.h" | 7 #include "vm/bit_vector.h" |
| 8 #include "vm/il_printer.h" | 8 #include "vm/il_printer.h" |
| 9 | 9 |
| 10 namespace dart { | 10 namespace dart { |
| (...skipping 423 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 434 | 434 |
| 435 return (max.ConstantValue() >= new_max.ConstantValue()) ? | 435 return (max.ConstantValue() >= new_max.ConstantValue()) ? |
| 436 max : RangeBoundary::MaxConstant(size); | 436 max : RangeBoundary::MaxConstant(size); |
| 437 } | 437 } |
| 438 | 438 |
| 439 | 439 |
| 440 // Given the current range of a phi and a newly computed range check | 440 // Given the current range of a phi and a newly computed range check |
| 441 // if we can perform narrowing: use newly computed minimum to improve precision | 441 // if we can perform narrowing: use newly computed minimum to improve precision |
| 442 // of the computed range. We do it only if current minimum was widened and is | 442 // of the computed range. We do it only if current minimum was widened and is |
| 443 // equal to MinSmi. | 443 // equal to MinSmi. |
| 444 // Newly computed minimum is expected to be greater of equal then old one as | 444 // Newly computed minimum is expected to be greater or equal than old one as |
| 445 // we are running after widening phase. | 445 // we are running after widening phase. |
| 446 static RangeBoundary NarrowMin(const Range* range, | 446 static RangeBoundary NarrowMin(const Range* range, |
| 447 const Range* new_range, | 447 const Range* new_range, |
| 448 RangeBoundary::RangeSize size) { | 448 RangeBoundary::RangeSize size) { |
| 449 #ifdef DEBUG | 449 #ifdef DEBUG |
| 450 const RangeBoundary min = Range::ConstantMin(range, size); | 450 const RangeBoundary min = Range::ConstantMin(range, size); |
| 451 const RangeBoundary new_min = Range::ConstantMin(new_range, size); | 451 const RangeBoundary new_min = Range::ConstantMin(new_range, size); |
| 452 ASSERT(min.ConstantValue() <= new_min.ConstantValue()); | 452 ASSERT(min.ConstantValue() <= new_min.ConstantValue()); |
| 453 #endif | 453 #endif |
| 454 // TODO(vegorov): consider using negative infinity to indicate widened bound. | 454 // TODO(vegorov): consider using negative infinity to indicate widened bound. |
| 455 return range->min().IsMinimumOrBelow(size) ? new_range->min() : range->min(); | 455 return range->min().IsMinimumOrBelow(size) ? new_range->min() : range->min(); |
| 456 } | 456 } |
| 457 | 457 |
| 458 | 458 |
| 459 // Given the current range of a phi and a newly computed range check | 459 // Given the current range of a phi and a newly computed range check |
| 460 // if we can perform narrowing: use newly computed maximum to improve precision | 460 // if we can perform narrowing: use newly computed maximum to improve precision |
| 461 // of the computed range. We do it only if current maximum was widened and is | 461 // of the computed range. We do it only if current maximum was widened and is |
| 462 // equal to MaxSmi. | 462 // equal to MaxSmi. |
| 463 // Newly computed minimum is expected to be greater of equal then old one as | 463 // Newly computed maximum is expected to be less or equal than old one as |
| 464 // we are running after widening phase. | 464 // we are running after widening phase. |
| 465 static RangeBoundary NarrowMax(const Range* range, | 465 static RangeBoundary NarrowMax(const Range* range, |
| 466 const Range* new_range, | 466 const Range* new_range, |
| 467 RangeBoundary::RangeSize size) { | 467 RangeBoundary::RangeSize size) { |
| 468 #ifdef DEBUG | 468 #ifdef DEBUG |
| 469 const RangeBoundary max = Range::ConstantMax(range, size); | 469 const RangeBoundary max = Range::ConstantMax(range, size); |
| 470 const RangeBoundary new_max = Range::ConstantMax(new_range, size); | 470 const RangeBoundary new_max = Range::ConstantMax(new_range, size); |
| 471 ASSERT(max.ConstantValue() >= new_max.ConstantValue()); | 471 ASSERT(max.ConstantValue() >= new_max.ConstantValue()); |
| 472 #endif | 472 #endif |
| 473 // TODO(vegorov): consider using positive infinity to indicate widened bound. | 473 // TODO(vegorov): consider using positive infinity to indicate widened bound. |
| (...skipping 721 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 1195 if ((range == NULL) || !range->max().IsSymbol()) return false; | 1195 if ((range == NULL) || !range->max().IsSymbol()) return false; |
| 1196 | 1196 |
| 1197 | 1197 |
| 1198 if (Utils::WillAddOverflow(range->max().offset(), a->offset())) { | 1198 if (Utils::WillAddOverflow(range->max().offset(), a->offset())) { |
| 1199 *a = RangeBoundary::PositiveInfinity(); | 1199 *a = RangeBoundary::PositiveInfinity(); |
| 1200 return true; | 1200 return true; |
| 1201 } | 1201 } |
| 1202 | 1202 |
| 1203 const int64_t offset = range->max().offset() + a->offset(); | 1203 const int64_t offset = range->max().offset() + a->offset(); |
| 1204 | 1204 |
| 1205 | |
| 1206 *a = CanonicalizeBoundary( | 1205 *a = CanonicalizeBoundary( |
| 1207 RangeBoundary::FromDefinition(range->max().symbol(), offset), | 1206 RangeBoundary::FromDefinition(range->max().symbol(), offset), |
| 1208 RangeBoundary::PositiveInfinity()); | 1207 RangeBoundary::PositiveInfinity()); |
| 1209 | 1208 |
| 1210 return true; | 1209 return true; |
| 1211 } | 1210 } |
| 1212 | 1211 |
| 1213 | 1212 |
| 1214 static bool CanonicalizeMinBoundary(RangeBoundary* a) { | 1213 static bool CanonicalizeMinBoundary(RangeBoundary* a) { |
| 1215 if (!a->IsSymbol()) return false; | 1214 if (!a->IsSymbol()) return false; |
| (...skipping 18 matching lines...) Expand all Loading... |
| 1234 typedef bool (*BoundaryOp)(RangeBoundary*); | 1233 typedef bool (*BoundaryOp)(RangeBoundary*); |
| 1235 | 1234 |
| 1236 static bool CanonicalizeForComparison(RangeBoundary* a, | 1235 static bool CanonicalizeForComparison(RangeBoundary* a, |
| 1237 RangeBoundary* b, | 1236 RangeBoundary* b, |
| 1238 BoundaryOp op, | 1237 BoundaryOp op, |
| 1239 const RangeBoundary& overflow) { | 1238 const RangeBoundary& overflow) { |
| 1240 if (!a->IsSymbol() || !b->IsSymbol()) { | 1239 if (!a->IsSymbol() || !b->IsSymbol()) { |
| 1241 return false; | 1240 return false; |
| 1242 } | 1241 } |
| 1243 | 1242 |
| 1244 if (DependOnSameSymbol(*a, *b)) { | 1243 RangeBoundary canonical_a = *a; |
| 1245 return true; | 1244 RangeBoundary canonical_b = *b; |
| 1246 } | |
| 1247 | |
| 1248 | |
| 1249 RangeBoundary canonical_a = CanonicalizeBoundary(*a, overflow); | |
| 1250 RangeBoundary canonical_b = CanonicalizeBoundary(*b, overflow); | |
| 1251 | 1245 |
| 1252 do { | 1246 do { |
| 1253 if (DependOnSameSymbol(canonical_a, canonical_b)) { | 1247 if (DependOnSameSymbol(canonical_a, canonical_b)) { |
| 1254 *a = canonical_a; | 1248 *a = canonical_a; |
| 1255 *b = canonical_b; | 1249 *b = canonical_b; |
| 1256 return true; | 1250 return true; |
| 1257 } | 1251 } |
| 1258 } while (op(&canonical_a) || op(&canonical_b)); | 1252 } while (op(&canonical_a) || op(&canonical_b)); |
| 1259 | 1253 |
| 1260 return false; | 1254 return false; |
| (...skipping 928 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 2189 } | 2183 } |
| 2190 } while (CanonicalizeMaxBoundary(&max) || | 2184 } while (CanonicalizeMaxBoundary(&max) || |
| 2191 CanonicalizeMinBoundary(&canonical_length)); | 2185 CanonicalizeMinBoundary(&canonical_length)); |
| 2192 | 2186 |
| 2193 // Failed to prove that maximum is bounded with array length. | 2187 // Failed to prove that maximum is bounded with array length. |
| 2194 return false; | 2188 return false; |
| 2195 } | 2189 } |
| 2196 | 2190 |
| 2197 | 2191 |
| 2198 } // namespace dart | 2192 } // namespace dart |
| OLD | NEW |