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
40using namespace mlir;
41using namespace mlir::dataflow;
42
43namespace mlir::dataflow {
44LogicalResult 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
52LogicalResult 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.
71static constexpr unsigned kIntegerRangeWideningBudget = 128;
72
73ChangeResult 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
84LogicalResult 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
115void 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