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 = std::function< bool(Value, std::optional< int64_t >, ValueBoundsConstraintSet &cstr)>
	The stop condition when traversing the backward slice of a shaped value/ index-type value. More...

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. More...

bool	populateAndCompare (const Variable &lhs, ComparisonOperator cmp, const Variable &rhs)
	Populate constraints for lhs/rhs (until the stop condition is met). More...

BoundBuilder	bound (Value value)
	Add a bound for the given index-typed value or shaped value. More...

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. More...

AffineExpr	getExpr (OpFoldResult ofr)
	Return an expression that represents a constant or index-typed SSA value. More...

AffineExpr	getExpr (int64_t constant)
	Return an expression that represents a constant. More...

void	dump () const
	Debugging only: Dump the constraint set and the column-to-value/dim mapping to llvm::errs. More...

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. More...

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`. More...

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`. More...

static FailureOr< int64_t >	computeConstantBound (presburger::BoundType type, const Variable &var, StopConditionFn stopCondition=nullptr, bool closedUB=false)
	Compute a constant bound for the given variable. More...

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. More...

static bool	compare (const Variable &lhs, ComparisonOperator cmp, const Variable &rhs)
	Return "true" if "lhs cmp rhs" was proven to hold. More...

static FailureOr< bool >	areEqual (const Variable &var1, const Variable &var2)
	Compute whether the given variables are equal. More...

static FailureOr< bool >	areOverlappingSlices (MLIRContext *ctx, HyperrectangularSlice slice1, HyperrectangularSlice slice2)
	Return "true" if the given slices are guaranteed to be overlapping. More...

static FailureOr< bool >	areEquivalentSlices (MLIRContext *ctx, HyperrectangularSlice slice1, HyperrectangularSlice slice2)
	Return "true" if the given slices are guaranteed to be equivalent. More...

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. More...

Protected Member Functions
	ValueBoundsConstraintSet (MLIRContext *ctx, StopConditionFn stopCondition)

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. More...

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. More...

void	processWorklist ()
	Iteratively process all elements on the worklist until an index-typed value or shaped value meets `stopCondition`. More...

void	addBound (presburger::BoundType type, int64_t pos, AffineExpr expr)
	Bound the given column in the underlying constraint set by the given expression. More...

int64_t	getPos (Value value, std::optional< int64_t > dim=std::nullopt) const
	Return the column position of the given value/dimension. More...

AffineExpr	getPosExpr (int64_t pos)
	Return an affine expression that represents column `pos` in the constraint set. More...

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). More...

int64_t	insert (Value value, std::optional< int64_t > dim, bool isSymbol=true, bool addToWorklist=true)
	Insert a value/dimension into the constraint set. More...

int64_t	insert (bool isSymbol=true)
	Insert an anonymous column into the constraint set. More...

int64_t	insert (AffineMap map, ValueDimList operands, bool isSymbol=true)
	Insert the given affine map and its bound operands as a new column in the constraint system. More...

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

void	projectOut (int64_t pos)
	Project out the given column in the constraint set. More...

void	projectOut (function_ref< bool(ValueDim)> condition)
	Project out all columns for which the condition holds. More...

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

Protected Attributes
SmallVector< std::optional< ValueDim > >	positionToValueDim
	Mapping of columns to values/shape dimensions. More...

DenseMap< ValueDim, int64_t >	valueDimToPosition
	Reverse mapping of values/shape dimensions to columns. More...

std::queue< int64_t >	worklist
	Worklist of values/shape dimensions that have not been processed yet. More...

FlatLinearConstraints	cstr
	Constraint system of equalities and inequalities. More...

Builder	builder
	Builder for constructing affine expressions. More...

StopConditionFn	stopCondition = nullptr
	The current stop condition function. More...

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

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 = std::function<bool( Value, std::optional<int64_t> , ValueBoundsConstraintSet &cstr)>

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 155 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 314 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 232 of file ValueBoundsOpInterface.h.

Constructor & Destructor Documentation

◆ ValueBoundsConstraintSet()

ValueBoundsConstraintSet::ValueBoundsConstraintSet	(	MLIRContext *	ctx,
		StopConditionFn	stopCondition
	)

protected

Definition at line 153 of file ValueBoundsOpInterface.cpp.

References stopCondition.

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 175 of file ValueBoundsOpInterface.cpp.

References mlir::FlatLinearConstraints::addBound(), cstr, mlir::failed(), mlir::AffineMap::get(), mlir::presburger::IntegerRelation::getNumDimVars(), and mlir::presburger::IntegerRelation::getNumSymbolVars().

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 757 of file ValueBoundsOpInterface.cpp.

References compare(), and mlir::failure().

Referenced by areEquivalentSlices(), and mlir::vector::isDisjointTransferIndices().

◆ areEquivalentSlices()

FailureOr< bool > ValueBoundsConstraintSet::areEquivalentSlices	(	MLIRContext *	ctx,
		HyperrectangularSlice	slice1,
		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 833 of file ValueBoundsOpInterface.cpp.

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

◆ areOverlappingSlices()

FailureOr< bool > ValueBoundsConstraintSet::areOverlappingSlices	(	MLIRContext *	ctx,
		HyperrectangularSlice	slice1,
		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 768 of file ValueBoundsOpInterface.cpp.

References computeConstantBound(), mlir::presburger::EQ, mlir::failed(), mlir::failure(), mlir::foldAttributesIntoMap(), mlir::AffineMap::get(), mlir::Builder::getAffineSymbolExpr(), mlir::HyperrectangularSlice::getMixedOffsets(), mlir::HyperrectangularSlice::getMixedSizes(), mlir::HyperrectangularSlice::getMixedStrides(), and mlir::succeeded().

◆ 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 287 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 738 of file ValueBoundsOpInterface.cpp.

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

Referenced by areEqual().

◆ 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 683 of file ValueBoundsOpInterface.cpp.

References mlir::presburger::IntegerRelation::addInequality(), cstr, EQ, GE, mlir::presburger::IntegerRelation::getNumCols(), mlir::presburger::IntegerRelation::getNumInequalities(), GT, mlir::presburger::IntegerRelation::isEmpty(), LE, LT, and mlir::presburger::IntegerRelation::removeInequality().

Referenced by populateAndCompare().

◆ 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 454 of file ValueBoundsOpInterface.cpp.

References bound(), cstr, mlir::failure(), mlir::AffineMap::get(), mlir::Builder::getAffineConstantExpr(), mlir::Builder::getAffineDimExpr(), mlir::Builder::getAffineSymbolExpr(), mlir::ValueBoundsConstraintSet::Variable::getContext(), mlir::presburger::IntegerRelation::getNumDimAndSymbolVars(), mlir::presburger::IntegerRelation::getNumDimVars(), mlir::FlatLinearConstraints::getSliceBounds(), mlir::Value::getType(), mlir::Type::isIndex(), kIndexValue, mlir::presburger::IntegerRelation::projectOut(), stopCondition, and mlir::success().

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

◆ computeConstantBound()

FailureOr< int64_t > ValueBoundsConstraintSet::computeConstantBound	(	presburger::BoundType	type,
		const Variable &	var,
		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 621 of file ValueBoundsOpInterface.cpp.

References bound(), cstr, mlir::failure(), mlir::presburger::IntegerRelation::getConstantBound64(), mlir::ValueBoundsConstraintSet::Variable::getContext(), and stopCondition.

Referenced by areOverlappingSlices(), computeConstantDelta(), computePaddedShape(), and mlir::affine::fullyComposeAndComputeConstantDelta().

◆ 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 668 of file ValueBoundsOpInterface.cpp.

References assertValidValueDim(), computeConstantBound(), mlir::presburger::EQ, mlir::AffineMap::get(), mlir::Builder::getAffineDimExpr(), 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 575 of file ValueBoundsOpInterface.cpp.

References computeBound(), and cstr.

◆ 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 586 of file ValueBoundsOpInterface.cpp.

References 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 874 of file ValueBoundsOpInterface.cpp.

References cstr, mlir::presburger::IntegerRelation::dump(), mlir::detail::enumerate(), mlir::Operation::getName(), getOwnerOfValue(), kIndexValue, and positionToValueDim.

◆ getExpr() [1/3]

AffineExpr ValueBoundsConstraintSet::getExpr ( int64_t constant )

Return an expression that represents a constant.

Definition at line 247 of file ValueBoundsOpInterface.cpp.

References builder, and mlir::Builder::getAffineConstantExpr().

◆ 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 239 of file ValueBoundsOpInterface.cpp.

References builder, mlir::Builder::getAffineConstantExpr(), 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 190 of file ValueBoundsOpInterface.cpp.

References assertValidValueDim(), bound(), builder, mlir::Builder::getAffineConstantExpr(), 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 321 of file ValueBoundsOpInterface.cpp.

References assertValidValueDim(), 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 339 of file ValueBoundsOpInterface.cpp.

References builder, cstr, mlir::Builder::getAffineDimExpr(), mlir::Builder::getAffineSymbolExpr(), mlir::presburger::IntegerRelation::getNumDimAndSymbolVars(), and mlir::presburger::IntegerRelation::getNumDimVars().

Referenced by getExpr().

◆ insert() [1/4]

int64_t ValueBoundsConstraintSet::insert	(	AffineMap	map,
		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 295 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 282 of file ValueBoundsOpInterface.cpp.

References mlir::presburger::IntegerRelation::appendVar(), cstr, positionToValueDim, and valueDimToPosition.

◆ insert() [3/4]

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

protected

Definition at line 317 of file ValueBoundsOpInterface.cpp.

References insert().

◆ 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 251 of file ValueBoundsOpInterface.cpp.

References mlir::presburger::IntegerRelation::appendVar(), assertValidValueDim(), cstr, 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 346 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 730 of file ValueBoundsOpInterface.cpp.

References comparePos(), and populateConstraints().

◆ 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 658 of file ValueBoundsOpInterface.cpp.

References insert(), and processWorklist().