[LoopInterchange] Simplify DepMatrix to a dependency vector.

[Meinersbur]

Summary

It is not necessary to store all pairwise dependencies when it is sufficient to know which kind of dependencies occured.

This might have some behavioral effects such as when two dependencies can be interchange on their own but combined into a single loop nest they can not. Example:
Dependence 1: [<,=,>] (carried by outer loop)
Dependence 2: [=,<,>] (carried by inner loop)
when combined:
[<=,<=,>]
which would not be considered interchangeable.

In any case, all of our current tests pass after this change and is significantly more efficient (still quadratic in the number of memory instructions, because we have to query DA for each pair)

[bmahjour]

This would collapse two dimensions of the dependency matrix into one without providing a way to recover the individual dependency vectors, and as you pointed out in the description it could make some interchangeable cases look illegal. Another example is if we have [S, >, = ] and [S, <, =], we can safely interchange the two inner loops (by factoring out the S from the beginning of both vectors), but after merging them we get [S, <>, = ] and now the inner two loops can no longer be interchanged.

Is the size of dependency matrix proving to be problematic for certain workloads? If so, maybe looking at some concrete examples can help solve the problem in a more effective way (eg. considering sparse data structures or some sort of compression/decompression techniques).

On a different note, I think we can make the code more elegant and robust by encapsulating all the dependency matrix analysis inside a class. For example:

class DepMatrix {
public:
  /// Enumerates the possible kind of dependency in a dependence vector.
  enum class DepKind : char {
    NEG, 
    EQ,  
    POS,
    S,
    STAR
  };

  /// Represents a row of the dependency matrix.
  using DepVector = std::vector<DepKind>;
  ...

  /// Update the dependence matrix by exchanging two columns.
  void interchangeColumns(const Loop &A, const Loop &B);
  
  bool isPositive(int row);
  ...
private:
  /// The dependency matrix is represented by a vector of dependency vectors.
  std::vector<DepVector> DM;
};

llvm/lib/Transforms/Scalar/LoopInterchange.cpp

84

why does this need to be reduced so much?

[congzhe]

llvm/lib/Transforms/Scalar/LoopInterchange.cpp

154

typo?

179

Please correct me if I'm wrong - IIUC Scalar is considered a type of dependence that prevents interchange?

208

If Scalar is considered a type of dependence that prevents interchange, would isAnydirectional() be the following?

return ((F & LT) && (F & GT)) || (F & Scalar);

[congzhe]

Just one more question on the summary: when combining the two dependencies [<,=] and [=,<] that generated [<=,<=], I think we could still interchange the combined dependency? [<=,<=] is non-negative and swapping the two elements <= and <= gives a non-negative dependency. Thus we are not converting a positive dependency to a negative dependency, hence not violating the dependency rules for a valid interchange. Perhaps with the current validDepInterchange() we cannot interchange [<=,<=], but like I mentioned in the past meetings I'm rewriting validDepInterchange() to make the legality decisions be purely based on the signs of the dependence vectors before/after interchange. With the rewritten validDepInterchange() I think we can interchange [<=,<=].

My apologies for not being able to post the patch that rewrites validDepInterchange() sooner. We are actively working on it recently and now it seems there is a real need for this patch. We'll post the patch as soon as we can.

[Meinersbur]

In D136277#3899782, @bmahjour wrote:

Is the size of dependency matrix proving to be problematic for certain workloads?

I am not aware of concrete problems, I mostly felt that it would not be necessary to always go through the entire list of pairwise dependencies and instead could be summarized since which instructions induce the dependencies is irrelevant.

However, due to experimenting with it I now understand that there indeed is a difference than what is done now, although I am not sure whether that situation is sufficiently common.

In D136277#3899782, @bmahjour wrote:

On a different note, I think we can make the code more elegant and robust by encapsulating all the dependency matrix analysis inside a class. For example:

class DepMatrix {
....

Could we call it something else than a matrix? In a matrix, I'd expect the indices have some relevance, here the outer dimension is an unordered collection (DenseSet<SmallString<4>>? That would also de-duplicate identical dependence vectors and thus less work later. Or just a flat array SmallVector<char> managed by DepMatrix). Also, std::vector of std::vectors is not the most elegant, esp when resizing.

llvm/lib/Transforms/Scalar/LoopInterchange.cpp

84

Without this patch, MaxMemInstrCount does not compare to the number of instructions, but the number of instruction pairs (that have a dependency). That is, the constant name and the comment above it are inconsistent.

Since in worst case, there can be a quadratic number of pairs, I just took the square of it.

179

The original code explicitly ignores scalar types (DepMatrix[Row][i] != 'S')

[congzhe]

llvm/lib/Transforms/Scalar/LoopInterchange.cpp

179

Right, but I remember earlier this year when discussing a few related bugs we reached to a conclusion that it is not correct to ignore scalar types (in other words the current code is wrong)? Anyways I'm rewriting the whole validDepInterchange() so it may not be too big of a concern for now.

[Meinersbur]

Abandon as discussed in the LoopWG call. It coarsens the analysis when compile time wasn't even a problem.

llvm/lib/Transforms/Scalar/LoopInterchange.cpp

 static cl::opt<int> LoopInterchangeCostThreshold(
     "loop-interchange-threshold", cl::init(0), cl::Hidden,
     cl::desc("Interchange if you gain more than this number"));
 
 namespace {
 
 using LoopVector = SmallVector<Loop *, 8>;
 
+// Synchronize with Dependence::DVEntry::LT,EQ,GT from DependenceAnalysis
+enum DepFlags {
+  LT = 1 << 0,
+  EQ = 1 << 1,
+  GT = 1 << 2,
+  Scalar = 1 << 3,
+  Ignore = 1 << 4,
+  LLVM_MARK_AS_BITMASK_ENUM(/*LargestValue=*/Ignore)
+};
+
 // TODO: Check if we can use a sparse matrix here.
-using CharMatrix = std::vector<std::vector<char>>;
+using CharMatrix = std::vector<DepFlags>;
 
 } // end anonymous namespace
 
 // Maximum number of dependencies that can be handled in the dependency matrix.
-static const unsigned MaxMemInstrCount = 100;
+static const unsigned MaxMemInstrCount = 10;
 
 // Maximum loop depth supported.
 static const unsigned MaxLoopNestDepth = 10;
 
-#ifdef DUMP_DEP_MATRICIES
-static void printDepMatrix(CharMatrix &DepMatrix) {
-  for (auto &Row : DepMatrix) {
-    for (auto D : Row)
-      LLVM_DEBUG(dbgs() << D << " ");
-    LLVM_DEBUG(dbgs() << "\n");
-  }
-}
-#endif
-
 static bool populateDependencyMatrix(CharMatrix &DepMatrix, unsigned Level,
                                      Loop *L, DependenceInfo *DI,
                                      ScalarEvolution *SE) {
   using ValueVector = SmallVector<Value *, 16>;
 
   ValueVector MemInstr;
 
   // For each block.
for (Instruction &I : *BB) {
         MemInstr.push_back(&I);
       }
     }
   }
 
   LLVM_DEBUG(dbgs() << "Found " << MemInstr.size()
                     << " Loads and Stores to analyze\n");
 
-  ValueVector::iterator I, IE, J, JE;
+  if (MemInstr.size() > MaxMemInstrCount) {
+    LLVM_DEBUG(dbgs() << "Cannot handle more than " << MaxMemInstrCount
+                      << " dependencies inside loop\n");
+    return false;
+  }
+
+  DepMatrix.resize(Level);
+  for (unsigned II = 0; II < Level; ++II)
+    DepMatrix[II] = static_cast<DepFlags>(0);
 
+  ValueVector::iterator I, IE, J, JE;
   for (I = MemInstr.begin(), IE = MemInstr.end(); I != IE; ++I) {
     for (J = I, JE = MemInstr.end(); J != JE; ++J) {
-      std::vector<char> Dep;
       Instruction *Src = cast<Instruction>(*I);
       Instruction *Dst = cast<Instruction>(*J);
       // Ignore Input dependencies.
       if (isa<LoadInst>(Src) && isa<LoadInst>(Dst))
         continue;
       // Track Output, Flow, and Anti dependencies.
       if (auto D = DI->depends(Src, Dst, true)) {
         assert(D->isOrdered() && "Expected an output, flow or anti dep.");
         // If the direction vector is negative, normalize it to
         // make it non-negative.
         if (D->normalize(SE))
           LLVM_DEBUG(dbgs() << "Negative dependence vector normalized.\n");
         LLVM_DEBUG(StringRef DepType =
                        D->isFlow() ? "flow" : D->isAnti() ? "anti" : "output";
                    dbgs() << "Found " << DepType
                           << " dependency between Src and Dst\n"
                           << " Src:" << *Src << "\n Dst:" << *Dst << '\n');
         unsigned Levels = D->getLevels();
-        char Direction;
-        for (unsigned II = 1; II <= Levels; ++II) {
-          if (D->isScalar(II)) {
-            Direction = 'S';
-            Dep.push_back(Direction);
+        unsigned II = 0;
+        for (; II < Levels; ++II) {
+          DepFlags &Lvl = DepMatrix[II];
+          if (D->isScalar(II + 1)) {
+            Lvl |= Scalar;
           } 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);
+            // DepFlags needs lower 3 bits of DepFlags for be the same as used
+            // by DA.
+            Lvl |= static_cast<DepFlags>(D->getDirection(II + 1));
           }
         }
-        while (Dep.size() != Level) {
-          Dep.push_back('I');
-        }
-
-        DepMatrix.push_back(Dep);
-        if (DepMatrix.size() > MaxMemInstrCount) {
-          LLVM_DEBUG(dbgs() << "Cannot handle more than " << MaxMemInstrCount
-                            << " dependencies inside loop\n");
-          return false;
-        }
+        for (; II < Level; ++II)
+          DepMatrix[II] |= Ignore;
       }
     }
   }
 
   return true;
 }
 
 // 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]);
+  std::swap(DepMatrix[ToIndx], DepMatrix[FromIndx]);
 }
 
 // Checks if no dependence exist in the dependency matrix in Row before Column.
-static bool containsNoDependence(CharMatrix &DepMatrix, unsigned Row,
-                                 unsigned Column) {
+static bool containsNoDependence(CharMatrix &DepMatrix, unsigned Column) {
   for (unsigned i = 0; i < Column; ++i) {
-    if (DepMatrix[Row][i] != '=' && DepMatrix[Row][i] != 'S' &&
-        DepMatrix[Row][i] != 'I')
+    DepFlags Lvl = DepMatrix[i];
+    if (Lvl & LT || Lvl & GT)
       return false;
   }
   return true;
 }
 
-static bool validDepInterchange(CharMatrix &DepMatrix, unsigned Row,
-                                unsigned OuterLoopId, char InnerDep,
-                                char OuterDep) {
+static bool validDepInterchange(CharMatrix &DepMatrix, unsigned OuterLoopId,
+                                DepFlags InnerDep, DepFlags 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 == '<')
-    return true;
-
-  if (InnerDep == '>') {
+  if (InnerDep & GT) {
     // If OuterLoopId represents outermost loop then interchanging will make the
     // 1st dependency as '>'
     if (OuterLoopId == 0)
       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))
+    if (!containsNoDependence(DepMatrix, OuterLoopId))
       return true;
   }
 
-  return false;
+  return true;
 }
 
+static bool isAnydirectional(DepFlags F) { return (F & LT) && (F & GT); }
+
 // 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();
   // 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 == '*')
-      return false;
-    if (!validDepInterchange(DepMatrix, Row, OuterLoopId, InnerDep, OuterDep))
-      return false;
-  }
+  DepFlags InnerDep = DepMatrix[InnerLoopId];
+  DepFlags OuterDep = DepMatrix[OuterLoopId];
+  if (isAnydirectional(InnerDep) || isAnydirectional(OuterDep))
+  if (!validDepInterchange(DepMatrix, OuterLoopId, InnerDep, OuterDep))
+
   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');
   assert(LoopList.empty() && "LoopList should initially be empty!");
bool processLoopList(SmallVectorImpl<Loop *> &LoopList) {
 
     CharMatrix DependencyMatrix;
     Loop *OuterMostLoop = *(LoopList.begin());
     if (!populateDependencyMatrix(DependencyMatrix, LoopNestDepth,
                                   OuterMostLoop, DI, SE)) {
       LLVM_DEBUG(dbgs() << "Populating dependency matrix failed\n");
       return false;
     }
-#ifdef DUMP_DEP_MATRICIES
-    LLVM_DEBUG(dbgs() << "Dependence before interchange\n");
-    printDepMatrix(DependencyMatrix);
-#endif
 
     // Get the Outermost loop exit.
     BasicBlock *LoopNestExit = OuterMostLoop->getExitBlock();
     if (!LoopNestExit) {
       LLVM_DEBUG(dbgs() << "OuterMostLoop needs an unique exit block");
       return false;
     }
 
for (unsigned j = SelecLoopId; j > 0; j--) {
         bool Interchanged = processLoop(LoopList[i], LoopList[i - 1], i, i - 1,
                                         DependencyMatrix, CostMap);
         if (!Interchanged)
           continue;
         // Loops interchanged, update LoopList accordingly.
         std::swap(LoopList[i - 1], LoopList[i]);
         // Update the DependencyMatrix
         interChangeDependencies(DependencyMatrix, i, i - 1);
-#ifdef DUMP_DEP_MATRICIES
-        LLVM_DEBUG(dbgs() << "Dependence after interchange\n");
-        printDepMatrix(DependencyMatrix);
-#endif
         ChangedPerIter |= Interchanged;
         Changed |= Interchanged;
       }
       // Early abort if there was no interchange during an entire round of
       // moving loops outwards.
       if (!ChangedPerIter)
         break;
     }
     return Changed;
   }
 
   bool processLoop(Loop *InnerLoop, Loop *OuterLoop, unsigned InnerLoopId,
-                   unsigned OuterLoopId,
-                   std::vector<std::vector<char>> &DependencyMatrix,
+                   unsigned OuterLoopId, CharMatrix &DependencyMatrix,
                    const DenseMap<const Loop *, unsigned> &CostMap) {
     LLVM_DEBUG(dbgs() << "Processing InnerLoopId = " << InnerLoopId
                       << " and OuterLoopId = " << OuterLoopId << "\n");
     LoopInterchangeLegality LIL(OuterLoop, InnerLoop, SE, ORE);
     if (!LIL.canInterchangeLoops(InnerLoopId, OuterLoopId, DependencyMatrix)) {
       LLVM_DEBUG(dbgs() << "Not interchanging loops. Cannot prove legality.\n");
       return false;
     }

 }
 
 static bool isProfitableForVectorization(unsigned InnerLoopId,
                                          unsigned OuterLoopId,
                                          CharMatrix &DepMatrix) {
   // TODO: Improve this heuristic to catch more cases.
   // If the inner loop is loop independent or doesn't carry any dependency it is
   // profitable to move this to outer position.
-  for (auto &Row : DepMatrix) {
-    if (Row[InnerLoopId] != 'S' && Row[InnerLoopId] != 'I')
-      return false;
-    // TODO: We need to improve this heuristic.
-    if (Row[OuterLoopId] != '=')
-      return false;
-  }
+  if (DepMatrix[InnerLoopId] & ~(Scalar | Ignore))
+
+  if (DepMatrix[OuterLoopId] & ~EQ)
+
   // If outer loop has dependence and inner loop is loop independent then it is
   // profitable to interchange to enable parallelism.
   // If there are no dependences, interchanging will not improve anything.
-  return !DepMatrix.empty();
+  return DepMatrix[InnerLoopId] != 0;
 }
 
 bool LoopInterchangeProfitability::isProfitable(
     const Loop *InnerLoop, const Loop *OuterLoop, unsigned InnerLoopId,
     unsigned OuterLoopId, CharMatrix &DepMatrix,
     const DenseMap<const Loop *, unsigned> &CostMap) {
   // TODO: Remove the legacy cost model.