Index: llvm/lib/Transforms/Scalar/LoopInterchange.cpp =================================================================== --- llvm/lib/Transforms/Scalar/LoopInterchange.cpp +++ llvm/lib/Transforms/Scalar/LoopInterchange.cpp @@ -182,52 +182,22 @@ 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 == '>') 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) { @@ -238,7 +208,11 @@ char OuterDep = DepMatrix[Row][OuterLoopId]; if (InnerDep == '*' || OuterDep == '*') return false; - if (!validDepInterchange(DepMatrix, Row, OuterLoopId, InnerDep, OuterDep)) + + // Create temporary DepVector and swap OutterLoop vs InnerLoop + std::vector Cur = DepMatrix[Row]; + std::swap(Cur[InnerLoopId], Cur[OuterLoopId]); + if (!isLexicographicallyPositive(Cur)) return false; } return true;