diff --git a/mlir/include/mlir/Analysis/Presburger/Utils.h b/mlir/include/mlir/Analysis/Presburger/Utils.h --- a/mlir/include/mlir/Analysis/Presburger/Utils.h +++ b/mlir/include/mlir/Analysis/Presburger/Utils.h @@ -14,6 +14,7 @@ #define MLIR_ANALYSIS_PRESBURGER_UTILS_H #include "mlir/Support/LLVM.h" +#include "llvm/ADT/STLExtras.h" namespace mlir { @@ -51,6 +52,22 @@ SmallVector ÷nd, unsigned &divisor); +/// Given dividends of divisions `divs` and denominators `denoms`, detects and +/// removes duplicate divisions. `localOffset` is the offset in dividend of a +/// division from where local identifiers start. +/// +/// On every possible duplicate division found, `merge(i, j)`, where `i`, `j` +/// are current index of the duplicate divisions, is called and division at +/// index `j` is merged into division at index `i`. If `merge(i, j)` returns +/// `true`, the divisions are merged i.e. `j^th` division gets eliminated and +/// it's each instance is replaced by `i^th` division. If it returns `false`, +/// the divisions are not merged. `merge` can also do side effects, For example +/// it can merge the local identifiers in IntegerPolyhedron. +void removeDuplicateDivs( + std::vector> &divs, + SmallVectorImpl &denoms, unsigned localOffset, + llvm::function_ref merge); + } // namespace presburger_utils } // namespace mlir diff --git a/mlir/lib/Analysis/Presburger/IntegerPolyhedron.cpp b/mlir/lib/Analysis/Presburger/IntegerPolyhedron.cpp --- a/mlir/lib/Analysis/Presburger/IntegerPolyhedron.cpp +++ b/mlir/lib/Analysis/Presburger/IntegerPolyhedron.cpp @@ -1090,47 +1090,17 @@ std::copy(denomsB.begin() + initLocals, denomsB.end(), denomsA.begin() + initLocals); - // Find and merge duplicate divisions. - // TODO: Add division normalization to support divisions that differ by - // a constant. - // TODO: Add division ordering such that a division representation for local - // identifier at position `i` only depends on local identifiers at position < - // `i`. This would make sure that all divisions depending on other local - // variables that can be merged, are merged. - unsigned localOffset = getIdKindOffset(IdKind::Local); - for (unsigned i = 0; i < divsA.size(); ++i) { - // Check if a division representation exists for the `i^th` local id. - if (denomsA[i] == 0) - continue; - // Check if a division exists which is a duplicate of the division at `i`. - for (unsigned j = i + 1; j < divsA.size(); ++j) { - // Check if a division representation exists for the `j^th` local id. - if (denomsA[j] == 0) - continue; - // Check if the denominators match. - if (denomsA[i] != denomsA[j]) - continue; - // Check if the representations are equal. - if (divsA[i] != divsA[j]) - continue; - - // Merge divisions at position `j` into division at position `i`. - eliminateRedundantLocalId(polyA, i, j); - eliminateRedundantLocalId(polyB, i, j); - for (unsigned k = 0, g = divsA.size(); k < g; ++k) { - SmallVector &div = divsA[k]; - if (denomsA[k] != 0) { - div[localOffset + i] += div[localOffset + j]; - div.erase(div.begin() + localOffset + j); - } - } + // Merge function that merges the local variables in both sets by treating + // them as the same identifier. + auto merge = [&polyA, &polyB](unsigned i, unsigned j) -> bool { + eliminateRedundantLocalId(polyA, i, j); + eliminateRedundantLocalId(polyB, i, j); + return true; + }; - divsA.erase(divsA.begin() + j); - denomsA.erase(denomsA.begin() + j); - // Since `j` can never be zero, we do not need to worry about overflows. - --j; - } - } + // Merge all divisions by removing duplicate divisions. + unsigned localOffset = getIdKindOffset(IdKind::Local); + removeDuplicateDivs(divsA, denomsA, localOffset, merge); } /// Removes local variables using equalities. Each equality is checked if it diff --git a/mlir/lib/Analysis/Presburger/Utils.cpp b/mlir/lib/Analysis/Presburger/Utils.cpp --- a/mlir/lib/Analysis/Presburger/Utils.cpp +++ b/mlir/lib/Analysis/Presburger/Utils.cpp @@ -190,3 +190,54 @@ } return repr; } + +void presburger_utils::removeDuplicateDivs( + std::vector> &divs, + SmallVectorImpl &denoms, unsigned localOffset, + llvm::function_ref merge) { + + // Find and merge duplicate divisions. + // TODO: Add division normalization to support divisions that differ by + // a constant. + // TODO: Add division ordering such that a division representation for local + // identifier at position `i` only depends on local identifiers at position < + // `i`. This would make sure that all divisions depending on other local + // variables that can be merged, are merged. + for (unsigned i = 0; i < divs.size(); ++i) { + // Check if a division representation exists for the `i^th` local id. + if (denoms[i] == 0) + continue; + // Check if a division exists which is a duplicate of the division at `i`. + for (unsigned j = i + 1; j < divs.size(); ++j) { + // Check if a division representation exists for the `j^th` local id. + if (denoms[j] == 0) + continue; + // Check if the denominators match. + if (denoms[i] != denoms[j]) + continue; + // Check if the representations are equal. + if (divs[i] != divs[j]) + continue; + + // Merge divisions at position `j` into division at position `i`. If + // merge fails, do not merge these divs. + bool mergeResult = merge(i, j); + if (!mergeResult) + continue; + + // Update division information to reflect merging. + for (unsigned k = 0, g = divs.size(); k < g; ++k) { + SmallVector &div = divs[k]; + if (denoms[k] != 0) { + div[localOffset + i] += div[localOffset + j]; + div.erase(div.begin() + localOffset + j); + } + } + + divs.erase(divs.begin() + j); + denoms.erase(denoms.begin() + j); + // Since `j` can never be zero, we do not need to worry about overflows. + --j; + } + } +}