From b754d09fde0b5f82acfd1d5e0423271823db4905 Mon Sep 17 00:00:00 2001 From: Groverkss Date: Mon, 24 Jan 2022 18:11:55 +0530 Subject: [PATCH] [MLIR][Presburger] Refactor duplicate division merging to Utils This patch moves merging of duplicate divisions to presburger utility functions. This is required to support division merging in structures other than IntegerPolyhedron. Reviewed By: arjunp Differential Revision: https://reviews.llvm.org/D118001 --- mlir/include/mlir/Analysis/Presburger/Utils.h | 17 ++++++++ mlir/lib/Analysis/Presburger/IntegerPolyhedron.cpp | 50 +++++---------------- mlir/lib/Analysis/Presburger/Utils.cpp | 51 ++++++++++++++++++++++ 3 files changed, 78 insertions(+), 40 deletions(-) diff --git a/mlir/include/mlir/Analysis/Presburger/Utils.h b/mlir/include/mlir/Analysis/Presburger/Utils.h index 637ab59..d9d7be4 100644 --- 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 @@ MaybeLocalRepr computeSingleVarRepr(const IntegerPolyhedron &cst, 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 index b936016..0080756 100644 --- a/mlir/lib/Analysis/Presburger/IntegerPolyhedron.cpp +++ b/mlir/lib/Analysis/Presburger/IntegerPolyhedron.cpp @@ -1090,47 +1090,17 @@ void IntegerPolyhedron::mergeLocalIds(IntegerPolyhedron &other) { 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 index 7b8fe49..373dce2 100644 --- a/mlir/lib/Analysis/Presburger/Utils.cpp +++ b/mlir/lib/Analysis/Presburger/Utils.cpp @@ -190,3 +190,54 @@ MaybeLocalRepr presburger_utils::computeSingleVarRepr( } 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; + } + } +} -- 2.7.4