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