| 1 | //===- SubgroupReduceLowering.cpp - subgroup_reduce lowering patterns -----===// |
| 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 | // Implements gradual lowering of `gpu.subgroup_reduce` ops. |
| 10 | // |
| 11 | //===----------------------------------------------------------------------===// |
| 12 | |
| 13 | #include "mlir/Dialect/Arith/IR/Arith.h" |
| 14 | #include "mlir/Dialect/GPU/IR/GPUDialect.h" |
| 15 | #include "mlir/Dialect/GPU/Transforms/Passes.h" |
| 16 | #include "mlir/Dialect/GPU/Utils/GPUUtils.h" |
| 17 | #include "mlir/Dialect/Vector/IR/VectorOps.h" |
| 18 | #include "mlir/IR/BuiltinTypes.h" |
| 19 | #include "mlir/IR/Location.h" |
| 20 | #include "mlir/IR/PatternMatch.h" |
| 21 | #include "mlir/IR/TypeUtilities.h" |
| 22 | #include "llvm/Support/FormatVariadic.h" |
| 23 | #include "llvm/Support/MathExtras.h" |
| 24 | #include <cassert> |
| 25 | #include <cstdint> |
| 26 | |
| 27 | using namespace mlir; |
| 28 | |
| 29 | namespace { |
| 30 | |
| 31 | /// Example, assumes `maxShuffleBitwidth` equal to 32: |
| 32 | /// ``` |
| 33 | /// %a = gpu.subgroup_reduce add %x : (vector<3xf16>) -> vector<3xf16> |
| 34 | /// ==> |
| 35 | /// %v0 = arith.constant dense<0.0> : vector<3xf16> |
| 36 | /// %e0 = vector.extract_strided_slice %x |
| 37 | /// {offsets = [0], sizes = [2], strides = [1}: vector<3xf32> to vector<2xf32> |
| 38 | /// %r0 = gpu.subgroup_reduce add %e0 : (vector<2xf16>) -> vector<2xf16> |
| 39 | /// %v1 = vector.insert_strided_slice %r0, %v0 |
| 40 | /// {offsets = [0], strides = [1}: vector<2xf32> into vector<3xf32> |
| 41 | /// %e1 = vector.extract %x[2] : f16 from vector<2xf16> |
| 42 | /// %r1 = gpu.subgroup_reduce add %e1 : (f16) -> f16 |
| 43 | /// %a = vector.insert %r1, %v1[2] : f16 into vector<3xf16> |
| 44 | /// ``` |
| 45 | struct BreakDownSubgroupReduce final : OpRewritePattern<gpu::SubgroupReduceOp> { |
| 46 | BreakDownSubgroupReduce(MLIRContext *ctx, unsigned maxShuffleBitwidth, |
| 47 | PatternBenefit benefit) |
| 48 | : OpRewritePattern(ctx, benefit), maxShuffleBitwidth(maxShuffleBitwidth) { |
| 49 | } |
| 50 | |
| 51 | LogicalResult matchAndRewrite(gpu::SubgroupReduceOp op, |
| 52 | PatternRewriter &rewriter) const override { |
| 53 | auto vecTy = dyn_cast<VectorType>(Val: op.getType()); |
| 54 | if (!vecTy || vecTy.getNumElements() < 2) |
| 55 | return rewriter.notifyMatchFailure(arg&: op, msg: "not a multi-element reduction" ); |
| 56 | |
| 57 | assert(vecTy.getRank() == 1 && "Unexpected vector type" ); |
| 58 | assert(!vecTy.isScalable() && "Unexpected vector type" ); |
| 59 | |
| 60 | Type elemTy = vecTy.getElementType(); |
| 61 | unsigned elemBitwidth = elemTy.getIntOrFloatBitWidth(); |
| 62 | if (elemBitwidth >= maxShuffleBitwidth) |
| 63 | return rewriter.notifyMatchFailure( |
| 64 | arg&: op, msg: llvm::formatv(Fmt: "element type too large ({0}), cannot break down " |
| 65 | "into vectors of bitwidth {1} or less" , |
| 66 | Vals&: elemBitwidth, Vals: maxShuffleBitwidth)); |
| 67 | |
| 68 | unsigned elementsPerShuffle = maxShuffleBitwidth / elemBitwidth; |
| 69 | assert(elementsPerShuffle >= 1); |
| 70 | |
| 71 | unsigned numNewReductions = |
| 72 | llvm::divideCeil(Numerator: vecTy.getNumElements(), Denominator: elementsPerShuffle); |
| 73 | assert(numNewReductions >= 1); |
| 74 | if (numNewReductions == 1) |
| 75 | return rewriter.notifyMatchFailure(arg&: op, msg: "nothing to break down" ); |
| 76 | |
| 77 | Location loc = op.getLoc(); |
| 78 | Value res = |
| 79 | arith::ConstantOp::create(builder&: rewriter, location: loc, value: rewriter.getZeroAttr(type: vecTy)); |
| 80 | |
| 81 | for (unsigned i = 0; i != numNewReductions; ++i) { |
| 82 | int64_t startIdx = i * elementsPerShuffle; |
| 83 | int64_t endIdx = |
| 84 | std::min(a: startIdx + elementsPerShuffle, b: vecTy.getNumElements()); |
| 85 | int64_t numElems = endIdx - startIdx; |
| 86 | |
| 87 | Value ; |
| 88 | if (numElems == 1) { |
| 89 | extracted = |
| 90 | vector::ExtractOp::create(builder&: rewriter, location: loc, source: op.getValue(), position: startIdx); |
| 91 | } else { |
| 92 | extracted = vector::ExtractStridedSliceOp::create( |
| 93 | builder&: rewriter, location: loc, source: op.getValue(), /*offsets=*/startIdx, |
| 94 | /*sizes=*/numElems, |
| 95 | /*strides=*/1); |
| 96 | } |
| 97 | |
| 98 | Value reduce = gpu::SubgroupReduceOp::create( |
| 99 | builder&: rewriter, location: loc, value: extracted, op: op.getOp(), uniform: op.getUniform(), |
| 100 | cluster_size: op.getClusterSize(), cluster_stride: op.getClusterStride()); |
| 101 | if (numElems == 1) { |
| 102 | res = vector::InsertOp::create(builder&: rewriter, location: loc, valueToStore: reduce, dest: res, position: startIdx); |
| 103 | continue; |
| 104 | } |
| 105 | |
| 106 | res = vector::InsertStridedSliceOp::create( |
| 107 | builder&: rewriter, location: loc, valueToStore: reduce, dest: res, /*offsets=*/startIdx, /*strides=*/1); |
| 108 | } |
| 109 | |
| 110 | rewriter.replaceOp(op, newValues: res); |
| 111 | return success(); |
| 112 | } |
| 113 | |
| 114 | private: |
| 115 | unsigned maxShuffleBitwidth = 0; |
| 116 | }; |
| 117 | |
| 118 | /// Example: |
| 119 | /// ``` |
| 120 | /// %a = gpu.subgroup_reduce add %x : (vector<1xf32>) -> vector<1xf32> |
| 121 | /// ==> |
| 122 | /// %e0 = vector.extract %x[0] : f32 from vector<1xf32> |
| 123 | /// %r0 = gpu.subgroup_reduce add %e0 : (f32) -> f32 |
| 124 | /// %a = vector.broadcast %r0 : f32 to vector<1xf32> |
| 125 | /// ``` |
| 126 | struct ScalarizeSingleElementReduce final |
| 127 | : OpRewritePattern<gpu::SubgroupReduceOp> { |
| 128 | using Base::Base; |
| 129 | |
| 130 | LogicalResult matchAndRewrite(gpu::SubgroupReduceOp op, |
| 131 | PatternRewriter &rewriter) const override { |
| 132 | auto vecTy = dyn_cast<VectorType>(Val: op.getType()); |
| 133 | if (!vecTy || vecTy.getNumElements() != 1) |
| 134 | return rewriter.notifyMatchFailure(arg&: op, msg: "not a single-element reduction" ); |
| 135 | |
| 136 | assert(vecTy.getRank() == 1 && "Unexpected vector type" ); |
| 137 | assert(!vecTy.isScalable() && "Unexpected vector type" ); |
| 138 | Location loc = op.getLoc(); |
| 139 | Value = |
| 140 | vector::ExtractOp::create(builder&: rewriter, location: loc, source: op.getValue(), position: 0); |
| 141 | Value reduce = gpu::SubgroupReduceOp::create( |
| 142 | builder&: rewriter, location: loc, value: extracted, op: op.getOp(), uniform: op.getUniform(), |
| 143 | cluster_size: op.getClusterSize(), cluster_stride: op.getClusterStride()); |
| 144 | rewriter.replaceOpWithNewOp<vector::BroadcastOp>(op, args&: vecTy, args&: reduce); |
| 145 | return success(); |
| 146 | } |
| 147 | }; |
| 148 | |
| 149 | /// Emits a subgroup reduction using a sequence of shuffles. Uses the `packFn` |
| 150 | /// and `unpackFn` to convert to the native shuffle type and to the reduction |
| 151 | /// type, respectively. For example, with `input` of type `f16`, `packFn` could |
| 152 | /// build ops to cast the value to `i32` to perform shuffles, while `unpackFn` |
| 153 | /// would cast it back to `f16` to perform arithmetic reduction on. Assumes that |
| 154 | /// the subgroup is `subgroupSize` lanes wide and divides it into clusters of |
| 155 | /// `clusterSize` lanes starting at lane 0 with a stride of `clusterStride` for |
| 156 | /// lanes within a cluster, reducing all lanes in each cluster in parallel. |
| 157 | Value createSubgroupShuffleReduction(OpBuilder &builder, Location loc, |
| 158 | Value input, gpu::AllReduceOperation mode, |
| 159 | const gpu::SubgroupReduceClusterInfo &ci, |
| 160 | function_ref<Value(Value)> packFn, |
| 161 | function_ref<Value(Value)> unpackFn) { |
| 162 | // Lane value always stays in the original type. We use it to perform arith |
| 163 | // reductions. |
| 164 | Value laneVal = input; |
| 165 | // Parallel reduction using butterfly shuffles. |
| 166 | for (unsigned i = ci.clusterStride; i < ci.clusterStride * ci.clusterSize; |
| 167 | i <<= 1) { |
| 168 | Value shuffled = gpu::ShuffleOp::create(builder, location: loc, value: packFn(laneVal), offset: i, |
| 169 | /*width=*/ci.subgroupSize, |
| 170 | /*mode=*/gpu::ShuffleMode::XOR) |
| 171 | .getShuffleResult(); |
| 172 | laneVal = vector::makeArithReduction(b&: builder, loc, |
| 173 | kind: gpu::convertReductionKind(mode), |
| 174 | v1: laneVal, acc: unpackFn(shuffled)); |
| 175 | assert(laneVal.getType() == input.getType()); |
| 176 | } |
| 177 | |
| 178 | return laneVal; |
| 179 | } |
| 180 | |
| 181 | /// Lowers scalar gpu subgroup reductions to a series of shuffles. |
| 182 | struct ScalarSubgroupReduceToShuffles final |
| 183 | : OpRewritePattern<gpu::SubgroupReduceOp> { |
| 184 | ScalarSubgroupReduceToShuffles(MLIRContext *ctx, unsigned subgroupSize, |
| 185 | unsigned shuffleBitwidth, bool matchClustered, |
| 186 | PatternBenefit benefit) |
| 187 | : OpRewritePattern(ctx, benefit), subgroupSize(subgroupSize), |
| 188 | shuffleBitwidth(shuffleBitwidth), matchClustered(matchClustered) {} |
| 189 | |
| 190 | LogicalResult matchAndRewrite(gpu::SubgroupReduceOp op, |
| 191 | PatternRewriter &rewriter) const override { |
| 192 | if (op.getClusterSize().has_value() != matchClustered) { |
| 193 | return rewriter.notifyMatchFailure( |
| 194 | arg&: op, msg: llvm::formatv(Fmt: "op is {0}clustered but pattern is configured to " |
| 195 | "only match {1}clustered ops" , |
| 196 | Vals: matchClustered ? "non-" : "" , |
| 197 | Vals: matchClustered ? "" : "non-" )); |
| 198 | } |
| 199 | |
| 200 | auto ci = gpu::getSubgroupReduceClusterInfo(op, subgroupSize); |
| 201 | if (failed(Result: ci)) |
| 202 | return failure(); |
| 203 | |
| 204 | Type valueTy = op.getType(); |
| 205 | unsigned elemBitwidth = |
| 206 | getElementTypeOrSelf(type: valueTy).getIntOrFloatBitWidth(); |
| 207 | if (!valueTy.isIntOrFloat() || elemBitwidth > shuffleBitwidth) |
| 208 | return rewriter.notifyMatchFailure( |
| 209 | arg&: op, msg: "value type is not a compatible scalar" ); |
| 210 | |
| 211 | Location loc = op.getLoc(); |
| 212 | // Since this is already a native shuffle scalar, no packing is necessary. |
| 213 | if (elemBitwidth == shuffleBitwidth) { |
| 214 | auto identityFn = [](Value v) { return v; }; |
| 215 | rewriter.replaceOp(op, newValues: createSubgroupShuffleReduction( |
| 216 | builder&: rewriter, loc, input: op.getValue(), mode: op.getOp(), ci: *ci, |
| 217 | packFn: identityFn, unpackFn: identityFn)); |
| 218 | return success(); |
| 219 | } |
| 220 | |
| 221 | auto shuffleIntType = rewriter.getIntegerType(width: shuffleBitwidth); |
| 222 | auto equivIntType = rewriter.getIntegerType(width: elemBitwidth); |
| 223 | auto packFn = [loc, &rewriter, equivIntType, |
| 224 | shuffleIntType](Value unpackedVal) -> Value { |
| 225 | auto asInt = |
| 226 | arith::BitcastOp::create(builder&: rewriter, location: loc, out: equivIntType, in: unpackedVal); |
| 227 | return arith::ExtUIOp::create(builder&: rewriter, location: loc, out: shuffleIntType, in: asInt); |
| 228 | }; |
| 229 | auto unpackFn = [loc, &rewriter, equivIntType, |
| 230 | valueTy](Value packedVal) -> Value { |
| 231 | auto asInt = |
| 232 | arith::TruncIOp::create(builder&: rewriter, location: loc, out: equivIntType, in: packedVal); |
| 233 | return arith::BitcastOp::create(builder&: rewriter, location: loc, out: valueTy, in: asInt); |
| 234 | }; |
| 235 | |
| 236 | rewriter.replaceOp( |
| 237 | op, newValues: createSubgroupShuffleReduction(builder&: rewriter, loc, input: op.getValue(), |
| 238 | mode: op.getOp(), ci: *ci, packFn, unpackFn)); |
| 239 | return success(); |
| 240 | } |
| 241 | |
| 242 | private: |
| 243 | unsigned subgroupSize = 0; |
| 244 | unsigned shuffleBitwidth = 0; |
| 245 | bool matchClustered = false; |
| 246 | }; |
| 247 | |
| 248 | /// Lowers vector gpu subgroup reductions to a series of shuffles. |
| 249 | struct VectorSubgroupReduceToShuffles final |
| 250 | : OpRewritePattern<gpu::SubgroupReduceOp> { |
| 251 | VectorSubgroupReduceToShuffles(MLIRContext *ctx, unsigned subgroupSize, |
| 252 | unsigned shuffleBitwidth, bool matchClustered, |
| 253 | PatternBenefit benefit) |
| 254 | : OpRewritePattern(ctx, benefit), subgroupSize(subgroupSize), |
| 255 | shuffleBitwidth(shuffleBitwidth), matchClustered(matchClustered) {} |
| 256 | |
| 257 | LogicalResult matchAndRewrite(gpu::SubgroupReduceOp op, |
| 258 | PatternRewriter &rewriter) const override { |
| 259 | if (op.getClusterSize().has_value() != matchClustered) { |
| 260 | return rewriter.notifyMatchFailure( |
| 261 | arg&: op, msg: llvm::formatv(Fmt: "op is {0}clustered but pattern is configured to " |
| 262 | "only match {1}clustered ops" , |
| 263 | Vals: matchClustered ? "non-" : "" , |
| 264 | Vals: matchClustered ? "" : "non-" )); |
| 265 | } |
| 266 | |
| 267 | auto ci = gpu::getSubgroupReduceClusterInfo(op, subgroupSize); |
| 268 | if (failed(Result: ci)) |
| 269 | return failure(); |
| 270 | |
| 271 | auto vecTy = dyn_cast<VectorType>(Val: op.getType()); |
| 272 | if (!vecTy) |
| 273 | return rewriter.notifyMatchFailure(arg&: op, msg: "value type is not a vector" ); |
| 274 | |
| 275 | unsigned vecBitwidth = |
| 276 | vecTy.getNumElements() * vecTy.getElementTypeBitWidth(); |
| 277 | if (vecBitwidth > shuffleBitwidth) |
| 278 | return rewriter.notifyMatchFailure( |
| 279 | arg&: op, |
| 280 | msg: llvm::formatv(Fmt: "vector type bitwidth too large ({0}), cannot lower " |
| 281 | "to shuffles of size {1}" , |
| 282 | Vals&: vecBitwidth, Vals: shuffleBitwidth)); |
| 283 | |
| 284 | unsigned elementsPerShuffle = |
| 285 | shuffleBitwidth / vecTy.getElementTypeBitWidth(); |
| 286 | if (elementsPerShuffle * vecTy.getElementTypeBitWidth() != shuffleBitwidth) |
| 287 | return rewriter.notifyMatchFailure( |
| 288 | arg&: op, msg: "shuffle bitwidth is not a multiple of the element bitwidth" ); |
| 289 | |
| 290 | Location loc = op.getLoc(); |
| 291 | |
| 292 | // If the reduced type is smaller than the native shuffle size, extend it, |
| 293 | // perform the shuffles, and extract at the end. |
| 294 | auto extendedVecTy = VectorType::get( |
| 295 | shape: static_cast<int64_t>(elementsPerShuffle), elementType: vecTy.getElementType()); |
| 296 | Value extendedInput = op.getValue(); |
| 297 | if (vecBitwidth < shuffleBitwidth) { |
| 298 | auto zero = arith::ConstantOp::create( |
| 299 | builder&: rewriter, location: loc, value: rewriter.getZeroAttr(type: extendedVecTy)); |
| 300 | extendedInput = vector::InsertStridedSliceOp::create( |
| 301 | builder&: rewriter, location: loc, valueToStore: extendedInput, dest: zero, /*offsets=*/0, /*strides=*/1); |
| 302 | } |
| 303 | |
| 304 | auto shuffleIntType = rewriter.getIntegerType(width: shuffleBitwidth); |
| 305 | auto shuffleVecType = VectorType::get(shape: 1, elementType: shuffleIntType); |
| 306 | |
| 307 | auto packFn = [loc, &rewriter, shuffleVecType](Value unpackedVal) -> Value { |
| 308 | auto asIntVec = |
| 309 | vector::BitCastOp::create(builder&: rewriter, location: loc, result: shuffleVecType, source: unpackedVal); |
| 310 | return vector::ExtractOp::create(builder&: rewriter, location: loc, source: asIntVec, position: 0); |
| 311 | }; |
| 312 | auto unpackFn = [loc, &rewriter, shuffleVecType, |
| 313 | extendedVecTy](Value packedVal) -> Value { |
| 314 | auto asIntVec = |
| 315 | vector::BroadcastOp::create(builder&: rewriter, location: loc, result: shuffleVecType, source: packedVal); |
| 316 | return vector::BitCastOp::create(builder&: rewriter, location: loc, result: extendedVecTy, source: asIntVec); |
| 317 | }; |
| 318 | |
| 319 | Value res = createSubgroupShuffleReduction( |
| 320 | builder&: rewriter, loc, input: extendedInput, mode: op.getOp(), ci: *ci, packFn, unpackFn); |
| 321 | |
| 322 | if (vecBitwidth < shuffleBitwidth) { |
| 323 | res = vector::ExtractStridedSliceOp::create( |
| 324 | builder&: rewriter, location: loc, source: res, /*offsets=*/0, /*sizes=*/vecTy.getNumElements(), |
| 325 | /*strides=*/1); |
| 326 | } |
| 327 | |
| 328 | rewriter.replaceOp(op, newValues: res); |
| 329 | return success(); |
| 330 | } |
| 331 | |
| 332 | private: |
| 333 | unsigned subgroupSize = 0; |
| 334 | unsigned shuffleBitwidth = 0; |
| 335 | bool matchClustered = false; |
| 336 | }; |
| 337 | } // namespace |
| 338 | |
| 339 | void mlir::populateGpuBreakDownSubgroupReducePatterns( |
| 340 | RewritePatternSet &patterns, unsigned maxShuffleBitwidth, |
| 341 | PatternBenefit benefit) { |
| 342 | patterns.add<BreakDownSubgroupReduce>(arg: patterns.getContext(), |
| 343 | args&: maxShuffleBitwidth, args&: benefit); |
| 344 | patterns.add<ScalarizeSingleElementReduce>(arg: patterns.getContext(), args&: benefit); |
| 345 | } |
| 346 | |
| 347 | void mlir::populateGpuLowerSubgroupReduceToShufflePatterns( |
| 348 | RewritePatternSet &patterns, unsigned subgroupSize, |
| 349 | unsigned shuffleBitwidth, PatternBenefit benefit) { |
| 350 | patterns.add<ScalarSubgroupReduceToShuffles, VectorSubgroupReduceToShuffles>( |
| 351 | arg: patterns.getContext(), args&: subgroupSize, args&: shuffleBitwidth, |
| 352 | /*matchClustered=*/args: false, args&: benefit); |
| 353 | } |
| 354 | |
| 355 | void mlir::populateGpuLowerClusteredSubgroupReduceToShufflePatterns( |
| 356 | RewritePatternSet &patterns, unsigned subgroupSize, |
| 357 | unsigned shuffleBitwidth, PatternBenefit benefit) { |
| 358 | patterns.add<ScalarSubgroupReduceToShuffles, VectorSubgroupReduceToShuffles>( |
| 359 | arg: patterns.getContext(), args&: subgroupSize, args&: shuffleBitwidth, |
| 360 | /*matchClustered=*/args: true, args&: benefit); |
| 361 | } |
| 362 | |