| 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 #ifndef RUNTIME_VM_FLOW_GRAPH_RANGE_ANALYSIS_H_ | 5 #ifndef RUNTIME_VM_FLOW_GRAPH_RANGE_ANALYSIS_H_ |
| 6 #define RUNTIME_VM_FLOW_GRAPH_RANGE_ANALYSIS_H_ | 6 #define RUNTIME_VM_FLOW_GRAPH_RANGE_ANALYSIS_H_ |
| 7 | 7 |
| 8 #include "vm/flow_graph.h" | 8 #include "vm/flow_graph.h" |
| 9 #include "vm/intermediate_language.h" | 9 #include "vm/intermediate_language.h" |
| 10 | 10 |
| (...skipping 84 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 95 return FromConstant(Smi::kMaxValue); | 95 return FromConstant(Smi::kMaxValue); |
| 96 case kRangeBoundaryInt32: | 96 case kRangeBoundaryInt32: |
| 97 return FromConstant(kMaxInt32); | 97 return FromConstant(kMaxInt32); |
| 98 case kRangeBoundaryInt64: | 98 case kRangeBoundaryInt64: |
| 99 return FromConstant(kMaxInt64); | 99 return FromConstant(kMaxInt64); |
| 100 } | 100 } |
| 101 UNREACHABLE(); | 101 UNREACHABLE(); |
| 102 return FromConstant(kMaxInt64); | 102 return FromConstant(kMaxInt64); |
| 103 } | 103 } |
| 104 | 104 |
| 105 | |
| 106 // Given two boundaries a and b, select one of them as c so that | 105 // Given two boundaries a and b, select one of them as c so that |
| 107 // | 106 // |
| 108 // inf {[a, ...) ^ [b, ...)} >= inf {c} | 107 // inf {[a, ...) ^ [b, ...)} >= inf {c} |
| 109 // | 108 // |
| 110 static RangeBoundary IntersectionMin(RangeBoundary a, RangeBoundary b); | 109 static RangeBoundary IntersectionMin(RangeBoundary a, RangeBoundary b); |
| 111 | 110 |
| 112 // Given two boundaries a and b, select one of them as c so that | 111 // Given two boundaries a and b, select one of them as c so that |
| 113 // | 112 // |
| 114 // sup {(..., a] ^ (..., b]} <= sup {c} | 113 // sup {(..., a] ^ (..., b]} <= sup {c} |
| 115 // | 114 // |
| (...skipping 163 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 279 | 278 |
| 280 private: | 279 private: |
| 281 RangeBoundary(Kind kind, int64_t value, int64_t offset) | 280 RangeBoundary(Kind kind, int64_t value, int64_t offset) |
| 282 : kind_(kind), value_(value), offset_(offset) {} | 281 : kind_(kind), value_(value), offset_(offset) {} |
| 283 | 282 |
| 284 Kind kind_; | 283 Kind kind_; |
| 285 int64_t value_; | 284 int64_t value_; |
| 286 int64_t offset_; | 285 int64_t offset_; |
| 287 }; | 286 }; |
| 288 | 287 |
| 289 | |
| 290 class Range : public ZoneAllocated { | 288 class Range : public ZoneAllocated { |
| 291 public: | 289 public: |
| 292 Range() : min_(), max_() {} | 290 Range() : min_(), max_() {} |
| 293 Range(RangeBoundary min, RangeBoundary max) : min_(min), max_(max) { | 291 Range(RangeBoundary min, RangeBoundary max) : min_(min), max_(max) { |
| 294 ASSERT(min_.IsUnknown() == max_.IsUnknown()); | 292 ASSERT(min_.IsUnknown() == max_.IsUnknown()); |
| 295 } | 293 } |
| 296 | 294 |
| 297 Range(const Range& other) | 295 Range(const Range& other) |
| 298 : ZoneAllocated(), min_(other.min_), max_(other.max_) {} | 296 : ZoneAllocated(), min_(other.min_), max_(other.max_) {} |
| 299 | 297 |
| (...skipping 56 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 356 } | 354 } |
| 357 | 355 |
| 358 static RangeBoundary ConstantMax(const Range* range, | 356 static RangeBoundary ConstantMax(const Range* range, |
| 359 RangeBoundary::RangeSize size) { | 357 RangeBoundary::RangeSize size) { |
| 360 if (range == NULL) { | 358 if (range == NULL) { |
| 361 return RangeBoundary::MaxConstant(size); | 359 return RangeBoundary::MaxConstant(size); |
| 362 } | 360 } |
| 363 return range->max().UpperBound().Clamp(size); | 361 return range->max().UpperBound().Clamp(size); |
| 364 } | 362 } |
| 365 | 363 |
| 366 | |
| 367 // [0, +inf] | 364 // [0, +inf] |
| 368 bool IsPositive() const; | 365 bool IsPositive() const; |
| 369 | 366 |
| 370 // [-inf, val]. | 367 // [-inf, val]. |
| 371 bool OnlyLessThanOrEqualTo(int64_t val) const; | 368 bool OnlyLessThanOrEqualTo(int64_t val) const; |
| 372 | 369 |
| 373 // [val, +inf]. | 370 // [val, +inf]. |
| 374 bool OnlyGreaterThanOrEqualTo(int64_t val) const; | 371 bool OnlyGreaterThanOrEqualTo(int64_t val) const; |
| 375 | 372 |
| 376 // Inclusive. | 373 // Inclusive. |
| (...skipping 74 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 451 const Range* left_range, | 448 const Range* left_range, |
| 452 const Range* right_range, | 449 const Range* right_range, |
| 453 Definition* left_defn, | 450 Definition* left_defn, |
| 454 Range* result); | 451 Range* result); |
| 455 | 452 |
| 456 private: | 453 private: |
| 457 RangeBoundary min_; | 454 RangeBoundary min_; |
| 458 RangeBoundary max_; | 455 RangeBoundary max_; |
| 459 }; | 456 }; |
| 460 | 457 |
| 461 | |
| 462 class RangeUtils : public AllStatic { | 458 class RangeUtils : public AllStatic { |
| 463 public: | 459 public: |
| 464 static bool Fits(Range* range, RangeBoundary::RangeSize size) { | 460 static bool Fits(Range* range, RangeBoundary::RangeSize size) { |
| 465 return !Range::IsUnknown(range) && range->Fits(size); | 461 return !Range::IsUnknown(range) && range->Fits(size); |
| 466 } | 462 } |
| 467 | 463 |
| 468 static bool IsWithin(Range* range, int64_t min, int64_t max) { | 464 static bool IsWithin(Range* range, int64_t min, int64_t max) { |
| 469 return !Range::IsUnknown(range) && range->IsWithin(min, max); | 465 return !Range::IsUnknown(range) && range->IsWithin(min, max); |
| 470 } | 466 } |
| 471 | 467 |
| 472 static bool IsPositive(Range* range) { | 468 static bool IsPositive(Range* range) { |
| 473 return !Range::IsUnknown(range) && range->IsPositive(); | 469 return !Range::IsUnknown(range) && range->IsPositive(); |
| 474 } | 470 } |
| 475 | 471 |
| 476 static bool Overlaps(Range* range, intptr_t min, intptr_t max) { | 472 static bool Overlaps(Range* range, intptr_t min, intptr_t max) { |
| 477 return Range::IsUnknown(range) || range->Overlaps(min, max); | 473 return Range::IsUnknown(range) || range->Overlaps(min, max); |
| 478 } | 474 } |
| 479 | 475 |
| 480 static bool CanBeZero(Range* range) { return Overlaps(range, 0, 0); } | 476 static bool CanBeZero(Range* range) { return Overlaps(range, 0, 0); } |
| 481 | 477 |
| 482 static bool OnlyLessThanOrEqualTo(Range* range, intptr_t value) { | 478 static bool OnlyLessThanOrEqualTo(Range* range, intptr_t value) { |
| 483 return !Range::IsUnknown(range) && range->OnlyLessThanOrEqualTo(value); | 479 return !Range::IsUnknown(range) && range->OnlyLessThanOrEqualTo(value); |
| 484 } | 480 } |
| 485 }; | 481 }; |
| 486 | 482 |
| 487 | |
| 488 // Range analysis for integer values. | 483 // Range analysis for integer values. |
| 489 class RangeAnalysis : public ValueObject { | 484 class RangeAnalysis : public ValueObject { |
| 490 public: | 485 public: |
| 491 explicit RangeAnalysis(FlowGraph* flow_graph) | 486 explicit RangeAnalysis(FlowGraph* flow_graph) |
| 492 : flow_graph_(flow_graph), | 487 : flow_graph_(flow_graph), |
| 493 smi_range_(Range::Full(RangeBoundary::kRangeBoundarySmi)), | 488 smi_range_(Range::Full(RangeBoundary::kRangeBoundarySmi)), |
| 494 int64_range_(Range::Full(RangeBoundary::kRangeBoundaryInt64)) {} | 489 int64_range_(Range::Full(RangeBoundary::kRangeBoundaryInt64)) {} |
| 495 | 490 |
| 496 // Infer ranges for all values and remove overflow checks from binary smi | 491 // Infer ranges for all values and remove overflow checks from binary smi |
| 497 // operations when proven redundant. | 492 // operations when proven redundant. |
| (...skipping 43 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 541 | 536 |
| 542 bool ConstrainValueAfterBranch(Value* use, Definition* defn); | 537 bool ConstrainValueAfterBranch(Value* use, Definition* defn); |
| 543 void ConstrainValueAfterCheckArrayBound(Value* use, Definition* defn); | 538 void ConstrainValueAfterCheckArrayBound(Value* use, Definition* defn); |
| 544 | 539 |
| 545 // Replace uses of the definition def that are dominated by instruction dom | 540 // Replace uses of the definition def that are dominated by instruction dom |
| 546 // with uses of other definition. | 541 // with uses of other definition. |
| 547 void RenameDominatedUses(Definition* def, | 542 void RenameDominatedUses(Definition* def, |
| 548 Instruction* dom, | 543 Instruction* dom, |
| 549 Definition* other); | 544 Definition* other); |
| 550 | 545 |
| 551 | |
| 552 // Infer ranges for integer (smi or mint) definitions. | 546 // Infer ranges for integer (smi or mint) definitions. |
| 553 void InferRanges(); | 547 void InferRanges(); |
| 554 | 548 |
| 555 // Collect integer definition in the reverse postorder. | 549 // Collect integer definition in the reverse postorder. |
| 556 void CollectDefinitions(BitVector* set); | 550 void CollectDefinitions(BitVector* set); |
| 557 | 551 |
| 558 // Recompute ranges of all definitions until they stop changing. | 552 // Recompute ranges of all definitions until they stop changing. |
| 559 // Apply the given JoinOperator when computing Phi ranges. | 553 // Apply the given JoinOperator when computing Phi ranges. |
| 560 void Iterate(JoinOperator op, intptr_t max_iterations); | 554 void Iterate(JoinOperator op, intptr_t max_iterations); |
| 561 bool InferRange(JoinOperator op, Definition* defn, intptr_t iteration); | 555 bool InferRange(JoinOperator op, Definition* defn, intptr_t iteration); |
| (...skipping 39 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 601 // as smi values. | 595 // as smi values. |
| 602 GrowableArray<ConstraintInstr*> constraints_; | 596 GrowableArray<ConstraintInstr*> constraints_; |
| 603 | 597 |
| 604 // List of integer (smi or mint) definitions including constraints sorted | 598 // List of integer (smi or mint) definitions including constraints sorted |
| 605 // in the reverse postorder. | 599 // in the reverse postorder. |
| 606 GrowableArray<Definition*> definitions_; | 600 GrowableArray<Definition*> definitions_; |
| 607 | 601 |
| 608 DISALLOW_COPY_AND_ASSIGN(RangeAnalysis); | 602 DISALLOW_COPY_AND_ASSIGN(RangeAnalysis); |
| 609 }; | 603 }; |
| 610 | 604 |
| 611 | |
| 612 // Replaces Mint IL instructions with Uint32 IL instructions | 605 // Replaces Mint IL instructions with Uint32 IL instructions |
| 613 // when possible. Uses output of RangeAnalysis. | 606 // when possible. Uses output of RangeAnalysis. |
| 614 class IntegerInstructionSelector : public ValueObject { | 607 class IntegerInstructionSelector : public ValueObject { |
| 615 public: | 608 public: |
| 616 explicit IntegerInstructionSelector(FlowGraph* flow_graph); | 609 explicit IntegerInstructionSelector(FlowGraph* flow_graph); |
| 617 | 610 |
| 618 void Select(); | 611 void Select(); |
| 619 | 612 |
| 620 private: | 613 private: |
| 621 bool IsPotentialUint32Definition(Definition* def); | 614 bool IsPotentialUint32Definition(Definition* def); |
| 622 void FindPotentialUint32Definitions(); | 615 void FindPotentialUint32Definitions(); |
| 623 bool IsUint32NarrowingDefinition(Definition* def); | 616 bool IsUint32NarrowingDefinition(Definition* def); |
| 624 void FindUint32NarrowingDefinitions(); | 617 void FindUint32NarrowingDefinitions(); |
| 625 bool AllUsesAreUint32Narrowing(Value* list_head); | 618 bool AllUsesAreUint32Narrowing(Value* list_head); |
| 626 bool CanBecomeUint32(Definition* def); | 619 bool CanBecomeUint32(Definition* def); |
| 627 void Propagate(); | 620 void Propagate(); |
| 628 Definition* ConstructReplacementFor(Definition* def); | 621 Definition* ConstructReplacementFor(Definition* def); |
| 629 void ReplaceInstructions(); | 622 void ReplaceInstructions(); |
| 630 | 623 |
| 631 Zone* zone() const { return zone_; } | 624 Zone* zone() const { return zone_; } |
| 632 | 625 |
| 633 GrowableArray<Definition*> potential_uint32_defs_; | 626 GrowableArray<Definition*> potential_uint32_defs_; |
| 634 BitVector* selected_uint32_defs_; | 627 BitVector* selected_uint32_defs_; |
| 635 | 628 |
| 636 FlowGraph* flow_graph_; | 629 FlowGraph* flow_graph_; |
| 637 Zone* zone_; | 630 Zone* zone_; |
| 638 }; | 631 }; |
| 639 | 632 |
| 640 | |
| 641 } // namespace dart | 633 } // namespace dart |
| 642 | 634 |
| 643 #endif // RUNTIME_VM_FLOW_GRAPH_RANGE_ANALYSIS_H_ | 635 #endif // RUNTIME_VM_FLOW_GRAPH_RANGE_ANALYSIS_H_ |
| OLD | NEW |