diff --git a/mlir/include/mlir/Analysis/Presburger/PWMAFunction.h b/mlir/include/mlir/Analysis/Presburger/PWMAFunction.h --- a/mlir/include/mlir/Analysis/Presburger/PWMAFunction.h +++ b/mlir/include/mlir/Analysis/Presburger/PWMAFunction.h @@ -17,7 +17,7 @@ #define MLIR_ANALYSIS_PRESBURGER_PWMAFUNCTION_H #include "mlir/Analysis/Presburger/IntegerRelation.h" -#include "mlir/Analysis/Presburger/PresburgerSet.h" +#include "mlir/Analysis/Presburger/PresburgerRelation.h" namespace mlir { namespace presburger { diff --git a/mlir/include/mlir/Analysis/Presburger/PresburgerRelation.h b/mlir/include/mlir/Analysis/Presburger/PresburgerRelation.h new file mode 100644 --- /dev/null +++ b/mlir/include/mlir/Analysis/Presburger/PresburgerRelation.h @@ -0,0 +1,157 @@ +//===- PresburgerRelation.h - MLIR PresburgerRelation Class -----*- C++ -*-===// +// +// 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 +// +//===----------------------------------------------------------------------===// +// +// A class to represent unions of IntegerRelations. +// +//===----------------------------------------------------------------------===// + +#ifndef MLIR_ANALYSIS_PRESBURGER_PRESBURGERRELATION_H +#define MLIR_ANALYSIS_PRESBURGER_PRESBURGERRELATION_H + +#include "mlir/Analysis/Presburger/IntegerRelation.h" + +namespace mlir { +namespace presburger { + +/// A PresburgerRelation represents a union of IntegerRelations that live in +/// the same PresburgerSpace with support for union, intersection, subtraction, +/// and complement operations, as well as sampling. +/// +/// The IntegerRelations (relations) are stored in a vector, and the set +/// represents the union of these relations. An empty list corresponds to +/// the empty set. +/// +/// Note that there are no invariants guaranteed on the list of relations +/// other than that they are all in the same PresburgerSpace. For example, the +/// relations may overlap with each other. +class PresburgerRelation : public PresburgerSpace { +public: + /// Return a universe set of the specified type that contains all points. + static PresburgerRelation getUniverse(unsigned numDomain, unsigned numRange, + unsigned numSymbols); + + /// Return an empty set of the specified type that contains no points. + static PresburgerRelation getEmpty(unsigned numDomain = 0, + unsigned numRange = 0, + unsigned numSymbols = 0); + + explicit PresburgerRelation(const IntegerRelation &disjunct); + + /// Return the number of Disjuncts in the union. + unsigned getNumDisjuncts() const; + + /// Return a reference to the list of IntegerRelations. + ArrayRef getAllDisjuncts() const; + + /// Return the IntegerRelation at the specified index. + const IntegerRelation &getDisjunct(unsigned index) const; + + /// Mutate this set, turning it into the union of this set and the given + /// IntegerRelation. + void unionInPlace(const IntegerRelation &disjunct); + + /// Mutate this set, turning it into the union of this set and the given set. + void unionInPlace(const PresburgerRelation &set); + + /// Return the union of this set and the given set. + PresburgerRelation unionSet(const PresburgerRelation &set) const; + + /// Return the intersection of this set and the given set. + PresburgerRelation intersect(const PresburgerRelation &set) const; + + /// Return true if the set contains the given point, and false otherwise. + bool containsPoint(ArrayRef point) const; + + /// Return the complement of this set. All local variables in the set must + /// correspond to floor divisions. + PresburgerRelation complement() const; + + /// Return the set difference of this set and the given set, i.e., + /// return `this \ set`. All local variables in `set` must correspond + /// to floor divisions, but local variables in `this` need not correspond to + /// divisions. + PresburgerRelation subtract(const PresburgerRelation &set) const; + + /// Return true if this set is a subset of the given set, and false otherwise. + bool isSubsetOf(const PresburgerRelation &set) const; + + /// Return true if this set is equal to the given set, and false otherwise. + /// All local variables in both sets must correspond to floor divisions. + bool isEqual(const PresburgerRelation &set) const; + + /// Return true if all the sets in the union are known to be integer empty + /// false otherwise. + bool isIntegerEmpty() const; + + /// Find an integer sample from the given set. This should not be called if + /// any of the disjuncts in the union are unbounded. + bool findIntegerSample(SmallVectorImpl &sample); + + /// Compute an overapproximation of the number of integer points in the + /// disjunct. Symbol ids are currently not supported. If the computed + /// overapproximation is infinite, an empty optional is returned. + /// + /// This currently just sums up the overapproximations of the volumes of the + /// disjuncts, so the approximation might be far from the true volume in the + /// case when there is a lot of overlap between disjuncts. + Optional computeVolume() const; + + /// Simplifies the representation of a PresburgerRelation. + /// + /// In particular, removes all disjuncts which are subsets of other + /// disjuncts in the union. + PresburgerRelation coalesce() const; + + /// Print the set's internal state. + void print(raw_ostream &os) const; + void dump() const; + +protected: + /// Construct an empty PresburgerRelation with the specified number of + /// dimension and symbols. + PresburgerRelation(unsigned numDomain = 0, unsigned numRange = 0, + unsigned numSymbols = 0) + : PresburgerSpace(numDomain, numRange, numSymbols) {} + + /// The list of disjuncts that this set is the union of. + SmallVector integerRelations; +}; + +class PresburgerSet : public PresburgerRelation { +public: + /// Return a universe set of the specified type that contains all points. + static PresburgerSet getUniverse(unsigned numDims = 0, + unsigned numSymbols = 0); + + /// Return an empty set of the specified type that contains no points. + static PresburgerSet getEmpty(unsigned numDims = 0, unsigned numSymbols = 0); + + /// Create a set from a relation. + explicit PresburgerSet(const IntegerPolyhedron &disjunct); + explicit PresburgerSet(const PresburgerRelation &set); + + /// These operations are the same as the ones in PresburgeRelation, they just + /// forward the arguement and return the result as a set instead of a + /// relation. + PresburgerSet unionSet(const PresburgerRelation &set) const; + PresburgerSet intersect(const PresburgerRelation &set) const; + PresburgerSet complement() const; + PresburgerSet subtract(const PresburgerRelation &set) const; + PresburgerSet coalesce() const; + +protected: + /// Construct an empty PresburgerRelation with the specified number of + /// dimension and symbols. + PresburgerSet(unsigned numDims = 0, unsigned numSymbols = 0) + : PresburgerRelation(/*numDomain=*/0, numDims, numSymbols) {} +}; + +} // namespace presburger +} // namespace mlir + +#endif // MLIR_ANALYSIS_PRESBURGER_PRESBURGERRELATION_H diff --git a/mlir/include/mlir/Analysis/Presburger/PresburgerSet.h b/mlir/include/mlir/Analysis/Presburger/PresburgerSet.h deleted file mode 100644 --- a/mlir/include/mlir/Analysis/Presburger/PresburgerSet.h +++ /dev/null @@ -1,126 +0,0 @@ -//===- Set.h - MLIR PresburgerSet Class -------------------------*- C++ -*-===// -// -// 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 -// -//===----------------------------------------------------------------------===// -// -// A class to represent unions of IntegerPolyhedrons. -// -//===----------------------------------------------------------------------===// - -#ifndef MLIR_ANALYSIS_PRESBURGER_PRESBURGERSET_H -#define MLIR_ANALYSIS_PRESBURGER_PRESBURGERSET_H - -#include "mlir/Analysis/Presburger/IntegerRelation.h" - -namespace mlir { -namespace presburger { - -/// A PresburgerSet represents a union of IntegerPolyhedrons that live in the -/// same PresburgerSpace with support for union, intersection, subtraction, and -/// complement operations, as well as sampling. -/// -/// The IntegerPolyhedrons (polyhedrons) are stored in a vector, and the set -/// represents the union of these polyhedrons. An empty list corresponds to the -/// empty set. -/// -/// Note that there are no invariants guaranteed on the list of polyhedrons -/// other than that they are all in the same PresburgerSpace, i.e., they all -/// have the same number of dimensions and symbols. For example, the polyhedrons -/// may overlap each other. -class PresburgerSet : public PresburgerSpace { -public: - /// Return a universe set of the specified type that contains all points. - static PresburgerSet getUniverse(unsigned numDims = 0, - unsigned numSymbols = 0); - /// Return an empty set of the specified type that contains no points. - static PresburgerSet getEmptySet(unsigned numDims = 0, - unsigned numSymbols = 0); - - explicit PresburgerSet(const IntegerPolyhedron &poly); - - /// Return the number of Polys in the union. - unsigned getNumPolys() const; - - /// Return a reference to the list of IntegerPolyhedrons. - ArrayRef getAllPolys() const; - - /// Return the IntegerPolyhedron at the specified index. - const IntegerPolyhedron &getPoly(unsigned index) const; - - /// Mutate this set, turning it into the union of this set and the given - /// IntegerPolyhedron. - void unionInPlace(const IntegerPolyhedron &poly); - - /// Mutate this set, turning it into the union of this set and the given set. - void unionInPlace(const PresburgerSet &set); - - /// Return the union of this set and the given set. - PresburgerSet unionSet(const PresburgerSet &set) const; - - /// Return the intersection of this set and the given set. - PresburgerSet intersect(const PresburgerSet &set) const; - - /// Return true if the set contains the given point, and false otherwise. - bool containsPoint(ArrayRef point) const; - - /// Return the complement of this set. All local variables in the set must - /// correspond to floor divisions. - PresburgerSet complement() const; - - /// Return the set difference of this set and the given set, i.e., - /// return `this \ set`. All local variables in `set` must correspond - /// to floor divisions, but local variables in `this` need not correspond to - /// divisions. - PresburgerSet subtract(const PresburgerSet &set) const; - - /// Return true if this set is a subset of the given set, and false otherwise. - bool isSubsetOf(const PresburgerSet &set) const; - - /// Return true if this set is equal to the given set, and false otherwise. - /// All local variables in both sets must correspond to floor divisions. - bool isEqual(const PresburgerSet &set) const; - - /// Return true if all the sets in the union are known to be integer empty - /// false otherwise. - bool isIntegerEmpty() const; - - /// Find an integer sample from the given set. This should not be called if - /// any of the polyhedrons in the union are unbounded. - bool findIntegerSample(SmallVectorImpl &sample); - - /// Compute an overapproximation of the number of integer points in the - /// polyhedron. Symbol ids are currently not supported. If the computed - /// overapproximation is infinite, an empty optional is returned. - /// - /// This currently just sums up the overapproximations of the volumes of the - /// disjuncts, so the approximation might be far from the true volume in the - /// case when there is a lot of overlap between disjuncts. - Optional computeVolume() const; - - /// Simplifies the representation of a PresburgerSet. - /// - /// In particular, removes all polyhedrons which are subsets of other - /// polyhedrons in the union. - PresburgerSet coalesce() const; - - /// Print the set's internal state. - void print(raw_ostream &os) const; - void dump() const; - -private: - /// Construct an empty PresburgerSet with the specified number of dimension - /// and symbols. - PresburgerSet(unsigned numDims = 0, unsigned numSymbols = 0) - : PresburgerSpace(/*numDomain=*/0, /*numRange=*/numDims, numSymbols) {} - - /// The list of polyhedrons that this set is the union of. - SmallVector integerPolyhedrons; -}; - -} // namespace presburger -} // namespace mlir - -#endif // MLIR_ANALYSIS_PRESBURGER_PRESBURGERSET_H diff --git a/mlir/lib/Analysis/Presburger/CMakeLists.txt b/mlir/lib/Analysis/Presburger/CMakeLists.txt --- a/mlir/lib/Analysis/Presburger/CMakeLists.txt +++ b/mlir/lib/Analysis/Presburger/CMakeLists.txt @@ -2,7 +2,7 @@ IntegerRelation.cpp LinearTransform.cpp Matrix.cpp - PresburgerSet.cpp + PresburgerRelation.cpp PresburgerSpace.cpp PWMAFunction.cpp Simplex.cpp diff --git a/mlir/lib/Analysis/Presburger/IntegerRelation.cpp b/mlir/lib/Analysis/Presburger/IntegerRelation.cpp --- a/mlir/lib/Analysis/Presburger/IntegerRelation.cpp +++ b/mlir/lib/Analysis/Presburger/IntegerRelation.cpp @@ -14,7 +14,7 @@ #include "mlir/Analysis/Presburger/IntegerRelation.h" #include "mlir/Analysis/Presburger/LinearTransform.h" -#include "mlir/Analysis/Presburger/PresburgerSet.h" +#include "mlir/Analysis/Presburger/PresburgerRelation.h" #include "mlir/Analysis/Presburger/Simplex.h" #include "mlir/Analysis/Presburger/Utils.h" #include "llvm/ADT/DenseMap.h" @@ -52,28 +52,14 @@ } } -static IntegerPolyhedron createSetFromRelation(const IntegerRelation &rel) { - IntegerPolyhedron result(rel.getNumDimIds(), rel.getNumSymbolIds(), - rel.getNumLocalIds()); - - for (unsigned i = 0, e = rel.getNumInequalities(); i < e; ++i) - result.addInequality(rel.getInequality(i)); - for (unsigned i = 0, e = rel.getNumEqualities(); i < e; ++i) - result.addEquality(rel.getEquality(i)); - - return result; -} - bool IntegerRelation::isEqual(const IntegerRelation &other) const { assert(PresburgerLocalSpace::isEqual(other) && "Spaces must be equal."); - return PresburgerSet(createSetFromRelation(*this)) - .isEqual(PresburgerSet(createSetFromRelation(other))); + return PresburgerRelation(*this).isEqual(PresburgerRelation(other)); } bool IntegerRelation::isSubsetOf(const IntegerRelation &other) const { assert(PresburgerLocalSpace::isEqual(other) && "Spaces must be equal."); - return PresburgerSet(createSetFromRelation(*this)) - .isSubsetOf(PresburgerSet(createSetFromRelation(other))); + return PresburgerRelation(*this).isSubsetOf(PresburgerRelation(other)); } MaybeOptimum> diff --git a/mlir/lib/Analysis/Presburger/PWMAFunction.cpp b/mlir/lib/Analysis/Presburger/PWMAFunction.cpp --- a/mlir/lib/Analysis/Presburger/PWMAFunction.cpp +++ b/mlir/lib/Analysis/Presburger/PWMAFunction.cpp @@ -28,7 +28,7 @@ PresburgerSet PWMAFunction::getDomain() const { PresburgerSet domain = - PresburgerSet::getEmptySet(getNumDimIds(), getNumSymbolIds()); + PresburgerSet::getEmpty(getNumDimIds(), getNumSymbolIds()); for (const MultiAffineFunction &piece : pieces) domain.unionInPlace(piece.getDomain()); return domain; diff --git a/mlir/lib/Analysis/Presburger/PresburgerSet.cpp b/mlir/lib/Analysis/Presburger/PresburgerRelation.cpp rename from mlir/lib/Analysis/Presburger/PresburgerSet.cpp rename to mlir/lib/Analysis/Presburger/PresburgerRelation.cpp --- a/mlir/lib/Analysis/Presburger/PresburgerSet.cpp +++ b/mlir/lib/Analysis/Presburger/PresburgerRelation.cpp @@ -1,4 +1,4 @@ -//===- Set.cpp - MLIR PresburgerSet Class ---------------------------------===// +//===- PresburgerRelation.cpp - MLIR PresburgerRelation Class -------------===// // // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. // See https://llvm.org/LICENSE.txt for license information. @@ -6,7 +6,7 @@ // //===----------------------------------------------------------------------===// -#include "mlir/Analysis/Presburger/PresburgerSet.h" +#include "mlir/Analysis/Presburger/PresburgerRelation.h" #include "mlir/Analysis/Presburger/Simplex.h" #include "mlir/Analysis/Presburger/Utils.h" #include "llvm/ADT/STLExtras.h" @@ -16,66 +16,70 @@ using namespace mlir; using namespace presburger; -PresburgerSet::PresburgerSet(const IntegerPolyhedron &poly) - : PresburgerSpace(poly) { - unionInPlace(poly); +PresburgerRelation::PresburgerRelation(const IntegerRelation &disjunct) + : PresburgerSpace(disjunct) { + unionInPlace(disjunct); } -unsigned PresburgerSet::getNumPolys() const { - return integerPolyhedrons.size(); +unsigned PresburgerRelation::getNumDisjuncts() const { + return integerRelations.size(); } -ArrayRef PresburgerSet::getAllPolys() const { - return integerPolyhedrons; +ArrayRef PresburgerRelation::getAllDisjuncts() const { + return integerRelations; } -const IntegerPolyhedron &PresburgerSet::getPoly(unsigned index) const { - assert(index < integerPolyhedrons.size() && "index out of bounds!"); - return integerPolyhedrons[index]; +const IntegerRelation &PresburgerRelation::getDisjunct(unsigned index) const { + assert(index < integerRelations.size() && "index out of bounds!"); + return integerRelations[index]; } /// Mutate this set, turning it into the union of this set and the given -/// IntegerPolyhedron. -void PresburgerSet::unionInPlace(const IntegerPolyhedron &poly) { - assert(PresburgerSpace::isEqual(poly) && "Spaces should match"); - integerPolyhedrons.push_back(poly); +/// IntegerRelation. +void PresburgerRelation::unionInPlace(const IntegerRelation &disjunct) { + assert(PresburgerSpace::isEqual(disjunct) && "Spaces should match"); + integerRelations.push_back(disjunct); } /// Mutate this set, turning it into the union of this set and the given set. /// -/// This is accomplished by simply adding all the polyhedrons of the given set +/// This is accomplished by simply adding all the disjuncts of the given set /// to this set. -void PresburgerSet::unionInPlace(const PresburgerSet &set) { +void PresburgerRelation::unionInPlace(const PresburgerRelation &set) { assert(PresburgerSpace::isEqual(set) && "Spaces should match"); - for (const IntegerPolyhedron &poly : set.integerPolyhedrons) - unionInPlace(poly); + for (const IntegerRelation &disjunct : set.integerRelations) + unionInPlace(disjunct); } /// Return the union of this set and the given set. -PresburgerSet PresburgerSet::unionSet(const PresburgerSet &set) const { +PresburgerRelation +PresburgerRelation::unionSet(const PresburgerRelation &set) const { assert(PresburgerSpace::isEqual(set) && "Spaces should match"); - PresburgerSet result = *this; + PresburgerRelation result = *this; result.unionInPlace(set); return result; } /// A point is contained in the union iff any of the parts contain the point. -bool PresburgerSet::containsPoint(ArrayRef point) const { - return llvm::any_of(integerPolyhedrons, [&](const IntegerPolyhedron &poly) { - return (poly.containsPoint(point)); +bool PresburgerRelation::containsPoint(ArrayRef point) const { + return llvm::any_of(integerRelations, [&](const IntegerRelation &disjunct) { + return (disjunct.containsPoint(point)); }); } -PresburgerSet PresburgerSet::getUniverse(unsigned numDims, - unsigned numSymbols) { - PresburgerSet result(numDims, numSymbols); - result.unionInPlace(IntegerPolyhedron::getUniverse(numDims, numSymbols)); +PresburgerRelation PresburgerRelation::getUniverse(unsigned numDomain, + unsigned numRange, + unsigned numSymbols) { + PresburgerRelation result(numDomain, numRange, numSymbols); + result.unionInPlace( + IntegerRelation::getUniverse(numDomain, numRange, numSymbols)); return result; } -PresburgerSet PresburgerSet::getEmptySet(unsigned numDims, - unsigned numSymbols) { - return PresburgerSet(numDims, numSymbols); +PresburgerRelation PresburgerRelation::getEmpty(unsigned numDomain, + unsigned numRange, + unsigned numSymbols) { + return PresburgerRelation(numDomain, numRange, numSymbols); } // Return the intersection of this set with the given set. @@ -85,13 +89,15 @@ // // If S_i or T_j have local variables, then S_i and T_j contains the local // variables of both. -PresburgerSet PresburgerSet::intersect(const PresburgerSet &set) const { +PresburgerRelation +PresburgerRelation::intersect(const PresburgerRelation &set) const { assert(PresburgerSpace::isEqual(set) && "Spaces should match"); - PresburgerSet result(getNumDimIds(), getNumSymbolIds()); - for (const IntegerPolyhedron &csA : integerPolyhedrons) { - for (const IntegerPolyhedron &csB : set.integerPolyhedrons) { - IntegerPolyhedron csACopy = csA, csBCopy = csB; + PresburgerRelation result(getNumDomainIds(), getNumRangeIds(), + getNumSymbolIds()); + for (const IntegerRelation &csA : integerRelations) { + for (const IntegerRelation &csB : set.integerRelations) { + IntegerRelation csACopy = csA, csBCopy = csB; csACopy.mergeLocalIds(csBCopy); csACopy.append(csBCopy); if (!csACopy.isEmpty()) @@ -129,7 +135,7 @@ /// /// In the following, U denotes union, ^ denotes intersection, \ denotes set /// difference and ~ denotes complement. -/// Let b be the IntegerPolyhedron and s = (U_i s_i) be the set. We want +/// Let b be the IntegerRelation and s = (U_i s_i) be the set. We want /// b \ (U_i s_i). /// /// Let s_i = ^_j s_ij, where each s_ij is a single inequality. To compute @@ -153,20 +159,20 @@ /// /// As a heuristic, we try adding all the constraints and check if simplex /// says that the intersection is empty. If it is, then subtracting this -/// polyhedrons is a no-op and we just skip it. Also, in the process we find out +/// disjuncts is a no-op and we just skip it. Also, in the process we find out /// that some constraints are redundant. These redundant constraints are /// ignored. /// /// b and simplex are callee saved, i.e., their values on return are /// semantically equivalent to their values when the function is called. -static void subtractRecursively(IntegerPolyhedron &b, Simplex &simplex, - const PresburgerSet &s, unsigned i, - PresburgerSet &result) { - if (i == s.getNumPolys()) { +static void subtractRecursively(IntegerRelation &b, Simplex &simplex, + const PresburgerRelation &s, unsigned i, + PresburgerRelation &result) { + if (i == s.getNumDisjuncts()) { result.unionInPlace(b); return; } - IntegerPolyhedron sI = s.getPoly(i); + IntegerRelation sI = s.getDisjunct(i); // Below, we append some additional constraints and ids to b. We want to // rollback b to its initial state before returning, which we will do by @@ -297,68 +303,75 @@ } } -/// Return the set difference poly \ set. +/// Return the set difference disjunct \ set. /// -/// The polyhedron here is modified in subtractRecursively, so it cannot be a +/// The disjunct here is modified in subtractRecursively, so it cannot be a /// const reference even though it is restored to its original state before /// returning from that function. -static PresburgerSet getSetDifference(IntegerPolyhedron poly, - const PresburgerSet &set) { - assert(poly.PresburgerSpace::isEqual(set) && "Spaces should match"); - if (poly.isEmptyByGCDTest()) - return PresburgerSet::getEmptySet(poly.getNumDimIds(), - poly.getNumSymbolIds()); - - PresburgerSet result = - PresburgerSet::getEmptySet(poly.getNumDimIds(), poly.getNumSymbolIds()); - Simplex simplex(poly); - subtractRecursively(poly, simplex, set, 0, result); +static PresburgerRelation getSetDifference(IntegerRelation disjunct, + const PresburgerRelation &set) { + assert(disjunct.PresburgerSpace::isEqual(set) && "Spaces should match"); + if (disjunct.isEmptyByGCDTest()) + return PresburgerRelation::getEmpty(disjunct.getNumDomainIds(), + disjunct.getNumRangeIds(), + disjunct.getNumSymbolIds()); + + PresburgerRelation result = PresburgerRelation::getEmpty( + disjunct.getNumDomainIds(), disjunct.getNumRangeIds(), + disjunct.getNumSymbolIds()); + Simplex simplex(disjunct); + subtractRecursively(disjunct, simplex, set, 0, result); return result; } /// Return the complement of this set. -PresburgerSet PresburgerSet::complement() const { - return getSetDifference( - IntegerPolyhedron::getUniverse(getNumDimIds(), getNumSymbolIds()), *this); +PresburgerRelation PresburgerRelation::complement() const { + return getSetDifference(IntegerRelation::getUniverse(getNumDomainIds(), + getNumRangeIds(), + getNumSymbolIds()), + *this); } /// Return the result of subtract the given set from this set, i.e., /// return `this \ set`. -PresburgerSet PresburgerSet::subtract(const PresburgerSet &set) const { +PresburgerRelation +PresburgerRelation::subtract(const PresburgerRelation &set) const { assert(PresburgerSpace::isEqual(set) && "Spaces should match"); - PresburgerSet result(getNumDimIds(), getNumSymbolIds()); + PresburgerRelation result(getNumDomainIds(), getNumRangeIds(), + getNumSymbolIds()); // We compute (U_i t_i) \ (U_i set_i) as U_i (t_i \ V_i set_i). - for (const IntegerPolyhedron &poly : integerPolyhedrons) - result.unionInPlace(getSetDifference(poly, set)); + for (const IntegerRelation &disjunct : integerRelations) + result.unionInPlace(getSetDifference(disjunct, set)); return result; } /// T is a subset of S iff T \ S is empty, since if T \ S contains a /// point then this is a point that is contained in T but not S, and /// if T contains a point that is not in S, this also lies in T \ S. -bool PresburgerSet::isSubsetOf(const PresburgerSet &set) const { +bool PresburgerRelation::isSubsetOf(const PresburgerRelation &set) const { return this->subtract(set).isIntegerEmpty(); } /// Two sets are equal iff they are subsets of each other. -bool PresburgerSet::isEqual(const PresburgerSet &set) const { +bool PresburgerRelation::isEqual(const PresburgerRelation &set) const { assert(PresburgerSpace::isEqual(set) && "Spaces should match"); return this->isSubsetOf(set) && set.isSubsetOf(*this); } /// Return true if all the sets in the union are known to be integer empty, /// false otherwise. -bool PresburgerSet::isIntegerEmpty() const { +bool PresburgerRelation::isIntegerEmpty() const { // The set is empty iff all of the disjuncts are empty. - return std::all_of( - integerPolyhedrons.begin(), integerPolyhedrons.end(), - [](const IntegerPolyhedron &poly) { return poly.isIntegerEmpty(); }); + return std::all_of(integerRelations.begin(), integerRelations.end(), + [](const IntegerRelation &disjunct) { + return disjunct.isIntegerEmpty(); + }); } -bool PresburgerSet::findIntegerSample(SmallVectorImpl &sample) { +bool PresburgerRelation::findIntegerSample(SmallVectorImpl &sample) { // A sample exists iff any of the disjuncts contains a sample. - for (const IntegerPolyhedron &poly : integerPolyhedrons) { - if (Optional> opt = poly.findIntegerSample()) { + for (const IntegerRelation &disjunct : integerRelations) { + if (Optional> opt = disjunct.findIntegerSample()) { sample = std::move(*opt); return true; } @@ -366,13 +379,13 @@ return false; } -Optional PresburgerSet::computeVolume() const { +Optional PresburgerRelation::computeVolume() const { assert(getNumSymbolIds() == 0 && "Symbols are not yet supported!"); // The sum of the volumes of the disjuncts is a valid overapproximation of the // volume of their union, even if they overlap. uint64_t result = 0; - for (const IntegerPolyhedron &poly : integerPolyhedrons) { - Optional volume = poly.computeVolume(); + for (const IntegerRelation &disjunct : integerRelations) { + Optional volume = disjunct.computeVolume(); if (!volume) return {}; result += *volume; @@ -380,12 +393,12 @@ return result; } -/// Given an IntegerPolyhedron `p` and one of its inequalities `ineq`, check +/// Given an IntegerRelation `p` and one of its inequalities `ineq`, check /// that all inequalities of `cuttingIneqs` are redundant for the facet of `p` /// where `ineq` holds as an equality. `simp` must be the Simplex constructed /// from `p`. static bool isFacetContained(ArrayRef ineq, Simplex &simp, - IntegerPolyhedron &p, + IntegerRelation &p, ArrayRef> cuttingIneqs) { unsigned snapshot = simp.getSnapshot(); simp.addEquality(ineq); @@ -399,50 +412,50 @@ return true; } -/// Adds `poly` to `polyhedrons` and removes the polyhedrons at position `i` and +/// Adds `disjunct` to `disjuncts` and removes the disjuncts at position `i` and /// `j`. Updates `simplices` to reflect the changes. `i` and `j` cannot be /// equal. -static void -addCoalescedPolyhedron(SmallVectorImpl &polyhedrons, - unsigned i, unsigned j, const IntegerPolyhedron &poly, - SmallVectorImpl &simplices) { - assert(i != j && "The indices must refer to different polyhedra"); +static void addCoalescedDisjunct(SmallVectorImpl &disjuncts, + unsigned i, unsigned j, + const IntegerRelation &disjunct, + SmallVectorImpl &simplices) { + assert(i != j && "The indices must refer to different disjuncts"); - unsigned n = polyhedrons.size(); + unsigned n = disjuncts.size(); if (j == n - 1) { // This case needs special handling since position `n` - 1 is removed from - // the vector, hence the `IntegerPolyhedron` at position `n` - 2 is lost + // the vector, hence the `IntegerRelation` at position `n` - 2 is lost // otherwise. - polyhedrons[i] = polyhedrons[n - 2]; - polyhedrons.pop_back(); - polyhedrons[n - 2] = poly; + disjuncts[i] = disjuncts[n - 2]; + disjuncts.pop_back(); + disjuncts[n - 2] = disjunct; simplices[i] = simplices[n - 2]; simplices.pop_back(); - simplices[n - 2] = Simplex(poly); + simplices[n - 2] = Simplex(disjunct); } else { // Other possible edge cases are correct since for `j` or `i` == `n` - 2, - // the `IntegerPolyhedron` at position `n` - 2 should be lost. The case + // the `IntegerRelation` at position `n` - 2 should be lost. The case // `i` == `n` - 1 makes the first following statement a noop. Hence, in this // case the same thing is done as above, but with `j` rather than `i`. - polyhedrons[i] = polyhedrons[n - 1]; - polyhedrons[j] = polyhedrons[n - 2]; - polyhedrons.pop_back(); - polyhedrons[n - 2] = poly; + disjuncts[i] = disjuncts[n - 1]; + disjuncts[j] = disjuncts[n - 2]; + disjuncts.pop_back(); + disjuncts[n - 2] = disjunct; simplices[i] = simplices[n - 1]; simplices[j] = simplices[n - 2]; simplices.pop_back(); - simplices[n - 2] = Simplex(poly); + simplices[n - 2] = Simplex(disjunct); } } -/// Given two polyhedra `a` and `b` at positions `i` and `j` in `polyhedrons` +/// Given two disjuncts `a` and `b` at positions `i` and `j` in `disjuncts` /// and `redundantIneqsA` being the inequalities of `a` that are redundant for /// `b` (similarly for `cuttingIneqsA`, `redundantIneqsB`, and `cuttingIneqsB`), /// checks whether the facets of all cutting inequalites of `a` are contained in -/// `b`. If so, a new polyhedron consisting of all redundant inequalites of `a` +/// `b`. If so, a new disjunct consisting of all redundant inequalites of `a` /// and `b` and all equalities of both is created. /// /// An example of this case: @@ -454,7 +467,7 @@ /// /// static LogicalResult -coalescePairCutCase(SmallVectorImpl &polyhedrons, +coalescePairCutCase(SmallVectorImpl &disjuncts, SmallVectorImpl &simplices, unsigned i, unsigned j, ArrayRef> redundantIneqsA, ArrayRef> cuttingIneqsA, @@ -463,14 +476,14 @@ /// All inequalities of `b` need to be redundant. We already know that the /// redundant ones are, so only the cutting ones remain to be checked. Simplex &simp = simplices[i]; - IntegerPolyhedron &poly = polyhedrons[i]; - if (llvm::any_of(cuttingIneqsA, - [&simp, &poly, &cuttingIneqsB](ArrayRef curr) { - return !isFacetContained(curr, simp, poly, cuttingIneqsB); - })) + IntegerRelation &disjunct = disjuncts[i]; + if (llvm::any_of(cuttingIneqsA, [&simp, &disjunct, + &cuttingIneqsB](ArrayRef curr) { + return !isFacetContained(curr, simp, disjunct, cuttingIneqsB); + })) return failure(); - IntegerPolyhedron newSet(poly.getNumDimIds(), poly.getNumSymbolIds(), - poly.getNumLocalIds()); + IntegerRelation newSet(disjunct.getNumDomainIds(), disjunct.getNumRangeIds(), + disjunct.getNumSymbolIds(), disjunct.getNumLocalIds()); for (ArrayRef curr : redundantIneqsA) newSet.addInequality(curr); @@ -478,7 +491,7 @@ for (ArrayRef curr : redundantIneqsB) newSet.addInequality(curr); - addCoalescedPolyhedron(polyhedrons, i, j, newSet, simplices); + addCoalescedDisjunct(disjuncts, i, j, newSet, simplices); return success(); } @@ -518,30 +531,29 @@ } /// Replaces the element at position `i` with the last element and erases the -/// last element for both `polyhedrons` and `simplices`. -static void erasePolyhedron(unsigned i, - SmallVectorImpl &polyhedrons, - SmallVectorImpl &simplices) { - assert(simplices.size() == polyhedrons.size() && - "simplices and polyhedrons must be equally as long"); - polyhedrons[i] = polyhedrons.back(); - polyhedrons.pop_back(); +/// last element for both `disjuncts` and `simplices`. +static void eraseDisjunct(unsigned i, + SmallVectorImpl &disjuncts, + SmallVectorImpl &simplices) { + assert(simplices.size() == disjuncts.size() && + "simplices and disjuncts must be equally as long"); + disjuncts[i] = disjuncts.back(); + disjuncts.pop_back(); simplices[i] = simplices.back(); simplices.pop_back(); } -/// Attempts to coalesce the two IntegerPolyhedrons at position `i` and `j` in -/// `polyhedrons` in-place. Returns whether the polyhedrons were successfully +/// Attempts to coalesce the two IntegerRelations at position `i` and `j` in +/// `disjuncts` in-place. Returns whether the disjuncts were successfully /// coalesced. The simplices in `simplices` need to be the ones constructed from -/// `polyhedrons`. At this point, there are no empty polyhedrons in -/// `polyhedrons` left. -static LogicalResult -coalescePair(unsigned i, unsigned j, - SmallVectorImpl &polyhedrons, - SmallVectorImpl &simplices) { - - IntegerPolyhedron &a = polyhedrons[i]; - IntegerPolyhedron &b = polyhedrons[j]; +/// `disjuncts`. At this point, there are no empty disjuncts in +/// `disjuncts` left. +static LogicalResult coalescePair(unsigned i, unsigned j, + SmallVectorImpl &disjuncts, + SmallVectorImpl &simplices) { + + IntegerRelation &a = disjuncts[i]; + IntegerRelation &b = disjuncts[j]; /// Handling of local ids is not yet implemented, so these cases are skipped. /// TODO: implement local id support. if (a.getNumLocalIds() != 0 || b.getNumLocalIds() != 0) @@ -556,7 +568,7 @@ // Organize all inequalities and equalities of `a` according to their type for // `b` into `redundantIneqsA` and `cuttingIneqsA` (and vice versa for all // inequalities of `b` according to their type in `a`). If a separate - // inequality is encountered during typing, the two IntegerPolyhedrons cannot + // inequality is encountered during typing, the two IntegerRelations cannot // be coalesced. for (int k = 0, e = a.getNumInequalities(); k < e; ++k) if (typeInequality(a.getInequality(k), simpB, redundantIneqsA, @@ -587,22 +599,22 @@ // If there are no cutting inequalities of `a`, `b` is contained // within `a` (and vice versa for `b`). if (cuttingIneqsA.empty()) { - erasePolyhedron(j, polyhedrons, simplices); + eraseDisjunct(j, disjuncts, simplices); return success(); } if (cuttingIneqsB.empty()) { - erasePolyhedron(i, polyhedrons, simplices); + eraseDisjunct(i, disjuncts, simplices); return success(); } // Try to apply the cut case - if (coalescePairCutCase(polyhedrons, simplices, i, j, redundantIneqsA, + if (coalescePairCutCase(disjuncts, simplices, i, j, redundantIneqsA, cuttingIneqsA, redundantIneqsB, cuttingIneqsB) .succeeded()) return success(); - if (coalescePairCutCase(polyhedrons, simplices, j, i, redundantIneqsB, + if (coalescePairCutCase(disjuncts, simplices, j, i, redundantIneqsB, cuttingIneqsB, redundantIneqsA, cuttingIneqsA) .succeeded()) return success(); @@ -610,62 +622,99 @@ return failure(); } -PresburgerSet PresburgerSet::coalesce() const { - PresburgerSet newSet = - PresburgerSet::getEmptySet(getNumDimIds(), getNumSymbolIds()); - SmallVector polyhedrons = integerPolyhedrons; +PresburgerRelation PresburgerRelation::coalesce() const { + PresburgerRelation newSet = PresburgerRelation::getEmpty( + getNumDomainIds(), getNumRangeIds(), getNumSymbolIds()); + SmallVector disjuncts = integerRelations; SmallVector simplices; - simplices.reserve(getNumPolys()); - // Note that polyhedrons.size() changes during the loop. - for (unsigned i = 0; i < polyhedrons.size();) { - Simplex simp(polyhedrons[i]); + simplices.reserve(getNumDisjuncts()); + // Note that disjuncts.size() changes during the loop. + for (unsigned i = 0; i < disjuncts.size();) { + Simplex simp(disjuncts[i]); if (simp.isEmpty()) { - polyhedrons[i] = polyhedrons[polyhedrons.size() - 1]; - polyhedrons.pop_back(); + disjuncts[i] = disjuncts[disjuncts.size() - 1]; + disjuncts.pop_back(); continue; } ++i; simplices.push_back(simp); } - // For all tuples of IntegerPolyhedrons, check whether they can be coalesced. - // When coalescing is successful, the contained IntegerPolyhedron is swapped - // with the last element of `polyhedrons` and subsequently erased and + // For all tuples of IntegerRelations, check whether they can be coalesced. + // When coalescing is successful, the contained IntegerRelation is swapped + // with the last element of `disjuncts` and subsequently erased and // similarly for simplices. - for (unsigned i = 0; i < polyhedrons.size();) { + for (unsigned i = 0; i < disjuncts.size();) { // TODO: This does some comparisons two times (index 0 with 1 and index 1 // with 0). bool broken = false; - for (unsigned j = 0, e = polyhedrons.size(); j < e; ++j) { + for (unsigned j = 0, e = disjuncts.size(); j < e; ++j) { if (i == j) continue; - if (coalescePair(i, j, polyhedrons, simplices).succeeded()) { + if (coalescePair(i, j, disjuncts, simplices).succeeded()) { broken = true; break; } } // Only if the inner loop was not broken, i is incremented. This is - // required as otherwise, if a coalescing occurs, the IntegerPolyhedron + // required as otherwise, if a coalescing occurs, the IntegerRelation // now at position i is not compared. if (!broken) ++i; } - for (unsigned i = 0, e = polyhedrons.size(); i < e; ++i) - newSet.unionInPlace(polyhedrons[i]); + for (unsigned i = 0, e = disjuncts.size(); i < e; ++i) + newSet.unionInPlace(disjuncts[i]); return newSet; } -void PresburgerSet::print(raw_ostream &os) const { - os << "Number of Polyhedrons: " << getNumPolys() << "\n"; - for (const IntegerPolyhedron &poly : integerPolyhedrons) { - poly.print(os); +void PresburgerRelation::print(raw_ostream &os) const { + os << "Number of Disjuncts: " << getNumDisjuncts() << "\n"; + for (const IntegerRelation &disjunct : integerRelations) { + disjunct.print(os); os << '\n'; } } -void PresburgerSet::dump() const { print(llvm::errs()); } +void PresburgerRelation::dump() const { print(llvm::errs()); } + +PresburgerSet PresburgerSet::getUniverse(unsigned numDims, + unsigned numSymbols) { + PresburgerSet result(numDims, numSymbols); + result.unionInPlace(IntegerPolyhedron::getUniverse(numDims, numSymbols)); + return result; +} + +PresburgerSet PresburgerSet::getEmpty(unsigned numDims, unsigned numSymbols) { + return PresburgerSet(numDims, numSymbols); +} + +PresburgerSet::PresburgerSet(const IntegerPolyhedron &disjunct) + : PresburgerRelation(disjunct) {} + +PresburgerSet::PresburgerSet(const PresburgerRelation &set) + : PresburgerRelation(set) {} + +PresburgerSet PresburgerSet::unionSet(const PresburgerRelation &set) const { + return PresburgerSet(PresburgerRelation::unionSet(set)); +} + +PresburgerSet PresburgerSet::intersect(const PresburgerRelation &set) const { + return PresburgerSet(PresburgerRelation::intersect(set)); +} + +PresburgerSet PresburgerSet::complement() const { + return PresburgerSet(PresburgerRelation::complement()); +} + +PresburgerSet PresburgerSet::subtract(const PresburgerRelation &set) const { + return PresburgerSet(PresburgerRelation::subtract(set)); +} + +PresburgerSet PresburgerSet::coalesce() const { + return PresburgerSet(PresburgerRelation::coalesce()); +} diff --git a/mlir/lib/Dialect/Affine/Analysis/Utils.cpp b/mlir/lib/Dialect/Affine/Analysis/Utils.cpp --- a/mlir/lib/Dialect/Affine/Analysis/Utils.cpp +++ b/mlir/lib/Dialect/Affine/Analysis/Utils.cpp @@ -12,7 +12,7 @@ //===----------------------------------------------------------------------===// #include "mlir/Dialect/Affine/Analysis/Utils.h" -#include "mlir/Analysis/Presburger/PresburgerSet.h" +#include "mlir/Analysis/Presburger/PresburgerRelation.h" #include "mlir/Dialect/Affine/Analysis/AffineAnalysis.h" #include "mlir/Dialect/Affine/Analysis/LoopAnalysis.h" #include "mlir/Dialect/Affine/IR/AffineOps.h" diff --git a/mlir/unittests/Analysis/Presburger/PWMAFunctionTest.cpp b/mlir/unittests/Analysis/Presburger/PWMAFunctionTest.cpp --- a/mlir/unittests/Analysis/Presburger/PWMAFunctionTest.cpp +++ b/mlir/unittests/Analysis/Presburger/PWMAFunctionTest.cpp @@ -13,7 +13,7 @@ #include "./Utils.h" #include "mlir/Analysis/Presburger/PWMAFunction.h" -#include "mlir/Analysis/Presburger/PresburgerSet.h" +#include "mlir/Analysis/Presburger/PresburgerRelation.h" #include "mlir/IR/MLIRContext.h" #include diff --git a/mlir/unittests/Analysis/Presburger/PresburgerSetTest.cpp b/mlir/unittests/Analysis/Presburger/PresburgerSetTest.cpp --- a/mlir/unittests/Analysis/Presburger/PresburgerSetTest.cpp +++ b/mlir/unittests/Analysis/Presburger/PresburgerSetTest.cpp @@ -14,8 +14,8 @@ // //===----------------------------------------------------------------------===// -#include "mlir/Analysis/Presburger/PresburgerSet.h" #include "./Utils.h" +#include "mlir/Analysis/Presburger/PresburgerRelation.h" #include "mlir/IR/MLIRContext.h" #include @@ -30,7 +30,7 @@ /// number of dimensions as is specified by the numDims argument. static PresburgerSet parsePresburgerSetFromPolyStrings(unsigned numDims, ArrayRef strs) { - PresburgerSet set = PresburgerSet::getEmptySet(numDims); + PresburgerSet set = PresburgerSet::getEmpty(numDims); for (StringRef str : strs) set.unionInPlace(parsePoly(str)); return set; @@ -101,7 +101,7 @@ /// local ids. static PresburgerSet makeSetFromPoly(unsigned numDims, ArrayRef polys) { - PresburgerSet set = PresburgerSet::getEmptySet(numDims); + PresburgerSet set = PresburgerSet::getEmpty(numDims); for (const IntegerPolyhedron &poly : polys) set.unionInPlace(poly); return set; @@ -147,20 +147,20 @@ {{1}, {2}, {8}, {9}, {10}, {20}, {21}}); // empty set union set. - testUnionAtPoints(PresburgerSet::getEmptySet(1), set, + testUnionAtPoints(PresburgerSet::getEmpty(1), set, {{1}, {2}, {8}, {9}, {10}, {20}, {21}}); // empty set union Universe. - testUnionAtPoints(PresburgerSet::getEmptySet(1), - PresburgerSet::getUniverse(1), {{1}, {2}, {0}, {-1}}); + testUnionAtPoints(PresburgerSet::getEmpty(1), PresburgerSet::getUniverse(1), + {{1}, {2}, {0}, {-1}}); // Universe union empty set. - testUnionAtPoints(PresburgerSet::getUniverse(1), - PresburgerSet::getEmptySet(1), {{1}, {2}, {0}, {-1}}); + testUnionAtPoints(PresburgerSet::getUniverse(1), PresburgerSet::getEmpty(1), + {{1}, {2}, {0}, {-1}}); // empty set union empty set. - testUnionAtPoints(PresburgerSet::getEmptySet(1), - PresburgerSet::getEmptySet(1), {{1}, {2}, {0}, {-1}}); + testUnionAtPoints(PresburgerSet::getEmpty(1), PresburgerSet::getEmpty(1), + {{1}, {2}, {0}, {-1}}); } TEST(SetTest, Intersect) { @@ -173,16 +173,16 @@ {{1}, {2}, {8}, {9}, {10}, {20}, {21}}); // empty set intersection set. - testIntersectAtPoints(PresburgerSet::getEmptySet(1), set, + testIntersectAtPoints(PresburgerSet::getEmpty(1), set, {{1}, {2}, {8}, {9}, {10}, {20}, {21}}); // empty set intersection Universe. - testIntersectAtPoints(PresburgerSet::getEmptySet(1), + testIntersectAtPoints(PresburgerSet::getEmpty(1), PresburgerSet::getUniverse(1), {{1}, {2}, {0}, {-1}}); // Universe intersection empty set. testIntersectAtPoints(PresburgerSet::getUniverse(1), - PresburgerSet::getEmptySet(1), {{1}, {2}, {0}, {-1}}); + PresburgerSet::getEmpty(1), {{1}, {2}, {0}, {-1}}); // Universe intersection Universe. testIntersectAtPoints(PresburgerSet::getUniverse(1), @@ -346,7 +346,7 @@ // Complement of empty set. testComplementAtPoints( - PresburgerSet::getEmptySet(1), + PresburgerSet::getEmpty(1), {{-1}, {-2}, {-8}, {1}, {2}, {8}, {9}, {10}, {20}, {21}}); testComplementAtPoints( @@ -369,7 +369,7 @@ TEST(SetTest, isEqual) { // set = [2, 8] U [10, 20]. PresburgerSet universe = PresburgerSet::getUniverse(1); - PresburgerSet emptySet = PresburgerSet::getEmptySet(1); + PresburgerSet emptySet = PresburgerSet::getEmpty(1); PresburgerSet set = parsePresburgerSetFromPolyStrings( 1, {"(x) : (x - 2 >= 0, -x + 8 >= 0)", "(x) : (x - 10 >= 0, -x + 20 >= 0)"}); @@ -460,7 +460,7 @@ void expectCoalesce(size_t expectedNumPoly, const PresburgerSet &set) { PresburgerSet newSet = set.coalesce(); EXPECT_TRUE(set.isEqual(newSet)); - EXPECT_TRUE(expectedNumPoly == newSet.getNumPolys()); + EXPECT_TRUE(expectedNumPoly == newSet.getNumDisjuncts()); } TEST(SetTest, coalesceNoPoly) { diff --git a/mlir/unittests/Analysis/Presburger/Utils.h b/mlir/unittests/Analysis/Presburger/Utils.h --- a/mlir/unittests/Analysis/Presburger/Utils.h +++ b/mlir/unittests/Analysis/Presburger/Utils.h @@ -15,7 +15,7 @@ #include "../../Dialect/Affine/Analysis/AffineStructuresParser.h" #include "mlir/Analysis/Presburger/IntegerRelation.h" -#include "mlir/Analysis/Presburger/PresburgerSet.h" +#include "mlir/Analysis/Presburger/PresburgerRelation.h" #include "mlir/IR/MLIRContext.h" #include diff --git a/mlir/unittests/Dialect/Affine/Analysis/AffineStructuresParserTest.cpp b/mlir/unittests/Dialect/Affine/Analysis/AffineStructuresParserTest.cpp --- a/mlir/unittests/Dialect/Affine/Analysis/AffineStructuresParserTest.cpp +++ b/mlir/unittests/Dialect/Affine/Analysis/AffineStructuresParserTest.cpp @@ -14,7 +14,7 @@ //===----------------------------------------------------------------------===// #include "./AffineStructuresParser.h" -#include "mlir/Analysis/Presburger/PresburgerSet.h" +#include "mlir/Analysis/Presburger/PresburgerRelation.h" #include