1 //===- Set.h - MLIR PresburgerSet 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 FlatAffineConstraints. 10 // 11 //===----------------------------------------------------------------------===// 12 13 #ifndef MLIR_ANALYSIS_PRESBURGERSET_H 14 #define MLIR_ANALYSIS_PRESBURGERSET_H 15 16 #include "mlir/Analysis/AffineStructures.h" 17 18 namespace mlir { 19 20 /// This class can represent a union of FlatAffineConstraints, with support for 21 /// union, intersection, subtraction and complement operations, as well as 22 /// sampling. 23 /// 24 /// The FlatAffineConstraints (FACs) are stored in a vector, and the set 25 /// represents the union of these FACs. An empty list corresponds to the empty 26 /// set. 27 /// 28 /// Note that there are no invariants guaranteed on the list of FACs other than 29 /// that they are all in the same space, i.e., they all have the same number of 30 /// dimensions and symbols. For example, the FACs may overlap each other. 31 class PresburgerSet { 32 public: 33 explicit PresburgerSet(const FlatAffineConstraints &fac); 34 35 /// Return the number of FACs in the union. 36 unsigned getNumFACs() const; 37 38 /// Return the number of real dimensions. 39 unsigned getNumDims() const; 40 41 /// Return the number of symbolic dimensions. 42 unsigned getNumSyms() const; 43 44 /// Return a reference to the list of FlatAffineConstraints. 45 ArrayRef<FlatAffineConstraints> getAllFlatAffineConstraints() const; 46 47 /// Return the FlatAffineConstraints at the specified index. 48 const FlatAffineConstraints &getFlatAffineConstraints(unsigned index) const; 49 50 /// Mutate this set, turning it into the union of this set and the given 51 /// FlatAffineConstraints. 52 void unionFACInPlace(const FlatAffineConstraints &fac); 53 54 /// Mutate this set, turning it into the union of this set and the given set. 55 void unionSetInPlace(const PresburgerSet &set); 56 57 /// Return the union of this set and the given set. 58 PresburgerSet unionSet(const PresburgerSet &set) const; 59 60 /// Return the intersection of this set and the given set. 61 PresburgerSet intersect(const PresburgerSet &set) const; 62 63 /// Return true if the set contains the given point, and false otherwise. 64 bool containsPoint(ArrayRef<int64_t> point) const; 65 66 /// Print the set's internal state. 67 void print(raw_ostream &os) const; 68 void dump() const; 69 70 /// Return the complement of this set. All local variables in the set must 71 /// correspond to floor divisions. 72 PresburgerSet complement() const; 73 74 /// Return the set difference of this set and the given set, i.e., 75 /// return `this \ set`. All local variables in `set` must correspond 76 /// to floor divisions, but local variables in `this` need not correspond to 77 /// divisions. 78 PresburgerSet subtract(const PresburgerSet &set) const; 79 80 /// Return true if this set is equal to the given set, and false otherwise. 81 /// All local variables in both sets must correspond to floor divisions. 82 bool isEqual(const PresburgerSet &set) const; 83 84 /// Return a universe set of the specified type that contains all points. 85 static PresburgerSet getUniverse(unsigned nDim = 0, unsigned nSym = 0); 86 /// Return an empty set of the specified type that contains no points. 87 static PresburgerSet getEmptySet(unsigned nDim = 0, unsigned nSym = 0); 88 89 /// Return true if all the sets in the union are known to be integer empty 90 /// false otherwise. 91 bool isIntegerEmpty() const; 92 93 /// Find an integer sample from the given set. This should not be called if 94 /// any of the FACs in the union are unbounded. 95 bool findIntegerSample(SmallVectorImpl<int64_t> &sample); 96 97 private: 98 /// Construct an empty PresburgerSet. 99 PresburgerSet(unsigned nDim = 0, unsigned nSym = 0) nDim(nDim)100 : nDim(nDim), nSym(nSym) {} 101 102 /// Return the set difference fac \ set. 103 static PresburgerSet getSetDifference(FlatAffineConstraints fac, 104 const PresburgerSet &set); 105 106 /// Number of identifiers corresponding to real dimensions. 107 unsigned nDim; 108 109 /// Number of symbolic dimensions, unknown but constant for analysis, as in 110 /// FlatAffineConstraints. 111 unsigned nSym; 112 113 /// The list of flatAffineConstraints that this set is the union of. 114 SmallVector<FlatAffineConstraints, 2> flatAffineConstraints; 115 }; 116 117 } // namespace mlir 118 119 #endif // MLIR_ANALYSIS_PRESBURGERSET_H 120