Method GCDMIVTest

source/opt/loop_dependence.cpp:1075–1112

Perform the GCD test if both, the source and the destination nodes, are in the form a0*i0 + a1*i1 + ... an*in + c.

// 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*>>>;