| 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 | |
| 24 | using 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. |
| 38 | static Value |
| 39 | handleMultidimensionalVectors(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> (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 | |
| 112 | namespace { |
| 113 | struct 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 | |
| 121 | LogicalResult |
| 122 | RsqrtApproximation::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 | |
| 188 | void mlir::x86::populateMathRsqrtApproximationPatterns( |
| 189 | RewritePatternSet &patterns) { |
| 190 | patterns.add<RsqrtApproximation>(arg: patterns.getContext()); |
| 191 | } |
| 192 | |