1//===- IntRangeOptimizations.cpp - Optimizations based on integer ranges --===//
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 <utility>
10
11#include "llvm/ADT/TypeSwitch.h"
12
13#include "mlir/Analysis/DataFlow/ConstantPropagationAnalysis.h"
14#include "mlir/Analysis/DataFlow/Utils.h"
15#include "mlir/Analysis/DataFlowFramework.h"
16#include "mlir/Dialect/Arith/Transforms/Passes.h"
17
18#include "mlir/Analysis/DataFlow/DeadCodeAnalysis.h"
19#include "mlir/Analysis/DataFlow/IntegerRangeAnalysis.h"
20#include "mlir/Dialect/Arith/IR/Arith.h"
21#include "mlir/IR/IRMapping.h"
22#include "mlir/IR/Matchers.h"
23#include "mlir/IR/PatternMatch.h"
24#include "mlir/IR/TypeUtilities.h"
25#include "mlir/Interfaces/LoopLikeInterface.h"
26#include "mlir/Interfaces/SideEffectInterfaces.h"
27#include "mlir/Transforms/FoldUtils.h"
28#include "mlir/Transforms/GreedyPatternRewriteDriver.h"
29
30namespace mlir::arith {
31#define GEN_PASS_DEF_ARITHINTRANGEOPTS
32#include "mlir/Dialect/Arith/Transforms/Passes.h.inc"
33
34#define GEN_PASS_DEF_ARITHINTRANGENARROWING
35#include "mlir/Dialect/Arith/Transforms/Passes.h.inc"
36} // namespace mlir::arith
37
38using namespace mlir;
39using namespace mlir::arith;
40using namespace mlir::dataflow;
41
42static std::optional<APInt> getMaybeConstantValue(DataFlowSolver &solver,
43 Value value) {
44 auto *maybeInferredRange =
45 solver.lookupState<IntegerValueRangeLattice>(anchor: value);
46 if (!maybeInferredRange || maybeInferredRange->getValue().isUninitialized())
47 return std::nullopt;
48 const ConstantIntRanges &inferredRange =
49 maybeInferredRange->getValue().getValue();
50 return inferredRange.getConstantValue();
51}
52
53static void copyIntegerRange(DataFlowSolver &solver, Value oldVal,
54 Value newVal) {
55 auto *oldState = solver.lookupState<IntegerValueRangeLattice>(anchor: oldVal);
56 if (!oldState)
57 return;
58 (void)solver.getOrCreateState<IntegerValueRangeLattice>(anchor: newVal)->join(
59 rhs: *oldState);
60}
61
62namespace mlir::dataflow {
63/// Patterned after SCCP
64LogicalResult maybeReplaceWithConstant(DataFlowSolver &solver,
65 RewriterBase &rewriter, Value value) {
66 if (value.use_empty())
67 return failure();
68 std::optional<APInt> maybeConstValue = getMaybeConstantValue(solver, value);
69 if (!maybeConstValue.has_value())
70 return failure();
71
72 Type type = value.getType();
73 // If the type or element type is non-integral, the attribute constructor
74 // will crash, so eagerly check for an integer type to avoid this.
75 if (!getElementTypeOrSelf(type).isIntOrIndex())
76 return failure();
77
78 // Bail out if the inferred APInt bitwidth does not match the storage width
79 // of the IR type; IntegerAttr::get would assert otherwise.
80 unsigned storageWidth = ConstantIntRanges::getStorageBitwidth(type);
81 if (storageWidth != 0 && maybeConstValue->getBitWidth() != storageWidth)
82 return failure();
83
84 Location loc = value.getLoc();
85 Operation *maybeDefiningOp = value.getDefiningOp();
86 Dialect *valueDialect =
87 maybeDefiningOp ? maybeDefiningOp->getDialect()
88 : value.getParentRegion()->getParentOp()->getDialect();
89
90 Attribute constAttr;
91 if (auto shaped = dyn_cast<ShapedType>(Val&: type)) {
92 constAttr = mlir::DenseIntElementsAttr::get(type: shaped, arg&: *maybeConstValue);
93 } else {
94 constAttr = rewriter.getIntegerAttr(type, value: *maybeConstValue);
95 }
96 Operation *constOp =
97 valueDialect->materializeConstant(builder&: rewriter, value: constAttr, type, loc);
98 // Fall back to arith.constant if the dialect materializer doesn't know what
99 // to do with an integer constant.
100 if (!constOp)
101 constOp = rewriter.getContext()
102 ->getLoadedDialect<ArithDialect>()
103 ->materializeConstant(builder&: rewriter, value: constAttr, type, loc);
104 if (!constOp)
105 return failure();
106
107 OpResult res = constOp->getResult(idx: 0);
108 if (solver.lookupState<dataflow::IntegerValueRangeLattice>(anchor: res))
109 solver.eraseState(anchor: res);
110 copyIntegerRange(solver, oldVal: value, newVal: res);
111 rewriter.replaceAllUsesWith(from: value, to: res);
112 return success();
113}
114} // namespace mlir::dataflow
115
116namespace {
117class DataFlowListener : public RewriterBase::Listener {
118public:
119 DataFlowListener(DataFlowSolver &s) : s(s) {}
120
121protected:
122 void notifyOperationErased(Operation *op) override {
123 s.eraseState(anchor: s.getProgramPointAfter(op));
124 for (Value res : op->getResults())
125 s.eraseState(anchor: res);
126 }
127
128 DataFlowSolver &s;
129};
130
131/// Rewrite any results of `op` that were inferred to be constant integers to
132/// and replace their uses with that constant. Return success() if all results
133/// where thus replaced and the operation is erased. Also replace any block
134/// arguments with their constant values.
135struct MaterializeKnownConstantValues : public RewritePattern {
136 MaterializeKnownConstantValues(MLIRContext *context, DataFlowSolver &s)
137 : RewritePattern::RewritePattern(Pattern::MatchAnyOpTypeTag(),
138 /*benefit=*/1, context),
139 solver(s) {}
140
141 LogicalResult matchAndRewrite(Operation *op,
142 PatternRewriter &rewriter) const override {
143 if (matchPattern(op, pattern: m_Constant()))
144 return failure();
145
146 // We need to check isIntOrIndex() and APInt bitwidth compatibility here
147 // as well to avoid infinite loops in the greedy pattern rewriter. If we
148 // only check in maybeReplaceWithConstant, this lambda might still return
149 // true for values that cannot be materialized, causing the pattern to
150 // match and claim success without making any changes, leading to
151 // non-convergence.
152 auto needsReplacing = [&](Value v) {
153 if (!getElementTypeOrSelf(type: v.getType()).isIntOrIndex())
154 return false;
155 std::optional<APInt> maybeConstValue = getMaybeConstantValue(solver, value: v);
156 if (!maybeConstValue.has_value() || v.use_empty())
157 return false;
158 unsigned storageWidth =
159 ConstantIntRanges::getStorageBitwidth(type: v.getType());
160 return storageWidth == 0 ||
161 maybeConstValue->getBitWidth() == storageWidth;
162 };
163 bool hasConstantResults = llvm::any_of(Range: op->getResults(), P: needsReplacing);
164 if (op->getNumRegions() == 0)
165 if (!hasConstantResults)
166 return failure();
167 bool hasConstantRegionArgs = false;
168 for (Region &region : op->getRegions()) {
169 for (Block &block : region.getBlocks()) {
170 hasConstantRegionArgs |=
171 llvm::any_of(Range: block.getArguments(), P: needsReplacing);
172 }
173 }
174 if (!hasConstantResults && !hasConstantRegionArgs)
175 return failure();
176
177 bool replacedAll = (op->getNumResults() != 0);
178 for (Value v : op->getResults())
179 replacedAll &=
180 (succeeded(Result: maybeReplaceWithConstant(solver, rewriter, value: v)) ||
181 v.use_empty());
182 if (replacedAll && isOpTriviallyDead(op)) {
183 rewriter.eraseOp(op);
184 return success();
185 }
186
187 PatternRewriter::InsertionGuard guard(rewriter);
188 for (Region &region : op->getRegions()) {
189 for (Block &block : region.getBlocks()) {
190 rewriter.setInsertionPointToStart(&block);
191 for (BlockArgument &arg : block.getArguments()) {
192 (void)maybeReplaceWithConstant(solver, rewriter, value: arg);
193 }
194 }
195 }
196
197 return success();
198 }
199
200private:
201 DataFlowSolver &solver;
202};
203
204template <typename RemOp>
205struct DeleteTrivialRem : public OpRewritePattern<RemOp> {
206 DeleteTrivialRem(MLIRContext *context, DataFlowSolver &s)
207 : OpRewritePattern<RemOp>(context), solver(s) {}
208
209 LogicalResult matchAndRewrite(RemOp op,
210 PatternRewriter &rewriter) const override {
211 Value lhs = op.getOperand(0);
212 Value rhs = op.getOperand(1);
213 // TODO: Support index types once integer range inference can use the target
214 // index bitwidth, e.g. from DLTI.
215 if (isa<IndexType>(Val: getElementTypeOrSelf(type: lhs.getType())))
216 return failure();
217 APInt modulus;
218 bool isUnsigned = isa<RemUIOp>(op);
219 // Any nonzero bit pattern is a valid unsigned modulus. Keep the existing
220 // positive-modulus restriction for signed remainder.
221 if (!matchPattern(value: rhs, pattern: m_ConstantInt(bind_value: &modulus)) || modulus.isZero() ||
222 (!isUnsigned && modulus.isNegative()))
223 return failure();
224 auto *maybeLhsRange = solver.lookupState<IntegerValueRangeLattice>(anchor: lhs);
225 if (!maybeLhsRange || maybeLhsRange->getValue().isUninitialized())
226 return failure();
227 const ConstantIntRanges &lhsRange = maybeLhsRange->getValue().getValue();
228 const APInt &min = isUnsigned ? lhsRange.umin() : lhsRange.smin();
229 const APInt &max = isUnsigned ? lhsRange.umax() : lhsRange.smax();
230 if (min.getBitWidth() != modulus.getBitWidth() ||
231 max.getBitWidth() != modulus.getBitWidth())
232 return failure();
233 // The minima and maxima here are given as closed ranges, we must be
234 // non-negative for signed remainder and strictly less than the modulus.
235 if ((!isUnsigned && min.isNegative()) || min.uge(RHS: modulus))
236 return failure();
237 if ((!isUnsigned && max.isNegative()) || max.uge(RHS: modulus))
238 return failure();
239 if (!min.ule(RHS: max))
240 return failure();
241
242 // With all those conditions out of the way, we know thas this invocation of
243 // a remainder is a noop because the input is strictly within the range
244 // [0, modulus), so get rid of it.
245 rewriter.replaceOp(op, ValueRange{lhs});
246 return success();
247 }
248
249private:
250 DataFlowSolver &solver;
251};
252
253/// Gather ranges for all the values in `values`. Appends to the existing
254/// vector.
255static LogicalResult collectRanges(DataFlowSolver &solver, ValueRange values,
256 SmallVectorImpl<ConstantIntRanges> &ranges) {
257 for (Value val : values) {
258 auto *maybeInferredRange =
259 solver.lookupState<IntegerValueRangeLattice>(anchor: val);
260 if (!maybeInferredRange || maybeInferredRange->getValue().isUninitialized())
261 return failure();
262
263 const ConstantIntRanges &inferredRange =
264 maybeInferredRange->getValue().getValue();
265 ranges.push_back(Elt: inferredRange);
266 }
267 return success();
268}
269
270/// Return int type truncated to `targetBitwidth`. If `srcType` is shaped,
271/// return shaped type as well.
272static Type getTargetType(Type srcType, unsigned targetBitwidth) {
273 auto dstType = IntegerType::get(context: srcType.getContext(), width: targetBitwidth);
274 if (auto shaped = dyn_cast<ShapedType>(Val&: srcType))
275 return shaped.clone(elementType: dstType);
276
277 assert(srcType.isIntOrIndex() && "Invalid src type");
278 return dstType;
279}
280
281namespace {
282// Enum for tracking which type of truncation should be performed
283// to narrow an operation, if any.
284enum class CastKind : uint8_t { None, Signed, Unsigned, Both };
285} // namespace
286
287/// If the values within `range` can be represented using only `width` bits,
288/// return the kind of truncation needed to preserve that property.
289///
290/// This check relies on the fact that the signed and unsigned ranges are both
291/// always correct, but that one might be an approximation of the other,
292/// so we want to use the correct truncation operation.
293static CastKind checkTruncatability(const ConstantIntRanges &range,
294 unsigned targetWidth) {
295 unsigned srcWidth = range.smin().getBitWidth();
296 if (srcWidth <= targetWidth)
297 return CastKind::None;
298 unsigned removedWidth = srcWidth - targetWidth;
299 // The sign bits need to extend into the sign bit of the target width. For
300 // example, if we're truncating 64 bits to 32, we need 64 - 32 + 1 = 33 sign
301 // bits.
302 bool canTruncateSigned =
303 range.smin().getNumSignBits() >= (removedWidth + 1) &&
304 range.smax().getNumSignBits() >= (removedWidth + 1);
305 bool canTruncateUnsigned = range.umin().countLeadingZeros() >= removedWidth &&
306 range.umax().countLeadingZeros() >= removedWidth;
307 if (canTruncateSigned && canTruncateUnsigned)
308 return CastKind::Both;
309 if (canTruncateSigned)
310 return CastKind::Signed;
311 if (canTruncateUnsigned)
312 return CastKind::Unsigned;
313 return CastKind::None;
314}
315
316static CastKind mergeCastKinds(CastKind lhs, CastKind rhs) {
317 if (lhs == CastKind::None || rhs == CastKind::None)
318 return CastKind::None;
319 if (lhs == CastKind::Both)
320 return rhs;
321 if (rhs == CastKind::Both)
322 return lhs;
323 if (lhs == rhs)
324 return lhs;
325 return CastKind::None;
326}
327
328static Value doCast(OpBuilder &builder, Location loc, Value src, Type dstType,
329 CastKind castKind) {
330 Type srcType = src.getType();
331 assert(isa<VectorType>(srcType) == isa<VectorType>(dstType) &&
332 "Mixing vector and non-vector types");
333 assert(castKind != CastKind::None && "Can't cast when casting isn't allowed");
334 Type srcElemType = getElementTypeOrSelf(type: srcType);
335 Type dstElemType = getElementTypeOrSelf(type: dstType);
336 assert(srcElemType.isIntOrIndex() && "Invalid src type");
337 assert(dstElemType.isIntOrIndex() && "Invalid dst type");
338 if (srcType == dstType)
339 return src;
340
341 if (isa<IndexType>(Val: srcElemType) || isa<IndexType>(Val: dstElemType)) {
342 if (castKind == CastKind::Signed)
343 return arith::IndexCastOp::create(builder, location: loc, out: dstType, in: src);
344 return arith::IndexCastUIOp::create(builder, location: loc, out: dstType, in: src);
345 }
346
347 auto srcInt = cast<IntegerType>(Val&: srcElemType);
348 auto dstInt = cast<IntegerType>(Val&: dstElemType);
349 if (dstInt.getWidth() < srcInt.getWidth())
350 return arith::TruncIOp::create(builder, location: loc, out: dstType, in: src);
351
352 if (castKind == CastKind::Signed)
353 return arith::ExtSIOp::create(builder, location: loc, out: dstType, in: src);
354 return arith::ExtUIOp::create(builder, location: loc, out: dstType, in: src);
355}
356
357struct NarrowElementwise final : OpTraitRewritePattern<OpTrait::Elementwise> {
358 NarrowElementwise(MLIRContext *context, DataFlowSolver &s,
359 ArrayRef<unsigned> target)
360 : OpTraitRewritePattern(context), solver(s), targetBitwidths(target) {}
361
362 using Base::Base;
363 LogicalResult matchAndRewrite(Operation *op,
364 PatternRewriter &rewriter) const override {
365 if (op->getNumResults() == 0)
366 return rewriter.notifyMatchFailure(arg&: op, msg: "can't narrow resultless op");
367
368 // Inline size chosen empirically based on compilation profiling.
369 // Profiled: 2.6M calls, avg=1.7+-1.3. N=4 covers >95% of cases inline.
370 SmallVector<ConstantIntRanges, 4> ranges;
371 if (failed(Result: collectRanges(solver, values: op->getOperands(), ranges)))
372 return rewriter.notifyMatchFailure(arg&: op, msg: "input without specified range");
373 if (failed(Result: collectRanges(solver, values: op->getResults(), ranges)))
374 return rewriter.notifyMatchFailure(arg&: op, msg: "output without specified range");
375
376 Type srcType = op->getResult(idx: 0).getType();
377 if (!llvm::all_equal(Range: op->getResultTypes()))
378 return rewriter.notifyMatchFailure(arg&: op, msg: "mismatched result types");
379 if (op->getNumOperands() == 0 ||
380 !llvm::all_of(Range: op->getOperandTypes(),
381 P: [=](Type t) { return t == srcType; }))
382 return rewriter.notifyMatchFailure(
383 arg&: op, msg: "no operands or operand types don't match result type");
384
385 for (unsigned targetBitwidth : targetBitwidths) {
386 CastKind castKind = CastKind::Both;
387 for (const ConstantIntRanges &range : ranges) {
388 castKind = mergeCastKinds(lhs: castKind,
389 rhs: checkTruncatability(range, targetWidth: targetBitwidth));
390 if (castKind == CastKind::None)
391 break;
392 }
393 // Constrain the cast kind to preserve the interpretation required by the
394 // operation.
395 auto castKindForOp =
396 llvm::TypeSwitch<Operation *, CastKind>(op)
397 .Case<arith::DivSIOp, arith::CeilDivSIOp, arith::FloorDivSIOp,
398 arith::RemSIOp, arith::MaxSIOp, arith::MinSIOp,
399 arith::ShRSIOp>(caseFn: [](auto) { return CastKind::Signed; })
400 .Case<arith::DivUIOp, arith::CeilDivUIOp, arith::RemUIOp,
401 arith::ShRUIOp>(caseFn: [](auto) { return CastKind::Unsigned; })
402 .Default(defaultResult: CastKind::Both);
403 castKind = mergeCastKinds(lhs: castKind, rhs: castKindForOp);
404 if (castKind == CastKind::None)
405 continue;
406 // A shift by an amount >= the bitwidth is poison, so only narrow shifts
407 // when the shift amount (second operand) stays below the target width.
408 if (isa<arith::ShLIOp, arith::ShRSIOp, arith::ShRUIOp>(Val: op) &&
409 !ranges[1].umax().ult(RHS: targetBitwidth))
410 continue;
411 Type targetType = getTargetType(srcType, targetBitwidth);
412 if (targetType == srcType)
413 continue;
414
415 Location loc = op->getLoc();
416 IRMapping mapping;
417 for (auto [arg, argRange] : llvm::zip_first(t: op->getOperands(), u&: ranges)) {
418 CastKind argCastKind = castKind;
419 // When dealing with `index` values, preserve non-negativity in the
420 // index_casts since we can't recover this in unsigned when equivalent.
421 if (argCastKind == CastKind::Signed && argRange.smin().isNonNegative())
422 argCastKind = CastKind::Both;
423 Value newArg = doCast(builder&: rewriter, loc, src: arg, dstType: targetType, castKind: argCastKind);
424 mapping.map(from: arg, to: newArg);
425 }
426
427 Operation *newOp = rewriter.clone(op&: *op, mapper&: mapping);
428 rewriter.modifyOpInPlace(root: newOp, callable: [&]() {
429 for (OpResult res : newOp->getResults()) {
430 res.setType(targetType);
431 }
432 // Retain an overflow flag only when the casts preserve operand and
433 // result values in the flag's signed or unsigned interpretation.
434 if (auto overflowOp =
435 dyn_cast<arith::ArithIntegerOverflowFlagsInterface>(Val: newOp)) {
436 auto flags = overflowOp.getOverflowAttr().getValue();
437 if (castKind == CastKind::Unsigned)
438 flags = bitEnumClear(bits: flags, bit: IntegerOverflowFlags::nsw);
439 else if (castKind == CastKind::Signed)
440 flags = bitEnumClear(bits: flags, bit: IntegerOverflowFlags::nuw);
441 newOp->setAttr(
442 name: overflowOp.getIntegerOverflowAttrName(),
443 value: IntegerOverflowFlagsAttr::get(context: rewriter.getContext(), value: flags));
444 }
445 });
446 SmallVector<Value> newResults;
447 for (auto [newRes, oldRes] :
448 llvm::zip_equal(t: newOp->getResults(), u: op->getResults())) {
449 Value castBack = doCast(builder&: rewriter, loc, src: newRes, dstType: srcType, castKind);
450 copyIntegerRange(solver, oldVal: oldRes, newVal: castBack);
451 newResults.push_back(Elt: castBack);
452 }
453
454 rewriter.replaceOp(op, newValues: newResults);
455 return success();
456 }
457 return failure();
458 }
459
460private:
461 DataFlowSolver &solver;
462 SmallVector<unsigned, 4> targetBitwidths;
463};
464
465struct NarrowCmpI final : OpRewritePattern<arith::CmpIOp> {
466 NarrowCmpI(MLIRContext *context, DataFlowSolver &s, ArrayRef<unsigned> target)
467 : OpRewritePattern(context), solver(s), targetBitwidths(target) {}
468
469 LogicalResult matchAndRewrite(arith::CmpIOp op,
470 PatternRewriter &rewriter) const override {
471 Value lhs = op.getLhs();
472 Value rhs = op.getRhs();
473
474 SmallVector<ConstantIntRanges> ranges;
475 if (failed(Result: collectRanges(solver, values: op.getOperands(), ranges)))
476 return failure();
477 const ConstantIntRanges &lhsRange = ranges[0];
478 const ConstantIntRanges &rhsRange = ranges[1];
479
480 auto isSignedCmpPredicate = [](arith::CmpIPredicate pred) -> bool {
481 return pred == arith::CmpIPredicate::sge ||
482 pred == arith::CmpIPredicate::sgt ||
483 pred == arith::CmpIPredicate::sle ||
484 pred == arith::CmpIPredicate::slt;
485 };
486 // If we're to narrow the input values via a cast, we should preserve the
487 // sign.
488 CastKind predicateBasedCastRestriction =
489 isSignedCmpPredicate(op.getPredicate()) ? CastKind::Signed
490 : CastKind::Both;
491
492 Type srcType = lhs.getType();
493 for (unsigned targetBitwidth : targetBitwidths) {
494 CastKind lhsCastKind = checkTruncatability(range: lhsRange, targetWidth: targetBitwidth);
495 CastKind rhsCastKind = checkTruncatability(range: rhsRange, targetWidth: targetBitwidth);
496 CastKind castKind = mergeCastKinds(lhs: lhsCastKind, rhs: rhsCastKind);
497 castKind = mergeCastKinds(lhs: castKind, rhs: predicateBasedCastRestriction);
498 // Note: this includes target width > src width, as well as the unsigned
499 // truncatability & signed predicate scenario.
500 if (castKind == CastKind::None)
501 continue;
502
503 Type targetType = getTargetType(srcType, targetBitwidth);
504 if (targetType == srcType)
505 continue;
506
507 Location loc = op->getLoc();
508 IRMapping mapping;
509 Value lhsCast = doCast(builder&: rewriter, loc, src: lhs, dstType: targetType, castKind: lhsCastKind);
510 Value rhsCast = doCast(builder&: rewriter, loc, src: rhs, dstType: targetType, castKind: rhsCastKind);
511 mapping.map(from: lhs, to: lhsCast);
512 mapping.map(from: rhs, to: rhsCast);
513
514 Operation *newOp = rewriter.clone(op&: *op, mapper&: mapping);
515 copyIntegerRange(solver, oldVal: op.getResult(), newVal: newOp->getResult(idx: 0));
516 rewriter.replaceOp(op, newValues: newOp->getResults());
517 return success();
518 }
519 return failure();
520 }
521
522private:
523 DataFlowSolver &solver;
524 SmallVector<unsigned, 4> targetBitwidths;
525};
526
527/// Fold index_cast(index_cast(%arg: i8, index), i8) -> %arg
528/// This pattern assumes all passed `targetBitwidths` are not wider than index
529/// type.
530template <typename CastOp>
531struct FoldIndexCastChain final : OpRewritePattern<CastOp> {
532 FoldIndexCastChain(MLIRContext *context, ArrayRef<unsigned> target)
533 : OpRewritePattern<CastOp>(context), targetBitwidths(target) {}
534
535 LogicalResult matchAndRewrite(CastOp op,
536 PatternRewriter &rewriter) const override {
537 auto srcOp = op.getIn().template getDefiningOp<CastOp>();
538 if (!srcOp)
539 return rewriter.notifyMatchFailure(op, "doesn't come from an index cast");
540
541 Value src = srcOp.getIn();
542 if (src.getType() != op.getType())
543 return rewriter.notifyMatchFailure(op, "outer types don't match");
544
545 if (!srcOp.getType().isIndex())
546 return rewriter.notifyMatchFailure(op, "intermediate type isn't index");
547
548 auto intType = dyn_cast<IntegerType>(op.getType());
549 if (!intType || !llvm::is_contained(targetBitwidths, intType.getWidth()))
550 return failure();
551
552 rewriter.replaceOp(op, src);
553 return success();
554 }
555
556private:
557 SmallVector<unsigned, 4> targetBitwidths;
558};
559
560struct NarrowLoopBounds final : OpInterfaceRewritePattern<LoopLikeOpInterface> {
561 NarrowLoopBounds(MLIRContext *context, DataFlowSolver &s,
562 ArrayRef<unsigned> target)
563 : OpInterfaceRewritePattern<LoopLikeOpInterface>(context), solver(s),
564 targetBitwidths(target),
565 boundsNarrowingFailedAttr(
566 StringAttr::get(context, bytes: "arith.bounds_narrowing_failed")) {}
567
568 LogicalResult matchAndRewrite(LoopLikeOpInterface loopLike,
569 PatternRewriter &rewriter) const override {
570 // Skip ops where bounds narrowing previously failed.
571 if (loopLike->hasDiscardableAttr(name: boundsNarrowingFailedAttr))
572 return rewriter.notifyMatchFailure(arg&: loopLike,
573 msg: "bounds narrowing previously failed");
574
575 std::optional<SmallVector<Value>> inductionVars =
576 loopLike.getLoopInductionVars();
577 if (!inductionVars.has_value() || inductionVars->empty())
578 return rewriter.notifyMatchFailure(arg&: loopLike, msg: "no induction variables");
579
580 std::optional<SmallVector<OpFoldResult>> lowerBounds =
581 loopLike.getLoopLowerBounds();
582 std::optional<SmallVector<OpFoldResult>> upperBounds =
583 loopLike.getLoopUpperBounds();
584 std::optional<SmallVector<OpFoldResult>> steps = loopLike.getLoopSteps();
585
586 if (!lowerBounds.has_value() || !upperBounds.has_value() ||
587 !steps.has_value())
588 return rewriter.notifyMatchFailure(arg&: loopLike, msg: "no loop bounds or steps");
589
590 if (lowerBounds->size() != inductionVars->size() ||
591 upperBounds->size() != inductionVars->size() ||
592 steps->size() != inductionVars->size())
593 return rewriter.notifyMatchFailure(arg&: loopLike,
594 msg: "mismatched bounds/steps count");
595
596 Location loc = loopLike->getLoc();
597 SmallVector<OpFoldResult> newLowerBounds(*lowerBounds);
598 SmallVector<OpFoldResult> newUpperBounds(*upperBounds);
599 SmallVector<OpFoldResult> newSteps(*steps);
600 SmallVector<std::tuple<size_t, Type, CastKind>> narrowings;
601
602 // Check each (indVar, lb, ub, step) tuple.
603 for (auto [idx, indVar, lbOFR, ubOFR, stepOFR] :
604 llvm::enumerate(First&: *inductionVars, Rest&: *lowerBounds, Rest&: *upperBounds, Rest&: *steps)) {
605
606 // Only process value operands, skip attributes.
607 auto maybeLb = dyn_cast<Value>(Val&: lbOFR);
608 auto maybeUb = dyn_cast<Value>(Val&: ubOFR);
609 auto maybeStep = dyn_cast<Value>(Val&: stepOFR);
610
611 if (!maybeLb || !maybeUb || !maybeStep)
612 continue;
613
614 // Collect ranges for (lb, ub, step, indVar).
615 SmallVector<ConstantIntRanges> ranges;
616 if (failed(Result: collectRanges(
617 solver, values: ValueRange{maybeLb, maybeUb, maybeStep, indVar}, ranges)))
618 continue;
619
620 const ConstantIntRanges &stepRange = ranges[2];
621 const ConstantIntRanges &indVarRange = ranges[3];
622
623 Type srcType = maybeLb.getType();
624
625 // Try each target bitwidth.
626 for (unsigned targetBitwidth : targetBitwidths) {
627 Type targetType = getTargetType(srcType, targetBitwidth);
628 if (targetType == srcType)
629 continue;
630
631 // Check if the target type is valid for this loop's induction
632 // variables.
633 if (!loopLike.isValidInductionVarType(type: targetType))
634 continue;
635
636 // Check if all values in this tuple can be truncated.
637 CastKind castKind = CastKind::Both;
638 for (const ConstantIntRanges &range : ranges) {
639 castKind = mergeCastKinds(lhs: castKind,
640 rhs: checkTruncatability(range, targetWidth: targetBitwidth));
641 if (castKind == CastKind::None)
642 break;
643 }
644
645 if (castKind == CastKind::None)
646 continue;
647
648 // Check if indVar + step fits in the narrowed type.
649 // This is critical for loop correctness: the loop computes
650 // iv_next = iv_current + step in the narrowed type, then compares
651 // iv_next < ub. If iv_current + step overflows, the comparison may
652 // produce incorrect results and break loop termination.
653 // Both signed and unsigned interpretations must fit because loop
654 // semantics are unknown (integer types are signless).
655 ConstantIntRanges indVarPlusStepRange(
656 indVarRange.smin().sadd_sat(RHS: stepRange.smin()),
657 indVarRange.smax().sadd_sat(RHS: stepRange.smax()),
658 indVarRange.umin().uadd_sat(RHS: stepRange.umin()),
659 indVarRange.umax().uadd_sat(RHS: stepRange.umax()));
660
661 if (checkTruncatability(range: indVarPlusStepRange, targetWidth: targetBitwidth) !=
662 CastKind::Both)
663 continue;
664
665 // Narrow the bounds and step values.
666 Value newLb = doCast(builder&: rewriter, loc, src: maybeLb, dstType: targetType, castKind);
667 Value newUb = doCast(builder&: rewriter, loc, src: maybeUb, dstType: targetType, castKind);
668 Value newStep = doCast(builder&: rewriter, loc, src: maybeStep, dstType: targetType, castKind);
669
670 newLowerBounds[idx] = newLb;
671 newUpperBounds[idx] = newUb;
672 newSteps[idx] = newStep;
673 narrowings.push_back(Elt: {idx, targetType, castKind});
674 break;
675 }
676 }
677
678 if (narrowings.empty())
679 return rewriter.notifyMatchFailure(arg&: loopLike, msg: "no narrowings found");
680
681 // Save original types before modifying.
682 SmallVector<Type> origTypes;
683 for (auto [idx, targetType, castKind] : narrowings) {
684 Value indVar = (*inductionVars)[idx];
685 origTypes.push_back(Elt: indVar.getType());
686 }
687
688 // Attempt to update bounds and induction variable types.
689 // If this fails, mark the op so we don't try again.
690 bool updateFailed = false;
691 rewriter.modifyOpInPlace(root: loopLike, callable: [&]() {
692 // Update the loop bounds and steps.
693 if (failed(Result: loopLike.setLoopLowerBounds(newLowerBounds)) ||
694 failed(Result: loopLike.setLoopUpperBounds(newUpperBounds)) ||
695 failed(Result: loopLike.setLoopSteps(newSteps))) {
696 // Mark op to prevent future attempts. IR was modified (attribute
697 // added), so we must return success() from the pattern.
698 loopLike->setDiscardableAttr(name: boundsNarrowingFailedAttr,
699 value: rewriter.getUnitAttr());
700 updateFailed = true;
701 return;
702 }
703
704 // Update induction variable types.
705 for (auto [idx, targetType, castKind] : narrowings) {
706 Value indVar = (*inductionVars)[idx];
707 auto blockArg = cast<BlockArgument>(Val&: indVar);
708
709 // Change the block argument type.
710 blockArg.setType(targetType);
711 }
712 });
713
714 if (updateFailed)
715 return success();
716
717 // Insert casts back to original type for uses.
718 for (auto [narrowingIdx, narrowingInfo] : llvm::enumerate(First&: narrowings)) {
719 auto [idx, targetType, castKind] = narrowingInfo;
720 Value indVar = (*inductionVars)[idx];
721 auto blockArg = cast<BlockArgument>(Val&: indVar);
722 Type origType = origTypes[narrowingIdx];
723
724 OpBuilder::InsertionGuard guard(rewriter);
725 rewriter.setInsertionPointToStart(blockArg.getOwner());
726 Value casted = doCast(builder&: rewriter, loc, src: blockArg, dstType: origType, castKind);
727 copyIntegerRange(solver, oldVal: blockArg, newVal: casted);
728
729 // Replace all uses of the narrowed indVar with the casted value.
730 rewriter.replaceAllUsesExcept(from: blockArg, to: casted, exceptedUser: casted.getDefiningOp());
731 }
732
733 return success();
734 }
735
736private:
737 DataFlowSolver &solver;
738 SmallVector<unsigned, 4> targetBitwidths;
739 StringAttr boundsNarrowingFailedAttr;
740};
741
742struct IntRangeOptimizationsPass final
743 : arith::impl::ArithIntRangeOptsBase<IntRangeOptimizationsPass> {
744
745 void runOnOperation() override {
746 Operation *op = getOperation();
747 MLIRContext *ctx = op->getContext();
748 DataFlowSolver solver;
749 loadBaselineAnalyses(solver);
750 solver.load<IntegerRangeAnalysis>();
751 if (failed(Result: solver.initializeAndRun(top: op)))
752 return signalPassFailure();
753
754 DataFlowListener listener(solver);
755
756 RewritePatternSet patterns(ctx);
757 populateIntRangeOptimizationsPatterns(patterns, solver);
758
759 // Disable folding and region simplification to avoid breaking the solver
760 // state. Both can remove block arguments (folding via control-flow
761 // simplification, region simplification via dead-arg elimination), which
762 // frees their underlying storage. A subsequent allocation may reuse the
763 // same address for a different block argument, causing stale solver state
764 // to be associated with the new argument and producing incorrect constants.
765 if (failed(
766 Result: applyPatternsGreedily(op, patterns: std::move(patterns),
767 config: GreedyRewriteConfig()
768 .enableFolding(enable: false)
769 .setRegionSimplificationLevel(
770 GreedySimplifyRegionLevel::Disabled)
771 .setListener(&listener))))
772 signalPassFailure();
773 }
774};
775
776struct IntRangeNarrowingPass final
777 : arith::impl::ArithIntRangeNarrowingBase<IntRangeNarrowingPass> {
778 using ArithIntRangeNarrowingBase::ArithIntRangeNarrowingBase;
779
780 void runOnOperation() override {
781 Operation *op = getOperation();
782 MLIRContext *ctx = op->getContext();
783 DataFlowSolver solver;
784 loadBaselineAnalyses(solver);
785 solver.load<IntegerRangeAnalysis>();
786 if (failed(Result: solver.initializeAndRun(top: op)))
787 return signalPassFailure();
788
789 DataFlowListener listener(solver);
790
791 RewritePatternSet patterns(ctx);
792 populateIntRangeNarrowingPatterns(patterns, solver, bitwidthsSupported);
793 populateControlFlowValuesNarrowingPatterns(patterns, solver,
794 bitwidthsSupported);
795
796 // We specifically need bottom-up traversal as cmpi pattern needs range
797 // data, attached to its original argument values.
798 if (failed(Result: applyPatternsGreedily(
799 op, patterns: std::move(patterns),
800 config: GreedyRewriteConfig().setUseTopDownTraversal(false).setListener(
801 &listener))))
802 signalPassFailure();
803 }
804};
805} // namespace
806
807void mlir::arith::populateIntRangeOptimizationsPatterns(
808 RewritePatternSet &patterns, DataFlowSolver &solver) {
809 patterns.add<MaterializeKnownConstantValues, DeleteTrivialRem<RemSIOp>,
810 DeleteTrivialRem<RemUIOp>>(arg: patterns.getContext(), args&: solver);
811}
812
813void mlir::arith::populateIntRangeNarrowingPatterns(
814 RewritePatternSet &patterns, DataFlowSolver &solver,
815 ArrayRef<unsigned> bitwidthsSupported) {
816 patterns.add<NarrowElementwise, NarrowCmpI>(arg: patterns.getContext(), args&: solver,
817 args&: bitwidthsSupported);
818 patterns.add<FoldIndexCastChain<arith::IndexCastUIOp>,
819 FoldIndexCastChain<arith::IndexCastOp>>(arg: patterns.getContext(),
820 args&: bitwidthsSupported);
821}
822
823void mlir::arith::populateControlFlowValuesNarrowingPatterns(
824 RewritePatternSet &patterns, DataFlowSolver &solver,
825 ArrayRef<unsigned> bitwidthsSupported) {
826 patterns.add<NarrowLoopBounds>(arg: patterns.getContext(), args&: solver,
827 args&: bitwidthsSupported);
828}
829
830std::unique_ptr<Pass> mlir::arith::createIntRangeOptimizationsPass() {
831 return std::make_unique<IntRangeOptimizationsPass>();
832}
833