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
27using namespace mlir;
28
29namespace {
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/// ```
45struct 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 extracted;
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
114private:
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/// ```
126struct 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 extracted =
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.
157Value 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.
182struct 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
242private:
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.
249struct 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
332private:
333 unsigned subgroupSize = 0;
334 unsigned shuffleBitwidth = 0;
335 bool matchClustered = false;
336};
337} // namespace
338
339void 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
347void 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
355void 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