| 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 | |
| 39 | namespace mlir::shard { |
| 40 | |
| 41 | /// Base class for resharding patterns. |
| 42 | /// Subclasses implement `tryApply` to detect and apply a specific resharding. |
| 43 | class ReshardingPattern { |
| 44 | public: |
| 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 | |
| 55 | protected: |
| 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]]. |
| 74 | class 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 | |
| 132 | public: |
| 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]] -> []. |
| 148 | class 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 | |
| 240 | public: |
| 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. |
| 257 | static 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]]. |
| 269 | class 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 | |
| 374 | public: |
| 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. |
| 394 | class UpdateHaloPattern : public ReshardingPattern { |
| 395 | public: |
| 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. |
| 469 | static 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 | |
| 521 | TypedValue<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 | |
| 532 | TypedValue<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 | |
| 541 | void reshardingRegisterDependentDialects(DialectRegistry ®istry) { |
| 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 | |
| 548 | using 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. |
| 553 | static SmallVector<Type> |
| 554 | shardedBlockArgumentTypes(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 | |
| 577 | static LogicalResult |
| 578 | partitionOperation(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. |
| 607 | static 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. |
| 627 | static 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 | |
| 660 | static LogicalResult |
| 661 | partitionOperation(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 |
| 693 | static 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. |
| 725 | static 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 | |
| 764 | static LogicalResult |
| 765 | partitionOperation(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 | |
| 803 | static LogicalResult |
| 804 | partitionBlock(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 | |
| 834 | static LogicalResult |
| 835 | partitionFuncOp(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 | |
| 882 | namespace { |
| 883 | |
| 884 | struct 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 | |