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. /// /// 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. +/// that they are all in the same PresburgerSpace, i.e., they all have the same +/// number of dimensions and symbols. For example, the Polys 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,13 +83,6 @@ /// 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; @@ -109,17 +106,18 @@ /// 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. - SmallVector integerPolyhedrons; + /// The list of polys that this set is the union of. + SmallVector polys; }; } // namespace presburger 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,51 +18,46 @@ PresburgerSet::PresburgerSet(const IntegerPolyhedron &poly) : PresburgerSpace(poly) { - unionPolyInPlace(poly); + unionInPlace(poly); } -unsigned PresburgerSet::getNumPolys() const { - return integerPolyhedrons.size(); -} +unsigned PresburgerSet::getNumPolys() const { return polys.size(); } -ArrayRef PresburgerSet::getAllIntegerPolyhedron() const { - return integerPolyhedrons; -} +ArrayRef PresburgerSet::getAllPolys() const { return polys; } -const IntegerPolyhedron & -PresburgerSet::getIntegerPolyhedron(unsigned index) const { - assert(index < integerPolyhedrons.size() && "index out of bounds!"); - return integerPolyhedrons[index]; +const IntegerPolyhedron &PresburgerSet::getPoly(unsigned index) const { + assert(index < polys.size() && "index out of bounds!"); + return polys[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); + polys.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) { +void PresburgerSet::unionInPlace(const PresburgerSet &set) { assert(PresburgerSpace::isEqual(set) && "Spaces should match"); - for (const IntegerPolyhedron &poly : set.integerPolyhedrons) - unionPolyInPlace(poly); + for (const IntegerPolyhedron &poly : set.polys) + 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; } /// 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 llvm::any_of(polys, [&](const IntegerPolyhedron &poly) { return (poly.containsPoint(point)); }); } @@ -70,7 +65,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; } @@ -90,13 +85,13 @@ assert(PresburgerSpace::isEqual(set) && "Spaces should match"); PresburgerSet result(getNumDimIds(), getNumSymbolIds()); - for (const IntegerPolyhedron &csA : integerPolyhedrons) { - for (const IntegerPolyhedron &csB : set.integerPolyhedrons) { + for (const IntegerPolyhedron &csA : polys) { + for (const IntegerPolyhedron &csB : set.polys) { IntegerPolyhedron csACopy = csA, csBCopy = csB; csACopy.mergeLocalIds(csBCopy); csACopy.append(csBCopy); if (!csACopy.isEmpty()) - result.unionPolyInPlace(csACopy); + result.unionInPlace(csACopy); } } return result; @@ -163,10 +158,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 @@ -302,14 +297,15 @@ /// 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) { +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; @@ -327,8 +323,8 @@ assert(PresburgerSpace::isEqual(set) && "Spaces should match"); 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)); + for (const IntegerPolyhedron &poly : polys) + result.unionInPlace(getSetDifference(poly, set)); return result; } @@ -350,13 +346,13 @@ bool PresburgerSet::isIntegerEmpty() const { // The set is empty iff all of the disjuncts are empty. return std::all_of( - integerPolyhedrons.begin(), integerPolyhedrons.end(), + polys.begin(), polys.end(), [](const IntegerPolyhedron &poly) { return poly.isIntegerEmpty(); }); } bool PresburgerSet::findIntegerSample(SmallVectorImpl &sample) { // A sample exists iff any of the disjuncts contains a sample. - for (const IntegerPolyhedron &poly : integerPolyhedrons) { + for (const IntegerPolyhedron &poly : polys) { if (Optional> opt = poly.findIntegerSample()) { sample = std::move(*opt); return true; @@ -370,7 +366,7 @@ // 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) { + for (const IntegerPolyhedron &poly : polys) { Optional volume = poly.computeVolume(); if (!volume) return {}; @@ -594,7 +590,7 @@ PresburgerSet PresburgerSet::coalesce() const { PresburgerSet newSet = PresburgerSet::getEmptySet(getNumDimIds(), getNumSymbolIds()); - SmallVector polyhedrons = integerPolyhedrons; + SmallVector polyhedrons = polys; SmallVector simplices; simplices.reserve(getNumPolys()); @@ -636,14 +632,14 @@ } 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"; - for (const IntegerPolyhedron &poly : integerPolyhedrons) { + os << getNumPolys() << " polys:\n"; + for (const IntegerPolyhedron &poly : polys) { 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; }