MLIR  16.0.0git
Macros | Enumerations | Functions
IntegerRelation.cpp File Reference
#include "mlir/Analysis/Presburger/IntegerRelation.h"
#include "mlir/Analysis/Presburger/LinearTransform.h"
#include "mlir/Analysis/Presburger/PWMAFunction.h"
#include "mlir/Analysis/Presburger/PresburgerRelation.h"
#include "mlir/Analysis/Presburger/Simplex.h"
#include "mlir/Analysis/Presburger/Utils.h"
#include "llvm/ADT/DenseMap.h"
#include "llvm/ADT/DenseSet.h"
#include "llvm/Support/Debug.h"
#include <numeric>
+ Include dependency graph for IntegerRelation.cpp:

Go to the source code of this file.

Macros

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

Enumerations

enum  BoundCmpResult
 

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

◆ DEBUG_TYPE [2/3]

#define DEBUG_TYPE   "fm"

Definition at line 1891 of file IntegerRelation.cpp.

◆ DEBUG_TYPE [3/3]

#define DEBUG_TYPE   "presburger"

Definition at line 1891 of file IntegerRelation.cpp.

Enumeration Type Documentation

◆ BoundCmpResult

Definition at line 1930 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 525 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::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 1334 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 562 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

◆ getIndependentConstraints()

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

◆ rangeIsZero()

static bool rangeIsZero ( ArrayRef< MPInt range)
static

Definition at line 126 of file IntegerRelation.cpp.

Referenced by removeConstraintsInvolvingVarRange().

◆ removeConstraintsInvolvingVarRange()

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

◆ valueAt()

static MPInt valueAt ( ArrayRef< MPInt expr,
ArrayRef< MPInt point 
)
static

Helper to evaluate an affine expression at a point.

The expression is a list of coefficients for the dimensions followed by the constant term.

Definition at line 872 of file IntegerRelation.cpp.

References value.

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