MLIR  18.0.0git
AffineMap.h
Go to the documentation of this file.
1 //===- AffineMap.h - MLIR Affine Map 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 // Affine maps are mathematical functions which map a list of dimension
10 // identifiers and symbols, to multidimensional affine expressions.
11 //
12 //===----------------------------------------------------------------------===//
13 
14 #ifndef MLIR_IR_AFFINEMAP_H
15 #define MLIR_IR_AFFINEMAP_H
16 
17 #include "mlir/IR/AffineExpr.h"
18 #include "mlir/Support/LLVM.h"
19 #include "llvm/ADT/ArrayRef.h"
20 #include "llvm/ADT/DenseMapInfo.h"
21 #include "llvm/ADT/SmallBitVector.h"
22 #include "llvm/ADT/SmallVectorExtras.h"
23 #include <optional>
24 
25 namespace llvm {
26 class SmallBitVector;
27 } // namespace llvm
28 
29 namespace mlir {
30 
31 namespace detail {
32 struct AffineMapStorage;
33 } // namespace detail
34 
35 class Attribute;
36 struct LogicalResult;
37 class MLIRContext;
38 
39 /// A multi-dimensional affine map
40 /// Affine map's are immutable like Type's, and they are uniqued.
41 /// Eg: (d0, d1) -> (d0/128, d0 mod 128, d1)
42 /// The names used (d0, d1) don't matter - it's the mathematical function that
43 /// is unique to this affine map.
44 class AffineMap {
45 public:
47 
48  constexpr AffineMap() = default;
49  explicit AffineMap(ImplType *map) : map(map) {}
50 
51  /// Returns a zero result affine map with no dimensions or symbols: () -> ().
52  static AffineMap get(MLIRContext *context);
53 
54  /// Returns a zero result affine map with `dimCount` dimensions and
55  /// `symbolCount` symbols, e.g.: `(...) -> ()`.
56  static AffineMap get(unsigned dimCount, unsigned symbolCount,
57  MLIRContext *context);
58 
59  /// Returns an affine map with `dimCount` dimensions and `symbolCount` mapping
60  /// to a single output dimension
61  static AffineMap get(unsigned dimCount, unsigned symbolCount,
62  AffineExpr result);
63 
64  /// Returns an affine map with `dimCount` dimensions and `symbolCount` mapping
65  /// to the given results.
66  static AffineMap get(unsigned dimCount, unsigned symbolCount,
67  ArrayRef<AffineExpr> results, MLIRContext *context);
68 
69  /// Returns a single constant result affine map.
70  static AffineMap getConstantMap(int64_t val, MLIRContext *context);
71 
72  /// Returns an AffineMap with 'numDims' identity result dim exprs.
73  static AffineMap getMultiDimIdentityMap(unsigned numDims,
74  MLIRContext *context);
75 
76  /// Returns an identity affine map (d0, ..., dn) -> (dp, ..., dn) on the most
77  /// minor dimensions.
78  static AffineMap getMinorIdentityMap(unsigned dims, unsigned results,
79  MLIRContext *context);
80 
81  /// Returns an identity affine map witn `numDims` input dimensions and
82  /// filtered results using `keepDimFilter`. If `keepDimFilter` returns true
83  /// for a dimension, the dimension is kept in the affine map results.
84  /// Otherwise, the dimension is dropped from the results.
85  ///
86  /// Examples:
87  /// * getFilteredIdentityMap(4, [false, true, false, true])
88  /// -> affine_map<(d0, d1, d2, d3) -> (d1, d3)>
89  /// * getFilteredIdentityMap(3, [false, false, true])
90  /// -> affine_map<(d0, d1, d2) -> (d2)>
91  static AffineMap
92  getFilteredIdentityMap(MLIRContext *ctx, unsigned numDims,
93  llvm::function_ref<bool(AffineDimExpr)> keepDimFilter);
94 
95  /// Returns an AffineMap representing a permutation.
96  /// The permutation is expressed as a non-empty vector of integers.
97  /// E.g. the permutation `(i,j,k) -> (j,k,i)` will be expressed with
98  /// `permutation = [1,2,0]`. All values in `permutation` must be
99  /// integers, in the range 0..`permutation.size()-1` without duplications
100  /// (i.e. `[1,1,2]` is an invalid permutation).
102  MLIRContext *context);
103 
104  /// Returns a vector of AffineMaps; each with as many results as
105  /// `exprs.size()`, as many dims as the largest dim in `exprs` and as many
106  /// symbols as the largest symbol in `exprs`.
111 
112  MLIRContext *getContext() const;
113 
114  explicit operator bool() const { return map != nullptr; }
115  bool operator==(AffineMap other) const { return other.map == map; }
116  bool operator!=(AffineMap other) const { return !(other.map == map); }
117 
118  /// Returns true if this affine map is an identity affine map.
119  /// An identity affine map corresponds to an identity affine function on the
120  /// dimensional identifiers.
121  bool isIdentity() const;
122 
123  /// Returns true if this affine map is an identity affine map on the symbol
124  /// identifiers.
125  bool isSymbolIdentity() const;
126 
127  /// Returns true if this affine map is a minor identity, i.e. an identity
128  /// affine map (d0, ..., dn) -> (dp, ..., dn) on the most minor dimensions.
129  bool isMinorIdentity() const;
130 
131  /// Returns true if this affine map is a minor identity up to broadcasted
132  /// dimensions which are indicated by value 0 in the result. If
133  /// `broadcastedDims` is not null, it will be populated with the indices of
134  /// the broadcasted dimensions in the result array.
135  /// Example: affine_map<(d0, d1, d2, d3, d4) -> (0, d2, 0, d4)>
136  /// (`broadcastedDims` will contain [0, 2])
138  SmallVectorImpl<unsigned> *broadcastedDims = nullptr) const;
139 
140  /// Return true if this affine map can be converted to a minor identity with
141  /// broadcast by doing a permute. Return a permutation (there may be
142  /// several) to apply to get to a minor identity with broadcasts.
143  /// Ex:
144  /// * (d0, d1, d2) -> (0, d1) maps to minor identity (d1, 0 = d2) with
145  /// perm = [1, 0] and broadcast d2
146  /// * (d0, d1, d2) -> (d0, 0) cannot be mapped to a minor identity by
147  /// permutation + broadcast
148  /// * (d0, d1, d2, d3) -> (0, d1, d3) maps to minor identity (d1, 0 = d2, d3)
149  /// with perm = [1, 0, 2] and broadcast d2
150  /// * (d0, d1) -> (d1, 0, 0, d0) maps to minor identity (d0, d1) with extra
151  /// leading broadcat dimensions. The map returned would be (0, 0, d0, d1)
152  /// with perm = [3, 0, 1, 2]
154  SmallVectorImpl<unsigned> &permutedDims) const;
155 
156  /// Returns true if this affine map is an empty map, i.e., () -> ().
157  bool isEmpty() const;
158 
159  /// Returns true if this affine map is a single result constant function.
160  bool isSingleConstant() const;
161 
162  /// Returns true if this affine map has only constant results.
163  bool isConstant() const;
164 
165  /// Returns the constant result of this map. This methods asserts that the map
166  /// has a single constant result.
167  int64_t getSingleConstantResult() const;
168 
169  /// Returns the constant results of this map. This method asserts that the map
170  /// has all constant results.
172 
173  // Prints affine map to 'os'.
174  void print(raw_ostream &os) const;
175  void dump() const;
176 
177  unsigned getNumDims() const;
178  unsigned getNumSymbols() const;
179  unsigned getNumResults() const;
180  unsigned getNumInputs() const;
181 
183  AffineExpr getResult(unsigned idx) const;
184 
185  /// Extracts the position of the dimensional expression at the given result,
186  /// when the caller knows it is safe to do so.
187  unsigned getDimPosition(unsigned idx) const;
188 
189  /// Extracts the first result position where `input` dimension resides.
190  /// Returns `std::nullopt` if `input` is not a dimension expression or cannot
191  /// be found in results.
192  std::optional<unsigned> getResultPosition(AffineExpr input) const;
193 
194  /// Return true if any affine expression involves AffineDimExpr `position`.
195  bool isFunctionOfDim(unsigned position) const {
196  return llvm::any_of(getResults(), [&](AffineExpr e) {
197  return e.isFunctionOfDim(position);
198  });
199  }
200 
201  /// Return true if any affine expression involves AffineSymbolExpr `position`.
202  bool isFunctionOfSymbol(unsigned position) const {
203  return llvm::any_of(getResults(), [&](AffineExpr e) {
204  return e.isFunctionOfSymbol(position);
205  });
206  }
207 
208  /// Walk all of the AffineExpr's in this mapping. Each node in an expression
209  /// tree is visited in postorder.
210  void walkExprs(llvm::function_ref<void(AffineExpr)> callback) const;
211 
212  /// This method substitutes any uses of dimensions and symbols (e.g.
213  /// dim#0 with dimReplacements[0]) in subexpressions and returns the modified
214  /// expression mapping. Because this can be used to eliminate dims and
215  /// symbols, the client needs to specify the number of dims and symbols in
216  /// the result. The returned map always has the same number of results.
218  ArrayRef<AffineExpr> symReplacements,
219  unsigned numResultDims,
220  unsigned numResultSyms) const;
221 
222  /// Sparse replace method. Apply AffineExpr::replace(`expr`, `replacement`) to
223  /// each of the results and return a new AffineMap with the new results and
224  /// with the specified number of dims and symbols.
225  AffineMap replace(AffineExpr expr, AffineExpr replacement,
226  unsigned numResultDims, unsigned numResultSyms) const;
227 
228  /// Sparse replace method. Apply AffineExpr::replace(`map`) to each of the
229  /// results and return a new AffineMap with the new results and with inferred
230  /// number of dims and symbols.
232 
233  /// Sparse replace method. Apply AffineExpr::replace(`map`) to each of the
234  /// results and return a new AffineMap with the new results and with the
235  /// specified number of dims and symbols.
237  unsigned numResultDims, unsigned numResultSyms) const;
238 
239  /// Replace dims[offset ... numDims)
240  /// by dims[offset + shift ... shift + numDims).
241  AffineMap shiftDims(unsigned shift, unsigned offset = 0) const {
242  assert(offset <= getNumDims());
243  return AffineMap::get(getNumDims() + shift, getNumSymbols(),
244  llvm::map_to_vector<4>(
245  getResults(),
246  [&](AffineExpr e) {
247  return e.shiftDims(getNumDims(), shift, offset);
248  }),
249  getContext());
250  }
251 
252  /// Replace symbols[offset ... numSymbols)
253  /// by symbols[offset + shift ... shift + numSymbols).
254  AffineMap shiftSymbols(unsigned shift, unsigned offset = 0) const {
255  return AffineMap::get(getNumDims(), getNumSymbols() + shift,
256  llvm::map_to_vector<4>(getResults(),
257  [&](AffineExpr e) {
258  return e.shiftSymbols(
259  getNumSymbols(), shift,
260  offset);
261  }),
262  getContext());
263  }
264 
265  /// Returns a new AffineMap with the same number of dims and symbols and one
266  /// less result at `pos`, dropped.
267  AffineMap dropResult(int64_t pos) const {
268  return dropResults(ArrayRef({pos}));
269  }
270 
271  // Returns a new AffineMap with the same number of dims and symbols, but all
272  // results in `positions` dropped.
274  SmallVector<int64_t> reverse_sorted_positions = llvm::to_vector(positions);
275  llvm::sort(reverse_sorted_positions, std::greater<int64_t>());
276 
277  auto exprs = llvm::to_vector<4>(getResults());
278  for (int64_t pos : reverse_sorted_positions)
279  exprs.erase(exprs.begin() + pos);
280  return AffineMap::get(getNumDims(), getNumSymbols(), exprs, getContext());
281  }
282 
283  // Returns a new AffineMap with the same number of dims and symbols, but all
284  // results in `positions` dropped.
285  AffineMap dropResults(const llvm::SmallBitVector &positions) const;
286 
287  /// Returns a new AffineMap with the same number of dims and symbols and an
288  /// extra result inserted at `pos`.
289  AffineMap insertResult(AffineExpr expr, unsigned pos) const {
290  auto exprs = llvm::to_vector<4>(getResults());
291  exprs.insert(exprs.begin() + pos, expr);
292  return AffineMap::get(getNumDims(), getNumSymbols(), exprs, getContext());
293  }
294 
295  /// Folds the results of the application of an affine map on the provided
296  /// operands to a constant if possible.
298  SmallVectorImpl<Attribute> &results) const;
299 
300  /// Propagates the constant operands into this affine map. Operands are
301  /// allowed to be null, at which point they are treated as non-constant. This
302  /// does not change the number of symbols and dimensions. Returns a new map,
303  /// which may be equal to the old map if no folding happened. If `results` is
304  /// provided and if all expressions in the map were folded to constants,
305  /// `results` will contain the values of these constants.
306  AffineMap
307  partialConstantFold(ArrayRef<Attribute> operandConstants,
308  SmallVectorImpl<int64_t> *results = nullptr) const;
309 
310  /// Returns the AffineMap resulting from composing `this` with `map`.
311  /// The resulting AffineMap has as many AffineDimExpr as `map` and as many
312  /// AffineSymbolExpr as the concatenation of `this` and `map` (in which case
313  /// the symbols of `this` map come first).
314  ///
315  /// Prerequisites:
316  /// The maps are composable, i.e. that the number of AffineDimExpr of `this`
317  /// matches the number of results of `map`.
318  ///
319  /// Example:
320  /// map1: `(d0, d1)[s0, s1] -> (d0 + 1 + s1, d1 - 1 - s0)`
321  /// map2: `(d0)[s0] -> (d0 + s0, d0 - s0)`
322  /// map1.compose(map2):
323  /// `(d0)[s0, s1, s2] -> (d0 + s1 + s2 + 1, d0 - s0 - s2 - 1)`
324  AffineMap compose(AffineMap map) const;
325 
326  /// Applies composition by the dims of `this` to the integer `values` and
327  /// returns the resulting values. `this` must be symbol-less.
329 
330  /// Returns true if the AffineMap represents a subset (i.e. a projection) of a
331  /// symbol-less permutation map. `allowZeroInResults` allows projected
332  /// permutation maps with constant zero result expressions.
333  /// TODO: Remove `allowZeroInResults` when constant zero result expressions
334  /// are broadly supported.
335  bool isProjectedPermutation(bool allowZeroInResults = false) const;
336 
337  /// Returns true if the AffineMap represents a symbol-less permutation map.
338  bool isPermutation() const;
339 
340  /// Returns the map consisting of the `resultPos` subset.
341  AffineMap getSubMap(ArrayRef<unsigned> resultPos) const;
342 
343  /// Returns the map consisting of `length` expressions starting from `start`.
344  AffineMap getSliceMap(unsigned start, unsigned length) const;
345 
346  /// Returns the map consisting of the most major `numResults` results.
347  /// Returns the null AffineMap if `numResults` == 0.
348  /// Returns `*this` if `numResults` >= `this->getNumResults()`.
349  AffineMap getMajorSubMap(unsigned numResults) const;
350 
351  /// Returns the map consisting of the most minor `numResults` results.
352  /// Returns the null AffineMap if `numResults` == 0.
353  /// Returns `*this` if `numResults` >= `this->getNumResults()`.
354  AffineMap getMinorSubMap(unsigned numResults) const;
355 
356  /// Get the largest known divisor of all map expressions.
357  /// For eg: for (d0, d1) -> (8*d0 + 4, 4*d1 + 2), the result is 2.
358  /// In the case of maps with no expressions or all zero constant expressions,
359  /// the largest known divisor is trivially the max uint64_t value.
361 
362  friend ::llvm::hash_code hash_value(AffineMap arg);
363 
364  /// Methods supporting C API.
365  const void *getAsOpaquePointer() const {
366  return static_cast<const void *>(map);
367  }
368  static AffineMap getFromOpaquePointer(const void *pointer) {
369  return AffineMap(reinterpret_cast<ImplType *>(const_cast<void *>(pointer)));
370  }
371 
372 private:
373  ImplType *map{nullptr};
374 
375  static AffineMap getImpl(unsigned dimCount, unsigned symbolCount,
376  ArrayRef<AffineExpr> results, MLIRContext *context);
377 };
378 
379 // Make AffineExpr hashable.
380 inline ::llvm::hash_code hash_value(AffineMap arg) {
381  return ::llvm::hash_value(arg.map);
382 }
383 
384 /// A mutable affine map. Its affine expressions are however unique.
386 public:
387  MutableAffineMap() = default;
389 
390  ArrayRef<AffineExpr> getResults() const { return results; }
391  AffineExpr getResult(unsigned idx) const { return results[idx]; }
392  void setResult(unsigned idx, AffineExpr result) { results[idx] = result; }
393  unsigned getNumResults() const { return results.size(); }
394  unsigned getNumDims() const { return numDims; }
395  void setNumDims(unsigned d) { numDims = d; }
396  unsigned getNumSymbols() const { return numSymbols; }
397  void setNumSymbols(unsigned d) { numSymbols = d; }
398  MLIRContext *getContext() const { return context; }
399 
400  /// Returns true if the idx'th result expression is a multiple of factor.
401  bool isMultipleOf(unsigned idx, int64_t factor) const;
402 
403  /// Resets this MutableAffineMap with 'map'.
404  void reset(AffineMap map);
405 
406  /// Simplify the (result) expressions in this map using analysis (used by
407  //-simplify-affine-expr pass).
408  void simplify();
409  /// Get the AffineMap corresponding to this MutableAffineMap. Note that an
410  /// AffineMap will be uniqued and stored in context, while a mutable one
411  /// isn't.
412  AffineMap getAffineMap() const;
413 
414 private:
415  // Same meaning as AffineMap's fields.
417  unsigned numDims = 0;
418  unsigned numSymbols = 0;
419  /// A pointer to the IR's context to store all newly created
420  /// AffineExprStorage's.
421  MLIRContext *context = nullptr;
422 };
423 
424 /// Simplifies an affine map by simplifying its underlying AffineExpr results.
425 AffineMap simplifyAffineMap(AffineMap map);
426 
427 /// Drop the dims that are listed in `unusedDims`.
428 AffineMap compressDims(AffineMap map, const llvm::SmallBitVector &unusedDims);
429 
430 /// Drop the dims that are not used.
431 AffineMap compressUnusedDims(AffineMap map);
432 
433 /// Drop the dims that are not used by any of the individual maps in `maps`.
434 /// Asserts that all maps in `maps` are normalized to the same number of
435 /// dims and symbols.
436 SmallVector<AffineMap> compressUnusedDims(ArrayRef<AffineMap> maps);
437 
438 /// Drop the symbols that are listed in `unusedSymbols`.
439 AffineMap compressSymbols(AffineMap map,
440  const llvm::SmallBitVector &unusedSymbols);
441 
442 /// Drop the symbols that are not used.
443 AffineMap compressUnusedSymbols(AffineMap map);
444 
445 /// Drop the symbols that are not used by any of the individual maps in `maps`.
446 /// Asserts that all maps in `maps` are normalized to the same number of
447 /// dims and symbols.
448 SmallVector<AffineMap> compressUnusedSymbols(ArrayRef<AffineMap> maps);
449 
450 /// Returns a map with the same dimension and symbol count as `map`, but whose
451 /// results are the unique affine expressions of `map`.
452 AffineMap removeDuplicateExprs(AffineMap map);
453 
454 /// Returns a map of codomain to domain dimensions such that the first codomain
455 /// dimension for a particular domain dimension is selected.
456 /// Returns an empty map if the input map is empty.
457 /// Returns null map (not empty map) if `map` is not invertible (i.e. `map` does
458 /// not contain a subset that is a permutation of full domain rank).
459 ///
460 /// Prerequisites:
461 /// 1. `map` has no symbols.
462 ///
463 /// Example 1:
464 ///
465 /// ```mlir
466 /// (d0, d1, d2) -> (d1, d1, d0, d2, d1, d2, d1, d0)
467 /// 0 2 3
468 /// ```
469 ///
470 /// returns:
471 ///
472 /// ```mlir
473 /// (d0, d1, d2, d3, d4, d5, d6, d7) -> (d2, d0, d3)
474 /// ```
475 ///
476 /// Example 2:
477 ///
478 /// ```mlir
479 /// (d0, d1, d2) -> (d1, d0 + d1, d0, d2, d1, d2, d1, d0)
480 /// 0 2 3
481 /// ```
482 ///
483 /// returns:
484 ///
485 /// ```mlir
486 /// (d0, d1, d2, d3, d4, d5, d6, d7) -> (d2, d0, d3)
487 /// ```
488 AffineMap inversePermutation(AffineMap map);
489 
490 /// Return the reverse map of a projected permutation where the projected
491 /// dimensions are transformed into 0s.
492 ///
493 /// Prerequisites: `map` must be a projected permutation.
494 ///
495 /// Example 1:
496 ///
497 /// ```mlir
498 /// affine_map<(d0, d1, d2, d3) -> (d2, d0)>
499 /// ```
500 ///
501 /// returns:
502 ///
503 /// ```mlir
504 /// affine_map<(d0, d1) -> (d1, 0, d0, 0)>
505 /// ```
506 ///
507 /// Example 2:
508 ///
509 /// ```mlir
510 /// affine_map<(d0, d1, d2, d3) -> (d0, d3)>
511 /// ```
512 ///
513 /// returns:
514 ///
515 /// ```mlir
516 /// affine_map<(d0, d1) -> (d0, 0, 0, d1)>
517 /// ```
518 ///
519 /// Example 3:
520 ///
521 /// ```mlir
522 /// affine_map<(d0, d1, d2, d3) -> (d2)>
523 /// ```
524 ///
525 /// returns:
526 ///
527 /// ```mlir
528 /// affine_map<(d0) -> (0, 0, d0, 0)>
529 /// ```
530 /// Example 4:
531 ///
532 /// ```mlir
533 /// affine_map<(d0, d1, d2) -> (d0, 0)>
534 /// ```
535 ///
536 /// returns:
537 ///
538 /// ```mlir
539 /// affine_map<(d0, d1) -> (d0, 0, 0)>
540 /// ```
541 AffineMap inverseAndBroadcastProjectedPermutation(AffineMap map);
542 
543 /// Concatenates a list of `maps` into a single AffineMap, stepping over
544 /// potentially empty maps. Assumes each of the underlying map has 0 symbols.
545 /// The resulting map has a number of dims equal to the max of `maps`' dims and
546 /// the concatenated results as its results.
547 /// Returns an empty map if all input `maps` are empty.
548 ///
549 /// Example:
550 /// When applied to the following list of 3 affine maps,
551 ///
552 /// ```mlir
553 /// {
554 /// (i, j, k) -> (i, k),
555 /// (i, j, k) -> (k, j),
556 /// (i, j, k) -> (i, j)
557 /// }
558 /// ```
559 ///
560 /// Returns the map:
561 ///
562 /// ```mlir
563 /// (i, j, k) -> (i, k, k, j, i, j)
564 /// ```
565 AffineMap concatAffineMaps(ArrayRef<AffineMap> maps);
566 
567 /// Returns the map that results from projecting out the dimensions specified in
568 /// `projectedDimensions`. The projected dimensions are set to 0.
569 ///
570 /// Example:
571 /// 1) map : affine_map<(d0, d1, d2) -> (d0, d1)>
572 /// projected_dimensions : {2}
573 /// result : affine_map<(d0, d1) -> (d0, d1)>
574 ///
575 /// 2) map : affine_map<(d0, d1) -> (d0 + d1)>
576 /// projected_dimensions : {1}
577 /// result : affine_map<(d0) -> (d0)>
578 ///
579 /// 3) map : affine_map<(d0, d1, d2) -> (d0, d1)>
580 /// projected_dimensions : {1}
581 /// result : affine_map<(d0, d1) -> (d0, 0)>
582 ///
583 /// This function also compresses the dims when the boolean flag is true.
584 AffineMap projectDims(AffineMap map,
585  const llvm::SmallBitVector &projectedDimensions,
586  bool compressDimsFlag = false);
587 /// Symbol counterpart of `projectDims`.
588 /// This function also compresses the symbols when the boolean flag is true.
589 AffineMap projectSymbols(AffineMap map,
590  const llvm::SmallBitVector &projectedSymbols,
591  bool compressSymbolsFlag = false);
592 /// Calls `projectDims(map, projectedDimensions, compressDimsFlag)`.
593 /// If `compressSymbolsFlag` is true, additionally call `compressUnusedSymbols`.
594 AffineMap getProjectedMap(AffineMap map,
595  const llvm::SmallBitVector &projectedDimensions,
596  bool compressDimsFlag = true,
597  bool compressSymbolsFlag = true);
598 
599 // Return a bitvector where each bit set indicates a dimension that is not used
600 // by any of the maps in the input array `maps`.
601 llvm::SmallBitVector getUnusedDimsBitVector(ArrayRef<AffineMap> maps);
602 
603 // Return a bitvector where each bit set indicates a symbol that is not used
604 // by any of the maps in the input array `maps`.
605 llvm::SmallBitVector getUnusedSymbolsBitVector(ArrayRef<AffineMap> maps);
606 
607 /// Expand `map` to operate on `rank` dims while projecting out the dims in
608 /// `projectedDimensions`. This amounts to composing `map` with
609 /// `id(rank).dropResults(projectedDimensions)`.
610 AffineMap expandDimsToRank(AffineMap map, int64_t rank,
611  const llvm::SmallBitVector &projectedDimensions);
612 
613 inline raw_ostream &operator<<(raw_ostream &os, AffineMap map) {
614  map.print(os);
615  return os;
616 }
617 
618 //===----------------------------------------------------------------------===//
619 // Templated helper functions.
620 //===----------------------------------------------------------------------===//
621 
622 /// Apply a permutation from `map` to `source` and return the result.
623 template <typename T>
625  assert(map.isProjectedPermutation());
626  assert(map.getNumInputs() == source.size());
627  SmallVector<T> result;
628  result.reserve(map.getNumResults());
629  for (AffineExpr expr : map.getResults()) {
630  if (auto dimExpr = expr.dyn_cast<AffineDimExpr>()) {
631  result.push_back(source[dimExpr.getPosition()]);
632  } else if (auto constExpr = expr.dyn_cast<AffineConstantExpr>()) {
633  assert(constExpr.getValue() == 0 &&
634  "Unexpected constant in projected permutation map");
635  result.push_back(0);
636  } else {
637  llvm_unreachable("Unexpected result in projected permutation map");
638  }
639  }
640  return result;
641 }
642 
643 /// Calculates maximum dimension and symbol positions from the expressions
644 /// in `exprsLists` and stores them in `maxDim` and `maxSym` respectively.
645 template <typename AffineExprContainer>
647  int64_t &maxDim, int64_t &maxSym) {
648  for (const auto &exprs : exprsList) {
649  for (auto expr : exprs) {
650  expr.walk([&maxDim, &maxSym](AffineExpr e) {
651  if (auto d = e.dyn_cast<AffineDimExpr>())
652  maxDim = std::max(maxDim, static_cast<int64_t>(d.getPosition()));
653  if (auto s = e.dyn_cast<AffineSymbolExpr>())
654  maxSym = std::max(maxSym, static_cast<int64_t>(s.getPosition()));
655  });
656  }
657  }
658 }
659 
660 } // namespace mlir
661 
662 namespace llvm {
663 
664 // AffineExpr hash just like pointers
665 template <>
666 struct DenseMapInfo<mlir::AffineMap> {
668  auto *pointer = llvm::DenseMapInfo<void *>::getEmptyKey();
669  return mlir::AffineMap(static_cast<mlir::AffineMap::ImplType *>(pointer));
670  }
673  return mlir::AffineMap(static_cast<mlir::AffineMap::ImplType *>(pointer));
674  }
675  static unsigned getHashValue(mlir::AffineMap val) {
676  return mlir::hash_value(val);
677  }
678  static bool isEqual(mlir::AffineMap LHS, mlir::AffineMap RHS) {
679  return LHS == RHS;
680  }
681 };
682 
683 } // namespace llvm
684 
685 #endif // MLIR_IR_AFFINEMAP_H
static Value max(ImplicitLocOpBuilder &builder, Value value, Value bound)
An integer constant appearing in affine expression.
Definition: AffineExpr.h:232
A dimensional identifier appearing in an affine expression.
Definition: AffineExpr.h:216
Base type for affine expression.
Definition: AffineExpr.h:68
AffineExpr shiftDims(unsigned numDims, unsigned shift, unsigned offset=0) const
Replace dims[offset ...
Definition: AffineExpr.cpp:110
AffineExpr shiftSymbols(unsigned numSymbols, unsigned shift, unsigned offset=0) const
Replace symbols[offset ...
Definition: AffineExpr.cpp:122
bool isFunctionOfDim(unsigned position) const
Return true if the affine expression involves AffineDimExpr position.
Definition: AffineExpr.cpp:293
bool isFunctionOfSymbol(unsigned position) const
Return true if the affine expression involves AffineSymbolExpr position.
Definition: AffineExpr.cpp:304
U dyn_cast() const
Definition: AffineExpr.h:283
A multi-dimensional affine map Affine map's are immutable like Type's, and they are uniqued.
Definition: AffineMap.h:44
int64_t getSingleConstantResult() const
Returns the constant result of this map.
Definition: AffineMap.cpp:324
static AffineMap getMinorIdentityMap(unsigned dims, unsigned results, MLIRContext *context)
Returns an identity affine map (d0, ..., dn) -> (dp, ..., dn) on the most minor dimensions.
Definition: AffineMap.cpp:109
AffineMap dropResults(ArrayRef< int64_t > positions) const
Definition: AffineMap.h:273
AffineMap getSliceMap(unsigned start, unsigned length) const
Returns the map consisting of length expressions starting from start.
Definition: AffineMap.cpp:578
AffineMap getMajorSubMap(unsigned numResults) const
Returns the map consisting of the most major numResults results.
Definition: AffineMap.cpp:583
MLIRContext * getContext() const
Definition: AffineMap.cpp:284
friend ::llvm::hash_code hash_value(AffineMap arg)
Definition: AffineMap.h:380
bool isFunctionOfDim(unsigned position) const
Return true if any affine expression involves AffineDimExpr position.
Definition: AffineMap.h:195
AffineMap partialConstantFold(ArrayRef< Attribute > operandConstants, SmallVectorImpl< int64_t > *results=nullptr) const
Propagates the constant operands into this affine map.
Definition: AffineMap.cpp:397
bool isMinorIdentity() const
Returns true if this affine map is a minor identity, i.e.
Definition: AffineMap.cpp:129
unsigned getDimPosition(unsigned idx) const
Extracts the position of the dimensional expression at the given result, when the caller knows it is ...
Definition: AffineMap.cpp:358
bool isConstant() const
Returns true if this affine map has only constant results.
Definition: AffineMap.cpp:318
static AffineMap getMultiDimIdentityMap(unsigned numDims, MLIRContext *context)
Returns an AffineMap with 'numDims' identity result dim exprs.
Definition: AffineMap.cpp:275
static AffineMap get(MLIRContext *context)
Returns a zero result affine map with no dimensions or symbols: () -> ().
AffineMap shiftDims(unsigned shift, unsigned offset=0) const
Replace dims[offset ...
Definition: AffineMap.h:241
bool isSingleConstant() const
Returns true if this affine map is a single result constant function.
Definition: AffineMap.cpp:314
AffineMap insertResult(AffineExpr expr, unsigned pos) const
Returns a new AffineMap with the same number of dims and symbols and an extra result inserted at pos.
Definition: AffineMap.h:289
bool isProjectedPermutation(bool allowZeroInResults=false) const
Returns true if the AffineMap represents a subset (i.e.
Definition: AffineMap.cpp:534
AffineMap getMinorSubMap(unsigned numResults) const
Returns the map consisting of the most minor numResults results.
Definition: AffineMap.cpp:591
detail::AffineMapStorage ImplType
Definition: AffineMap.h:46
uint64_t getLargestKnownDivisorOfMapExprs()
Get the largest known divisor of all map expressions.
Definition: AffineMap.cpp:264
constexpr AffineMap()=default
bool isEmpty() const
Returns true if this affine map is an empty map, i.e., () -> ().
Definition: AffineMap.cpp:310
AffineMap dropResult(int64_t pos) const
Returns a new AffineMap with the same number of dims and symbols and one less result at pos,...
Definition: AffineMap.h:267
AffineMap(ImplType *map)
Definition: AffineMap.h:49
std::optional< unsigned > getResultPosition(AffineExpr input) const
Extracts the first result position where input dimension resides.
Definition: AffineMap.cpp:362
bool operator==(AffineMap other) const
Definition: AffineMap.h:115
unsigned getNumSymbols() const
Definition: AffineMap.cpp:341
bool isMinorIdentityWithBroadcasting(SmallVectorImpl< unsigned > *broadcastedDims=nullptr) const
Returns true if this affine map is a minor identity up to broadcasted dimensions which are indicated ...
Definition: AffineMap.cpp:137
unsigned getNumDims() const
Definition: AffineMap.cpp:337
ArrayRef< AffineExpr > getResults() const
Definition: AffineMap.cpp:350
SmallVector< int64_t > getConstantResults() const
Returns the constant results of this map.
Definition: AffineMap.cpp:329
bool isFunctionOfSymbol(unsigned position) const
Return true if any affine expression involves AffineSymbolExpr position.
Definition: AffineMap.h:202
bool isPermutationOfMinorIdentityWithBroadcasting(SmallVectorImpl< unsigned > &permutedDims) const
Return true if this affine map can be converted to a minor identity with broadcast by doing a permute...
Definition: AffineMap.cpp:177
LogicalResult constantFold(ArrayRef< Attribute > operandConstants, SmallVectorImpl< Attribute > &results) const
Folds the results of the application of an affine map on the provided operands to a constant if possi...
Definition: AffineMap.cpp:378
bool isSymbolIdentity() const
Returns true if this affine map is an identity affine map on the symbol identifiers.
Definition: AffineMap.cpp:298
unsigned getNumResults() const
Definition: AffineMap.cpp:345
AffineMap replaceDimsAndSymbols(ArrayRef< AffineExpr > dimReplacements, ArrayRef< AffineExpr > symReplacements, unsigned numResultDims, unsigned numResultSyms) const
This method substitutes any uses of dimensions and symbols (e.g.
Definition: AffineMap.cpp:439
unsigned getNumInputs() const
Definition: AffineMap.cpp:346
AffineMap shiftSymbols(unsigned shift, unsigned offset=0) const
Replace symbols[offset ...
Definition: AffineMap.h:254
static AffineMap getFromOpaquePointer(const void *pointer)
Definition: AffineMap.h:368
static SmallVector< AffineMap, 4 > inferFromExprList(ArrayRef< ArrayRef< AffineExpr >> exprsList)
Returns a vector of AffineMaps; each with as many results as exprs.size(), as many dims as the larges...
Definition: AffineMap.cpp:255
const void * getAsOpaquePointer() const
Methods supporting C API.
Definition: AffineMap.h:365
AffineExpr getResult(unsigned idx) const
Definition: AffineMap.cpp:354
static AffineMap getFilteredIdentityMap(MLIRContext *ctx, unsigned numDims, llvm::function_ref< bool(AffineDimExpr)> keepDimFilter)
Returns an identity affine map witn numDims input dimensions and filtered results using keepDimFilter...
Definition: AffineMap.cpp:116
AffineMap replace(AffineExpr expr, AffineExpr replacement, unsigned numResultDims, unsigned numResultSyms) const
Sparse replace method.
Definition: AffineMap.cpp:454
void dump() const
static AffineMap getPermutationMap(ArrayRef< unsigned > permutation, MLIRContext *context)
Returns an AffineMap representing a permutation.
Definition: AffineMap.cpp:225
bool operator!=(AffineMap other) const
Definition: AffineMap.h:116
void walkExprs(llvm::function_ref< void(AffineExpr)> callback) const
Walk all of the AffineExpr's in this mapping.
Definition: AffineMap.cpp:429
static AffineMap getConstantMap(int64_t val, MLIRContext *context)
Returns a single constant result affine map.
Definition: AffineMap.cpp:102
AffineMap getSubMap(ArrayRef< unsigned > resultPos) const
Returns the map consisting of the resultPos subset.
Definition: AffineMap.cpp:570
void print(raw_ostream &os) const
AffineMap compose(AffineMap map) const
Returns the AffineMap resulting from composing this with map.
Definition: AffineMap.cpp:495
bool isIdentity() const
Returns true if this affine map is an identity affine map.
Definition: AffineMap.cpp:286
bool isPermutation() const
Returns true if the AffineMap represents a symbol-less permutation map.
Definition: AffineMap.cpp:564
A symbolic identifier appearing in an affine expression.
Definition: AffineExpr.h:224
MLIRContext is the top-level object for a collection of MLIR operations.
Definition: MLIRContext.h:60
Include the generated interface declarations.
Definition: CallGraph.h:229
This header declares functions that assist transformations in the MemRef dialect.
AffineMap simplifyAffineMap(AffineMap map)
Simplifies an affine map by simplifying its underlying AffineExpr results.
Definition: AffineMap.cpp:661
inline ::llvm::hash_code hash_value(AffineMap arg)
Definition: AffineMap.h:380
AffineMap expandDimsToRank(AffineMap map, int64_t rank, const llvm::SmallBitVector &projectedDimensions)
Expand map to operate on rank dims while projecting out the dims in projectedDimensions.
Definition: AffineMap.cpp:842
AffineMap removeDuplicateExprs(AffineMap map)
Returns a map with the same dimension and symbol count as map, but whose results are the unique affin...
Definition: AffineMap.cpp:671
llvm::SmallBitVector getUnusedSymbolsBitVector(ArrayRef< AffineMap > maps)
Definition: AffineMap.cpp:829
SmallVector< T > applyPermutationMap(AffineMap map, llvm::ArrayRef< T > source)
Apply a permutation from map to source and return the result.
Definition: AffineMap.h:624
AffineMap inverseAndBroadcastProjectedPermutation(AffineMap map)
Return the reverse map of a projected permutation where the projected dimensions are transformed into...
Definition: AffineMap.cpp:704
AffineMap inversePermutation(AffineMap map)
Returns a map of codomain to domain dimensions such that the first codomain dimension for a particula...
Definition: AffineMap.cpp:680
AffineMap concatAffineMaps(ArrayRef< AffineMap > maps)
Concatenates a list of maps into a single AffineMap, stepping over potentially empty maps.
Definition: AffineMap.cpp:725
AffineMap compressSymbols(AffineMap map, const llvm::SmallBitVector &unusedSymbols)
Drop the symbols that are listed in unusedSymbols.
Definition: AffineMap.cpp:647
static void getMaxDimAndSymbol(ArrayRef< AffineExprContainer > exprsList, int64_t &maxDim, int64_t &maxSym)
Calculates maximum dimension and symbol positions from the expressions in exprsLists and stores them ...
Definition: AffineMap.h:646
AffineMap compressUnusedDims(AffineMap map)
Drop the dims that are not used.
Definition: AffineMap.cpp:638
AffineMap compressDims(AffineMap map, const llvm::SmallBitVector &unusedDims)
Drop the dims that are listed in unusedDims.
Definition: AffineMap.cpp:633
AffineMap getProjectedMap(AffineMap map, const llvm::SmallBitVector &projectedDimensions, bool compressDimsFlag=true, bool compressSymbolsFlag=true)
Calls projectDims(map, projectedDimensions, compressDimsFlag).
Definition: AffineMap.cpp:807
llvm::SmallBitVector getUnusedDimsBitVector(ArrayRef< AffineMap > maps)
Definition: AffineMap.cpp:817
inline ::llvm::hash_code hash_value(AffineExpr arg)
Make AffineExpr hashable.
Definition: AffineExpr.h:240
AffineMap projectDims(AffineMap map, const llvm::SmallBitVector &projectedDimensions, bool compressDimsFlag=false)
Returns the map that results from projecting out the dimensions specified in projectedDimensions.
Definition: AffineMap.cpp:793
AffineMap compressUnusedSymbols(AffineMap map)
Drop the symbols that are not used.
Definition: AffineMap.cpp:652
AffineMap projectSymbols(AffineMap map, const llvm::SmallBitVector &projectedSymbols, bool compressSymbolsFlag=false)
Symbol counterpart of projectDims.
Definition: AffineMap.cpp:800
raw_ostream & operator<<(raw_ostream &os, const AliasResult &result)
Definition: AliasAnalysis.h:78
static unsigned getHashValue(mlir::AffineMap val)
Definition: AffineMap.h:675
static mlir::AffineMap getEmptyKey()
Definition: AffineMap.h:667
static bool isEqual(mlir::AffineMap LHS, mlir::AffineMap RHS)
Definition: AffineMap.h:678
static mlir::AffineMap getTombstoneKey()
Definition: AffineMap.h:671
This class represents an efficient way to signal success or failure.
Definition: LogicalResult.h:26
A mutable affine map. Its affine expressions are however unique.
Definition: AffineMap.h:385
void setNumDims(unsigned d)
Definition: AffineMap.h:395
void reset(AffineMap map)
Resets this MutableAffineMap with 'map'.
Definition: AffineMap.cpp:858
void setResult(unsigned idx, AffineExpr result)
Definition: AffineMap.h:392
AffineMap getAffineMap() const
Get the AffineMap corresponding to this MutableAffineMap.
Definition: AffineMap.cpp:885
void setNumSymbols(unsigned d)
Definition: AffineMap.h:397
AffineExpr getResult(unsigned idx) const
Definition: AffineMap.h:391
unsigned getNumSymbols() const
Definition: AffineMap.h:396
ArrayRef< AffineExpr > getResults() const
Definition: AffineMap.h:390
bool isMultipleOf(unsigned idx, int64_t factor) const
Returns true if the idx'th result expression is a multiple of factor.
Definition: AffineMap.cpp:866
MLIRContext * getContext() const
Definition: AffineMap.h:398
unsigned getNumResults() const
Definition: AffineMap.h:393
unsigned getNumDims() const
Definition: AffineMap.h:394
void simplify()
Simplify the (result) expressions in this map using analysis (used by.
Definition: AffineMap.cpp:877