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 |