28 #include "llvm/ADT/STLExtras.h"
29 #include "llvm/Support/Casting.h"
30 #include "llvm/Support/Debug.h"
35 #define DEBUG_TYPE "int-range-analysis"
43 if (!result || result->getValue().isUninitialized())
46 return success(range.
smin().isNonNegative());
50 auto nonNegativePred = [&solver](
Value v) ->
bool {
53 return success(llvm::all_of(op->
getOperands(), nonNegativePred) &&
54 llvm::all_of(op->
getResults(), nonNegativePred));
64 auto value = cast<Value>(
anchor);
71 if (
auto *parent = value.getDefiningOp())
72 dialect = parent->getDialect();
74 dialect = value.getParentBlock()->getParentOp()->getDialect();
84 auto inferrable = dyn_cast<InferIntRangeInterface>(op);
90 LLVM_DEBUG(llvm::dbgs() <<
"Inferring ranges for " << *op <<
"\n");
91 auto argRanges = llvm::map_to_vector(
97 auto result = dyn_cast<OpResult>(v);
100 assert(llvm::is_contained(op->
getResults(), result));
102 LLVM_DEBUG(llvm::dbgs() <<
"Inferred range " << attrs <<
"\n");
113 return op->hasTrait<OpTrait::IsTerminator>();
116 !(lattice->
getValue() == oldRange)) {
117 LLVM_DEBUG(llvm::dbgs() <<
"Loop variant loop result detected\n");
123 inferrable.inferResultRangesFromOptional(argRanges, joinCallback);
130 if (
auto inferrable = dyn_cast<InferIntRangeInterface>(op)) {
131 LLVM_DEBUG(llvm::dbgs() <<
"Inferring ranges for " << *op <<
"\n");
134 return getLatticeElementFor(getProgramPointAfter(op), value)->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.inferResultRangesFromOptional(argRanges, joinCallback);
172 auto getLoopBoundFromFold = [&](std::optional<OpFoldResult> loopBound,
173 Type boundType,
Block *block,
bool getUpper) {
175 if (loopBound.has_value()) {
176 if (
auto attr = dyn_cast<Attribute>(*loopBound)) {
177 if (
auto bound = dyn_cast_or_null<IntegerAttr>(attr))
178 return bound.getValue();
179 }
else if (
auto value = llvm::dyn_cast_if_present<Value>(*loopBound)) {
190 return getUpper ? APInt::getSignedMaxValue(width)
191 : APInt::getSignedMinValue(width);
195 if (
auto loop = dyn_cast<LoopLikeOpInterface>(op)) {
196 std::optional<Value> iv = loop.getSingleInductionVar();
199 op, successor, argLattices, firstIndex);
201 Block *block = iv->getParentBlock();
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(), block,
207 APInt
max = getLoopBoundFromFold(upperBound, iv->getType(), block,
211 getLoopBoundFromFold(step, iv->getType(), block,
true);
213 if (stepVal.isNegative()) {
233 op, successor, argLattices, firstIndex);
static Value max(ImplicitLocOpBuilder &builder, Value value, Value bound)
static Value min(ImplicitLocOpBuilder &builder, Value value, Value bound)
LatticeAnchor anchor
The lattice anchor to which the state belongs.
Block represents an ordered list 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.
ProgramPoint * getProgramPointBefore(Operation *op)
Get a uniqued program point instance.
The general data-flow analysis solver.
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...
const StateT * lookupState(AnchorT anchor) const
Lookup an analysis state for the given lattice anchor.
StateT * getOrCreateState(AnchorT anchor)
Get the state associated with the given lattice anchor.
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.
LogicalResult 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,...
LogicalResult staticallyNonNegative(DataFlowSolver &solver, Operation *op)
Succeeds if an op can be converted to its unsigned equivalent without changing its semantics.
Include the generated interface declarations.
const FrozenRewritePatternSet GreedyRewriteConfig bool * changed
ChangeResult
A result type used to indicate if a change happened.
Type getElementTypeOrSelf(Type type)
Return the element type or return the type itself.
auto get(MLIRContext *context, Ts &&...params)
Helper method that injects context only if needed, this helps unify some of the attribute constructio...