1//===- MathRsqrtApproximation.cpp - Approximate math.rsqrt with AVX -------===//
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 an approximation of `math.rsqrt` using the AVX
10// `vrsqrtps` instruction refined by one Newton-Raphson step.
11//
12//===----------------------------------------------------------------------===//
13
14#include "mlir/Dialect/Arith/IR/Arith.h"
15#include "mlir/Dialect/Math/IR/Math.h"
16#include "mlir/Dialect/Utils/IndexingUtils.h"
17#include "mlir/Dialect/Vector/IR/VectorOps.h"
18#include "mlir/Dialect/X86/Transforms.h"
19#include "mlir/Dialect/X86/X86Dialect.h"
20#include "mlir/IR/ImplicitLocOpBuilder.h"
21#include "mlir/IR/PatternMatch.h"
22#include "mlir/IR/TypeUtilities.h"
23
24using namespace mlir;
25
26// Expands and unrolls n-D vector operands into multiple fixed size 1-D vectors
27// and calls the compute function with 1-D vector operands. Stitches back all
28// results into the original n-D vector result.
29//
30// Examples: vectorWidth = 8
31// - vector<4x8xf32> unrolled 4 times
32// - vector<16xf32> expanded to vector<2x8xf32> and unrolled 2 times
33// - vector<4x16xf32> expanded to vector<4x2x8xf32> and unrolled 4*2 times
34//
35// It is the caller's responsibility to verify that the inner dimension is
36// divisible by the vectorWidth, and that all operands have the same vector
37// shape.
38static Value
39handleMultidimensionalVectors(ImplicitLocOpBuilder &builder,
40 ValueRange operands, int64_t vectorWidth,
41 llvm::function_ref<Value(ValueRange)> compute) {
42 assert(!operands.empty() && "operands must be not empty");
43 assert(vectorWidth > 0 && "vector width must be larger than 0");
44
45 VectorType inputType = cast<VectorType>(Val: operands[0].getType());
46 ArrayRef<int64_t> inputShape = inputType.getShape();
47
48 // If input shape matches target vector width, we can just call the
49 // user-provided compute function with the operands.
50 if (inputShape == llvm::ArrayRef(vectorWidth))
51 return compute(operands);
52
53 // Check if the inner dimension has to be expanded, or we can directly iterate
54 // over the outer dimensions of the vector.
55 int64_t innerDim = inputShape.back();
56 int64_t expansionDim = innerDim / vectorWidth;
57 assert((innerDim % vectorWidth == 0) && "invalid inner dimension size");
58
59 // Maybe expand operands to the higher rank vector shape that we'll use to
60 // iterate over and extract one dimensional vectors.
61 SmallVector<int64_t> expandedShape(inputShape);
62 SmallVector<Value> expandedOperands(operands);
63
64 if (expansionDim > 1) {
65 // Expand shape from [..., innerDim] to [..., expansionDim, vectorWidth].
66 expandedShape.insert(I: expandedShape.end() - 1, Elt: expansionDim);
67 expandedShape.back() = vectorWidth;
68
69 for (unsigned i = 0; i < operands.size(); ++i) {
70 auto operand = operands[i];
71 auto eltType = cast<VectorType>(Val: operand.getType()).getElementType();
72 auto expandedType = VectorType::get(shape: expandedShape, elementType: eltType);
73 expandedOperands[i] =
74 vector::ShapeCastOp::create(builder, result: expandedType, source: operand);
75 }
76 }
77
78 // Iterate over all outer dimensions of the compute shape vector type.
79 auto iterationDims = ArrayRef<int64_t>(expandedShape).drop_back();
80 int64_t maxIndex = computeMaxLinearIndex(basis: iterationDims);
81 auto strides = computeStrides(sizes: iterationDims);
82
83 // Compute results for each one dimensional vector.
84 SmallVector<Value> results(maxIndex);
85
86 for (int64_t i = 0; i < maxIndex; ++i) {
87 auto offsets = delinearize(linearIndex: i, strides);
88
89 SmallVector<Value> extracted(expandedOperands.size());
90 for (const auto &tuple : llvm::enumerate(First&: expandedOperands))
91 extracted[tuple.index()] =
92 vector::ExtractOp::create(builder, source: tuple.value(), position: offsets);
93
94 results[i] = compute(extracted);
95 }
96
97 // Stitch results together into one large vector.
98 Type resultEltType = cast<VectorType>(Val: results[0].getType()).getElementType();
99 Type resultExpandedType = VectorType::get(shape: expandedShape, elementType: resultEltType);
100 Value result = arith::ConstantOp::create(
101 builder, result: resultExpandedType, value: builder.getZeroAttr(type: resultExpandedType));
102
103 for (int64_t i = 0; i < maxIndex; ++i)
104 result = vector::InsertOp::create(builder, valueToStore: results[i], dest: result,
105 position: delinearize(linearIndex: i, strides));
106
107 // Reshape back to the original vector shape.
108 return vector::ShapeCastOp::create(
109 builder, result: VectorType::get(shape: inputShape, elementType: resultEltType), source: result);
110}
111
112namespace {
113struct RsqrtApproximation : public OpRewritePattern<math::RsqrtOp> {
114 using Base::Base;
115
116 LogicalResult matchAndRewrite(math::RsqrtOp op,
117 PatternRewriter &rewriter) const final;
118};
119} // namespace
120
121LogicalResult
122RsqrtApproximation::matchAndRewrite(math::RsqrtOp op,
123 PatternRewriter &rewriter) const {
124 if (!getElementTypeOrSelf(val: op.getOperand()).isF32())
125 return rewriter.notifyMatchFailure(arg&: op, msg: "unsupported operand type");
126
127 // Only support already-vectorized rsqrt's.
128 auto vectorType = dyn_cast<VectorType>(Val: op.getOperand().getType());
129 if (!vectorType || vectorType.getRank() == 0 ||
130 vectorType.getShape().back() % 8 != 0)
131 return rewriter.notifyMatchFailure(arg&: op, msg: "unsupported operand type");
132
133 ImplicitLocOpBuilder builder(op->getLoc(), rewriter);
134 auto bcastF32FromBits = [&](uint32_t bits) -> Value {
135 Value i32Value = arith::ConstantOp::create(
136 builder, value: builder.getI32IntegerAttr(value: static_cast<int32_t>(bits)));
137 Value f32Value =
138 arith::BitcastOp::create(builder, out: builder.getF32Type(), in: i32Value);
139 return vector::BroadcastOp::create(builder, result: vectorType, source: f32Value);
140 };
141 auto bcastF32 = [&](float value) -> Value {
142 Value f32Value =
143 arith::ConstantOp::create(builder, value: builder.getF32FloatAttr(value));
144 return vector::BroadcastOp::create(builder, result: vectorType, source: f32Value);
145 };
146
147 Value cstPosInf = bcastF32FromBits(0x7f800000u);
148 Value cstOnePointFive = bcastF32(1.5f);
149 Value cstNegHalf = bcastF32(-0.5f);
150 Value cstMinNormPos = bcastF32FromBits(0x00800000u);
151
152 Value negHalf = arith::MulFOp::create(builder, lhs: op.getOperand(), rhs: cstNegHalf);
153
154 // Select only the inverse sqrt of positive normals (denormals are
155 // flushed to zero).
156 Value ltMinMask = arith::CmpFOp::create(builder, predicate: arith::CmpFPredicate::OLT,
157 lhs: op.getOperand(), rhs: cstMinNormPos);
158 Value infMask = arith::CmpFOp::create(builder, predicate: arith::CmpFPredicate::OEQ,
159 lhs: op.getOperand(), rhs: cstPosInf);
160 Value notNormalFiniteMask = arith::OrIOp::create(builder, lhs: ltMinMask, rhs: infMask);
161
162 // Compute an approximate result.
163 Value yApprox = handleMultidimensionalVectors(
164 builder, operands: op->getOperands(), vectorWidth: 8, compute: [&builder](ValueRange operands) -> Value {
165 return x86::avx::RsqrtOp::create(builder, operands);
166 });
167
168 // Do a single step of Newton-Raphson iteration to improve the approximation.
169 // This uses the formula y_{n+1} = y_n * (1.5 - y_n * (0.5 * x) * y_n).
170 // It is essential to evaluate the inner term like this because forming
171 // y_n^2 may over- or underflow.
172 Value inner = arith::MulFOp::create(builder, lhs: negHalf, rhs: yApprox);
173 Value fma = math::FmaOp::create(builder, a: yApprox, b: inner, c: cstOnePointFive);
174 Value yNewton = arith::MulFOp::create(builder, lhs: yApprox, rhs: fma);
175
176 // Select the result of the Newton-Raphson step for positive normal arguments.
177 // For other arguments, choose the output of the intrinsic. This will
178 // return rsqrt(+inf) = 0, rsqrt(x) = NaN if x < 0, and rsqrt(x) = +inf if
179 // x is zero or a positive denormalized float (equivalent to flushing positive
180 // denormalized inputs to zero).
181 Value res =
182 arith::SelectOp::create(builder, condition: notNormalFiniteMask, true_value: yApprox, false_value: yNewton);
183 rewriter.replaceOp(op, newValues: res);
184
185 return success();
186}
187
188void mlir::x86::populateMathRsqrtApproximationPatterns(
189 RewritePatternSet &patterns) {
190 patterns.add<RsqrtApproximation>(arg: patterns.getContext());
191}
192