| // Copyright (c) 2018 Google LLC. | |
| // | |
| // Licensed under the Apache License, Version 2.0 (the "License"); | |
| // you may not use this file except in compliance with the License. | |
| // You may obtain a copy of the License at | |
| // | |
| // http://www.apache.org/licenses/LICENSE-2.0 | |
| // | |
| // Unless required by applicable law or agreed to in writing, software | |
| // distributed under the License is distributed on an "AS IS" BASIS, | |
| // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. | |
| // See the License for the specific language governing permissions and | |
| // limitations under the License. | |
| #include "source/opt/loop_dependence.h" | |
| #include <functional> | |
| #include <memory> | |
| #include <numeric> | |
| #include <string> | |
| #include <utility> | |
| #include <vector> | |
| #include "source/opt/instruction.h" | |
| #include "source/opt/scalar_analysis.h" | |
| #include "source/opt/scalar_analysis_nodes.h" | |
| namespace spvtools { | |
| namespace opt { | |
| using SubscriptPair = std::pair<SENode*, SENode*>; | |
| namespace { | |
| // Calculate the greatest common divisor of a & b using Stein's algorithm. | |
| // https://en.wikipedia.org/wiki/Binary_GCD_algorithm | |
| int64_t GreatestCommonDivisor(int64_t a, int64_t b) { | |
| // Simple cases | |
| if (a == b) { | |
| return a; | |
| } else if (a == 0) { | |
| return b; | |
| } else if (b == 0) { | |
| return a; | |
| } | |
| // Both even | |
| if (a % 2 == 0 && b % 2 == 0) { | |
| return 2 * GreatestCommonDivisor(a / 2, b / 2); | |
| } | |
| // Even a, odd b | |
| if (a % 2 == 0 && b % 2 == 1) { | |
| return GreatestCommonDivisor(a / 2, b); | |
| } | |
| // Odd a, even b | |
| if (a % 2 == 1 && b % 2 == 0) { | |
| return GreatestCommonDivisor(a, b / 2); | |
| } | |
| // Both odd, reduce the larger argument | |
| if (a > b) { | |
| return GreatestCommonDivisor((a - b) / 2, b); | |
| } else { | |
| return GreatestCommonDivisor((b - a) / 2, a); | |
| } | |
| } | |
| // Check if node is affine, ie in the form: a0*i0 + a1*i1 + ... an*in + c | |
| // and contains only the following types of nodes: SERecurrentNode, SEAddNode | |
| // and SEConstantNode | |
| bool IsInCorrectFormForGCDTest(SENode* node) { | |
| bool children_ok = true; | |
| if (auto add_node = node->AsSEAddNode()) { | |
| for (auto child : add_node->GetChildren()) { | |
| children_ok &= IsInCorrectFormForGCDTest(child); | |
| } | |
| } | |
| bool this_ok = node->AsSERecurrentNode() || node->AsSEAddNode() || | |
| node->AsSEConstantNode(); | |
| return children_ok && this_ok; | |
| } | |
| // If |node| is an SERecurrentNode then returns |node| or if |node| is an | |
| // SEAddNode returns a vector of SERecurrentNode that are its children. | |
| std::vector<SERecurrentNode*> GetAllTopLevelRecurrences(SENode* node) { | |
| auto nodes = std::vector<SERecurrentNode*>{}; | |
| if (auto recurrent_node = node->AsSERecurrentNode()) { | |
| nodes.push_back(recurrent_node); | |
| } | |
| if (auto add_node = node->AsSEAddNode()) { | |
| for (auto child : add_node->GetChildren()) { | |
| auto child_nodes = GetAllTopLevelRecurrences(child); | |
| nodes.insert(nodes.end(), child_nodes.begin(), child_nodes.end()); | |
| } | |
| } | |
| return nodes; | |
| } | |
| // If |node| is an SEConstantNode then returns |node| or if |node| is an | |
| // SEAddNode returns a vector of SEConstantNode that are its children. | |
| std::vector<SEConstantNode*> GetAllTopLevelConstants(SENode* node) { | |
| auto nodes = std::vector<SEConstantNode*>{}; | |
| if (auto recurrent_node = node->AsSEConstantNode()) { | |
| nodes.push_back(recurrent_node); | |
| } | |
| if (auto add_node = node->AsSEAddNode()) { | |
| for (auto child : add_node->GetChildren()) { | |
| auto child_nodes = GetAllTopLevelConstants(child); | |
| nodes.insert(nodes.end(), child_nodes.begin(), child_nodes.end()); | |
| } | |
| } | |
| return nodes; | |
| } | |
| bool AreOffsetsAndCoefficientsConstant( | |
| const std::vector<SERecurrentNode*>& nodes) { | |
| for (auto node : nodes) { | |
| if (!node->GetOffset()->AsSEConstantNode() || | |
| !node->GetOffset()->AsSEConstantNode()) { | |
| return false; | |
| } | |
| } | |
| return true; | |
| } | |
| // Fold all SEConstantNode that appear in |recurrences| and |constants| into a | |
| // single integer value. | |
| int64_t CalculateConstantTerm(const std::vector<SERecurrentNode*>& recurrences, | |
| const std::vector<SEConstantNode*>& constants) { | |
| int64_t constant_term = 0; | |
| for (auto recurrence : recurrences) { | |
| constant_term += | |
| recurrence->GetOffset()->AsSEConstantNode()->FoldToSingleValue(); | |
| } | |
| for (auto constant : constants) { | |
| constant_term += constant->FoldToSingleValue(); | |
| } | |
| return constant_term; | |
| } | |
| int64_t CalculateGCDFromCoefficients( | |
| const std::vector<SERecurrentNode*>& recurrences, int64_t running_gcd) { | |
| for (SERecurrentNode* recurrence : recurrences) { | |
| auto coefficient = recurrence->GetCoefficient()->AsSEConstantNode(); | |
| running_gcd = GreatestCommonDivisor( | |
| running_gcd, std::abs(coefficient->FoldToSingleValue())); | |
| } | |
| return running_gcd; | |
| } | |
| // Compare 2 fractions while first normalizing them, e.g. 2/4 and 4/8 will both | |
| // be simplified to 1/2 and then determined to be equal. | |
| bool NormalizeAndCompareFractions(int64_t numerator_0, int64_t denominator_0, | |
| int64_t numerator_1, int64_t denominator_1) { | |
| auto gcd_0 = | |
| GreatestCommonDivisor(std::abs(numerator_0), std::abs(denominator_0)); | |
| auto gcd_1 = | |
| GreatestCommonDivisor(std::abs(numerator_1), std::abs(denominator_1)); | |
| auto normalized_numerator_0 = numerator_0 / gcd_0; | |
| auto normalized_denominator_0 = denominator_0 / gcd_0; | |
| auto normalized_numerator_1 = numerator_1 / gcd_1; | |
| auto normalized_denominator_1 = denominator_1 / gcd_1; | |
| return normalized_numerator_0 == normalized_numerator_1 && | |
| normalized_denominator_0 == normalized_denominator_1; | |
| } | |
| } // namespace | |
| bool LoopDependenceAnalysis::GetDependence(const Instruction* source, | |
| const Instruction* destination, | |
| DistanceVector* distance_vector) { | |
| // Start off by finding and marking all the loops in |loops_| that are | |
| // irrelevant to the dependence analysis. | |
| MarkUnsusedDistanceEntriesAsIrrelevant(source, destination, distance_vector); | |
| Instruction* source_access_chain = GetOperandDefinition(source, 0); | |
| Instruction* destination_access_chain = GetOperandDefinition(destination, 0); | |
| auto num_access_chains = | |
| (source_access_chain->opcode() == SpvOpAccessChain) + | |
| (destination_access_chain->opcode() == SpvOpAccessChain); | |
| // If neither is an access chain, then they are load/store to a variable. | |
| if (num_access_chains == 0) { | |
| if (source_access_chain != destination_access_chain) { | |
| // Not the same location, report independence | |
| return true; | |
| } else { | |
| // Accessing the same variable | |
| for (auto& entry : distance_vector->GetEntries()) { | |
| entry = DistanceEntry(); | |
| } | |
| return false; | |
| } | |
| } | |
| // If only one is an access chain, it could be accessing a part of a struct | |
| if (num_access_chains == 1) { | |
| auto source_is_chain = source_access_chain->opcode() == SpvOpAccessChain; | |
| auto access_chain = | |
| source_is_chain ? source_access_chain : destination_access_chain; | |
| auto variable = | |
| source_is_chain ? destination_access_chain : source_access_chain; | |
| auto location_in_chain = GetOperandDefinition(access_chain, 0); | |
| if (variable != location_in_chain) { | |
| // Not the same location, report independence | |
| return true; | |
| } else { | |
| // Accessing the same variable | |
| for (auto& entry : distance_vector->GetEntries()) { | |
| entry = DistanceEntry(); | |
| } | |
| return false; | |
| } | |
| } | |
| // If the access chains aren't collecting from the same structure there is no | |
| // dependence. | |
| Instruction* source_array = GetOperandDefinition(source_access_chain, 0); | |
| Instruction* destination_array = | |
| GetOperandDefinition(destination_access_chain, 0); | |
| // Nested access chains are not supported yet, bail out. | |
| if (source_array->opcode() == SpvOpAccessChain || | |
| destination_array->opcode() == SpvOpAccessChain) { | |
| for (auto& entry : distance_vector->GetEntries()) { | |
| entry = DistanceEntry(); | |
| } | |
| return false; | |
| } | |
| if (source_array != destination_array) { | |
| PrintDebug("Proved independence through different arrays."); | |
| return true; | |
| } | |
| // To handle multiple subscripts we must get every operand in the access | |
| // chains past the first. | |
| std::vector<Instruction*> source_subscripts = GetSubscripts(source); | |
| std::vector<Instruction*> destination_subscripts = GetSubscripts(destination); | |
| auto sets_of_subscripts = | |
| PartitionSubscripts(source_subscripts, destination_subscripts); | |
| auto first_coupled = std::partition( | |
| std::begin(sets_of_subscripts), std::end(sets_of_subscripts), | |
| [](const std::set<std::pair<Instruction*, Instruction*>>& set) { | |
| return set.size() == 1; | |
| }); | |
| // Go through each subscript testing for independence. | |
| // If any subscript results in independence, we prove independence between the | |
| // load and store. | |
| // If we can't prove independence we store what information we can gather in | |
| // a DistanceVector. | |
| for (auto it = std::begin(sets_of_subscripts); it < first_coupled; ++it) { | |
| auto source_subscript = std::get<0>(*(*it).begin()); | |
| auto destination_subscript = std::get<1>(*(*it).begin()); | |
| SENode* source_node = scalar_evolution_.SimplifyExpression( | |
| scalar_evolution_.AnalyzeInstruction(source_subscript)); | |
| SENode* destination_node = scalar_evolution_.SimplifyExpression( | |
| scalar_evolution_.AnalyzeInstruction(destination_subscript)); | |
| // Check the loops are in a form we support. | |
| auto subscript_pair = std::make_pair(source_node, destination_node); | |
| const Loop* loop = GetLoopForSubscriptPair(subscript_pair); | |
| if (loop) { | |
| if (!IsSupportedLoop(loop)) { | |
| PrintDebug( | |
| "GetDependence found an unsupported loop form. Assuming <=> for " | |
| "loop."); | |
| DistanceEntry* distance_entry = | |
| GetDistanceEntryForSubscriptPair(subscript_pair, distance_vector); | |
| if (distance_entry) { | |
| distance_entry->direction = DistanceEntry::Directions::ALL; | |
| } | |
| continue; | |
| } | |
| } | |
| // If either node is simplified to a CanNotCompute we can't perform any | |
| // analysis so must assume <=> dependence and return. | |
| if (source_node->GetType() == SENode::CanNotCompute || | |
| destination_node->GetType() == SENode::CanNotCompute) { | |
| // Record the <=> dependence if we can get a DistanceEntry | |
| PrintDebug( | |
| "GetDependence found source_node || destination_node as " | |
| "CanNotCompute. Abandoning evaluation for this subscript."); | |
| DistanceEntry* distance_entry = | |
| GetDistanceEntryForSubscriptPair(subscript_pair, distance_vector); | |
| if (distance_entry) { | |
| distance_entry->direction = DistanceEntry::Directions::ALL; | |
| } | |
| continue; | |
| } | |
| // We have no induction variables so can apply a ZIV test. | |
| if (IsZIV(subscript_pair)) { | |
| PrintDebug("Found a ZIV subscript pair"); | |
| if (ZIVTest(subscript_pair)) { | |
| PrintDebug("Proved independence with ZIVTest."); | |
| return true; | |
| } | |
| } | |
| // We have only one induction variable so should attempt an SIV test. | |
| if (IsSIV(subscript_pair)) { | |
| PrintDebug("Found a SIV subscript pair."); | |
| if (SIVTest(subscript_pair, distance_vector)) { | |
| PrintDebug("Proved independence with SIVTest."); | |
| return true; | |
| } | |
| } | |
| // We have multiple induction variables so should attempt an MIV test. | |
| if (IsMIV(subscript_pair)) { | |
| PrintDebug("Found a MIV subscript pair."); | |
| if (GCDMIVTest(subscript_pair)) { | |
| PrintDebug("Proved independence with the GCD test."); | |
| auto current_loops = CollectLoops(source_node, destination_node); | |
| for (auto current_loop : current_loops) { | |
| auto distance_entry = | |
| GetDistanceEntryForLoop(current_loop, distance_vector); | |
| distance_entry->direction = DistanceEntry::Directions::NONE; | |
| } | |
| return true; | |
| } | |
| } | |
| } | |
| for (auto it = first_coupled; it < std::end(sets_of_subscripts); ++it) { | |
| auto coupled_instructions = *it; | |
| std::vector<SubscriptPair> coupled_subscripts{}; | |
| for (const auto& elem : coupled_instructions) { | |
| auto source_subscript = std::get<0>(elem); | |
| auto destination_subscript = std::get<1>(elem); | |
| SENode* source_node = scalar_evolution_.SimplifyExpression( | |
| scalar_evolution_.AnalyzeInstruction(source_subscript)); | |
| SENode* destination_node = scalar_evolution_.SimplifyExpression( | |
| scalar_evolution_.AnalyzeInstruction(destination_subscript)); | |
| coupled_subscripts.push_back({source_node, destination_node}); | |
| } | |
| auto supported = true; | |
| for (const auto& subscript : coupled_subscripts) { | |
| auto loops = CollectLoops(std::get<0>(subscript), std::get<1>(subscript)); | |
| auto is_subscript_supported = | |
| std::all_of(std::begin(loops), std::end(loops), | |
| [this](const Loop* l) { return IsSupportedLoop(l); }); | |
| supported = supported && is_subscript_supported; | |
| } | |
| if (DeltaTest(coupled_subscripts, distance_vector)) { | |
| return true; | |
| } | |
| } | |
| // We were unable to prove independence so must gather all of the direction | |
| // information we found. | |
| PrintDebug( | |
| "Couldn't prove independence.\n" | |
| "All possible direction information has been collected in the input " | |
| "DistanceVector."); | |
| return false; | |
| } | |
| bool LoopDependenceAnalysis::ZIVTest( | |
| const std::pair<SENode*, SENode*>& subscript_pair) { | |
| auto source = std::get<0>(subscript_pair); | |
| auto destination = std::get<1>(subscript_pair); | |
| PrintDebug("Performing ZIVTest"); | |
| // If source == destination, dependence with direction = and distance 0. | |
| if (source == destination) { | |
| PrintDebug("ZIVTest found EQ dependence."); | |
| return false; | |
| } else { | |
| PrintDebug("ZIVTest found independence."); | |
| // Otherwise we prove independence. | |
| return true; | |
| } | |
| } | |
| bool LoopDependenceAnalysis::SIVTest( | |
| const std::pair<SENode*, SENode*>& subscript_pair, | |
| DistanceVector* distance_vector) { | |
| DistanceEntry* distance_entry = | |
| GetDistanceEntryForSubscriptPair(subscript_pair, distance_vector); | |
| if (!distance_entry) { | |
| PrintDebug( | |
| "SIVTest could not find a DistanceEntry for subscript_pair. Exiting"); | |
| } | |
| SENode* source_node = std::get<0>(subscript_pair); | |
| SENode* destination_node = std::get<1>(subscript_pair); | |
| int64_t source_induction_count = CountInductionVariables(source_node); | |
| int64_t destination_induction_count = | |
| CountInductionVariables(destination_node); | |
| // If the source node has no induction variables we can apply a | |
| // WeakZeroSrcTest. | |
| if (source_induction_count == 0) { | |
| PrintDebug("Found source has no induction variable."); | |
| if (WeakZeroSourceSIVTest( | |
| source_node, destination_node->AsSERecurrentNode(), | |
| destination_node->AsSERecurrentNode()->GetCoefficient(), | |
| distance_entry)) { | |
| PrintDebug("Proved independence with WeakZeroSourceSIVTest."); | |
| distance_entry->dependence_information = | |
| DistanceEntry::DependenceInformation::DIRECTION; | |
| distance_entry->direction = DistanceEntry::Directions::NONE; | |
| return true; | |
| } | |
| } | |
| // If the destination has no induction variables we can apply a | |
| // WeakZeroDestTest. | |
| if (destination_induction_count == 0) { | |
| PrintDebug("Found destination has no induction variable."); | |
| if (WeakZeroDestinationSIVTest( | |
| source_node->AsSERecurrentNode(), destination_node, | |
| source_node->AsSERecurrentNode()->GetCoefficient(), | |
| distance_entry)) { | |
| PrintDebug("Proved independence with WeakZeroDestinationSIVTest."); | |
| distance_entry->dependence_information = | |
| DistanceEntry::DependenceInformation::DIRECTION; | |
| distance_entry->direction = DistanceEntry::Directions::NONE; | |
| return true; | |
| } | |
| } | |
| // We now need to collect the SERecurrentExpr nodes from source and | |
| // destination. We do not handle cases where source or destination have | |
| // multiple SERecurrentExpr nodes. | |
| std::vector<SERecurrentNode*> source_recurrent_nodes = | |
| source_node->CollectRecurrentNodes(); | |
| std::vector<SERecurrentNode*> destination_recurrent_nodes = | |
| destination_node->CollectRecurrentNodes(); | |
| if (source_recurrent_nodes.size() == 1 && | |
| destination_recurrent_nodes.size() == 1) { | |
| PrintDebug("Found source and destination have 1 induction variable."); | |
| SERecurrentNode* source_recurrent_expr = *source_recurrent_nodes.begin(); | |
| SERecurrentNode* destination_recurrent_expr = | |
| *destination_recurrent_nodes.begin(); | |
| // If the coefficients are identical we can apply a StrongSIVTest. | |
| if (source_recurrent_expr->GetCoefficient() == | |
| destination_recurrent_expr->GetCoefficient()) { | |
| PrintDebug("Found source and destination share coefficient."); | |
| if (StrongSIVTest(source_node, destination_node, | |
| source_recurrent_expr->GetCoefficient(), | |
| distance_entry)) { | |
| PrintDebug("Proved independence with StrongSIVTest"); | |
| distance_entry->dependence_information = | |
| DistanceEntry::DependenceInformation::DIRECTION; | |
| distance_entry->direction = DistanceEntry::Directions::NONE; | |
| return true; | |
| } | |
| } | |
| // If the coefficients are of equal magnitude and opposite sign we can | |
| // apply a WeakCrossingSIVTest. | |
| if (source_recurrent_expr->GetCoefficient() == | |
| scalar_evolution_.CreateNegation( | |
| destination_recurrent_expr->GetCoefficient())) { | |
| PrintDebug("Found source coefficient = -destination coefficient."); | |
| if (WeakCrossingSIVTest(source_node, destination_node, | |
| source_recurrent_expr->GetCoefficient(), | |
| distance_entry)) { | |
| PrintDebug("Proved independence with WeakCrossingSIVTest"); | |
| distance_entry->dependence_information = | |
| DistanceEntry::DependenceInformation::DIRECTION; | |
| distance_entry->direction = DistanceEntry::Directions::NONE; | |
| return true; | |
| } | |
| } | |
| } | |
| return false; | |
| } | |
| bool LoopDependenceAnalysis::StrongSIVTest(SENode* source, SENode* destination, | |
| SENode* coefficient, | |
| DistanceEntry* distance_entry) { | |
| PrintDebug("Performing StrongSIVTest."); | |
| // If both source and destination are SERecurrentNodes we can perform tests | |
| // based on distance. | |
| // If either source or destination contain value unknown nodes or if one or | |
| // both are not SERecurrentNodes we must attempt a symbolic test. | |
| std::vector<SEValueUnknown*> source_value_unknown_nodes = | |
| source->CollectValueUnknownNodes(); | |
| std::vector<SEValueUnknown*> destination_value_unknown_nodes = | |
| destination->CollectValueUnknownNodes(); | |
| if (source_value_unknown_nodes.size() > 0 || | |
| destination_value_unknown_nodes.size() > 0) { | |
| PrintDebug( | |
| "StrongSIVTest found symbolics. Will attempt SymbolicStrongSIVTest."); | |
| return SymbolicStrongSIVTest(source, destination, coefficient, | |
| distance_entry); | |
| } | |
| if (!source->AsSERecurrentNode() || !destination->AsSERecurrentNode()) { | |
| PrintDebug( | |
| "StrongSIVTest could not simplify source and destination to " | |
| "SERecurrentNodes so will exit."); | |
| distance_entry->direction = DistanceEntry::Directions::ALL; | |
| return false; | |
| } | |
| // Build an SENode for distance. | |
| std::pair<SENode*, SENode*> subscript_pair = | |
| std::make_pair(source, destination); | |
| const Loop* subscript_loop = GetLoopForSubscriptPair(subscript_pair); | |
| SENode* source_constant_term = | |
| GetConstantTerm(subscript_loop, source->AsSERecurrentNode()); | |
| SENode* destination_constant_term = | |
| GetConstantTerm(subscript_loop, destination->AsSERecurrentNode()); | |
| if (!source_constant_term || !destination_constant_term) { | |
| PrintDebug( | |
| "StrongSIVTest could not collect the constant terms of either source " | |
| "or destination so will exit."); | |
| return false; | |
| } | |
| SENode* constant_term_delta = | |
| scalar_evolution_.SimplifyExpression(scalar_evolution_.CreateSubtraction( | |
| destination_constant_term, source_constant_term)); | |
| // Scalar evolution doesn't perform division, so we must fold to constants and | |
| // do it manually. | |
| // We must check the offset delta and coefficient are constants. | |
| int64_t distance = 0; | |
| SEConstantNode* delta_constant = constant_term_delta->AsSEConstantNode(); | |
| SEConstantNode* coefficient_constant = coefficient->AsSEConstantNode(); | |
| if (delta_constant && coefficient_constant) { | |
| int64_t delta_value = delta_constant->FoldToSingleValue(); | |
| int64_t coefficient_value = coefficient_constant->FoldToSingleValue(); | |
| PrintDebug( | |
| "StrongSIVTest found delta value and coefficient value as constants " | |
| "with values:\n" | |
| "\tdelta value: " + | |
| ToString(delta_value) + | |
| "\n\tcoefficient value: " + ToString(coefficient_value) + "\n"); | |
| // Check if the distance is not integral to try to prove independence. | |
| if (delta_value % coefficient_value != 0) { | |
| PrintDebug( | |
| "StrongSIVTest proved independence through distance not being an " | |
| "integer."); | |
| distance_entry->dependence_information = | |
| DistanceEntry::DependenceInformation::DIRECTION; | |
| distance_entry->direction = DistanceEntry::Directions::NONE; | |
| return true; | |
| } else { | |
| distance = delta_value / coefficient_value; | |
| PrintDebug("StrongSIV test found distance as " + ToString(distance)); | |
| } | |
| } else { | |
| // If we can't fold delta and coefficient to single values we can't produce | |
| // distance. | |
| // As a result we can't perform the rest of the pass and must assume | |
| // dependence in all directions. | |
| PrintDebug("StrongSIVTest could not produce a distance. Must exit."); | |
| distance_entry->distance = DistanceEntry::Directions::ALL; | |
| return false; | |
| } | |
| // Next we gather the upper and lower bounds as constants if possible. If | |
| // distance > upper_bound - lower_bound we prove independence. | |
| SENode* lower_bound = GetLowerBound(subscript_loop); | |
| SENode* upper_bound = GetUpperBound(subscript_loop); | |
| if (lower_bound && upper_bound) { | |
| PrintDebug("StrongSIVTest found bounds."); | |
| SENode* bounds = scalar_evolution_.SimplifyExpression( | |
| scalar_evolution_.CreateSubtraction(upper_bound, lower_bound)); | |
| if (bounds->GetType() == SENode::SENodeType::Constant) { | |
| int64_t bounds_value = bounds->AsSEConstantNode()->FoldToSingleValue(); | |
| PrintDebug( | |
| "StrongSIVTest found upper_bound - lower_bound as a constant with " | |
| "value " + | |
| ToString(bounds_value)); | |
| // If the absolute value of the distance is > upper bound - lower bound | |
| // then we prove independence. | |
| if (llabs(distance) > llabs(bounds_value)) { | |
| PrintDebug( | |
| "StrongSIVTest proved independence through distance escaping the " | |
| "loop bounds."); | |
| distance_entry->dependence_information = | |
| DistanceEntry::DependenceInformation::DISTANCE; | |
| distance_entry->direction = DistanceEntry::Directions::NONE; | |
| distance_entry->distance = distance; | |
| return true; | |
| } | |
| } | |
| } else { | |
| PrintDebug("StrongSIVTest was unable to gather lower and upper bounds."); | |
| } | |
| // Otherwise we can get a direction as follows | |
| // { < if distance > 0 | |
| // direction = { = if distance == 0 | |
| // { > if distance < 0 | |
| PrintDebug( | |
| "StrongSIVTest could not prove independence. Gathering direction " | |
| "information."); | |
| if (distance > 0) { | |
| distance_entry->dependence_information = | |
| DistanceEntry::DependenceInformation::DISTANCE; | |
| distance_entry->direction = DistanceEntry::Directions::LT; | |
| distance_entry->distance = distance; | |
| return false; | |
| } | |
| if (distance == 0) { | |
| distance_entry->dependence_information = | |
| DistanceEntry::DependenceInformation::DISTANCE; | |
| distance_entry->direction = DistanceEntry::Directions::EQ; | |
| distance_entry->distance = 0; | |
| return false; | |
| } | |
| if (distance < 0) { | |
| distance_entry->dependence_information = | |
| DistanceEntry::DependenceInformation::DISTANCE; | |
| distance_entry->direction = DistanceEntry::Directions::GT; | |
| distance_entry->distance = distance; | |
| return false; | |
| } | |
| // We were unable to prove independence or discern any additional information | |
| // Must assume <=> direction. | |
| PrintDebug( | |
| "StrongSIVTest was unable to determine any dependence information."); | |
| distance_entry->direction = DistanceEntry::Directions::ALL; | |
| return false; | |
| } | |
| bool LoopDependenceAnalysis::SymbolicStrongSIVTest( | |
| SENode* source, SENode* destination, SENode* coefficient, | |
| DistanceEntry* distance_entry) { | |
| PrintDebug("Performing SymbolicStrongSIVTest."); | |
| SENode* source_destination_delta = scalar_evolution_.SimplifyExpression( | |
| scalar_evolution_.CreateSubtraction(source, destination)); | |
| // By cancelling out the induction variables by subtracting the source and | |
| // destination we can produce an expression of symbolics and constants. This | |
| // expression can be compared to the loop bounds to find if the offset is | |
| // outwith the bounds. | |
| std::pair<SENode*, SENode*> subscript_pair = | |
| std::make_pair(source, destination); | |
| const Loop* subscript_loop = GetLoopForSubscriptPair(subscript_pair); | |
| if (IsProvablyOutsideOfLoopBounds(subscript_loop, source_destination_delta, | |
| coefficient)) { | |
| PrintDebug( | |
| "SymbolicStrongSIVTest proved independence through loop bounds."); | |
| distance_entry->dependence_information = | |
| DistanceEntry::DependenceInformation::DIRECTION; | |
| distance_entry->direction = DistanceEntry::Directions::NONE; | |
| return true; | |
| } | |
| // We were unable to prove independence or discern any additional information. | |
| // Must assume <=> direction. | |
| PrintDebug( | |
| "SymbolicStrongSIVTest was unable to determine any dependence " | |
| "information."); | |
| distance_entry->direction = DistanceEntry::Directions::ALL; | |
| return false; | |
| } | |
| bool LoopDependenceAnalysis::WeakZeroSourceSIVTest( | |
| SENode* source, SERecurrentNode* destination, SENode* coefficient, | |
| DistanceEntry* distance_entry) { | |
| PrintDebug("Performing WeakZeroSourceSIVTest."); | |
| std::pair<SENode*, SENode*> subscript_pair = | |
| std::make_pair(source, destination); | |
| const Loop* subscript_loop = GetLoopForSubscriptPair(subscript_pair); | |
| // Build an SENode for distance. | |
| SENode* destination_constant_term = | |
| GetConstantTerm(subscript_loop, destination); | |
| SENode* delta = scalar_evolution_.SimplifyExpression( | |
| scalar_evolution_.CreateSubtraction(source, destination_constant_term)); | |
| // Scalar evolution doesn't perform division, so we must fold to constants and | |
| // do it manually. | |
| int64_t distance = 0; | |
| SEConstantNode* delta_constant = delta->AsSEConstantNode(); | |
| SEConstantNode* coefficient_constant = coefficient->AsSEConstantNode(); | |
| if (delta_constant && coefficient_constant) { | |
| PrintDebug( | |
| "WeakZeroSourceSIVTest folding delta and coefficient to constants."); | |
| int64_t delta_value = delta_constant->FoldToSingleValue(); | |
| int64_t coefficient_value = coefficient_constant->FoldToSingleValue(); | |
| // Check if the distance is not integral. | |
| if (delta_value % coefficient_value != 0) { | |
| PrintDebug( | |
| "WeakZeroSourceSIVTest proved independence through distance not " | |
| "being an integer."); | |
| distance_entry->dependence_information = | |
| DistanceEntry::DependenceInformation::DIRECTION; | |
| distance_entry->direction = DistanceEntry::Directions::NONE; | |
| return true; | |
| } else { | |
| distance = delta_value / coefficient_value; | |
| PrintDebug( | |
| "WeakZeroSourceSIVTest calculated distance with the following " | |
| "values\n" | |
| "\tdelta value: " + | |
| ToString(delta_value) + | |
| "\n\tcoefficient value: " + ToString(coefficient_value) + | |
| "\n\tdistance: " + ToString(distance) + "\n"); | |
| } | |
| } else { | |
| PrintDebug( | |
| "WeakZeroSourceSIVTest was unable to fold delta and coefficient to " | |
| "constants."); | |
| } | |
| // If we can prove the distance is outside the bounds we prove independence. | |
| SEConstantNode* lower_bound = | |
| GetLowerBound(subscript_loop)->AsSEConstantNode(); | |
| SEConstantNode* upper_bound = | |
| GetUpperBound(subscript_loop)->AsSEConstantNode(); | |
| if (lower_bound && upper_bound) { | |
| PrintDebug("WeakZeroSourceSIVTest found bounds as SEConstantNodes."); | |
| int64_t lower_bound_value = lower_bound->FoldToSingleValue(); | |
| int64_t upper_bound_value = upper_bound->FoldToSingleValue(); | |
| if (!IsWithinBounds(llabs(distance), lower_bound_value, | |
| upper_bound_value)) { | |
| PrintDebug( | |
| "WeakZeroSourceSIVTest proved independence through distance escaping " | |
| "the loop bounds."); | |
| PrintDebug( | |
| "Bound values were as follow\n" | |
| "\tlower bound value: " + | |
| ToString(lower_bound_value) + | |
| "\n\tupper bound value: " + ToString(upper_bound_value) + | |
| "\n\tdistance value: " + ToString(distance) + "\n"); | |
| distance_entry->dependence_information = | |
| DistanceEntry::DependenceInformation::DISTANCE; | |
| distance_entry->direction = DistanceEntry::Directions::NONE; | |
| distance_entry->distance = distance; | |
| return true; | |
| } | |
| } else { | |
| PrintDebug( | |
| "WeakZeroSourceSIVTest was unable to find lower and upper bound as " | |
| "SEConstantNodes."); | |
| } | |
| // Now we want to see if we can detect to peel the first or last iterations. | |
| // We get the FirstTripValue as GetFirstTripInductionNode() + | |
| // GetConstantTerm(destination) | |
| SENode* first_trip_SENode = | |
| scalar_evolution_.SimplifyExpression(scalar_evolution_.CreateAddNode( | |
| GetFirstTripInductionNode(subscript_loop), | |
| GetConstantTerm(subscript_loop, destination))); | |
| // If source == FirstTripValue, peel_first. | |
| if (first_trip_SENode) { | |
| PrintDebug("WeakZeroSourceSIVTest built first_trip_SENode."); | |
| if (first_trip_SENode->AsSEConstantNode()) { | |
| PrintDebug( | |
| "WeakZeroSourceSIVTest has found first_trip_SENode as an " | |
| "SEConstantNode with value: " + | |
| ToString(first_trip_SENode->AsSEConstantNode()->FoldToSingleValue()) + | |
| "\n"); | |
| } | |
| if (source == first_trip_SENode) { | |
| // We have found that peeling the first iteration will break dependency. | |
| PrintDebug( | |
| "WeakZeroSourceSIVTest has found peeling first iteration will break " | |
| "dependency"); | |
| distance_entry->dependence_information = | |
| DistanceEntry::DependenceInformation::PEEL; | |
| distance_entry->peel_first = true; | |
| return false; | |
| } | |
| } else { | |
| PrintDebug("WeakZeroSourceSIVTest was unable to build first_trip_SENode"); | |
| } | |
| // We get the LastTripValue as GetFinalTripInductionNode(coefficient) + | |
| // GetConstantTerm(destination) | |
| SENode* final_trip_SENode = | |
| scalar_evolution_.SimplifyExpression(scalar_evolution_.CreateAddNode( | |
| GetFinalTripInductionNode(subscript_loop, coefficient), | |
| GetConstantTerm(subscript_loop, destination))); | |
| // If source == LastTripValue, peel_last. | |
| if (final_trip_SENode) { | |
| PrintDebug("WeakZeroSourceSIVTest built final_trip_SENode."); | |
| if (first_trip_SENode->AsSEConstantNode()) { | |
| PrintDebug( | |
| "WeakZeroSourceSIVTest has found final_trip_SENode as an " | |
| "SEConstantNode with value: " + | |
| ToString(final_trip_SENode->AsSEConstantNode()->FoldToSingleValue()) + | |
| "\n"); | |
| } | |
| if (source == final_trip_SENode) { | |
| // We have found that peeling the last iteration will break dependency. | |
| PrintDebug( | |
| "WeakZeroSourceSIVTest has found peeling final iteration will break " | |
| "dependency"); | |
| distance_entry->dependence_information = | |
| DistanceEntry::DependenceInformation::PEEL; | |
| distance_entry->peel_last = true; | |
| return false; | |
| } | |
| } else { | |
| PrintDebug("WeakZeroSourceSIVTest was unable to build final_trip_SENode"); | |
| } | |
| // We were unable to prove independence or discern any additional information. | |
| // Must assume <=> direction. | |
| PrintDebug( | |
| "WeakZeroSourceSIVTest was unable to determine any dependence " | |
| "information."); | |
| distance_entry->direction = DistanceEntry::Directions::ALL; | |
| return false; | |
| } | |
| bool LoopDependenceAnalysis::WeakZeroDestinationSIVTest( | |
| SERecurrentNode* source, SENode* destination, SENode* coefficient, | |
| DistanceEntry* distance_entry) { | |
| PrintDebug("Performing WeakZeroDestinationSIVTest."); | |
| // Build an SENode for distance. | |
| std::pair<SENode*, SENode*> subscript_pair = | |
| std::make_pair(source, destination); | |
| const Loop* subscript_loop = GetLoopForSubscriptPair(subscript_pair); | |
| SENode* source_constant_term = GetConstantTerm(subscript_loop, source); | |
| SENode* delta = scalar_evolution_.SimplifyExpression( | |
| scalar_evolution_.CreateSubtraction(destination, source_constant_term)); | |
| // Scalar evolution doesn't perform division, so we must fold to constants and | |
| // do it manually. | |
| int64_t distance = 0; | |
| SEConstantNode* delta_constant = delta->AsSEConstantNode(); | |
| SEConstantNode* coefficient_constant = coefficient->AsSEConstantNode(); | |
| if (delta_constant && coefficient_constant) { | |
| PrintDebug( | |
| "WeakZeroDestinationSIVTest folding delta and coefficient to " | |
| "constants."); | |
| int64_t delta_value = delta_constant->FoldToSingleValue(); | |
| int64_t coefficient_value = coefficient_constant->FoldToSingleValue(); | |
| // Check if the distance is not integral. | |
| if (delta_value % coefficient_value != 0) { | |
| PrintDebug( | |
| "WeakZeroDestinationSIVTest proved independence through distance not " | |
| "being an integer."); | |
| distance_entry->dependence_information = | |
| DistanceEntry::DependenceInformation::DIRECTION; | |
| distance_entry->direction = DistanceEntry::Directions::NONE; | |
| return true; | |
| } else { | |
| distance = delta_value / coefficient_value; | |
| PrintDebug( | |
| "WeakZeroDestinationSIVTest calculated distance with the following " | |
| "values\n" | |
| "\tdelta value: " + | |
| ToString(delta_value) + | |
| "\n\tcoefficient value: " + ToString(coefficient_value) + | |
| "\n\tdistance: " + ToString(distance) + "\n"); | |
| } | |
| } else { | |
| PrintDebug( | |
| "WeakZeroDestinationSIVTest was unable to fold delta and coefficient " | |
| "to constants."); | |
| } | |
| // If we can prove the distance is outside the bounds we prove independence. | |
| SEConstantNode* lower_bound = | |
| GetLowerBound(subscript_loop)->AsSEConstantNode(); | |
| SEConstantNode* upper_bound = | |
| GetUpperBound(subscript_loop)->AsSEConstantNode(); | |
| if (lower_bound && upper_bound) { | |
| PrintDebug("WeakZeroDestinationSIVTest found bounds as SEConstantNodes."); | |
| int64_t lower_bound_value = lower_bound->FoldToSingleValue(); | |
| int64_t upper_bound_value = upper_bound->FoldToSingleValue(); | |
| if (!IsWithinBounds(llabs(distance), lower_bound_value, | |
| upper_bound_value)) { | |
| PrintDebug( | |
| "WeakZeroDestinationSIVTest proved independence through distance " | |
| "escaping the loop bounds."); | |
| PrintDebug( | |
| "Bound values were as follows\n" | |
| "\tlower bound value: " + | |
| ToString(lower_bound_value) + | |
| "\n\tupper bound value: " + ToString(upper_bound_value) + | |
| "\n\tdistance value: " + ToString(distance)); | |
| distance_entry->dependence_information = | |
| DistanceEntry::DependenceInformation::DISTANCE; | |
| distance_entry->direction = DistanceEntry::Directions::NONE; | |
| distance_entry->distance = distance; | |
| return true; | |
| } | |
| } else { | |
| PrintDebug( | |
| "WeakZeroDestinationSIVTest was unable to find lower and upper bound " | |
| "as SEConstantNodes."); | |
| } | |
| // Now we want to see if we can detect to peel the first or last iterations. | |
| // We get the FirstTripValue as GetFirstTripInductionNode() + | |
| // GetConstantTerm(source) | |
| SENode* first_trip_SENode = scalar_evolution_.SimplifyExpression( | |
| scalar_evolution_.CreateAddNode(GetFirstTripInductionNode(subscript_loop), | |
| GetConstantTerm(subscript_loop, source))); | |
| // If destination == FirstTripValue, peel_first. | |
| if (first_trip_SENode) { | |
| PrintDebug("WeakZeroDestinationSIVTest built first_trip_SENode."); | |
| if (first_trip_SENode->AsSEConstantNode()) { | |
| PrintDebug( | |
| "WeakZeroDestinationSIVTest has found first_trip_SENode as an " | |
| "SEConstantNode with value: " + | |
| ToString(first_trip_SENode->AsSEConstantNode()->FoldToSingleValue()) + | |
| "\n"); | |
| } | |
| if (destination == first_trip_SENode) { | |
| // We have found that peeling the first iteration will break dependency. | |
| PrintDebug( | |
| "WeakZeroDestinationSIVTest has found peeling first iteration will " | |
| "break dependency"); | |
| distance_entry->dependence_information = | |
| DistanceEntry::DependenceInformation::PEEL; | |
| distance_entry->peel_first = true; | |
| return false; | |
| } | |
| } else { | |
| PrintDebug( | |
| "WeakZeroDestinationSIVTest was unable to build first_trip_SENode"); | |
| } | |
| // We get the LastTripValue as GetFinalTripInductionNode(coefficient) + | |
| // GetConstantTerm(source) | |
| SENode* final_trip_SENode = | |
| scalar_evolution_.SimplifyExpression(scalar_evolution_.CreateAddNode( | |
| GetFinalTripInductionNode(subscript_loop, coefficient), | |
| GetConstantTerm(subscript_loop, source))); | |
| // If destination == LastTripValue, peel_last. | |
| if (final_trip_SENode) { | |
| PrintDebug("WeakZeroDestinationSIVTest built final_trip_SENode."); | |
| if (final_trip_SENode->AsSEConstantNode()) { | |
| PrintDebug( | |
| "WeakZeroDestinationSIVTest has found final_trip_SENode as an " | |
| "SEConstantNode with value: " + | |
| ToString(final_trip_SENode->AsSEConstantNode()->FoldToSingleValue()) + | |
| "\n"); | |
| } | |
| if (destination == final_trip_SENode) { | |
| // We have found that peeling the last iteration will break dependency. | |
| PrintDebug( | |
| "WeakZeroDestinationSIVTest has found peeling final iteration will " | |
| "break dependency"); | |
| distance_entry->dependence_information = | |
| DistanceEntry::DependenceInformation::PEEL; | |
| distance_entry->peel_last = true; | |
| return false; | |
| } | |
| } else { | |
| PrintDebug( | |
| "WeakZeroDestinationSIVTest was unable to build final_trip_SENode"); | |
| } | |
| // We were unable to prove independence or discern any additional information. | |
| // Must assume <=> direction. | |
| PrintDebug( | |
| "WeakZeroDestinationSIVTest was unable to determine any dependence " | |
| "information."); | |
| distance_entry->direction = DistanceEntry::Directions::ALL; | |
| return false; | |
| } | |
| bool LoopDependenceAnalysis::WeakCrossingSIVTest( | |
| SENode* source, SENode* destination, SENode* coefficient, | |
| DistanceEntry* distance_entry) { | |
| PrintDebug("Performing WeakCrossingSIVTest."); | |
| // We currently can't handle symbolic WeakCrossingSIVTests. If either source | |
| // or destination are not SERecurrentNodes we must exit. | |
| if (!source->AsSERecurrentNode() || !destination->AsSERecurrentNode()) { | |
| PrintDebug( | |
| "WeakCrossingSIVTest found source or destination != SERecurrentNode. " | |
| "Exiting"); | |
| distance_entry->direction = DistanceEntry::Directions::ALL; | |
| return false; | |
| } | |
| // Build an SENode for distance. | |
| SENode* offset_delta = | |
| scalar_evolution_.SimplifyExpression(scalar_evolution_.CreateSubtraction( | |
| destination->AsSERecurrentNode()->GetOffset(), | |
| source->AsSERecurrentNode()->GetOffset())); | |
| // Scalar evolution doesn't perform division, so we must fold to constants and | |
| // do it manually. | |
| int64_t distance = 0; | |
| SEConstantNode* delta_constant = offset_delta->AsSEConstantNode(); | |
| SEConstantNode* coefficient_constant = coefficient->AsSEConstantNode(); | |
| if (delta_constant && coefficient_constant) { | |
| PrintDebug( | |
| "WeakCrossingSIVTest folding offset_delta and coefficient to " | |
| "constants."); | |
| int64_t delta_value = delta_constant->FoldToSingleValue(); | |
| int64_t coefficient_value = coefficient_constant->FoldToSingleValue(); | |
| // Check if the distance is not integral or if it has a non-integral part | |
| // equal to 1/2. | |
| if (delta_value % (2 * coefficient_value) != 0 && | |
| static_cast<float>(delta_value % (2 * coefficient_value)) / | |
| static_cast<float>(2 * coefficient_value) != | |
| 0.5) { | |
| PrintDebug( | |
| "WeakCrossingSIVTest proved independence through distance escaping " | |
| "the loop bounds."); | |
| distance_entry->dependence_information = | |
| DistanceEntry::DependenceInformation::DIRECTION; | |
| distance_entry->direction = DistanceEntry::Directions::NONE; | |
| return true; | |
| } else { | |
| distance = delta_value / (2 * coefficient_value); | |
| } | |
| if (distance == 0) { | |
| PrintDebug("WeakCrossingSIVTest found EQ dependence."); | |
| distance_entry->dependence_information = | |
| DistanceEntry::DependenceInformation::DISTANCE; | |
| distance_entry->direction = DistanceEntry::Directions::EQ; | |
| distance_entry->distance = 0; | |
| return false; | |
| } | |
| } else { | |
| PrintDebug( | |
| "WeakCrossingSIVTest was unable to fold offset_delta and coefficient " | |
| "to constants."); | |
| } | |
| // We were unable to prove independence or discern any additional information. | |
| // Must assume <=> direction. | |
| PrintDebug( | |
| "WeakCrossingSIVTest was unable to determine any dependence " | |
| "information."); | |
| distance_entry->direction = DistanceEntry::Directions::ALL; | |
| return false; | |
| } | |
| // Perform the GCD test if both, the source and the destination nodes, are in | |
| // the form a0*i0 + a1*i1 + ... an*in + c. | |
| bool LoopDependenceAnalysis::GCDMIVTest( | |
| const std::pair<SENode*, SENode*>& subscript_pair) { | |
| auto source = std::get<0>(subscript_pair); | |
| auto destination = std::get<1>(subscript_pair); | |
| // Bail out if source/destination is in an unexpected form. | |
| if (!IsInCorrectFormForGCDTest(source) || | |
| !IsInCorrectFormForGCDTest(destination)) { | |
| return false; | |
| } | |
| auto source_recurrences = GetAllTopLevelRecurrences(source); | |
| auto dest_recurrences = GetAllTopLevelRecurrences(destination); | |
| // Bail out if all offsets and coefficients aren't constant. | |
| if (!AreOffsetsAndCoefficientsConstant(source_recurrences) || | |
| !AreOffsetsAndCoefficientsConstant(dest_recurrences)) { | |
| return false; | |
| } | |
| // Calculate the GCD of all coefficients. | |
| auto source_constants = GetAllTopLevelConstants(source); | |
| int64_t source_constant = | |
| CalculateConstantTerm(source_recurrences, source_constants); | |
| auto dest_constants = GetAllTopLevelConstants(destination); | |
| int64_t destination_constant = | |
| CalculateConstantTerm(dest_recurrences, dest_constants); | |
| int64_t delta = std::abs(source_constant - destination_constant); | |
| int64_t running_gcd = 0; | |
| running_gcd = CalculateGCDFromCoefficients(source_recurrences, running_gcd); | |
| running_gcd = CalculateGCDFromCoefficients(dest_recurrences, running_gcd); | |
| return delta % running_gcd != 0; | |
| } | |
| using PartitionedSubscripts = | |
| std::vector<std::set<std::pair<Instruction*, Instruction*>>>; | |
| PartitionedSubscripts LoopDependenceAnalysis::PartitionSubscripts( | |
| const std::vector<Instruction*>& source_subscripts, | |
| const std::vector<Instruction*>& destination_subscripts) { | |
| PartitionedSubscripts partitions{}; | |
| auto num_subscripts = source_subscripts.size(); | |
| // Create initial partitions with one subscript pair per partition. | |
| for (size_t i = 0; i < num_subscripts; ++i) { | |
| partitions.push_back({{source_subscripts[i], destination_subscripts[i]}}); | |
| } | |
| // Iterate over the loops to create all partitions | |
| for (auto loop : loops_) { | |
| int64_t k = -1; | |
| for (size_t j = 0; j < partitions.size(); ++j) { | |
| auto& current_partition = partitions[j]; | |
| // Does |loop| appear in |current_partition| | |
| auto it = std::find_if( | |
| current_partition.begin(), current_partition.end(), | |
| [loop, | |
| this](const std::pair<Instruction*, Instruction*>& elem) -> bool { | |
| auto source_recurrences = | |
| scalar_evolution_.AnalyzeInstruction(std::get<0>(elem)) | |
| ->CollectRecurrentNodes(); | |
| auto destination_recurrences = | |
| scalar_evolution_.AnalyzeInstruction(std::get<1>(elem)) | |
| ->CollectRecurrentNodes(); | |
| source_recurrences.insert(source_recurrences.end(), | |
| destination_recurrences.begin(), | |
| destination_recurrences.end()); | |
| auto loops_in_pair = CollectLoops(source_recurrences); | |
| auto end_it = loops_in_pair.end(); | |
| return std::find(loops_in_pair.begin(), end_it, loop) != end_it; | |
| }); | |
| auto has_loop = it != current_partition.end(); | |
| if (has_loop) { | |
| if (k == -1) { | |
| k = j; | |
| } else { | |
| // Add |partitions[j]| to |partitions[k]| and discard |partitions[j]| | |
| partitions[static_cast<size_t>(k)].insert(current_partition.begin(), | |
| current_partition.end()); | |
| current_partition.clear(); | |
| } | |
| } | |
| } | |
| } | |
| // Remove empty (discarded) partitions | |
| partitions.erase( | |
| std::remove_if( | |
| partitions.begin(), partitions.end(), | |
| [](const std::set<std::pair<Instruction*, Instruction*>>& partition) { | |
| return partition.empty(); | |
| }), | |
| partitions.end()); | |
| return partitions; | |
| } | |
| Constraint* LoopDependenceAnalysis::IntersectConstraints( | |
| Constraint* constraint_0, Constraint* constraint_1, | |
| const SENode* lower_bound, const SENode* upper_bound) { | |
| if (constraint_0->AsDependenceNone()) { | |
| return constraint_1; | |
| } else if (constraint_1->AsDependenceNone()) { | |
| return constraint_0; | |
| } | |
| // Both constraints are distances. Either the same distance or independent. | |
| if (constraint_0->AsDependenceDistance() && | |
| constraint_1->AsDependenceDistance()) { | |
| auto dist_0 = constraint_0->AsDependenceDistance(); | |
| auto dist_1 = constraint_1->AsDependenceDistance(); | |
| if (*dist_0->GetDistance() == *dist_1->GetDistance()) { | |
| return constraint_0; | |
| } else { | |
| return make_constraint<DependenceEmpty>(); | |
| } | |
| } | |
| // Both constraints are points. Either the same point or independent. | |
| if (constraint_0->AsDependencePoint() && constraint_1->AsDependencePoint()) { | |
| auto point_0 = constraint_0->AsDependencePoint(); | |
| auto point_1 = constraint_1->AsDependencePoint(); | |
| if (*point_0->GetSource() == *point_1->GetSource() && | |
| *point_0->GetDestination() == *point_1->GetDestination()) { | |
| return constraint_0; | |
| } else { | |
| return make_constraint<DependenceEmpty>(); | |
| } | |
| } | |
| // Both constraints are lines/distances. | |
| if ((constraint_0->AsDependenceDistance() || | |
| constraint_0->AsDependenceLine()) && | |
| (constraint_1->AsDependenceDistance() || | |
| constraint_1->AsDependenceLine())) { | |
| auto is_distance_0 = constraint_0->AsDependenceDistance() != nullptr; | |
| auto is_distance_1 = constraint_1->AsDependenceDistance() != nullptr; | |
| auto a0 = is_distance_0 ? scalar_evolution_.CreateConstant(1) | |
| : constraint_0->AsDependenceLine()->GetA(); | |
| auto b0 = is_distance_0 ? scalar_evolution_.CreateConstant(-1) | |
| : constraint_0->AsDependenceLine()->GetB(); | |
| auto c0 = | |
| is_distance_0 | |
| ? scalar_evolution_.SimplifyExpression( | |
| scalar_evolution_.CreateNegation( | |
| constraint_0->AsDependenceDistance()->GetDistance())) | |
| : constraint_0->AsDependenceLine()->GetC(); | |
| auto a1 = is_distance_1 ? scalar_evolution_.CreateConstant(1) | |
| : constraint_1->AsDependenceLine()->GetA(); | |
| auto b1 = is_distance_1 ? scalar_evolution_.CreateConstant(-1) | |
| : constraint_1->AsDependenceLine()->GetB(); | |
| auto c1 = | |
| is_distance_1 | |
| ? scalar_evolution_.SimplifyExpression( | |
| scalar_evolution_.CreateNegation( | |
| constraint_1->AsDependenceDistance()->GetDistance())) | |
| : constraint_1->AsDependenceLine()->GetC(); | |
| if (a0->AsSEConstantNode() && b0->AsSEConstantNode() && | |
| c0->AsSEConstantNode() && a1->AsSEConstantNode() && | |
| b1->AsSEConstantNode() && c1->AsSEConstantNode()) { | |
| auto constant_a0 = a0->AsSEConstantNode()->FoldToSingleValue(); | |
| auto constant_b0 = b0->AsSEConstantNode()->FoldToSingleValue(); | |
| auto constant_c0 = c0->AsSEConstantNode()->FoldToSingleValue(); | |
| auto constant_a1 = a1->AsSEConstantNode()->FoldToSingleValue(); | |
| auto constant_b1 = b1->AsSEConstantNode()->FoldToSingleValue(); | |
| auto constant_c1 = c1->AsSEConstantNode()->FoldToSingleValue(); | |
| // a & b can't both be zero, otherwise it wouldn't be line. | |
| if (NormalizeAndCompareFractions(constant_a0, constant_b0, constant_a1, | |
| constant_b1)) { | |
| // Slopes are equal, either parallel lines or the same line. | |
| if (constant_b0 == 0 && constant_b1 == 0) { | |
| if (NormalizeAndCompareFractions(constant_c0, constant_a0, | |
| constant_c1, constant_a1)) { | |
| return constraint_0; | |
| } | |
| return make_constraint<DependenceEmpty>(); | |
| } else if (NormalizeAndCompareFractions(constant_c0, constant_b0, | |
| constant_c1, constant_b1)) { | |
| // Same line. | |
| return constraint_0; | |
| } else { | |
| // Parallel lines can't intersect, report independence. | |
| return make_constraint<DependenceEmpty>(); | |
| } | |
| } else { | |
| // Lines are not parallel, therefore, they must intersect. | |
| // Calculate intersection. | |
| if (upper_bound->AsSEConstantNode() && | |
| lower_bound->AsSEConstantNode()) { | |
| auto constant_lower_bound = | |
| lower_bound->AsSEConstantNode()->FoldToSingleValue(); | |
| auto constant_upper_bound = | |
| upper_bound->AsSEConstantNode()->FoldToSingleValue(); | |
| auto up = constant_b1 * constant_c0 - constant_b0 * constant_c1; | |
| // Both b or both a can't be 0, so down is never 0 | |
| // otherwise would have entered the parallel line section. | |
| auto down = constant_b1 * constant_a0 - constant_b0 * constant_a1; | |
| auto x_coord = up / down; | |
| int64_t y_coord = 0; | |
| int64_t arg1 = 0; | |
| int64_t const_b_to_use = 0; | |
| if (constant_b1 != 0) { | |
| arg1 = constant_c1 - constant_a1 * x_coord; | |
| y_coord = arg1 / constant_b1; | |
| const_b_to_use = constant_b1; | |
| } else if (constant_b0 != 0) { | |
| arg1 = constant_c0 - constant_a0 * x_coord; | |
| y_coord = arg1 / constant_b0; | |
| const_b_to_use = constant_b0; | |
| } | |
| if (up % down == 0 && | |
| arg1 % const_b_to_use == 0 && // Coordinates are integers. | |
| constant_lower_bound <= | |
| x_coord && // x_coord is within loop bounds. | |
| x_coord <= constant_upper_bound && | |
| constant_lower_bound <= | |
| y_coord && // y_coord is within loop bounds. | |
| y_coord <= constant_upper_bound) { | |
| // Lines intersect at integer coordinates. | |
| return make_constraint<DependencePoint>( | |
| scalar_evolution_.CreateConstant(x_coord), | |
| scalar_evolution_.CreateConstant(y_coord), | |
| constraint_0->GetLoop()); | |
| } else { | |
| return make_constraint<DependenceEmpty>(); | |
| } | |
| } else { | |
| // Not constants, bail out. | |
| return make_constraint<DependenceNone>(); | |
| } | |
| } | |
| } else { | |
| // Not constants, bail out. | |
| return make_constraint<DependenceNone>(); | |
| } | |
| } | |
| // One constraint is a line/distance and the other is a point. | |
| if ((constraint_0->AsDependencePoint() && | |
| (constraint_1->AsDependenceLine() || | |
| constraint_1->AsDependenceDistance())) || | |
| (constraint_1->AsDependencePoint() && | |
| (constraint_0->AsDependenceLine() || | |
| constraint_0->AsDependenceDistance()))) { | |
| auto point_0 = constraint_0->AsDependencePoint() != nullptr; | |
| auto point = point_0 ? constraint_0->AsDependencePoint() | |
| : constraint_1->AsDependencePoint(); | |
| auto line_or_distance = point_0 ? constraint_1 : constraint_0; | |
| auto is_distance = line_or_distance->AsDependenceDistance() != nullptr; | |
| auto a = is_distance ? scalar_evolution_.CreateConstant(1) | |
| : line_or_distance->AsDependenceLine()->GetA(); | |
| auto b = is_distance ? scalar_evolution_.CreateConstant(-1) | |
| : line_or_distance->AsDependenceLine()->GetB(); | |
| auto c = | |
| is_distance | |
| ? scalar_evolution_.SimplifyExpression( | |
| scalar_evolution_.CreateNegation( | |
| line_or_distance->AsDependenceDistance()->GetDistance())) | |
| : line_or_distance->AsDependenceLine()->GetC(); | |
| auto x = point->GetSource(); | |
| auto y = point->GetDestination(); | |
| if (a->AsSEConstantNode() && b->AsSEConstantNode() && | |
| c->AsSEConstantNode() && x->AsSEConstantNode() && | |
| y->AsSEConstantNode()) { | |
| auto constant_a = a->AsSEConstantNode()->FoldToSingleValue(); | |
| auto constant_b = b->AsSEConstantNode()->FoldToSingleValue(); | |
| auto constant_c = c->AsSEConstantNode()->FoldToSingleValue(); | |
| auto constant_x = x->AsSEConstantNode()->FoldToSingleValue(); | |
| auto constant_y = y->AsSEConstantNode()->FoldToSingleValue(); | |
| auto left_hand_side = constant_a * constant_x + constant_b * constant_y; | |
| if (left_hand_side == constant_c) { | |
| // Point is on line, return point | |
| return point_0 ? constraint_0 : constraint_1; | |
| } else { | |
| // Point not on line, report independence (empty constraint). | |
| return make_constraint<DependenceEmpty>(); | |
| } | |
| } else { | |
| // Not constants, bail out. | |
| return make_constraint<DependenceNone>(); | |
| } | |
| } | |
| return nullptr; | |
| } | |
| // Propagate constraints function as described in section 5 of Practical | |
| // Dependence Testing, Goff, Kennedy, Tseng, 1991. | |
| SubscriptPair LoopDependenceAnalysis::PropagateConstraints( | |
| const SubscriptPair& subscript_pair, | |
| const std::vector<Constraint*>& constraints) { | |
| SENode* new_first = subscript_pair.first; | |
| SENode* new_second = subscript_pair.second; | |
| for (auto& constraint : constraints) { | |
| // In the paper this is a[k]. We're extracting the coefficient ('a') of a | |
| // recurrent expression with respect to the loop 'k'. | |
| SENode* coefficient_of_recurrent = | |
| scalar_evolution_.GetCoefficientFromRecurrentTerm( | |
| new_first, constraint->GetLoop()); | |
| // In the paper this is a'[k]. | |
| SENode* coefficient_of_recurrent_prime = | |
| scalar_evolution_.GetCoefficientFromRecurrentTerm( | |
| new_second, constraint->GetLoop()); | |
| if (constraint->GetType() == Constraint::Distance) { | |
| DependenceDistance* as_distance = constraint->AsDependenceDistance(); | |
| // In the paper this is a[k]*d | |
| SENode* rhs = scalar_evolution_.CreateMultiplyNode( | |
| coefficient_of_recurrent, as_distance->GetDistance()); | |
| // In the paper this is a[k] <- 0 | |
| SENode* zeroed_coefficient = | |
| scalar_evolution_.BuildGraphWithoutRecurrentTerm( | |
| new_first, constraint->GetLoop()); | |
| // In the paper this is e <- e - a[k]*d. | |
| new_first = scalar_evolution_.CreateSubtraction(zeroed_coefficient, rhs); | |
| new_first = scalar_evolution_.SimplifyExpression(new_first); | |
| // In the paper this is a'[k] - a[k]. | |
| SENode* new_child = scalar_evolution_.SimplifyExpression( | |
| scalar_evolution_.CreateSubtraction(coefficient_of_recurrent_prime, | |
| coefficient_of_recurrent)); | |
| // In the paper this is a'[k]'i[k]. | |
| SERecurrentNode* prime_recurrent = | |
| scalar_evolution_.GetRecurrentTerm(new_second, constraint->GetLoop()); | |
| if (!prime_recurrent) continue; | |
| // As we hash the nodes we need to create a new node when we update a | |
| // child. | |
| SENode* new_recurrent = scalar_evolution_.CreateRecurrentExpression( | |
| constraint->GetLoop(), prime_recurrent->GetOffset(), new_child); | |
| // In the paper this is a'[k] <- a'[k] - a[k]. | |
| new_second = scalar_evolution_.UpdateChildNode( | |
| new_second, prime_recurrent, new_recurrent); | |
| } | |
| } | |
| new_second = scalar_evolution_.SimplifyExpression(new_second); | |
| return std::make_pair(new_first, new_second); | |
| } | |
| bool LoopDependenceAnalysis::DeltaTest( | |
| const std::vector<SubscriptPair>& coupled_subscripts, | |
| DistanceVector* dv_entry) { | |
| std::vector<Constraint*> constraints(loops_.size()); | |
| std::vector<bool> loop_appeared(loops_.size()); | |
| std::generate(std::begin(constraints), std::end(constraints), | |
| [this]() { return make_constraint<DependenceNone>(); }); | |
| // Separate SIV and MIV subscripts | |
| std::vector<SubscriptPair> siv_subscripts{}; | |
| std::vector<SubscriptPair> miv_subscripts{}; | |
| for (const auto& subscript_pair : coupled_subscripts) { | |
| if (IsSIV(subscript_pair)) { | |
| siv_subscripts.push_back(subscript_pair); | |
| } else { | |
| miv_subscripts.push_back(subscript_pair); | |
| } | |
| } | |
| // Delta Test | |
| while (!siv_subscripts.empty()) { | |
| std::vector<bool> results(siv_subscripts.size()); | |
| std::vector<DistanceVector> current_distances( | |
| siv_subscripts.size(), DistanceVector(loops_.size())); | |
| // Apply SIV test to all SIV subscripts, report independence if any of them | |
| // is independent | |
| std::transform( | |
| std::begin(siv_subscripts), std::end(siv_subscripts), | |
| std::begin(current_distances), std::begin(results), | |
| [this](SubscriptPair& p, DistanceVector& d) { return SIVTest(p, &d); }); | |
| if (std::accumulate(std::begin(results), std::end(results), false, | |
| std::logical_or<bool>{})) { | |
| return true; | |
| } | |
| // Derive new constraint vector. | |
| std::vector<std::pair<Constraint*, size_t>> all_new_constrants{}; | |
| for (size_t i = 0; i < siv_subscripts.size(); ++i) { | |
| auto loop = GetLoopForSubscriptPair(siv_subscripts[i]); | |
| auto loop_id = | |
| std::distance(std::begin(loops_), | |
| std::find(std::begin(loops_), std::end(loops_), loop)); | |
| loop_appeared[loop_id] = true; | |
| auto distance_entry = current_distances[i].GetEntries()[loop_id]; | |
| if (distance_entry.dependence_information == | |
| DistanceEntry::DependenceInformation::DISTANCE) { | |
| // Construct a DependenceDistance. | |
| auto node = scalar_evolution_.CreateConstant(distance_entry.distance); | |
| all_new_constrants.push_back( | |
| {make_constraint<DependenceDistance>(node, loop), loop_id}); | |
| } else { | |
| // Construct a DependenceLine. | |
| const auto& subscript_pair = siv_subscripts[i]; | |
| SENode* source_node = std::get<0>(subscript_pair); | |
| SENode* destination_node = std::get<1>(subscript_pair); | |
| int64_t source_induction_count = CountInductionVariables(source_node); | |
| int64_t destination_induction_count = | |
| CountInductionVariables(destination_node); | |
| SENode* a = nullptr; | |
| SENode* b = nullptr; | |
| SENode* c = nullptr; | |
| if (destination_induction_count != 0) { | |
| a = destination_node->AsSERecurrentNode()->GetCoefficient(); | |
| c = scalar_evolution_.CreateNegation( | |
| destination_node->AsSERecurrentNode()->GetOffset()); | |
| } else { | |
| a = scalar_evolution_.CreateConstant(0); | |
| c = scalar_evolution_.CreateNegation(destination_node); | |
| } | |
| if (source_induction_count != 0) { | |
| b = scalar_evolution_.CreateNegation( | |
| source_node->AsSERecurrentNode()->GetCoefficient()); | |
| c = scalar_evolution_.CreateAddNode( | |
| c, source_node->AsSERecurrentNode()->GetOffset()); | |
| } else { | |
| b = scalar_evolution_.CreateConstant(0); | |
| c = scalar_evolution_.CreateAddNode(c, source_node); | |
| } | |
| a = scalar_evolution_.SimplifyExpression(a); | |
| b = scalar_evolution_.SimplifyExpression(b); | |
| c = scalar_evolution_.SimplifyExpression(c); | |
| all_new_constrants.push_back( | |
| {make_constraint<DependenceLine>(a, b, c, loop), loop_id}); | |
| } | |
| } | |
| // Calculate the intersection between the new and existing constraints. | |
| std::vector<Constraint*> intersection = constraints; | |
| for (const auto& constraint_to_intersect : all_new_constrants) { | |
| auto loop_id = std::get<1>(constraint_to_intersect); | |
| auto loop = loops_[loop_id]; | |
| intersection[loop_id] = IntersectConstraints( | |
| intersection[loop_id], std::get<0>(constraint_to_intersect), | |
| GetLowerBound(loop), GetUpperBound(loop)); | |
| } | |
| // Report independence if an empty constraint (DependenceEmpty) is found. | |
| auto first_empty = | |
| std::find_if(std::begin(intersection), std::end(intersection), | |
| [](Constraint* constraint) { | |
| return constraint->AsDependenceEmpty() != nullptr; | |
| }); | |
| if (first_empty != std::end(intersection)) { | |
| return true; | |
| } | |
| std::vector<SubscriptPair> new_siv_subscripts{}; | |
| std::vector<SubscriptPair> new_miv_subscripts{}; | |
| auto equal = | |
| std::equal(std::begin(constraints), std::end(constraints), | |
| std::begin(intersection), | |
| [](Constraint* a, Constraint* b) { return *a == *b; }); | |
| // If any constraints have changed, propagate them into the rest of the | |
| // subscripts possibly creating new ZIV/SIV subscripts. | |
| if (!equal) { | |
| std::vector<SubscriptPair> new_subscripts(miv_subscripts.size()); | |
| // Propagate constraints into MIV subscripts | |
| std::transform(std::begin(miv_subscripts), std::end(miv_subscripts), | |
| std::begin(new_subscripts), | |
| [this, &intersection](SubscriptPair& subscript_pair) { | |
| return PropagateConstraints(subscript_pair, | |
| intersection); | |
| }); | |
| // If a ZIV subscript is returned, apply test, otherwise, update untested | |
| // subscripts. | |
| for (auto& subscript : new_subscripts) { | |
| if (IsZIV(subscript) && ZIVTest(subscript)) { | |
| return true; | |
| } else if (IsSIV(subscript)) { | |
| new_siv_subscripts.push_back(subscript); | |
| } else { | |
| new_miv_subscripts.push_back(subscript); | |
| } | |
| } | |
| } | |
| // Set new constraints and subscripts to test. | |
| std::swap(siv_subscripts, new_siv_subscripts); | |
| std::swap(miv_subscripts, new_miv_subscripts); | |
| std::swap(constraints, intersection); | |
| } | |
| // Create the dependence vector from the constraints. | |
| for (size_t i = 0; i < loops_.size(); ++i) { | |
| // Don't touch entries for loops that weren't tested. | |
| if (loop_appeared[i]) { | |
| auto current_constraint = constraints[i]; | |
| auto& current_distance_entry = (*dv_entry).GetEntries()[i]; | |
| if (auto dependence_distance = | |
| current_constraint->AsDependenceDistance()) { | |
| if (auto constant_node = | |
| dependence_distance->GetDistance()->AsSEConstantNode()) { | |
| current_distance_entry.dependence_information = | |
| DistanceEntry::DependenceInformation::DISTANCE; | |
| current_distance_entry.distance = constant_node->FoldToSingleValue(); | |
| if (current_distance_entry.distance == 0) { | |
| current_distance_entry.direction = DistanceEntry::Directions::EQ; | |
| } else if (current_distance_entry.distance < 0) { | |
| current_distance_entry.direction = DistanceEntry::Directions::GT; | |
| } else { | |
| current_distance_entry.direction = DistanceEntry::Directions::LT; | |
| } | |
| } | |
| } else if (auto dependence_point = | |
| current_constraint->AsDependencePoint()) { | |
| auto source = dependence_point->GetSource(); | |
| auto destination = dependence_point->GetDestination(); | |
| if (source->AsSEConstantNode() && destination->AsSEConstantNode()) { | |
| current_distance_entry = DistanceEntry( | |
| source->AsSEConstantNode()->FoldToSingleValue(), | |
| destination->AsSEConstantNode()->FoldToSingleValue()); | |
| } | |
| } | |
| } | |
| } | |
| // Test any remaining MIV subscripts and report independence if found. | |
| std::vector<bool> results(miv_subscripts.size()); | |
| std::transform(std::begin(miv_subscripts), std::end(miv_subscripts), | |
| std::begin(results), | |
| [this](const SubscriptPair& p) { return GCDMIVTest(p); }); | |
| return std::accumulate(std::begin(results), std::end(results), false, | |
| std::logical_or<bool>{}); | |
| } | |
| } // namespace opt | |
| } // namespace spvtools |