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, or 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. 71 PresburgerSet complement() const; 72 73 /// Return the set difference of this set and the given set, i.e., 74 /// return `this \ set`. 75 PresburgerSet subtract(const PresburgerSet &set) const; 76 77 /// Return a universe set of the specified type that contains all points. 78 static PresburgerSet getUniverse(unsigned nDim = 0, unsigned nSym = 0); 79 /// Return an empty set of the specified type that contains no points. 80 static PresburgerSet getEmptySet(unsigned nDim = 0, unsigned nSym = 0); 81 82 /// Return true if all the sets in the union are known to be integer empty 83 /// false otherwise. 84 bool isIntegerEmpty() const; 85 86 /// Find an integer sample from the given set. This should not be called if 87 /// any of the FACs in the union are unbounded. 88 bool findIntegerSample(SmallVectorImpl<int64_t> &sample); 89 90 private: 91 /// Construct an empty PresburgerSet. 92 PresburgerSet(unsigned nDim = 0, unsigned nSym = 0) nDim(nDim)93 : nDim(nDim), nSym(nSym) {} 94 95 /// Return the set difference fac \ set. 96 static PresburgerSet getSetDifference(FlatAffineConstraints fac, 97 const PresburgerSet &set); 98 99 /// Number of identifiers corresponding to real dimensions. 100 unsigned nDim; 101 102 /// Number of symbolic dimensions, unknown but constant for analysis, as in 103 /// FlatAffineConstraints. 104 unsigned nSym; 105 106 /// The list of flatAffineConstraints that this set is the union of. 107 SmallVector<FlatAffineConstraints, 2> flatAffineConstraints; 108 }; 109 110 } // namespace mlir 111 112 #endif // MLIR_ANALYSIS_PRESBURGERSET_H 113