1//===----------------------------------------------------------------------===//
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#include "mlir/Conversion/ArithCommon/CeilFloorDivExpansion.h"
10#include "mlir/Dialect/Arith/IR/Arith.h"
11#include "mlir/IR/PatternMatch.h"
12#include "mlir/IR/TypeUtilities.h"
13
14using namespace mlir;
15
16/// Create an integer or index constant.
17static Value createConst(Location loc, Type type, int value,
18 PatternRewriter &rewriter) {
19 auto attr = rewriter.getIntegerAttr(type: getElementTypeOrSelf(type), value);
20 if (auto shapedTy = dyn_cast<ShapedType>(Val&: type)) {
21 return arith::ConstantOp::create(builder&: rewriter, location: loc,
22 value: DenseElementsAttr::get(type: shapedTy, values: attr));
23 }
24 return arith::ConstantOp::create(builder&: rewriter, location: loc, value: attr);
25}
26
27namespace {
28/// Expands CeilDivUIOp (n, m) into
29/// n == 0 ? 0 : ((n-1) / m) + 1
30struct CeilDivUIOpConverter : public OpRewritePattern<arith::CeilDivUIOp> {
31 using Base::Base;
32 LogicalResult matchAndRewrite(arith::CeilDivUIOp op,
33 PatternRewriter &rewriter) const final {
34 Location loc = op.getLoc();
35 Value a = op.getLhs();
36 Value b = op.getRhs();
37 Value zero = createConst(loc, type: a.getType(), value: 0, rewriter);
38 Value compare =
39 arith::CmpIOp::create(builder&: rewriter, location: loc, predicate: arith::CmpIPredicate::eq, lhs: a, rhs: zero);
40 Value one = createConst(loc, type: a.getType(), value: 1, rewriter);
41 Value minusOne = arith::SubIOp::create(builder&: rewriter, location: loc, lhs: a, rhs: one);
42 Value quotient = arith::DivUIOp::create(builder&: rewriter, location: loc, lhs: minusOne, rhs: b);
43 Value plusOne = arith::AddIOp::create(builder&: rewriter, location: loc, lhs: quotient, rhs: one);
44 rewriter.replaceOpWithNewOp<arith::SelectOp>(op, args&: compare, args&: zero, args&: plusOne);
45 return success();
46 }
47};
48
49/// Expands CeilDivSIOp (a, b) into
50/// z = a / b
51/// if (z * b != a && (a < 0) == (b < 0)) {
52/// return z + 1;
53/// } else {
54/// return z;
55/// }
56struct CeilDivSIOpConverter : public OpRewritePattern<arith::CeilDivSIOp> {
57 using Base::Base;
58 LogicalResult matchAndRewrite(arith::CeilDivSIOp op,
59 PatternRewriter &rewriter) const final {
60 Location loc = op.getLoc();
61 Type type = op.getType();
62 Value a = op.getLhs();
63 Value b = op.getRhs();
64
65 Value zero = createConst(loc, type, value: 0, rewriter);
66 Value one = createConst(loc, type, value: 1, rewriter);
67
68 Value quotient = arith::DivSIOp::create(builder&: rewriter, location: loc, lhs: a, rhs: b);
69 Value product = arith::MulIOp::create(builder&: rewriter, location: loc, lhs: quotient, rhs: b);
70 Value notEqualDivisor = arith::CmpIOp::create(
71 builder&: rewriter, location: loc, predicate: arith::CmpIPredicate::ne, lhs: a, rhs: product);
72
73 Value aNeg = arith::CmpIOp::create(builder&: rewriter, location: loc, predicate: arith::CmpIPredicate::slt,
74 lhs: a, rhs: zero);
75 Value bNeg = arith::CmpIOp::create(builder&: rewriter, location: loc, predicate: arith::CmpIPredicate::slt,
76 lhs: b, rhs: zero);
77
78 Value signEqual = arith::CmpIOp::create(
79 builder&: rewriter, location: loc, predicate: arith::CmpIPredicate::eq, lhs: aNeg, rhs: bNeg);
80 Value cond =
81 arith::AndIOp::create(builder&: rewriter, location: loc, lhs: notEqualDivisor, rhs: signEqual);
82
83 Value quotientPlusOne = arith::AddIOp::create(builder&: rewriter, location: loc, lhs: quotient, rhs: one);
84
85 rewriter.replaceOpWithNewOp<arith::SelectOp>(op, args&: cond, args&: quotientPlusOne,
86 args&: quotient);
87 return success();
88 }
89};
90
91/// Expands FloorDivSIOp (x, y) into
92/// z = x / y
93/// if (z * y != x && (x < 0) != (y < 0)) {
94/// return z - 1;
95/// } else {
96/// return z;
97/// }
98struct FloorDivSIOpConverter : public OpRewritePattern<arith::FloorDivSIOp> {
99 using Base::Base;
100 LogicalResult matchAndRewrite(arith::FloorDivSIOp op,
101 PatternRewriter &rewriter) const final {
102 Location loc = op.getLoc();
103 Type type = op.getType();
104 Value a = op.getLhs();
105 Value b = op.getRhs();
106
107 Value quotient = arith::DivSIOp::create(builder&: rewriter, location: loc, lhs: a, rhs: b);
108 Value product = arith::MulIOp::create(builder&: rewriter, location: loc, lhs: quotient, rhs: b);
109 Value notEqualDivisor = arith::CmpIOp::create(
110 builder&: rewriter, location: loc, predicate: arith::CmpIPredicate::ne, lhs: a, rhs: product);
111 Value zero = createConst(loc, type, value: 0, rewriter);
112
113 Value aNeg = arith::CmpIOp::create(builder&: rewriter, location: loc, predicate: arith::CmpIPredicate::slt,
114 lhs: a, rhs: zero);
115 Value bNeg = arith::CmpIOp::create(builder&: rewriter, location: loc, predicate: arith::CmpIPredicate::slt,
116 lhs: b, rhs: zero);
117
118 Value signOpposite = arith::CmpIOp::create(
119 builder&: rewriter, location: loc, predicate: arith::CmpIPredicate::ne, lhs: aNeg, rhs: bNeg);
120 Value cond =
121 arith::AndIOp::create(builder&: rewriter, location: loc, lhs: notEqualDivisor, rhs: signOpposite);
122
123 Value minusOne = createConst(loc, type, value: -1, rewriter);
124 Value quotientMinusOne =
125 arith::AddIOp::create(builder&: rewriter, location: loc, lhs: quotient, rhs: minusOne);
126
127 rewriter.replaceOpWithNewOp<arith::SelectOp>(op, args&: cond, args&: quotientMinusOne,
128 args&: quotient);
129 return success();
130 }
131};
132} // namespace
133
134void mlir::arith::populateCeilFloorDivExpandOpsPatterns(
135 RewritePatternSet &patterns) {
136 patterns
137 .add<CeilDivSIOpConverter, CeilDivUIOpConverter, FloorDivSIOpConverter>(
138 arg: patterns.getContext());
139}
140