[DA] Remove base pointers from subscripts (NFCI)

[kasuga-fj]

This patch removes base pointers from subscripts when delinearization fails. Previously, in such cases, the pointer type SCEVs were used instead of offset SCEVs derived from them.
For example, here is a portion of the debug output when analyzing strong0 in test/Analysis/DependenceAnalysis/StrongSIV.ll:

testing subscript 0, SIV
    src = {(8 + %A),+,4}<nuw><%for.body>
    dst = {(8 + %A),+,4}<nuw><%for.body>
	Strong SIV test
	    Coeff = 4, i64
	    SrcConst = (8 + %A), ptr
	    DstConst = (8 + %A), ptr
	    Delta = 0, i64
	    UpperBound = (-1 + %n), i64
	    Distance = 0
	    Remainder = 0

As shown above, the SrcConst and DstConst are pointer values rather than integer offsets. %A should be removed.

This change is necessary for #157086, since ScalarEvolution::willNotOverflow expects integer type SCEVs as arguments. This change alone alone should not affect the analysis results.

[kasuga-fj]

• [DA] Add test where WeakCrossingSIV misses dependency due to overflow (NFC) #158281
• [DA] Add overflow check in ExactSIV #157086
• [DA] Add test where ExactSIV misses dependency due to overflow (NFC) #157085
• [DA] Add option to run only SIV routines #157084
• [DA] Remove base pointers from subscripts (NFCI) #157083 👈 (View in Graphite)
• main

This stack of pull requests is managed by Graphite. Learn more about stacking.

[llvmbot]

@llvm/pr-subscribers-llvm-analysis

Author: Ryotaro Kasuga (kasuga-fj)

Changes

This patch removes base pointers from subscripts when delinearization fails. Previously, in such cases, the pointer type SCEVs were used instead of offset SCEVs derived from them. For example, here is a portion of the debug output when analyzing strong0 in test/Analysis/DependenceAnalysis/StrongSIV.ll:

testing subscript 0, SIV
    src = {(8 + %A),+,4}<nuw><%for.body>
    dst = {(8 + %A),+,4}<nuw><%for.body>
	Strong SIV test
	    Coeff = 4, i64
	    SrcConst = (8 + %A), ptr
	    DstConst = (8 + %A), ptr
	    Delta = 0, i64
	    UpperBound = (-1 + %n), i64
	    Distance = 0
	    Remainder = 0

As shown above, the SrcConst and DstConst are pointer values rather than integer offsets. %A should be removed.

This change is necessary for #157086, since ScalarEvolution::willNotOverflow expects integer type SCEVs as arguments.

---

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

1 Files Affected:

• (modified) llvm/lib/Analysis/DependenceAnalysis.cpp (+8-4)

diff --git a/llvm/lib/Analysis/DependenceAnalysis.cpp b/llvm/lib/Analysis/DependenceAnalysis.cpp
index da86a8d2cc9c0..43eefc3120f9e 100644
--- a/llvm/lib/Analysis/DependenceAnalysis.cpp
+++ b/llvm/lib/Analysis/DependenceAnalysis.cpp
@@ -3698,8 +3698,8 @@ DependenceInfo::depends(Instruction *Src, Instruction *Dst,
 
   unsigned Pairs = 1;
   SmallVector<Subscript, 2> Pair(Pairs);
-  Pair[0].Src = SrcSCEV;
-  Pair[0].Dst = DstSCEV;
+  Pair[0].Src = SrcEv;
+  Pair[0].Dst = DstEv;
 
   if (Delinearize) {
     if (tryDelinearize(Src, Dst, Pair)) {
@@ -3709,6 +3709,8 @@ DependenceInfo::depends(Instruction *Src, Instruction *Dst,
   }
 
   for (unsigned P = 0; P < Pairs; ++P) {
+    assert(Pair[P].Src->getType()->isIntegerTy() && "Src must be an integer");
+    assert(Pair[P].Dst->getType()->isIntegerTy() && "Dst must be an integer");
     Pair[P].Loops.resize(MaxLevels + 1);
     Pair[P].GroupLoops.resize(MaxLevels + 1);
     Pair[P].Group.resize(Pairs);
@@ -4111,8 +4113,8 @@ const SCEV *DependenceInfo::getSplitIteration(const Dependence &Dep,
   SmallVector<Subscript, 2> Pair(Pairs);
   const SCEV *SrcSCEV = SE->getSCEV(SrcPtr);
   const SCEV *DstSCEV = SE->getSCEV(DstPtr);
-  Pair[0].Src = SrcSCEV;
-  Pair[0].Dst = DstSCEV;
+  Pair[0].Src = SE->removePointerBase(SrcSCEV);
+  Pair[0].Dst = SE->removePointerBase(DstSCEV);
 
   if (Delinearize) {
     if (tryDelinearize(Src, Dst, Pair)) {
@@ -4122,6 +4124,8 @@ const SCEV *DependenceInfo::getSplitIteration(const Dependence &Dep,
   }
 
   for (unsigned P = 0; P < Pairs; ++P) {
+    assert(Pair[P].Src->getType()->isIntegerTy() && "Src must be an integer");
+    assert(Pair[P].Dst->getType()->isIntegerTy() && "Dst must be an integer");
     Pair[P].Loops.resize(MaxLevels + 1);
     Pair[P].GroupLoops.resize(MaxLevels + 1);
     Pair[P].Group.resize(Pairs);

[Meinersbur]

LGTM

Not a change request since the fix seems rather obvious, but there is no regression test for this?

[kasuga-fj]

Not a change request since the fix seems rather obvious, but there is no regression test for this?

It is intentional. As far as I can tell, this patch itself is not functional change, and is necessary for the subsequent patch. I can add a regression test relying on the debug outputs, but I'd prefer not to, especially for what I believe is a trivial fix.

I’m not sure what is usually done in such cases, but if adding a test depending on the debug outputs is better than nothing, I’m okay with that.

Anyway, I added NFCI to the title.

[kasuga-fj]

I'll go ahead and land this now, as it affects other patches related to overflow handling. If tests are needed, I'll add them separately.