27 #include "llvm/ADT/STLExtras.h"
28 #include "llvm/Support/Casting.h"
29 #include "llvm/Support/Debug.h"
34 #define DEBUG_TYPE "int-range-analysis"
43 APInt umin = APInt::getMinValue(width);
44 APInt umax = APInt::getMaxValue(width);
45 APInt smin = width != 0 ? APInt::getSignedMinValue(width) : umin;
46 APInt smax = width != 0 ? APInt::getSignedMaxValue(width) : umax;
63 if (
auto *parent = value.getDefiningOp())
64 dialect = parent->getDialect();
66 dialect = value.getParentBlock()->getParentOp()->getDialect();
77 return lattice->
getValue().isUninitialized();
82 auto inferrable = dyn_cast<InferIntRangeInterface>(op);
86 LLVM_DEBUG(llvm::dbgs() <<
"Inferring ranges for " << *op <<
"\n");
93 auto result = dyn_cast<OpResult>(v);
96 assert(llvm::is_contained(op->
getResults(), result));
98 LLVM_DEBUG(llvm::dbgs() <<
"Inferred range " << attrs <<
"\n");
109 return op->hasTrait<OpTrait::IsTerminator>();
112 !(lattice->
getValue() == oldRange)) {
113 LLVM_DEBUG(llvm::dbgs() <<
"Loop variant loop result detected\n");
119 inferrable.inferResultRanges(argRanges, joinCallback);
125 if (
auto inferrable = dyn_cast<InferIntRangeInterface>(op)) {
126 LLVM_DEBUG(llvm::dbgs() <<
"Inferring ranges for " << *op <<
"\n");
129 return getLatticeElementFor(op, value)->getValue().isUninitialized();
134 return getLatticeElementFor(op, value)->getValue().getValue();
138 auto arg = dyn_cast<BlockArgument>(v);
144 LLVM_DEBUG(llvm::dbgs() <<
"Inferred range " << attrs <<
"\n");
155 return op->hasTrait<OpTrait::IsTerminator>();
158 !(lattice->
getValue() == oldRange)) {
159 LLVM_DEBUG(llvm::dbgs() <<
"Loop variant loop result detected\n");
165 inferrable.inferResultRanges(argRanges, joinCallback);
172 auto getLoopBoundFromFold = [&](std::optional<OpFoldResult> loopBound,
173 Type boundType,
bool getUpper) {
175 if (loopBound.has_value()) {
178 dyn_cast_or_null<IntegerAttr>(loopBound->get<
Attribute>()))
179 return bound.getValue();
180 }
else if (
auto value = llvm::dyn_cast_if_present<Value>(*loopBound)) {
183 if (lattice !=
nullptr)
191 return getUpper ? APInt::getSignedMaxValue(width)
192 : APInt::getSignedMinValue(width);
196 if (
auto loop = dyn_cast<LoopLikeOpInterface>(op)) {
197 std::optional<Value> iv = loop.getSingleInductionVar();
200 op, successor, argLattices, firstIndex);
202 std::optional<OpFoldResult> lowerBound = loop.getSingleLowerBound();
203 std::optional<OpFoldResult> upperBound = loop.getSingleUpperBound();
204 std::optional<OpFoldResult> step = loop.getSingleStep();
205 APInt
min = getLoopBoundFromFold(lowerBound, iv->getType(),
207 APInt
max = getLoopBoundFromFold(upperBound, iv->getType(),
211 getLoopBoundFromFold(step, iv->getType(),
true);
213 if (stepVal.isNegative()) {
228 op, successor, argLattices, firstIndex);
static Value max(ImplicitLocOpBuilder &builder, Value value, Value bound)
static Value min(ImplicitLocOpBuilder &builder, Value value, Value bound)
ProgramPoint point
The program point to which the state belongs.
Attributes are known-constant values of operations.
A set of arbitrary-precision integers representing bounds on a given integer value.
const APInt & smax() const
The maximum value of an integer when it is interpreted as signed.
const APInt & smin() const
The minimum value of an integer when it is interpreted as signed.
static ConstantIntRanges fromSigned(const APInt &smin, const APInt &smax)
Create an ConstantIntRanges with the signed minimum and maximum equal to smin and smax,...
static unsigned getStorageBitwidth(Type type)
Return the bitwidth that should be used for integer ranges describing type.
std::optional< APInt > getConstantValue() const
If either the signed or unsigned interpretations of the range indicate that the value it bounds is a ...
void propagateIfChanged(AnalysisState *state, ChangeResult changed)
Propagate an update to a state if it changed.
The general data-flow analysis solver.
StateT * getOrCreateState(PointT point)
Get the state associated with the given program point.
void propagateIfChanged(AnalysisState *state, ChangeResult changed)
Propagate an update to an analysis state if it changed by pushing dependent work items to the back of...
Dialects are groups of MLIR operations, types and attributes, as well as behavior associated with the...
Operation is the basic unit of execution within MLIR.
operand_range getOperands()
Returns an iterator on the underlying Value's.
result_range getResults()
This class represents a successor of a region.
Region * getSuccessor() const
Return the given region successor.
BlockArgListType getArguments()
Instances of the Type class are uniqued, have an immutable identifier and an optional mutable compone...
This class represents an instance of an SSA value in the MLIR system, representing a computable value...
Type getType() const
Return the type of this value.
user_range getUsers() const
void onUpdate(DataFlowSolver *solver) const override
When the lattice gets updated, propagate an update to users of the value using its use-def chain to s...
This lattice value represents a known constant value of a lattice.
static ConstantValue getUnknownConstant()
The state where the constant value is unknown.
void visitOperation(Operation *op, ArrayRef< const IntegerValueRangeLattice * > operands, ArrayRef< IntegerValueRangeLattice * > results) override
Visit an operation.
void visitNonControlFlowArguments(Operation *op, const RegionSuccessor &successor, ArrayRef< IntegerValueRangeLattice * > argLattices, unsigned firstIndex) override
Visit block arguments or operation results of an operation with region control-flow for which values ...
This lattice element represents the integer value range of an SSA value.
void onUpdate(DataFlowSolver *solver) const override
If the range can be narrowed to an integer constant, update the constant value of the SSA value.
This lattice value represents the integer range of an SSA value.
const ConstantIntRanges & getValue() const
Get the known integer value range.
bool isUninitialized() const
Whether the range is uninitialized.
static IntegerValueRange getMaxRange(Value value)
Create a maximal range ([0, uint_max(t)] / [int_min(t), int_max(t)]) range that is used to mark the v...
This class represents a lattice holding a specific value of type ValueT.
IntegerValueRange & getValue()
Return the value held by this lattice.
ChangeResult join(const AbstractSparseLattice &rhs) override
Join the information contained in the 'rhs' lattice into this lattice.
const IntegerValueRangeLattice * getLatticeElementFor(ProgramPoint point, Value value)
Get the lattice element for a value and create a dependency on the provided program point.
IntegerValueRangeLattice * getLatticeElement(Value value) override
Get the lattice element for a value.
void setAllToEntryStates(ArrayRef< IntegerValueRangeLattice * > lattices)
virtual void visitNonControlFlowArguments(Operation *op, const RegionSuccessor &successor, ArrayRef< StateT * > argLattices, unsigned firstIndex)
Given an operation with possible region control-flow, the lattices of the operands,...
Include the generated interface declarations.
ChangeResult
A result type used to indicate if a change happened.
auto get(MLIRContext *context, Ts &&...params)
Helper method that injects context only if needed, this helps unify some of the attribute constructio...