1//===- AffineValueMap.cpp - MLIR Affine Value Map Class -------------------===//
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/Dialect/Affine/IR/AffineValueMap.h"
10#include "mlir/Dialect/Affine/IR/AffineOps.h"
11
12using namespace mlir;
13using namespace mlir::affine;
14
15AffineValueMap::AffineValueMap(AffineMap map, ValueRange operands,
16 ValueRange results)
17 : map(map), operands(operands.begin(), operands.end()),
18 results(results.begin(), results.end()) {}
19
20void AffineValueMap::reset(AffineMap map, ValueRange operands,
21 ValueRange results) {
22 this->map.reset(map);
23 this->operands.assign(in_start: operands.begin(), in_end: operands.end());
24 this->results.assign(in_start: results.begin(), in_end: results.end());
25}
26
27void AffineValueMap::composeSimplifyAndCanonicalize() {
28 AffineMap sMap = getAffineMap();
29 fullyComposeAffineMapAndOperands(map: &sMap, operands: &operands);
30 // Full composition also canonicalizes and simplifies before returning. We
31 // need to canonicalize once more to drop unused operands.
32 canonicalizeMapAndOperands(map: &sMap, operands: &operands);
33 this->map.reset(map: sMap);
34}
35
36void AffineValueMap::combine(const AffineValueMap &a, const AffineValueMap &b,
37 AffineExpr expr, AffineValueMap *res,
38 bool pairwise) {
39 assert((!pairwise || a.getNumResults() == b.getNumResults()) &&
40 "matching by position requires equal result counts");
41 bool validExpr = true;
42 expr.walk(callback: [&](AffineExpr subExpr) {
43 if (auto dim = llvm::dyn_cast<AffineDimExpr>(Val&: subExpr))
44 validExpr &= dim.getPosition() < 2;
45 else if (llvm::isa<AffineSymbolExpr>(Val: subExpr))
46 validExpr = false;
47 });
48 assert(validExpr && "combining expression must use only d0 and d1");
49
50 SmallVector<Value, 4> allOperands;
51 allOperands.reserve(N: a.getNumOperands() + b.getNumOperands());
52 auto aDims = a.getOperands().take_front(N: a.getNumDims());
53 auto bDims = b.getOperands().take_front(N: b.getNumDims());
54 auto aSyms = a.getOperands().take_back(N: a.getNumSymbols());
55 auto bSyms = b.getOperands().take_back(N: b.getNumSymbols());
56 allOperands.append(in_start: aDims.begin(), in_end: aDims.end());
57 allOperands.append(in_start: bDims.begin(), in_end: bDims.end());
58 allOperands.append(in_start: aSyms.begin(), in_end: aSyms.end());
59 allOperands.append(in_start: bSyms.begin(), in_end: bSyms.end());
60
61 // Shift dims and symbols of b's map.
62 auto bMap = b.getAffineMap()
63 .shiftDims(shift: a.getNumDims())
64 .shiftSymbols(shift: a.getNumSymbols());
65
66 // Substitute each pair of results into the combining expression.
67 auto aMap = a.getAffineMap();
68 SmallVector<AffineExpr> resultExprs;
69 if (pairwise) {
70 resultExprs.reserve(N: a.getNumResults());
71 for (auto [aResult, bResult] :
72 llvm::zip_equal(t: aMap.getResults(), u: bMap.getResults())) {
73 AffineExpr replacements[] = {aResult, bResult};
74 resultExprs.push_back(Elt: expr.replaceDims(dimReplacements: replacements));
75 }
76 } else {
77 resultExprs.reserve(N: a.getNumResults() * b.getNumResults());
78 for (AffineExpr aResult : aMap.getResults())
79 for (AffineExpr bResult : bMap.getResults()) {
80 AffineExpr replacements[] = {aResult, bResult};
81 resultExprs.push_back(Elt: expr.replaceDims(dimReplacements: replacements));
82 }
83 }
84
85 auto resultMap = AffineMap::get(dimCount: bMap.getNumDims(), symbolCount: bMap.getNumSymbols(),
86 results: resultExprs, context: bMap.getContext());
87 fullyComposeAffineMapAndOperands(map: &resultMap, operands: &allOperands);
88 canonicalizeMapAndOperands(map: &resultMap, operands: &allOperands);
89 resultMap = simplifyAffineMap(map: resultMap);
90 res->reset(map: resultMap, operands: allOperands);
91}
92
93void AffineValueMap::difference(const AffineValueMap &a,
94 const AffineValueMap &b, AffineValueMap *res) {
95 MLIRContext *context = a.getAffineMap().getContext();
96 AffineExpr lhs = getAffineDimExpr(position: 0, context);
97 AffineExpr rhs = getAffineDimExpr(position: 1, context);
98 combine(a, b, expr: lhs - rhs, res);
99}
100
101void AffineValueMap::cartesianProductDifference(const AffineValueMap &a,
102 const AffineValueMap &b,
103 AffineValueMap *res) {
104 MLIRContext *context = a.getAffineMap().getContext();
105 AffineExpr lhs = getAffineDimExpr(position: 0, context);
106 AffineExpr rhs = getAffineDimExpr(position: 1, context);
107 combine(a, b, expr: lhs - rhs, res, /*pairwise=*/false);
108}
109
110// Returns true and sets 'indexOfMatch' if 'valueToMatch' is found in
111// 'valuesToSearch' beginning at 'indexStart'. Returns false otherwise.
112static bool findIndex(Value valueToMatch, ArrayRef<Value> valuesToSearch,
113 unsigned indexStart, unsigned *indexOfMatch) {
114 unsigned size = valuesToSearch.size();
115 for (unsigned i = indexStart; i < size; ++i) {
116 if (valueToMatch == valuesToSearch[i]) {
117 *indexOfMatch = i;
118 return true;
119 }
120 }
121 return false;
122}
123
124bool AffineValueMap::isMultipleOf(unsigned idx, int64_t factor) const {
125 return map.isMultipleOf(idx, factor);
126}
127
128/// This method uses the invariant that operands are always positionally aligned
129/// with the AffineDimExpr in the underlying AffineMap.
130bool AffineValueMap::isFunctionOf(unsigned idx, Value value) const {
131 unsigned index;
132 if (!findIndex(valueToMatch: value, valuesToSearch: operands, /*indexStart=*/0, indexOfMatch: &index)) {
133 return false;
134 }
135 auto expr = const_cast<AffineValueMap *>(this)->getAffineMap().getResult(idx);
136 // TODO: this is better implemented on a flattened representation.
137 // At least for now it is conservative.
138 return expr.isFunctionOfDim(position: index);
139}
140
141Value AffineValueMap::getOperand(unsigned i) const {
142 return static_cast<Value>(operands[i]);
143}
144
145ArrayRef<Value> AffineValueMap::getOperands() const {
146 return ArrayRef<Value>(operands);
147}
148
149AffineMap AffineValueMap::getAffineMap() const { return map.getAffineMap(); }
150
151bool AffineValueMap::operator==(const AffineValueMap &other) const {
152 if (getNumResults() != other.getNumResults())
153 return false;
154 AffineValueMap diff;
155 AffineValueMap::difference(a: *this, b: other, res: &diff);
156 return llvm::all_of(Range: diff.getAffineMap().getResults(), P: [](AffineExpr e) {
157 return e == getAffineConstantExpr(constant: 0, context: e.getContext());
158 });
159}
160
161AffineValueMap::~AffineValueMap() = default;
162