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,18 @@ void print(raw_ostream &os) const; void dump() const; + /// Check if the specified inequality already holds in the polytope. + bool isRedundantInequality(ArrayRef coeffs); + + /// Check if the specified equality already holds in the polytope. + bool isRedundantEquality(ArrayRef coeffs); + + /// Check if the specified FAC contains the polytope, + /// i.e. whether all constraints of the specified FAC hold for the polytope. + /// If the FAC backing `this` is empty, returns always true. + /// If `fac` is empty, returns false unless the FAC backing `this` is empty. + 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. + /// + /// In particular, removes all FACs which are subsets 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,39 @@ 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 (!isRedundantInequality(fac.getInequality(i))) + return false; + + for (unsigned i = 0, e = fac.getNumEqualities(); i < e; ++i) + if (!isRedundantEquality(fac.getEquality(i))) + return false; + + return true; +} + +/// Computes the minimum value `coeffs` can take. If the value is greater +/// than zero, the entire FAC backing `this` lies in the subplane defined +/// by `coeffs`. +bool Simplex::isRedundantInequality(ArrayRef coeffs) { + Optional minimum = computeOptimum(Direction::Down, coeffs); + return minimum && *minimum >= Fraction(0, 1); +} + +/// Computes the minimum and maximum value `coeffs` can take. If the +/// minimum is greater than 0 and the maximum is less than 0, the +/// FAC backing `this` is entirely contained in the both subplanes +/// defined by `coeffs`, hence it is contained in the equality defined +/// by `coeffs`. +bool Simplex::isRedundantEquality(ArrayRef coeffs) { + Optional minimum = computeOptimum(Direction::Down, coeffs); + Optional maximum = computeOptimum(Direction::Up, coeffs); + return minimum && maximum && *maximum <= Fraction(0, 1) && + *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,43 @@ return false; } +PresburgerSet PresburgerSet::coalesce() { + PresburgerSet newSet = PresburgerSet::getEmptySet(getNumDims(), getNumSyms()); + // Marking an FAC implies that it will be dropped. + llvm::SmallBitVector marked(getNumFACs()); + + for (unsigned i = 0, e = flatAffineConstraints.size(); i < e; ++i) { + if (marked[i]) + continue; + Simplex simplex(flatAffineConstraints[i]); + + // Check whether the FAC backing `simplex` is empty. If so, it can be + // marked. + if (simplex.isEmpty()) { + marked[i] = true; + continue; + } + + // Check whether `bs1` is contained in any FAC, that is different from + // itself and not yet marked. + 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/AffineStructuresTest.cpp b/mlir/unittests/Analysis/AffineStructuresTest.cpp --- a/mlir/unittests/Analysis/AffineStructuresTest.cpp +++ b/mlir/unittests/Analysis/AffineStructuresTest.cpp @@ -7,6 +7,7 @@ //===----------------------------------------------------------------------===// #include "mlir/Analysis/AffineStructures.h" +#include "./Utils.h" #include "mlir/IR/IntegerSet.h" #include "mlir/IR/MLIRContext.h" @@ -52,21 +53,6 @@ } } -/// Construct a FlatAffineConstraints from a set of inequality and -/// equality constraints. -static FlatAffineConstraints -makeFACFromConstraints(unsigned ids, ArrayRef> ineqs, - ArrayRef> eqs, - unsigned syms = 0) { - FlatAffineConstraints fac(ineqs.size(), eqs.size(), ids + 1, ids - syms, syms, - /*numLocals=*/0); - for (const auto &eq : eqs) - fac.addEquality(eq); - for (const auto &ineq : ineqs) - fac.addInequality(ineq); - return fac; -} - /// Check sampling for all the permutations of the dimensions for the given /// constraint set. Since the GBR algorithm progresses dimension-wise, different /// orderings may cause the algorithm to proceed differently. At least some of @@ -434,7 +420,7 @@ { {1, -1, 0}, }, - 1); + 0, 1); EXPECT_FALSE(fac6.isIntegerEmpty()); } 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 "../Utils.h" #include #include @@ -410,4 +411,75 @@ EXPECT_EQ(simplex.getNumConstraints(), 0u); } +TEST(SimplexTest, isRedundantInequality) { + Simplex simplex(2); + simplex.addInequality({0, -1, 2}); // y <= 2. + simplex.addInequality({1, 0, 0}); // x >= 0. + simplex.addEquality({-1, 1, 0}); // y = x. + + EXPECT_TRUE(simplex.isRedundantInequality({-1, 0, 2})); // x <= 2. + EXPECT_TRUE(simplex.isRedundantInequality({0, 1, 0})); // y >= 0. + + EXPECT_FALSE(simplex.isRedundantInequality({-1, 0, -1})); // x <= -1. + EXPECT_FALSE(simplex.isRedundantInequality({0, 1, -2})); // y >= 2. + EXPECT_FALSE(simplex.isRedundantInequality({0, 1, -1})); // y >= 1. +} + +TEST(SimplexTest, isRedundantEquality) { + Simplex simplex(2); + simplex.addInequality({0, -1, 2}); // y <= 2. + simplex.addInequality({1, 0, 0}); // x >= 0. + simplex.addEquality({-1, 1, 0}); // y = x. + + EXPECT_TRUE(simplex.isRedundantEquality({-1, 1, 0})); // y = x. + EXPECT_TRUE(simplex.isRedundantEquality({1, -1, 0})); // x = y. + + EXPECT_FALSE(simplex.isRedundantEquality({0, 1, -1})); // y = 1. + + simplex.addEquality({0, -1, 2}); // y = 2. + + EXPECT_TRUE(simplex.isRedundantEquality({-1, 0, 2})); // x = 2. +} + +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 "./Utils.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,254 @@ 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, coalesceNoFAC) { + PresburgerSet set = makeSetFromFACs(0, {}); + expectCoalesce(0, set); +} + +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); +} + +TEST(SetTest, coalesceContainedEq) { + PresburgerSet set = + makeSetFromFACs(2, { + makeFACFromConstraints(2, + {{1, 0, 0}, // x >= 0. + {-1, 0, 3}}, // x <= 3. + {{1, -1, 0}}), // x = y + makeFACFromConstraints(2, + {{1, 0, -1}, // x >= 1. + {-1, 0, 2}}, // x <= 2. + {{1, -1, 0}}) // x = y + }); + expectCoalesce(1, set); +} + +TEST(SetTest, coalesceCuttingEq) { + PresburgerSet set = + makeSetFromFACs(2, { + makeFACFromConstraints(2, + {{1, 0, -1}, // x >= 1. + {-1, 0, 3}}, // x <= 3. + {{1, -1, 0}}), // x = y + makeFACFromConstraints(2, + {{1, 0, 0}, // x >= 0. + {-1, 0, 2}}, // x <= 2. + {{1, -1, 0}}) // x = y + }); + expectCoalesce(2, set); +} + +TEST(SetTest, coalesceSeparateEq) { + PresburgerSet set = + makeSetFromFACs(2, { + makeFACFromConstraints(2, + {{1, 0, -3}, // x >= 3. + {-1, 0, 4}}, // x <= 4. + {{1, -1, 0}}), // x = y + makeFACFromConstraints(2, + {{1, 0, 0}, // x >= 0. + {-1, 0, 1}}, // x <= 1. + {{1, -1, 0}}) // x = y + }); + expectCoalesce(2, set); +} + +TEST(SetTest, coalesceContainedEqAsIneq) { + PresburgerSet set = + makeSetFromFACs(2, { + makeFACFromConstraints(2, + {{1, 0, 0}, // x >= 0. + {-1, 0, 3}, // x <= 3. + {1, -1, 0}, // x >= y + {-1, 1, 0}}, // x <= y + {}), + makeFACFromConstraints(2, + {{1, 0, -1}, // x >= 1. + {-1, 0, 2}}, // x <= 2. + {{1, -1, 0}}) // x = y + }); + expectCoalesce(1, set); +} + +TEST(SetTest, coalesceContainedEqComplex) { + PresburgerSet set = + makeSetFromFACs(2, { + makeFACFromConstraints(2, {}, + {{1, -1, 0}, // x = y + {1, 0, -2}}), // x = 2 + makeFACFromConstraints(2, + {{1, 0, -1}, // x >= 1. + {-1, 0, 2}}, // x <= 2. + {{1, -1, 0}}) // x = y + }); + expectCoalesce(1, set); +} + } // namespace mlir diff --git a/mlir/unittests/Analysis/Utils.h b/mlir/unittests/Analysis/Utils.h new file mode 100644 --- /dev/null +++ b/mlir/unittests/Analysis/Utils.h @@ -0,0 +1,47 @@ +//===- Utils.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 +// +//===----------------------------------------------------------------------===// + +#ifndef MLIR_UNITTESTS_ANALYSIS_FACUTILS_H +#define MLIR_UNITTESTS_ANALYSIS_FACUTILS_H + +#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, unsigned numSymbols = 0) { + FlatAffineConstraints fac(/*numReservedInequalities=*/ineqs.size(), + /*numReservedEqualities=*/eqs.size(), + /*numReservedCols=*/numIds + 1, + /*numDims=*/numIds - numLocals - numSymbols, + /*numSymbols=*/numSymbols, + /*numLocals=*/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 + +#endif // MLIR_UNITTESTS_ANALYSIS_FACUTILS_H