diff --git a/mlir/include/mlir/Analysis/Presburger/PresburgerSet.h b/mlir/include/mlir/Analysis/Presburger/PresburgerSet.h --- a/mlir/include/mlir/Analysis/Presburger/PresburgerSet.h +++ b/mlir/include/mlir/Analysis/Presburger/PresburgerSet.h @@ -18,36 +18,44 @@ namespace mlir { namespace presburger { -/// This class can represent a union of IntegerPolyhedrons, with support for -/// union, intersection, subtraction and complement operations, as well as -/// sampling. +/// 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 (Polys) are stored in a vector, and the set -/// represents the union of these Polys. An empty list corresponds to the empty -/// set. +/// 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 Poly other than -/// that they are all in the same space, i.e., they all have the same number of -/// dimensions and symbols. For example, the Polys may overlap each other. +/// 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 getAllIntegerPolyhedron() const; + ArrayRef getAllPolys() const; /// Return the IntegerPolyhedron at the specified index. - const IntegerPolyhedron &getIntegerPolyhedron(unsigned index) const; + const IntegerPolyhedron &getPoly(unsigned index) const; /// Mutate this set, turning it into the union of this set and the given /// IntegerPolyhedron. - void unionPolyInPlace(const IntegerPolyhedron &poly); + void unionInPlace(const IntegerPolyhedron &poly); /// Mutate this set, turning it into the union of this set and the given set. - void unionSetInPlace(const PresburgerSet &set); + void unionInPlace(const PresburgerSet &set); /// Return the union of this set and the given set. PresburgerSet unionSet(const PresburgerSet &set) const; @@ -58,10 +66,6 @@ /// Return true if the set contains the given point, and false otherwise. bool containsPoint(ArrayRef point) const; - /// Print the set's internal state. - void print(raw_ostream &os) const; - void dump() const; - /// Return the complement of this set. All local variables in the set must /// correspond to floor divisions. PresburgerSet complement() const; @@ -79,19 +83,12 @@ /// All local variables in both sets must correspond to floor divisions. bool isEqual(const PresburgerSet &set) const; - /// 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); - /// 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 Polys in the union are unbounded. + /// any of the polyhedrons in the union are unbounded. bool findIntegerSample(SmallVectorImpl &sample); /// Compute an overapproximation of the number of integer points in the @@ -105,20 +102,21 @@ /// Simplifies the representation of a PresburgerSet. /// - /// In particular, removes all Polys which are subsets of other Polys in the - /// union. + /// 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. + /// Construct an empty PresburgerSet with the specified number of dimension + /// and symbols. PresburgerSet(unsigned numDims = 0, unsigned numSymbols = 0) : PresburgerSpace(numDims, numSymbols) {} - /// Return the set difference poly \ set. - static PresburgerSet getSetDifference(IntegerPolyhedron poly, - const PresburgerSet &set); - - /// The list of integerPolyhedrons that this set is the union of. + /// The list of polyhedrons that this set is the union of. SmallVector integerPolyhedrons; }; 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 @@ -30,7 +30,7 @@ PresburgerSet domain = PresburgerSet::getEmptySet(getNumDimIds(), getNumSymbolIds()); for (const MultiAffineFunction &piece : pieces) - domain.unionPolyInPlace(piece.getDomain()); + domain.unionInPlace(piece.getDomain()); return domain; } diff --git a/mlir/lib/Analysis/Presburger/PresburgerSet.cpp b/mlir/lib/Analysis/Presburger/PresburgerSet.cpp --- a/mlir/lib/Analysis/Presburger/PresburgerSet.cpp +++ b/mlir/lib/Analysis/Presburger/PresburgerSet.cpp @@ -18,45 +18,44 @@ PresburgerSet::PresburgerSet(const IntegerPolyhedron &poly) : PresburgerSpace(poly) { - unionPolyInPlace(poly); + unionInPlace(poly); } unsigned PresburgerSet::getNumPolys() const { return integerPolyhedrons.size(); } -ArrayRef PresburgerSet::getAllIntegerPolyhedron() const { +ArrayRef PresburgerSet::getAllPolys() const { return integerPolyhedrons; } -const IntegerPolyhedron & -PresburgerSet::getIntegerPolyhedron(unsigned index) const { +const IntegerPolyhedron &PresburgerSet::getPoly(unsigned index) const { assert(index < integerPolyhedrons.size() && "index out of bounds!"); return integerPolyhedrons[index]; } /// Mutate this set, turning it into the union of this set and the given /// IntegerPolyhedron. -void PresburgerSet::unionPolyInPlace(const IntegerPolyhedron &poly) { +void PresburgerSet::unionInPlace(const IntegerPolyhedron &poly) { assert(PresburgerSpace::isEqual(poly) && "Spaces should match"); integerPolyhedrons.push_back(poly); } /// Mutate this set, turning it into the union of this set and the given set. /// -/// This is accomplished by simply adding all the Poly of the given set to this -/// set. -void PresburgerSet::unionSetInPlace(const PresburgerSet &set) { +/// This is accomplished by simply adding all the polyhedrons of the given set +/// to this set. +void PresburgerSet::unionInPlace(const PresburgerSet &set) { assert(PresburgerSpace::isEqual(set) && "Spaces should match"); for (const IntegerPolyhedron &poly : set.integerPolyhedrons) - unionPolyInPlace(poly); + unionInPlace(poly); } /// Return the union of this set and the given set. PresburgerSet PresburgerSet::unionSet(const PresburgerSet &set) const { assert(PresburgerSpace::isEqual(set) && "Spaces should match"); PresburgerSet result = *this; - result.unionSetInPlace(set); + result.unionInPlace(set); return result; } @@ -70,7 +69,7 @@ PresburgerSet PresburgerSet::getUniverse(unsigned numDims, unsigned numSymbols) { PresburgerSet result(numDims, numSymbols); - result.unionPolyInPlace(IntegerPolyhedron::getUniverse(numDims, numSymbols)); + result.unionInPlace(IntegerPolyhedron::getUniverse(numDims, numSymbols)); return result; } @@ -96,7 +95,7 @@ csACopy.mergeLocalIds(csBCopy); csACopy.append(csBCopy); if (!csACopy.isEmpty()) - result.unionPolyInPlace(csACopy); + result.unionInPlace(csACopy); } } return result; @@ -153,9 +152,10 @@ /// division inequality is added, as these parts will become empty anyway. /// /// 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 Poly 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. +/// 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 +/// 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. @@ -163,10 +163,10 @@ const PresburgerSet &s, unsigned i, PresburgerSet &result) { if (i == s.getNumPolys()) { - result.unionPolyInPlace(b); + result.unionInPlace(b); return; } - IntegerPolyhedron sI = s.getIntegerPolyhedron(i); + IntegerPolyhedron sI = s.getPoly(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 @@ -299,17 +299,18 @@ /// Return the set difference poly \ set. /// -/// The Poly 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. -PresburgerSet PresburgerSet::getSetDifference(IntegerPolyhedron poly, - const PresburgerSet &set) { +/// The polyhedron 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(poly.getNumDimIds(), poly.getNumSymbolIds()); + PresburgerSet result = + PresburgerSet::getEmptySet(poly.getNumDimIds(), poly.getNumSymbolIds()); Simplex simplex(poly); subtractRecursively(poly, simplex, set, 0, result); return result; @@ -328,7 +329,7 @@ PresburgerSet result(getNumDimIds(), 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.unionSetInPlace(getSetDifference(poly, set)); + result.unionInPlace(getSetDifference(poly, set)); return result; } @@ -636,13 +637,13 @@ } for (unsigned i = 0, e = polyhedrons.size(); i < e; ++i) - newSet.unionPolyInPlace(polyhedrons[i]); + newSet.unionInPlace(polyhedrons[i]); return newSet; } void PresburgerSet::print(raw_ostream &os) const { - os << getNumPolys() << " IntegerPolyhedron:\n"; + os << "Number of Polyhedrons: " << getNumPolys() << "\n"; for (const IntegerPolyhedron &poly : integerPolyhedrons) { poly.print(os); os << '\n'; 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 @@ -32,7 +32,7 @@ parsePresburgerSetFromPolyStrings(unsigned numDims, ArrayRef strs) { PresburgerSet set = PresburgerSet::getEmptySet(numDims); for (StringRef str : strs) - set.unionPolyInPlace(parsePoly(str)); + set.unionInPlace(parsePoly(str)); return set; } @@ -103,7 +103,7 @@ ArrayRef polys) { PresburgerSet set = PresburgerSet::getEmptySet(numDims); for (const IntegerPolyhedron &poly : polys) - set.unionPolyInPlace(poly); + set.unionInPlace(poly); return set; }