To represent various loop levels within a nest, DA implements a special numbering scheme (see comment atop establishNestingLevels). The goal of this numbering scheme appears to be representing each unique loop distinctively by using as little memory as possible. This numbering scheme is simple when the source and destination of the dependence are in the same loop. In such cases the level is simply the depth of the loop in which src and dst reside. When the src and dst are not in the same loop, we could run into the following situation exposed by https://reviews.llvm.org/D71539.
Suppose we have the following loop structure and memory access:
1: L1 2: L2 3: A[s1] 4: L3 5: A[s2]
Further assume that the subscript of the first access (ie s1) is an LCSSA phi with a single incoming value from L2. With the change in D71539, the SCEV expression for s1 (queried at the scope of L1 where the access on line 3 occurs) will be an AddRec whose loop is L2.
Since the access A[s1] occurs at a loop depth of 1, but its subscript references a loop at depth 2, the current numbering scheme gets confused and assigns the same level value to both s1 and s2, which further causes classifyPair to incorrectly classify the subscript pair. In an assert enabled build, this would trigger the following assertion:
bool llvm::DependenceInfo::testSIV(const llvm::SCEV *, const llvm::SCEV *, unsigned int &, llvm::FullDependence &, llvm::DependenceInfo::Constraint &, const llvm::SCEV *&) const: Assertion `CurLoop == DstAddRec->getLoop() && "both loops in SIV should be same"' failed.
This patch proposes a simpler but much more conservative approach than D110972. It simply treats such cases as non-linear and therefore not analyzable.