#include "mlir/Analysis/Presburger/IntegerRelation.h"
#include "mlir/Analysis/Presburger/Fraction.h"
#include "mlir/Analysis/Presburger/LinearTransform.h"
#include "mlir/Analysis/Presburger/MPInt.h"
#include "mlir/Analysis/Presburger/PWMAFunction.h"
#include "mlir/Analysis/Presburger/PresburgerRelation.h"
#include "mlir/Analysis/Presburger/PresburgerSpace.h"
#include "mlir/Analysis/Presburger/Simplex.h"
#include "mlir/Analysis/Presburger/Utils.h"
#include "mlir/Support/LLVM.h"
#include "mlir/Support/LogicalResult.h"
#include "llvm/ADT/DenseMap.h"
#include "llvm/ADT/DenseSet.h"
#include "llvm/ADT/STLExtras.h"
#include "llvm/ADT/Sequence.h"
#include "llvm/ADT/SmallBitVector.h"
#include "llvm/Support/Debug.h"
#include "llvm/Support/raw_ostream.h"
#include <algorithm>
#include <cassert>
#include <functional>
#include <memory>
#include <optional>
#include <utility>
#include <vector>

Macros
#define	DEBUG_TYPE "presburger"

#define	DEBUG_TYPE "fm"

#define	DEBUG_TYPE "presburger"

Functions
static bool	rangeIsZero (ArrayRef< MPInt > range)

static void	removeConstraintsInvolvingVarRange (IntegerRelation &poly, unsigned begin, unsigned count)

static void	eliminateFromConstraint (IntegerRelation *constraints, unsigned rowIdx, unsigned pivotRow, unsigned pivotCol, unsigned elimColStart, bool isEq)
	Eliminate variable from constraint at `rowIdx` based on coefficient at pivotRow, pivotCol. More...

static unsigned	getBestVarToEliminate (const IntegerRelation &cst, unsigned start, unsigned end)
	Returns the position of the variable that has the minimum <number of lower bounds> times <number of upper bounds> from the specified range of variables [start, end). More...

static MPInt	valueAt (ArrayRef< MPInt > expr, ArrayRef< MPInt > point)
	Helper to evaluate an affine expression at a point. More...

static int	findEqualityToConstant (const IntegerRelation &cst, unsigned pos, bool symbolic=false)
	Finds an equality that equates the specified variable to a constant. More...

static void	getCommonConstraints (const IntegerRelation &a, const IntegerRelation &b, IntegerRelation &c)

static void	getIndependentConstraints (const IntegerRelation &cst, unsigned pos, unsigned num, SmallVectorImpl< unsigned > &nbIneqIndices, SmallVectorImpl< unsigned > &nbEqIndices)
	Find positions of inequalities and equalities that do not have a coefficient for [pos, pos + num) variables. More...

Macro Definition Documentation

◆ DEBUG_TYPE [1/3]

#define DEBUG_TYPE "presburger"

Definition at line 2086 of file IntegerRelation.cpp.

◆ DEBUG_TYPE [2/3]

#define DEBUG_TYPE "fm"

Definition at line 2086 of file IntegerRelation.cpp.

◆ DEBUG_TYPE [3/3]

#define DEBUG_TYPE "presburger"

Definition at line 2086 of file IntegerRelation.cpp.

Function Documentation

◆ eliminateFromConstraint()

static void eliminateFromConstraint	(	IntegerRelation *	constraints,
		unsigned	rowIdx,
		unsigned	pivotRow,
		unsigned	pivotCol,
		unsigned	elimColStart,
		bool	isEq
	)

static

Eliminate variable from constraint at rowIdx based on coefficient at pivotRow, pivotCol.

Columns in range [elimColStart, pivotCol) will not be updated as they have already been eliminated.

Definition at line 622 of file IntegerRelation.cpp.

References mlir::presburger::abs(), mlir::presburger::IntegerRelation::atEq(), mlir::presburger::IntegerRelation::atIneq(), mlir::presburger::IntegerRelation::getNumCols(), and mlir::presburger::lcm().

Referenced by mlir::presburger::IntegerRelation::gaussianEliminate(), mlir::presburger::IntegerRelation::gaussianEliminateVars(), and mlir::presburger::IntegerRelation::removeRedundantLocalVars().

◆ findEqualityToConstant()

static int findEqualityToConstant	(	const IntegerRelation &	cst,
		unsigned	pos,
		bool	symbolic = `false`
	)

static

Finds an equality that equates the specified variable to a constant.

Returns the position of the equality row. If 'symbolic' is set to true, symbols are also treated like a constant, i.e., an affine function of the symbols is also treated like a constant. Returns -1 if such an equality could not be found.

Definition at line 1529 of file IntegerRelation.cpp.

References mlir::presburger::IntegerRelation::atEq(), mlir::presburger::IntegerRelation::getNumDimVars(), mlir::presburger::IntegerRelation::getNumEqualities(), and mlir::presburger::IntegerRelation::getNumVars().

Referenced by mlir::presburger::IntegerRelation::computeConstantLowerOrUpperBound(), mlir::presburger::IntegerRelation::constantFoldVar(), and mlir::presburger::IntegerRelation::getConstantBoundOnDimSize().

◆ getBestVarToEliminate()

static unsigned getBestVarToEliminate	(	const IntegerRelation &	cst,
		unsigned	start,
		unsigned	end
	)

static

Returns the position of the variable that has the minimum <number of lower bounds> times <number of upper bounds> from the specified range of variables [start, end).

It is often best to eliminate in the increasing order of these counts when doing Fourier-Motzkin elimination since FM adds that many new constraints.

Definition at line 659 of file IntegerRelation.cpp.

References mlir::presburger::IntegerRelation::atIneq(), mlir::presburger::IntegerRelation::getNumInequalities(), mlir::presburger::IntegerRelation::getNumVars(), and min().

Referenced by mlir::presburger::IntegerRelation::isEmpty(), and mlir::presburger::IntegerRelation::projectOut().

◆ getCommonConstraints()

static void getCommonConstraints	(	const IntegerRelation &	a,
		const IntegerRelation &	b,
		IntegerRelation &	c
	)

static

Definition at line 2147 of file IntegerRelation.cpp.

References mlir::presburger::IntegerRelation::addEquality(), mlir::presburger::IntegerRelation::addInequality(), mlir::presburger::IntegerRelation::getEquality(), mlir::presburger::IntegerRelation::getInequality(), mlir::presburger::IntegerRelation::getNumEqualities(), mlir::presburger::IntegerRelation::getNumInequalities(), and mlir::presburger::IntegerRelation::getSpace().

Referenced by mlir::presburger::IntegerRelation::unionBoundingBox().

◆ getIndependentConstraints()

static void getIndependentConstraints	(	const IntegerRelation &	cst,
		unsigned	pos,
		unsigned	num,
		SmallVectorImpl< unsigned > &	nbIneqIndices,
		SmallVectorImpl< unsigned > &	nbEqIndices
	)