[LoopInterchange] Refactor and rewrite validDepInterchange()

[Narutoworld]

Summary

The current code of validDepInterchange() enumerates cases that are legal for interchange.
This could be simplified by checking lexicographically order of the swapped direction matrix.
It is pure refactoring and rewriting, the new code aligns with the logic within validInterchange()

[congzhe]

LGTM.

Hi @bmahjour and @Meinersbur , would you like to take a look on the patch?

[Meinersbur]

This involves a deep copy of the entire DepMatrix. I still find that acceptable to gain a much more logical dependency checking.

llvm/lib/Transforms/Scalar/LoopInterchange.cpp

207–212

I think this logic here is also superseded by the new logic.

214

[typo]

[Narutoworld]

llvm/lib/Transforms/Scalar/LoopInterchange.cpp

207–212

Hi @Meinersbur, Thanks for your comment.

The logic says if any dependency vector of InnerLoop or OuterLoop is unknown, it is not legal to do interchange.
And the function isLexicographicallyPositive() only checked the direction vector after potential interchage.

Suppose we have a dependency direction vector (*, <, =) for 3 layers loop, i, j, k. and we want to check if we can interchange loop i, j.

The original code will prohibit interchange since i-Dep is *.

However, with isLexicographicallyPositive(), the temp dependency direction vector is (<,*,=), which makes it a valid interchange candidate.
Although I can add more codes to force the same logic, (checking the interchanged position has a * ), it contains logic beyond checking Lexicographical Order only.

That is the reason why I would like to keep the original code.

[Narutoworld]

Fix typo

[Narutoworld]

Hi @Meinersbur, would you like to take a second look?

[bmahjour]

This is definitely an improvement and I'm glad to see this change, but please see my inline comments.

llvm/lib/Transforms/Scalar/LoopInterchange.cpp

190

Here we only check if direction is either < or >, but it could be S, which is a non-"=" direction. I think we should return false if we encounter an S in this loop, or only iterate if it's not = or I.

207–212

I prefer having isLexicographicallyPositive() handle all kinds of possible directions including S and *, this way it stands up to its name. We can check that a direction vector is positive before we swap two columns. If the direction vector is not positive to begin with, that means we couldn't correct it even with the normalization applied, so it must be treated as unsafe to interchange. If it passes the first test, we can then check if the direction vector is positive after doing the swap. This makes the logic simpler as it's all about whether an entry is isLexicographicallyPositive() or not, albeit we need to call the function twice for each row.

[bmahjour]

llvm/lib/Transforms/Scalar/LoopInterchange.cpp

190

correction: "...or only iterate if it *is* = or I"

[Meinersbur]

The two changes (Direction == '*' and checking the dep vector before doing the interchange) may add safety, but also cause tests to fail. @bmahjour suggested we could mark those as XFAIL and fix in a followup-patch, if not directly handled in this patch. Thing that I think are two strict:

1. I don't think the check before the interchange is necessary. Dependency vectors in the original code are in forward direction by definition.
2. The surrounding loops do not matter if the interchanged loops can still preserve any dependency. That is, the two innermost loop in a dependency vector (* < <) can be interchanged. Same argument that true dependency must have been forward in the original code. Think of the * being in another function that calls a function containing the < < loops. In that case, DependenceAnalysis would not even see that surrounding loops and would not have mattered. On the other side, the case (< * *) could still be interchanged because the dependency is known to be already carried by that surrounding loops and the two inner loops don't need to care.

llvm/lib/Transforms/Scalar/LoopInterchange.cpp

147–152

<= and >= are handled the same way as < and > respectively. I think this is incorrect.

Consider the loops i,j,k and the the dependency vector (<,*,<=). i and k cannot be interchanged as it would yield (<=,*,< ): <= is not guaranteed to carry all the dependencies before hitting *. This code here handles is the same as (<,*,<) where i and k can be interchanged.
Alternatively, to have just neighboring loops, consider (*,<=) assuming we do not need to check the before-state that was suggested by @bmahjour .

194

A dependency vector with a leading * (and maybe S as @bmahjour suggests) (such as (* <), (= * <), (= = * <) etc) would not be known to be lexicographically positive. Even if this would change the semantics, I think we should change this so match what is expected from a function called isLexicographicallyPositive.

I think this was missing to supersede the * logic below.

207–212

I do think interchanging the loop that results in a (<, *, =) vector is perfectly fine. This is because the original dependency will always be lexicographic positive because .. the instruction cannot have dependendent on another instruction that is executed in the future. The confused * state comes from the limitation from being represented in a dependence vector or limitations of DependenceAnalysis not understanding the dependency.

With moving < to the outer position, we know that dependence will be carried by that loop and the inner position dependency becomes irrelevant.

At the LoopWG call we discussed that we still could call isLexicographicallyPositive before the interchange to check that the dependency is understood before risting breaking things. I don't think it's necessary, but I don't mind.

215

[suggestion] Consider moving the std::vector<char> declaration out of the loop so it does not need to be reallocated each time, and/or SmallVector

[Narutoworld]

Update patch based on comments

[Narutoworld]

Update comments

[bmahjour]

Think of the * being in another function that calls a function containing the < < loops.

I agree we can think of it that way in the case of S dependencies (eg. where the outer loop IVs are not used in the subscripts of the memory access), but I'd worry about the possibility that confused direction in the outermost level might have been caused by use of outer loop IVs in combination with inner loop IVs. For example, in the following scenario we cannot think of the two inner loops being in another function unless we pass in the IV of the outer loop as parameter to that function. That will almost certainly change the way DA computes dependencies and will likely result in different direction entries for the two inner loops.

for (i)
  for (j)
   for (k)
    ... A[i, j, k+i]

[bmahjour]

The two changes (Direction == '*' and checking the dep vector before doing the interchange) may add safety, but also cause tests to fail.

@Narutoworld your latest patch calls isLexicographicallyPositive once before the swap and once afterwards, and I don't see any XFAILed tests in your update. Have you check to see if all LIT tests pass?

[Narutoworld]

In D137461#3931490, @bmahjour wrote:

The two changes (Direction == '*' and checking the dep vector before doing the interchange) may add safety, but also cause tests to fail.

@Narutoworld your latest patch calls isLexicographicallyPositive once before the swap and once afterwards, and I don't see any XFAILed tests in your update. Have you check to see if all LIT tests pass?

Hi @bmahjour
I have run the whole LIT tests with ninja check-all. No failed tests found.

[bmahjour]

In D137461#3931498, @Narutoworld wrote:

In D137461#3931490, @bmahjour wrote:

The two changes (Direction == '*' and checking the dep vector before doing the interchange) may add safety, but also cause tests to fail.

@Narutoworld your latest patch calls isLexicographicallyPositive once before the swap and once afterwards, and I don't see any XFAILed tests in your update. Have you check to see if all LIT tests pass?

Hi @bmahjour
I have run the whole LIT tests with ninja check-all. No failed tests found.

Thanks. LGTM then.

[Narutoworld]

rerun git clang-fomat and remove a white space

llvm/lib/Transforms/Scalar/LoopInterchange.cpp

for (J = I, JE = MemInstr.end(); J != JE; ++J) {
         unsigned Levels = D->getLevels();
         char Direction;
         for (unsigned II = 1; II <= Levels; ++II) {
           if (D->isScalar(II)) {
             Direction = 'S';
             Dep.push_back(Direction);
           } else {
             unsigned Dir = D->getDirection(II);
             if (Dir == Dependence::DVEntry::LT ||
                 Dir == Dependence::DVEntry::LE)
               Direction = '<';
             else if (Dir == Dependence::DVEntry::GT ||
                      Dir == Dependence::DVEntry::GE)
               Direction = '>';
             else if (Dir == Dependence::DVEntry::EQ)
               Direction = '=';
             else
               Direction = '*';
             Dep.push_back(Direction);
           }
         }
         while (Dep.size() != Level) {

 // A loop is moved from index 'from' to an index 'to'. Update the Dependence
 // matrix by exchanging the two columns.
 static void interChangeDependencies(CharMatrix &DepMatrix, unsigned FromIndx,
                                     unsigned ToIndx) {
   for (unsigned I = 0, E = DepMatrix.size(); I < E; ++I)
     std::swap(DepMatrix[I][ToIndx], DepMatrix[I][FromIndx]);
 }
 
-// Checks if no dependence exist in the dependency matrix in Row before Column.
-static bool containsNoDependence(CharMatrix &DepMatrix, unsigned Row,
-                                 unsigned Column) {
-  for (unsigned i = 0; i < Column; ++i) {
-    if (DepMatrix[Row][i] != '=' && DepMatrix[Row][i] != 'S' &&
-        DepMatrix[Row][i] != 'I')
-      return false;
-  }
-  return true;
-}
-
-static bool validDepInterchange(CharMatrix &DepMatrix, unsigned Row,
-                                unsigned OuterLoopId, char InnerDep,
-                                char OuterDep) {
-  if (InnerDep == OuterDep)
-    return true;
-
-  // It is legal to interchange if and only if after interchange no row has a
-  // '>' direction as the leftmost non-'='.
-
-  if (InnerDep == '=' || InnerDep == 'S' || InnerDep == 'I')
-    return true;
-
-  if (InnerDep == '<')
+// After interchanging, check if the direction vector is valid.
+// [Theorem] A permutation of the loops in a perfect nest is legal if and only
+// if the direction matrix, after the same permutation is applied to its
+// columns, has no ">" direction as the leftmost non-"=" direction in any row.
+static bool isLexicographicallyPositive(std::vector<char> &DV) {
+  for (unsigned Level = 0; Level < DV.size(); ++Level) {
+    unsigned char Direction = DV[Level];
+    if (Direction == '<')
       return true;
-
-  if (InnerDep == '>') {
-    // If OuterLoopId represents outermost loop then interchanging will make the
-    // 1st dependency as '>'
-    if (OuterLoopId == 0)
+    if (Direction == '>' || Direction == '*')
       return false;
-
-    // If all dependencies before OuterloopId are '=','S'or 'I'. Then
-    // interchanging will result in this row having an outermost non '='
-    // dependency of '>'
-    if (!containsNoDependence(DepMatrix, Row, OuterLoopId))
-      return true;
   }
-
-  return false;
+  return true;
 }
 
 // Checks if it is legal to interchange 2 loops.
-// [Theorem] A permutation of the loops in a perfect nest is legal if and only
-// if the direction matrix, after the same permutation is applied to its
-// columns, has no ">" direction as the leftmost non-"=" direction in any row.
 static bool isLegalToInterChangeLoops(CharMatrix &DepMatrix,
                                       unsigned InnerLoopId,
                                       unsigned OuterLoopId) {
   unsigned NumRows = DepMatrix.size();
+  std::vector<char> Cur;
   // For each row check if it is valid to interchange.
   for (unsigned Row = 0; Row < NumRows; ++Row) {
-    char InnerDep = DepMatrix[Row][InnerLoopId];
-    char OuterDep = DepMatrix[Row][OuterLoopId];
-    if (InnerDep == '*' || OuterDep == '*')
+    // Create temporary DepVector check its lexicographical order
+    // before and after swapping OuterLoop vs InnerLoop
+    Cur = DepMatrix[Row];
+    if (!isLexicographicallyPositive(Cur))
       return false;
-    if (!validDepInterchange(DepMatrix, Row, OuterLoopId, InnerDep, OuterDep))
+    std::swap(Cur[InnerLoopId], Cur[OuterLoopId]);
+    if (!isLexicographicallyPositive(Cur))
       return false;
   }
   return true;
 }
 
 static void populateWorklist(Loop &L, LoopVector &LoopList) {
   LLVM_DEBUG(dbgs() << "Calling populateWorklist on Func: "
                     << L.getHeader()->getParent()->getName() << " Loop: %"
                     << L.getHeader()->getName() << '\n');