llvmbot wrote:
<!--LLVM PR SUMMARY COMMENT-->
@llvm/pr-subscribers-llvm-analysis
Author: Ryotaro Kasuga (kasuga-fj)
<details>
<summary>Changes</summary>
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/157086.diff
2 Files Affected:
- (modified) llvm/lib/Analysis/DependenceAnalysis.cpp (+13-1)
- (modified) llvm/test/Analysis/DependenceAnalysis/ExactSIV.ll (+1-1)
``````````diff
diff --git a/llvm/lib/Analysis/DependenceAnalysis.cpp
b/llvm/lib/Analysis/DependenceAnalysis.cpp
index 0f77a1410e83b..6e576e866b310 100644
--- a/llvm/lib/Analysis/DependenceAnalysis.cpp
+++ b/llvm/lib/Analysis/DependenceAnalysis.cpp
@@ -1170,6 +1170,15 @@ const SCEVConstant
*DependenceInfo::collectConstantUpperBound(const Loop *L,
return nullptr;
}
+/// Returns \p A - \p B if it guaranteed not to signed wrap. Otherwise returns
+/// nullptr. \p A and \p B must have the same integer type.
+static const SCEV *minusSCEVNoSignedOverflow(const SCEV *A, const SCEV *B,
+ ScalarEvolution &SE) {
+ if (SE.willNotOverflow(Instruction::Sub, /*Signed=*/true, A, B))
+ return SE.getMinusSCEV(A, B);
+ return nullptr;
+}
+
// testZIV -
// When we have a pair of subscripts of the form [c1] and [c2],
// where c1 and c2 are both loop invariant, we attack it using
@@ -1626,7 +1635,9 @@ bool DependenceInfo::exactSIVtest(const SCEV *SrcCoeff,
const SCEV *DstCoeff,
assert(0 < Level && Level <= CommonLevels && "Level out of range");
Level--;
Result.Consistent = false;
- const SCEV *Delta = SE->getMinusSCEV(DstConst, SrcConst);
+ const SCEV *Delta = minusSCEVNoSignedOverflow(DstConst, SrcConst, *SE);
+ if (!Delta)
+ return false;
LLVM_DEBUG(dbgs() << "\t Delta = " << *Delta << "\n");
NewConstraint.setLine(SrcCoeff, SE->getNegativeSCEV(DstCoeff), Delta,
CurLoop);
@@ -1716,6 +1727,7 @@ bool DependenceInfo::exactSIVtest(const SCEV *SrcCoeff,
const SCEV *DstCoeff,
// explore directions
unsigned NewDirection = Dependence::DVEntry::NONE;
APInt LowerDistance, UpperDistance;
+ // TODO: Overflow check may be needed.
if (TA.sgt(TB)) {
LowerDistance = (TY - TX) + (TA - TB) * TL;
UpperDistance = (TY - TX) + (TA - TB) * TU;
diff --git a/llvm/test/Analysis/DependenceAnalysis/ExactSIV.ll
b/llvm/test/Analysis/DependenceAnalysis/ExactSIV.ll
index 97b58c06303e6..5a8a60a6833ae 100644
--- a/llvm/test/Analysis/DependenceAnalysis/ExactSIV.ll
+++ b/llvm/test/Analysis/DependenceAnalysis/ExactSIV.ll
@@ -834,7 +834,7 @@ define void @exact14(ptr %A) {
; CHECK-SIV-ONLY-NEXT: Src: store i8 0, ptr %idx.0, align 1 --> Dst: store i8
0, ptr %idx.0, align 1
; CHECK-SIV-ONLY-NEXT: da analyze - none!
; CHECK-SIV-ONLY-NEXT: Src: store i8 0, ptr %idx.0, align 1 --> Dst: store i8
1, ptr %idx.1, align 1
-; CHECK-SIV-ONLY-NEXT: da analyze - none!
+; CHECK-SIV-ONLY-NEXT: da analyze - output [*|<]!
; CHECK-SIV-ONLY-NEXT: Src: store i8 1, ptr %idx.1, align 1 --> Dst: store i8
1, ptr %idx.1, align 1
; CHECK-SIV-ONLY-NEXT: da analyze - none!
;
``````````
</details>
https://github.com/llvm/llvm-project/pull/157086
_______________________________________________
llvm-branch-commits mailing list
[email protected]
https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-branch-commits
