MLIR  16.0.0git
PWMAFunction.h
Go to the documentation of this file.
1 //===- PWMAFunction.h - MLIR PWMAFunction 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 // Support for piece-wise multi-affine functions. These are functions that are
10 // defined on a domain that is a union of IntegerPolyhedrons, and on each domain
11 // the value of the function is a tuple of integers, with each value in the
12 // tuple being an affine expression in the vars of the IntegerPolyhedron.
13 //
14 //===----------------------------------------------------------------------===//
15 
16 #ifndef MLIR_ANALYSIS_PRESBURGER_PWMAFUNCTION_H
17 #define MLIR_ANALYSIS_PRESBURGER_PWMAFUNCTION_H
18 
21 
22 namespace mlir {
23 namespace presburger {
24 
25 /// This class represents a multi-affine function with the domain as Z^d, where
26 /// `d` is the number of domain variables of the function. For example:
27 ///
28 /// (x, y) -> (x + 2, 2*x - 3y + 5, 2*x + y).
29 ///
30 /// The output expressions are represented as a matrix with one row for every
31 /// output, one column for each var including division variables, and an extra
32 /// column at the end for the constant term.
33 ///
34 /// Checking equality of two such functions is supported, as well as finding the
35 /// value of the function at a specified point.
37 public:
38  MultiAffineFunction(const PresburgerSpace &space, const Matrix &output)
39  : space(space), output(output),
40  divs(space.getNumVars() - space.getNumRangeVars()) {
41  assertIsConsistent();
42  }
43 
44  MultiAffineFunction(const PresburgerSpace &space, const Matrix &output,
45  const DivisionRepr &divs)
46  : space(space), output(output), divs(divs) {
47  assertIsConsistent();
48  }
49 
50  unsigned getNumDomainVars() const { return space.getNumDomainVars(); }
51  unsigned getNumSymbolVars() const { return space.getNumSymbolVars(); }
52  unsigned getNumOutputs() const { return space.getNumRangeVars(); }
53  unsigned getNumDivs() const { return space.getNumLocalVars(); }
54 
55  /// Get the space of this function.
56  const PresburgerSpace &getSpace() const { return space; }
57  /// Get the domain/output space of the function. The returned space is a set
58  /// space.
59  PresburgerSpace getDomainSpace() const { return space.getDomainSpace(); }
60  PresburgerSpace getOutputSpace() const { return space.getRangeSpace(); }
61 
62  /// Get a matrix with each row representing row^th output expression.
63  const Matrix &getOutputMatrix() const { return output; }
64  /// Get the `i^th` output expression.
65  ArrayRef<MPInt> getOutputExpr(unsigned i) const { return output.getRow(i); }
66 
67  // Remove the specified range of outputs.
68  void removeOutputs(unsigned start, unsigned end);
69 
70  /// Given a MAF `other`, merges division variables such that both functions
71  /// have the union of the division vars that exist in the functions.
72  void mergeDivs(MultiAffineFunction &other);
73 
74  //// Return the output of the function at the given point.
77  return valueAt(getMPIntVec(point));
78  }
79 
80  /// Return whether the `this` and `other` are equal when the domain is
81  /// restricted to `domain`. This is the case if they lie in the same space,
82  /// and their outputs are equal for every point in `domain`.
83  bool isEqual(const MultiAffineFunction &other) const;
84  bool isEqual(const MultiAffineFunction &other,
85  const IntegerPolyhedron &domain) const;
86  bool isEqual(const MultiAffineFunction &other,
87  const PresburgerSet &domain) const;
88 
89  void subtract(const MultiAffineFunction &other);
90 
91  /// Get this function as a relation.
93 
94  void print(raw_ostream &os) const;
95  void dump() const;
96 
97 private:
98  /// Assert that the MAF is consistent.
99  void assertIsConsistent() const;
100 
101  /// The space of this function. The domain variables are considered as the
102  /// input variables of the function. The range variables are considered as
103  /// the outputs. The symbols parametrize the function and locals are used to
104  /// represent divisions. Each local variable has a corressponding division
105  /// representation stored in `divs`.
106  PresburgerSpace space;
107 
108  /// The function's output is a tuple of integers, with the ith element of the
109  /// tuple defined by the affine expression given by the ith row of this output
110  /// matrix.
111  Matrix output;
112 
113  /// Storage for division representation for each local variable in space.
114  DivisionRepr divs;
115 };
116 
117 /// This class represents a piece-wise MultiAffineFunction. This can be thought
118 /// of as a list of MultiAffineFunction with disjoint domains, with each having
119 /// their own affine expressions for their output tuples. For example, we could
120 /// have a function with two input variables (x, y), defined as
121 ///
122 /// f(x, y) = (2*x + y, y - 4) if x >= 0, y >= 0
123 /// = (-2*x + y, y + 4) if x < 0, y < 0
124 /// = (4, 1) if x < 0, y >= 0
125 ///
126 /// Note that the domains all have to be *disjoint*. Otherwise, the behaviour of
127 /// this class is undefined. The domains need not cover all possible points;
128 /// this represents a partial function and so could be undefined at some points.
129 ///
130 /// As in PresburgerSets, the input vars are partitioned into dimension vars and
131 /// symbolic vars.
132 ///
133 /// Support is provided to compare equality of two such functions as well as
134 /// finding the value of the function at a point.
136 public:
137  struct Piece {
140 
141  bool isConsistent() const {
143  }
144  };
145 
146  PWMAFunction(const PresburgerSpace &space) : space(space) {
147  assert(space.getNumLocalVars() == 0 &&
148  "PWMAFunction cannot have local vars.");
149  }
150 
151  // Get the space of this function.
152  const PresburgerSpace &getSpace() const { return space; }
153 
154  // Add a piece ([domain, output] pair) to this function.
155  void addPiece(const Piece &piece);
156 
157  unsigned getNumPieces() const { return pieces.size(); }
158  unsigned getNumVarKind(VarKind kind) const {
159  return space.getNumVarKind(kind);
160  }
161  unsigned getNumDomainVars() const { return space.getNumDomainVars(); }
162  unsigned getNumOutputs() const { return space.getNumRangeVars(); }
163  unsigned getNumSymbolVars() const { return space.getNumSymbolVars(); }
164 
165  /// Remove the specified range of outputs.
166  void removeOutputs(unsigned start, unsigned end);
167 
168  /// Get the domain/output space of the function. The returned space is a set
169  /// space.
170  PresburgerSpace getDomainSpace() const { return space.getDomainSpace(); }
171  PresburgerSpace getOutputSpace() const { return space.getDomainSpace(); }
172 
173  /// Return the domain of this piece-wise MultiAffineFunction. This is the
174  /// union of the domains of all the pieces.
175  PresburgerSet getDomain() const;
176 
177  /// Return the output of the function at the given point.
180  return valueAt(getMPIntVec(point));
181  }
182 
183  /// Return whether `this` and `other` are equal as PWMAFunctions, i.e. whether
184  /// they have the same dimensions, the same domain and they take the same
185  /// value at every point in the domain.
186  bool isEqual(const PWMAFunction &other) const;
187 
188  /// Return a function defined on the union of the domains of this and func,
189  /// such that when only one of the functions is defined, it outputs the same
190  /// as that function, and if both are defined, it outputs the lexmax/lexmin of
191  /// the two outputs. On points where neither function is defined, the returned
192  /// function is not defined either.
193  ///
194  /// Currently this does not support PWMAFunctions which have pieces containing
195  /// divisions.
196  /// TODO: Support division in pieces.
199 
200  void print(raw_ostream &os) const;
201  void dump() const;
202 
203 private:
204  /// Return a function defined on the union of the domains of `this` and
205  /// `func`, such that when only one of the functions is defined, it outputs
206  /// the same as that function, and if neither is defined, the returned
207  /// function is not defined either.
208  ///
209  /// The provided `tiebreak` function determines which of the two functions'
210  /// output should be used on inputs where both the functions are defined. More
211  /// precisely, given two `MultiAffineFunction`s `mafA` and `mafB`, `tiebreak`
212  /// returns the subset of the intersection of the two functions' domains where
213  /// the output of `mafA` should be used.
214  ///
215  /// The PresburgerSet returned by `tiebreak` should be disjoint.
216  /// TODO: Remove this constraint of returning disjoint set.
217  PWMAFunction unionFunction(
218  const PWMAFunction &func,
219  llvm::function_ref<PresburgerSet(Piece mafA, Piece mafB)> tiebreak) const;
220 
221  /// The space of this function. The domain variables are considered as the
222  /// input variables of the function. The range variables are considered as
223  /// the outputs. The symbols paramterize the function.
224  PresburgerSpace space;
225 
226  // The pieces of the PWMAFunction.
227  SmallVector<Piece, 4> pieces;
228 };
229 
230 } // namespace presburger
231 } // namespace mlir
232 
233 #endif // MLIR_ANALYSIS_PRESBURGER_PWMAFUNCTION_H
Class storing division representation of local variables of a constraint system.
Definition: Utils.h:117
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 ...
This is a class to represent a resizable matrix.
Definition: Matrix.h:35
MutableArrayRef< MPInt > getRow(unsigned row)
Get a [Mutable]ArrayRef corresponding to the specified row.
Definition: Matrix.cpp:87
This class represents a multi-affine function with the domain as Z^d, where d is the number of domain...
Definition: PWMAFunction.h:36
MultiAffineFunction(const PresburgerSpace &space, const Matrix &output, const DivisionRepr &divs)
Definition: PWMAFunction.h:44
const Matrix & getOutputMatrix() const
Get a matrix with each row representing row^th output expression.
Definition: PWMAFunction.h:63
void subtract(const MultiAffineFunction &other)
void removeOutputs(unsigned start, unsigned end)
void print(raw_ostream &os) const
PresburgerSpace getOutputSpace() const
Definition: PWMAFunction.h:60
ArrayRef< MPInt > getOutputExpr(unsigned i) const
Get the i^th output expression.
Definition: PWMAFunction.h:65
const PresburgerSpace & getSpace() const
Get the space of this function.
Definition: PWMAFunction.h:56
PresburgerSpace getDomainSpace() const
Get the domain/output space of the function.
Definition: PWMAFunction.h:59
SmallVector< MPInt, 8 > valueAt(ArrayRef< MPInt > point) const
MultiAffineFunction(const PresburgerSpace &space, const Matrix &output)
Definition: PWMAFunction.h:38
SmallVector< MPInt, 8 > valueAt(ArrayRef< int64_t > point) const
Definition: PWMAFunction.h:76
void mergeDivs(MultiAffineFunction &other)
Given a MAF other, merges division variables such that both functions have the union of the division ...
IntegerRelation getAsRelation() const
Get this function as a relation.
bool isEqual(const MultiAffineFunction &other) const
Return whether the this and other are equal when the domain is restricted to domain.
This class represents a piece-wise MultiAffineFunction.
Definition: PWMAFunction.h:135
const PresburgerSpace & getSpace() const
Definition: PWMAFunction.h:152
void addPiece(const Piece &piece)
unsigned getNumDomainVars() const
Definition: PWMAFunction.h:161
void print(raw_ostream &os) const
PWMAFunction unionLexMax(const PWMAFunction &func)
void removeOutputs(unsigned start, unsigned end)
Remove the specified range of outputs.
unsigned getNumOutputs() const
Definition: PWMAFunction.h:162
unsigned getNumVarKind(VarKind kind) const
Definition: PWMAFunction.h:158
PWMAFunction unionLexMin(const PWMAFunction &func)
Return a function defined on the union of the domains of this and func, such that when only one of th...
PWMAFunction(const PresburgerSpace &space)
Definition: PWMAFunction.h:146
Optional< SmallVector< MPInt, 8 > > valueAt(ArrayRef< int64_t > point) const
Definition: PWMAFunction.h:179
PresburgerSet getDomain() const
Return the domain of this piece-wise MultiAffineFunction.
Optional< SmallVector< MPInt, 8 > > valueAt(ArrayRef< MPInt > point) const
Return the output of the function at the given point.
PresburgerSpace getDomainSpace() const
Get the domain/output space of the function.
Definition: PWMAFunction.h:170
PresburgerSpace getOutputSpace() const
Definition: PWMAFunction.h:171
unsigned getNumSymbolVars() const
Definition: PWMAFunction.h:163
bool isEqual(const PWMAFunction &other) const
Return whether this and other are equal as PWMAFunctions, i.e.
const PresburgerSpace & getSpace() const
PresburgerSpace is the space of all possible values of a tuple of integer valued variables/variables.
PresburgerSpace getRangeSpace() const
unsigned getNumVarKind(VarKind kind) const
Get the number of vars of the specified kind.
PresburgerSpace getDomainSpace() const
bool isCompatible(const PresburgerSpace &other) const
Returns true if both the spaces are compatible i.e.
VarKind
Kind of variable.
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.