diff --git a/mlir/include/mlir/Analysis/Presburger/Simplex.h b/mlir/include/mlir/Analysis/Presburger/Simplex.h --- a/mlir/include/mlir/Analysis/Presburger/Simplex.h +++ b/mlir/include/mlir/Analysis/Presburger/Simplex.h @@ -237,6 +237,13 @@ void print(raw_ostream &os) const; void dump() const; + /// Check if the specified inequality already holds in the polytope. + bool isRedundant(ArrayRef coeffs); + + /// Check if the specified FAC contains the polytope, + /// i.e. whether all inequalities of the specified FAC hold for the polytope. + bool containedIn(const FlatAffineConstraints &fac); + private: friend class GBRSimplex; diff --git a/mlir/include/mlir/Analysis/PresburgerSet.h b/mlir/include/mlir/Analysis/PresburgerSet.h --- a/mlir/include/mlir/Analysis/PresburgerSet.h +++ b/mlir/include/mlir/Analysis/PresburgerSet.h @@ -94,6 +94,12 @@ /// any of the FACs in the union are unbounded. bool findIntegerSample(SmallVectorImpl &sample); + /// Simplifies the representation of a PresburgerSet. + /// + /// Inparticular, removes all FACs which are subset of other FACs in the + /// union. + PresburgerSet coalesce(); + private: /// Construct an empty PresburgerSet. PresburgerSet(unsigned nDim = 0, unsigned nSym = 0) diff --git a/mlir/lib/Analysis/Presburger/Simplex.cpp b/mlir/lib/Analysis/Presburger/Simplex.cpp --- a/mlir/lib/Analysis/Presburger/Simplex.cpp +++ b/mlir/lib/Analysis/Presburger/Simplex.cpp @@ -1240,4 +1240,25 @@ void Simplex::dump() const { print(llvm::errs()); } +bool Simplex::containedIn(const FlatAffineConstraints &fac) { + + if (isEmpty()) + return true; + + for (unsigned i = 0, e = fac.getNumInequalities(); i < e; ++i) + if (!isRedundant(fac.getInequality(i))) + return false; + + for (unsigned i = 0, e = fac.getNumEqualities(); i < e; ++i) + if (!isRedundant(fac.getEquality(i))) + return false; + + return true; +} + +bool Simplex::isRedundant(ArrayRef coeffs) { + Optional minimum = computeOptimum(Direction::Down, coeffs); + return minimum && *minimum >= Fraction(0, 1); +} + } // namespace mlir diff --git a/mlir/lib/Analysis/PresburgerSet.cpp b/mlir/lib/Analysis/PresburgerSet.cpp --- a/mlir/lib/Analysis/PresburgerSet.cpp +++ b/mlir/lib/Analysis/PresburgerSet.cpp @@ -381,6 +381,39 @@ return false; } +PresburgerSet PresburgerSet::coalesce() { + PresburgerSet newSet = + PresburgerSet::getEmptySet(this->getNumDims(), this->getNumSyms()); + SmallVector marked(this->getNumFACs()); + + for (unsigned i = 0, e = flatAffineConstraints.size(); i < e; i++) { + if (marked[i]) + continue; + Simplex simplex(flatAffineConstraints[i]); + + if (simplex.isEmpty()) { + marked[i] = true; + continue; + } + // check if bs1 is contained in any basicSet + for (unsigned j = 0, e = flatAffineConstraints.size(); j < e; ++j) { + if (j == i || marked[j]) + continue; + + if (simplex.containedIn(flatAffineConstraints[j])) { + marked[i] = true; + break; + } + } + } + + for (unsigned i = 0, e = flatAffineConstraints.size(); i < e; ++i) { + if (!marked[i]) + newSet.unionFACInPlace(flatAffineConstraints[i]); + } + return newSet; +} + void PresburgerSet::print(raw_ostream &os) const { os << getNumFACs() << " FlatAffineConstraints:\n"; for (const FlatAffineConstraints &fac : flatAffineConstraints) { diff --git a/mlir/unittests/Analysis/FACUtils.h b/mlir/unittests/Analysis/FACUtils.h new file mode 100644 --- /dev/null +++ b/mlir/unittests/Analysis/FACUtils.h @@ -0,0 +1,41 @@ +//===- FACUtils.h - utility functions for testing -------------------------===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// + +#include "mlir/Analysis/AffineStructures.h" + +namespace mlir { + +/// Construct a FlatAffineConstraints from a set of inequality and +/// equality constraints. `numIds` is the total number of ids, of which +/// `numLocals` is the number of local ids. +static FlatAffineConstraints +makeFACFromConstraints(unsigned numIds, ArrayRef> ineqs, + ArrayRef> eqs, + unsigned numLocals = 0) { + FlatAffineConstraints fac(/*numReservedInequalities=*/ineqs.size(), + /*numReservedEqualities=*/eqs.size(), + /*numReservedCols=*/numIds + 1, + /*numDims=*/numIds - numLocals, + /*numSymbols=*/0, numLocals); + for (const SmallVector &eq : eqs) + fac.addEquality(eq); + for (const SmallVector &ineq : ineqs) + fac.addInequality(ineq); + return fac; +} + +/// Construct a FlatAffineConstraints having `numDims` dimensions from the given +/// set of inequality constraints. This is a convenience function to be used +/// when the FAC to be constructed does not have any local ids and does not have +/// equalties. +static FlatAffineConstraints +makeFACFromIneqs(unsigned dims, ArrayRef> ineqs) { + return makeFACFromConstraints(dims, ineqs, {}); +} + +} // namespace mlir diff --git a/mlir/unittests/Analysis/Presburger/CMakeLists.txt b/mlir/unittests/Analysis/Presburger/CMakeLists.txt --- a/mlir/unittests/Analysis/Presburger/CMakeLists.txt +++ b/mlir/unittests/Analysis/Presburger/CMakeLists.txt @@ -4,5 +4,5 @@ ) target_link_libraries(MLIRPresburgerTests - PRIVATE MLIRPresburger) - + PRIVATE MLIRPresburger + MLIRLoopAnalysis) diff --git a/mlir/unittests/Analysis/Presburger/SimplexTest.cpp b/mlir/unittests/Analysis/Presburger/SimplexTest.cpp --- a/mlir/unittests/Analysis/Presburger/SimplexTest.cpp +++ b/mlir/unittests/Analysis/Presburger/SimplexTest.cpp @@ -7,6 +7,7 @@ //===----------------------------------------------------------------------===// #include "mlir/Analysis/Presburger/Simplex.h" +#include "../FACUtils.h" #include #include @@ -410,4 +411,62 @@ EXPECT_EQ(simplex.getNumConstraints(), 0u); } +TEST(SimplexTest, isRedundant) { + Simplex simplex(2); + simplex.addInequality({0, -1, 2}); // [0]: y <= 2. + simplex.addInequality({1, 0, 0}); // [1]: x >= 0. + simplex.addEquality({-1, 1, 0}); // [2]: y = x. + + EXPECT_TRUE(simplex.isRedundant({-1, 0, 2})); // x <= 2. + EXPECT_TRUE(simplex.isRedundant({0, 1, 0})); // y >= 0. + + EXPECT_FALSE(simplex.isRedundant({-1, 0, -1})); // x <= -1. + EXPECT_FALSE(simplex.isRedundant({0, 1, -2})); // y >= 2. + EXPECT_FALSE(simplex.isRedundant({0, 1, -1})); // y >= 1. +} + +TEST(SimplexTest, ContainedIn) { + + FlatAffineConstraints univ = FlatAffineConstraints::getUniverse(1, 0); + + FlatAffineConstraints empty = makeFACFromIneqs(1, {{1, 0}, // x >= 0. + {-1, -1}}); // x <= -1. + + FlatAffineConstraints s1 = makeFACFromIneqs(1, {{1, 0}, // x >= 0. + {-1, 4}}); // x <= 4. + + FlatAffineConstraints s2 = makeFACFromIneqs(1, {{1, -1}, // x >= 1. + {-1, 3}}); // x <= 3. + + Simplex simUniv(univ); + Simplex simEmpty(empty); + Simplex sim1(s1); + Simplex sim2(s2); + + EXPECT_TRUE(simUniv.containedIn(univ)); + EXPECT_TRUE(simEmpty.containedIn(empty)); + EXPECT_TRUE(sim1.containedIn(s1)); + EXPECT_TRUE(sim2.containedIn(s2)); + + EXPECT_TRUE(simEmpty.containedIn(univ)); + EXPECT_TRUE(simEmpty.containedIn(s1)); + EXPECT_TRUE(simEmpty.containedIn(s2)); + EXPECT_TRUE(simEmpty.containedIn(empty)); + + EXPECT_TRUE(simUniv.containedIn(univ)); + EXPECT_FALSE(simUniv.containedIn(s1)); + EXPECT_FALSE(simUniv.containedIn(s2)); + EXPECT_FALSE(simUniv.containedIn(empty)); + + EXPECT_TRUE(sim1.containedIn(univ)); + EXPECT_TRUE(sim1.containedIn(s1)); + EXPECT_FALSE(sim1.containedIn(s2)); + EXPECT_FALSE(sim1.containedIn(empty)); + + EXPECT_TRUE(sim2.containedIn(univ)); + EXPECT_TRUE(sim2.containedIn(s1)); + EXPECT_TRUE(sim2.containedIn(s2)); + EXPECT_FALSE(sim2.containedIn(empty)); +} + } // namespace mlir diff --git a/mlir/unittests/Analysis/PresburgerSetTest.cpp b/mlir/unittests/Analysis/PresburgerSetTest.cpp --- a/mlir/unittests/Analysis/PresburgerSetTest.cpp +++ b/mlir/unittests/Analysis/PresburgerSetTest.cpp @@ -15,6 +15,7 @@ //===----------------------------------------------------------------------===// #include "mlir/Analysis/PresburgerSet.h" +#include "./FACUtils.h" #include #include @@ -79,34 +80,6 @@ } } -/// Construct a FlatAffineConstraints from a set of inequality and -/// equality constraints. `numIds` is the total number of ids, of which -/// `numLocals` is the number of local ids. -static FlatAffineConstraints -makeFACFromConstraints(unsigned numIds, ArrayRef> ineqs, - ArrayRef> eqs, - unsigned numLocals = 0) { - FlatAffineConstraints fac(/*numReservedInequalities=*/ineqs.size(), - /*numReservedEqualities=*/eqs.size(), - /*numReservedCols=*/numIds + 1, - /*numDims=*/numIds - numLocals, - /*numSymbols=*/0, numLocals); - for (const SmallVector &eq : eqs) - fac.addEquality(eq); - for (const SmallVector &ineq : ineqs) - fac.addInequality(ineq); - return fac; -} - -/// Construct a FlatAffineConstraints having `numDims` dimensions from the given -/// set of inequality constraints. This is a convenience function to be used -/// when the FAC to be constructed does not have any local ids and does not have -/// equalties. -static FlatAffineConstraints -makeFACFromIneqs(unsigned numDims, ArrayRef> ineqs) { - return makeFACFromConstraints(numDims, ineqs, /*eqs=*/{}); -} - /// Construct a PresburgerSet having `numDims` dimensions and no symbols from /// the given list of FlatAffineConstraints. Each FAC in `facs` should also have /// `numDims` dimensions and no symbols, although it can have any number of @@ -638,4 +611,173 @@ expectEqual(multiples3.intersect(evens), multiples6); } +void expectCoalesce(size_t expectedNumBasicSets, PresburgerSet set) { + PresburgerSet newSet = set.coalesce(); + if (!set.isEqual(newSet) || !(expectedNumBasicSets == newSet.getNumFACs())) { + set.dump(); + newSet.dump(); + } + EXPECT_TRUE(set.isEqual(newSet)); + EXPECT_TRUE(expectedNumBasicSets == newSet.getNumFACs()); +} + +TEST(SetTest, coalesceContainedOneDim) { + PresburgerSet set = + makeSetFromFACs(1, { + makeFACFromIneqs(1, {{1, 0}, // x >= 0. + {-1, 4}}), // x <= 4. + makeFACFromIneqs(1, {{1, -1}, // x >= 1. + {-1, 2}}), // x <= 2. + }); + expectCoalesce(1, set); +} + +TEST(SetTest, coalesceFirstEmpty) { + PresburgerSet set = + makeSetFromFACs(1, { + makeFACFromIneqs(1, {{1, 0}, // x >= 0. + {-1, -1}}), // x <= -1. + makeFACFromIneqs(1, {{1, -1}, // x >= 1. + {-1, 2}}), // x <= 2. + }); + expectCoalesce(1, set); +} + +TEST(SetTest, coalesceSecondEmpty) { + PresburgerSet set = + makeSetFromFACs(1, { + makeFACFromIneqs(1, {{1, -1}, // x >= 1. + {-1, 2}}), // x <= 2. + makeFACFromIneqs(1, {{1, 0}, // x >= 0. + {-1, -1}}), // x <= -1. + }); + expectCoalesce(1, set); +} + +TEST(SetTest, coalesceBothEmpty) { + PresburgerSet set = + makeSetFromFACs(1, { + makeFACFromIneqs(1, {{1, -3}, // x >= 3. + {-1, -1}}), // x <= -1. + makeFACFromIneqs(1, {{1, 0}, // x >= 0. + {-1, -1}}), // x <= -1. + }); + expectCoalesce(0, set); +} + +TEST(SetTest, coalesceFirstUniv) { + PresburgerSet set = + makeSetFromFACs(1, { + makeFACFromIneqs(1, {}), + makeFACFromIneqs(1, {{1, 0}, // x >= 0. + {-1, 1}}), // x <= 1. + }); + expectCoalesce(1, set); +} + +TEST(SetTest, coalesceSecondUniv) { + PresburgerSet set = + makeSetFromFACs(1, { + makeFACFromIneqs(1, {{1, 0}, // x >= 0. + {-1, 1}}), // x <= 1. + makeFACFromIneqs(1, {}), + }); + expectCoalesce(1, set); +} + +TEST(SetTest, coalesceBothUniv) { + PresburgerSet set = makeSetFromFACs(1, { + makeFACFromIneqs(1, {}), + makeFACFromIneqs(1, {}), + }); + expectCoalesce(1, set); +} + +TEST(SetTest, coalesceFirstUnivSecondEmpty) { + PresburgerSet set = + makeSetFromFACs(1, { + makeFACFromIneqs(1, {}), + makeFACFromIneqs(1, {{1, 0}, // x >= 0. + {-1, -1}}), // x <= -1. + }); + expectCoalesce(1, set); +} + +TEST(SetTest, coalesceFirstEmptySecondUniv) { + PresburgerSet set = + makeSetFromFACs(1, { + makeFACFromIneqs(1, {}), + makeFACFromIneqs(1, {{1, 0}, // x >= 0. + {-1, -1}}), // x <= -1. + }); + expectCoalesce(1, set); +} + +TEST(SetTest, coalesceCutOneDim) { + PresburgerSet set = + makeSetFromFACs(1, { + makeFACFromIneqs(1, {{1, 0}, // x >= 0. + {-1, 3}}), // x <= 3. + makeFACFromIneqs(1, {{1, -2}, // x >= 2. + {-1, 4}}), // x <= 4. + }); + expectCoalesce(2, set); +} + +TEST(SetTest, coalesceSeparateOneDim) { + PresburgerSet set = + makeSetFromFACs(1, { + makeFACFromIneqs(1, {{1, 0}, // x >= 0. + {-1, 2}}), // x <= 2. + makeFACFromIneqs(1, {{1, -3}, // x >= 3. + {-1, 4}}), // x <= 4. + }); + expectCoalesce(2, set); +} + +TEST(SetTest, coalesceContainedTwoDim) { + PresburgerSet set = + makeSetFromFACs(2, { + makeFACFromIneqs(2, {{1, 0, 0}, // x >= 0. + {-1, 0, 3}, // x <= 3. + {0, 1, 0}, // y >= 0 + {0, -1, 3}}), // y <= 3. + makeFACFromIneqs(2, {{1, 0, 0}, // x >= 0. + {-1, 0, 3}, // x <= 3. + {0, 1, -2}, // y >= 2. + {0, -1, 3}}), // y <= 3 + }); + expectCoalesce(1, set); +} + +TEST(SetTest, coalesceCutTwoDim) { + PresburgerSet set = + makeSetFromFACs(2, { + makeFACFromIneqs(2, {{1, 0, 0}, // x >= 0. + {-1, 0, 3}, // x <= 3. + {0, 1, 0}, // y >= 0 + {0, -1, 2}}), // y <= 2. + makeFACFromIneqs(2, {{1, 0, 0}, // x >= 0. + {-1, 0, 3}, // x <= 3. + {0, 1, -1}, // y >= 1. + {0, -1, 3}}), // y <= 3 + }); + expectCoalesce(2, set); +} + +TEST(SetTest, coalesceSeparateTwoDim) { + PresburgerSet set = + makeSetFromFACs(2, { + makeFACFromIneqs(2, {{1, 0, 0}, // x >= 0. + {-1, 0, 3}, // x <= 3. + {0, 1, 0}, // y >= 0 + {0, -1, 1}}), // y <= 1. + makeFACFromIneqs(2, {{1, 0, 0}, // x >= 0. + {-1, 0, 3}, // x <= 3. + {0, 1, -2}, // y >= 2. + {0, -1, 3}}), // y <= 3 + }); + expectCoalesce(2, set); +} + } // namespace mlir