diff --git a/llvm/lib/Transforms/Scalar/LoopInterchange.cpp b/llvm/lib/Transforms/Scalar/LoopInterchange.cpp --- a/llvm/lib/Transforms/Scalar/LoopInterchange.cpp +++ b/llvm/lib/Transforms/Scalar/LoopInterchange.cpp @@ -182,63 +182,35 @@ 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') +// 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 &DV) { + for (unsigned Level = 0; Level < DV.size(); ++Level) { + unsigned char Direction = DV[Level]; + if (Direction == '<') + return true; + if (Direction == '>' || Direction == '*') 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 == '<') - return true; - - if (InnerDep == '>') { - // 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)) - return true; - } - - return false; -} - // 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 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 == '*') - return false; - if (!validDepInterchange(DepMatrix, Row, OuterLoopId, InnerDep, OuterDep)) + // Create temporary DepVector and swap OuterLoop vs InnerLoop + Cur = DepMatrix[Row]; + if (!isLexicographicallyPositive(Cur)) + return false; + std::swap(Cur[InnerLoopId], Cur[OuterLoopId]); + if (!isLexicographicallyPositive(Cur)) return false; } return true;