1//===- ShardingInterfaceImpl.cpp - Linalg sharding models -----------------===//
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/Linalg/Extensions/ShardingInterfaceImpl.h"
10
11#include "mlir/Analysis/SliceAnalysis.h"
12#include "mlir/Dialect/Affine/IR/AffineDialect.h"
13#include "mlir/Dialect/Arith/IR/Arith.h"
14#include "mlir/Dialect/Linalg/IR/Linalg.h"
15#include "mlir/Dialect/Linalg/IR/LinalgInterfaces.h"
16#include "mlir/Dialect/SCF/IR/SCF.h"
17#include "mlir/Dialect/Shard/IR/ShardOps.h"
18#include "mlir/Dialect/Shard/Interfaces/ShardingInterface.h"
19#include "mlir/Dialect/Shard/Interfaces/ShardingInterfaceImpl.h"
20#include "mlir/Dialect/Shard/Transforms/Transforms.h"
21#include "mlir/Dialect/Tensor/IR/Tensor.h"
22#include "mlir/Dialect/Utils/StructuredOpsUtils.h"
23#include "mlir/IR/AffineExpr.h"
24#include "mlir/IR/DialectRegistry.h"
25#include "mlir/IR/IRMapping.h"
26#include "mlir/IR/MLIRContext.h"
27#include "mlir/IR/OpDefinition.h"
28#include "mlir/IR/Operation.h"
29#include "mlir/IR/SymbolTable.h"
30#include "mlir/IR/Value.h"
31#include "llvm/ADT/STLExtras.h"
32#include "llvm/ADT/SmallVector.h"
33#include "llvm/ADT/TypeSwitch.h"
34#include <numeric>
35#include <optional>
36
37namespace mlir::linalg {
38using GridAxis = shard::GridAxis;
39using ReductionKind = shard::ReductionKind;
40using Sharding = shard::Sharding;
41using ShardingArray = shard::ShardingArray;
42using GridOp = shard::GridOp;
43
44// Returns the corresponding grid reduction kind for the given arith op.
45static ReductionKind getReductionKind(Operation *op) {
46 return llvm::TypeSwitch<Operation *, ReductionKind>(op)
47 // Floating-point operations.
48 .Case(caseFn: [](arith::AddFOp op) { return ReductionKind::Sum; })
49 .Case(caseFn: [](arith::MulFOp op) { return ReductionKind::Product; })
50 // TODO: handle maxnumf and minnumf.
51 .Case(caseFn: [](arith::MaximumFOp op) { return ReductionKind::Max; })
52 .Case(caseFn: [](arith::MinimumFOp op) { return ReductionKind::Min; })
53 // Integer operations.
54 .Case(caseFn: [](arith::AddIOp op) { return ReductionKind::Sum; })
55 .Case(caseFn: [](arith::OrIOp op) { return ReductionKind::BitwiseOr; })
56 .Case(caseFn: [](arith::XOrIOp op) { return ReductionKind::BitwiseXor; })
57 .Case(caseFn: [](arith::AndIOp op) { return ReductionKind::BitwiseAnd; })
58 // TODO: handle signless, signed and unsigned types properly.
59 // It is assumed that the element type of the collective operands and
60 // result drive the meaning of the reduction kind, whether it is signed
61 // or unsigned.
62 // The reduction op inside the linalg op may have different result type
63 // from the element type of the linalg op's result.
64 // Also signed and unsigned Arith dialect ops may accept signed, unsigned
65 // or signless operands.
66 // Maybe expand the reduction kinds.
67 .Case(caseFn: [](arith::MaxUIOp op) { return ReductionKind::Max; })
68 .Case(caseFn: [](arith::MinUIOp op) { return ReductionKind::Min; })
69 .Case(caseFn: [](arith::MaxSIOp op) { return ReductionKind::Max; })
70 .Case(caseFn: [](arith::MinSIOp op) { return ReductionKind::Min; })
71 .Case(caseFn: [](arith::MulIOp op) { return ReductionKind::Product; })
72 .Default(defaultFn: [](Operation *op) { return ReductionKind::Generic; });
73}
74
75static std::optional<Operation *> getCombinerOp(LinalgOp op) {
76 SmallVector<Operation *> combinerOps;
77 Value reducedValue = matchReduction(iterCarriedArgs: op.getRegionOutputArgs(), redPos: 0, combinerOps);
78 if (!reducedValue || combinerOps.size() != 1) {
79 return std::nullopt;
80 }
81
82 return combinerOps[0];
83}
84
85static ReductionKind getReductionKindOfLinalgOp(LinalgOp op) {
86 std::optional<Operation *> reductionOp = getCombinerOp(op);
87 if (!reductionOp) {
88 return ReductionKind::Generic;
89 }
90 [[maybe_unused]] Type resultElementType =
91 llvm::cast<RankedTensorType>(Val: op->getResult(idx: 0).getType()).getElementType();
92 // TODO: handle case when result type of the reduction op does not match the
93 // element type of the result tensor.
94 // Would it makes sense at all?
95 assert(resultElementType == reductionOp.value()->getResult(0).getType());
96 return getReductionKind(op: reductionOp.value());
97}
98
99static GridOp getGrid(Operation *op, ArrayRef<Sharding> operandShardings,
100 ArrayRef<Sharding> resultShardings,
101 SymbolTableCollection &symbolTable) {
102 for (const Sharding &sharding : operandShardings) {
103 if (sharding) {
104 return shard::getGrid(op, gridSymbol: sharding.getGridAttr(), symbolTableCollection&: symbolTable);
105 }
106 }
107
108 for (const Sharding &sharding : resultShardings) {
109 if (sharding) {
110 return shard::getGrid(op, gridSymbol: sharding.getGridAttr(), symbolTableCollection&: symbolTable);
111 }
112 }
113
114 assert(false);
115 return nullptr;
116}
117
118// Choose the operand based on the current process index along the reduction
119// grid axes.
120// We need to use the initial value only once to avoid including it in the
121// reduction multiple times.
122// In each process group only the leading process with linear index 0 would use
123// the original operand.
124// The other processes would use the reduction operation neutral tensor.
125static Value createDestinationPassingStyleInitOperand(
126 LinalgOp op, int operandNumber, Value partitionedOperand,
127 ArrayRef<GridAxis> reductionGridAxes, GridOp gridOp,
128 ImplicitLocOpBuilder &builder) {
129 Value processLinearIndexInReductionGroup = shard::createProcessLinearIndex(
130 builder, grid: gridOp.getSymName(), gridAxes: reductionGridAxes);
131 Value zero = arith::ConstantIndexOp::create(builder, value: 0);
132 Value isLeadProcess = arith::CmpIOp::create(
133 builder, result: builder.getI1Type(), predicate: arith::CmpIPredicate::eq,
134 lhs: processLinearIndexInReductionGroup, rhs: zero);
135 scf::IfOp ifOp = scf::IfOp::create(builder, resultTypes: partitionedOperand.getType(),
136 cond: isLeadProcess, addThenBlock: true, addElseBlock: true);
137 // Then block.
138 {
139 OpBuilder::InsertionGuard insertionGuard(builder);
140 builder.setInsertionPointToEnd(&ifOp.getThenRegion().front());
141 scf::YieldOp::create(builder, results: partitionedOperand);
142 }
143
144 // Else block.
145 {
146 OpBuilder::InsertionGuard insertionGuard(builder);
147 builder.setInsertionPointToEnd(&ifOp.getElseRegion().front());
148 SmallVector<OpFoldResult> shape =
149 tensor::getMixedSizes(builder, loc: builder.getLoc(), value: partitionedOperand);
150
151 SmallVector<Operation *> combinerOps;
152 matchReduction(iterCarriedArgs: op.getRegionOutputArgs(), redPos: operandNumber, combinerOps);
153 assert(combinerOps.size() == 1);
154 std::optional<TypedAttr> neutralEl =
155 arith::getNeutralElement(op: combinerOps[0]);
156
157 Value init = tensor::EmptyOp::create(builder, location: op.getLoc(), sizes: shape,
158 elementType: neutralEl.value().getType());
159 Value constant =
160 arith::ConstantOp::create(builder, location: op.getLoc(), value: neutralEl.value());
161 Value fill = linalg::FillOp::create(builder, location: op.getLoc(), inputs: constant, outputs: init)
162 .getResult(i: 0);
163
164 scf::YieldOp::create(builder, results: fill);
165 }
166 return ifOp.getResult(i: 0);
167}
168
169// Create the DPS init operands for the partitioned Linalg op.
170// Return all the new partitioned operands.
171static SmallVector<Value> createDestinationPassingStyleInitOperands(
172 LinalgOp op, GridOp gridOp, ArrayRef<Value> partitionedOperands,
173 ArrayRef<GridAxis> reductionGridAxes, IRMapping &partitionMap,
174 ImplicitLocOpBuilder &builder) {
175 // TODO: add support for multiple destination passing style initial value
176 // operands.
177 assert(op.getNumDpsInits() == 1 && "Multiple initial values not supported.");
178 SmallVector<Value> newOperands = llvm::to_vector(Range&: partitionedOperands);
179 auto operandIdx = op.getDpsInitOperand(i: 0)->getOperandNumber();
180 Value partitionedInitOperand =
181 partitionMap.lookup(from: op->getOperands()[operandIdx]);
182 newOperands[operandIdx] = createDestinationPassingStyleInitOperand(
183 op, operandNumber: 0, partitionedOperand: partitionedInitOperand, reductionGridAxes, gridOp, builder);
184 return newOperands;
185}
186
187static void createAllReduceForResultsWithoutPartialShardings(
188 LinalgOp unshardedOp, ArrayRef<GridAxis> opReductionGridAxes,
189 ArrayRef<Sharding> resultShardings, IRMapping &partitionMap,
190 ImplicitLocOpBuilder &builder) {
191 ReductionKind reductionKind = getReductionKindOfLinalgOp(op: unshardedOp);
192 for (auto [unshardedLinalgOpResult, resultSharding] :
193 llvm::zip_equal(t: unshardedOp->getResults(), u&: resultShardings)) {
194 Value partitionedLinalgOpResult =
195 partitionMap.lookup(from: unshardedLinalgOpResult);
196 Value reducedValue = shard::AllReduceOp::create(
197 builder, input: partitionedLinalgOpResult, grid: resultSharding.getGrid(),
198 gridAxes: opReductionGridAxes, reduction: reductionKind);
199 partitionMap.map(from: unshardedLinalgOpResult, to: reducedValue);
200 }
201}
202
203static void partitionLinalgOpWithShardedReduction(
204 LinalgOp op, ArrayRef<Value> partitionedOperands,
205 ArrayRef<Sharding> operandShardings, ArrayRef<Sharding> resultShardings,
206 ArrayRef<utils::IteratorType> loopIteratorTypes,
207 ArrayRef<SmallVector<GridAxis>> gridAxisAssignmentForLoopIterators,
208 IRMapping &partitionMap, SymbolTableCollection &symbolTable,
209 ImplicitLocOpBuilder &builder) {
210 GridOp grid = getGrid(op, operandShardings, resultShardings, symbolTable);
211 SmallVector<GridAxis> reductionGridAxes = shard::getReductionGridAxes(
212 loopIteratorTypes, gridAxisAssignmentForLoopIterators);
213 SmallVector<Value> partitionedLinalgOpOperands =
214 createDestinationPassingStyleInitOperands(op, gridOp: grid, partitionedOperands,
215 reductionGridAxes, partitionMap,
216 builder);
217 // We must not change the operand mappings of the original partitionMap as
218 // they are the mappings for the whole partition blob and may be used by
219 // others.
220 IRMapping internalPartitionMap;
221 for (auto [unshardedOperand, partitionedOperand] :
222 llvm::zip_equal(t: op->getOperands(), u&: partitionedLinalgOpOperands)) {
223 internalPartitionMap.map(from: unshardedOperand, to: partitionedOperand);
224 }
225 partitionTriviallyShardableOperation(
226 op&: *op, partitionedOperands: partitionedLinalgOpOperands, operandShardings, resultShardings,
227 partitionMap&: internalPartitionMap, symbolTable, builder);
228 for (Value result : op->getResults()) {
229 partitionMap.map(from: result, to: internalPartitionMap.lookup(from: result));
230 }
231
232 // Handle partial shardings.
233 createAllReduceForResultsWithoutPartialShardings(
234 unshardedOp: op, opReductionGridAxes: reductionGridAxes, resultShardings, partitionMap, builder);
235}
236
237namespace {
238// ShardingInterface for ops that implement LinalgStructuredInterface.
239// The supported ops are only those where the indexing maps are projected
240// permutations.
241template <typename Op>
242struct StructuredOpShardingInterface
243 : public shard::ShardingInterface::ExternalModel<
244 StructuredOpShardingInterface<Op>, Op> {
245 SmallVector<utils::IteratorType> getLoopIteratorTypes(Operation *op) const {
246 return llvm::cast<LinalgOp>(Val: op).getIteratorTypesArray();
247 }
248
249 SmallVector<AffineMap> getIndexingMaps(Operation *op) const {
250 LinalgOp linalgOp = llvm::cast<LinalgOp>(Val: op);
251 SmallVector<AffineMap> res = linalgOp.getIndexingMapsArray();
252
253 // Results must have the same indexing as destination passing style initial
254 // operands.
255 for (int64_t i = 0; i < linalgOp.getNumDpsInits(); ++i) {
256 res.push_back(Elt: res[linalgOp.getDpsInitOperand(i)->getOperandNumber()]);
257 }
258
259 return res;
260 }
261
262 SmallVector<ReductionKind>
263 getReductionLoopIteratorKinds(Operation *op) const {
264 LinalgOp linalgOp = llvm::cast<LinalgOp>(Val: op);
265 SmallVector<utils::IteratorType> iteratorTypes =
266 linalgOp.getIteratorTypesArray();
267 unsigned reductionItersCount = llvm::accumulate(
268 iteratorTypes, 0u, [](unsigned count, utils::IteratorType iter) {
269 return count + (iter == utils::IteratorType::reduction);
270 });
271 shard::ReductionKind reductionKind = getReductionKindOfLinalgOp(op: linalgOp);
272 return SmallVector<ReductionKind>(reductionItersCount, reductionKind);
273 }
274
275 LogicalResult partition(Operation *op, ArrayRef<Value> partitionedOperands,
276 ArrayRef<Sharding> operandShardings,
277 ArrayRef<Sharding> resultShardings,
278 IRMapping &partitionMap,
279 SymbolTableCollection &symbolTable,
280 OpBuilder &builder) const {
281 LinalgOp linalgOp = llvm::cast<LinalgOp>(Val: op);
282
283 SmallVector<AffineMap> indexingMaps = linalgOp.getIndexingMapsArray();
284 bool allIndexingMapsAreProjectedPermutation =
285 llvm::all_of(indexingMaps, [](AffineMap map) {
286 return map.isProjectedPermutation();
287 });
288 if (!allIndexingMapsAreProjectedPermutation) {
289 // TODO: handle non-projected permutations.
290 return op->emitOpError()
291 << "supports indexing maps that are only projected permutation.";
292 }
293
294 SmallVector<utils::IteratorType> loopIteratorTypes =
295 linalgOp.getIteratorTypesArray();
296 ShardingArray gridAxisAssignmentForLoopIterators =
297 getGridAxisAssignmentForLoopIterators(operandShardings, resultShardings,
298 loopIteratorTypes, indexingMaps);
299 if (shard::isAtLeastOneReductionIteratorSharded(
300 loopIteratorTypes, gridAxisAssignmentForLoopIterators)) {
301 ImplicitLocOpBuilder implicitLocBuilder(op->getLoc(), builder);
302 partitionLinalgOpWithShardedReduction(
303 op: linalgOp, partitionedOperands, operandShardings, resultShardings,
304 loopIteratorTypes, gridAxisAssignmentForLoopIterators, partitionMap,
305 symbolTable, builder&: implicitLocBuilder);
306 } else {
307 partitionTriviallyShardableOperation(op&: *op, partitionedOperands,
308 operandShardings, resultShardings,
309 partitionMap, symbolTable, builder);
310 }
311
312 return success();
313 }
314};
315} // namespace
316
317template <typename OpType>
318static void registerOne(MLIRContext *ctx) {
319 OpType::template attachInterface<StructuredOpShardingInterface<OpType>>(*ctx);
320}
321
322/// Variadic helper function.
323template <typename... OpTypes>
324static void registerAll(MLIRContext *ctx) {
325 (registerOne<OpTypes>(ctx), ...);
326}
327
328void registerShardingInterfaceExternalModels(DialectRegistry &registry) {
329 registry.addExtension(extensionFn: +[](MLIRContext *ctx, LinalgDialect *dialect) {
330 DialectRegistry registry;
331 registry.insert<affine::AffineDialect, arith::ArithDialect, scf::SCFDialect,
332 tensor::TensorDialect>();
333 ctx->appendDialectRegistry(registry);
334 for (StringRef name : registry.getRegisteredDialectNames())
335 ctx->getOrLoadDialect(name);
336
337 registerOne<linalg::GenericOp>(ctx);
338 registerAll<
339#define GET_OP_LIST
340#include "mlir/Dialect/Linalg/IR/LinalgStructuredOps.cpp.inc"
341 >(ctx);
342 });
343}
344} // namespace mlir::linalg
345