#include "mlir/Dialect/Affine/Analysis/AffineStructures.h"
#include "mlir/Analysis/Presburger/LinearTransform.h"
#include "mlir/Analysis/Presburger/Simplex.h"
#include "mlir/Analysis/Presburger/Utils.h"
#include "mlir/Dialect/Affine/IR/AffineOps.h"
#include "mlir/Dialect/Affine/IR/AffineValueMap.h"
#include "mlir/Dialect/Arithmetic/IR/Arithmetic.h"
#include "mlir/IR/AffineExprVisitor.h"
#include "mlir/IR/IntegerSet.h"
#include "mlir/Support/LLVM.h"
#include "mlir/Support/MathExtras.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 dependency graph for AffineStructures.cpp:

Macros
#define	DEBUG_TYPE "affine-structures"

Functions
static LogicalResult	getFlattenedAffineExprs (ArrayRef< AffineExpr > exprs, unsigned numDims, unsigned numSymbols, std::vector< SmallVector< int64_t, 8 >> flattenedExprs, FlatAffineValueConstraints localVarCst)

static bool	areVarsAligned (const FlatAffineValueConstraints &a, const FlatAffineValueConstraints &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 FlatAffineValueConstraints &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 FlatAffineValueConstraints &cst)
	Checks if the SSA values associated with `cst`'s variables are unique. More...

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

static void	mergeAndAlignVars (unsigned offset, FlatAffineValueConstraints a, FlatAffineValueConstraints 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...

static void	turnSymbolIntoDim (FlatAffineValueConstraints *cst, Value value)

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

static bool	detectAsFloorDiv (const FlatAffineValueConstraints &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 LogicalResult	computeLocalVars (const FlatAffineValueConstraints &cst, SmallVectorImpl< AffineExpr > &memo, MLIRContext *context)
	Compute an explicit representation for local vars. More...

Macro Definition Documentation

◆ DEBUG_TYPE

#define DEBUG_TYPE "affine-structures"

Definition at line 30 of file AffineStructures.cpp.

Function Documentation

◆ areVarsAligned()

static bool areVarsAligned	(	const FlatAffineValueConstraints &	a,
		const FlatAffineValueConstraints &	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 328 of file AffineStructures.cpp.

References mlir::FlatAffineValueConstraints::getMaybeValues(), mlir::presburger::IntegerRelation::getNumDimVars(), mlir::presburger::IntegerRelation::getNumSymbolVars(), and mlir::presburger::IntegerRelation::getNumVars().

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

◆ areVarsUnique() [1/3]

static bool LLVM_ATTRIBUTE_UNUSED areVarsUnique	(	const FlatAffineValueConstraints &	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 345 of file AffineStructures.cpp.

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

Referenced by areVarsUnique(), mergeAndAlignVars(), and mlir::FlatAffineValueConstraints::mergeSymbolVars().

◆ areVarsUnique() [2/3]

static bool LLVM_ATTRIBUTE_UNUSED areVarsUnique ( const FlatAffineValueConstraints & cst )

static

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

Definition at line 367 of file AffineStructures.cpp.

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

◆ areVarsUnique() [3/3]

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

static

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

Definition at line 374 of file AffineStructures.cpp.

◆ computeLocalVars()

static LogicalResult computeLocalVars	(	const FlatAffineValueConstraints &	cst,
		SmallVectorImpl< AffineExpr > &	memo,
		MLIRContext *	context
	)

static

Compute an explicit representation for local vars.

For all systems coming from MLIR integer sets, maps, or expressions where local vars were introduced to model floordivs and mods, this always succeeds.

Definition at line 1442 of file AffineStructures.cpp.

References detectAsFloorDiv(), mlir::getAffineDimExpr(), mlir::getAffineSymbolExpr(), mlir::presburger::IntegerRelation::getNumDimVars(), mlir::presburger::IntegerRelation::getNumLocalVars(), mlir::presburger::IntegerRelation::getNumSymbolVars(), and mlir::success().

Referenced by mlir::FlatAffineValueConstraints::getAsIntegerSet(), and mlir::FlatAffineValueConstraints::getIneqAsAffineValueMap().

◆ detectAsFloorDiv()

static bool detectAsFloorDiv	(	const FlatAffineValueConstraints &	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 854 of file AffineStructures.cpp.

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

Referenced by computeLocalVars(), and mlir::FlatAffineValueConstraints::getSliceBounds().

◆ detectAsMod()

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

static

Definition at line 743 of file AffineStructures.cpp.

References mlir::presburger::IntegerRelation::atEq(), mlir::AffineExpr::dyn_cast(), mlir::floorDiv(), mlir::getAffineConstantExpr(), mlir::presburger::IntegerRelation::getConstantBound(), mlir::presburger::IntegerRelation::getNumCols(), mlir::presburger::IntegerRelation::getNumDimAndSymbolVars(), mlir::presburger::IntegerRelation::getNumDimVars(), mlir::presburger::IntegerRelation::getNumEqualities(), mlir::presburger::IntegerRelation::getNumSymbolVars(), mlir::presburger::IntegerRelation::getNumVars(), and mlir::simplifyAffineExpr().

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

◆ getFlattenedAffineExprs()

static LogicalResult getFlattenedAffineExprs	(	ArrayRef< AffineExpr >	exprs,
		unsigned	numDims,
		unsigned	numSymbols,
		std::vector< SmallVector< int64_t, 8 >> *	flattenedExprs,
		FlatAffineValueConstraints *	localVarCst
	)

static

Definition at line 72 of file AffineStructures.cpp.

References mlir::FlatAffineValueConstraints::clearAndCopyFrom(), mlir::failure(), mlir::FlatAffineValueConstraints::reset(), and mlir::success().

Referenced by mlir::getFlattenedAffineExprs().

◆ mergeAndAlignVars()

static void mergeAndAlignVars	(	unsigned	offset,
		FlatAffineValueConstraints *	a,
		FlatAffineValueConstraints *	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.

Definition at line 393 of file AffineStructures.cpp.