Page MenuHomePhabricator

[DA] Handle mismatching loop levels by updating the numbering scheme
Needs ReviewPublic

Authored by bmahjour on Oct 1 2021, 1:54 PM.
This revision needs review, but there are no reviewers specified.

Details

Reviewers
None
Summary

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 slight change to the numbering scheme using the subscript SCEVs to treat the memory access instructions in such cases, as if they appeared inside the AddRec loop of the inner-most subscript.

An alternative fix can be reviewed in D110973.

Diff Detail