#include "mlir/Analysis//FlatLinearValueConstraints.h"
#include "mlir/Analysis/Presburger/LinearTransform.h"
#include "mlir/Analysis/Presburger/PresburgerSpace.h"
#include "mlir/Analysis/Presburger/Simplex.h"
#include "mlir/Analysis/Presburger/Utils.h"
#include "mlir/IR/AffineExprVisitor.h"
#include "mlir/IR/Builders.h"
#include "mlir/IR/IntegerSet.h"
#include "mlir/Support/LLVM.h"
#include "llvm/ADT/STLExtras.h"
#include "llvm/ADT/SmallPtrSet.h"
#include "llvm/ADT/SmallVector.h"
#include "llvm/Support/Debug.h"
#include "llvm/Support/raw_ostream.h"
#include <optional>

Macros
#define	DEBUG_TYPE "flat-value-constraints"

Functions
static LogicalResult	getFlattenedAffineExprs (ArrayRef< AffineExpr > exprs, unsigned numDims, unsigned numSymbols, std::vector< SmallVector< int64_t, 8 >> flattenedExprs, FlatLinearConstraints localVarCst, bool addConservativeSemiAffineBounds=false)

static bool	detectAsMod (const FlatLinearConstraints &cst, unsigned pos, unsigned offset, unsigned num, int64_t lbConst, int64_t ubConst, MLIRContext *context, SmallVectorImpl< AffineExpr > &memo)

static bool	detectAsFloorDiv (const FlatLinearConstraints &cst, unsigned pos, MLIRContext *context, SmallVectorImpl< AffineExpr > &exprs)
	Check if the pos^th variable can be expressed as a floordiv of an affine function of other variables (where the divisor is a positive constant) given the initial set of expressions in `exprs`. More...

static bool	detectAsExpr (const FlatLinearConstraints &cst, unsigned pos, unsigned idx, MLIRContext *context, SmallVectorImpl< AffineExpr > &exprs)
	Express the pos^th identifier of `cst` as an affine expression in terms of other identifiers, if they are available in `exprs`, using the equality at position `idx` in `cs`t. More...

static void	computeUnknownVars (const FlatLinearConstraints &cst, MLIRContext *context, unsigned offset, unsigned num, SmallVectorImpl< AffineExpr > &memo)
	Compute a representation of `num` identifiers starting at `offset` in `cst` as affine expressions involving other known identifiers. More...

static std::optional< AffineExpr >	getAsExpr (const FlatLinearConstraints &cst, unsigned pos, MLIRContext *context, ArrayRef< AffineExpr > exprs, unsigned idx, bool isEquality)
	Given an equality or inequality (`isEquality` used to disambiguate) of `cst` at `idx`, traverse and sum up `AffineExpr`s of all known ids other than the `pos`th. More...

static bool	areVarsAligned (const FlatLinearValueConstraints &a, const FlatLinearValueConstraints &b)
	Checks if two constraint systems are in the same space, i.e., if they are associated with the same set of variables, appearing in the same order. More...

static bool LLVM_ATTRIBUTE_UNUSED	areVarsUnique (const FlatLinearValueConstraints &cst, unsigned start, unsigned end)
	Checks if the SSA values associated with `cst`'s variables in range [start, end) are unique. More...

static bool LLVM_ATTRIBUTE_UNUSED	areVarsUnique (const FlatLinearValueConstraints &cst)
	Checks if the SSA values associated with `cst`'s variables are unique. More...

static bool LLVM_ATTRIBUTE_UNUSED	areVarsUnique (const FlatLinearValueConstraints &cst, VarKind kind)
	Checks if the SSA values associated with `cst`'s variables of kind `kind` are unique. More...

static void	mergeAndAlignVars (unsigned offset, FlatLinearValueConstraints a, FlatLinearValueConstraints b)
	Merge and align the variables of A and B starting at 'offset', so that both constraint systems get the union of the contained variables that is dimension-wise and symbol-wise unique; both constraint systems are updated so that they have the union of all variables, with A's original variables appearing first followed by any of B's variables that didn't appear in A. More...

Macro Definition Documentation

◆ DEBUG_TYPE

#define DEBUG_TYPE "flat-value-constraints"

Definition at line 26 of file FlatLinearValueConstraints.cpp.

Function Documentation

◆ areVarsAligned()

static bool areVarsAligned	(	const FlatLinearValueConstraints &	a,
		const FlatLinearValueConstraints &	b
	)

static

Checks if two constraint systems are in the same space, i.e., if they are associated with the same set of variables, appearing in the same order.

Definition at line 1227 of file FlatLinearValueConstraints.cpp.

References mlir::FlatLinearValueConstraints::getMaybeValues(), mlir::presburger::IntegerRelation::getNumDomainVars(), mlir::presburger::IntegerRelation::getNumRangeVars(), and mlir::presburger::IntegerRelation::getNumSymbolVars().

Referenced by mlir::FlatLinearValueConstraints::areVarsAlignedWithOther(), mergeAndAlignVars(), and mlir::FlatLinearValueConstraints::unionBoundingBox().

◆ areVarsUnique() [1/3]

static bool LLVM_ATTRIBUTE_UNUSED areVarsUnique ( const FlatLinearValueConstraints & cst )

static

Checks if the SSA values associated with cst's variables are unique.

Definition at line 1272 of file FlatLinearValueConstraints.cpp.

References areVarsUnique(), and mlir::presburger::IntegerRelation::getNumDimAndSymbolVars().

◆ areVarsUnique() [2/3]

static bool LLVM_ATTRIBUTE_UNUSED areVarsUnique	(	const FlatLinearValueConstraints &	cst,
		unsigned	start,
		unsigned	end
	)

static

Checks if the SSA values associated with cst's variables in range [start, end) are unique.

Definition at line 1248 of file FlatLinearValueConstraints.cpp.

References mlir::FlatLinearValueConstraints::getMaybeValues(), and mlir::presburger::IntegerRelation::getNumDimAndSymbolVars().

Referenced by areVarsUnique().

◆ areVarsUnique() [3/3]

static bool LLVM_ATTRIBUTE_UNUSED areVarsUnique	(	const FlatLinearValueConstraints &	cst,
		VarKind	kind
	)

static

Checks if the SSA values associated with cst's variables of kind kind are unique.

Definition at line 1279 of file FlatLinearValueConstraints.cpp.

References areVarsUnique(), mlir::presburger::IntegerRelation::getNumDimAndSymbolVars(), mlir::presburger::IntegerRelation::getNumDimVars(), and kind.

◆ computeUnknownVars()

static void computeUnknownVars	(	const FlatLinearConstraints &	cst,
		MLIRContext *	context,
		unsigned	offset,
		unsigned	num,
		SmallVectorImpl< AffineExpr > &	memo
	)

static

Compute a representation of num identifiers starting at offset in cst as affine expressions involving other known identifiers.

Each identifier's expression (in terms of known identifiers) is populated into memo.

Definition at line 630 of file FlatLinearValueConstraints.cpp.

References mlir::changed, detectAsExpr(), detectAsFloorDiv(), detectAsMod(), mlir::presburger::IntegerRelation::findConstraintWithNonZeroAt(), mlir::getAffineConstantExpr(), mlir::getAffineDimExpr(), mlir::getAffineSymbolExpr(), mlir::presburger::IntegerRelation::getConstantBound64(), mlir::presburger::IntegerRelation::getNumDimAndSymbolVars(), mlir::presburger::IntegerRelation::getNumDimVars(), mlir::presburger::IntegerRelation::getNumVars(), mlir::presburger::LB, and mlir::presburger::UB.

Referenced by mlir::FlatLinearConstraints::getSliceBounds().

◆ detectAsExpr()

static bool detectAsExpr	(	const FlatLinearConstraints &	cst,
		unsigned	pos,
		unsigned	idx,
		MLIRContext *	context,
		SmallVectorImpl< AffineExpr > &	exprs
	)

static

Express the pos^th identifier of cst as an affine expression in terms of other identifiers, if they are available in exprs, using the equality at position idx in cst.

Populates exprs with such an expression if possible, and return true. Returns false otherwise.

Definition at line 588 of file FlatLinearValueConstraints.cpp.

References mlir::presburger::IntegerRelation::atEq64(), mlir::getAffineConstantExpr(), and mlir::presburger::IntegerRelation::getNumVars().

Referenced by computeUnknownVars(), and mlir::FlatLinearConstraints::getConstantBoundOnDimSize().

◆ detectAsFloorDiv()

static bool detectAsFloorDiv	(	const FlatLinearConstraints &	cst,
		unsigned	pos,
		MLIRContext *	context,
		SmallVectorImpl< AffineExpr > &	exprs
	)

static

Check if the pos^th variable can be expressed as a floordiv of an affine function of other variables (where the divisor is a positive constant) given the initial set of expressions in exprs.

If it can be, the corresponding position in exprs is set as the detected affine expr. For eg: 4q <= i + j <= 4q + 3 <=> q = (i + j) floordiv 4. An equality can also yield a floordiv: eg. 4q = i + j <=> q = (i + j) floordiv 4. 32q + 28 <= i <= 32q + 31 => q = i floordiv 32.

Definition at line 418 of file FlatLinearValueConstraints.cpp.

References mlir::presburger::computeSingleVarRepr(), mlir::presburger::Equality, mlir::getAffineConstantExpr(), mlir::presburger::IntegerRelation::getNumCols(), mlir::presburger::IntegerRelation::getNumVars(), and mlir::presburger::None.

Referenced by mlir::FlatLinearConstraints::computeLocalVars(), and computeUnknownVars().

◆ detectAsMod()

static bool detectAsMod	(	const FlatLinearConstraints &	cst,
		unsigned	pos,
		unsigned	offset,
		unsigned	num,
		int64_t	lbConst,
		int64_t	ubConst,
		MLIRContext *	context,
		SmallVectorImpl< AffineExpr > &	memo
	)

static

Definition at line 302 of file FlatLinearValueConstraints.cpp.

References mlir::presburger::IntegerRelation::atEq64(), mlir::getAffineConstantExpr(), mlir::presburger::IntegerRelation::getNumCols(), mlir::presburger::IntegerRelation::getNumEqualities(), and mlir::presburger::IntegerRelation::getNumVars().

Referenced by computeUnknownVars().

◆ getAsExpr()

static std::optional<AffineExpr> getAsExpr	(	const FlatLinearConstraints &	cst,
		unsigned	pos,
		MLIRContext *	context,
		ArrayRef< AffineExpr >	exprs,
		unsigned	idx,
		bool	isEquality
	)

static

Given an equality or inequality (isEquality used to disambiguate) of cst at idx, traverse and sum up AffineExprs of all known ids other than the posth.

Known AffineExprs are given in exprs (unknowns are null). If the equality/inequality contains any unknown id, return None. Otherwise return sum as AffineExpr.

Definition at line 914 of file FlatLinearValueConstraints.cpp.

References mlir::getAffineConstantExpr(), mlir::presburger::IntegerRelation::getEquality64(), mlir::presburger::IntegerRelation::getInequality64(), and mlir::presburger::IntegerRelation::getNumVars().

Referenced by mlir::FlatLinearConstraints::getConstantBoundOnDimSize().

◆ getFlattenedAffineExprs()

static LogicalResult getFlattenedAffineExprs	(	ArrayRef< AffineExpr >	exprs,
		unsigned	numDims,
		unsigned	numSymbols,
		std::vector< SmallVector< int64_t, 8 >> *	flattenedExprs,
		FlatLinearConstraints *	localVarCst,
		bool	addConservativeSemiAffineBounds = `false`
	)

static

Definition at line 136 of file FlatLinearValueConstraints.cpp.

References mlir::presburger::IntegerRelation::clearAndCopyFrom().

Referenced by mlir::getFlattenedAffineExprs().

◆ mergeAndAlignVars()

static void mergeAndAlignVars	(	unsigned	offset,
		FlatLinearValueConstraints *	a,
		FlatLinearValueConstraints *	b
	)

static

Merge and align the variables of A and B starting at 'offset', so that both constraint systems get the union of the contained variables that is dimension-wise and symbol-wise unique; both constraint systems are updated so that they have the union of all variables, with A's original variables appearing first followed by any of B's variables that didn't appear in A.

Local variables in B that have the same division representation as local variables in A are merged into one. We allow A and B to have non-unique values for their variables; in such cases, they are still aligned with the variables appearing first aligned with those appearing first in the other system from left to right.

Definition at line 1301 of file FlatLinearValueConstraints.cpp.

References mlir::FlatLinearValueConstraints::appendDimVar(), areVarsAligned(), mlir::FlatLinearValueConstraints::findVar(), mlir::FlatLinearValueConstraints::getMaybeValues(), mlir::presburger::IntegerRelation::getNumDimVars(), mlir::FlatLinearValueConstraints::getValue(), mlir::FlatLinearValueConstraints::getValues(), mlir::FlatLinearValueConstraints::insertDimVar(), mlir::presburger::IntegerRelation::mergeLocalVars(), mlir::FlatLinearValueConstraints::mergeSymbolVars(), and mlir::presburger::IntegerRelation::swapVar().

Referenced by mlir::FlatLinearValueConstraints::mergeAndAlignVarsWithOther(), and mlir::FlatLinearValueConstraints::unionBoundingBox().

Macros

Functions

Macro Definition Documentation

◆ DEBUG_TYPE

Function Documentation

◆ areVarsAligned()

◆ areVarsUnique() [1/3]

◆ areVarsUnique() [2/3]

◆ areVarsUnique() [3/3]

◆ computeUnknownVars()

◆ detectAsExpr()

◆ detectAsFloorDiv()

◆ detectAsMod()

◆ getAsExpr()

◆ getFlattenedAffineExprs()

◆ mergeAndAlignVars()