1//===- Partition.cpp --------------------------------------------- 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#include "mlir/Dialect/Shard/Transforms/Partition.h"
10
11#include "mlir/Dialect/Shard/IR/ShardDialect.h"
12#include "mlir/Dialect/Shard/IR/ShardOps.h"
13#include "mlir/Dialect/Shard/Interfaces/ShardingInterface.h"
14#include "mlir/Dialect/Tensor/IR/Tensor.h"
15#include "mlir/IR/Builders.h"
16#include "mlir/IR/BuiltinAttributes.h"
17#include "mlir/IR/BuiltinTypeInterfaces.h"
18#include "mlir/IR/BuiltinTypes.h"
19#include "mlir/IR/Diagnostics.h"
20#include "mlir/IR/IRMapping.h"
21#include "mlir/IR/Location.h"
22#include "mlir/IR/MLIRContext.h"
23#include "mlir/IR/SymbolTable.h"
24#include "mlir/IR/Value.h"
25#include "mlir/Interfaces/ControlFlowInterfaces.h"
26#include "mlir/Interfaces/FunctionInterfaces.h"
27#include "mlir/Pass/Pass.h"
28#include "mlir/Support/LLVM.h"
29#include "llvm/ADT/STLExtras.h"
30#include "llvm/ADT/SmallVector.h"
31#include "llvm/Support/Casting.h"
32#include <array>
33#include <iterator>
34#include <memory>
35#include <optional>
36#include <tuple>
37#include <utility>
38
39namespace mlir::shard {
40
41/// Base class for resharding patterns.
42/// Subclasses implement `tryApply` to detect and apply a specific resharding.
43class ReshardingPattern {
44public:
45 virtual ~ReshardingPattern() = default;
46
47 /// Try to apply this resharding pattern. Returns the resharded value and
48 /// resulting sharding on success, or std::nullopt if the pattern doesn't
49 /// match.
50 virtual std::optional<std::tuple<TypedValue<ShapedType>, Sharding>>
51 tryApply(ImplicitLocOpBuilder &builder, GridOp grid, int64_t tensorDim,
52 const Sharding &srcSharding, const Sharding &tgtSharding,
53 ShapedType srcUnshardedType, TypedValue<ShapedType> srcShard) = 0;
54
55protected:
56 /// Returns true if either sharding has non-empty static sharded dims offsets.
57 static bool hasStaticOffsets(const Sharding &srcSharding,
58 const Sharding &tgtSharding) {
59 return !srcSharding.getStaticShardedDimsOffsets().empty() ||
60 !tgtSharding.getStaticShardedDimsOffsets().empty();
61 }
62
63 /// Returns true if either sharding has non-empty static sharded dims offsets
64 /// or non-empty static halo sizes.
65 static bool hasStaticOffsetsOrHalos(const Sharding &srcSharding,
66 const Sharding &tgtSharding) {
67 return hasStaticOffsets(srcSharding, tgtSharding) ||
68 !srcSharding.getStaticHaloSizes().empty() ||
69 !tgtSharding.getStaticHaloSizes().empty();
70 }
71};
72
73/// Split a replicated axis: e.g. [[0, 1]] -> [[0, 1, 2]].
74class SplitLastAxisPattern : public ReshardingPattern {
75 static Sharding tgtSharding(MLIRContext *ctx, const Sharding &srcSharding,
76 int64_t splitTensorDim, GridAxis splitGridAxis) {
77 SmallVector<GridAxesAttr> tgtShardingSplitAxes =
78 llvm::to_vector(Range: srcSharding.getSplitAxes());
79 while (static_cast<int64_t>(tgtShardingSplitAxes.size()) <=
80 splitTensorDim) {
81 tgtShardingSplitAxes.push_back(Elt: GridAxesAttr::get(context: ctx, content: {}));
82 }
83 auto tgtSplitAxes =
84 llvm::to_vector(Range: tgtShardingSplitAxes[splitTensorDim].asArrayRef());
85 tgtSplitAxes.push_back(Elt: splitGridAxis);
86 tgtShardingSplitAxes[splitTensorDim] = GridAxesAttr::get(context: ctx, content: tgtSplitAxes);
87 return Sharding::get(grid_: srcSharding.getGridAttr(), split_axes_: tgtShardingSplitAxes);
88 }
89
90 // Split a replicated tensor along a grid axis.
91 // E.g. [[0, 1]] -> [[0, 1, 2]].
92 // Returns the partitioned target value with its sharding.
93 static std::tuple<TypedValue<ShapedType>, Sharding>
94 apply(ImplicitLocOpBuilder &builder, Sharding srcSharding,
95 TypedValue<ShapedType> srcShard, GridOp grid, int64_t splitTensorDim,
96 GridAxis splitGridAxis) {
97 TypedValue<ShapedType> tgtShard =
98 AllSliceOp::create(builder, input: srcShard, grid,
99 gridAxes: ArrayRef<GridAxis>(splitGridAxis), sliceAxis: splitTensorDim)
100 .getResult();
101 Sharding resultSharding =
102 tgtSharding(ctx: builder.getContext(), srcSharding: std::move(srcSharding),
103 splitTensorDim, splitGridAxis);
104 return {tgtShard, resultSharding};
105 }
106
107 // Detect if the resharding is of type e.g.
108 // [[0, 1]] -> [[0, 1, 2]].
109 // If detected, returns the corresponding grid axis.
110 // Does not detect insertions like
111 // [[0, 1]] -> [[0, 2, 1]].
112 static std::optional<GridAxis> detect(const Sharding &srcSharding,
113 const Sharding &tgtSharding,
114 int64_t tensorDim) {
115 if (static_cast<size_t>(tensorDim) >= tgtSharding.getSplitAxes().size())
116 return std::nullopt;
117 auto tgtAxes = tgtSharding.getSplitAxes()[tensorDim].asArrayRef();
118 if (srcSharding.getSplitAxes().size() > static_cast<size_t>(tensorDim)) {
119 auto srcAxes = srcSharding.getSplitAxes()[tensorDim].asArrayRef();
120 if (srcAxes.size() + 1 != tgtAxes.size())
121 return std::nullopt;
122 if (!llvm::equal(LRange&: srcAxes,
123 RRange: llvm::make_range(x: tgtAxes.begin(), y: tgtAxes.end() - 1)))
124 return std::nullopt;
125 } else {
126 if (tgtAxes.size() != 1)
127 return std::nullopt;
128 }
129 return tgtAxes.back();
130 }
131
132public:
133 std::optional<std::tuple<TypedValue<ShapedType>, Sharding>>
134 tryApply(ImplicitLocOpBuilder &builder, GridOp grid, int64_t tensorDim,
135 const Sharding &srcSharding, const Sharding &tgtSharding,
136 ShapedType srcUnshardedType,
137 TypedValue<ShapedType> srcShard) override {
138 if (hasStaticOffsetsOrHalos(srcSharding, tgtSharding))
139 return std::nullopt;
140 if (auto gridAxis = detect(srcSharding, tgtSharding, tensorDim))
141 return apply(builder, srcSharding, srcShard, grid, splitTensorDim: tensorDim,
142 splitGridAxis: gridAxis.value());
143 return std::nullopt;
144 }
145};
146
147/// Unsplit trailing axes: e.g. [[0, 1, 2]] -> [[0, 1]] or [[0, 1, 2]] -> [].
148class UnsplitLastAxesPattern : public ReshardingPattern {
149 // Detect if the resharding removes trailing split axes along a tensor
150 // dimension, e.g.
151 // [[0, 1, 2]] -> [[0, 1]], [[0, 1, 2]] -> [0] or [[0, 1, 2]] -> [].
152 // If detected, returns the removed trailing split axes (grid axes).
153 static std::optional<SmallVector<GridAxis>>
154 detect(const Sharding &srcSharding, const Sharding &tgtSharding,
155 int64_t tensorDim) {
156 if (static_cast<size_t>(tensorDim) >= srcSharding.getSplitAxes().size())
157 return std::nullopt;
158 size_t dimOff = 0;
159 auto srcSplitAxes = srcSharding.getSplitAxes()[tensorDim].asArrayRef();
160 if (tgtSharding.getSplitAxes().size() > static_cast<size_t>(tensorDim)) {
161 auto tgtSplitAxes = tgtSharding.getSplitAxes()[tensorDim].asArrayRef();
162 // No match if the target sharding does not have less split axes than
163 // the source sharding along the current tensor dimension.
164 if (srcSplitAxes.size() <= tgtSplitAxes.size())
165 return std::nullopt;
166 // No match if the split axes of the target sharding are different from
167 // the first split axes of the source sharding.
168 if (!std::equal(first1: tgtSplitAxes.begin(), last1: tgtSplitAxes.end(),
169 first2: srcSplitAxes.begin()))
170 return std::nullopt;
171 dimOff = tgtSplitAxes.size();
172 } else {
173 // Here the target dimension is replicated; there is nothing to do if
174 // the source dimension is also replicated.
175 if (srcSplitAxes.size() == 0)
176 return std::nullopt;
177 dimOff = 0;
178 }
179 // This is a match. Return the trailing grid axes of the source sharding
180 // along this dimension.
181 ArrayRef<GridAxis> trailingAxes = srcSplitAxes.drop_front(N: dimOff);
182 SmallVector<GridAxis> unsplitAxes(trailingAxes.begin(), trailingAxes.end());
183 return unsplitAxes;
184 }
185
186 // Return the resulting Sharding if the unsplit last axes resharding is
187 // applied.
188 static Sharding tgtSharding(MLIRContext *ctx, const Sharding &srcSharding,
189 int64_t splitTensorDim, size_t numUnsplitAxes) {
190 SmallVector<GridAxesAttr> resSplitAxes =
191 llvm::to_vector(Range: srcSharding.getSplitAxes());
192 assert(static_cast<int64_t>(resSplitAxes.size()) > splitTensorDim);
193 ArrayRef<GridAxis> srcSplitAxes = resSplitAxes[splitTensorDim].asArrayRef();
194 assert(srcSplitAxes.size() >= numUnsplitAxes);
195 size_t numSplitAxes = srcSplitAxes.size() - numUnsplitAxes;
196 SmallVector<GridAxis> newSplitAxes(srcSplitAxes.begin(),
197 srcSplitAxes.begin() + numSplitAxes);
198 resSplitAxes[splitTensorDim] = GridAxesAttr::get(context: ctx, content: newSplitAxes);
199 return Sharding::get(grid_: srcSharding.getGridAttr(), split_axes_: resSplitAxes);
200 }
201
202 // Return the resulting Tensor type after applying the unsplit last axes
203 // resharding.
204 static ShapedType allGatherResultType(ShapedType srcType,
205 int64_t splitTensorDim,
206 ArrayRef<int64_t> gridShape,
207 ArrayRef<GridAxis> unsplitAxes) {
208 SmallVector<int64_t> tgtShape = llvm::to_vector(Range: srcType.getShape());
209 for (GridAxis gridAxis : unsplitAxes)
210 tgtShape[splitTensorDim] =
211 gatherDimension(dimSize: tgtShape[splitTensorDim], shardCount: gridShape[gridAxis]);
212 return srcType.cloneWith(shape: tgtShape, elementType: srcType.getElementType());
213 }
214
215 // Perform the resharding for the unsplit last axes case.
216 // This basically performs an all-gather along the unsplit grid axes.
217 static std::tuple<TypedValue<ShapedType>, Sharding>
218 apply(ImplicitLocOpBuilder &builder, Sharding srcSharding,
219 ShapedType srcUnshardedType, TypedValue<ShapedType> srcShard,
220 GridOp grid, int64_t splitTensorDim, ArrayRef<GridAxis> unsplitAxes) {
221 MLIRContext *ctx = builder.getContext();
222 builder.setInsertionPointAfterValue(srcShard);
223
224 Sharding resultSharding = tgtSharding(ctx, srcSharding: std::move(srcSharding),
225 splitTensorDim, numUnsplitAxes: unsplitAxes.size());
226 ShapedType agResultType = allGatherResultType(
227 srcType: srcShard.getType(), splitTensorDim, gridShape: grid.getShape(), unsplitAxes);
228 Value allGatherResult = AllGatherOp::create(
229 builder,
230 result: RankedTensorType::get(shape: agResultType.getShape(),
231 elementType: agResultType.getElementType()),
232 grid: grid.getSymName(), grid_axes: unsplitAxes, input: srcShard, gather_axis: APInt(64, splitTensorDim));
233 ShapedType tgtType =
234 shardShapedType(shape: srcUnshardedType, grid, sharding: resultSharding);
235 TypedValue<ShapedType> tgtShard =
236 tensor::CastOp::create(builder, dest: tgtType, source: allGatherResult).getResult();
237 return {tgtShard, resultSharding};
238 }
239
240public:
241 std::optional<std::tuple<TypedValue<ShapedType>, Sharding>>
242 tryApply(ImplicitLocOpBuilder &builder, GridOp grid, int64_t tensorDim,
243 const Sharding &srcSharding, const Sharding &tgtSharding,
244 ShapedType srcUnshardedType,
245 TypedValue<ShapedType> srcShard) override {
246 if (hasStaticOffsetsOrHalos(srcSharding, tgtSharding))
247 return std::nullopt;
248 if (auto gridAxes = detect(srcSharding, tgtSharding, tensorDim))
249 return apply(builder, srcSharding, srcUnshardedType, srcShard, grid,
250 splitTensorDim: tensorDim, unsplitAxes: gridAxes.value());
251 return std::nullopt;
252 }
253};
254
255// Compute the result shape of an all-to-all that gathers along srcTensorDim
256// and scatters along tgtTensorDim with the given split count.
257static ShapedType allToAllResultShape(ShapedType srcShape, int64_t splitCount,
258 int64_t srcTensorDim,
259 int64_t tgtTensorDim) {
260 SmallVector<int64_t> tgtShape = llvm::to_vector(Range: srcShape.getShape());
261 tgtShape[srcTensorDim] = gatherDimension(dimSize: tgtShape[srcTensorDim], shardCount: splitCount);
262 tgtShape[tgtTensorDim] = shardDimension(dimSize: tgtShape[tgtTensorDim], shardCount: splitCount);
263 return srcShape.cloneWith(shape: tgtShape, elementType: srcShape.getElementType());
264}
265
266/// Move the last split axis of one tensor dimension to the front of another
267/// tensor dimension's split axes, e.g. [[0], []] -> [[], [0]] or
268/// [[0, 1], [2]] -> [[0], [1, 2]].
269class MoveLastSplitAxisPattern : public ReshardingPattern {
270 // Detect if the resharding moves the last grid axis of srcTensorDim to the
271 // front of another tensor dimension's split axes. If detected, returns
272 // (tgtTensorDim, movedGridAxis).
273 //
274 // Pattern: src[srcTensorDim] = [a1,...,a(n-1),an] (n >= 1)
275 // tgt[srcTensorDim] = [a1,...,a(n-1)]
276 // src[tgtTensorDim] = [b1,...,bm] (m >= 0)
277 // tgt[tgtTensorDim] = [an, b1,...,bm]
278 static std::optional<std::tuple<int64_t, GridAxis>>
279 detect(const Sharding &srcSharding, const Sharding &tgtSharding,
280 int64_t srcTensorDim) {
281 if (static_cast<size_t>(srcTensorDim) >= srcSharding.getSplitAxes().size())
282 return std::nullopt;
283 auto srcAxes = srcSharding.getSplitAxes()[srcTensorDim].asArrayRef();
284 // Need at least 1 axis to move.
285 if (srcAxes.empty())
286 return std::nullopt;
287
288 // After the move the source tensor dim should lose its last axis.
289 if (static_cast<size_t>(srcTensorDim) >= tgtSharding.getSplitAxes().size())
290 return std::nullopt;
291 auto tgtSrcAxes = tgtSharding.getSplitAxes()[srcTensorDim].asArrayRef();
292 if (tgtSrcAxes.size() + 1 != srcAxes.size())
293 return std::nullopt;
294 // The remaining axes at srcTensorDim must be the same (prefix of source).
295 if (!llvm::equal(LRange&: tgtSrcAxes,
296 RRange: llvm::make_range(x: srcAxes.begin(), y: srcAxes.end() - 1)))
297 return std::nullopt;
298
299 GridAxis movedAxis = srcAxes.back();
300
301 // Find a target tensor dimension whose split axes start with movedAxis
302 // and whose remaining axes match the source sharding at that dimension.
303 for (size_t tgtTensorDim = 0;
304 tgtTensorDim < tgtSharding.getSplitAxes().size(); ++tgtTensorDim) {
305 if (static_cast<int64_t>(tgtTensorDim) == srcTensorDim)
306 continue;
307 auto tgtAxes = tgtSharding.getSplitAxes()[tgtTensorDim].asArrayRef();
308 // The target dimension must start with the moved axis.
309 if (tgtAxes.empty() || tgtAxes.front() != movedAxis)
310 continue;
311 // The remainder of tgtAxes must equal the source sharding at
312 // tgtTensorDim.
313 ArrayRef<GridAxis> srcTgtAxes =
314 static_cast<size_t>(tgtTensorDim) < srcSharding.getSplitAxes().size()
315 ? srcSharding.getSplitAxes()[tgtTensorDim].asArrayRef()
316 : ArrayRef<GridAxis>{};
317 if (!llvm::equal(LRange&: srcTgtAxes,
318 RRange: llvm::make_range(x: tgtAxes.begin() + 1, y: tgtAxes.end())))
319 continue;
320 return std::make_tuple(args: static_cast<int64_t>(tgtTensorDim), args&: movedAxis);
321 }
322 return std::nullopt;
323 }
324
325 // Compute the result sharding after moving movedAxis from srcTensorDim
326 // to the front of tgtTensorDim.
327 static Sharding tgtSharding(MLIRContext *ctx, const Sharding &srcSharding,
328 int64_t srcTensorDim, int64_t tgtTensorDim,
329 GridAxis movedAxis) {
330 SmallVector<GridAxesAttr> splitAxes =
331 llvm::to_vector(Range: srcSharding.getSplitAxes());
332 while (static_cast<int64_t>(splitAxes.size()) <= tgtTensorDim)
333 splitAxes.push_back(Elt: GridAxesAttr::get(context: ctx, content: {}));
334
335 // Remove last axis from srcTensorDim.
336 auto srcSplitAxes = llvm::to_vector(Range: splitAxes[srcTensorDim].asArrayRef());
337 assert(!srcSplitAxes.empty() && srcSplitAxes.back() == movedAxis);
338 srcSplitAxes.pop_back();
339 splitAxes[srcTensorDim] = GridAxesAttr::get(context: ctx, content: srcSplitAxes);
340
341 // Prepend movedAxis to tgtTensorDim.
342 auto tgtSplitAxes = llvm::to_vector(Range: splitAxes[tgtTensorDim].asArrayRef());
343 tgtSplitAxes.insert(I: tgtSplitAxes.begin(), Elt: movedAxis);
344 splitAxes[tgtTensorDim] = GridAxesAttr::get(context: ctx, content: tgtSplitAxes);
345
346 return Sharding::get(grid_: srcSharding.getGridAttr(), split_axes_: splitAxes);
347 }
348
349 static std::tuple<TypedValue<ShapedType>, Sharding>
350 apply(ImplicitLocOpBuilder &builder, GridOp grid, const Sharding &srcSharding,
351 ShapedType srcUnshardedType, TypedValue<ShapedType> srcShard,
352 int64_t srcTensorDim, int64_t tgtTensorDim, GridAxis movedAxis) {
353 MLIRContext *ctx = builder.getContext();
354 builder.setInsertionPointAfterValue(srcShard);
355
356 Sharding resultSharding =
357 tgtSharding(ctx, srcSharding, srcTensorDim, tgtTensorDim, movedAxis);
358 ShapedType a2aResultShape =
359 allToAllResultShape(srcShape: srcShard.getType(), splitCount: grid.getShape()[movedAxis],
360 srcTensorDim, tgtTensorDim);
361 Value allToAllResult = AllToAllOp::create(
362 builder,
363 result: RankedTensorType::get(shape: a2aResultShape.getShape(),
364 elementType: a2aResultShape.getElementType()),
365 grid: grid.getSymName(), grid_axes: SmallVector<GridAxis>({movedAxis}), input: srcShard,
366 split_axis: APInt(64, tgtTensorDim), concat_axis: APInt(64, srcTensorDim));
367 ShapedType tgtShape =
368 shardShapedType(shape: srcUnshardedType, grid, sharding: resultSharding);
369 TypedValue<ShapedType> tgtShard =
370 tensor::CastOp::create(builder, dest: tgtShape, source: allToAllResult).getResult();
371 return {tgtShard, resultSharding};
372 }
373
374public:
375 std::optional<std::tuple<TypedValue<ShapedType>, Sharding>>
376 tryApply(ImplicitLocOpBuilder &builder, GridOp grid, int64_t tensorDim,
377 const Sharding &srcSharding, const Sharding &tgtSharding,
378 ShapedType srcUnshardedType,
379 TypedValue<ShapedType> srcShard) override {
380 if (hasStaticOffsetsOrHalos(srcSharding, tgtSharding))
381 return std::nullopt;
382 if (auto detectRes = detect(srcSharding, tgtSharding, srcTensorDim: tensorDim)) {
383 auto [tgtTensorDim, movedAxis] = detectRes.value();
384 return apply(builder, grid, srcSharding, srcUnshardedType, srcShard,
385 srcTensorDim: tensorDim, tgtTensorDim, movedAxis);
386 }
387 return std::nullopt;
388 }
389};
390
391/// Update halo sizes: handles cases where only the halo sizes differ between
392/// source and target sharding. Requires copying the "core" of the source tensor
393/// into the "core" of the destination tensor followed by an update halo op.
394class UpdateHaloPattern : public ReshardingPattern {
395public:
396 std::optional<std::tuple<TypedValue<ShapedType>, Sharding>>
397 tryApply(ImplicitLocOpBuilder &builder, GridOp grid, int64_t tensorDim,
398 const Sharding &srcSharding, const Sharding &tgtSharding,
399 ShapedType srcUnshardedType,
400 TypedValue<ShapedType> srcShard) override {
401 // UpdateHaloPattern handles all dimensions at once; only trigger on dim 0.
402 if (tensorDim != 0)
403 return std::nullopt;
404 // Currently handles only cases where halo sizes differ but everything else
405 // stays the same (from source to destination sharding).
406 if (!srcSharding.equalSplitAxes(rhs: tgtSharding) ||
407 hasStaticOffsets(srcSharding, tgtSharding) ||
408 srcSharding.equalHaloSizes(rhs: tgtSharding)) {
409 return std::nullopt;
410 }
411
412 auto srcHaloSizes = srcSharding.getStaticHaloSizes();
413 auto tgtHaloSizes = tgtSharding.getStaticHaloSizes();
414 assert(srcHaloSizes.empty() || srcHaloSizes.size() == tgtHaloSizes.size());
415 assert(((srcHaloSizes.empty() || ShapedType::isStaticShape(srcHaloSizes)) &&
416 ShapedType::isStaticShape(tgtHaloSizes) &&
417 srcShard.getType().hasStaticShape()) &&
418 "dynamic shapes/halos are not supported yet for shard-partition");
419 auto rank = srcShard.getType().getRank();
420 auto splitAxes = srcSharding.getSplitAxes();
421 SmallVector<int64_t> srcCoreOffs(rank, 0), tgtCoreOffs(rank, 0),
422 strides(rank, 1), outShape(srcShard.getType().getShape()),
423 coreShape(srcShard.getType().getShape());
424
425 // Determine "core" of source and destination.
426 // The core is the local part of the shard excluding halo regions.
427 for (auto i = 0u; i < rank; ++i) {
428 if (i < splitAxes.size() && !splitAxes[i].empty()) {
429 if (!srcHaloSizes.empty()) {
430 coreShape[i] -= srcHaloSizes[i * 2] + srcHaloSizes[i * 2 + 1];
431 srcCoreOffs[i] = srcHaloSizes[i * 2];
432 }
433 tgtCoreOffs[i] = tgtHaloSizes[i * 2];
434 outShape[i] =
435 coreShape[i] + tgtHaloSizes[i * 2] + tgtHaloSizes[i * 2 + 1];
436 }
437 }
438
439 // Extract core from source and copy into destination core.
440 auto noVals = ValueRange{};
441 auto initVal = tensor::EmptyOp::create(builder, location: srcShard.getLoc(), staticShape: outShape,
442 elementType: srcShard.getType().getElementType());
443 auto core = tensor::ExtractSliceOp::create(
444 builder, location: srcShard.getLoc(),
445 result: RankedTensorType::get(shape: coreShape, elementType: srcShard.getType().getElementType()),
446 source: srcShard, offsets: noVals, sizes: noVals, strides: noVals, static_offsets: srcCoreOffs, static_sizes: coreShape, static_strides: strides);
447 auto initOprnd = tensor::InsertSliceOp::create(
448 builder, location: srcShard.getLoc(), source: core, dest: initVal, offsets: noVals, sizes: noVals, strides: noVals,
449 static_offsets: tgtCoreOffs, static_sizes: coreShape, static_strides: strides);
450
451 // Finally update the halo.
452 auto updateHaloResult =
453 UpdateHaloOp::create(builder, location: srcShard.getLoc(),
454 result: RankedTensorType::get(
455 shape: outShape, elementType: srcShard.getType().getElementType()),
456 destination: initOprnd, grid: grid.getSymName(),
457 split_axes: GridAxesArrayAttr::get(context: builder.getContext(),
458 axes: srcSharding.getSplitAxes()),
459 halo_sizes: tgtSharding.getDynamicHaloSizes(),
460 static_halo_sizes: tgtSharding.getStaticHaloSizes())
461 .getResult();
462 return std::make_tuple(args: cast<TypedValue<ShapedType>>(Val&: updateHaloResult),
463 args: tgtSharding);
464 }
465};
466
467// In most cases the sharded tensor axes must be exactly divisible by the single
468// grid axis size. Only halo size changes can deal with non-divisible cases.
469static TypedValue<ShapedType> reshard(ImplicitLocOpBuilder &builder,
470 GridOp grid, const Sharding &srcSharding,
471 const Sharding &tgtSharding,
472 TypedValue<ShapedType> unshardedSrc,
473 TypedValue<ShapedType> shardedSrc) {
474 // If source and destination sharding are the same, no need to do anything.
475 if (srcSharding == tgtSharding ||
476 (isFullReplication(sharding: srcSharding) && isFullReplication(sharding: tgtSharding))) {
477 return shardedSrc;
478 }
479
480 assert(shardedSrc.getType() ==
481 shardShapedType(unshardedSrc.getType(), grid, srcSharding));
482 [[maybe_unused]] ShapedType tgtShardType =
483 shardShapedType(shape: unshardedSrc.getType(), grid, sharding: tgtSharding);
484 assert(shardedSrc.getType().getRank() == tgtShardType.getRank());
485 assert(unshardedSrc.getType().getRank() == tgtShardType.getRank());
486
487 // Each pattern's tryApply checks its own applicability preconditions.
488 static UpdateHaloPattern updateHaloPattern;
489 static MoveLastSplitAxisPattern moveLastSplitAxisPattern;
490 static SplitLastAxisPattern splitLastAxisPattern;
491 static UnsplitLastAxesPattern unsplitLastAxesPattern;
492 static ReshardingPattern *patterns[] = {
493 &updateHaloPattern, &moveLastSplitAxisPattern, &splitLastAxisPattern,
494 &unsplitLastAxesPattern};
495 TypedValue<ShapedType> currentShard = shardedSrc;
496 Sharding currentSharding = srcSharding;
497 for (int64_t dim = 0;
498 dim < tgtShardType.getRank() && currentSharding != tgtSharding; ++dim) {
499 for (auto &pattern : patterns) {
500 if (auto tryRes = pattern->tryApply(builder, grid, tensorDim: dim, srcSharding: currentSharding,
501 tgtSharding, srcUnshardedType: unshardedSrc.getType(),
502 srcShard: currentShard)) {
503 std::tie(args&: currentShard, args&: currentSharding) = tryRes.value();
504 break;
505 }
506 }
507 }
508
509 if (currentSharding != tgtSharding ||
510 currentShard.getType() != tgtShardType) {
511 builder.emitError()
512 << "Failed to reshard; probably hitting an unknown resharding pattern:"
513 << " got " << currentSharding << " expected " << tgtSharding
514 << " got type " << currentShard.getType() << " expected "
515 << tgtShardType;
516 return TypedValue<ShapedType>();
517 }
518 return currentShard;
519}
520
521TypedValue<ShapedType> reshard(OpBuilder &builder, GridOp grid,
522 ShardOp srcShardOp, ShardOp tgtShardOp,
523 TypedValue<ShapedType> shardedSrc) {
524 assert(srcShardOp.getResult() == tgtShardOp.getSrc());
525 auto srcSharding = srcShardOp.getSharding();
526 auto tgtSharding = tgtShardOp.getSharding();
527 ImplicitLocOpBuilder implicitLocOpBuilder(tgtShardOp->getLoc(), builder);
528 return reshard(builder&: implicitLocOpBuilder, grid, srcSharding, tgtSharding,
529 unshardedSrc: srcShardOp.getSrc(), shardedSrc);
530}
531
532TypedValue<ShapedType> reshard(OpBuilder &builder, ShardOp srcShardOp,
533 ShardOp tgtShardOp,
534 TypedValue<ShapedType> shardedSrc,
535 SymbolTableCollection &symbolTableCollection) {
536 GridOp srcGrid = getGrid(op: srcShardOp, symbolTableCollection);
537 assert(srcGrid && srcGrid == getGrid(tgtShardOp, symbolTableCollection));
538 return reshard(builder, grid: srcGrid, srcShardOp, tgtShardOp, shardedSrc);
539}
540
541void reshardingRegisterDependentDialects(DialectRegistry &registry) {
542 registry.insert<shard::ShardDialect, tensor::TensorDialect>();
543}
544
545#define GEN_PASS_DEF_PARTITION
546#include "mlir/Dialect/Shard/Transforms/Passes.h.inc"
547
548using UnshardedToShardedValueMap = DenseMap<Value, Value>;
549
550// Get the types of block arguments for an partitioned block.
551// Reads the sharding annotations of the arguments to deduce the sharded types.
552// Types that are not ranked tensors are left unchanged.
553static SmallVector<Type>
554shardedBlockArgumentTypes(Block &block,
555 SymbolTableCollection &symbolTableCollection) {
556 SmallVector<Type> res;
557 llvm::transform(
558 Range: block.getArguments(), d_first: std::back_inserter(x&: res),
559 F: [&symbolTableCollection](BlockArgument arg) {
560 auto rankedTensorArg = dyn_cast<TypedValue<RankedTensorType>>(Val&: arg);
561 if (!rankedTensorArg || rankedTensorArg.getType().getRank() == 0 ||
562 rankedTensorArg.use_empty()) {
563 return arg.getType();
564 }
565
566 assert(rankedTensorArg.hasOneUse());
567 Operation *useOp = *rankedTensorArg.getUsers().begin();
568 ShardOp shardOp = llvm::dyn_cast<ShardOp>(Val: useOp);
569 assert(shardOp);
570 GridOp grid = getGrid(op: shardOp, symbolTableCollection);
571 return cast<Type>(Val: shardShapedType(shape: rankedTensorArg.getType(), grid,
572 sharding: shardOp.getSharding()));
573 });
574 return res;
575}
576
577static LogicalResult
578partitionOperation(Operation &op, ArrayRef<Value> partitionedOperands,
579 ArrayRef<Sharding> operandShardings,
580 ArrayRef<Sharding> resultShardings, IRMapping &partitionMap,
581 SymbolTableCollection &symbolTableCollection,
582 OpBuilder &builder) {
583 ShardingInterface shardingInterface = llvm::dyn_cast<ShardingInterface>(Val&: op);
584 if (!shardingInterface) {
585 // If there is no sharding interface we are conservative and assume that
586 // the op should be fully replicated no all devices.
587 partitionFullyReplicatedOperation(op, partitionedOperands, operandShardings,
588 resultShardings, partitionMap,
589 symbolTable&: symbolTableCollection, builder);
590 } else {
591 if (failed(Result: shardingInterface.partition(
592 partitionedOperands, operandShardings, resultShardings,
593 partitionMap, symbolTableCollection, builder))) {
594 return failure();
595 }
596 }
597
598 assert(llvm::all_of(op.getResults(), [&partitionMap](OpResult result) {
599 return partitionMap.contains(result);
600 }));
601
602 return success();
603}
604
605// Retrieve the sharding annotations for the operands of the given operation.
606// If the type is not a ranked tensor it is not require to have an annotation.
607static std::vector<Sharding> getOperandShardings(Operation &op) {
608 std::vector<Sharding> res;
609 res.reserve(n: op.getNumOperands());
610 llvm::transform(Range: op.getOperands(), d_first: std::back_inserter(x&: res), F: [](Value operand) {
611 TypedValue<RankedTensorType> rankedTensor =
612 dyn_cast<TypedValue<RankedTensorType>>(Val&: operand);
613 if (!rankedTensor || rankedTensor.getType().getRank() == 0) {
614 return Sharding();
615 }
616
617 Operation *definingOp = operand.getDefiningOp();
618 assert(definingOp);
619 ShardOp shardOp = llvm::cast<ShardOp>(Val: definingOp);
620 return Sharding(shardOp.getSharding());
621 });
622 return res;
623}
624
625// Retrieve the sharding annotations for the results of the given operation.
626// If the type is not a ranked tensor it is not require to have an annotation.
627static std::vector<Sharding> getResultShardings(Operation &op) {
628 std::vector<Sharding> res;
629 res.reserve(n: op.getNumResults());
630 llvm::transform(
631 Range: op.getResults(), d_first: std::back_inserter(x&: res), F: [&op](OpResult result) {
632 if (!result.hasOneUse() || result.use_empty()) {
633 return Sharding();
634 }
635 TypedValue<RankedTensorType> rankedTensor =
636 dyn_cast<TypedValue<RankedTensorType>>(Val&: result);
637 if (!rankedTensor) {
638 return Sharding();
639 }
640 Operation *userOp = *result.getUsers().begin();
641 ShardOp shardOp = llvm::dyn_cast<ShardOp>(Val: userOp);
642 if (shardOp) {
643 return Sharding(shardOp.getSharding());
644 }
645 if (rankedTensor.getType().getRank() == 0) {
646 // This is a 0d tensor result without explicit sharding.
647 // Find grid symbol from operands, if any.
648 // Shardings without grid are not always fully supported yet.
649 for (auto operand : op.getOperands()) {
650 if (auto sharding = operand.getDefiningOp<ShardingOp>()) {
651 return Sharding(sharding.getGridAttr());
652 }
653 }
654 }
655 return Sharding();
656 });
657 return res;
658}
659
660static LogicalResult
661partitionOperation(ShardOp shardOp, IRMapping &partitionMap,
662 SymbolTableCollection &symbolTableCollection,
663 OpBuilder &builder) {
664 Value tgtPartitionValue;
665
666 // Check if 2 shard ops are chained. If not there is no need for resharding
667 // as the source and target shared the same sharding.
668 ShardOp srcShardOp = shardOp.getSrc().getDefiningOp<ShardOp>();
669 if (!srcShardOp) {
670 tgtPartitionValue = partitionMap.lookup(from: shardOp.getSrc());
671 } else {
672 // Insert resharding.
673 TypedValue<ShapedType> shardedSrc =
674 cast<TypedValue<ShapedType>>(Val: partitionMap.lookup(from: srcShardOp));
675 tgtPartitionValue = reshard(builder, srcShardOp, tgtShardOp: shardOp, shardedSrc,
676 symbolTableCollection);
677 if (!tgtPartitionValue) {
678 return shardOp.emitError()
679 << "Failed to reshard from " << srcShardOp.getSharding() << " to "
680 << shardOp.getSharding();
681 }
682 }
683
684 assert(!partitionMap.contains(shardOp.getResult()));
685 partitionMap.map(from: shardOp.getResult(), to: tgtPartitionValue);
686 return success();
687}
688
689// Check if the block args are correctly annotated with sharding information:
690// - non-tensor, 0d-tensor and unused args are ignored
691// - each tensor arg must have exactly one use, which must be a shard.shard
692// operation
693static LogicalResult checkFullyAnnotated(Block &block) {
694 for (const BlockArgument &arg : block.getArguments()) {
695 auto rankedTensorArg = dyn_cast<TypedValue<RankedTensorType>>(Val: arg);
696 if (!rankedTensorArg || rankedTensorArg.getType().getRank() == 0 ||
697 rankedTensorArg.use_empty())
698 continue;
699
700 if (!rankedTensorArg.hasOneUse())
701 return emitError(loc: block.getParent()->getLoc())
702 << "Cannot partition: expected a single use for block argument "
703 << arg.getArgNumber() << " in block "
704 << block.computeBlockNumber();
705
706 Operation *useOp = *rankedTensorArg.getUsers().begin();
707 auto shardOp = dyn_cast<ShardOp>(Val: useOp);
708 if (!shardOp)
709 return emitError(loc: block.getParent()->getLoc())
710 << "Cannot partition: expected a shard.shard op for block "
711 << "argument " << arg.getArgNumber() << " in block "
712 << block.computeBlockNumber();
713 }
714 return success();
715}
716
717// Check if the operation is correctly and fully annotated with sharding
718// information:
719// - Operation results must have exactly one use (e.g. the shard operation).
720// - All operands and all results must be annotated, e.g. they must be
721// produced by/consumed by a shard.shard operation.
722// - Result annotations must not include the 'annotate_for_users' attribute.
723// - Operand annotations must include the 'annotate_for_users' attribute.
724// raises an error if the operation is not correctly and fully annotated.
725static LogicalResult checkFullyAnnotated(Operation *op) {
726 // constant ops do not need to have sharding annotations
727 if (op->hasTrait<OpTrait::ConstantLike>())
728 return success();
729
730 for (OpOperand &operand : op->getOpOperands()) {
731 // non-tensor and 0d-tensor operands are ignored
732 auto rankedTT = dyn_cast<RankedTensorType>(Val: operand.get().getType());
733 if (!rankedTT || rankedTT.getRank() == 0)
734 continue;
735
736 auto shard = operand.get().getDefiningOp<ShardOp>();
737 if (!shard)
738 return op->emitError() << "Cannot partition: tensor operand "
739 << operand.getOperandNumber()
740 << " must be defined by a shard.shard operation.";
741 if (!shard.getAnnotateForUsers())
742 return op->emitError()
743 << "Cannot partition: shard.shard for operand "
744 << operand.getOperandNumber() << " must set 'annotate_for_users'.";
745 }
746 for (const OpResult &result : op->getResults()) {
747 if (!result.hasOneUse())
748 return op->emitError()
749 << "Cannot partition: result " << result.getResultNumber()
750 << " must have exactly one use.";
751 auto shard = dyn_cast<ShardOp>(Val: *result.user_begin());
752 if (!shard)
753 return op->emitError()
754 << "Cannot partition: user of result " << result.getResultNumber()
755 << " must be shard.shard operation.";
756 if (shard.getAnnotateForUsers())
757 return op->emitError() << "Cannot partition: shard.shard for result "
758 << result.getResultNumber()
759 << " must not set 'annotate_for_users'.";
760 }
761 return success();
762}
763
764static LogicalResult
765partitionOperation(Operation &op, IRMapping &partitionMap,
766 SymbolTableCollection &symbolTableCollection,
767 OpBuilder &builder) {
768 if (isa<ShardingOp>(Val: op)) {
769 return success();
770 }
771
772 if (auto getShardingOp = dyn_cast<GetShardingOp>(Val&: op)) {
773 auto shardOp = getShardingOp.getSource().getDefiningOp<ShardOp>();
774 if (!shardOp) {
775 return op.emitError(message: "expected a shard op as source of get_sharding");
776 }
777 auto newSharding = builder.clone(op&: *shardOp.getSharding().getDefiningOp());
778 partitionMap.map(from: op.getResult(idx: 0), to: newSharding->getResult(idx: 0));
779 return success();
780 }
781
782 ShardOp shardOp = llvm::dyn_cast<ShardOp>(Val&: op);
783 if (shardOp) {
784 return partitionOperation(shardOp, partitionMap, symbolTableCollection,
785 builder);
786 }
787
788 // Check if operation is correctly and fully annotated.
789 if (failed(Result: checkFullyAnnotated(op: &op)))
790 return failure();
791
792 SmallVector<Value> partitionedOperands;
793 llvm::transform(Range: op.getOperands(), d_first: std::back_inserter(x&: partitionedOperands),
794 F: [&partitionMap](Value operand) {
795 assert(partitionMap.contains(operand));
796 return partitionMap.lookup(from: operand);
797 });
798 return partitionOperation(op, partitionedOperands, operandShardings: getOperandShardings(op),
799 resultShardings: getResultShardings(op), partitionMap,
800 symbolTableCollection, builder);
801}
802
803static LogicalResult
804partitionBlock(Block &block, IRMapping &partitionMap,
805 SymbolTableCollection &symbolTableCollection,
806 OpBuilder &builder) {
807
808 if (failed(Result: checkFullyAnnotated(block)))
809 return failure();
810
811 SmallVector<Location> argLocations;
812 llvm::transform(Range: block.getArguments(), d_first: std::back_inserter(x&: argLocations),
813 F: [](BlockArgument arg) { return arg.getLoc(); });
814 Block *newBlock = builder.createBlock(
815 parent: block.getParent(), insertPt: {},
816 argTypes: shardedBlockArgumentTypes(block, symbolTableCollection), locs: argLocations);
817 for (auto [unshardedBlockArg, partitionedBlockArg] :
818 llvm::zip(t: block.getArguments(), u: newBlock->getArguments())) {
819 partitionMap.map(from: unshardedBlockArg, to: partitionedBlockArg);
820 }
821
822 OpBuilder::InsertionGuard insertionGuard(builder);
823 builder.setInsertionPointToEnd(newBlock);
824 for (Operation &op : block.getOperations()) {
825 if (failed(Result: partitionOperation(op, partitionMap, symbolTableCollection,
826 builder))) {
827 return failure();
828 }
829 }
830
831 return success();
832}
833
834static LogicalResult
835partitionFuncOp(FunctionOpInterface op, IRMapping &partitionMap,
836 SymbolTableCollection &symbolTableCollection) {
837 OpBuilder builder(op.getFunctionBody());
838
839 // Snapshot the original blocks to not mess up the iteration when adding new
840 // blocks.
841 SmallVector<Block *> originalBlocks;
842 for (Block &b : op.getBlocks()) {
843 if (llvm::any_of(Range&: b.getOperations(),
844 P: [](Operation &op) { return isa<ShardOp>(Val: op); })) {
845 originalBlocks.push_back(Elt: &b);
846 }
847 }
848
849 for (Block *block : originalBlocks) {
850 if (failed(Result: partitionBlock(block&: *block, partitionMap, symbolTableCollection,
851 builder))) {
852 return failure();
853 }
854 }
855
856 for (Block *block : originalBlocks) {
857 block->erase();
858 }
859
860 // Find a return op and change the function results signature to its operands
861 // signature.
862 Operation *returnOp = nullptr;
863 for (Block &block : op.getFunctionBody()) {
864 if (block.empty()) {
865 continue;
866 }
867
868 if (block.back().hasTrait<OpTrait::ReturnLike>()) {
869 returnOp = &block.back();
870 break;
871 }
872 }
873 if (returnOp) {
874 op.setType(FunctionType::get(
875 context: op->getContext(), inputs: op.getFunctionBody().front().getArgumentTypes(),
876 results: returnOp->getOperandTypes()));
877 }
878
879 return success();
880}
881
882namespace {
883
884struct Partition : public impl::PartitionBase<Partition> {
885 void runOnOperation() override {
886 IRMapping partitionMap;
887 SymbolTableCollection symbolTableCollection;
888 if (failed(Result: partitionFuncOp(op: getOperation(), partitionMap,
889 symbolTableCollection))) {
890 return signalPassFailure();
891 }
892 }
893};
894
895} // namespace
896
897} // namespace mlir::shard
898