| 1 | //===- IntegerRangeAnalysis.cpp - Integer range analysis --------*- C++ -*-===// |
| 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 defines the dataflow analysis class for integer range inference |
| 10 | // which is used in transformations over the `arith` dialect such as |
| 11 | // branch elimination or signed->unsigned rewriting |
| 12 | // |
| 13 | //===----------------------------------------------------------------------===// |
| 14 | |
| 15 | #include "mlir/Analysis/DataFlow/IntegerRangeAnalysis.h" |
| 16 | #include "mlir/Analysis/DataFlow/SparseAnalysis.h" |
| 17 | #include "mlir/Analysis/DataFlowFramework.h" |
| 18 | #include "mlir/IR/BuiltinAttributes.h" |
| 19 | #include "mlir/IR/Dialect.h" |
| 20 | #include "mlir/IR/OpDefinition.h" |
| 21 | #include "mlir/IR/Operation.h" |
| 22 | #include "mlir/IR/OperationSupport.h" |
| 23 | #include "mlir/IR/TypeUtilities.h" |
| 24 | #include "mlir/IR/Value.h" |
| 25 | #include "mlir/Interfaces/ControlFlowInterfaces.h" |
| 26 | #include "mlir/Interfaces/InferIntRangeInterface.h" |
| 27 | #include "mlir/Interfaces/LoopLikeInterface.h" |
| 28 | #include "mlir/Support/DebugStringHelper.h" |
| 29 | #include "mlir/Support/LLVM.h" |
| 30 | #include "llvm/ADT/STLExtras.h" |
| 31 | #include "llvm/Support/Casting.h" |
| 32 | #include "llvm/Support/Debug.h" |
| 33 | #include "llvm/Support/DebugLog.h" |
| 34 | #include <cassert> |
| 35 | #include <optional> |
| 36 | #include <utility> |
| 37 | |
| 38 | #define DEBUG_TYPE "int-range-analysis" |
| 39 | |
| 40 | using namespace mlir; |
| 41 | using namespace mlir::dataflow; |
| 42 | |
| 43 | namespace mlir::dataflow { |
| 44 | LogicalResult staticallyNonNegative(DataFlowSolver &solver, Value v) { |
| 45 | auto *result = solver.lookupState<IntegerValueRangeLattice>(anchor: v); |
| 46 | if (!result || result->getValue().isUninitialized()) |
| 47 | return failure(); |
| 48 | const ConstantIntRanges &range = result->getValue().getValue(); |
| 49 | return success(IsSuccess: range.smin().isNonNegative()); |
| 50 | } |
| 51 | |
| 52 | LogicalResult staticallyNonNegative(DataFlowSolver &solver, Operation *op) { |
| 53 | auto nonNegativePred = [&solver](Value v) -> bool { |
| 54 | return succeeded(Result: staticallyNonNegative(solver, v)); |
| 55 | }; |
| 56 | return success(IsSuccess: llvm::all_of(Range: op->getOperands(), P: nonNegativePred) && |
| 57 | llvm::all_of(Range: op->getResults(), P: nonNegativePred)); |
| 58 | } |
| 59 | } // namespace mlir::dataflow |
| 60 | |
| 61 | /// Number of merge-site joins a single integer-range lattice element is |
| 62 | /// allowed to absorb before `IntegerValueRangeLattice::join` forces it to |
| 63 | /// its max as a sound over-approximation. |
| 64 | /// |
| 65 | /// Trade-off: high enough that realistic loops with dynamic bounds (which |
| 66 | /// typically converge to a tight range in a small number of merge |
| 67 | /// iterations) are not widened prematurely; low enough that the +1 |
| 68 | /// ratchet pathology this widening exists to cut off (loop-carried ranges |
| 69 | /// growing by one per worklist visit) terminates after at most this many |
| 70 | /// extra solver iterations rather than ~2^31. |
| 71 | static constexpr unsigned kIntegerRangeWideningBudget = 128; |
| 72 | |
| 73 | ChangeResult IntegerValueRangeLattice::join(const AbstractSparseLattice &rhs) { |
| 74 | ChangeResult changed = Lattice::join(rhs); |
| 75 | if (mergeChangeCount >= kIntegerRangeWideningBudget) { |
| 76 | return changed | Lattice::join(rhs: IntegerValueRange::getMaxRange( |
| 77 | value: cast<Value>(Val: getAnchor()))); |
| 78 | } |
| 79 | if (changed == ChangeResult::Change) |
| 80 | ++mergeChangeCount; |
| 81 | return changed; |
| 82 | } |
| 83 | |
| 84 | LogicalResult IntegerRangeAnalysis::visitOperation( |
| 85 | Operation *op, ArrayRef<const IntegerValueRangeLattice *> operands, |
| 86 | ArrayRef<IntegerValueRangeLattice *> results) { |
| 87 | auto inferrable = dyn_cast<InferIntRangeInterface>(Val: op); |
| 88 | if (!inferrable) { |
| 89 | setAllToEntryStates(results); |
| 90 | return success(); |
| 91 | } |
| 92 | |
| 93 | LDBG() << "Inferring ranges for " |
| 94 | << OpWithFlags(op, OpPrintingFlags().skipRegions()); |
| 95 | auto argRanges = llvm::map_to_vector( |
| 96 | C&: operands, F: [](const IntegerValueRangeLattice *lattice) { |
| 97 | return lattice->getValue(); |
| 98 | }); |
| 99 | |
| 100 | auto joinCallback = [&](Value v, const IntegerValueRange &attrs) { |
| 101 | auto result = dyn_cast<OpResult>(Val&: v); |
| 102 | if (!result) |
| 103 | return; |
| 104 | assert(llvm::is_contained(op->getResults(), result)); |
| 105 | |
| 106 | LDBG() << "Inferred range " << attrs; |
| 107 | IntegerValueRangeLattice *lattice = results[result.getResultNumber()]; |
| 108 | propagateIfChanged(state: lattice, changed: lattice->join(rhs: attrs)); |
| 109 | }; |
| 110 | |
| 111 | inferrable.inferResultRangesFromOptional(argRanges, setResultRanges: joinCallback); |
| 112 | return success(); |
| 113 | } |
| 114 | |
| 115 | void IntegerRangeAnalysis::visitNonControlFlowArguments( |
| 116 | Operation *op, const RegionSuccessor &successor, |
| 117 | ValueRange nonSuccessorInputs, |
| 118 | ArrayRef<IntegerValueRangeLattice *> nonSuccessorInputLattices, |
| 119 | GetLatticeFn getLattice) { |
| 120 | assert(nonSuccessorInputs.size() == nonSuccessorInputLattices.size() && |
| 121 | "size mismatch" ); |
| 122 | if (auto inferrable = dyn_cast<InferIntRangeInterface>(Val: op)) { |
| 123 | LDBG() << "Inferring ranges for " |
| 124 | << OpWithFlags(op, OpPrintingFlags().skipRegions()); |
| 125 | |
| 126 | auto argRanges = llvm::map_to_vector(C: op->getOperands(), F: [&](Value value) { |
| 127 | return getLattice(value)->getValue(); |
| 128 | }); |
| 129 | |
| 130 | auto joinCallback = [&](Value v, const IntegerValueRange &attrs) { |
| 131 | auto it = llvm::find(Range&: nonSuccessorInputs, Val: v); |
| 132 | if (it == nonSuccessorInputs.end()) |
| 133 | return; |
| 134 | |
| 135 | LDBG() << "Inferred range " << attrs; |
| 136 | unsigned nonSuccessorInputIdx = |
| 137 | std::distance(first: nonSuccessorInputs.begin(), last: it); |
| 138 | IntegerValueRangeLattice *lattice = |
| 139 | nonSuccessorInputLattices[nonSuccessorInputIdx]; |
| 140 | propagateIfChanged(state: lattice, changed: lattice->join(rhs: attrs)); |
| 141 | }; |
| 142 | |
| 143 | inferrable.inferResultRangesFromOptional(argRanges, setResultRanges: joinCallback); |
| 144 | return; |
| 145 | } |
| 146 | |
| 147 | /// Given a lower bound, upper bound, or step from a LoopLikeInterface return |
| 148 | /// the lower/upper bound for that result if possible. |
| 149 | auto getLoopBoundFromFold = [&](OpFoldResult loopBound, Type boundType, |
| 150 | bool getUpper) { |
| 151 | unsigned int width = ConstantIntRanges::getStorageBitwidth(type: boundType); |
| 152 | if (auto attr = dyn_cast<Attribute>(Val&: loopBound)) { |
| 153 | if (auto bound = dyn_cast<IntegerAttr>(Val&: attr)) |
| 154 | return bound.getValue(); |
| 155 | } else if (auto value = llvm::dyn_cast<Value>(Val&: loopBound)) { |
| 156 | const IntegerValueRangeLattice *lattice = getLattice(value); |
| 157 | if (lattice != nullptr && !lattice->getValue().isUninitialized()) |
| 158 | return getUpper ? lattice->getValue().getValue().smax() |
| 159 | : lattice->getValue().getValue().smin(); |
| 160 | } |
| 161 | // Given the results of getConstant{Lower,Upper}Bound() |
| 162 | // or getConstantStep() on a LoopLikeInterface return the lower/upper |
| 163 | // bound |
| 164 | return getUpper ? APInt::getSignedMaxValue(numBits: width) |
| 165 | : APInt::getSignedMinValue(numBits: width); |
| 166 | }; |
| 167 | |
| 168 | // Infer bounds for loop arguments that have static bounds |
| 169 | if (auto loop = dyn_cast<LoopLikeOpInterface>(Val: op)) { |
| 170 | std::optional<llvm::SmallVector<Value>> maybeIvs = |
| 171 | loop.getLoopInductionVars(); |
| 172 | if (!maybeIvs) { |
| 173 | return SparseForwardDataFlowAnalysis::visitNonControlFlowArguments( |
| 174 | op, successor, nonSuccessorInputs, nonSuccessorInputLattices, |
| 175 | getLattice); |
| 176 | } |
| 177 | // Some loop implementations may return nullopt for non-constant bounds |
| 178 | // (e.g. affine.for with a dynamic upper bound), even when induction |
| 179 | // variables exist. Fall back to the generic analysis in that case. |
| 180 | std::optional<SmallVector<OpFoldResult>> maybeLowerBounds = |
| 181 | loop.getLoopLowerBounds(); |
| 182 | std::optional<SmallVector<OpFoldResult>> maybeUpperBounds = |
| 183 | loop.getLoopUpperBounds(); |
| 184 | std::optional<SmallVector<OpFoldResult>> maybeSteps = loop.getLoopSteps(); |
| 185 | if (!maybeLowerBounds || !maybeUpperBounds || !maybeSteps) { |
| 186 | return SparseForwardDataFlowAnalysis::visitNonControlFlowArguments( |
| 187 | op, successor, nonSuccessorInputs, nonSuccessorInputLattices, |
| 188 | getLattice); |
| 189 | } |
| 190 | SmallVector<OpFoldResult> lowerBounds = *maybeLowerBounds; |
| 191 | SmallVector<OpFoldResult> upperBounds = *maybeUpperBounds; |
| 192 | SmallVector<OpFoldResult> steps = *maybeSteps; |
| 193 | for (auto [iv, lowerBound, upperBound, step] : |
| 194 | llvm::zip_equal(t&: *maybeIvs, u&: lowerBounds, args&: upperBounds, args&: steps)) { |
| 195 | APInt min = getLoopBoundFromFold(lowerBound, iv.getType(), |
| 196 | /*getUpper=*/false); |
| 197 | APInt max = getLoopBoundFromFold(upperBound, iv.getType(), |
| 198 | /*getUpper=*/true); |
| 199 | // Assume positivity for uniscoverable steps by way of getUpper = true. |
| 200 | APInt stepVal = |
| 201 | getLoopBoundFromFold(step, iv.getType(), /*getUpper=*/true); |
| 202 | |
| 203 | if (stepVal.isNegative()) { |
| 204 | std::swap(a&: min, b&: max); |
| 205 | } else { |
| 206 | // Correct the upper bound by subtracting 1 so that it becomes a <= |
| 207 | // bound, because loops do not generally include their upper bound. |
| 208 | max -= 1; |
| 209 | } |
| 210 | |
| 211 | // If we infer the lower bound to be larger than the upper bound, the |
| 212 | // resulting range is meaningless and should not be used in further |
| 213 | // inferences. |
| 214 | if (max.sge(RHS: min)) { |
| 215 | IntegerValueRangeLattice *ivEntry = getLatticeElement(value: iv); |
| 216 | auto ivRange = ConstantIntRanges::fromSigned(smin: min, smax: max); |
| 217 | propagateIfChanged(state: ivEntry, changed: ivEntry->join(rhs: IntegerValueRange{ivRange})); |
| 218 | } |
| 219 | } |
| 220 | return; |
| 221 | } |
| 222 | |
| 223 | return SparseForwardDataFlowAnalysis::visitNonControlFlowArguments( |
| 224 | op, successor, nonSuccessorInputs, nonSuccessorInputLattices, getLattice); |
| 225 | } |
| 226 | |