iter_affine_map.h File Reference

Iterator quasi-affine mapping patterns. More...

#include <tvm/arith/analyzer.h>
#include <tvm/ffi/reflection/registry.h>
#include <tvm/ir/cow.h>
#include <tvm/ir/expr.h>
#include <tvm/tirx/var.h>

Include dependency graph for iter_affine_map.h:

This graph shows which files directly or indirectly include this file:

Go to the source code of this file.

Classes
class	tvm::arith::IterMapExprNode
	Base class of all iter map expressions. More...
class	tvm::arith::IterMapExpr
	Managed reference to IterMapExprNode. More...
class	tvm::arith::IterMarkNode
	Mark the source as an iterator in [0, extent). More...
class	tvm::arith::IterMark
	Managed reference to IterMarkExprNode. More...
class	tvm::arith::IterSplitExprNode
	Split of an iterator. More...
class	tvm::arith::IterSplitExpr
	Managed reference to IterSplitExprNode. More...
class	tvm::arith::IterSumExprNode
	Fuse multiple iterators by summing them with scaling. More...
class	tvm::arith::IterSumExpr
	Managed reference to IterSumExprNode. More...
class	tvm::arith::IterMapResultNode
	Result of DetectIterMap. More...
class	tvm::arith::IterMapResult
	Managed reference to IterMapResultNode. More...

Namespaces
namespace	tvm
	An object that builds and maintains block scope and StmtSref mapping for Dependence analysis.
namespace	tvm::arith
	namespace of arithmetic analysis.
namespace	tvm::ffi

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

Functions
IterMapResult	tvm::arith::DetectIterMap (const ffi::Array< PrimExpr > &indices, const ffi::Map< tirx::PrimVar, Range > &input_iters, const PrimExpr &predicate, IterMapLevel check_level, const 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].
ffi::Array< PrimExpr >	tvm::arith::IterMapSimplify (const ffi::Array< PrimExpr > &indices, const ffi::Map< tirx::PrimVar, Range > &input_iters, const PrimExpr &input_pred, IterMapLevel check_level, const arith::Analyzer &analyzer, bool simplify_trivial_iterators=true)
	Use IterVarMap detector to rewrite and simplify the indices.
ffi::Map< Var, PrimExpr >	tvm::arith::InverseAffineIterMap (const ffi::Array< IterSumExpr > &iter_map, const ffi::Array< PrimExpr > outputs)
	Apply the inverse of the affine transformation to the outputs.
ffi::Array< ffi::Array< IterMark > >	tvm::arith::SubspaceDivide (const ffi::Array< PrimExpr > &bindings, const ffi::Map< tirx::PrimVar, Range > &input_iters, const ffi::Array< tirx::PrimVar > &sub_iters, const PrimExpr &predicate, IterMapLevel check_level, const 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].
PrimExpr	tvm::arith::NormalizeIterMapToExpr (const PrimExpr &expr)
	Given an expression that may contain IterMapExpr, transform it to normal PrimExpr.
IterSumExpr	tvm::arith::NormalizeToIterSum (PrimExpr index, const ffi::Map< tirx::PrimVar, Range > &input_iters, const arith::Analyzer &analyzer)
	Rewrite index as IterSumExpr.

Detailed Description

Iterator quasi-affine mapping patterns.

This file defines a collection of mapping patterns maps a collection of independent iterators to another collection of independent iterators.

There are two main kinds of mapping patterns:

• Fuse: fuse a collection of iterators into a single one

  domain(x0) = [0, 4), domain(x1) = [0, 3), domain(x2) = [0, 2) fuse(x0, x1, x2): y = x2 * 12 + x1 * 4 + x0 domain(y) = [0, 24)

• Split: split an iterator into multiple ones

  domain(x) = [0, 24) split(x, 3, 12): [y0, y1, y2] = [x % 3, (x % 12) / 3, x / 12] domain(y0) = [0, 3), domain(y1) = [0, 4), domain(y2) = [0, 2)

We use the name "(quasi)affine" to be consistent with the terminology used in the polyhedral compilation. Notably, fuse is an affine transformation, while split corresponds to additional floordiv/mod operations that can appear in quasi-affine transformations.