1//===- AffineExpandIndexOps.cpp - Affine expand index ops pass ------------===//
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// This file implements a pass to expand affine index ops into one or more more
10// fundamental operations.
11//===----------------------------------------------------------------------===//
12
13#include "mlir/Dialect/Affine/LoopUtils.h"
14#include "mlir/Dialect/Affine/Transforms/Passes.h"
15
16#include "mlir/Dialect/Affine/IR/AffineOps.h"
17#include "mlir/Dialect/Affine/Transforms/Transforms.h"
18#include "mlir/Dialect/Arith/IR/Arith.h"
19#include "mlir/Dialect/Vector/IR/VectorOps.h"
20#include "mlir/Transforms/GreedyPatternRewriteDriver.h"
21
22namespace mlir {
23namespace affine {
24#define GEN_PASS_DEF_AFFINEEXPANDINDEXOPS
25#include "mlir/Dialect/Affine/Transforms/Passes.h.inc"
26} // namespace affine
27} // namespace mlir
28
29using namespace mlir;
30using namespace mlir::affine;
31
32/// Given a basis (in static and dynamic components), return the sequence of
33/// suffix products of the basis, including the product of the entire basis,
34/// which must **not** contain an outer bound.
35///
36/// If excess dynamic values are provided, the values at the beginning
37/// will be ignored. This allows for dropping the outer bound without
38/// needing to manipulate the dynamic value array. `knownPositive`
39/// indicases that the values being used to compute the strides are known
40/// to be non-negative.
41static SmallVector<Value> computeStrides(Location loc, RewriterBase &rewriter,
42 ValueRange dynamicBasis,
43 ArrayRef<int64_t> staticBasis,
44 bool knownNonNegative) {
45 if (staticBasis.empty())
46 return {};
47
48 SmallVector<Value> result;
49 result.reserve(N: staticBasis.size());
50 size_t dynamicIndex = dynamicBasis.size();
51 Value dynamicPart = nullptr;
52 int64_t staticPart = 1;
53 // The products of the strides can't have overflow by definition of
54 // affine.*_index.
55 arith::IntegerOverflowFlags ovflags = arith::IntegerOverflowFlags::nsw;
56 if (knownNonNegative)
57 ovflags = ovflags | arith::IntegerOverflowFlags::nuw;
58 for (int64_t elem : llvm::reverse(C&: staticBasis)) {
59 if (ShapedType::isDynamic(dValue: elem)) {
60 // Note: basis elements and their products are, definitionally,
61 // non-negative, so `nuw` is justified.
62 if (dynamicPart)
63 dynamicPart =
64 arith::MulIOp::create(builder&: rewriter, location: loc, lhs: dynamicPart,
65 rhs: dynamicBasis[dynamicIndex - 1], overflowFlags: ovflags);
66 else
67 dynamicPart = dynamicBasis[dynamicIndex - 1];
68 --dynamicIndex;
69 } else {
70 staticPart *= elem;
71 }
72
73 if (dynamicPart && staticPart == 1) {
74 result.push_back(Elt: dynamicPart);
75 } else {
76 Value stride =
77 rewriter.createOrFold<arith::ConstantIndexOp>(location: loc, args&: staticPart);
78 if (dynamicPart)
79 stride =
80 arith::MulIOp::create(builder&: rewriter, location: loc, lhs: dynamicPart, rhs: stride, overflowFlags: ovflags);
81 result.push_back(Elt: stride);
82 }
83 }
84 std::reverse(first: result.begin(), last: result.end());
85 return result;
86}
87
88/// Broadcast a scalar value to match the given type. If the type is already
89/// scalar, returns the value as-is. For vector types, uses vector.broadcast.
90static Value broadcastToMatchType(RewriterBase &rewriter, Location loc,
91 Value value, Type targetType) {
92 if (value.getType() == targetType)
93 return value;
94 return vector::BroadcastOp::create(builder&: rewriter, location: loc, result: targetType, source: value);
95}
96
97LogicalResult
98affine::lowerAffineDelinearizeIndexOp(RewriterBase &rewriter,
99 AffineDelinearizeIndexOp op) {
100 Location loc = op.getLoc();
101 Value linearIdx = op.getLinearIndex();
102 unsigned numResults = op.getNumResults();
103 ArrayRef<int64_t> staticBasis = op.getStaticBasis();
104 if (numResults == staticBasis.size())
105 staticBasis = staticBasis.drop_front();
106
107 if (numResults == 1) {
108 rewriter.replaceOp(op, newValues: linearIdx);
109 return success();
110 }
111
112 SmallVector<Value> results;
113 results.reserve(N: numResults);
114 SmallVector<Value> strides =
115 computeStrides(loc, rewriter, dynamicBasis: op.getDynamicBasis(), staticBasis,
116 /*knownNonNegative=*/true);
117
118 // Broadcast strides and zero to match the linear index type (needed for
119 // vector types where the strides are scalar but the index is a vector).
120 Type indexType = linearIdx.getType();
121 for (Value &stride : strides)
122 stride = broadcastToMatchType(rewriter, loc, value: stride, targetType: indexType);
123
124 Value zero =
125 arith::ConstantOp::create(builder&: rewriter, location: loc, value: rewriter.getZeroAttr(type: indexType));
126
127 Value initialPart =
128 arith::FloorDivSIOp::create(builder&: rewriter, location: loc, lhs: linearIdx, rhs: strides.front());
129 results.push_back(Elt: initialPart);
130
131 auto emitModTerm = [&](Value stride) -> Value {
132 Value remainder = arith::RemSIOp::create(builder&: rewriter, location: loc, lhs: linearIdx, rhs: stride);
133 Value remainderNegative = arith::CmpIOp::create(
134 builder&: rewriter, location: loc, predicate: arith::CmpIPredicate::slt, lhs: remainder, rhs: zero);
135 // If the correction is relevant, this term is <= stride, which is known
136 // to be positive in `index`. Otherwise, while 2 * stride might overflow,
137 // this branch won't be taken, so the risk of `poison` is fine.
138 Value corrected = arith::AddIOp::create(builder&: rewriter, location: loc, lhs: remainder, rhs: stride,
139 overflowFlags: arith::IntegerOverflowFlags::nsw);
140 Value mod = arith::SelectOp::create(builder&: rewriter, location: loc, condition: remainderNegative,
141 true_value: corrected, false_value: remainder);
142 return mod;
143 };
144
145 // Generate all the intermediate parts
146 for (size_t i = 0, e = strides.size() - 1; i < e; ++i) {
147 Value thisStride = strides[i];
148 Value nextStride = strides[i + 1];
149 Value modulus = emitModTerm(thisStride);
150 // We know both inputs are positive, so floorDiv == div.
151 // This could potentially be a divui, but it's not clear if that would
152 // cause issues.
153 Value divided = arith::DivSIOp::create(builder&: rewriter, location: loc, lhs: modulus, rhs: nextStride);
154 results.push_back(Elt: divided);
155 }
156
157 results.push_back(Elt: emitModTerm(strides.back()));
158
159 rewriter.replaceOp(op, newValues: results);
160 return success();
161}
162
163LogicalResult affine::lowerAffineLinearizeIndexOp(RewriterBase &rewriter,
164 AffineLinearizeIndexOp op) {
165 // Should be folded away, included here for safety.
166 if (op.getMultiIndex().empty()) {
167 rewriter.replaceOpWithNewOp<arith::ConstantOp>(
168 op, args: rewriter.getZeroAttr(type: op.getLinearIndex().getType()));
169 return success();
170 }
171
172 Location loc = op.getLoc();
173 ValueRange multiIndex = op.getMultiIndex();
174 Type indexType = op.getLinearIndex().getType();
175 size_t numIndexes = multiIndex.size();
176 ArrayRef<int64_t> staticBasis = op.getStaticBasis();
177 if (numIndexes == staticBasis.size())
178 staticBasis = staticBasis.drop_front();
179
180 SmallVector<Value> strides =
181 computeStrides(loc, rewriter, dynamicBasis: op.getDynamicBasis(), staticBasis,
182 /*knownNonNegative=*/op.getDisjoint());
183
184 // Broadcast strides to match the index type (needed for vector types).
185 for (Value &stride : strides)
186 stride = broadcastToMatchType(rewriter, loc, value: stride, targetType: indexType);
187
188 SmallVector<std::pair<Value, int64_t>> scaledValues;
189 scaledValues.reserve(N: numIndexes);
190
191 // Note: strides doesn't contain a value for the final element (stride 1)
192 // and everything else lines up. We use the "mutable" accessor so we can get
193 // our hands on an `OpOperand&` for the loop invariant counting function.
194 for (auto [stride, idxOp] :
195 llvm::zip_equal(t&: strides, u: llvm::drop_end(RangeOrContainer: op.getMultiIndexMutable()))) {
196 Value scaledIdx = arith::MulIOp::create(builder&: rewriter, location: loc, lhs: idxOp.get(), rhs: stride,
197 overflowFlags: arith::IntegerOverflowFlags::nsw);
198 int64_t numHoistableLoops = numEnclosingInvariantLoops(operand&: idxOp);
199 scaledValues.emplace_back(Args&: scaledIdx, Args&: numHoistableLoops);
200 }
201 scaledValues.emplace_back(
202 Args: multiIndex.back(),
203 Args: numEnclosingInvariantLoops(operand&: op.getMultiIndexMutable()[numIndexes - 1]));
204
205 // Sort by how many enclosing loops there are, ties implicitly broken by
206 // size of the stride.
207 llvm::stable_sort(Range&: scaledValues,
208 C: [&](auto l, auto r) { return l.second > r.second; });
209
210 Value result = scaledValues.front().first;
211 for (auto [scaledValue, numHoistableLoops] : llvm::drop_begin(RangeOrContainer&: scaledValues)) {
212 std::ignore = numHoistableLoops;
213 result = arith::AddIOp::create(builder&: rewriter, location: loc, lhs: result, rhs: scaledValue,
214 overflowFlags: arith::IntegerOverflowFlags::nsw);
215 }
216 rewriter.replaceOp(op, newValues: result);
217 return success();
218}
219
220namespace {
221struct LowerDelinearizeIndexOps
222 : public OpRewritePattern<AffineDelinearizeIndexOp> {
223 using OpRewritePattern<AffineDelinearizeIndexOp>::OpRewritePattern;
224 LogicalResult matchAndRewrite(AffineDelinearizeIndexOp op,
225 PatternRewriter &rewriter) const override {
226 return affine::lowerAffineDelinearizeIndexOp(rewriter, op);
227 }
228};
229
230struct LowerLinearizeIndexOps final : OpRewritePattern<AffineLinearizeIndexOp> {
231 using Base::Base;
232 LogicalResult matchAndRewrite(AffineLinearizeIndexOp op,
233 PatternRewriter &rewriter) const override {
234 return affine::lowerAffineLinearizeIndexOp(rewriter, op);
235 }
236};
237
238class ExpandAffineIndexOpsPass
239 : public affine::impl::AffineExpandIndexOpsBase<ExpandAffineIndexOpsPass> {
240public:
241 ExpandAffineIndexOpsPass() = default;
242
243 void runOnOperation() override {
244 MLIRContext *context = &getContext();
245 RewritePatternSet patterns(context);
246 populateAffineExpandIndexOpsPatterns(patterns);
247 if (failed(Result: applyPatternsGreedily(op: getOperation(), patterns: std::move(patterns))))
248 return signalPassFailure();
249 }
250};
251
252} // namespace
253
254void mlir::affine::populateAffineExpandIndexOpsPatterns(
255 RewritePatternSet &patterns) {
256 patterns.insert<LowerDelinearizeIndexOps, LowerLinearizeIndexOps>(
257 arg: patterns.getContext());
258}
259
260std::unique_ptr<Pass> mlir::affine::createAffineExpandIndexOpsPass() {
261 return std::make_unique<ExpandAffineIndexOpsPass>();
262}
263