| 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 | |
| 20 | namespace mlir { |
| 21 | namespace arith { |
| 22 | #define GEN_PASS_DEF_ARITHUNSIGNEDWHENEQUIVALENTPASS |
| 23 | #include "mlir/Dialect/Arith/Transforms/Passes.h.inc" |
| 24 | } // namespace arith |
| 25 | } // namespace mlir |
| 26 | |
| 27 | using namespace mlir; |
| 28 | using namespace mlir::arith; |
| 29 | using 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. |
| 34 | static 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. |
| 51 | static 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 | |
| 66 | namespace { |
| 67 | class DataFlowListener : public RewriterBase::Listener { |
| 68 | public: |
| 69 | DataFlowListener(DataFlowSolver &s) : s(s) {} |
| 70 | |
| 71 | protected: |
| 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 | |
| 85 | template <typename Signed, typename Unsigned> |
| 86 | struct 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 | |
| 105 | private: |
| 106 | DataFlowSolver &solver; |
| 107 | }; |
| 108 | |
| 109 | struct 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 | |
| 125 | private: |
| 126 | DataFlowSolver &solver; |
| 127 | }; |
| 128 | |
| 129 | struct 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 | |
| 142 | private: |
| 143 | DataFlowSolver &solver; |
| 144 | }; |
| 145 | |
| 146 | struct 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 | |
| 170 | void 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 | |