1//===- UnsignedWhenEquivalent.cpp - Pass to replace signed operations with
2// unsigned
3// ones when all their arguments and results are statically non-negative --===//
4//
5// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
6// See https://llvm.org/LICENSE.txt for license information.
7// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
8//
9//===----------------------------------------------------------------------===//
10
11#include "mlir/Analysis/DataFlow/ConstantPropagationAnalysis.h"
12#include "mlir/Dialect/Arith/Transforms/Passes.h"
13
14#include "mlir/Analysis/DataFlow/DeadCodeAnalysis.h"
15#include "mlir/Analysis/DataFlow/IntegerRangeAnalysis.h"
16#include "mlir/Dialect/Arith/IR/Arith.h"
17#include "mlir/IR/PatternMatch.h"
18#include "mlir/Transforms/WalkPatternRewriteDriver.h"
19
20namespace mlir {
21namespace arith {
22#define GEN_PASS_DEF_ARITHUNSIGNEDWHENEQUIVALENTPASS
23#include "mlir/Dialect/Arith/Transforms/Passes.h.inc"
24} // namespace arith
25} // namespace mlir
26
27using namespace mlir;
28using namespace mlir::arith;
29using namespace mlir::dataflow;
30
31/// Succeeds when the comparison predicate is a signed operation and all the
32/// operands are non-negative, indicating that the cmpi operation `op` can have
33/// its predicate changed to an unsigned equivalent.
34static LogicalResult isCmpIConvertable(DataFlowSolver &solver, CmpIOp op) {
35 CmpIPredicate pred = op.getPredicate();
36 switch (pred) {
37 case CmpIPredicate::sle:
38 case CmpIPredicate::slt:
39 case CmpIPredicate::sge:
40 case CmpIPredicate::sgt:
41 return success(IsSuccess: llvm::all_of(Range: op.getOperands(), P: [&solver](Value v) -> bool {
42 return succeeded(Result: staticallyNonNegative(solver, v));
43 }));
44 default:
45 return failure();
46 }
47}
48
49/// Return the unsigned equivalent of a signed comparison predicate,
50/// or the predicate itself if there is none.
51static CmpIPredicate toUnsignedPred(CmpIPredicate pred) {
52 switch (pred) {
53 case CmpIPredicate::sle:
54 return CmpIPredicate::ule;
55 case CmpIPredicate::slt:
56 return CmpIPredicate::ult;
57 case CmpIPredicate::sge:
58 return CmpIPredicate::uge;
59 case CmpIPredicate::sgt:
60 return CmpIPredicate::ugt;
61 default:
62 return pred;
63 }
64}
65
66namespace {
67class DataFlowListener : public RewriterBase::Listener {
68public:
69 DataFlowListener(DataFlowSolver &s) : s(s) {}
70
71protected:
72 void notifyOperationErased(Operation *op) override {
73 s.eraseState(anchor: s.getProgramPointAfter(op));
74 for (Value res : op->getResults())
75 s.eraseState(anchor: res);
76 }
77
78 DataFlowSolver &s;
79};
80
81// TODO: IntegerRangeAnalysis internally assumes index is 64bit and this pattern
82// (via staticallyNonNegative) relies on this. These transformations may not be
83// valid for 32bit index, need more investigation.
84
85template <typename Signed, typename Unsigned>
86struct ConvertOpToUnsigned final : OpRewritePattern<Signed> {
87 ConvertOpToUnsigned(MLIRContext *context, DataFlowSolver &s)
88 : OpRewritePattern<Signed>(context), solver(s) {}
89
90 LogicalResult matchAndRewrite(Signed op, PatternRewriter &rw) const override {
91 if (failed(
92 Result: staticallyNonNegative(solver&: this->solver, op: static_cast<Operation *>(op))))
93 return failure();
94
95 typename Unsigned::Properties properties{};
96 Unsigned::populateDefaultProperties(
97 OperationName(Unsigned::getOperationName(), rw.getContext()),
98 properties);
99 rw.replaceOpWithNewOp<Unsigned>(
100 op, op->getResultTypes(), op->getOperands(), properties,
101 op->getDiscardableAttrDictionary().getValue());
102 return success();
103 }
104
105private:
106 DataFlowSolver &solver;
107};
108
109struct ConvertDivSIToUnsigned final : OpRewritePattern<DivSIOp> {
110 ConvertDivSIToUnsigned(MLIRContext *context, DataFlowSolver &s)
111 : OpRewritePattern<DivSIOp>(context), solver(s) {}
112
113 LogicalResult matchAndRewrite(DivSIOp op,
114 PatternRewriter &rw) const override {
115 if (failed(Result: staticallyNonNegative(solver, op: op.getOperation())))
116 return failure();
117
118 auto newOp = DivUIOp::create(builder&: rw, location: op.getLoc(), result: op.getType(), lhs: op.getLhs(),
119 rhs: op.getRhs(), isExact: op.getIsExactAttr());
120 newOp->setDiscardableAttrs(op->getDiscardableAttrDictionary());
121 rw.replaceOp(op, newOp);
122 return success();
123 }
124
125private:
126 DataFlowSolver &solver;
127};
128
129struct ConvertCmpIToUnsigned final : OpRewritePattern<CmpIOp> {
130 ConvertCmpIToUnsigned(MLIRContext *context, DataFlowSolver &s)
131 : OpRewritePattern<CmpIOp>(context), solver(s) {}
132
133 LogicalResult matchAndRewrite(CmpIOp op, PatternRewriter &rw) const override {
134 if (failed(Result: isCmpIConvertable(solver&: this->solver, op)))
135 return failure();
136
137 rw.replaceOpWithNewOp<CmpIOp>(op, args: toUnsignedPred(pred: op.getPredicate()),
138 args: op.getLhs(), args: op.getRhs());
139 return success();
140 }
141
142private:
143 DataFlowSolver &solver;
144};
145
146struct ArithUnsignedWhenEquivalentPass
147 : public arith::impl::ArithUnsignedWhenEquivalentPassBase<
148 ArithUnsignedWhenEquivalentPass> {
149
150 void runOnOperation() override {
151 Operation *op = getOperation();
152 MLIRContext *ctx = op->getContext();
153 DataFlowSolver solver;
154 solver.load<SparseConstantPropagation>();
155 solver.load<DeadCodeAnalysis>();
156 solver.load<IntegerRangeAnalysis>();
157 if (failed(Result: solver.initializeAndRun(top: op)))
158 return signalPassFailure();
159
160 DataFlowListener listener(solver);
161
162 RewritePatternSet patterns(ctx);
163 populateUnsignedWhenEquivalentPatterns(patterns, solver);
164
165 walkAndApplyPatterns(op, patterns: std::move(patterns), listener: &listener);
166 }
167};
168} // end anonymous namespace
169
170void mlir::arith::populateUnsignedWhenEquivalentPatterns(
171 RewritePatternSet &patterns, DataFlowSolver &solver) {
172 patterns.add<ConvertDivSIToUnsigned,
173 ConvertOpToUnsigned<CeilDivSIOp, CeilDivUIOp>,
174 ConvertOpToUnsigned<FloorDivSIOp, DivUIOp>,
175 ConvertOpToUnsigned<RemSIOp, RemUIOp>,
176 ConvertOpToUnsigned<MinSIOp, MinUIOp>,
177 ConvertOpToUnsigned<MaxSIOp, MaxUIOp>,
178 ConvertOpToUnsigned<ExtSIOp, ExtUIOp>, ConvertCmpIToUnsigned>(
179 arg: patterns.getContext(), args&: solver);
180}
181