namespace of arithmetic analysis. More...

Classes
class	ConstIntBoundNode
	Constant integer up and lower bound(inclusive). Useful for value bound analysis. More...

class	ConstIntBound
	reference class to ConstIntBoundNode More...

class	ConstIntBoundAnalyzer
	Analyzer to get constant integer bound over expression. More...

class	ModularSetNode
	Range of a linear integer function. Use to do specify the possible index values. More...

class	ModularSet
	reference of ModularSetNode More...

class	ModularSetAnalyzer
	Analyzer to get modular information over expression. More...

class	RewriteSimplifier
	Rewrite-rule based simplifier. More...

class	CanonicalSimplifier
	Canonical-form based simplifier. More...

class	TransitiveComparisonAnalyzer
	Using previously specified knowns, compare the expressions provided. More...

class	ConstraintContext
	Constraint context. More...

class	IntSetAnalyzer
	Integer set analyzer. More...

class	Analyzer
	Analyzer that contains bunch of sub-analyzers. More...

class	IntSetNode
	Base class of all Integer set containers. represent a set of integers in one dimension. More...

class	IntSet
	Managed reference to IntSetNode. More...

class	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	IntGroupBounds
	Managed reference to IntGroupBoundsNode. More...

class	IntConstraintsNode
	Represent integer constrains including (integer) variables, their ranges and the relations between them (either equations or inequalities). More...

class	IntConstraints
	Managed reference to IntConstraintsNode. More...

class	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	IntConstraintsTransform
	Managed reference to IntConstraintsTransformNode. More...

class	IterMapExprNode
	Base class of all iter map expressions. More...

class	IterMapExpr
	Managed reference to IterMapExprNode. More...

class	IterMarkNode
	Mark the source as an iterator in [0, extent). More...

class	IterMark
	Managed reference to IterMarkExprNode. More...

class	IterSplitExprNode
	Split of an iterator. More...

class	IterSplitExpr
	Managed reference to IterSplitExprNode. More...

class	IterSumExprNode
	Fuse multiple iterators by summing them with scaling. More...

class	IterSumExpr
	Managed reference to IterSumExprNode. More...

class	IterMapResultNode
	Result of DetectIterMap. More...

class	IterMapResult
	Managed reference to IterMapResultNode. More...

Typedefs
using	ExprIntSetMap = std::unordered_map< PrimExpr, IntSet, ObjectPtrHash, ObjectPtrEqual >
	Map from Expr to IntSet. More...

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

Enumerations
enum	DivMode { kTruncDiv , kFloorDiv }

enum class	ProofStrength : int { kDefault = 0 , kSymbolicBound = 1 }
	The strength used in top-level condition proves. More...

enum class	CompareResult : int { kInconsistent = 0 , kEQ = 1 , kLT = 2 , kLE = 3 , kGT = 4 , kGE = 5 , kNE = 6 , kUnknown = 7 }
	Structure for representing result of known. More...

enum	SignType { kPositive , kNegative , kZero , kUnknown , kUnknown = 7 }
	Sign type of an integer expression. More...

enum	IterMapLevel { Bijective = 0 , Surjective = 1 , NoCheck = 3 }
	Mapping level for iterators. More...

Functions
constexpr CompareResult	operator& (CompareResult lhs, CompareResult rhs)

constexpr CompareResult	operator\| (CompareResult lhs, CompareResult rhs)

IntSet	DeduceBound (PrimExpr v, PrimExpr cond, const Map< Var, IntSet > &hint_map, const Map< Var, IntSet > &relax_map)
	Deduce the bound of the target variable in a expression, give the domain of each variables. Return undefined IntSet to represent failure. More...

IntSet	DeduceBound (PrimExpr v, PrimExpr cond, const std::unordered_map< const VarNode , IntSet > &hint_map, const std::unordered_map< const VarNode , IntSet > &relax_map)
	Same as DeduceBound with unordered_map signature. More...

Region	DomainTouched (const Stmt &body, const tir::Buffer &buffer, bool consider_loads, bool consider_stores)
	Infer a regular domain that covers all the calls or provides within the given statement. More...

Map< Var, IntSet >	ConvertDomMap (const std::unordered_map< const VarNode *, IntSet > &dom_map)
	Convert std::unordered_map<const VarNode*, IntSet> to Map<Var, IntSet> More...

IntSet	EvalSet (PrimExpr e, const Map< IterVar, IntSet > &dom_map)
	Find an symbolic integer set that contains all possible values of e given the domain of each iteration variables. More...

IntSet	EvalSet (PrimExpr e, const Map< Var, IntSet > &dom_map)
	Find an symbolic integer set that contains all possible values of e given the domain of each variables. More...

IntSet	EvalSet (PrimExpr e, const std::unordered_map< const tir::VarNode *, IntSet > &dom_map)
	Same as EvalSet, but takes unordered_map. More...

IntSet	EvalSet (Range r, const Map< IterVar, IntSet > &dom_map)
	Find an symbolic integer set that contains is union over all the possible conditional values in dom_map. More...

IntSet	EvalSet (IntSet s, const std::unordered_map< const VarNode *, IntSet > &dom_map)
	Find an symbolic integer set that contains is union over all the possible conditional values in dom_map. More...

IntSet	EvalSet (Range r, const std::unordered_map< const VarNode *, IntSet > &dom_map)
	Same as EvalSet, but takes unordered_map. More...

Array< IntSet >	EvalSet (const Array< Range > &region, const Map< Var, IntSet > &dom_map)
	Same as EvalSet, but takes Array<Range> More...

ExprIntSetMap	EvalSetForEachSubExpr (PrimExpr e, const std::unordered_map< const VarNode *, IntSet > &dom_map)
	Find the integer set of every sub-expression, given the domain of each iteration variables. More...

IntSet	Union (const Array< IntSet > &sets)
	Create a union set of all sets, possibly relaxed. More...

Array< IntSet >	UnionRegion (const Array< Array< IntSet >> &nd_int_sets)
	The union of N-dimensional integer sets. More...

IntSet	UnionLowerBound (const Array< IntSet > &sets)
	Create a lower-bound of union set, where some of the segments may be dropped. More...

Array< IntSet >	UnionRegionLowerBound (const Array< Array< IntSet >> &nd_int_sets)
	The union of N-dimensional integer sets. More...

IntSet	Intersect (const Array< IntSet > &sets)
	Create an intersected set of all sets. More...

Map< Var, arith::IntSet >	AsIntSet (const Map< Var, Range > &var_dom)
	Converts the Ranges to IntSets. More...

Optional< Array< IntSet > >	EstimateRegionStrictBound (const Array< Range > &region, const Map< Var, Range > &var_dom, const PrimExpr &predicate, arith::Analyzer *analyzer)
	Analyze the region with affine map, given the domain of variables and their predicate. The result should be strict, i.e. no region is discarded or relaxed. More...

Optional< Array< IntSet > >	EstimateRegionLowerBound (const Array< Range > &region, const Map< Var, Range > &var_dom, const PrimExpr &predicate, arith::Analyzer *analyzer)
	Analyze the region with affine map, given the domain of variables and their predicate. Some subregion may be discarded during the lower-bound analysis. More...

Array< IntSet >	EstimateRegionUpperBound (const Array< Range > &region, const Map< Var, Range > &var_dom, const PrimExpr &predicate, arith::Analyzer *analyzer)
	Analyze the region with affine map, given the domain of variables and their predicate Relaxation of the region may be used in upper-bound analysis, i.e. some extra region may be added to the result. More...

void	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	SolveLinearEquations (const IntConstraints &system_to_solve)
	Solve linear equations. More...

PartialSolvedInequalities	SolveLinearInequalities (const IntConstraints &system_to_solve)
	Solve linear inequalities. More...

Array< PrimExpr >	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	SolveInequalitiesToRange (const IntConstraints &system_to_solve)
	Solve linear inequalities and infer the range of each variable. More...

IntConstraintsTransform	SolveInequalitiesDeskewRange (const IntConstraints &system_to_solve)
	Solve linear inequalities and deskew the ranges towards zero. More...

IterMapResult	DetectIterMap (const Array< PrimExpr > &indices, const Map< Var, Range > &input_iters, const PrimExpr &predicate, IterMapLevel check_level, arith::Analyzer *analyzer, bool simplify_trivial_iterators=true)
	Detect if indices can be written as [y_0 + c_0, y_1 + c_1, ..., y_n + c_n]. More...

Array< PrimExpr >	IterMapSimplify (const Array< PrimExpr > &indices, const Map< Var, Range > &input_iters, const PrimExpr &input_pred, IterMapLevel check_level, arith::Analyzer *analyzer, bool simplify_trivial_iterators=true)
	Use IterVarMap detector to rewrite and simplify the indices. More...

Map< Var, PrimExpr >	InverseAffineIterMap (const Array< IterSumExpr > &iter_map, const Array< PrimExpr > outputs)
	Apply the inverse of the affine transformation to the outputs. More...

Array< Array< IterMark > >	SubspaceDivide (const Array< PrimExpr > &bindings, const Map< Var, Range > &input_iters, const Array< Var > &sub_iters, const PrimExpr &predicate, IterMapLevel check_level, arith::Analyzer *analyzer, bool simplify_trivial_iterators=true)
	Detect if bindings can be written as [a_0e_0 + b_0 + c_0, a_1e_1 + b_1, ..., a_n*e_n + b_n]. More...

PrimExpr	NormalizeIterMapToExpr (const PrimExpr &expr)
	Given an expression that may contain IterMapExpr, transform it to normal PrimExpr. More...

IterSumExpr	NormalizeToIterSum (PrimExpr index, const Map< Var, Range > &input_iters, arith::Analyzer *analyzer)
	Rewrite index as IterSumExpr. More...

Array< PrimExpr >	DetectLinearEquation (const PrimExpr &e, const Array< tir::Var > &vars)
	Detect if e can be rewritten as e = sum_{i=0}^{n-1} var[i] * coeff[i] + coeff[n] Where coeff[i] and base are invariant of var[j] for all i and j. More...

Array< PrimExpr >	DetectClipBound (const PrimExpr &e, const Array< tir::Var > &vars)
	Detect if expression corresponds to clip bound of the vars. More...

Variables
constexpr int	kSimplifyRewriteCanonicalRewrite = 3

Detailed Description

namespace of arithmetic analysis.

Typedef Documentation

◆ ExprIntSetMap

using tvm::arith::ExprIntSetMap = typedef std::unordered_map<PrimExpr, IntSet, ObjectPtrHash, ObjectPtrEqual>

Map from Expr to IntSet.

◆ PartialSolvedInequalities

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

Enumeration Type Documentation

◆ CompareResult

enum tvm::arith::CompareResult : int

strong

Structure for representing result of known.

Values are assigned to allow these flags to be used in bitwise operations.

Enumerator
kInconsistent
kEQ
kLT
kLE
kGT
kGE
kNE
kUnknown

◆ DivMode

enum tvm::arith::DivMode

Enumerator
kTruncDiv	Truncated division.
kFloorDiv	Floor division.

◆ IterMapLevel

enum tvm::arith::IterMapLevel

Mapping level for iterators.

Enumerator
Bijective
Surjective
NoCheck

◆ ProofStrength

enum tvm::arith::ProofStrength : int

strong

The strength used in top-level condition proves.

Note: The higher, the more time consuming it can be.

Do not use level beyond kDefault in internal recursive rewriting in arith analysis and only use it at top-level simplification to avoid speed issues.

Enumerator
kDefault	default strength, can be used in.
kSymbolicBound	Prove using symbolic bound analysis.

◆ SignType

enum tvm::arith::SignType

Sign type of an integer expression.

Enumerator
kPositive
kNegative
kZero
kUnknown
kUnknown

Function Documentation

◆ AsConditions()

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.

Parameters

variables	The variables in `bounds`. It is used to determine the iteration order to avoid indeterministic results.
bounds	grouped boundary of the variables.
relations	other relations.

◆ AsIntSet()

Map<Var, arith::IntSet> tvm::arith::AsIntSet ( const Map< Var, Range > & var_dom )

Converts the Ranges to IntSets.

Parameters

var_dom The ranges of variables

Returns: The integer sets of the variables

◆ ConvertDomMap()

Map<Var, IntSet> tvm::arith::ConvertDomMap ( const std::unordered_map< const VarNode *, IntSet > & dom_map )

Convert std::unordered_map<const VarNode*, IntSet> to Map<Var, IntSet>

Parameters

dom_map The domain map to convert.

Returns: The converted map.

◆ DeduceBound() [1/2]

IntSet tvm::arith::DeduceBound	(	PrimExpr	v,
		PrimExpr	cond,
		const Map< Var, IntSet > &	hint_map,
		const Map< Var, IntSet > &	relax_map
	)

Deduce the bound of the target variable in a expression, give the domain of each variables. Return undefined IntSet to represent failure.

Note: The returned set may be smaller than set that contains all possible values of v that satisfies the bound.

Parameters

v	The target variable to be deduced.
cond	The conditional expression.
hint_map	The domain of variable, used to help deduce.
relax_map	The domain of each variable, used to relax the domain, The deduce bound must implies e for all value in relax_map

Returns: An integer set that always satisfies the condition.

◆ DeduceBound() [2/2]

IntSet tvm::arith::DeduceBound	(	PrimExpr	v,
		PrimExpr	cond,
		const std::unordered_map< const VarNode *, IntSet > &	hint_map,
		const std::unordered_map< const VarNode *, IntSet > &	relax_map
	)

Same as DeduceBound with unordered_map signature.

Parameters

v	The target variable to be deduced.
cond	The conditional expression.
hint_map	The domain of variable, used to help deduce.
relax_map	The domain of each variable, used to relax the domain, The deduce bound mush implies e for all value in relax_map

Returns: An integer set that always satisfies the condition.

◆ DetectClipBound()

Array<PrimExpr> tvm::arith::DetectClipBound	(	const PrimExpr &	e,
		const Array< tir::Var > &	vars
	)

Detect if expression corresponds to clip bound of the vars.

Parameters

e	The expression to be detected.
vars	List of variables to be used in detection.

Returns: concat([min_value[i], max_value[i]]), None is returned if there is no min or max value return empty if the e does not match the pattern.

◆ DetectIterMap()

IterMapResult tvm::arith::DetectIterMap	(	const Array< PrimExpr > &	indices,
		const Map< Var, Range > &	input_iters,
		const PrimExpr &	predicate,
		IterMapLevel	check_level,
		arith::Analyzer *	analyzer,
		bool	simplify_trivial_iterators = `true`
	)

Detect if indices can be written as [y_0 + c_0, y_1 + c_1, ..., y_n + c_n].

Here y = some-quasi-affine-iter-map(input_iters) and c are symbolic constants.

We also requires that y_i and y_j to be independent for i != j.

For returned value rv, the following is always true:

rv[i]->args.size() <=1: only one iterator per element.

Parameters

indices	The indices to detect pattern for.
input_iters	Map from variable to iterator's range.
predicate	The predicate constraints on the input iterators
check_level	The iter mapping checking level.
analyzer	Analyzer used to get context information.
simplify_trivial_iterators	If true, iterators with extent of 1 will be replaced with a constant value.

Returns: The detected iteration result. The return object's .indices is empty on failure.

◆ DetectLinearEquation()

Array<PrimExpr> tvm::arith::DetectLinearEquation	(	const PrimExpr &	e,
		const Array< tir::Var > &	vars
	)

Detect if e can be rewritten as e = sum_{i=0}^{n-1} var[i] * coeff[i] + coeff[n] Where coeff[i] and base are invariant of var[j] for all i and j.

Parameters

e	The expression to be detected.
vars	List of variables to be used in detection.

Returns: [coeff[i]] if it is possible, empty array if it is not.

◆ DomainTouched()

Region tvm::arith::DomainTouched	(	const Stmt &	body,
		const tir::Buffer &	buffer,
		bool	consider_loads,
		bool	consider_stores
	)

Infer a regular domain that covers all the calls or provides within the given statement.

Parameters

body	The given statement.
buffer	The buffer to check the access info.
consider_loads	If loads are considered.
consider_stores	If stores are considered.

Returns: The domain that covers all the calls or provides within the given statement.

◆ EstimateRegionLowerBound()

Optional<Array<IntSet> > tvm::arith::EstimateRegionLowerBound	(	const Array< Range > &	region,
		const Map< Var, Range > &	var_dom,
		const PrimExpr &	predicate,
		arith::Analyzer *	analyzer
	)

Analyze the region with affine map, given the domain of variables and their predicate. Some subregion may be discarded during the lower-bound analysis.

Parameters

region	The region to be analyzed
var_dom	The ranges of the variables
predicate	The predicate for the affine map
analyzer	The analyzer used

Returns: NullOpt if the detection fails, or an array of arith::IntSet as the result of analysis

◆ EstimateRegionStrictBound()

Optional<Array<IntSet> > tvm::arith::EstimateRegionStrictBound	(	const Array< Range > &	region,
		const Map< Var, Range > &	var_dom,
		const PrimExpr &	predicate,
		arith::Analyzer *	analyzer
	)

Analyze the region with affine map, given the domain of variables and their predicate. The result should be strict, i.e. no region is discarded or relaxed.

Parameters

region	The region to be analyzed
var_dom	The ranges of the variables
predicate	The predicate for the affine map
analyzer	The analyzer used

Returns: NullOpt if the detection fails, or an array of arith::IntSet as the result of analysis

◆ EstimateRegionUpperBound()

Array<IntSet> tvm::arith::EstimateRegionUpperBound	(	const Array< Range > &	region,
		const Map< Var, Range > &	var_dom,
		const PrimExpr &	predicate,
		arith::Analyzer *	analyzer
	)

Analyze the region with affine map, given the domain of variables and their predicate Relaxation of the region may be used in upper-bound analysis, i.e. some extra region may be added to the result.

Parameters

region	The region to be analyzed
var_dom	The ranges of the variables
predicate	The predicate for the affine map
analyzer	The analyzer used

Returns: an array of arith::IntSet as the result of analysis

◆ EvalSet() [1/7]

Array<IntSet> tvm::arith::EvalSet	(	const Array< Range > &	region,
		const Map< Var, IntSet > &	dom_map
	)

Same as EvalSet, but takes Array<Range>

Parameters

region	The range to be evaluated.
dom_map	The domain of each variable.

Returns: An array of integer sets that can cover all the possible values.

◆ EvalSet() [2/7]

IntSet tvm::arith::EvalSet	(	IntSet	s,
		const std::unordered_map< const VarNode *, IntSet > &	dom_map
	)

Find an symbolic integer set that contains is union over all the possible conditional values in dom_map.

Parameters

s	The initial set.
dom_map	The domain of each variable.

Returns: An integer set that can cover all the possible values.

◆ EvalSet() [3/7]

IntSet tvm::arith::EvalSet	(	PrimExpr	e,
		const Map< IterVar, IntSet > &	dom_map
	)

Find an symbolic integer set that contains all possible values of e given the domain of each iteration variables.

Parameters

e	The expression to be evaluated.
dom_map	The domain of each variable.

Returns: An integer set that can cover all the possible values of e.

◆ EvalSet() [4/7]

IntSet tvm::arith::EvalSet	(	PrimExpr	e,
		const Map< Var, IntSet > &	dom_map
	)

Find an symbolic integer set that contains all possible values of e given the domain of each variables.

Parameters

e	The expression to be evaluated.
dom_map	The domain of each variable.

Returns: An integer set that can cover all the possible values of e.

◆ EvalSet() [5/7]

IntSet tvm::arith::EvalSet	(	PrimExpr	e,
		const std::unordered_map< const tir::VarNode *, IntSet > &	dom_map
	)

Same as EvalSet, but takes unordered_map.

Parameters

e	The expression to be evaluated.
dom_map	The domain of each variable.

Returns: An integer set that can cover all the possible values of e.

◆ EvalSet() [6/7]

IntSet tvm::arith::EvalSet	(	Range	r,
		const Map< IterVar, IntSet > &	dom_map
	)

Find an symbolic integer set that contains is union over all the possible conditional values in dom_map.

Parameters

r	The initial range.
dom_map	The domain of each variable.

Returns: An integer set that can cover all the possible values.

◆ EvalSet() [7/7]

IntSet tvm::arith::EvalSet	(	Range	r,
		const std::unordered_map< const VarNode *, IntSet > &	dom_map
	)

Same as EvalSet, but takes unordered_map.

Parameters

r	The range to be evaluated.
dom_map	The domain of each variable.

Returns: An integer set that can cover all the possible values of e.

◆ EvalSetForEachSubExpr()

ExprIntSetMap tvm::arith::EvalSetForEachSubExpr	(	PrimExpr	e,
		const std::unordered_map< const VarNode *, IntSet > &	dom_map
	)

Find the integer set of every sub-expression, given the domain of each iteration variables.

Parameters

e	The expression to be evaluated.
dom_map	The domain of each variable.

Returns: the map from the expression to its possible value.

◆ Intersect()

IntSet tvm::arith::Intersect ( const Array< IntSet > & sets )

Create an intersected set of all sets.

Parameters

sets	The sets to be intersected

Returns: the set after intersected

◆ InverseAffineIterMap()

Map<Var, PrimExpr> tvm::arith::InverseAffineIterMap	(	const Array< IterSumExpr > &	iter_map,
		const Array< PrimExpr >	outputs
	)

Apply the inverse of the affine transformation to the outputs.

Similar to the back-propagation, starting from the outputs, it visits the DAG of the expressions in reverse topology order and applies the inverse of the affine transformation until it reaches the input. The affine iter map is required to be bijective.

For example, iter_map = [l0 // 16, l0 % 16], outputs = [output_0, output_1], the affine transformation specified by iter_map will be applied to outputs and the result will be {l0: ((output_0*16) + output_1)}.

The range of outputs should be the same as the output range of the affine transmation.

See also: DetectIterMap

Parameters

iter_map	The bijective affine iter map.
outputs	The outputs of the affine transformation.

Returns: The map from the input to the transformed result.

◆ IterMapSimplify()

Array<PrimExpr> tvm::arith::IterMapSimplify	(	const Array< PrimExpr > &	indices,
		const Map< Var, Range > &	input_iters,
		const PrimExpr &	input_pred,
		IterMapLevel	check_level,
		arith::Analyzer *	analyzer,
		bool	simplify_trivial_iterators = `true`
	)

Use IterVarMap detector to rewrite and simplify the indices.

Parameters

indices	The indices to detect pattern for.
input_iters	Map from variable to iterator's range.
input_pred	The predicate constraints on the input iterators
check_level	The iter mapping checking level.
analyzer	Analyzer used to get context information.
simplify_trivial_iterators	If true, iterators with unit extents are simplified

Returns: The indices after rewrite

◆ NormalizeIterMapToExpr()

PrimExpr tvm::arith::NormalizeIterMapToExpr ( const PrimExpr & expr )

Given an expression that may contain IterMapExpr, transform it to normal PrimExpr.

Parameters

expr	The input expression, which may contain IterMapExpr.

Returns: The corresponding normal PrimExpr.

◆ NormalizeToIterSum()

IterSumExpr tvm::arith::NormalizeToIterSum	(	PrimExpr	index,
		const Map< Var, Range > &	input_iters,
		arith::Analyzer *	analyzer
	)

Rewrite index as IterSumExpr.

((i0 // b0) % a0) * s0 + ((i0 // b1) % a1) * s1 ... + base

The iterators are ordered such that s0 > s1 ... if we can prove the relation.

Note that base may contain expressions that cannot be detected as the right pattern.

Parameters

index	The input index
input_iters	The input iterators.
analyzer	The input analyzer.

Note: This function is useful to detect iterator stride patterns.

◆ operator&()

constexpr CompareResult tvm::arith::operator&	(	CompareResult	lhs,
		CompareResult	rhs
	)

inlineconstexpr

◆ operator|()

constexpr CompareResult tvm::arith::operator\|	(	CompareResult	lhs,
		CompareResult	rhs
	)

inlineconstexpr

◆ SmithNormalFormDiag()

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.

Parameters

S	the original A_{mxn}, it will be modified to S_{mxn}
V	an identity matrix, it will be modified to V_{nxn}
x	the x in A x = y. it will be modified to V^{-1}_{nxn} x_{nx1}
y	the y in A x = y. it will be modified to U_{mxm} y_{mx1}

◆ SolveInequalitiesDeskewRange()

IntConstraintsTransform tvm::arith::SolveInequalitiesDeskewRange ( const IntConstraints & system_to_solve )

Solve linear inequalities and deskew the ranges towards zero.

Parameters

system_to_solve the variables to solve, their ranges, and a list of inequalities.

Returns

A transform (src IntConstraints -> dst IntConstraints) from original variables to a set of new variables. The ranges of new variables always start from zero, their extents are solved from system_to_solve. src IntConstraints is the same as system_to_solve. dst IntConstraints(variables, ranges, relations) contains,

variables - the variables that have been solved.
ranges - the best range (start from zero) of each variable.
relations - constraints that cannot be transformed to Range will be stored in relations. Variable mapping can be obtained from IntConstraintsTransform.src_to_dst and IntConstraintsTransform.dst_to_src.

◆ SolveInequalitiesToRange()

IntConstraints tvm::arith::SolveInequalitiesToRange ( const IntConstraints & system_to_solve )

Solve linear inequalities and infer the range of each variable.

Parameters

system_to_solve the variables to solve, their ranges, and a list of inequalities.

Returns

The result ranges for each variables. The returned IntConstraints(variables, ranges, relations) contains,

variables - the variables that have been solved.
ranges - the best range of each variable.
relations - constraints that cannot be transformed to Range will be stored in relations.

◆ SolveLinearEquations()

IntConstraintsTransform tvm::arith::SolveLinearEquations ( const IntConstraints & system_to_solve )

Solve linear equations.

Parameters

system_to_solve the variables to solve, their ranges, and a list of equations.

Returns: A new linear system, with less variables (if system_to_solve is NOT of full rank), or no variable (if system_to_solve is of full rank), or an empty linear system (if system_to_solve is unsolvable). It also provides the ranges of the variables in the new system, as well as inequalities inferred from the system_to_solve. You can get the mapping from the original variables to the solution via ret->src_to_dst.

◆ SolveLinearInequalities()

PartialSolvedInequalities tvm::arith::SolveLinearInequalities ( const IntConstraints & system_to_solve )

Solve linear inequalities.

Parameters

system_to_solve the variables to solve, their ranges, and a list of inequalities. The inequalities are rewritten using Fourier-Motzkin elimination. This function takes an array of (in)equalities and an array of variables, and essentially rewrites the (in)equalities into an array of (in)equalities of the following form,

x0 >= f0(x1, x2, ..., xn) x0 <= g0(x1, x2, ..., xn) x1 >= f1(x2, ..., xn) x1 <= g1(x2, ..., xn) ... xn >= fn() // just a constant xn <= gn() // just a constant

Returns: A map of variables and their solved bounds, and constrains that cannot be solved to bounds.

◆ SubspaceDivide()

Array<Array<IterMark> > tvm::arith::SubspaceDivide	(	const Array< PrimExpr > &	bindings,
		const Map< Var, Range > &	input_iters,
		const Array< Var > &	sub_iters,
		const PrimExpr &	predicate,
		IterMapLevel	check_level,
		arith::Analyzer *	analyzer,
		bool	simplify_trivial_iterators = `true`
	)

Detect if bindings can be written as [a_0*e_0 + b_0 + c_0, a_1*e_1 + b_1, ..., a_n*e_n + b_n].

where a = some-quasi-affine-iter-map(input_iters set_minus sub_iters) b = some-quasi-affine-iter-map(sub_iters) c is constant symbols e is the extent of b

For example, z*12 + y*3 + x + c = (z*4+y)*3 + x, if sub_iters={x}

Parameters

bindings	The input bindings
input_iters	Map from variable to iterator's range.
sub_iters	Iterators of subspace.
predicate	The predicate constraints on the input iterators
check_level	The iter mapping checking level.
analyzer	Analyzer used to get context information.
simplify_trivial_iterators	If true, iterators with extent of 1 will be replaced with a constant value.

Returns: The result list has length len(bindings) + 1 [0, len(bindings)): The iter map matching result. The inner list is of length 2. The first expr is the basis of the quotient space. The second expr is the basis of the subspace. len(bindings): the predicate of outer space and inner space Empty array if no match can be found.

◆ Union()

IntSet tvm::arith::Union ( const Array< IntSet > & sets )

Create a union set of all sets, possibly relaxed.

Parameters

sets	The sets to be combined

Returns: the set after union

◆ UnionLowerBound()

IntSet tvm::arith::UnionLowerBound ( const Array< IntSet > & sets )

Create a lower-bound of union set, where some of the segments may be dropped.

Parameters

sets	The sets to be combined

Returns: the set after union

◆ UnionRegion()

Array<IntSet> tvm::arith::UnionRegion ( const Array< Array< IntSet >> & nd_int_sets )

The union of N-dimensional integer sets.

Parameters

nd_int_sets A list of N-dimensional integer sets

Returns: An N-dimensional integer set as the result of union

◆ UnionRegionLowerBound()

Array<IntSet> tvm::arith::UnionRegionLowerBound ( const Array< Array< IntSet >> & nd_int_sets )

The union of N-dimensional integer sets.

Parameters

nd_int_sets A list of N-dimensional integer sets

Returns: An N-dimensional integer set as the result of union

Variable Documentation

◆ kSimplifyRewriteCanonicalRewrite

constexpr int tvm::arith::kSimplifyRewriteCanonicalRewrite = 3

constexpr

Classes

Typedefs

Enumerations

Functions

Variables

Detailed Description

Typedef Documentation

◆ ExprIntSetMap

◆ PartialSolvedInequalities

Enumeration Type Documentation

◆ CompareResult

◆ DivMode

◆ IterMapLevel

◆ ProofStrength

◆ SignType

Function Documentation

◆ AsConditions()

◆ AsIntSet()

◆ ConvertDomMap()

◆ DeduceBound() [1/2]

◆ DeduceBound() [2/2]

◆ DetectClipBound()

◆ DetectIterMap()

◆ DetectLinearEquation()

◆ DomainTouched()

◆ EstimateRegionLowerBound()

◆ EstimateRegionStrictBound()

◆ EstimateRegionUpperBound()

◆ EvalSet() [1/7]

◆ EvalSet() [2/7]

◆ EvalSet() [3/7]

◆ EvalSet() [4/7]

◆ EvalSet() [5/7]

◆ EvalSet() [6/7]

◆ EvalSet() [7/7]

◆ EvalSetForEachSubExpr()

◆ Intersect()

◆ InverseAffineIterMap()

◆ IterMapSimplify()

◆ NormalizeIterMapToExpr()

◆ NormalizeToIterSum()

◆ operator&()

◆ operator|()

◆ SmithNormalFormDiag()

◆ SolveInequalitiesDeskewRange()

◆ SolveInequalitiesToRange()

◆ SolveLinearEquations()

◆ SolveLinearInequalities()

◆ SubspaceDivide()

◆ Union()

◆ UnionLowerBound()

◆ UnionRegion()

◆ UnionRegionLowerBound()

Variable Documentation

◆ kSimplifyRewriteCanonicalRewrite