MLIR  18.0.0git
ValueBoundsOpInterface.h
Go to the documentation of this file.
1 //===- ValueBoundsOpInterface.h - Value Bounds ------------------*- 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 #ifndef MLIR_INTERFACES_VALUEBOUNDSOPINTERFACE_H_
10 #define MLIR_INTERFACES_VALUEBOUNDSOPINTERFACE_H_
11 
13 #include "mlir/IR/Builders.h"
14 #include "mlir/IR/OpDefinition.h"
15 #include "mlir/IR/Value.h"
17 #include "llvm/ADT/SetVector.h"
18 
19 #include <queue>
20 
21 namespace mlir {
22 class OffsetSizeAndStrideOpInterface;
23 
24 /// A hyperrectangular slice, represented as a list of offsets, sizes and
25 /// strides.
27 public:
30  ArrayRef<OpFoldResult> strides);
31 
32  /// Create a hyperrectangular slice with unit strides.
35 
36  /// Infer a hyperrectangular slice from `OffsetSizeAndStrideOpInterface`.
37  HyperrectangularSlice(OffsetSizeAndStrideOpInterface op);
38 
39  ArrayRef<OpFoldResult> getMixedOffsets() const { return mixedOffsets; }
40  ArrayRef<OpFoldResult> getMixedSizes() const { return mixedSizes; }
41  ArrayRef<OpFoldResult> getMixedStrides() const { return mixedStrides; }
42 
43 private:
44  SmallVector<OpFoldResult> mixedOffsets;
45  SmallVector<OpFoldResult> mixedSizes;
46  SmallVector<OpFoldResult> mixedStrides;
47 };
48 
50 
51 /// A helper class to be used with `ValueBoundsOpInterface`. This class stores a
52 /// constraint system and mapping of constrained variables to index-typed
53 /// values or dimension sizes of shaped values.
54 ///
55 /// Interface implementations of `ValueBoundsOpInterface` use `addBounds` to
56 /// insert constraints about their results and/or region block arguments into
57 /// the constraint set in the form of an AffineExpr. When a bound should be
58 /// expressed in terms of another value/dimension, `getExpr` can be used to
59 /// retrieve an AffineExpr that represents the specified value/dimension.
60 ///
61 /// When a value/dimension is retrieved for the first time through `getExpr`,
62 /// it is added to an internal worklist. See `computeBound` for more details.
63 ///
64 /// Note: Any modification of existing IR invalides the data stored in this
65 /// class. Adding new operations is allowed.
67 protected:
68  /// Helper class that builds a bound for a shaped value dimension or
69  /// index-typed value.
70  class BoundBuilder {
71  public:
72  /// Specify a dimension, assuming that the underlying value is a shaped
73  /// value.
74  BoundBuilder &operator[](int64_t dim);
75 
76  // These overloaded operators add lower/upper/equality bounds.
77  void operator<(AffineExpr expr);
78  void operator<=(AffineExpr expr);
79  void operator>(AffineExpr expr);
80  void operator>=(AffineExpr expr);
81  void operator==(AffineExpr expr);
82  void operator<(OpFoldResult ofr);
83  void operator<=(OpFoldResult ofr);
84  void operator>(OpFoldResult ofr);
85  void operator>=(OpFoldResult ofr);
86  void operator==(OpFoldResult ofr);
87  void operator<(int64_t i);
88  void operator<=(int64_t i);
89  void operator>(int64_t i);
90  void operator>=(int64_t i);
91  void operator==(int64_t i);
92 
93  protected:
96  : cstr(cstr), value(value) {}
97 
98  private:
99  BoundBuilder(const BoundBuilder &) = delete;
100  BoundBuilder &operator=(const BoundBuilder &) = delete;
101  bool operator==(const BoundBuilder &) = delete;
102  bool operator!=(const BoundBuilder &) = delete;
103 
105  Value value;
106  std::optional<int64_t> dim;
107  };
108 
109 public:
110  /// The stop condition when traversing the backward slice of a shaped value/
111  /// index-type value. The traversal continues until the stop condition
112  /// evaluates to "true" for a value.
113  ///
114  /// The first parameter of the function is the shaped value/index-typed
115  /// value. The second parameter is the dimension in case of a shaped value.
117  function_ref<bool(Value, std::optional<int64_t> /*dim*/)>;
118 
119  /// Compute a bound for the given index-typed value or shape dimension size.
120  /// The computed bound is stored in `resultMap`. The operands of the bound are
121  /// stored in `mapOperands`. An operand is either an index-type SSA value
122  /// or a shaped value and a dimension.
123  ///
124  /// `dim` must be `nullopt` if and only if `value` is index-typed. The bound
125  /// is computed in terms of values/dimensions for which `stopCondition`
126  /// evaluates to "true". To that end, the backward slice (reverse use-def
127  /// chain) of the given value is visited in a worklist-driven manner and the
128  /// constraint set is populated according to `ValueBoundsOpInterface` for each
129  /// visited value.
130  ///
131  /// By default, lower/equal bounds are closed and upper bounds are open. If
132  /// `closedUB` is set to "true", upper bounds are also closed.
133  static LogicalResult computeBound(AffineMap &resultMap,
134  ValueDimList &mapOperands,
135  presburger::BoundType type, Value value,
136  std::optional<int64_t> dim,
137  StopConditionFn stopCondition,
138  bool closedUB = false);
139 
140  /// Compute a bound in terms of the values/dimensions in `dependencies`. The
141  /// computed bound consists of only constant terms and dependent values (or
142  /// dimension sizes thereof).
143  static LogicalResult
144  computeDependentBound(AffineMap &resultMap, ValueDimList &mapOperands,
145  presburger::BoundType type, Value value,
146  std::optional<int64_t> dim, ValueDimList dependencies,
147  bool closedUB = false);
148 
149  /// Compute a bound in that is independent of all values in `independencies`.
150  ///
151  /// Independencies are the opposite of dependencies. The computed bound does
152  /// not contain any SSA values that are part of `independencies`. E.g., this
153  /// function can be used to make ops hoistable from loops. To that end, ops
154  /// must be made independent of loop induction variables (in the case of "for"
155  /// loops). Loop induction variables are the independencies; they may not
156  /// appear in the computed bound.
157  static LogicalResult
158  computeIndependentBound(AffineMap &resultMap, ValueDimList &mapOperands,
159  presburger::BoundType type, Value value,
160  std::optional<int64_t> dim, ValueRange independencies,
161  bool closedUB = false);
162 
163  /// Compute a constant bound for the given affine map, where dims and symbols
164  /// are bound to the given operands. The affine map must have exactly one
165  /// result.
166  ///
167  /// This function traverses the backward slice of the given operands in a
168  /// worklist-driven manner until `stopCondition` evaluates to "true". The
169  /// constraint set is populated according to `ValueBoundsOpInterface` for each
170  /// visited value. (No constraints are added for values for which the stop
171  /// condition evaluates to "true".)
172  ///
173  /// The stop condition is optional: If none is specified, the backward slice
174  /// is traversed in a breadth-first manner until a constant bound could be
175  /// computed.
176  ///
177  /// By default, lower/equal bounds are closed and upper bounds are open. If
178  /// `closedUB` is set to "true", upper bounds are also closed.
179  static FailureOr<int64_t>
181  std::optional<int64_t> dim = std::nullopt,
182  StopConditionFn stopCondition = nullptr,
183  bool closedUB = false);
185  presburger::BoundType type, AffineMap map, ValueDimList mapOperands,
186  StopConditionFn stopCondition = nullptr, bool closedUB = false);
188  presburger::BoundType type, AffineMap map, ArrayRef<Value> mapOperands,
189  StopConditionFn stopCondition = nullptr, bool closedUB = false);
190 
191  /// Compute a constant delta between the given two values. Return "failure"
192  /// if a constant delta could not be determined.
193  ///
194  /// `dim1`/`dim2` must be `nullopt` if and only if `value1`/`value2` are
195  /// index-typed.
196  static FailureOr<int64_t>
197  computeConstantDelta(Value value1, Value value2,
198  std::optional<int64_t> dim1 = std::nullopt,
199  std::optional<int64_t> dim2 = std::nullopt);
200 
201  /// Compute whether the given values/dimensions are equal. Return "failure" if
202  /// equality could not be determined.
203  ///
204  /// `dim1`/`dim2` must be `nullopt` if and only if `value1`/`value2` are
205  /// index-typed.
206  static FailureOr<bool> areEqual(Value value1, Value value2,
207  std::optional<int64_t> dim1 = std::nullopt,
208  std::optional<int64_t> dim2 = std::nullopt);
209 
210  /// Compute whether the given values/attributes are equal. Return "failure" if
211  /// equality could not be determined.
212  ///
213  /// `ofr1`/`ofr2` must be of index type.
215 
216  /// Return "true" if the given slices are guaranteed to be overlapping.
217  /// Return "false" if the given slices are guaranteed to be non-overlapping.
218  /// Return "failure" if unknown.
219  ///
220  /// Slices are overlapping if for all dimensions:
221  /// * offset1 + size1 * stride1 <= offset2
222  /// * and offset2 + size2 * stride2 <= offset1
223  ///
224  /// Slice are non-overlapping if the above constraint is not satisfied for
225  /// at least one dimension.
227  HyperrectangularSlice slice1,
228  HyperrectangularSlice slice2);
229 
230  /// Return "true" if the given slices are guaranteed to be equivalent.
231  /// Return "false" if the given slices are guaranteed to be non-equivalent.
232  /// Return "failure" if unknown.
233  ///
234  /// Slices are equivalent if their offsets, sizes and strices are equal.
236  HyperrectangularSlice slice1,
237  HyperrectangularSlice slice2);
238 
239  /// Add a bound for the given index-typed value or shaped value. This function
240  /// returns a builder that adds the bound.
241  BoundBuilder bound(Value value) { return BoundBuilder(*this, value); }
242 
243  /// Return an expression that represents the given index-typed value or shaped
244  /// value dimension. If this value/dimension was not used so far, it is added
245  /// to the worklist.
246  ///
247  /// `dim` must be `nullopt` if and only if the given value is of index type.
248  AffineExpr getExpr(Value value, std::optional<int64_t> dim = std::nullopt);
249 
250  /// Return an expression that represents a constant or index-typed SSA value.
251  /// In case of a value, if this value was not used so far, it is added to the
252  /// worklist.
254 
255  /// Return an expression that represents a constant.
256  AffineExpr getExpr(int64_t constant);
257 
258 protected:
259  /// Dimension identifier to indicate a value is index-typed. This is used for
260  /// internal data structures/API only.
261  static constexpr int64_t kIndexValue = -1;
262 
263  /// An index-typed value or the dimension of a shaped-type value.
264  using ValueDim = std::pair<Value, int64_t>;
265 
267 
268  /// Iteratively process all elements on the worklist until an index-typed
269  /// value or shaped value meets `stopCondition`. Such values are not processed
270  /// any further.
271  void processWorklist(StopConditionFn stopCondition);
272 
273  /// Bound the given column in the underlying constraint set by the given
274  /// expression.
275  void addBound(presburger::BoundType type, int64_t pos, AffineExpr expr);
276 
277  /// Return the column position of the given value/dimension. Asserts that the
278  /// value/dimension exists in the constraint set.
279  int64_t getPos(Value value, std::optional<int64_t> dim = std::nullopt) const;
280 
281  /// Insert a value/dimension into the constraint set. If `isSymbol` is set to
282  /// "false", a dimension is added. The value/dimension is added to the
283  /// worklist.
284  ///
285  /// Note: There are certain affine restrictions wrt. dimensions. E.g., they
286  /// cannot be multiplied. Furthermore, bounds can only be queried for
287  /// dimensions but not for symbols.
288  int64_t insert(Value value, std::optional<int64_t> dim, bool isSymbol = true);
289 
290  /// Insert an anonymous column into the constraint set. The column is not
291  /// bound to any value/dimension. If `isSymbol` is set to "false", a dimension
292  /// is added.
293  ///
294  /// Note: There are certain affine restrictions wrt. dimensions. E.g., they
295  /// cannot be multiplied. Furthermore, bounds can only be queried for
296  /// dimensions but not for symbols.
297  int64_t insert(bool isSymbol = true);
298 
299  /// Project out the given column in the constraint set.
300  void projectOut(int64_t pos);
301 
302  /// Project out all columns for which the condition holds.
303  void projectOut(function_ref<bool(ValueDim)> condition);
304 
305  /// Mapping of columns to values/shape dimensions.
307  /// Reverse mapping of values/shape dimensions to columns.
309 
310  /// Worklist of values/shape dimensions that have not been processed yet.
311  std::queue<int64_t> worklist;
312 
313  /// Constraint system of equalities and inequalities.
315 
316  /// Builder for constructing affine expressions.
318 };
319 
320 } // namespace mlir
321 
322 #include "mlir/Interfaces/ValueBoundsOpInterface.h.inc"
323 
324 #endif // MLIR_INTERFACES_VALUEBOUNDSOPINTERFACE_H_
Base type for affine expression.
Definition: AffineExpr.h:68
A multi-dimensional affine map Affine map's are immutable like Type's, and they are uniqued.
Definition: AffineMap.h:47
This class is a general helper class for creating context-global objects like types,...
Definition: Builders.h:50
This class provides support for representing a failure result, or a valid value of type T.
Definition: LogicalResult.h:78
FlatLinearConstraints is an extension of IntegerPolyhedron.
A hyperrectangular slice, represented as a list of offsets, sizes and strides.
HyperrectangularSlice(ArrayRef< OpFoldResult > offsets, ArrayRef< OpFoldResult > sizes, ArrayRef< OpFoldResult > strides)
ArrayRef< OpFoldResult > getMixedOffsets() const
ArrayRef< OpFoldResult > getMixedSizes() const
ArrayRef< OpFoldResult > getMixedStrides() const
MLIRContext is the top-level object for a collection of MLIR operations.
Definition: MLIRContext.h:60
This class represents a single result from folding an operation.
Definition: OpDefinition.h:266
Helper class that builds a bound for a shaped value dimension or index-typed value.
BoundBuilder(ValueBoundsConstraintSet &cstr, Value value)
BoundBuilder & operator[](int64_t dim)
Specify a dimension, assuming that the underlying value is a shaped value.
A helper class to be used with ValueBoundsOpInterface.
DenseMap< ValueDim, int64_t > valueDimToPosition
Reverse mapping of values/shape dimensions to columns.
static FailureOr< bool > areEqual(Value value1, Value value2, std::optional< int64_t > dim1=std::nullopt, std::optional< int64_t > dim2=std::nullopt)
Compute whether the given values/dimensions are equal.
AffineExpr getExpr(Value value, std::optional< int64_t > dim=std::nullopt)
Return an expression that represents the given index-typed value or shaped value dimension.
SmallVector< std::optional< ValueDim > > positionToValueDim
Mapping of columns to values/shape dimensions.
static LogicalResult computeBound(AffineMap &resultMap, ValueDimList &mapOperands, presburger::BoundType type, Value value, std::optional< int64_t > dim, StopConditionFn stopCondition, bool closedUB=false)
Compute a bound for the given index-typed value or shape dimension size.
int64_t insert(Value value, std::optional< int64_t > dim, bool isSymbol=true)
Insert a value/dimension into the constraint set.
void projectOut(int64_t pos)
Project out the given column in the constraint set.
static FailureOr< int64_t > computeConstantDelta(Value value1, Value value2, std::optional< int64_t > dim1=std::nullopt, std::optional< int64_t > dim2=std::nullopt)
Compute a constant delta between the given two values.
void addBound(presburger::BoundType type, int64_t pos, AffineExpr expr)
Bound the given column in the underlying constraint set by the given expression.
BoundBuilder bound(Value value)
Add a bound for the given index-typed value or shaped value.
int64_t getPos(Value value, std::optional< int64_t > dim=std::nullopt) const
Return the column position of the given value/dimension.
std::queue< int64_t > worklist
Worklist of values/shape dimensions that have not been processed yet.
FlatLinearConstraints cstr
Constraint system of equalities and inequalities.
void processWorklist(StopConditionFn stopCondition)
Iteratively process all elements on the worklist until an index-typed value or shaped value meets sto...
static FailureOr< bool > areEquivalentSlices(MLIRContext *ctx, HyperrectangularSlice slice1, HyperrectangularSlice slice2)
Return "true" if the given slices are guaranteed to be equivalent.
std::pair< Value, int64_t > ValueDim
An index-typed value or the dimension of a shaped-type value.
static LogicalResult computeDependentBound(AffineMap &resultMap, ValueDimList &mapOperands, presburger::BoundType type, Value value, std::optional< int64_t > dim, ValueDimList dependencies, bool closedUB=false)
Compute a bound in terms of the values/dimensions in dependencies.
static FailureOr< bool > areOverlappingSlices(MLIRContext *ctx, HyperrectangularSlice slice1, HyperrectangularSlice slice2)
Return "true" if the given slices are guaranteed to be overlapping.
Builder builder
Builder for constructing affine expressions.
static LogicalResult computeIndependentBound(AffineMap &resultMap, ValueDimList &mapOperands, presburger::BoundType type, Value value, std::optional< int64_t > dim, ValueRange independencies, bool closedUB=false)
Compute a bound in that is independent of all values in independencies.
static FailureOr< int64_t > computeConstantBound(presburger::BoundType type, Value value, std::optional< int64_t > dim=std::nullopt, StopConditionFn stopCondition=nullptr, bool closedUB=false)
Compute a constant bound for the given affine map, where dims and symbols are bound to the given oper...
static constexpr int64_t kIndexValue
Dimension identifier to indicate a value is index-typed.
This class provides an abstraction over the different types of ranges over Values.
Definition: ValueRange.h:378
This class represents an instance of an SSA value in the MLIR system, representing a computable value...
Definition: Value.h:96
BoundType
The type of bound: equal, lower bound or upper bound.
bool operator!=(const Fraction &x, const Fraction &y)
Definition: Fraction.h:92
Include the generated interface declarations.
This class represents an efficient way to signal success or failure.
Definition: LogicalResult.h:26