1//===- SPIRVWebGPUTransforms.cpp - WebGPU-specific transforms -------------===//
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// This file implements SPIR-V transforms used when targetting WebGPU.
10//
11//===----------------------------------------------------------------------===//
12
13#include "mlir/Dialect/SPIRV/Transforms/SPIRVWebGPUTransforms.h"
14#include "mlir/Dialect/SPIRV/IR/SPIRVOps.h"
15#include "mlir/Dialect/SPIRV/Transforms/Passes.h"
16#include "mlir/IR/BuiltinAttributes.h"
17#include "mlir/IR/Location.h"
18#include "mlir/IR/PatternMatch.h"
19#include "mlir/IR/TypeUtilities.h"
20#include "mlir/Transforms/GreedyPatternRewriteDriver.h"
21#include "llvm/ADT/ArrayRef.h"
22#include "llvm/ADT/STLExtras.h"
23#include "llvm/Support/FormatVariadic.h"
24
25#include <array>
26#include <cstdint>
27
28namespace mlir {
29namespace spirv {
30#define GEN_PASS_DEF_SPIRVWEBGPUPREPAREPASS
31#include "mlir/Dialect/SPIRV/Transforms/Passes.h.inc"
32} // namespace spirv
33} // namespace mlir
34
35namespace mlir {
36namespace spirv {
37namespace {
38//===----------------------------------------------------------------------===//
39// Helpers
40//===----------------------------------------------------------------------===//
41static Attribute getScalarOrSplatAttr(Type type, int64_t value) {
42 APInt sizedValue(getElementTypeOrSelf(type).getIntOrFloatBitWidth(), value);
43 if (auto intTy = dyn_cast<IntegerType>(Val&: type))
44 return IntegerAttr::get(type: intTy, value: sizedValue);
45
46 return SplatElementsAttr::get(type: cast<ShapedType>(Val&: type), values: sizedValue);
47}
48
49static Value lowerExtendedMultiplication(Operation *mulOp,
50 PatternRewriter &rewriter, Value lhs,
51 Value rhs, bool signExtendArguments) {
52 Location loc = mulOp->getLoc();
53 Type argTy = lhs.getType();
54 // Emulate 64-bit multiplication by splitting each input element of type i32
55 // into 2 16-bit digits of type i32. This is so that the intermediate
56 // multiplications and additions do not overflow. We extract these 16-bit
57 // digits from i32 vector elements by masking (low digit) and shifting right
58 // (high digit).
59 //
60 // The multiplication algorithm used is the standard (long) multiplication.
61 // Multiplying two i32 integers produces 64 bits of result, i.e., 4 16-bit
62 // digits.
63 // - With zero-extended arguments, we end up emitting only 4 multiplications
64 // and 4 additions after constant folding.
65 // - With sign-extended arguments, we end up emitting 8 multiplications and
66 // and 12 additions after CSE.
67 Value cstLowMask = ConstantOp::create(
68 builder&: rewriter, location: loc, constant: lhs.getType(), value: getScalarOrSplatAttr(type: argTy, value: (1 << 16) - 1));
69 auto getLowDigit = [&rewriter, loc, cstLowMask](Value val) {
70 return BitwiseAndOp::create(builder&: rewriter, location: loc, operand1: val, operand2: cstLowMask);
71 };
72
73 Value cst16 = ConstantOp::create(builder&: rewriter, location: loc, constant: lhs.getType(),
74 value: getScalarOrSplatAttr(type: argTy, value: 16));
75 auto getHighDigit = [&rewriter, loc, cst16](Value val) {
76 return ShiftRightLogicalOp::create(builder&: rewriter, location: loc, operand1: val, operand2: cst16);
77 };
78
79 auto getSignDigit = [&rewriter, loc, cst16, &getHighDigit](Value val) {
80 // We only need to shift arithmetically by 15, but the extra
81 // sign-extension bit will be truncated by the logical shift, so this is
82 // fine. We do not have to introduce an extra constant since any
83 // value in [15, 32) would do.
84 return getHighDigit(
85 ShiftRightArithmeticOp::create(builder&: rewriter, location: loc, operand1: val, operand2: cst16));
86 };
87
88 Value cst0 = ConstantOp::create(builder&: rewriter, location: loc, constant: lhs.getType(),
89 value: getScalarOrSplatAttr(type: argTy, value: 0));
90
91 Value lhsLow = getLowDigit(lhs);
92 Value lhsHigh = getHighDigit(lhs);
93 Value lhsExt = signExtendArguments ? getSignDigit(lhs) : cst0;
94 Value rhsLow = getLowDigit(rhs);
95 Value rhsHigh = getHighDigit(rhs);
96 Value rhsExt = signExtendArguments ? getSignDigit(rhs) : cst0;
97
98 std::array<Value, 4> lhsDigits = {lhsLow, lhsHigh, lhsExt, lhsExt};
99 std::array<Value, 4> rhsDigits = {rhsLow, rhsHigh, rhsExt, rhsExt};
100 std::array<Value, 4> resultDigits = {cst0, cst0, cst0, cst0};
101
102 for (auto [i, lhsDigit] : llvm::enumerate(First&: lhsDigits)) {
103 for (auto [j, rhsDigit] : llvm::enumerate(First&: rhsDigits)) {
104 if (i + j >= resultDigits.size())
105 continue;
106
107 if (lhsDigit == cst0 || rhsDigit == cst0)
108 continue;
109
110 Value &thisResDigit = resultDigits[i + j];
111 Value mul = IMulOp::create(builder&: rewriter, location: loc, operand1: lhsDigit, operand2: rhsDigit);
112 Value current = rewriter.createOrFold<IAddOp>(location: loc, args&: thisResDigit, args&: mul);
113 thisResDigit = getLowDigit(current);
114
115 if (i + j + 1 != resultDigits.size()) {
116 Value &nextResDigit = resultDigits[i + j + 1];
117 Value carry = rewriter.createOrFold<IAddOp>(location: loc, args&: nextResDigit,
118 args: getHighDigit(current));
119 nextResDigit = carry;
120 }
121 }
122 }
123
124 auto combineDigits = [loc, cst16, &rewriter](Value low, Value high) {
125 Value highBits = ShiftLeftLogicalOp::create(builder&: rewriter, location: loc, operand1: high, operand2: cst16);
126 return BitwiseOrOp::create(builder&: rewriter, location: loc, operand1: low, operand2: highBits);
127 };
128 Value low = combineDigits(resultDigits[0], resultDigits[1]);
129 Value high = combineDigits(resultDigits[2], resultDigits[3]);
130
131 return CompositeConstructOp::create(builder&: rewriter, location: loc,
132 result: mulOp->getResultTypes().front(),
133 constituents: llvm::ArrayRef({low, high}));
134}
135
136//===----------------------------------------------------------------------===//
137// Rewrite Patterns
138//===----------------------------------------------------------------------===//
139
140template <typename MulExtendedOp, bool SignExtendArguments>
141struct ExpandMulExtendedPattern final : OpRewritePattern<MulExtendedOp> {
142 using OpRewritePattern<MulExtendedOp>::OpRewritePattern;
143
144 LogicalResult matchAndRewrite(MulExtendedOp op,
145 PatternRewriter &rewriter) const override {
146 Location loc = op->getLoc();
147 Value lhs = op.getOperand1();
148 Value rhs = op.getOperand2();
149
150 // Currently, WGSL only supports 32-bit integer types. Any other integer
151 // types should already have been promoted/demoted to i32.
152 auto elemTy = cast<IntegerType>(Val: getElementTypeOrSelf(type: lhs.getType()));
153 if (elemTy.getIntOrFloatBitWidth() != 32)
154 return rewriter.notifyMatchFailure(
155 arg&: loc,
156 msg: llvm::formatv(Fmt: "Unexpected integer type for WebGPU: '{0}'", Vals&: elemTy));
157
158 Value mul = lowerExtendedMultiplication(op, rewriter, lhs, rhs,
159 SignExtendArguments);
160 rewriter.replaceOp(op, mul);
161 return success();
162 }
163};
164
165using ExpandSMulExtendedPattern =
166 ExpandMulExtendedPattern<SMulExtendedOp, true>;
167using ExpandUMulExtendedPattern =
168 ExpandMulExtendedPattern<UMulExtendedOp, false>;
169
170template <typename Op, typename ArithOp>
171struct ExpandAddCarryOrSubBorrowPattern final : OpRewritePattern<Op> {
172 using OpRewritePattern<Op>::OpRewritePattern;
173
174 LogicalResult matchAndRewrite(Op op,
175 PatternRewriter &rewriter) const override {
176 Location loc = op->getLoc();
177 Value lhs = op.getOperand1();
178 Value rhs = op.getOperand2();
179
180 // Currently, WGSL only supports 32-bit integer types. Any other integer
181 // types should already have been promoted/demoted to i32.
182 Type argTy = lhs.getType();
183 auto elemTy = cast<IntegerType>(Val: getElementTypeOrSelf(type: argTy));
184 if (elemTy.getIntOrFloatBitWidth() != 32)
185 return rewriter.notifyMatchFailure(
186 arg&: loc,
187 msg: llvm::formatv(Fmt: "Unexpected integer type for WebGPU: '{0}'", Vals&: elemTy));
188
189 Value one = ConstantOp::create(builder&: rewriter, location: loc, constant: argTy,
190 value: getScalarOrSplatAttr(type: argTy, value: 1));
191 Value zero = ConstantOp::create(builder&: rewriter, location: loc, constant: argTy,
192 value: getScalarOrSplatAttr(type: argTy, value: 0));
193
194 Value out = ArithOp::create(rewriter, loc, lhs, rhs);
195 // For add: carry iff out < lhs (unsigned overflow).
196 // For sub: borrow iff lhs < rhs (unsigned underflow).
197 Value cmp;
198 if constexpr (std::is_same_v<Op, IAddCarryOp>)
199 cmp = ULessThanOp::create(builder&: rewriter, location: loc, operand1: out, operand2: lhs);
200 else
201 cmp = ULessThanOp::create(builder&: rewriter, location: loc, operand1: lhs, operand2: rhs);
202 Value flag = SelectOp::create(builder&: rewriter, location: loc, condition: cmp, true_value: one, false_value: zero);
203
204 Value result = CompositeConstructOp::create(rewriter, loc,
205 op->getResultTypes().front(),
206 llvm::ArrayRef({out, flag}));
207
208 rewriter.replaceOp(op, result);
209 return success();
210 }
211};
212
213using ExpandAddCarryPattern =
214 ExpandAddCarryOrSubBorrowPattern<IAddCarryOp, IAddOp>;
215using ExpandSubBorrowPattern =
216 ExpandAddCarryOrSubBorrowPattern<ISubBorrowOp, ISubOp>;
217
218struct ExpandIsInfPattern final : OpRewritePattern<IsInfOp> {
219 using Base::Base;
220
221 LogicalResult matchAndRewrite(IsInfOp op,
222 PatternRewriter &rewriter) const override {
223 // We assume values to be finite and turn `IsInf` info `false`.
224 rewriter.replaceOpWithNewOp<spirv::ConstantOp>(
225 op, args: op.getType(), args: getScalarOrSplatAttr(type: op.getType(), value: 0));
226 return success();
227 }
228};
229
230struct ExpandIsNanPattern final : OpRewritePattern<IsNanOp> {
231 using Base::Base;
232
233 LogicalResult matchAndRewrite(IsNanOp op,
234 PatternRewriter &rewriter) const override {
235 // We assume values to be finite and turn `IsNan` info `false`.
236 rewriter.replaceOpWithNewOp<spirv::ConstantOp>(
237 op, args: op.getType(), args: getScalarOrSplatAttr(type: op.getType(), value: 0));
238 return success();
239 }
240};
241
242//===----------------------------------------------------------------------===//
243// Passes
244//===----------------------------------------------------------------------===//
245struct WebGPUPreparePass final
246 : impl::SPIRVWebGPUPreparePassBase<WebGPUPreparePass> {
247 void runOnOperation() override {
248 RewritePatternSet patterns(&getContext());
249 populateSPIRVExpandExtendedMultiplicationPatterns(patterns);
250 populateSPIRVExpandNonFiniteArithmeticPatterns(patterns);
251
252 if (failed(Result: applyPatternsGreedily(op: getOperation(), patterns: std::move(patterns))))
253 signalPassFailure();
254 }
255};
256} // namespace
257
258//===----------------------------------------------------------------------===//
259// Public Interface
260//===----------------------------------------------------------------------===//
261void populateSPIRVExpandExtendedMultiplicationPatterns(
262 RewritePatternSet &patterns) {
263 // WGSL currently does not support extended multiplication ops, see:
264 // https://github.com/gpuweb/gpuweb/issues/1565.
265 patterns.add<ExpandSMulExtendedPattern, ExpandUMulExtendedPattern,
266 ExpandAddCarryPattern, ExpandSubBorrowPattern>(
267 arg: patterns.getContext());
268}
269
270void populateSPIRVExpandNonFiniteArithmeticPatterns(
271 RewritePatternSet &patterns) {
272 // WGSL currently does not support `isInf` and `isNan`, see:
273 // https://github.com/gpuweb/gpuweb/pull/2311.
274 patterns.add<ExpandIsInfPattern, ExpandIsNanPattern>(arg: patterns.getContext());
275}
276
277} // namespace spirv
278} // namespace mlir
279