MLIR 24.0.0git
AlgebraicSimplification.cpp
Go to the documentation of this file.
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
20#include "mlir/IR/Builders.h"
21#include "mlir/IR/Matchers.h"
23#include <climits>
24#include <limits>
25
26using namespace mlir;
27
28//----------------------------------------------------------------------------//
29// PowFOp strength reduction.
30//----------------------------------------------------------------------------//
31
32namespace {
33struct PowFStrengthReduction : public OpRewritePattern<math::PowFOp> {
34public:
35 using Base::Base;
36
37 LogicalResult matchAndRewrite(math::PowFOp op,
38 PatternRewriter &rewriter) const final;
39};
40} // namespace
41
42LogicalResult
43PowFStrengthReduction::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(op.getRhs(), m_Constant(&scalarExponent));
53 bool isVector = matchPattern(op.getRhs(), m_Constant(&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(value);
59
60 if (isVector && vectorExponent.isSplat())
61 return vectorExponent.getSplatValue<FloatAttr>()
62 .getValue()
63 .isExactlyValue(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>(op.getType()))
71 return vector::BroadcastOp::create(rewriter, loc, vec, value);
72 return value;
73 };
74
75 // Replace `pow(x, 1.0)` with `x`.
76 if (isExponentValue(1.0)) {
77 rewriter.replaceOp(op, 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, x, x, 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(rewriter, loc, x, x, fmf);
90 rewriter.replaceOpWithNewOp<arith::MulFOp>(op, x, square, 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 rewriter, loc,
98 rewriter.getFloatAttr(getElementTypeOrSelf(op.getType()), 1.0));
99 rewriter.replaceOpWithNewOp<arith::DivFOp>(op, bcast(one), x, 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, x, 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, x, 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(rewriter, loc, x, fmf);
118 Value powQuarter = math::SqrtOp::create(rewriter, loc, powHalf, fmf);
119 rewriter.replaceOpWithNewOp<arith::MulFOp>(op, powHalf, powQuarter, fmf);
120 return success();
121 }
122
123 return failure();
124}
125
126//----------------------------------------------------------------------------//
127// FPowIOp/IPowIOp strength reduction.
128//----------------------------------------------------------------------------//
129
130namespace {
131template <typename PowIOpTy, typename DivOpTy, typename MulOpTy>
132struct PowIStrengthReduction : public OpRewritePattern<PowIOpTy> {
133
134 unsigned exponentThreshold;
135
136public:
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
148template <typename PowIOpTy, typename DivOpTy, typename MulOpTy>
149LogicalResult
150PowIStrengthReduction<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(&exponent)))
158 return failure();
159
160 // Values outside int64_t exceed the strength reduction threshold.
161 if (!exponent.isSignedIntN(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(rewriter, loc,
202 rewriter.getFloatAttr(opType, 1.0));
203 } else if constexpr (std::is_same_v<PowIOpTy, complex::PowiOp>) {
204 auto complexTy = cast<ComplexType>(opType);
205 Type elementType = complexTy.getElementType();
206 auto realPart = rewriter.getFloatAttr(elementType, 1.0);
207 auto imagPart = rewriter.getFloatAttr(elementType, 0.0);
208 one = complex::ConstantOp::create(
209 rewriter, loc, complexTy, rewriter.getArrayAttr({realPart, imagPart}));
210 } else {
211 one = arith::ConstantOp::create(rewriter, loc,
212 rewriter.getIntegerAttr(opType, 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
259namespace {
260/// Replaces `exp(a) / exp(b)` with `exp(a - b)`, and likewise for `exp2`,
261/// trading a division and an exponential for a subtraction.
262template <typename ExpOpTy>
263struct ExpQuotientStrengthReduction : public OpRewritePattern<arith::DivFOp> {
264public:
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(fmf, 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(fmf, 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
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 patterns.getContext(), /*exponentThreshold=*/8);
341 patterns.add<ExpQuotientStrengthReduction<math::ExpOp>,
342 ExpQuotientStrengthReduction<math::Exp2Op>>(
343 patterns.getContext());
344}
return success()
lhs
IntegerAttr getIntegerAttr(Type type, int64_t value)
Definition Builders.cpp:237
FloatAttr getFloatAttr(Type type, double value)
Definition Builders.cpp:263
ArrayAttr getArrayAttr(ArrayRef< Attribute > value)
Definition Builders.cpp:275
A special type of RewriterBase that coordinates the application of a rewrite pattern on the current I...
MLIRContext * getContext() const
RewritePatternSet & add(ConstructorArg &&arg, ConstructorArgs &&...args)
Add an instance of each of the pattern types 'Ts' to the pattern list with the given arguments.
virtual void replaceOp(Operation *op, ValueRange newValues)
Replace the results of the given (original) operation with the specified list of values (replacements...
OpTy replaceOpWithNewOp(Operation *op, Args &&...args)
Replace the results of the given (original) op with a new op that is created without verification (re...
Include the generated interface declarations.
bool matchPattern(Value value, const Pattern &pattern)
Entry point for matching a pattern over a Value.
Definition Matchers.h:490
detail::constant_int_value_binder m_ConstantInt(IntegerAttr::ValueType *bind_value)
Matches a constant holding a scalar/vector/tensor integer (splat) and writes the integer value to bin...
Definition Matchers.h:527
void populateMathAlgebraicSimplificationPatterns(RewritePatternSet &patterns)
Type getElementTypeOrSelf(Type type)
Return the element type or return the type itself.
detail::constant_op_matcher m_Constant()
Matches a constant foldable operation.
Definition Matchers.h:369
OpRewritePattern is a wrapper around RewritePattern that allows for matching and rewriting against an...