A helper class to be used with ValueBoundsOpInterface. More...

#include "mlir/Interfaces/ValueBoundsOpInterface.h"

Inheritance diagram for mlir::ValueBoundsConstraintSet:

Classes
class	BoundBuilder
	Helper class that builds a bound for a shaped value dimension or index-typed value. More...
class	Variable
	A variable that can be added to the constraint set as a "column". More...

Public Types
enum	ComparisonOperator { LT , LE , EQ , GT , GE }
	Comparison operator for ValueBoundsConstraintSet::compare. More...
using	StopConditionFn
	The stop condition when traversing the backward slice of a shaped value/ index-type value.

Public Member Functions
void	populateConstraints (Value value, std::optional< int64_t > dim)
	Traverse the IR starting from the given value/dim and populate constraints as long as the stop condition holds.
bool	populateAndCompare (const Variable &lhs, ComparisonOperator cmp, const Variable &rhs)
	Populate constraints for lhs/rhs (until the stop condition is met).
BoundBuilder	bound (Value value)
	Add a bound for the given index-typed value or shaped value.
AffineExpr	getExpr (Value value, std::optional< int64_t > dim=std::nullopt)
	Return an expression that represents the given index-typed value or shaped value dimension.
AffineExpr	getExpr (OpFoldResult ofr)
	Return an expression that represents a constant or index-typed SSA value.
AffineExpr	getExpr (int64_t constant)
	Return an expression that represents a constant.
void	dump () const
	Debugging only: Dump the constraint set and the column-to-value/dim mapping to llvm::errs.

Static Public Member Functions
static LogicalResult	computeBound (AffineMap &resultMap, ValueDimList &mapOperands, presburger::BoundType type, const Variable &var, StopConditionFn stopCondition, bool closedUB=false)
	Compute a bound for the given variable.
static LogicalResult	computeDependentBound (AffineMap &resultMap, ValueDimList &mapOperands, presburger::BoundType type, const Variable &var, ValueDimList dependencies, bool closedUB=false)
	Compute a bound in terms of the values/dimensions in dependencies.
static LogicalResult	computeIndependentBound (AffineMap &resultMap, ValueDimList &mapOperands, presburger::BoundType type, const Variable &var, ValueRange independencies, bool closedUB=false)
	Compute a bound in that is independent of all values in independencies.
static FailureOr< int64_t >	computeConstantBound (presburger::BoundType type, const Variable &var, const StopConditionFn &stopCondition=nullptr, bool closedUB=false)
	Compute a constant bound for the given variable.
static FailureOr< int64_t >	computeConstantDelta (Value value1, Value value2, std::optional< int64_t > dim1=std::nullopt, std::optional< int64_t > dim2=std::nullopt)
	Compute a constant delta between the given two values.
static bool	compare (const Variable &lhs, ComparisonOperator cmp, const Variable &rhs)
	Return "true" if "lhs cmp rhs" was proven to hold.
static llvm::FailureOr< bool >	strongCompare (const Variable &lhs, ComparisonOperator cmp, const Variable &rhs)
	This function is similar to ValueBoundsConstraintSet::compare, except that it returns false if !(lhs cmp rhs), and failure if neither the relation nor its inverse relation could be proven.
static FailureOr< bool >	areEqual (const Variable &var1, const Variable &var2)
	Compute whether the given variables are equal.
static FailureOr< bool >	areOverlappingSlices (MLIRContext *ctx, const HyperrectangularSlice &slice1, const HyperrectangularSlice &slice2)
	Return "true" if the given slices are guaranteed to be overlapping.
static FailureOr< bool >	areEquivalentSlices (MLIRContext *ctx, const HyperrectangularSlice &slice1, const HyperrectangularSlice &slice2)
	Return "true" if the given slices are guaranteed to be equivalent.

Static Public Attributes
static char	ID = 0

Protected Types
using	ValueDim = std::pair<Value, int64_t>
	An index-typed value or the dimension of a shaped-type value.

Protected Member Functions
	ValueBoundsConstraintSet (MLIRContext *ctx, const StopConditionFn &stopCondition, bool addConservativeSemiAffineBounds=false)
bool	comparePos (int64_t lhsPos, ComparisonOperator cmp, int64_t rhsPos)
	Return "true" if, based on the current state of the constraint system, "lhs cmp rhs" was proven to hold.
llvm::FailureOr< bool >	strongComparePos (int64_t lhsPos, ComparisonOperator cmp, int64_t rhsPos)
	Return "true" if, based on the current state of the constraint system, "lhs cmp rhs" was proven to hold.
int64_t	populateConstraints (AffineMap map, ValueDimList mapOperands)
	Given an affine map with a single result (and map operands), add a new column to the constraint set that represents the result of the map.
void	processWorklist ()
	Iteratively process all elements on the worklist until an index-typed value or shaped value meets stopCondition.
void	addBound (presburger::BoundType type, int64_t pos, AffineExpr expr)
	Bound the given column in the underlying constraint set by the given expression.
int64_t	getPos (Value value, std::optional< int64_t > dim=std::nullopt) const
	Return the column position of the given value/dimension.
AffineExpr	getPosExpr (int64_t pos)
	Return an affine expression that represents column pos in the constraint set.
bool	isMapped (Value value, std::optional< int64_t > dim=std::nullopt) const
	Return "true" if the given value/dim is mapped (i.e., has a corresponding column in the constraint system).
int64_t	insert (Value value, std::optional< int64_t > dim, bool isSymbol=true, bool addToWorklist=true)
	Insert a value/dimension into the constraint set.
int64_t	insert (bool isSymbol=true)
	Insert an anonymous column into the constraint set.
int64_t	insert (AffineMap map, const ValueDimList &operands, bool isSymbol=true)
	Insert the given affine map and its bound operands as a new column in the constraint system.
int64_t	insert (const Variable &var, bool isSymbol=true)
void	projectOut (int64_t pos)
	Project out the given column in the constraint set.
void	projectOut (function_ref< bool(ValueDim)> condition)
	Project out all columns for which the condition holds.
void	projectOutAnonymous (std::optional< int64_t > except=std::nullopt)

Protected Attributes
SmallVector< std::optional< ValueDim > >	positionToValueDim
	Mapping of columns to values/shape dimensions.
DenseMap< ValueDim, int64_t >	valueDimToPosition
	Reverse mapping of values/shape dimensions to columns.
std::queue< int64_t >	worklist
	Worklist of values/shape dimensions that have not been processed yet.
FlatLinearConstraints	cstr
	Constraint system of equalities and inequalities.
Builder	builder
	Builder for constructing affine expressions.
StopConditionFn	stopCondition = nullptr
	The current stop condition function.
bool	addConservativeSemiAffineBounds = false
	Should conservative bounds be added for semi-affine expressions.

Static Protected Attributes
static constexpr int64_t	kIndexValue = -1
	Dimension identifier to indicate a value is index-typed.

Detailed Description

A helper class to be used with ValueBoundsOpInterface.

This class stores a constraint system and mapping of constrained variables to index-typed values or dimension sizes of shaped values.

Interface implementations of ValueBoundsOpInterface use addBounds to insert constraints about their results and/or region block arguments into the constraint set in the form of an AffineExpr. When a bound should be expressed in terms of another value/dimension, getExpr can be used to retrieve an AffineExpr that represents the specified value/dimension.

When a value/dimension is retrieved for the first time through getExpr, it is added to an internal worklist. See computeBound for more details.

Note: Any modification of existing IR invalides the data stored in this class. Adding new operations is allowed.

Definition at line 68 of file ValueBoundsOpInterface.h.

Member Typedef Documentation

◆ StopConditionFn

using mlir::ValueBoundsConstraintSet::StopConditionFn

Initial value:

std::function<bool(

Value, std::optional<int64_t> , ValueBoundsConstraintSet &cstr)>

bool

mlir::ValueBoundsConstraintSet::ValueBoundsConstraintSet

ValueBoundsConstraintSet(MLIRContext *ctx, const StopConditionFn &stopCondition, bool addConservativeSemiAffineBounds=false)

Definition ValueBoundsOpInterface.cpp:156

mlir::ValueBoundsConstraintSet::cstr

FlatLinearConstraints cstr

Constraint system of equalities and inequalities.

Definition ValueBoundsOpInterface.h:426

mlir::Value

This class represents an instance of an SSA value in the MLIR system, representing a computable value...

Definition Value.h:96

The stop condition when traversing the backward slice of a shaped value/ index-type value.

The traversal continues until the stop condition evaluates to "true" for a value.

The first parameter of the function is the shaped value/index-typed value. The second parameter is the dimension in case of a shaped value. The third parameter is this constraint set.

Definition at line 162 of file ValueBoundsOpInterface.h.

◆ ValueDim

using mlir::ValueBoundsConstraintSet::ValueDim = std::pair<Value, int64_t>

protected

An index-typed value or the dimension of a shaped-type value.

Definition at line 327 of file ValueBoundsOpInterface.h.

Member Enumeration Documentation

◆ ComparisonOperator

enum mlir::ValueBoundsConstraintSet::ComparisonOperator

Comparison operator for ValueBoundsConstraintSet::compare.

Enumerator
LT
LE
EQ
GT
GE

Definition at line 239 of file ValueBoundsOpInterface.h.

Constructor & Destructor Documentation

◆ ValueBoundsConstraintSet()

ValueBoundsConstraintSet::ValueBoundsConstraintSet	(	MLIRContext *	ctx,
		const StopConditionFn &	stopCondition,
		bool	addConservativeSemiAffineBounds = false )

protected

Definition at line 156 of file ValueBoundsOpInterface.cpp.

References addConservativeSemiAffineBounds, builder, and stopCondition.

Referenced by compare(), computeBound(), computeConstantBound(), computeDependentBound(), computeIndependentBound(), and strongCompare().

Member Function Documentation

◆ addBound()

void ValueBoundsConstraintSet::addBound	(	presburger::BoundType	type,
		int64_t	pos,
		AffineExpr	expr )

protected

Bound the given column in the underlying constraint set by the given expression.

Definition at line 180 of file ValueBoundsOpInterface.cpp.

References addConservativeSemiAffineBounds, cstr, mlir::AffineMap::get(), mlir::FlatLinearConstraints::No, and mlir::FlatLinearConstraints::Yes.

Referenced by insert().

◆ areEqual()

FailureOr< bool > ValueBoundsConstraintSet::areEqual	(	const Variable &	var1,
		const Variable &	var2 )

static

Compute whether the given variables are equal.

Return "failure" if equality could not be determined.

Definition at line 821 of file ValueBoundsOpInterface.cpp.

References EQ, and strongCompare().

Referenced by areEquivalentSlices(), mlir::tensor::getCollapsedExtractSliceInfo(), mlir::tensor::isCastLikeExtractSliceOp(), mlir::tensor::isCastLikeInsertSliceOp(), and mlir::vector::isDisjointTransferIndices().

◆ areEquivalentSlices()

FailureOr< bool > ValueBoundsConstraintSet::areEquivalentSlices	(	MLIRContext *	ctx,
		const HyperrectangularSlice &	slice1,
		const HyperrectangularSlice &	slice2 )

static

Return "true" if the given slices are guaranteed to be equivalent.

Return "false" if the given slices are guaranteed to be non-equivalent. Return "failure" if unknown.

Slices are equivalent if their offsets, sizes and strices are equal.

Definition at line 890 of file ValueBoundsOpInterface.cpp.

References areEqual(), mlir::HyperrectangularSlice::getMixedOffsets(), mlir::HyperrectangularSlice::getMixedSizes(), and mlir::HyperrectangularSlice::getMixedStrides().

Referenced by mlir::detail::defaultOperatesOnEquivalentSubset().

◆ areOverlappingSlices()

FailureOr< bool > ValueBoundsConstraintSet::areOverlappingSlices	(	MLIRContext *	ctx,
		const HyperrectangularSlice &	slice1,
		const HyperrectangularSlice &	slice2 )

static

Return "true" if the given slices are guaranteed to be overlapping.

Return "false" if the given slices are guaranteed to be non-overlapping. Return "failure" if unknown.

Slices are overlapping if for all dimensions:

offset1 + size1 * stride1 <= offset2
and offset2 + size2 * stride2 <= offset1

Slice are non-overlapping if the above constraint is not satisfied for at least one dimension.

Definition at line 826 of file ValueBoundsOpInterface.cpp.

References b, computeConstantBound(), mlir::presburger::EQ, mlir::foldAttributesIntoMap(), mlir::AffineMap::get(), mlir::HyperrectangularSlice::getMixedOffsets(), mlir::HyperrectangularSlice::getMixedSizes(), and mlir::HyperrectangularSlice::getMixedStrides().

Referenced by mlir::detail::defaultOperatesOnDisjointSubset().

◆ bound()

BoundBuilder mlir::ValueBoundsConstraintSet::bound ( Value value )

inline

Add a bound for the given index-typed value or shaped value.

This function returns a builder that adds the bound.

Definition at line 300 of file ValueBoundsOpInterface.h.

Referenced by computeBound(), computeConstantBound(), getExpr(), and processWorklist().

◆ compare()

bool ValueBoundsConstraintSet::compare	(	const Variable &	lhs,
		ComparisonOperator	cmp,
		const Variable &	rhs )

static

Return "true" if "lhs cmp rhs" was proven to hold.

Return "false" if the specified relation could not be proven. This could be because the specified relation does in fact not hold or because there is not enough information in the constraint set. In other words, if we do not know for sure, this function returns "false".

This function keeps traversing the backward slice of lhs/rhs until could prove the relation or until it ran out of IR.

Definition at line 782 of file ValueBoundsOpInterface.cpp.

References cstr, lhs, rhs, stopCondition, and ValueBoundsConstraintSet().

Referenced by replaceAffineMinBoundingBoxExpression().

◆ comparePos()

bool ValueBoundsConstraintSet::comparePos	(	int64_t	lhsPos,
		ComparisonOperator	cmp,
		int64_t	rhsPos )

protected

Return "true" if, based on the current state of the constraint system, "lhs cmp rhs" was proven to hold.

Return "false" if the specified relation could not be proven. This could be because the specified relation does in fact not hold or because there is not enough information in the constraint set. In other words, if we do not know for sure, this function returns "false".

This function does not analyze any IR and does not populate any additional constraints.

Definition at line 691 of file ValueBoundsOpInterface.cpp.

References comparePos(), cstr, EQ, GE, GT, LE, and LT.

Referenced by comparePos(), populateAndCompare(), and strongComparePos().

◆ computeBound()

LogicalResult ValueBoundsConstraintSet::computeBound	(	AffineMap &	resultMap,
		ValueDimList &	mapOperands,
		presburger::BoundType	type,
		const Variable &	var,
		StopConditionFn	stopCondition,
		bool	closedUB = false )

static

Compute a bound for the given variable.

The computed bound is stored in resultMap. The operands of the bound are stored in mapOperands. An operand is either an index-type SSA value or a shaped value and a dimension.

The bound is computed in terms of values/dimensions for which stopCondition evaluates to "true". To that end, the backward slice (reverse use-def chain) of the given value is visited in a worklist-driven manner and the constraint set is populated according to ValueBoundsOpInterface for each visited value.

By default, lower/equal bounds are closed and upper bounds are open. If closedUB is set to "true", upper bounds are also closed.

Definition at line 463 of file ValueBoundsOpInterface.cpp.

References b, bound(), cstr, mlir::AffineMap::get(), mlir::ValueBoundsConstraintSet::Variable::getContext(), mlir::Value::getType(), mlir::Type::isIndex(), kIndexValue, stopCondition, success(), and ValueBoundsConstraintSet().

Referenced by computeDependentBound(), computeIndependentBound(), mlir::affine::reifyValueBound(), and mlir::arith::reifyValueBound().

◆ computeConstantBound()

FailureOr< int64_t > ValueBoundsConstraintSet::computeConstantBound	(	presburger::BoundType	type,
		const Variable &	var,
		const StopConditionFn &	stopCondition = nullptr,
		bool	closedUB = false )

static

Compute a constant bound for the given variable.

This function traverses the backward slice of the given operands in a worklist-driven manner until stopCondition evaluates to "true". The constraint set is populated according to ValueBoundsOpInterface for each visited value. (No constraints are added for values for which the stop condition evaluates to "true".)

The stop condition is optional: If none is specified, the backward slice is traversed in a breadth-first manner until a constant bound could be computed.

By default, lower/equal bounds are closed and upper bounds are open. If closedUB is set to "true", upper bounds are also closed.

Definition at line 629 of file ValueBoundsOpInterface.cpp.

References bound(), cstr, mlir::ValueBoundsConstraintSet::Variable::getContext(), stopCondition, and ValueBoundsConstraintSet().

Referenced by areOverlappingSlices(), computeConstantDelta(), mlir::affine::fullyComposeAndComputeConstantDelta(), mlir::linalg::hoistRedundantVectorTransfers(), and mlir::linalg::promoteSubviewAsNewBuffer().

◆ computeConstantDelta()

FailureOr< int64_t > ValueBoundsConstraintSet::computeConstantDelta	(	Value	value1,
		Value	value2,
		std::optional< int64_t >	dim1 = std::nullopt,
		std::optional< int64_t >	dim2 = std::nullopt )

static

Compute a constant delta between the given two values.

Return "failure" if a constant delta could not be determined.

dim1/dim2 must be nullopt if and only if value1/value2 are index-typed.

Definition at line 676 of file ValueBoundsOpInterface.cpp.

References assertValidValueDim(), b, computeConstantBound(), mlir::presburger::EQ, mlir::AffineMap::get(), and mlir::Value::getContext().

Referenced by mlir::vector::isDisjointTransferIndices().

◆ computeDependentBound()

LogicalResult ValueBoundsConstraintSet::computeDependentBound	(	AffineMap &	resultMap,
		ValueDimList &	mapOperands,
		presburger::BoundType	type,
		const Variable &	var,
		ValueDimList	dependencies,
		bool	closedUB = false )

static

Compute a bound in terms of the values/dimensions in dependencies.

The computed bound consists of only constant terms and dependent values (or dimension sizes thereof).

Definition at line 584 of file ValueBoundsOpInterface.cpp.

References computeBound(), cstr, and ValueBoundsConstraintSet().

◆ computeIndependentBound()

LogicalResult ValueBoundsConstraintSet::computeIndependentBound	(	AffineMap &	resultMap,
		ValueDimList &	mapOperands,
		presburger::BoundType	type,
		const Variable &	var,
		ValueRange	independencies,
		bool	closedUB = false )

static

Compute a bound in that is independent of all values in independencies.

Independencies are the opposite of dependencies. The computed bound does not contain any SSA values that are part of independencies. E.g., this function can be used to make ops hoistable from loops. To that end, ops must be made independent of loop induction variables (in the case of "for" loops). Loop induction variables are the independencies; they may not appear in the computed bound.

Definition at line 595 of file ValueBoundsOpInterface.cpp.

References computeBound(), cstr, mlir::Value::getDefiningOp(), mlir::Operation::getOperands(), ValueBoundsConstraintSet(), and worklist.

Referenced by makeIndependent().

◆ dump()

void ValueBoundsConstraintSet::dump ( ) const

Debugging only: Dump the constraint set and the column-to-value/dim mapping to llvm::errs.

Definition at line 931 of file ValueBoundsOpInterface.cpp.

References cstr, mlir::Operation::getName(), getOwnerOfValue(), kIndexValue, positionToValueDim, and result.

◆ getExpr() [1/3]

AffineExpr ValueBoundsConstraintSet::getExpr ( int64_t constant )

Return an expression that represents a constant.

Definition at line 260 of file ValueBoundsOpInterface.cpp.

References builder.

◆ getExpr() [2/3]

AffineExpr ValueBoundsConstraintSet::getExpr ( OpFoldResult ofr )

Return an expression that represents a constant or index-typed SSA value.

In case of a value, if this value was not used so far, it is added to the worklist.

Definition at line 252 of file ValueBoundsOpInterface.cpp.

References builder, mlir::getConstantIntValue(), and getExpr().

◆ getExpr() [3/3]

AffineExpr ValueBoundsConstraintSet::getExpr	(	Value	value,
		std::optional< int64_t >	dim = std::nullopt )

Return an expression that represents the given index-typed value or shaped value dimension.

If this value/dimension was not used so far, it is added to the worklist.

dim must be nullopt if and only if the given value is of index type.

Definition at line 203 of file ValueBoundsOpInterface.cpp.

References assertValidValueDim(), bound(), builder, mlir::getConstantIntValue(), getPos(), getPosExpr(), mlir::Value::getType(), insert(), kIndexValue, and valueDimToPosition.

Referenced by getExpr(), insert(), populateConstraints(), and processWorklist().

◆ getPos()

int64_t ValueBoundsConstraintSet::getPos	(	Value	value,
		std::optional< int64_t >	dim = std::nullopt ) const

protected

Return the column position of the given value/dimension.

Asserts that the value/dimension exists in the constraint set.

Definition at line 332 of file ValueBoundsOpInterface.cpp.

References assertValidValueDim(), mlir::Operation::getName(), getOwnerOfValue(), kIndexValue, and valueDimToPosition.

Referenced by getExpr().

◆ getPosExpr()

AffineExpr ValueBoundsConstraintSet::getPosExpr ( int64_t pos )

protected

Return an affine expression that represents column pos in the constraint set.

Definition at line 349 of file ValueBoundsOpInterface.cpp.

References builder, and cstr.

Referenced by getExpr().

◆ insert() [1/4]

int64_t ValueBoundsConstraintSet::insert	(	AffineMap	map,
		const ValueDimList &	operands,
		bool	isSymbol = true )

protected

Insert the given affine map and its bound operands as a new column in the constraint system.

Return the position of the new column. Any operands that were not analyzed yet are put on the worklist.

Definition at line 305 of file ValueBoundsOpInterface.cpp.

References addBound(), mlir::presburger::EQ, getExpr(), mlir::AffineMap::getNumDims(), mlir::AffineMap::getNumResults(), mlir::AffineMap::getResult(), insert(), and mlir::AffineExpr::replaceDimsAndSymbols().

◆ insert() [2/4]

int64_t ValueBoundsConstraintSet::insert ( bool isSymbol = true )

protected

Insert an anonymous column into the constraint set.

The column is not bound to any value/dimension. If isSymbol is set to "false", a dimension is added.

Note: There are certain affine restrictions wrt. dimensions. E.g., they cannot be multiplied. Furthermore, bounds can only be queried for dimensions but not for symbols.

Definition at line 293 of file ValueBoundsOpInterface.cpp.

References cstr, positionToValueDim, and valueDimToPosition.

◆ insert() [3/4]

int64_t ValueBoundsConstraintSet::insert	(	const Variable &	var,
		bool	isSymbol = true )

protected

Definition at line 328 of file ValueBoundsOpInterface.cpp.

◆ insert() [4/4]

int64_t ValueBoundsConstraintSet::insert	(	Value	value,
		std::optional< int64_t >	dim,
		bool	isSymbol = true,
		bool	addToWorklist = true )

protected

Insert a value/dimension into the constraint set.

If isSymbol is set to "false", a dimension is added. The value/dimension is added to the worklist if addToWorklist is set.

Note: There are certain affine restrictions wrt. dimensions. E.g., they cannot be multiplied. Furthermore, bounds can only be queried for dimensions but not for symbols.

Definition at line 264 of file ValueBoundsOpInterface.cpp.

References assertValidValueDim(), cstr, mlir::Operation::getName(), getOwnerOfValue(), kIndexValue, positionToValueDim, valueDimToPosition, and worklist.

Referenced by getExpr(), insert(), and populateConstraints().

◆ isMapped()

bool ValueBoundsConstraintSet::isMapped	(	Value	value,
		std::optional< int64_t >	dim = std::nullopt ) const

protected

Return "true" if the given value/dim is mapped (i.e., has a corresponding column in the constraint system).

Definition at line 356 of file ValueBoundsOpInterface.cpp.

References kIndexValue, and valueDimToPosition.

◆ populateAndCompare()

bool ValueBoundsConstraintSet::populateAndCompare	(	const Variable &	lhs,
		ComparisonOperator	cmp,
		const Variable &	rhs )

Populate constraints for lhs/rhs (until the stop condition is met).

Then, try to prove that, based on the current state of this constraint set (i.e., without analyzing additional IR or adding new constraints), the "lhs" value/dim is LE/LT/EQ/GT/GE than the "rhs" value/dim.

Return "true" if the specified relation between the two values/dims was proven to hold. Return "false" if the specified relation could not be proven. This could be because the specified relation does in fact not hold or because there is not enough information in the constraint set. In other words, if we do not know for sure, this function returns "false".

Definition at line 774 of file ValueBoundsOpInterface.cpp.

References comparePos(), lhs, populateConstraints(), and rhs.

◆ populateConstraints() [1/2]

int64_t ValueBoundsConstraintSet::populateConstraints	(	AffineMap	map,
		ValueDimList	mapOperands )

protected

Given an affine map with a single result (and map operands), add a new column to the constraint set that represents the result of the map.

Traverse additional IR starting from the map operands as needed (as long as the stop condition is not satisfied). Also process all values/dims that are already on the worklist. Return the position of the newly added column.

Definition at line 666 of file ValueBoundsOpInterface.cpp.

References insert(), and processWorklist().

◆ populateConstraints() [2/2]

void ValueBoundsConstraintSet::populateConstraints	(	Value	value,
		std::optional< int64_t >	dim )

Traverse the IR starting from the given value/dim and populate constraints as long as the stop condition holds.

Also process all values/dims that are already on the worklist.

Definition at line 652 of file ValueBoundsOpInterface.cpp.

References assertValidValueDim(), getExpr(), and processWorklist().

Referenced by populateAndCompare().

◆ processWorklist()

void ValueBoundsConstraintSet::processWorklist ( )

protected

Iteratively process all elements on the worklist until an index-typed value or shaped value meets stopCondition.

Such values are not processed any further.

Definition at line 363 of file ValueBoundsOpInterface.cpp.

References bound(), mlir::Value::getDefiningOp(), getExpr(), mlir::Operation::getName(), getOwnerOfValue(), mlir::Value::getType(), kIndexValue, positionToValueDim, stopCondition, and worklist.

Referenced by populateConstraints(), and populateConstraints().

◆ projectOut() [1/2]

void ValueBoundsConstraintSet::projectOut ( function_ref< bool(ValueDim)> condition )

protected

Project out all columns for which the condition holds.

Definition at line 434 of file ValueBoundsOpInterface.cpp.

References positionToValueDim, and projectOut().

◆ projectOut() [2/2]

void ValueBoundsConstraintSet::projectOut ( int64_t pos )

protected

Project out the given column in the constraint set.

Definition at line 418 of file ValueBoundsOpInterface.cpp.

References cstr, positionToValueDim, and valueDimToPosition.

Referenced by projectOut(), and projectOutAnonymous().

◆ projectOutAnonymous()

void ValueBoundsConstraintSet::projectOutAnonymous ( std::optional< int64_t > except = std::nullopt )

protected

Definition at line 449 of file ValueBoundsOpInterface.cpp.

References positionToValueDim, and projectOut().

◆ strongCompare()

FailureOr< bool > ValueBoundsConstraintSet::strongCompare	(	const Variable &	lhs,
		ComparisonOperator	cmp,
		const Variable &	rhs )

static

This function is similar to ValueBoundsConstraintSet::compare, except that it returns false if !(lhs cmp rhs), and failure if neither the relation nor its inverse relation could be proven.

Definition at line 801 of file ValueBoundsOpInterface.cpp.

References cstr, lhs, rhs, stopCondition, and ValueBoundsConstraintSet().

Referenced by areEqual(), and simplifyAffineMinMaxOp().

◆ strongComparePos()

FailureOr< bool > ValueBoundsConstraintSet::strongComparePos	(	int64_t	lhsPos,
		ComparisonOperator	cmp,
		int64_t	rhsPos )

protected

Return "true" if, based on the current state of the constraint system, "lhs cmp rhs" was proven to hold.

It returns "false" if "!(lhs cmp rhs)" can be proven. Otherwise, it returns failure if neither the relation nor its inverse relation could be proven.

This function does not analyze any IR and does not populate any additional constraints.

Definition at line 736 of file ValueBoundsOpInterface.cpp.

References comparePos(), EQ, GE, GT, LE, LT, and strongComparePos().

Referenced by strongComparePos().

Member Data Documentation

◆ addConservativeSemiAffineBounds

bool mlir::ValueBoundsConstraintSet::addConservativeSemiAffineBounds = false

protected

Should conservative bounds be added for semi-affine expressions.

Definition at line 435 of file ValueBoundsOpInterface.h.

Referenced by addBound(), and ValueBoundsConstraintSet().

◆ builder

Builder mlir::ValueBoundsConstraintSet::builder

protected

Builder for constructing affine expressions.

Definition at line 429 of file ValueBoundsOpInterface.h.

Referenced by getExpr(), getExpr(), getExpr(), getPosExpr(), and ValueBoundsConstraintSet().

◆ cstr

FlatLinearConstraints mlir::ValueBoundsConstraintSet::cstr

protected

Constraint system of equalities and inequalities.

Definition at line 426 of file ValueBoundsOpInterface.h.

Referenced by addBound(), compare(), comparePos(), computeBound(), computeConstantBound(), computeDependentBound(), computeIndependentBound(), dump(), getPosExpr(), insert(), insert(), projectOut(), and strongCompare().

◆ ID

char ValueBoundsConstraintSet::ID = 0

static

Definition at line 113 of file ValueBoundsOpInterface.h.

◆ kIndexValue

int64_t mlir::ValueBoundsConstraintSet::kIndexValue = -1

staticconstexprprotected

Dimension identifier to indicate a value is index-typed.

This is used for internal data structures/API only.

Definition at line 324 of file ValueBoundsOpInterface.h.

Referenced by computeBound(), mlir::vector::ScalableValueBoundsConstraintSet::computeScalableBound(), dump(), getExpr(), getPos(), insert(), isMapped(), and processWorklist().

◆ positionToValueDim

SmallVector<std::optional<ValueDim> > mlir::ValueBoundsConstraintSet::positionToValueDim

protected

Mapping of columns to values/shape dimensions.

Definition at line 418 of file ValueBoundsOpInterface.h.

Referenced by dump(), insert(), insert(), processWorklist(), projectOut(), projectOut(), and projectOutAnonymous().

◆ stopCondition

StopConditionFn mlir::ValueBoundsConstraintSet::stopCondition = nullptr

protected

The current stop condition function.

Definition at line 432 of file ValueBoundsOpInterface.h.

Referenced by compare(), computeBound(), computeConstantBound(), processWorklist(), strongCompare(), and ValueBoundsConstraintSet().

◆ valueDimToPosition

DenseMap<ValueDim, int64_t> mlir::ValueBoundsConstraintSet::valueDimToPosition

protected

Reverse mapping of values/shape dimensions to columns.

Definition at line 420 of file ValueBoundsOpInterface.h.

Referenced by getExpr(), getPos(), insert(), insert(), isMapped(), and projectOut().

◆ worklist

std::queue<int64_t> mlir::ValueBoundsConstraintSet::worklist

protected

Worklist of values/shape dimensions that have not been processed yet.

Definition at line 423 of file ValueBoundsOpInterface.h.

Referenced by computeIndependentBound(), insert(), and processWorklist().

The documentation for this class was generated from the following files:

include/mlir/Interfaces/ValueBoundsOpInterface.h
lib/Interfaces/ValueBoundsOpInterface.cpp

Classes

Public Types

Public Member Functions

Static Public Member Functions

Static Public Attributes

Protected Types

Protected Member Functions

Protected Attributes

Static Protected Attributes

Detailed Description

Member Typedef Documentation

◆ StopConditionFn

◆ ValueDim

Member Enumeration Documentation

◆ ComparisonOperator

Constructor & Destructor Documentation

◆ ValueBoundsConstraintSet()

Member Function Documentation

◆ addBound()

◆ areEqual()

◆ areEquivalentSlices()

◆ areOverlappingSlices()

◆ bound()

◆ compare()

◆ comparePos()

◆ computeBound()

◆ computeConstantBound()

◆ computeConstantDelta()

◆ computeDependentBound()

◆ computeIndependentBound()

◆ dump()

◆ getExpr() [1/3]

◆ getExpr() [2/3]

◆ getExpr() [3/3]

◆ getPos()

◆ getPosExpr()

◆ insert() [1/4]

◆ insert() [2/4]

◆ insert() [3/4]

◆ insert() [4/4]

◆ isMapped()

◆ populateAndCompare()

◆ populateConstraints() [1/2]

◆ populateConstraints() [2/2]

◆ processWorklist()

◆ projectOut() [1/2]

◆ projectOut() [2/2]

◆ projectOutAnonymous()

◆ strongCompare()

◆ strongComparePos()

Member Data Documentation

◆ addConservativeSemiAffineBounds

◆ builder

◆ cstr

◆ ID

◆ kIndexValue

◆ positionToValueDim

◆ stopCondition

◆ valueDimToPosition

◆ worklist