[DA] Extract duplicated logic from gcdMIVtest (NFCI)

[kasuga-fj]

This patch refactors gcdMIVtest by consolidating duplicated logic into a single function. The main goal of this change is to improve code maintainability rather than readability, especially since we may need to revise this logic for correctness (as noted in the added TODO comments).

I hope this patch is NFC, but I've also added several new assertions, which may cause some previously passing cases to fail.

[llvmbot]

@llvm/pr-subscribers-llvm-analysis

Author: Ryotaro Kasuga (kasuga-fj)

Changes

This patch refactors gcdMIVtest by consolidating duplicated logic into a single function. The main goal of this change is to improve code maintainability rather than readability, especially since we may need to revise this logic for correctness (as noted in the added TODO comments). I believe this patch is NFC, but I've also added several new assertions, which may cause some previously passing cases to fail.

---

Full diff: https://github.com/llvm/llvm-project/pull/152688.diff

2 Files Affected:

• (modified) llvm/include/llvm/Analysis/DependenceAnalysis.h (+19)
• (modified) llvm/lib/Analysis/DependenceAnalysis.cpp (+42-34)

diff --git a/llvm/include/llvm/Analysis/DependenceAnalysis.h b/llvm/include/llvm/Analysis/DependenceAnalysis.h
index 16795969d4cd1..f66c79d915665 100644
--- a/llvm/include/llvm/Analysis/DependenceAnalysis.h
+++ b/llvm/include/llvm/Analysis/DependenceAnalysis.h
@@ -765,6 +765,25 @@ class DependenceInfo {
   CoefficientInfo *collectCoeffInfo(const SCEV *Subscript, bool SrcFlag,
                                     const SCEV *&Constant) const;
 
+  /// Given \p Expr of the form
+  ///
+  ///   c_0*X_0*i_0 + c_1*X_1*i_1 + ...c_n*X_n*i_n + C
+  ///
+  /// compute
+  ///
+  ///   RunningGCD = gcd(RunningGCD, c_0, c_1, ..., c_n)
+  ///
+  /// where c_0, c_1, ..., and c_n are the constant values. The result is stored
+  /// in \p RunningGCD. Also, the initial value of \p RunningGCD affects the
+  /// result. If we find a term like (c_k * X_k * i_k), where i_k is the
+  /// induction variable of \p CurLoop, c_k is stored in \p CurLoopCoeff and not
+  /// included in the GCD computation. Returns false if we fail to find a
+  /// constant coefficient for some loop, e.g., when a term like (X+Y)*i is
+  /// present. Otherwise returns true.
+  bool accumulateCoefficientsGCD(const SCEV *Expr, const Loop *CurLoop,
+                                 const SCEV *&CurLoopCoeff,
+                                 APInt &RunningGCD) const;
+
   /// getPositivePart - X^+ = max(X, 0).
   const SCEV *getPositivePart(const SCEV *X) const;
 
diff --git a/llvm/lib/Analysis/DependenceAnalysis.cpp b/llvm/lib/Analysis/DependenceAnalysis.cpp
index 835e270428694..777a040da4c9e 100644
--- a/llvm/lib/Analysis/DependenceAnalysis.cpp
+++ b/llvm/lib/Analysis/DependenceAnalysis.cpp
@@ -2345,6 +2345,43 @@ static std::optional<APInt> getConstantPart(const SCEV *Expr) {
   return std::nullopt;
 }
 
+bool DependenceInfo::accumulateCoefficientsGCD(const SCEV *Expr,
+                                               const Loop *CurLoop,
+                                               const SCEV *&CurLoopCoeff,
+                                               APInt &RunningGCD) const {
+  // If RunningGCD is already 1, exit early.
+  // TODO: It might be better to continue the recursion to find CurLoopCoeff.
+  if (RunningGCD == 1)
+    return true;
+
+  const SCEVAddRecExpr *AddRec = dyn_cast<SCEVAddRecExpr>(Expr);
+  if (!AddRec) {
+    assert(isLoopInvariant(Expr, CurLoop) &&
+           "Expected loop invariant expression");
+    return true;
+  }
+
+  assert(AddRec->isAffine() && "Unexpected Expr");
+  const SCEV *Start = AddRec->getStart();
+  const SCEV *Step = AddRec->getStepRecurrence(*SE);
+  if (AddRec->getLoop() == CurLoop) {
+    CurLoopCoeff = Step;
+  } else {
+    std::optional<APInt> ConstCoeff = getConstantPart(Step);
+
+    // If the coefficient is the product of a constant and other stuff, we can
+    // use the constant in the GCD computation.
+    if (!ConstCoeff)
+      return false;
+
+    // TODO: What happens if ConstCoeff is the "most negative" signed number
+    // (e.g. -128 for 8 bit wide APInt)?
+    RunningGCD = APIntOps::GreatestCommonDivisor(RunningGCD, ConstCoeff->abs());
+  }
+
+  return accumulateCoefficientsGCD(Start, CurLoop, CurLoopCoeff, RunningGCD);
+}
+
 //===----------------------------------------------------------------------===//
 // gcdMIVtest -
 // Tests an MIV subscript pair for dependence.
@@ -2464,40 +2501,11 @@ bool DependenceInfo::gcdMIVtest(const SCEV *Src, const SCEV *Dst,
     RunningGCD = ExtraGCD;
     const SCEV *SrcCoeff = AddRec->getStepRecurrence(*SE);
     const SCEV *DstCoeff = SE->getMinusSCEV(SrcCoeff, SrcCoeff);
-    const SCEV *Inner = Src;
-    while (RunningGCD != 1 && isa<SCEVAddRecExpr>(Inner)) {
-      AddRec = cast<SCEVAddRecExpr>(Inner);
-      const SCEV *Coeff = AddRec->getStepRecurrence(*SE);
-      if (CurLoop == AddRec->getLoop())
-        ; // SrcCoeff == Coeff
-      else {
-        // If the coefficient is the product of a constant and other stuff,
-        // we can use the constant in the GCD computation.
-        std::optional<APInt> ConstCoeff = getConstantPart(Coeff);
-        if (!ConstCoeff)
-          return false;
-        RunningGCD =
-            APIntOps::GreatestCommonDivisor(RunningGCD, ConstCoeff->abs());
-      }
-      Inner = AddRec->getStart();
-    }
-    Inner = Dst;
-    while (RunningGCD != 1 && isa<SCEVAddRecExpr>(Inner)) {
-      AddRec = cast<SCEVAddRecExpr>(Inner);
-      const SCEV *Coeff = AddRec->getStepRecurrence(*SE);
-      if (CurLoop == AddRec->getLoop())
-        DstCoeff = Coeff;
-      else {
-        // If the coefficient is the product of a constant and other stuff,
-        // we can use the constant in the GCD computation.
-        std::optional<APInt> ConstCoeff = getConstantPart(Coeff);
-        if (!ConstCoeff)
-          return false;
-        RunningGCD =
-            APIntOps::GreatestCommonDivisor(RunningGCD, ConstCoeff->abs());
-      }
-      Inner = AddRec->getStart();
-    }
+
+    if (!accumulateCoefficientsGCD(Src, CurLoop, SrcCoeff, RunningGCD) ||
+        !accumulateCoefficientsGCD(Dst, CurLoop, DstCoeff, RunningGCD))
+      return false;
+
     Delta = SE->getMinusSCEV(SrcCoeff, DstCoeff);
     // If the coefficient is the product of a constant and other stuff,
     // we can use the constant in the GCD computation.

[kasuga-fj]

This seems pretty buggy. Considering that DstCoeff is initialized to something like zero, we may not be able to distinguish between the case where Dst is invariant in CurLoop and the case where Dst is NOT invariant but the GCD is 1.

[Meinersbur]

LGTM

I hope this patch is NFC, but I've also added several new assertions, which may cause some previously passing cases to fail.

You can add "NFCI", I for "Intended"

[kasuga-fj]

You can add "NFCI", I for "Intended"

I didn’t know that’s what the ‘I’ in NFCI meant. Thanks!