#include "mlir/Analysis/Presburger/IntegerRelation.h"
#include "mlir/Analysis/Presburger/Fraction.h"
#include "mlir/Analysis/Presburger/LinearTransform.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 "llvm/ADT/DenseMap.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>

Classes
class	SmallDenseMap

Macros
#define	DEBUG_TYPE "presburger"
#define	DEBUG_TYPE "fm"
#define	DEBUG_TYPE "presburger"

Functions
static bool	rangeIsZero (ArrayRef< DynamicAPInt > 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.
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).
static DynamicAPInt	valueAt (ArrayRef< DynamicAPInt > expr, ArrayRef< DynamicAPInt > point)
	Helper to evaluate an affine expression at a point.
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.

Macro Definition Documentation

◆ DEBUG_TYPE [1/3]

#define DEBUG_TYPE "presburger"

Definition at line 37 of file IntegerRelation.cpp.

◆ DEBUG_TYPE [2/3]

#define DEBUG_TYPE "fm"

Definition at line 37 of file IntegerRelation.cpp.

◆ DEBUG_TYPE [3/3]

#define DEBUG_TYPE "presburger"

Definition at line 37 of file IntegerRelation.cpp.

Function Documentation

◆ eliminateFromConstraint()

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 615 of file IntegerRelation.cpp.

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

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

◆ getBestVarToEliminate()

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 652 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()

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

static

Definition at line 2160 of file IntegerRelation.cpp.

References mlir::presburger::IntegerRelation::addEquality(), mlir::presburger::IntegerRelation::addInequality(), b, 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()

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