MLIR  16.0.0git
PresburgerRelation.h
Go to the documentation of this file.
1 //===- PresburgerRelation.h - MLIR PresburgerRelation Class -----*- C++ -*-===//
2 //
3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4 // See https://llvm.org/LICENSE.txt for license information.
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6 //
7 //===----------------------------------------------------------------------===//
8 //
9 // A class to represent unions of IntegerRelations.
10 //
11 //===----------------------------------------------------------------------===//
12 
13 #ifndef MLIR_ANALYSIS_PRESBURGER_PRESBURGERRELATION_H
14 #define MLIR_ANALYSIS_PRESBURGER_PRESBURGERRELATION_H
15 
17 
18 namespace mlir {
19 namespace presburger {
20 
21 /// The SetCoalescer class contains all functionality concerning the coalesce
22 /// heuristic. It is built from a `PresburgerRelation` and has the `coalesce()`
23 /// function as its main API.
24 class SetCoalescer;
25 
26 /// A PresburgerRelation represents a union of IntegerRelations that live in
27 /// the same PresburgerSpace with support for union, intersection, subtraction,
28 /// and complement operations, as well as sampling.
29 ///
30 /// The IntegerRelations (disjuncts) are stored in a vector, and the set
31 /// represents the union of these relations. An empty list corresponds to
32 /// the empty set.
33 ///
34 /// Note that there are no invariants guaranteed on the list of disjuncts
35 /// other than that they are all in the same PresburgerSpace. For example, the
36 /// relations may overlap with each other.
38 public:
39  /// Return a universe set of the specified type that contains all points.
41 
42  /// Return an empty set of the specified type that contains no points.
44 
45  explicit PresburgerRelation(const IntegerRelation &disjunct);
46 
47  unsigned getNumDomainVars() const { return space.getNumDomainVars(); }
48  unsigned getNumRangeVars() const { return space.getNumRangeVars(); }
49  unsigned getNumSymbolVars() const { return space.getNumSymbolVars(); }
50  unsigned getNumLocalVars() const { return space.getNumLocalVars(); }
51  unsigned getNumVars() const { return space.getNumVars(); }
52 
53  /// Return the number of disjuncts in the union.
54  unsigned getNumDisjuncts() const;
55 
56  const PresburgerSpace &getSpace() const { return space; }
57 
58  /// Set the space to `oSpace`. `oSpace` should not contain any local ids.
59  /// `oSpace` need not have the same number of ids as the current space;
60  /// it could have more or less. If it has less, the extra ids become
61  /// locals of the disjuncts. It can also have more, in which case the
62  /// disjuncts will have fewer locals. If its total number of ids
63  /// exceeds that of some disjunct, an assert failure will occur.
64  void setSpace(const PresburgerSpace &oSpace);
65 
66  /// Return a reference to the list of disjuncts.
68 
69  /// Return the disjunct at the specified index.
70  const IntegerRelation &getDisjunct(unsigned index) const;
71 
72  /// Mutate this set, turning it into the union of this set and the given
73  /// disjunct.
74  void unionInPlace(const IntegerRelation &disjunct);
75 
76  /// Mutate this set, turning it into the union of this set and the given set.
77  void unionInPlace(const PresburgerRelation &set);
78 
79  /// Return the union of this set and the given set.
81 
82  /// Return the intersection of this set and the given set.
84 
85  /// Return true if the set contains the given point, and false otherwise.
86  bool containsPoint(ArrayRef<MPInt> point) const;
87  bool containsPoint(ArrayRef<int64_t> point) const {
88  return containsPoint(getMPIntVec(point));
89  }
90 
91  /// Return the complement of this set. All local variables in the set must
92  /// correspond to floor divisions.
94 
95  /// Return the set difference of this set and the given set, i.e.,
96  /// return `this \ set`. All local variables in `set` must correspond
97  /// to floor divisions, but local variables in `this` need not correspond to
98  /// divisions.
100 
101  /// Return true if this set is a subset of the given set, and false otherwise.
102  bool isSubsetOf(const PresburgerRelation &set) const;
103 
104  /// Return true if this set is equal to the given set, and false otherwise.
105  /// All local variables in both sets must correspond to floor divisions.
106  bool isEqual(const PresburgerRelation &set) const;
107 
108  /// Return true if all the sets in the union are known to be integer empty
109  /// false otherwise.
110  bool isIntegerEmpty() const;
111 
112  /// Find an integer sample from the given set. This should not be called if
113  /// any of the disjuncts in the union are unbounded.
115 
116  /// Compute an overapproximation of the number of integer points in the
117  /// disjunct. Symbol vars are currently not supported. If the computed
118  /// overapproximation is infinite, an empty optional is returned.
119  ///
120  /// This currently just sums up the overapproximations of the volumes of the
121  /// disjuncts, so the approximation might be far from the true volume in the
122  /// case when there is a lot of overlap between disjuncts.
124 
125  /// Simplifies the representation of a PresburgerRelation.
126  ///
127  /// In particular, removes all disjuncts which are subsets of other
128  /// disjuncts in the union.
130 
131  /// Check whether all local ids in all disjuncts have a div representation.
132  bool hasOnlyDivLocals() const;
133 
134  /// Compute an equivalent representation of the same relation, such that all
135  /// local ids in all disjuncts have division representations. This
136  /// representation may involve local ids that correspond to divisions, and may
137  /// also be a union of convex disjuncts.
139 
140  /// Print the set's internal state.
141  void print(raw_ostream &os) const;
142  void dump() const;
143 
144 protected:
145  /// Construct an empty PresburgerRelation with the specified number of
146  /// dimension and symbols.
148  assert(space.getNumLocalVars() == 0 &&
149  "PresburgerRelation cannot have local vars.");
150  }
151 
153 
154  /// The list of disjuncts that this set is the union of.
156 
157  friend class SetCoalescer;
158 };
159 
161 public:
162  /// Return a universe set of the specified type that contains all points.
164 
165  /// Return an empty set of the specified type that contains no points.
167 
168  /// Create a set from a relation.
169  explicit PresburgerSet(const IntegerPolyhedron &disjunct);
170  explicit PresburgerSet(const PresburgerRelation &set);
171 
172  /// These operations are the same as the ones in PresburgeRelation, they just
173  /// forward the arguement and return the result as a set instead of a
174  /// relation.
175  PresburgerSet unionSet(const PresburgerRelation &set) const;
176  PresburgerSet intersect(const PresburgerRelation &set) const;
177  PresburgerSet complement() const;
178  PresburgerSet subtract(const PresburgerRelation &set) const;
179  PresburgerSet coalesce() const;
180 
181 protected:
182  /// Construct an empty PresburgerRelation with the specified number of
183  /// dimension and symbols.
186  assert(space.getNumDomainVars() == 0 &&
187  "Set type cannot have domain vars.");
188  assert(space.getNumLocalVars() == 0 &&
189  "PresburgerRelation cannot have local vars.");
190  }
191 };
192 
193 } // namespace presburger
194 } // namespace mlir
195 
196 #endif // MLIR_ANALYSIS_PRESBURGER_PRESBURGERRELATION_H
An IntegerPolyhedron represents the set of points from a PresburgerSpace that satisfy a list of affin...
An IntegerRelation represents the set of points from a PresburgerSpace that satisfy a list of affine ...
A PresburgerRelation represents a union of IntegerRelations that live in the same PresburgerSpace wit...
bool containsPoint(ArrayRef< MPInt > point) const
Return true if the set contains the given point, and false otherwise.
void setSpace(const PresburgerSpace &oSpace)
Set the space to oSpace.
PresburgerRelation(const PresburgerSpace &space)
Construct an empty PresburgerRelation with the specified number of dimension and symbols.
PresburgerRelation intersect(const PresburgerRelation &set) const
Return the intersection of this set and the given set.
bool hasOnlyDivLocals() const
Check whether all local ids in all disjuncts have a div representation.
Optional< MPInt > computeVolume() const
Compute an overapproximation of the number of integer points in the disjunct.
PresburgerRelation subtract(const PresburgerRelation &set) const
Return the set difference of this set and the given set, i.e., return this \ set.
PresburgerRelation(const IntegerRelation &disjunct)
PresburgerRelation computeReprWithOnlyDivLocals() const
Compute an equivalent representation of the same relation, such that all local ids in all disjuncts h...
bool isSubsetOf(const PresburgerRelation &set) const
Return true if this set is a subset of the given set, and false otherwise.
bool containsPoint(ArrayRef< int64_t > point) const
bool isIntegerEmpty() const
Return true if all the sets in the union are known to be integer empty false otherwise.
void unionInPlace(const IntegerRelation &disjunct)
Mutate this set, turning it into the union of this set and the given disjunct.
bool isEqual(const PresburgerRelation &set) const
Return true if this set is equal to the given set, and false otherwise.
static PresburgerRelation getEmpty(const PresburgerSpace &space)
Return an empty set of the specified type that contains no points.
unsigned getNumDisjuncts() const
Return the number of disjuncts in the union.
PresburgerRelation coalesce() const
Simplifies the representation of a PresburgerRelation.
static PresburgerRelation getUniverse(const PresburgerSpace &space)
Return a universe set of the specified type that contains all points.
const IntegerRelation & getDisjunct(unsigned index) const
Return the disjunct at the specified index.
ArrayRef< IntegerRelation > getAllDisjuncts() const
Return a reference to the list of disjuncts.
SmallVector< IntegerRelation, 2 > disjuncts
The list of disjuncts that this set is the union of.
const PresburgerSpace & getSpace() const
void print(raw_ostream &os) const
Print the set's internal state.
PresburgerRelation unionSet(const PresburgerRelation &set) const
Return the union of this set and the given set.
bool findIntegerSample(SmallVectorImpl< MPInt > &sample)
Find an integer sample from the given set.
PresburgerRelation complement() const
Return the complement of this set.
PresburgerSet intersect(const PresburgerRelation &set) const
PresburgerSet(const IntegerPolyhedron &disjunct)
Create a set from a relation.
PresburgerSet unionSet(const PresburgerRelation &set) const
These operations are the same as the ones in PresburgeRelation, they just forward the arguement and r...
PresburgerSet subtract(const PresburgerRelation &set) const
static PresburgerSet getEmpty(const PresburgerSpace &space)
Return an empty set of the specified type that contains no points.
PresburgerSet(const PresburgerSpace &space)
Construct an empty PresburgerRelation with the specified number of dimension and symbols.
static PresburgerSet getUniverse(const PresburgerSpace &space)
Return a universe set of the specified type that contains all points.
PresburgerSpace is the space of all possible values of a tuple of integer valued variables/variables.
The SetCoalescer class contains all functionality concerning the coalesce heuristic.
SmallVector< MPInt, 8 > getMPIntVec(ArrayRef< int64_t > range)
Check if the pos^th variable can be expressed as a floordiv of an affine function of other variables ...
Definition: Utils.cpp:502
Include the generated interface declarations.