| 1 | //===- AlgebraicSimplification.cpp - Simplify algebraic expressions -------===// |
| 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 rewrites based on the basic rules of algebra |
| 10 | // (Commutativity, associativity, etc...) and strength reductions for math |
| 11 | // operations. |
| 12 | // |
| 13 | //===----------------------------------------------------------------------===// |
| 14 | |
| 15 | #include "mlir/Dialect/Arith/IR/Arith.h" |
| 16 | #include "mlir/Dialect/Complex/IR/Complex.h" |
| 17 | #include "mlir/Dialect/Math/IR/Math.h" |
| 18 | #include "mlir/Dialect/Math/Transforms/Passes.h" |
| 19 | #include "mlir/Dialect/Vector/IR/VectorOps.h" |
| 20 | #include "mlir/IR/Builders.h" |
| 21 | #include "mlir/IR/Matchers.h" |
| 22 | #include "mlir/IR/TypeUtilities.h" |
| 23 | #include <climits> |
| 24 | #include <limits> |
| 25 | |
| 26 | using namespace mlir; |
| 27 | |
| 28 | //----------------------------------------------------------------------------// |
| 29 | // PowFOp strength reduction. |
| 30 | //----------------------------------------------------------------------------// |
| 31 | |
| 32 | namespace { |
| 33 | struct PowFStrengthReduction : public OpRewritePattern<math::PowFOp> { |
| 34 | public: |
| 35 | using Base::Base; |
| 36 | |
| 37 | LogicalResult matchAndRewrite(math::PowFOp op, |
| 38 | PatternRewriter &rewriter) const final; |
| 39 | }; |
| 40 | } // namespace |
| 41 | |
| 42 | LogicalResult |
| 43 | PowFStrengthReduction::matchAndRewrite(math::PowFOp op, |
| 44 | PatternRewriter &rewriter) const { |
| 45 | Location loc = op.getLoc(); |
| 46 | Value x = op.getLhs(); |
| 47 | arith::FastMathFlags fmf = op.getFastmathAttr().getValue(); |
| 48 | |
| 49 | FloatAttr scalarExponent; |
| 50 | DenseFPElementsAttr vectorExponent; |
| 51 | |
| 52 | bool isScalar = matchPattern(value: op.getRhs(), pattern: m_Constant(bind_value: &scalarExponent)); |
| 53 | bool isVector = matchPattern(value: op.getRhs(), pattern: m_Constant(bind_value: &vectorExponent)); |
| 54 | |
| 55 | // Returns true if exponent is a constant equal to `value`. |
| 56 | auto isExponentValue = [&](double value) -> bool { |
| 57 | if (isScalar) |
| 58 | return scalarExponent.getValue().isExactlyValue(V: value); |
| 59 | |
| 60 | if (isVector && vectorExponent.isSplat()) |
| 61 | return vectorExponent.getSplatValue<FloatAttr>() |
| 62 | .getValue() |
| 63 | .isExactlyValue(V: value); |
| 64 | |
| 65 | return false; |
| 66 | }; |
| 67 | |
| 68 | // Maybe broadcasts scalar value into vector type compatible with `op`. |
| 69 | auto bcast = [&](Value value) -> Value { |
| 70 | if (auto vec = dyn_cast<VectorType>(Val: op.getType())) |
| 71 | return vector::BroadcastOp::create(builder&: rewriter, location: loc, result: vec, source: value); |
| 72 | return value; |
| 73 | }; |
| 74 | |
| 75 | // Replace `pow(x, 1.0)` with `x`. |
| 76 | if (isExponentValue(1.0)) { |
| 77 | rewriter.replaceOp(op, newValues: x); |
| 78 | return success(); |
| 79 | } |
| 80 | |
| 81 | // Replace `pow(x, 2.0)` with `x * x`. |
| 82 | if (isExponentValue(2.0)) { |
| 83 | rewriter.replaceOpWithNewOp<arith::MulFOp>(op, args&: x, args&: x, args&: fmf); |
| 84 | return success(); |
| 85 | } |
| 86 | |
| 87 | // Replace `pow(x, 3.0)` with `x * x * x`. |
| 88 | if (isExponentValue(3.0)) { |
| 89 | Value square = arith::MulFOp::create(builder&: rewriter, location: loc, lhs: x, rhs: x, fastmath: fmf); |
| 90 | rewriter.replaceOpWithNewOp<arith::MulFOp>(op, args&: x, args&: square, args&: fmf); |
| 91 | return success(); |
| 92 | } |
| 93 | |
| 94 | // Replace `pow(x, -1.0)` with `1.0 / x`. |
| 95 | if (isExponentValue(-1.0)) { |
| 96 | Value one = arith::ConstantOp::create( |
| 97 | builder&: rewriter, location: loc, |
| 98 | value: rewriter.getFloatAttr(type: getElementTypeOrSelf(type: op.getType()), value: 1.0)); |
| 99 | rewriter.replaceOpWithNewOp<arith::DivFOp>(op, args: bcast(one), args&: x, args&: fmf); |
| 100 | return success(); |
| 101 | } |
| 102 | |
| 103 | // Replace `pow(x, 0.5)` with `sqrt(x)`. |
| 104 | if (isExponentValue(0.5)) { |
| 105 | rewriter.replaceOpWithNewOp<math::SqrtOp>(op, args&: x, args&: fmf); |
| 106 | return success(); |
| 107 | } |
| 108 | |
| 109 | // Replace `pow(x, -0.5)` with `rsqrt(x)`. |
| 110 | if (isExponentValue(-0.5)) { |
| 111 | rewriter.replaceOpWithNewOp<math::RsqrtOp>(op, args&: x, args&: fmf); |
| 112 | return success(); |
| 113 | } |
| 114 | |
| 115 | // Replace `pow(x, 0.75)` with `sqrt(sqrt(x)) * sqrt(x)`. |
| 116 | if (isExponentValue(0.75)) { |
| 117 | Value powHalf = math::SqrtOp::create(builder&: rewriter, location: loc, operand: x, fastmath: fmf); |
| 118 | Value powQuarter = math::SqrtOp::create(builder&: rewriter, location: loc, operand: powHalf, fastmath: fmf); |
| 119 | rewriter.replaceOpWithNewOp<arith::MulFOp>(op, args&: powHalf, args&: powQuarter, args&: fmf); |
| 120 | return success(); |
| 121 | } |
| 122 | |
| 123 | return failure(); |
| 124 | } |
| 125 | |
| 126 | //----------------------------------------------------------------------------// |
| 127 | // FPowIOp/IPowIOp strength reduction. |
| 128 | //----------------------------------------------------------------------------// |
| 129 | |
| 130 | namespace { |
| 131 | template <typename PowIOpTy, typename DivOpTy, typename MulOpTy> |
| 132 | struct PowIStrengthReduction : public OpRewritePattern<PowIOpTy> { |
| 133 | |
| 134 | unsigned exponentThreshold; |
| 135 | |
| 136 | public: |
| 137 | PowIStrengthReduction(MLIRContext *context, unsigned exponentThreshold = 3, |
| 138 | PatternBenefit benefit = 1, |
| 139 | ArrayRef<StringRef> generatedNames = {}) |
| 140 | : OpRewritePattern<PowIOpTy>(context, benefit, generatedNames), |
| 141 | exponentThreshold(exponentThreshold) {} |
| 142 | |
| 143 | LogicalResult matchAndRewrite(PowIOpTy op, |
| 144 | PatternRewriter &rewriter) const final; |
| 145 | }; |
| 146 | } // namespace |
| 147 | |
| 148 | template <typename PowIOpTy, typename DivOpTy, typename MulOpTy> |
| 149 | LogicalResult |
| 150 | PowIStrengthReduction<PowIOpTy, DivOpTy, MulOpTy>::matchAndRewrite( |
| 151 | PowIOpTy op, PatternRewriter &rewriter) const { |
| 152 | Location loc = op.getLoc(); |
| 153 | Value base = op.getLhs(); |
| 154 | |
| 155 | // Simplify cases with known exponent value. |
| 156 | APInt exponent; |
| 157 | if (!matchPattern(op.getRhs(), m_ConstantInt(bind_value: &exponent))) |
| 158 | return failure(); |
| 159 | |
| 160 | // Values outside int64_t exceed the strength reduction threshold. |
| 161 | if (!exponent.isSignedIntN(N: 64)) |
| 162 | return failure(); |
| 163 | int64_t exponentValue = exponent.getSExtValue(); |
| 164 | |
| 165 | // Compute abs(exponent) and check the threshold before creating any IR, |
| 166 | // so that returning failure() here does not violate the pattern API contract. |
| 167 | bool exponentIsNegative = false; |
| 168 | if (exponentValue < 0) { |
| 169 | exponentIsNegative = true; |
| 170 | // Integer division by zero is UB (unlike float/complex, where the |
| 171 | // division is defined and yields Inf). base isn't necessarily constant |
| 172 | // here, so defer negative-exponent IPowIOp to MathToFuncs's |
| 173 | // createElementIPowIFunc, which returns 0 for base == 0 without |
| 174 | // dividing. MathToFuncs does not lower index, so index keeps the |
| 175 | // strength reduction below. |
| 176 | if constexpr (std::is_same_v<PowIOpTy, math::IPowIOp>) |
| 177 | if (isa<IntegerType>(getElementTypeOrSelf(op.getType()))) |
| 178 | return failure(); |
| 179 | // INT64_MIN has no positive representation in int64_t, so negating it |
| 180 | // below would overflow. Bail out rather than negate. This is reached by |
| 181 | // FPowIOp, complex::PowiOp and index-typed IPowIOp. |
| 182 | if (exponentValue == std::numeric_limits<int64_t>::min()) |
| 183 | return failure(); |
| 184 | exponentValue *= -1; |
| 185 | } |
| 186 | |
| 187 | // Bail out if `abs(exponent)` exceeds the threshold (exponent==0 is free). |
| 188 | if (exponentValue != 0 && exponentValue > exponentThreshold) |
| 189 | return failure(); |
| 190 | |
| 191 | // Maybe broadcasts scalar value into vector type compatible with `op`. |
| 192 | auto bcast = [&loc, &op, &rewriter](Value value) -> Value { |
| 193 | if (auto vec = dyn_cast<VectorType>(op.getType())) |
| 194 | return vector::BroadcastOp::create(rewriter, loc, vec, value); |
| 195 | return value; |
| 196 | }; |
| 197 | |
| 198 | Value one; |
| 199 | Type opType = getElementTypeOrSelf(op.getType()); |
| 200 | if constexpr (std::is_same_v<PowIOpTy, math::FPowIOp>) { |
| 201 | one = arith::ConstantOp::create(builder&: rewriter, location: loc, |
| 202 | value: rewriter.getFloatAttr(type: opType, value: 1.0)); |
| 203 | } else if constexpr (std::is_same_v<PowIOpTy, complex::PowiOp>) { |
| 204 | auto complexTy = cast<ComplexType>(Val&: opType); |
| 205 | Type elementType = complexTy.getElementType(); |
| 206 | auto realPart = rewriter.getFloatAttr(type: elementType, value: 1.0); |
| 207 | auto imagPart = rewriter.getFloatAttr(type: elementType, value: 0.0); |
| 208 | one = complex::ConstantOp::create( |
| 209 | builder&: rewriter, location: loc, complex: complexTy, value: rewriter.getArrayAttr(value: {realPart, imagPart})); |
| 210 | } else { |
| 211 | one = arith::ConstantOp::create(builder&: rewriter, location: loc, |
| 212 | value: rewriter.getIntegerAttr(type: opType, value: 1)); |
| 213 | } |
| 214 | |
| 215 | // Replace `[fi]powi(x, 0)` with `1`. |
| 216 | if (exponentValue == 0) { |
| 217 | rewriter.replaceOp(op, bcast(one)); |
| 218 | return success(); |
| 219 | } |
| 220 | |
| 221 | Value result = base; |
| 222 | // Transform to naive sequence of multiplications: |
| 223 | // * For positive exponent case replace: |
| 224 | // `[fi]powi(x, positive_exponent)` |
| 225 | // with: |
| 226 | // x * x * x * ... |
| 227 | // * For negative exponent case replace: |
| 228 | // `[fi]powi(x, negative_exponent)` |
| 229 | // with: |
| 230 | // (1 / x) * (1 / x) * (1 / x) * ... |
| 231 | auto buildMul = [&](Value lhs, Value rhs) { |
| 232 | if constexpr (std::is_same_v<PowIOpTy, complex::PowiOp>) |
| 233 | return MulOpTy::create(rewriter, loc, op.getType(), lhs, rhs, |
| 234 | op.getFastmathAttr()); |
| 235 | else |
| 236 | return MulOpTy::create(rewriter, loc, lhs, rhs); |
| 237 | }; |
| 238 | for (unsigned i = 1; i < exponentValue; ++i) |
| 239 | result = buildMul(result, base); |
| 240 | |
| 241 | // Inverse the base for negative exponent, i.e. for |
| 242 | // `[fi]powi(x, negative_exponent)` set `x` to `1 / x`. |
| 243 | if (exponentIsNegative) { |
| 244 | if constexpr (std::is_same_v<PowIOpTy, complex::PowiOp>) |
| 245 | result = DivOpTy::create(rewriter, loc, op.getType(), bcast(one), result, |
| 246 | op.getFastmathAttr()); |
| 247 | else |
| 248 | result = DivOpTy::create(rewriter, loc, bcast(one), result); |
| 249 | } |
| 250 | |
| 251 | rewriter.replaceOp(op, result); |
| 252 | return success(); |
| 253 | } |
| 254 | |
| 255 | //----------------------------------------------------------------------------// |
| 256 | // ExpOp/Exp2Op quotient strength reduction. |
| 257 | //----------------------------------------------------------------------------// |
| 258 | |
| 259 | namespace { |
| 260 | /// Replaces `exp(a) / exp(b)` with `exp(a - b)`, and likewise for `exp2`, |
| 261 | /// trading a division and an exponential for a subtraction. |
| 262 | template <typename ExpOpTy> |
| 263 | struct ExpQuotientStrengthReduction : public OpRewritePattern<arith::DivFOp> { |
| 264 | public: |
| 265 | using Base::Base; |
| 266 | |
| 267 | LogicalResult matchAndRewrite(arith::DivFOp op, |
| 268 | PatternRewriter &rewriter) const final { |
| 269 | auto numerator = op.getLhs().getDefiningOp<ExpOpTy>(); |
| 270 | auto denominator = op.getRhs().getDefiningOp<ExpOpTy>(); |
| 271 | if (!numerator || !denominator) |
| 272 | return failure(); |
| 273 | |
| 274 | // The rewrite is only valid when the division may be turned into a |
| 275 | // reciprocal multiplication and then reassociated with the exponentials: |
| 276 | // exp(a) / exp(b) --> exp(a) * exp(-b) --> exp(a + -b) |
| 277 | // This mirrors LLVM's InstCombine, which reaches the same result with |
| 278 | // `arcp` for the first step and `reassoc` for the second. Note that the |
| 279 | // rewrite also changes the overflow behaviour: for a large `a == b` the |
| 280 | // original expression is `inf / inf`, i.e. NaN, while the folded one is |
| 281 | // `exp(0.0)`, i.e. 1.0. |
| 282 | arith::FastMathFlags fmf = op.getFastmath(); |
| 283 | if (!bitEnumContainsAll(bits: fmf, bit: arith::FastMathFlags::arcp | |
| 284 | arith::FastMathFlags::reassoc)) |
| 285 | return failure(); |
| 286 | |
| 287 | // The rewrite introduces a new exponential, so it is only profitable if at |
| 288 | // least one of the two it feeds on dies with the division; the exponential |
| 289 | // count then never grows while a division is traded for a subtraction. |
| 290 | // This is the fused equivalent of the `isOnlyUserOfAnyOperand()` check |
| 291 | // LLVM's InstCombine applies to `exp(X) * exp(Y) --> exp(X + Y)`. |
| 292 | Operation *divOp = op; |
| 293 | auto diesWithDivision = [divOp](Operation *exp) { |
| 294 | return llvm::all_of(exp->getUsers(), |
| 295 | [divOp](Operation *user) { return user == divOp; }); |
| 296 | }; |
| 297 | if (!diesWithDivision(numerator) && !diesWithDivision(denominator)) |
| 298 | return failure(); |
| 299 | |
| 300 | // `nnan` and `ninf` are assumptions about the values an operation sees, and |
| 301 | // neither new operation sees the values its source did, so they cannot be |
| 302 | // carried over: |
| 303 | // - the subtraction consumes the exponents instead of the exponentials. |
| 304 | // `ninf` holds for `exp(-inf) / exp(0.0)`, i.e. `0.0 / 1.0`, while the |
| 305 | // subtraction `-inf - 0.0` is infinite. |
| 306 | // - the new exponential may overflow where neither of the old ones does. |
| 307 | // For f32 `exp(80.0)` and `exp(-80.0)` are both finite while |
| 308 | // `exp(80.0 - -80.0)` is not. |
| 309 | // All remaining flags only license *how* a value may be computed, so they |
| 310 | // stay. Derive them separately for the two new operations. |
| 311 | constexpr arith::FastMathFlags valueAssumptions = |
| 312 | arith::FastMathFlags::nnan | arith::FastMathFlags::ninf; |
| 313 | |
| 314 | // The subtraction takes the place of the division. |
| 315 | arith::FastMathFlags subFmf = bitEnumClear(bits: fmf, bit: valueAssumptions); |
| 316 | |
| 317 | // The new exponential may not be given a weaker accuracy contract than the |
| 318 | // ones it replaces, so it only keeps the flags common to both of them. |
| 319 | arith::FastMathFlags expFmf = bitEnumClear( |
| 320 | numerator.getFastmath() & denominator.getFastmath(), valueAssumptions); |
| 321 | |
| 322 | Value exponent = |
| 323 | arith::SubFOp::create(rewriter, op.getLoc(), numerator.getOperand(), |
| 324 | denominator.getOperand(), subFmf); |
| 325 | rewriter.replaceOpWithNewOp<ExpOpTy>(op, exponent, expFmf); |
| 326 | return success(); |
| 327 | } |
| 328 | }; |
| 329 | } // namespace |
| 330 | |
| 331 | //----------------------------------------------------------------------------// |
| 332 | |
| 333 | void mlir::populateMathAlgebraicSimplificationPatterns( |
| 334 | RewritePatternSet &patterns) { |
| 335 | patterns.add< |
| 336 | PowFStrengthReduction, |
| 337 | PowIStrengthReduction<math::IPowIOp, arith::DivSIOp, arith::MulIOp>, |
| 338 | PowIStrengthReduction<math::FPowIOp, arith::DivFOp, arith::MulFOp>, |
| 339 | PowIStrengthReduction<complex::PowiOp, complex::DivOp, complex::MulOp>>( |
| 340 | arg: patterns.getContext(), /*exponentThreshold=*/args: 8); |
| 341 | patterns.add<ExpQuotientStrengthReduction<math::ExpOp>, |
| 342 | ExpQuotientStrengthReduction<math::Exp2Op>>( |
| 343 | arg: patterns.getContext()); |
| 344 | } |
| 345 | |