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"
52 if (
auto *parent = value.getDefiningOp())
53 dialect = parent->getDialect();
55 dialect = value.getParentBlock()->getParentOp()->getDialect();
64 auto inferrable = dyn_cast<InferIntRangeInterface>(op);
68 LLVM_DEBUG(llvm::dbgs() <<
"Inferring ranges for " << *op <<
"\n");
69 auto argRanges = llvm::map_to_vector(
75 auto result = dyn_cast<OpResult>(v);
78 assert(llvm::is_contained(op->
getResults(), result));
80 LLVM_DEBUG(llvm::dbgs() <<
"Inferred range " << attrs <<
"\n");
91 return op->hasTrait<OpTrait::IsTerminator>();
94 !(lattice->
getValue() == oldRange)) {
95 LLVM_DEBUG(llvm::dbgs() <<
"Loop variant loop result detected\n");
101 inferrable.inferResultRangesFromOptional(argRanges, joinCallback);
107 if (
auto inferrable = dyn_cast<InferIntRangeInterface>(op)) {
108 LLVM_DEBUG(llvm::dbgs() <<
"Inferring ranges for " << *op <<
"\n");
111 return getLatticeElementFor(op, value)->getValue();
115 auto arg = dyn_cast<BlockArgument>(v);
121 LLVM_DEBUG(llvm::dbgs() <<
"Inferred range " << attrs <<
"\n");
132 return op->hasTrait<OpTrait::IsTerminator>();
135 !(lattice->
getValue() == oldRange)) {
136 LLVM_DEBUG(llvm::dbgs() <<
"Loop variant loop result detected\n");
142 inferrable.inferResultRangesFromOptional(argRanges, joinCallback);
149 auto getLoopBoundFromFold = [&](std::optional<OpFoldResult> loopBound,
150 Type boundType,
bool getUpper) {
152 if (loopBound.has_value()) {
155 dyn_cast_or_null<IntegerAttr>(loopBound->get<
Attribute>()))
156 return bound.getValue();
157 }
else if (
auto value = llvm::dyn_cast_if_present<Value>(*loopBound)) {
168 return getUpper ? APInt::getSignedMaxValue(width)
169 : APInt::getSignedMinValue(width);
173 if (
auto loop = dyn_cast<LoopLikeOpInterface>(op)) {
174 std::optional<Value> iv = loop.getSingleInductionVar();
177 op, successor, argLattices, firstIndex);
179 std::optional<OpFoldResult> lowerBound = loop.getSingleLowerBound();
180 std::optional<OpFoldResult> upperBound = loop.getSingleUpperBound();
181 std::optional<OpFoldResult> step = loop.getSingleStep();
182 APInt
min = getLoopBoundFromFold(lowerBound, iv->getType(),
184 APInt
max = getLoopBoundFromFold(upperBound, iv->getType(),
188 getLoopBoundFromFold(step, iv->getType(),
true);
190 if (stepVal.isNegative()) {
210 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.
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...
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...
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...
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 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...