1//===- AffineMap.cpp - MLIR Affine Map Classes ----------------------------===//
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#include "mlir/IR/AffineMap.h"
10#include "AffineMapDetail.h"
11#include "mlir/IR/AffineExpr.h"
12#include "mlir/IR/Builders.h"
13#include "mlir/IR/BuiltinAttributes.h"
14#include "mlir/IR/BuiltinTypes.h"
15#include "llvm/ADT/STLExtras.h"
16#include "llvm/ADT/SmallBitVector.h"
17#include "llvm/ADT/SmallVector.h"
18#include "llvm/Support/MathExtras.h"
19#include <numeric>
20#include <optional>
21#include <type_traits>
22
23using namespace mlir;
24
25using llvm::divideCeilSigned;
26using llvm::divideFloorSigned;
27using llvm::divideSignedWouldOverflow;
28using llvm::mod;
29
30namespace {
31
32// AffineExprConstantFolder evaluates an affine expression using constant
33// operands passed in 'operandConsts'. Returns an IntegerAttr attribute
34// representing the constant value of the affine expression evaluated on
35// constant 'operandConsts', or nullptr if it can't be folded.
36class AffineExprConstantFolder {
37public:
38 AffineExprConstantFolder(unsigned numDims, ArrayRef<Attribute> operandConsts)
39 : numDims(numDims), operandConsts(operandConsts) {}
40
41 /// Attempt to constant fold the specified affine expr, or return null on
42 /// failure.
43 IntegerAttr constantFold(AffineExpr expr) {
44 if (auto result = constantFoldImpl(expr))
45 return IntegerAttr::get(type: IndexType::get(context: expr.getContext()), value: *result);
46 return nullptr;
47 }
48
49 bool hasPoison() const { return hasPoison_; }
50
51private:
52 std::optional<int64_t> constantFoldImpl(AffineExpr expr) {
53 switch (expr.getKind()) {
54 case AffineExprKind::Add:
55 return constantFoldBinExpr(
56 expr, op: [](int64_t lhs, int64_t rhs) -> std::optional<int64_t> {
57 int64_t sum;
58 if (llvm::AddOverflow(X: lhs, Y: rhs, Result&: sum))
59 return std::nullopt;
60 return sum;
61 });
62 case AffineExprKind::Mul:
63 return constantFoldBinExpr(
64 expr, op: [](int64_t lhs, int64_t rhs) -> std::optional<int64_t> {
65 int64_t product;
66 if (llvm::MulOverflow(X: lhs, Y: rhs, Result&: product))
67 return std::nullopt;
68 return product;
69 });
70 case AffineExprKind::Mod:
71 return constantFoldBinExpr(
72 expr, op: [this](int64_t lhs, int64_t rhs) -> std::optional<int64_t> {
73 if (rhs < 1) {
74 hasPoison_ = true;
75 return std::nullopt;
76 }
77 return mod(Numerator: lhs, Denominator: rhs);
78 });
79 case AffineExprKind::FloorDiv:
80 return constantFoldBinExpr(
81 expr, op: [this](int64_t lhs, int64_t rhs) -> std::optional<int64_t> {
82 if (rhs == 0) {
83 hasPoison_ = true;
84 return std::nullopt;
85 }
86 if (divideSignedWouldOverflow(Numerator: lhs, Denominator: rhs))
87 return std::nullopt;
88 return divideFloorSigned(Numerator: lhs, Denominator: rhs);
89 });
90 case AffineExprKind::CeilDiv:
91 return constantFoldBinExpr(
92 expr, op: [this](int64_t lhs, int64_t rhs) -> std::optional<int64_t> {
93 if (rhs == 0) {
94 hasPoison_ = true;
95 return std::nullopt;
96 }
97 if (divideSignedWouldOverflow(Numerator: lhs, Denominator: rhs))
98 return std::nullopt;
99 return divideCeilSigned(Numerator: lhs, Denominator: rhs);
100 });
101 case AffineExprKind::Constant:
102 return cast<AffineConstantExpr>(Val&: expr).getValue();
103 case AffineExprKind::DimId:
104 if (auto attr = llvm::dyn_cast_or_null<IntegerAttr>(
105 Val: operandConsts[cast<AffineDimExpr>(Val&: expr).getPosition()]))
106 return attr.getInt();
107 return std::nullopt;
108 case AffineExprKind::SymbolId:
109 if (auto attr = llvm::dyn_cast_or_null<IntegerAttr>(
110 Val: operandConsts[numDims +
111 cast<AffineSymbolExpr>(Val&: expr).getPosition()]))
112 return attr.getInt();
113 return std::nullopt;
114 }
115 llvm_unreachable("Unknown AffineExpr");
116 }
117
118 // TODO: Change these to operate on APInts too.
119 std::optional<int64_t> constantFoldBinExpr(
120 AffineExpr expr,
121 llvm::function_ref<std::optional<int64_t>(int64_t, int64_t)> op) {
122 auto binOpExpr = cast<AffineBinaryOpExpr>(Val&: expr);
123 if (auto lhs = constantFoldImpl(expr: binOpExpr.getLHS()))
124 if (auto rhs = constantFoldImpl(expr: binOpExpr.getRHS()))
125 return op(*lhs, *rhs);
126 return std::nullopt;
127 }
128
129 // The number of dimension operands in AffineMap containing this expression.
130 unsigned numDims;
131 // The constant valued operands used to evaluate this AffineExpr.
132 ArrayRef<Attribute> operandConsts;
133 bool hasPoison_{false};
134};
135
136} // namespace
137
138/// Returns a single constant result affine map.
139AffineMap AffineMap::getConstantMap(int64_t val, MLIRContext *context) {
140 return get(/*dimCount=*/0, /*symbolCount=*/0,
141 result: {getAffineConstantExpr(constant: val, context)});
142}
143
144/// Returns an identity affine map (d0, ..., dn) -> (dp, ..., dn) on the most
145/// minor dimensions.
146AffineMap AffineMap::getMinorIdentityMap(unsigned dims, unsigned results,
147 MLIRContext *context) {
148 assert(dims >= results && "Dimension mismatch");
149 auto id = AffineMap::getMultiDimIdentityMap(numDims: dims, context);
150 return AffineMap::get(dimCount: dims, symbolCount: 0, results: id.getResults().take_back(N: results), context);
151}
152
153AffineMap AffineMap::getFilteredIdentityMap(
154 MLIRContext *ctx, unsigned numDims,
155 llvm::function_ref<bool(AffineDimExpr)> keepDimFilter) {
156 auto identityMap = getMultiDimIdentityMap(numDims, context: ctx);
157
158 // Apply filter to results.
159 llvm::SmallBitVector dropDimResults(numDims);
160 for (auto [idx, resultExpr] : llvm::enumerate(First: identityMap.getResults()))
161 dropDimResults[idx] = !keepDimFilter(cast<AffineDimExpr>(Val: resultExpr));
162
163 return identityMap.dropResults(positions: dropDimResults);
164}
165
166bool AffineMap::isMinorIdentity() const {
167 return getNumDims() >= getNumResults() &&
168 *this ==
169 getMinorIdentityMap(dims: getNumDims(), results: getNumResults(), context: getContext());
170}
171
172SmallVector<unsigned> AffineMap::getBroadcastDims() const {
173 SmallVector<unsigned> broadcastedDims;
174 for (const auto &[resIdx, expr] : llvm::enumerate(First: getResults())) {
175 if (auto constExpr = dyn_cast<AffineConstantExpr>(Val: expr)) {
176 if (constExpr.getValue() != 0)
177 continue;
178 broadcastedDims.push_back(Elt: resIdx);
179 }
180 }
181
182 return broadcastedDims;
183}
184
185/// Returns true if this affine map is a minor identity up to broadcasted
186/// dimensions which are indicated by value 0 in the result.
187bool AffineMap::isMinorIdentityWithBroadcasting(
188 SmallVectorImpl<unsigned> *broadcastedDims) const {
189 if (broadcastedDims)
190 broadcastedDims->clear();
191 if (getNumDims() < getNumResults())
192 return false;
193 unsigned suffixStart = getNumDims() - getNumResults();
194 for (const auto &idxAndExpr : llvm::enumerate(First: getResults())) {
195 unsigned resIdx = idxAndExpr.index();
196 AffineExpr expr = idxAndExpr.value();
197 if (auto constExpr = dyn_cast<AffineConstantExpr>(Val&: expr)) {
198 // Each result may be either a constant 0 (broadcasted dimension).
199 if (constExpr.getValue() != 0)
200 return false;
201 if (broadcastedDims)
202 broadcastedDims->push_back(Elt: resIdx);
203 } else if (auto dimExpr = dyn_cast<AffineDimExpr>(Val&: expr)) {
204 // Or it may be the input dimension corresponding to this result position.
205 if (dimExpr.getPosition() != suffixStart + resIdx)
206 return false;
207 } else {
208 return false;
209 }
210 }
211 return true;
212}
213
214/// Return true if this affine map can be converted to a minor identity with
215/// broadcast by doing a permute. Return a permutation (there may be
216/// several) to apply to get to a minor identity with broadcasts.
217/// Ex:
218/// * (d0, d1, d2) -> (0, d1) maps to minor identity (d1, 0 = d2) with
219/// perm = [1, 0] and broadcast d2
220/// * (d0, d1, d2) -> (d0, 0) cannot be mapped to a minor identity by
221/// permutation + broadcast
222/// * (d0, d1, d2, d3) -> (0, d1, d3) maps to minor identity (d1, 0 = d2, d3)
223/// with perm = [1, 0, 2] and broadcast d2
224/// * (d0, d1) -> (d1, 0, 0, d0) maps to minor identity (d0, d1) with extra
225/// leading broadcat dimensions. The map returned would be (0, 0, d0, d1) with
226/// perm = [3, 0, 1, 2]
227bool AffineMap::isPermutationOfMinorIdentityWithBroadcasting(
228 SmallVectorImpl<unsigned> &permutedDims) const {
229 unsigned projectionStart =
230 getNumResults() < getNumInputs() ? getNumInputs() - getNumResults() : 0;
231 permutedDims.clear();
232 SmallVector<unsigned> broadcastDims;
233 permutedDims.resize(N: getNumResults(), NV: 0);
234 // If there are more results than input dimensions we want the new map to
235 // start with broadcast dimensions in order to be a minor identity with
236 // broadcasting.
237 unsigned leadingBroadcast =
238 getNumResults() > getNumInputs() ? getNumResults() - getNumInputs() : 0;
239 llvm::SmallBitVector dimFound(std::max(a: getNumInputs(), b: getNumResults()),
240 false);
241 for (const auto &idxAndExpr : llvm::enumerate(First: getResults())) {
242 unsigned resIdx = idxAndExpr.index();
243 AffineExpr expr = idxAndExpr.value();
244 // Each result may be either a constant 0 (broadcast dimension) or a
245 // dimension.
246 if (auto constExpr = dyn_cast<AffineConstantExpr>(Val&: expr)) {
247 if (constExpr.getValue() != 0)
248 return false;
249 broadcastDims.push_back(Elt: resIdx);
250 } else if (auto dimExpr = dyn_cast<AffineDimExpr>(Val&: expr)) {
251 if (dimExpr.getPosition() < projectionStart)
252 return false;
253 unsigned newPosition =
254 dimExpr.getPosition() - projectionStart + leadingBroadcast;
255 permutedDims[resIdx] = newPosition;
256 dimFound[newPosition] = true;
257 } else {
258 return false;
259 }
260 }
261 // Find a permuation for the broadcast dimension. Since they are broadcasted
262 // any valid permutation is acceptable. We just permute the dim into a slot
263 // without an existing dimension.
264 unsigned pos = 0;
265 for (auto dim : broadcastDims) {
266 while (pos < dimFound.size() && dimFound[pos]) {
267 pos++;
268 }
269 permutedDims[dim] = pos++;
270 }
271 return true;
272}
273
274/// Returns an AffineMap representing a permutation.
275AffineMap AffineMap::getPermutationMap(ArrayRef<unsigned> permutation,
276 MLIRContext *context) {
277 assert(!permutation.empty() &&
278 "Cannot create permutation map from empty permutation vector");
279 const auto *m = llvm::max_element(Range&: permutation);
280 auto permutationMap = getMultiDimMapWithTargets(numDims: *m + 1, targets: permutation, context);
281 assert(permutationMap.isPermutation() && "Invalid permutation vector");
282 return permutationMap;
283}
284AffineMap AffineMap::getPermutationMap(ArrayRef<int64_t> permutation,
285 MLIRContext *context) {
286 SmallVector<unsigned> perm = llvm::map_to_vector(
287 C&: permutation, F: [](int64_t i) { return static_cast<unsigned>(i); });
288 return AffineMap::getPermutationMap(permutation: perm, context);
289}
290
291AffineMap AffineMap::getMultiDimMapWithTargets(unsigned numDims,
292 ArrayRef<unsigned> targets,
293 MLIRContext *context) {
294 // Inline size chosen empirically based on compilation profiling.
295 // Profiled: 3.1M calls, avg=4.1+-3.7. N=8 covers ~86% of cases inline.
296 SmallVector<AffineExpr, 8> affExprs;
297 for (unsigned t : targets)
298 affExprs.push_back(Elt: getAffineDimExpr(position: t, context));
299 AffineMap result = AffineMap::get(/*dimCount=*/numDims, /*symbolCount=*/0,
300 results: affExprs, context);
301 return result;
302}
303
304/// Creates an affine map each for each list of AffineExpr's in `exprsList`
305/// while inferring the right number of dimensional and symbolic inputs needed
306/// based on the maximum dimensional and symbolic identifier appearing in the
307/// expressions.
308template <typename AffineExprContainer>
309static SmallVector<AffineMap, 4>
310inferFromExprList(ArrayRef<AffineExprContainer> exprsList,
311 MLIRContext *context) {
312 if (exprsList.empty())
313 return {};
314 int64_t maxDim = -1, maxSym = -1;
315 getMaxDimAndSymbol(exprsList, maxDim, maxSym);
316 SmallVector<AffineMap, 4> maps;
317 maps.reserve(N: exprsList.size());
318 for (const auto &exprs : exprsList)
319 maps.push_back(Elt: AffineMap::get(/*dimCount=*/maxDim + 1,
320 /*symbolCount=*/maxSym + 1, exprs, context));
321 return maps;
322}
323
324SmallVector<AffineMap, 4>
325AffineMap::inferFromExprList(ArrayRef<ArrayRef<AffineExpr>> exprsList,
326 MLIRContext *context) {
327 return ::inferFromExprList(exprsList, context);
328}
329
330SmallVector<AffineMap, 4>
331AffineMap::inferFromExprList(ArrayRef<SmallVector<AffineExpr, 4>> exprsList,
332 MLIRContext *context) {
333 return ::inferFromExprList(exprsList, context);
334}
335
336uint64_t AffineMap::getLargestKnownDivisorOfMapExprs() {
337 uint64_t gcd = 0;
338 for (AffineExpr resultExpr : getResults()) {
339 uint64_t thisGcd = resultExpr.getLargestKnownDivisor();
340 gcd = std::gcd(m: gcd, n: thisGcd);
341 }
342 if (gcd == 0)
343 gcd = std::numeric_limits<uint64_t>::max();
344 return gcd;
345}
346
347AffineMap AffineMap::getMultiDimIdentityMap(unsigned numDims,
348 MLIRContext *context) {
349 SmallVector<AffineExpr, 4> dimExprs;
350 dimExprs.reserve(N: numDims);
351 for (unsigned i = 0; i < numDims; ++i)
352 dimExprs.push_back(Elt: mlir::getAffineDimExpr(position: i, context));
353 return get(/*dimCount=*/numDims, /*symbolCount=*/0, results: dimExprs, context);
354}
355
356MLIRContext *AffineMap::getContext() const { return map->context; }
357
358bool AffineMap::isIdentity() const {
359 if (getNumDims() != getNumResults())
360 return false;
361 ArrayRef<AffineExpr> results = getResults();
362 for (unsigned i = 0, numDims = getNumDims(); i < numDims; ++i) {
363 auto expr = dyn_cast<AffineDimExpr>(Val: results[i]);
364 if (!expr || expr.getPosition() != i)
365 return false;
366 }
367 return true;
368}
369
370bool AffineMap::isSymbolIdentity() const {
371 if (getNumSymbols() != getNumResults())
372 return false;
373 ArrayRef<AffineExpr> results = getResults();
374 for (unsigned i = 0, numSymbols = getNumSymbols(); i < numSymbols; ++i) {
375 auto expr = dyn_cast<AffineDimExpr>(Val: results[i]);
376 if (!expr || expr.getPosition() != i)
377 return false;
378 }
379 return true;
380}
381
382bool AffineMap::isEmpty() const {
383 return getNumDims() == 0 && getNumSymbols() == 0 && getNumResults() == 0;
384}
385
386bool AffineMap::isSingleConstant() const {
387 return getNumResults() == 1 && isa<AffineConstantExpr>(Val: getResult(idx: 0));
388}
389
390bool AffineMap::isConstant() const {
391 return llvm::all_of(Range: getResults(), P: llvm::IsaPred<AffineConstantExpr>);
392}
393
394int64_t AffineMap::getSingleConstantResult() const {
395 assert(isSingleConstant() && "map must have a single constant result");
396 return cast<AffineConstantExpr>(Val: getResult(idx: 0)).getValue();
397}
398
399SmallVector<int64_t> AffineMap::getConstantResults() const {
400 assert(isConstant() && "map must have only constant results");
401 SmallVector<int64_t> result;
402 for (auto expr : getResults())
403 result.emplace_back(Args: cast<AffineConstantExpr>(Val&: expr).getValue());
404 return result;
405}
406
407unsigned AffineMap::getNumDims() const {
408 assert(map && "uninitialized map storage");
409 return map->numDims;
410}
411unsigned AffineMap::getNumSymbols() const {
412 assert(map && "uninitialized map storage");
413 return map->numSymbols;
414}
415unsigned AffineMap::getNumResults() const { return getResults().size(); }
416unsigned AffineMap::getNumInputs() const {
417 assert(map && "uninitialized map storage");
418 return map->numDims + map->numSymbols;
419}
420ArrayRef<AffineExpr> AffineMap::getResults() const {
421 assert(map && "uninitialized map storage");
422 return map->results();
423}
424AffineExpr AffineMap::getResult(unsigned idx) const {
425 return getResults()[idx];
426}
427
428unsigned AffineMap::getDimPosition(unsigned idx) const {
429 return cast<AffineDimExpr>(Val: getResult(idx)).getPosition();
430}
431
432std::optional<unsigned> AffineMap::getResultPosition(AffineExpr input) const {
433 if (!isa<AffineDimExpr>(Val: input))
434 return std::nullopt;
435
436 for (unsigned i = 0, numResults = getNumResults(); i < numResults; i++) {
437 if (getResult(idx: i) == input)
438 return i;
439 }
440
441 return std::nullopt;
442}
443
444/// Folds the results of the application of an affine map on the provided
445/// operands to a constant if possible. Returns false if the folding happens,
446/// true otherwise.
447LogicalResult AffineMap::constantFold(ArrayRef<Attribute> operandConstants,
448 SmallVectorImpl<Attribute> &results,
449 bool *hasPoison) const {
450 // Attempt partial folding.
451 SmallVector<int64_t, 2> integers;
452 partialConstantFold(operandConstants, results: &integers, hasPoison);
453
454 // If all expressions folded to a constant, populate results with attributes
455 // containing those constants.
456 if (integers.empty())
457 return failure();
458
459 auto range = llvm::map_range(C&: integers, F: [this](int64_t i) {
460 return IntegerAttr::get(type: IndexType::get(context: getContext()), value: i);
461 });
462 results.append(in_start: range.begin(), in_end: range.end());
463 return success();
464}
465
466AffineMap AffineMap::partialConstantFold(ArrayRef<Attribute> operandConstants,
467 SmallVectorImpl<int64_t> *results,
468 bool *hasPoison) const {
469 assert(getNumInputs() == operandConstants.size());
470
471 // Fold each of the result expressions.
472 AffineExprConstantFolder exprFolder(getNumDims(), operandConstants);
473 SmallVector<AffineExpr, 4> exprs;
474 exprs.reserve(N: getNumResults());
475
476 for (auto expr : getResults()) {
477 auto folded = exprFolder.constantFold(expr);
478 if (exprFolder.hasPoison() && hasPoison) {
479 *hasPoison = true;
480 return {};
481 }
482 // If did not fold to a constant, keep the original expression, and clear
483 // the integer results vector.
484 if (folded) {
485 exprs.push_back(
486 Elt: getAffineConstantExpr(constant: folded.getInt(), context: folded.getContext()));
487 if (results)
488 results->push_back(Elt: folded.getInt());
489 } else {
490 exprs.push_back(Elt: expr);
491 if (results) {
492 results->clear();
493 results = nullptr;
494 }
495 }
496 }
497
498 return get(dimCount: getNumDims(), symbolCount: getNumSymbols(), results: exprs, context: getContext());
499}
500
501/// Walk all of the AffineExpr's in this mapping. Each node in an expression
502/// tree is visited in postorder.
503void AffineMap::walkExprs(llvm::function_ref<void(AffineExpr)> callback) const {
504 for (auto expr : getResults())
505 expr.walk(callback);
506}
507
508/// This method substitutes any uses of dimensions and symbols (e.g.
509/// dim#0 with dimReplacements[0]) in subexpressions and returns the modified
510/// expression mapping. Because this can be used to eliminate dims and
511/// symbols, the client needs to specify the number of dims and symbols in
512/// the result. The returned map always has the same number of results.
513AffineMap AffineMap::replaceDimsAndSymbols(ArrayRef<AffineExpr> dimReplacements,
514 ArrayRef<AffineExpr> symReplacements,
515 unsigned numResultDims,
516 unsigned numResultSyms) const {
517 SmallVector<AffineExpr, 8> results;
518 results.reserve(N: getNumResults());
519 for (auto expr : getResults())
520 results.push_back(
521 Elt: expr.replaceDimsAndSymbols(dimReplacements, symReplacements));
522 return get(dimCount: numResultDims, symbolCount: numResultSyms, results, context: getContext());
523}
524
525/// Sparse replace method. Apply AffineExpr::replace(`expr`, `replacement`) to
526/// each of the results and return a new AffineMap with the new results and
527/// with the specified number of dims and symbols.
528AffineMap AffineMap::replace(AffineExpr expr, AffineExpr replacement,
529 unsigned numResultDims,
530 unsigned numResultSyms) const {
531 SmallVector<AffineExpr, 4> newResults;
532 newResults.reserve(N: getNumResults());
533 for (AffineExpr e : getResults())
534 newResults.push_back(Elt: e.replace(expr, replacement));
535 return AffineMap::get(dimCount: numResultDims, symbolCount: numResultSyms, results: newResults, context: getContext());
536}
537
538/// Sparse replace method. Apply AffineExpr::replace(`map`) to each of the
539/// results and return a new AffineMap with the new results and with the
540/// specified number of dims and symbols.
541AffineMap AffineMap::replace(const DenseMap<AffineExpr, AffineExpr> &map,
542 unsigned numResultDims,
543 unsigned numResultSyms) const {
544 SmallVector<AffineExpr, 4> newResults;
545 newResults.reserve(N: getNumResults());
546 for (AffineExpr e : getResults())
547 newResults.push_back(Elt: e.replace(map));
548 return AffineMap::get(dimCount: numResultDims, symbolCount: numResultSyms, results: newResults, context: getContext());
549}
550
551AffineMap
552AffineMap::replace(const DenseMap<AffineExpr, AffineExpr> &map) const {
553 SmallVector<AffineExpr, 4> newResults;
554 newResults.reserve(N: getNumResults());
555 for (AffineExpr e : getResults())
556 newResults.push_back(Elt: e.replace(map));
557 return AffineMap::inferFromExprList(exprsList: newResults, context: getContext()).front();
558}
559
560AffineMap AffineMap::dropResults(const llvm::SmallBitVector &positions) const {
561 auto exprs = llvm::to_vector<4>(Range: getResults());
562 // TODO: this is a pretty terrible API .. is there anything better?
563 for (auto pos = positions.find_last(); pos != -1;
564 pos = positions.find_prev(PriorTo: pos))
565 exprs.erase(CI: exprs.begin() + pos);
566 return AffineMap::get(dimCount: getNumDims(), symbolCount: getNumSymbols(), results: exprs, context: getContext());
567}
568
569AffineMap AffineMap::compose(AffineMap map) const {
570 assert(getNumDims() == map.getNumResults() && "Number of results mismatch");
571 // Prepare `map` by concatenating the symbols and rewriting its exprs.
572 unsigned numDims = map.getNumDims();
573 unsigned numSymbolsThisMap = getNumSymbols();
574 unsigned numSymbols = numSymbolsThisMap + map.getNumSymbols();
575 SmallVector<AffineExpr, 8> newDims(numDims);
576 for (unsigned idx = 0; idx < numDims; ++idx) {
577 newDims[idx] = getAffineDimExpr(position: idx, context: getContext());
578 }
579 SmallVector<AffineExpr, 8> newSymbols(numSymbols - numSymbolsThisMap);
580 for (unsigned idx = numSymbolsThisMap; idx < numSymbols; ++idx) {
581 newSymbols[idx - numSymbolsThisMap] =
582 getAffineSymbolExpr(position: idx, context: getContext());
583 }
584 auto newMap =
585 map.replaceDimsAndSymbols(dimReplacements: newDims, symReplacements: newSymbols, numResultDims: numDims, numResultSyms: numSymbols);
586 SmallVector<AffineExpr, 8> exprs;
587 exprs.reserve(N: getResults().size());
588 for (auto expr : getResults())
589 exprs.push_back(Elt: expr.compose(map: newMap));
590 return AffineMap::get(dimCount: numDims, symbolCount: numSymbols, results: exprs, context: map.getContext());
591}
592
593// Inline size chosen empirically based on compilation profiling.
594// Profiled: 43.5M calls, avg=3.1+-2.3. N=8 covers ~98% of cases inline.
595SmallVector<int64_t, 8> AffineMap::compose(ArrayRef<int64_t> values) const {
596 assert(getNumSymbols() == 0 && "Expected symbol-less map");
597 SmallVector<AffineExpr, 8> exprs;
598 MLIRContext *ctx = getContext();
599 for (int64_t value : values)
600 exprs.push_back(Elt: getAffineConstantExpr(constant: value, context: ctx));
601 SmallVector<int64_t, 8> res;
602 res.reserve(N: getNumResults());
603 for (auto e : getResults())
604 res.push_back(Elt: cast<AffineConstantExpr>(Val: e.replaceDims(dimReplacements: exprs)).getValue());
605 return res;
606}
607
608size_t AffineMap::getNumOfZeroResults() const {
609 size_t res = 0;
610 for (auto expr : getResults()) {
611 auto constExpr = dyn_cast<AffineConstantExpr>(Val&: expr);
612 if (constExpr && constExpr.getValue() == 0)
613 res++;
614 }
615
616 return res;
617}
618
619AffineMap AffineMap::dropZeroResults() {
620 SmallVector<AffineExpr> newExprs;
621
622 for (auto expr : getResults()) {
623 auto constExpr = dyn_cast<AffineConstantExpr>(Val&: expr);
624 if (!constExpr || constExpr.getValue() != 0)
625 newExprs.push_back(Elt: expr);
626 }
627 return AffineMap::get(dimCount: getNumDims(), symbolCount: getNumSymbols(), results: newExprs, context: getContext());
628}
629
630bool AffineMap::isProjectedPermutation(bool allowZeroInResults) const {
631 if (getNumSymbols() > 0)
632 return false;
633
634 // Having more results than inputs means that results have duplicated dims or
635 // zeros that can't be mapped to input dims.
636 if (getNumResults() > getNumInputs())
637 return false;
638
639 SmallVector<bool, 8> seen(getNumInputs(), false);
640 // A projected permutation can have, at most, only one instance of each input
641 // dimension in the result expressions. Zeros are allowed as long as the
642 // number of result expressions is lower or equal than the number of input
643 // expressions.
644 for (auto expr : getResults()) {
645 if (auto dim = dyn_cast<AffineDimExpr>(Val&: expr)) {
646 if (seen[dim.getPosition()])
647 return false;
648 seen[dim.getPosition()] = true;
649 } else {
650 auto constExpr = dyn_cast<AffineConstantExpr>(Val&: expr);
651 if (!allowZeroInResults || !constExpr || constExpr.getValue() != 0)
652 return false;
653 }
654 }
655
656 // Results are either dims or zeros and zeros can be mapped to input dims.
657 return true;
658}
659
660bool AffineMap::isPermutation() const {
661 if (getNumDims() != getNumResults())
662 return false;
663 return isProjectedPermutation();
664}
665
666AffineMap AffineMap::getSubMap(ArrayRef<unsigned> resultPos) const {
667 SmallVector<AffineExpr, 4> exprs;
668 exprs.reserve(N: resultPos.size());
669 for (auto idx : resultPos)
670 exprs.push_back(Elt: getResult(idx));
671 return AffineMap::get(dimCount: getNumDims(), symbolCount: getNumSymbols(), results: exprs, context: getContext());
672}
673
674AffineMap AffineMap::getSliceMap(unsigned start, unsigned length) const {
675 return AffineMap::get(dimCount: getNumDims(), symbolCount: getNumSymbols(),
676 results: getResults().slice(N: start, M: length), context: getContext());
677}
678
679AffineMap AffineMap::getMajorSubMap(unsigned numResults) const {
680 if (numResults == 0)
681 return AffineMap();
682 if (numResults > getNumResults())
683 return *this;
684 return getSliceMap(start: 0, length: numResults);
685}
686
687AffineMap AffineMap::getMinorSubMap(unsigned numResults) const {
688 if (numResults == 0)
689 return AffineMap();
690 if (numResults > getNumResults())
691 return *this;
692 return getSliceMap(start: getNumResults() - numResults, length: numResults);
693}
694
695/// Implementation detail to compress multiple affine maps with a compressionFun
696/// that is expected to be either compressUnusedDims or compressUnusedSymbols.
697/// The implementation keeps track of num dims and symbols across the different
698/// affine maps.
699static SmallVector<AffineMap> compressUnusedListImpl(
700 ArrayRef<AffineMap> maps,
701 llvm::function_ref<AffineMap(AffineMap)> compressionFun) {
702 if (maps.empty())
703 return SmallVector<AffineMap>();
704 SmallVector<AffineExpr> allExprs;
705 allExprs.reserve(N: maps.size() * maps.front().getNumResults());
706 unsigned numDims = maps.front().getNumDims(),
707 numSymbols = maps.front().getNumSymbols();
708 for (auto m : maps) {
709 assert(numDims == m.getNumDims() && numSymbols == m.getNumSymbols() &&
710 "expected maps with same num dims and symbols");
711 llvm::append_range(C&: allExprs, R: m.getResults());
712 }
713 AffineMap unifiedMap = compressionFun(
714 AffineMap::get(dimCount: numDims, symbolCount: numSymbols, results: allExprs, context: maps.front().getContext()));
715 unsigned unifiedNumDims = unifiedMap.getNumDims(),
716 unifiedNumSymbols = unifiedMap.getNumSymbols();
717 ArrayRef<AffineExpr> unifiedResults = unifiedMap.getResults();
718 SmallVector<AffineMap> res;
719 res.reserve(N: maps.size());
720 for (auto m : maps) {
721 res.push_back(Elt: AffineMap::get(dimCount: unifiedNumDims, symbolCount: unifiedNumSymbols,
722 results: unifiedResults.take_front(N: m.getNumResults()),
723 context: m.getContext()));
724 unifiedResults = unifiedResults.drop_front(N: m.getNumResults());
725 }
726 return res;
727}
728
729AffineMap mlir::compressDims(AffineMap map,
730 const llvm::SmallBitVector &unusedDims) {
731 return projectDims(map, projectedDimensions: unusedDims, /*compressDimsFlag=*/true);
732}
733
734AffineMap mlir::compressUnusedDims(AffineMap map) {
735 return compressDims(map, unusedDims: getUnusedDimsBitVector(maps: {map}));
736}
737
738SmallVector<AffineMap> mlir::compressUnusedDims(ArrayRef<AffineMap> maps) {
739 return compressUnusedListImpl(
740 maps, compressionFun: [](AffineMap m) { return compressUnusedDims(map: m); });
741}
742
743AffineMap mlir::compressSymbols(AffineMap map,
744 const llvm::SmallBitVector &unusedSymbols) {
745 return projectSymbols(map, projectedSymbols: unusedSymbols, /*compressSymbolsFlag=*/true);
746}
747
748AffineMap mlir::compressUnusedSymbols(AffineMap map) {
749 return compressSymbols(map, unusedSymbols: getUnusedSymbolsBitVector(maps: {map}));
750}
751
752SmallVector<AffineMap> mlir::compressUnusedSymbols(ArrayRef<AffineMap> maps) {
753 return compressUnusedListImpl(
754 maps, compressionFun: [](AffineMap m) { return compressUnusedSymbols(map: m); });
755}
756
757AffineMap mlir::foldAttributesIntoMap(Builder &b, AffineMap map,
758 ArrayRef<OpFoldResult> operands,
759 SmallVector<Value> &remainingValues) {
760 SmallVector<AffineExpr> dimReplacements, symReplacements;
761 int64_t numDims = 0;
762 for (int64_t i = 0; i < map.getNumDims(); ++i) {
763 if (auto attr = dyn_cast<Attribute>(Val: operands[i])) {
764 dimReplacements.push_back(
765 Elt: b.getAffineConstantExpr(constant: cast<IntegerAttr>(Val&: attr).getInt()));
766 } else {
767 dimReplacements.push_back(Elt: b.getAffineDimExpr(position: numDims++));
768 remainingValues.push_back(Elt: cast<Value>(Val: operands[i]));
769 }
770 }
771 int64_t numSymbols = 0;
772 for (int64_t i = 0; i < map.getNumSymbols(); ++i) {
773 if (auto attr = dyn_cast<Attribute>(Val: operands[i + map.getNumDims()])) {
774 symReplacements.push_back(
775 Elt: b.getAffineConstantExpr(constant: cast<IntegerAttr>(Val&: attr).getInt()));
776 } else {
777 symReplacements.push_back(Elt: b.getAffineSymbolExpr(position: numSymbols++));
778 remainingValues.push_back(Elt: cast<Value>(Val: operands[i + map.getNumDims()]));
779 }
780 }
781 return map.replaceDimsAndSymbols(dimReplacements, symReplacements, numResultDims: numDims,
782 numResultSyms: numSymbols);
783}
784
785AffineMap mlir::simplifyAffineMap(AffineMap map) {
786 SmallVector<AffineExpr, 8> exprs;
787 for (auto e : map.getResults()) {
788 exprs.push_back(
789 Elt: simplifyAffineExpr(expr: e, numDims: map.getNumDims(), numSymbols: map.getNumSymbols()));
790 }
791 return AffineMap::get(dimCount: map.getNumDims(), symbolCount: map.getNumSymbols(), results: exprs,
792 context: map.getContext());
793}
794
795AffineMap mlir::removeDuplicateExprs(AffineMap map) {
796 auto results = map.getResults();
797 SmallVector<AffineExpr, 4> uniqueExprs(results);
798 uniqueExprs.erase(CS: llvm::unique(R&: uniqueExprs), CE: uniqueExprs.end());
799 return AffineMap::get(dimCount: map.getNumDims(), symbolCount: map.getNumSymbols(), results: uniqueExprs,
800 context: map.getContext());
801}
802
803AffineMap mlir::inversePermutation(AffineMap map) {
804 if (map.isEmpty())
805 return map;
806 assert(map.getNumSymbols() == 0 && "expected map without symbols");
807 SmallVector<AffineExpr, 4> exprs(map.getNumDims());
808 for (const auto &en : llvm::enumerate(First: map.getResults())) {
809 auto expr = en.value();
810 // Skip non-permutations.
811 if (auto d = dyn_cast<AffineDimExpr>(Val&: expr)) {
812 if (exprs[d.getPosition()])
813 continue;
814 exprs[d.getPosition()] = getAffineDimExpr(position: en.index(), context: d.getContext());
815 }
816 }
817 SmallVector<AffineExpr, 4> seenExprs;
818 seenExprs.reserve(N: map.getNumDims());
819 for (auto expr : exprs)
820 if (expr)
821 seenExprs.push_back(Elt: expr);
822 if (seenExprs.size() != map.getNumInputs())
823 return AffineMap();
824 return AffineMap::get(dimCount: map.getNumResults(), symbolCount: 0, results: seenExprs, context: map.getContext());
825}
826
827AffineMap mlir::inverseAndBroadcastProjectedPermutation(AffineMap map) {
828 assert(map.isProjectedPermutation(/*allowZeroInResults=*/true));
829 MLIRContext *context = map.getContext();
830 AffineExpr zero = mlir::getAffineConstantExpr(constant: 0, context);
831 // Start with all the results as 0.
832 SmallVector<AffineExpr, 4> exprs(map.getNumInputs(), zero);
833 for (unsigned i : llvm::seq(Begin: unsigned(0), End: map.getNumResults())) {
834 // Skip zeros from input map. 'exprs' is already initialized to zero.
835 if (auto constExpr = dyn_cast<AffineConstantExpr>(Val: map.getResult(idx: i))) {
836 assert(constExpr.getValue() == 0 &&
837 "Unexpected constant in projected permutation");
838 (void)constExpr;
839 continue;
840 }
841
842 // Reverse each dimension existing in the original map result.
843 exprs[map.getDimPosition(idx: i)] = getAffineDimExpr(position: i, context);
844 }
845 return AffineMap::get(dimCount: map.getNumResults(), /*symbolCount=*/0, results: exprs, context);
846}
847
848AffineMap mlir::concatAffineMaps(ArrayRef<AffineMap> maps,
849 MLIRContext *context) {
850 if (maps.empty())
851 return AffineMap::get(context);
852 unsigned numResults = 0, numDims = 0, numSymbols = 0;
853 for (auto m : maps)
854 numResults += m.getNumResults();
855 SmallVector<AffineExpr, 8> results;
856 results.reserve(N: numResults);
857 for (auto m : maps) {
858 for (auto res : m.getResults())
859 results.push_back(Elt: res.shiftSymbols(numSymbols: m.getNumSymbols(), shift: numSymbols));
860
861 numSymbols += m.getNumSymbols();
862 numDims = std::max(a: m.getNumDims(), b: numDims);
863 }
864 return AffineMap::get(dimCount: numDims, symbolCount: numSymbols, results, context);
865}
866
867/// Common implementation to project out dimensions or symbols from an affine
868/// map based on the template type.
869/// Additionally, if 'compress' is true, the projected out dimensions or symbols
870/// are also dropped from the resulting map.
871template <typename AffineDimOrSymExpr>
872static AffineMap projectCommonImpl(AffineMap map,
873 const llvm::SmallBitVector &toProject,
874 bool compress) {
875 static_assert(llvm::is_one_of<AffineDimOrSymExpr, AffineDimExpr,
876 AffineSymbolExpr>::value,
877 "expected AffineDimExpr or AffineSymbolExpr");
878
879 constexpr bool isDim = std::is_same<AffineDimOrSymExpr, AffineDimExpr>::value;
880 int64_t numDimOrSym = (isDim) ? map.getNumDims() : map.getNumSymbols();
881 SmallVector<AffineExpr> replacements;
882 replacements.reserve(N: numDimOrSym);
883
884 auto createNewDimOrSym = (isDim) ? getAffineDimExpr : getAffineSymbolExpr;
885
886 using replace_fn_ty =
887 std::function<AffineExpr(AffineExpr, ArrayRef<AffineExpr>)>;
888 replace_fn_ty replaceDims = [](AffineExpr e,
889 ArrayRef<AffineExpr> replacements) {
890 return e.replaceDims(dimReplacements: replacements);
891 };
892 replace_fn_ty replaceSymbols = [](AffineExpr e,
893 ArrayRef<AffineExpr> replacements) {
894 return e.replaceSymbols(symReplacements: replacements);
895 };
896 replace_fn_ty replaceNewDimOrSym = (isDim) ? replaceDims : replaceSymbols;
897
898 MLIRContext *context = map.getContext();
899 int64_t newNumDimOrSym = 0;
900 for (unsigned dimOrSym = 0; dimOrSym < numDimOrSym; ++dimOrSym) {
901 if (toProject.test(Idx: dimOrSym)) {
902 replacements.push_back(Elt: getAffineConstantExpr(constant: 0, context));
903 continue;
904 }
905 int64_t newPos = compress ? newNumDimOrSym++ : dimOrSym;
906 replacements.push_back(Elt: createNewDimOrSym(newPos, context));
907 }
908 SmallVector<AffineExpr> resultExprs;
909 resultExprs.reserve(N: map.getNumResults());
910 for (auto e : map.getResults())
911 resultExprs.push_back(Elt: replaceNewDimOrSym(e, replacements));
912
913 int64_t numDims = (compress && isDim) ? newNumDimOrSym : map.getNumDims();
914 int64_t numSyms = (compress && !isDim) ? newNumDimOrSym : map.getNumSymbols();
915 return AffineMap::get(dimCount: numDims, symbolCount: numSyms, results: resultExprs, context);
916}
917
918AffineMap mlir::projectDims(AffineMap map,
919 const llvm::SmallBitVector &projectedDimensions,
920 bool compressDimsFlag) {
921 return projectCommonImpl<AffineDimExpr>(map, toProject: projectedDimensions,
922 compress: compressDimsFlag);
923}
924
925AffineMap mlir::projectSymbols(AffineMap map,
926 const llvm::SmallBitVector &projectedSymbols,
927 bool compressSymbolsFlag) {
928 return projectCommonImpl<AffineSymbolExpr>(map, toProject: projectedSymbols,
929 compress: compressSymbolsFlag);
930}
931
932AffineMap mlir::getProjectedMap(AffineMap map,
933 const llvm::SmallBitVector &projectedDimensions,
934 bool compressDimsFlag,
935 bool compressSymbolsFlag) {
936 map = projectDims(map, projectedDimensions, compressDimsFlag);
937 if (compressSymbolsFlag)
938 map = compressUnusedSymbols(map);
939 return map;
940}
941
942llvm::SmallBitVector mlir::getUnusedDimsBitVector(ArrayRef<AffineMap> maps) {
943 unsigned numDims = maps[0].getNumDims();
944 llvm::SmallBitVector numDimsBitVector(numDims, true);
945 for (AffineMap m : maps) {
946 for (unsigned i = 0; i < numDims; ++i) {
947 if (m.isFunctionOfDim(position: i))
948 numDimsBitVector.reset(Idx: i);
949 }
950 }
951 return numDimsBitVector;
952}
953
954llvm::SmallBitVector mlir::getUnusedSymbolsBitVector(ArrayRef<AffineMap> maps) {
955 unsigned numSymbols = maps[0].getNumSymbols();
956 llvm::SmallBitVector numSymbolsBitVector(numSymbols, true);
957 for (AffineMap m : maps) {
958 for (unsigned i = 0; i < numSymbols; ++i) {
959 if (m.isFunctionOfSymbol(position: i))
960 numSymbolsBitVector.reset(Idx: i);
961 }
962 }
963 return numSymbolsBitVector;
964}
965
966AffineMap
967mlir::expandDimsToRank(AffineMap map, int64_t rank,
968 const llvm::SmallBitVector &projectedDimensions) {
969 auto id = AffineMap::getMultiDimIdentityMap(numDims: rank, context: map.getContext());
970 AffineMap proj = id.dropResults(positions: projectedDimensions);
971 return map.compose(map: proj);
972}
973
974//===----------------------------------------------------------------------===//
975// MutableAffineMap.
976//===----------------------------------------------------------------------===//
977
978MutableAffineMap::MutableAffineMap(AffineMap map)
979 : results(map.getResults()), numDims(map.getNumDims()),
980 numSymbols(map.getNumSymbols()), context(map.getContext()) {}
981
982void MutableAffineMap::reset(AffineMap map) {
983 results.clear();
984 numDims = map.getNumDims();
985 numSymbols = map.getNumSymbols();
986 context = map.getContext();
987 llvm::append_range(C&: results, R: map.getResults());
988}
989
990bool MutableAffineMap::isMultipleOf(unsigned idx, int64_t factor) const {
991 return results[idx].isMultipleOf(factor);
992}
993
994// Simplifies the result affine expressions of this map. The expressions
995// have to be pure for the simplification implemented.
996void MutableAffineMap::simplify() {
997 // Simplify each of the results if possible.
998 // TODO: functional-style map
999 for (unsigned i = 0, e = getNumResults(); i < e; i++) {
1000 results[i] = simplifyAffineExpr(expr: getResult(idx: i), numDims, numSymbols);
1001 }
1002}
1003
1004AffineMap MutableAffineMap::getAffineMap() const {
1005 return AffineMap::get(dimCount: numDims, symbolCount: numSymbols, results, context);
1006}
1007