int_solver.h File Reference

integer constraints data structures and solvers More...

#include <tvm/ir/expr.h>
#include <tvm/tir/expr.h>
#include <tvm/tir/op.h>
#include <unordered_map>
#include <utility>
#include <vector>
#include "analyzer.h"

Include dependency graph for int_solver.h:

Go to the source code of this file.

Classes
class	tvm::arith::IntGroupBoundsNode
	Represent integer grouped bounds which are classified into lower bounds (inclusive), upper bounds (inclusive) and equalities. It also contains coefficient as a multiplier for the bounds, i.e., coef * var >= lower coef * var == equal coef * var <= upper. More...
class	tvm::arith::IntGroupBounds
	Managed reference to IntGroupBoundsNode. More...
class	tvm::arith::IntConstraintsNode
	Represent integer constrains including (integer) variables, their ranges and the relations between them (either equations or inequalities). More...
class	tvm::arith::IntConstraints
	Managed reference to IntConstraintsNode. More...
class	tvm::arith::IntConstraintsTransformNode
	We can have different set of variables to represent the same constraints. For example, the following two systems are equivalent, {a + b = 0 | a >= 0, b >= 0} and {m - n = 0 | m >= 0, n <= 0} This data structure represents the transformation between two equivalent linear systems. In the above example, src : {a + b = 0 | a >= 0, b >= 0} dst : {m - n = 0 | m >= 0, n <= 0} src_to_dst : {a -> m, b -> -n} dst_to_src : {m -> a, n -> -b}. More...
class	tvm::arith::IntConstraintsTransform
	Managed reference to IntConstraintsTransformNode. More...

Namespaces
	tvm
	runtime implementation for LibTorch/TorchScript.
	tvm::arith
	namespace of arithmetic analysis.

Typedefs
typedef std::pair< Map< Var, IntGroupBounds >, Array< PrimExpr > >	tvm::arith::PartialSolvedInequalities

Functions
void	tvm::arith::SmithNormalFormDiag (std::vector< std::vector< int64_t >> *S, std::vector< std::vector< int64_t >> *V, std::vector< PrimExpr > *x, std::vector< PrimExpr > *y)
	Obtain Smith Normal Form of linear equation A x = y. Smith Normal Form of matrix A_{mxn} is S_{mxn} = U_{mxm} A_{mxn} V_{nxn}, in which S_{mxn} is diag(s1, s2, ..., sr, 0, ..., 0) and r is the rank of A. NOTE: Although in standard Smith Normal Form the diagonal elements satisfy s_i | s_{i+1} (| means divides), the implement here does not guarantee it. TODO(yzhliu): From sergei-grechanik: computing the proper Smith normal form may improve stability of automatic differentiation (generating the same gradient code for slightly different but equivalent input code U_{mxm} and V_{nxn} are invertible matrices. This function modifies S to be S_{mxn}, V to be V_{nxn}, y to be U_{mxm} y_{mx1} and x to be V^{-1} x. More...
IntConstraintsTransform	tvm::arith::SolveLinearEquations (const IntConstraints &system_to_solve)
	Solve linear equations. More...
PartialSolvedInequalities	tvm::arith::SolveLinearInequalities (const IntConstraints &system_to_solve)
	Solve linear inequalities. More...
Array< PrimExpr >	tvm::arith::AsConditions (const Array< Var > &variables, const Map< Var, IntGroupBounds > &bounds, const Array< PrimExpr > &relations)
	Combine the information into an array of (in)equalities. More...
IntConstraints	tvm::arith::SolveInequalitiesToRange (const IntConstraints &system_to_solve)
	Solve linear inequalities and infer the range of each variable. More...
IntConstraintsTransform	tvm::arith::SolveInequalitiesDeskewRange (const IntConstraints &system_to_solve)
	Solve linear inequalities and deskew the ranges towards zero. More...

Variables
constexpr int	tvm::arith::kSimplifyRewriteCanonicalRewrite = 3

Detailed Description

integer constraints data structures and solvers