| 693 | } |
| 694 | |
| 695 | bool LoopDependenceAnalysis::WeakZeroSourceSIVTest( |
| 696 | SENode* source, SERecurrentNode* destination, SENode* coefficient, |
| 697 | DistanceEntry* distance_entry) { |
| 698 | PrintDebug("Performing WeakZeroSourceSIVTest."); |
| 699 | std::pair<SENode*, SENode*> subscript_pair = |
| 700 | std::make_pair(source, destination); |
| 701 | const Loop* subscript_loop = GetLoopForSubscriptPair(subscript_pair); |
| 702 | // Build an SENode for distance. |
| 703 | SENode* destination_constant_term = |
| 704 | GetConstantTerm(subscript_loop, destination); |
| 705 | SENode* delta = scalar_evolution_.SimplifyExpression( |
| 706 | scalar_evolution_.CreateSubtraction(source, destination_constant_term)); |
| 707 | |
| 708 | // Scalar evolution doesn't perform division, so we must fold to constants and |
| 709 | // do it manually. |
| 710 | int64_t distance = 0; |
| 711 | SEConstantNode* delta_constant = delta->AsSEConstantNode(); |
| 712 | SEConstantNode* coefficient_constant = coefficient->AsSEConstantNode(); |
| 713 | if (delta_constant && coefficient_constant) { |
| 714 | PrintDebug( |
| 715 | "WeakZeroSourceSIVTest folding delta and coefficient to constants."); |
| 716 | int64_t delta_value = delta_constant->FoldToSingleValue(); |
| 717 | int64_t coefficient_value = coefficient_constant->FoldToSingleValue(); |
| 718 | // Check if the distance is not integral. |
| 719 | if (delta_value % coefficient_value != 0) { |
| 720 | PrintDebug( |
| 721 | "WeakZeroSourceSIVTest proved independence through distance not " |
| 722 | "being an integer."); |
| 723 | distance_entry->dependence_information = |
| 724 | DistanceEntry::DependenceInformation::DIRECTION; |
| 725 | distance_entry->direction = DistanceEntry::Directions::NONE; |
| 726 | return true; |
| 727 | } else { |
| 728 | distance = delta_value / coefficient_value; |
| 729 | PrintDebug( |
| 730 | "WeakZeroSourceSIVTest calculated distance with the following " |
| 731 | "values\n" |
| 732 | "\tdelta value: " + |
| 733 | ToString(delta_value) + |
| 734 | "\n\tcoefficient value: " + ToString(coefficient_value) + |
| 735 | "\n\tdistance: " + ToString(distance) + "\n"); |
| 736 | } |
| 737 | } else { |
| 738 | PrintDebug( |
| 739 | "WeakZeroSourceSIVTest was unable to fold delta and coefficient to " |
| 740 | "constants."); |
| 741 | } |
| 742 | |
| 743 | // If we can prove the distance is outside the bounds we prove independence. |
| 744 | SEConstantNode* lower_bound = |
| 745 | GetLowerBound(subscript_loop)->AsSEConstantNode(); |
| 746 | SEConstantNode* upper_bound = |
| 747 | GetUpperBound(subscript_loop)->AsSEConstantNode(); |
| 748 | if (lower_bound && upper_bound) { |
| 749 | PrintDebug("WeakZeroSourceSIVTest found bounds as SEConstantNodes."); |
| 750 | int64_t lower_bound_value = lower_bound->FoldToSingleValue(); |
| 751 | int64_t upper_bound_value = upper_bound->FoldToSingleValue(); |
| 752 | if (!IsWithinBounds(llabs(distance), lower_bound_value, |
nothing calls this directly
no test coverage detected