A class to handle all iteration lattice operations. More...

#include "mlir/Dialect/SparseTensor/Utils/Merger.h"

Public Types
using	ForeachTensorLoopIdCallback = function_ref< void(TensorLoopId, TensorId, std::optional< Level >, LevelType, bool)>

Public Member Functions
	Merger (unsigned numInputOutputTensors, unsigned numLoops, unsigned maxLvlRank)
	Constructs a merger for the given number of tensors and loops. More...

constexpr TensorId	makeTensorId (unsigned t) const
	Safely converts the argument to a tensor identifier. More...

constexpr LoopId	makeLoopId (unsigned i) const
	Safely converts the argument to a loop identifier. More...

constexpr TensorLoopId	makeTensorLoopId (unsigned t, unsigned i) const
	Safely converts the arguments to a pair of (tensor,loop) identifiers. More...

ExprId	addTensorExp (TensorId t)
	Constructs a new tensor expression, and returns its identifier. More...

ExprId	addLoopVarExp (LoopId i)
	Constructs a new loop-variable expression, and returns its identifier. More...

ExprId	addInvariantExp (Value v)
	Constructs a new invariant expression, and returns its identifier. More...

ExprId	addSynZeroExp ()
	Constructs a new synthetic zero expression. More...

ExprId	addExp (TensorExp::Kind k, ExprId e0, ExprId e1=detail::kInvalidId, Operation *op=nullptr, Attribute attr=nullptr)
	Constructs a new unary or binary expression, and returns its identifier. More...

ExprId	addExp (TensorExp::Kind k, ExprId e, Value v, Operation *op=nullptr, Attribute attr=nullptr)
	Constructs a new sesquinary expression, and returns its identifier. More...

LatPointId	addLat (TensorId t, LoopId i, ExprId e)
	Constructs a new iteration lattice point, and returns its identifier. More...

LatPointId	addLat (const BitVector &bits, ExprId e)

LatSetId	addSet ()
	Constructs a new (initially empty) set, and returns its identifier. More...

LatPointId	conjLat (ExprId e, LatPointId p0, LatPointId p1, Operation *op=nullptr)
	Computes a single conjunction of two lattice points by taking the "union" of `LoopId` (effectively constructing a larger "intersection" of those loops) with a newly constructed tensor (sub)expression of given kind. More...

LatSetId	conjSet (ExprId e, LatSetId s0, LatSetId s1, Operation *op=nullptr)
	Conjunctive merge of two lattice sets: `(s0 /\_op s1)`. More...

LatSetId	disjSet (ExprId e, LatSetId s0, LatSetId s1, Operation *op=nullptr)
	Disjunctive merge of two lattice sets: `(s0 /\_op s1, s0, s1)`. More...

LatSetId	disjSetWithZero (ExprId e, LatSetId s0, LatSetId s1)
	Disjunctive merge of two lattice sets and also set one of the operand to zero: `(s0 /\_op s1 (e0 op e1), s0 (0 op e0), s1 (e1 op 0))`. More...

LatSetId	combiSet (ExprId e, LatSetId s0, LatSetId s1, Operation orig, bool includeLeft, TensorExp::Kind ltrans, Operation opleft, bool includeRight, TensorExp::Kind rtrans, Operation *opright)
	Disjunctive merge of two lattice sets with custom handling of the overlap, left, and right regions. More...

LatSetId	mapSet (TensorExp::Kind kind, LatSetId s, Value v=Value(), Operation *op=nullptr)
	Maps the unary operator over the lattice set of the operand, i.e. More...

LatSetId	mapBinWithSynZeroSet (ExprId e, LatSetId s, bool lhsZero)
	Maps the binary operator to the same operation but with one of its operand set to zero, i.e. More...

LatSetId	optimizeSet (LatSetId s)
	Optimizes the iteration lattice points in the given set. More...

BitVector	simplifyCond (LatSetId s, LatPointId p)
	Simplifies the conditions in a conjunction of a given lattice point within the given set using just two basic rules: (1) multiple dense conditions are reduced to single dense, and (2) a singleton sparse/dense is reduced to sparse/random access. More...

bool	latGT (LatPointId p0, LatPointId p1) const
	Returns true if p0 > p1. More...

bool	onlyDenseDiff (LatPointId p0, LatPointId p1) const
	Returns true if p0 and p1 only differ in dense. More...

constexpr TensorId	tensor (TensorLoopId b) const
	Gets the tensor-identifier of the `TensorLoopId`. More...

constexpr LoopId	loop (TensorLoopId b) const
	Gets the loop-identifier of the `TensorLoopId`. More...

constexpr unsigned	getNumTensors () const
	Gets the total number of tensors (including the output-tensor and synthetic-tensor). More...

constexpr unsigned	getNumLoops () const
	Gets the total number of loops (native loops + filter loops). More...

constexpr bool	isOutTensor (TensorLoopId b, LoopId i) const
	Returns true if `b` is the `i`th loop of the output tensor. More...

constexpr TensorId	getOutTensorID () const
	Gets the output tensor's identifier. More...

constexpr TensorId	getSynTensorID () const
	Gets the synthetic tensor's identifier (used for all invariant tensor expressions). More...

bool	expIsTensor (ExprId e, TensorId t) const
	Returns true if the expression is `(kTensor t)`. More...

bool	expContainsTensor (ExprId e, TensorId t) const
	Returns true if the expression contains the tensor as an operand. More...

bool	hasNegateOnOut (ExprId e) const
	Returns true if the expression contains a negation on output tensor. More...

bool	isSingleCondition (TensorId t, ExprId e) const
	Returns true if given tensor iterates only in the given tensor expression. More...

bool	hasAnySparse (const BitVector &bits) const
	Returns true if any `TensorLoopId` in the bitvector corresponds to sparse level-type. More...

bool	hasSparseIdxReduction (const BitVector &bits) const
	Returns true if bits contains a dependent index reduction condition on sparse levels. More...

LevelType	getLvlType (TensorId t, LoopId i) const
	Gets the level-type of the `t`th tensor on `i`th loop. More...

LevelType	getLvlType (TensorLoopId b) const
	Gets the level-type of the TensorLoopId. More...

std::optional< LoopId >	getLoopId (TensorId t, Level lvl) const
	Gets the loop identifier for the `lvl`th level of the `t`th tensor. More...

std::optional< Level >	getLvl (TensorId t, LoopId i) const
	Gets the level number of the the `t`th tensor on `i`th loop. More...

std::optional< Level >	getLvl (TensorLoopId b) const

void	setLevelAndType (TensorId t, LoopId i, Level lvl, LevelType lt)
	Sets the level number and level-type of the `t`th tensor on `i`th loop. More...

void	foreachTensorLoopId (LatPointId p, ForeachTensorLoopIdCallback callback) const
	Iterates over a set of `TensorLoopId`s, invoking the callback for each `TensorLoopId` and passing it the corresponding tensor identifier, level, and level-type, following with a boolean value indicating whether it is a dependent index reduction loop condition. More...

void	foreachTensorLoopId (LatPointId p, bool simple, ForeachTensorLoopIdCallback callback) const

void	setHasSparseOut (bool s)
	Sets whether the output tensor is sparse or not. More...

void	setLoopDependentTensorLevel (LoopId i, TensorId t, Level lvl, LevelType lt, unsigned coefficient)
	Establishes the two-way map that i <-> <t, lvl, lt>. More...

bool	hasDependentLvl (LoopId i, TensorId t)
	Whether the loop has dependent slice. More...

std::vector< LoopCoeffPair > &	getDependentLoops (TensorId t, Level lvl)
	Returns the list of loop indices which appear in the non-trivial index expression on t_l, e.g., A[i+j] => {i, j}. More...

std::pair< TensorId, Level >	getLoopDefiningLvl (LoopId i) const
	Returns the defining [tid, lvl] for the loop. More...

bool	isLvlWithNonTrivialIdxExp (TensorLoopId b) const
	Checks whether the TensorLoopId represents a tensor level contains non-trivial index expression. More...

bool	isSparseLvlWithNonTrivialIdxExp (TensorLoopId b) const
	Checks whether the TensorLoopId represents a sparse tensor level contains non-trivial index expression. More...

Level	getLoopDependentLevel (TensorLoopId b) const

LevelType	getLoopDependentLevelType (TensorLoopId b) const

const TensorExp &	exp (ExprId e) const
	Convenience getters to immediately access the stored nodes. More...

const LatPoint &	lat (LatPointId p) const

ArrayRef< LatPointId >	set (LatSetId s) const

bool	hasExprValue (ExprId e) const
	Checks whether the given expression has an associated value. More...

void	setExprValue (ExprId e, Value v)
	Sets the expression to have the associated value. More...

void	clearExprValue (ExprId e)
	Clears the value associated with the expression. More...

void	dumpExp (ExprId e) const
	Print methods (for debugging). More...

void	dumpLat (LatPointId p) const

void	dumpSet (LatSetId s) const

void	dumpBits (const BitVector &bits) const

LatSetId	buildLattices (ExprId e, LoopId i)
	Builds the iteration lattices in a bottom-up traversal given the remaining tensor (sub)expression and the next loop in the iteration graph. More...

std::optional< ExprId >	buildTensorExpFromLinalg (linalg::GenericOp op)
	Builds a tensor expression from the given Linalg operation. More...

Value	buildExp (RewriterBase &rewriter, Location loc, ExprId e, Value v0, Value v1) const
	Rebuilds SSA format from a tensor expression. More...

Detailed Description

A class to handle all iteration lattice operations.

This class abstracts away from some implementation details of storing iteration lattices and tensor expressions. This allows for fine-tuning performance characteristics independently from the basic algorithm if bottlenecks are identified.

Definition at line 224 of file Merger.h.

Member Typedef Documentation

◆ ForeachTensorLoopIdCallback

using mlir::sparse_tensor::Merger::ForeachTensorLoopIdCallback = function_ref<void( TensorLoopId, TensorId, std::optional<Level>, LevelType, bool)>

Definition at line 434 of file Merger.h.

Constructor & Destructor Documentation

◆ Merger()

mlir::sparse_tensor::Merger::Merger	(	unsigned	numInputOutputTensors,
		unsigned	numLoops,
		unsigned	maxLvlRank
	)

Constructs a merger for the given number of tensors and loops.

The user supplies the number of tensors involved in the kernel, with the last tensor in this set denoting the output tensor. The merger adds an additional synthetic tensor at the end of this set to represent all invariant expressions in the kernel.

The maxLvlRank specifies the max level rank of all inputs/output tensors. It is used to pre-allocate sufficient memory for internal storage.

Definition at line 223 of file Merger.cpp.

References mlir::sparse_tensor::Undef.

Member Function Documentation

◆ addExp() [1/2]

ExprId mlir::sparse_tensor::Merger::addExp	(	TensorExp::Kind	k,
		ExprId	e,
		Value	v,
		Operation *	op = `nullptr`,
		Attribute	attr = `nullptr`
	)

Constructs a new sesquinary expression, and returns its identifier.

Currently no sesquinary Kind allows specifying the op, but we allow it anyways because mapSet is designed to allow it.

Definition at line 283 of file Merger.cpp.

◆ addExp() [2/2]

ExprId mlir::sparse_tensor::Merger::addExp	(	TensorExp::Kind	k,
		ExprId	e0,
		ExprId	e1 = `detail::kInvalidId`,
		Operation *	op = `nullptr`,
		Attribute	attr = `nullptr`
	)

Constructs a new unary or binary expression, and returns its identifier.

Definition at line 275 of file Merger.cpp.

◆ addInvariantExp()

ExprId mlir::sparse_tensor::Merger::addInvariantExp ( Value v )

Constructs a new invariant expression, and returns its identifier.

Definition at line 261 of file Merger.cpp.

References mlir::sparse_tensor::detail::kInvalidId, and mlir::sparse_tensor::TensorExp::kInvariant.

◆ addLat() [1/2]

LatPointId mlir::sparse_tensor::Merger::addLat	(	const BitVector &	bits,
		ExprId	e
	)

Definition at line 300 of file Merger.cpp.

◆ addLat() [2/2]

LatPointId mlir::sparse_tensor::Merger::addLat	(	TensorId	t,
		LoopId	i,
		ExprId	e
	)

Constructs a new iteration lattice point, and returns its identifier.

Definition at line 291 of file Merger.cpp.

References makeTensorLoopId().

◆ addLoopVarExp()

ExprId mlir::sparse_tensor::Merger::addLoopVarExp ( LoopId i )

Constructs a new loop-variable expression, and returns its identifier.

Definition at line 253 of file Merger.cpp.

References mlir::sparse_tensor::detail::kInvalidId, and mlir::sparse_tensor::TensorExp::kLoopVar.

◆ addSet()

LatSetId mlir::sparse_tensor::Merger::addSet ( )

Constructs a new (initially empty) set, and returns its identifier.

Definition at line 307 of file Merger.cpp.

Referenced by optimizeSet().

◆ addSynZeroExp()

ExprId mlir::sparse_tensor::Merger::addSynZeroExp ( )

Constructs a new synthetic zero expression.

Definition at line 268 of file Merger.cpp.

References mlir::sparse_tensor::detail::kInvalidId, and mlir::sparse_tensor::TensorExp::kSynZero.

◆ addTensorExp()

ExprId mlir::sparse_tensor::Merger::addTensorExp ( TensorId t )

Constructs a new tensor expression, and returns its identifier.

Definition at line 245 of file Merger.cpp.

References mlir::sparse_tensor::detail::kInvalidId, and mlir::sparse_tensor::TensorExp::kTensor.

◆ buildExp()

Value mlir::sparse_tensor::Merger::buildExp	(	RewriterBase &	rewriter,
		Location	loc,
		ExprId	e,
		Value	v0,
		Value	v1
	)		const

Rebuilds SSA format from a tensor expression.

Definition at line 1538 of file Merger.cpp.

◆ buildLattices()

LatSetId mlir::sparse_tensor::Merger::buildLattices	(	ExprId	e,
		LoopId	i
	)

Builds the iteration lattices in a bottom-up traversal given the remaining tensor (sub)expression and the next loop in the iteration graph.

Returns the identifier of the root set.

Definition at line 936 of file Merger.cpp.

References exp().

Referenced by genStmt().

◆ buildTensorExpFromLinalg()

std::optional< ExprId > mlir::sparse_tensor::Merger::buildTensorExpFromLinalg ( linalg::GenericOp op )

Builds a tensor expression from the given Linalg operation.

On success, returns the identifier of the root expression.

Definition at line 1187 of file Merger.cpp.

Referenced by mlir::sparse_tensor::CodegenEnv::initTensorExp().

◆ clearExprValue()

void mlir::sparse_tensor::Merger::clearExprValue ( ExprId e )

inline

Clears the value associated with the expression.

Asserts that the expression does indeed have an associated value before clearing it.

Definition at line 567 of file Merger.h.

References exp().

Referenced by mlir::sparse_tensor::CodegenEnv::endReduc(), and mlir::sparse_tensor::CodegenEnv::updateReduc().

◆ combiSet()

LatSetId mlir::sparse_tensor::Merger::combiSet	(	ExprId	e,
		LatSetId	s0,
		LatSetId	s1,
		Operation *	orig,
		bool	includeLeft,
		TensorExp::Kind	ltrans,
		Operation *	opleft,
		bool	includeRight,
		TensorExp::Kind	rtrans,
		Operation *	opright
	)

Disjunctive merge of two lattice sets with custom handling of the overlap, left, and right regions.

Any region may be left missing in the output. Returns the identifier of the new set.

Definition at line 379 of file Merger.cpp.

References conjSet(), and mapSet().

◆ conjLat()

LatPointId mlir::sparse_tensor::Merger::conjLat	(	ExprId	e,
		LatPointId	p0,
		LatPointId	p1,
		Operation *	op = `nullptr`
	)

Computes a single conjunction of two lattice points by taking the "union" of LoopId (effectively constructing a larger "intersection" of those loops) with a newly constructed tensor (sub)expression of given kind.

Returns the identifier of the new lattice point.

Definition at line 313 of file Merger.cpp.

◆ conjSet()

LatSetId mlir::sparse_tensor::Merger::conjSet	(	ExprId	e,
		LatSetId	s0,
		LatSetId	s1,
		Operation *	op = `nullptr`
	)

Conjunctive merge of two lattice sets: (s0 /\_op s1).

Returns the identifier of the new set.

Definition at line 327 of file Merger.cpp.

Referenced by combiSet().

◆ disjSet()

LatSetId mlir::sparse_tensor::Merger::disjSet	(	ExprId	e,
		LatSetId	s0,
		LatSetId	s1,
		Operation *	op = `nullptr`
	)

Disjunctive merge of two lattice sets: (s0 /\_op s1, s0, s1).

Returns the identifier of the new set.

Definition at line 336 of file Merger.cpp.

◆ disjSetWithZero()

LatSetId mlir::sparse_tensor::Merger::disjSetWithZero	(	ExprId	e,
		LatSetId	s0,
		LatSetId	s1
	)

Disjunctive merge of two lattice sets and also set one of the operand to zero: (s0 /\_op s1 (e0 op e1), s0 (0 op e0), s1 (e1 op 0)).

Returns the identifier of the new set.

Definition at line 355 of file Merger.cpp.

References exp().

◆ dumpBits()

void mlir::sparse_tensor::Merger::dumpBits ( const BitVector & bits ) const

Definition at line 916 of file Merger.cpp.

References isLvlWithNonTrivialIdxExp(), loop(), tensor(), and mlir::sparse_tensor::toMLIRString().

Referenced by dumpLat().

◆ dumpExp()

void mlir::sparse_tensor::Merger::dumpExp ( ExprId e ) const

Print methods (for debugging).

Definition at line 796 of file Merger.cpp.

Referenced by dumpLat().

◆ dumpLat()

void mlir::sparse_tensor::Merger::dumpLat ( LatPointId p ) const

Definition at line 895 of file Merger.cpp.

References dumpBits(), dumpExp(), and lat().

Referenced by dumpSet().

◆ dumpSet()

void mlir::sparse_tensor::Merger::dumpSet ( LatSetId s ) const

Definition at line 906 of file Merger.cpp.

References dumpLat(), and set().

◆ exp()

const TensorExp& mlir::sparse_tensor::Merger::exp ( ExprId e ) const

inline

Convenience getters to immediately access the stored nodes.

These methods return const& because the underlying objects must not be mutated by client code. The only exception is for mutating the value associated with an expression, for which there are dedicated methods below.

NOTE: It is inadvisable to keep the reference alive for a long time (e.g., as in TensorExpr &te = merger.exp(e)), since insertions into the merger can cause data movement which will invalidate the underlying memory address. This isn't just a problem with the & references, but also applies to the ArrayRef. In particular, using for (LatPointId p : merger.set(s)) will run into the same dangling-reference problems if the loop body inserts new sets.

Definition at line 541 of file Merger.h.

Referenced by buildExp(), buildLattices(), clearExprValue(), disjSetWithZero(), dumpExp(), mlir::sparse_tensor::CodegenEnv::exp(), expContainsTensor(), expIsTensor(), hasExprValue(), hasNegateOnOut(), isSingleCondition(), optimizeSet(), and setExprValue().

◆ expContainsTensor()

bool mlir::sparse_tensor::Merger::expContainsTensor	(	ExprId	e,
		TensorId	t
	)		const

Returns true if the expression contains the tensor as an operand.

Definition at line 521 of file Merger.cpp.

References exp(), mlir::sparse_tensor::getExpArity(), mlir::sparse_tensor::kBinary, mlir::sparse_tensor::kNullary, mlir::sparse_tensor::TensorExp::kTensor, and mlir::sparse_tensor::kUnary.

Referenced by hasNegateOnOut().

◆ expIsTensor()

bool mlir::sparse_tensor::Merger::expIsTensor	(	ExprId	e,
		TensorId	t
	)		const

inline

Returns true if the expression is (kTensor t).

Definition at line 369 of file Merger.h.

References exp(), and mlir::sparse_tensor::TensorExp::kTensor.

Referenced by optimizeSet().

◆ foreachTensorLoopId() [1/2]

void mlir::sparse_tensor::Merger::foreachTensorLoopId	(	LatPointId	p,
		bool	simple,
		ForeachTensorLoopIdCallback	callback
	)		const

inline

Definition at line 447 of file Merger.h.

References getLoopDependentLevel(), getLvl(), getLvlType(), isLvlWithNonTrivialIdxExp(), lat(), and tensor().

◆ foreachTensorLoopId() [2/2]

void mlir::sparse_tensor::Merger::foreachTensorLoopId	(	LatPointId	p,
		ForeachTensorLoopIdCallback	callback
	)		const

inline

Iterates over a set of TensorLoopIds, invoking the callback for each TensorLoopId and passing it the corresponding tensor identifier, level, and level-type, following with a boolean value indicating whether it is a dependent index reduction loop condition.

Definition at line 441 of file Merger.h.

Referenced by genIf(), startLoopSeq(), and translateBitsToTidLvlPairs().

◆ getDependentLoops()

std::vector<LoopCoeffPair>& mlir::sparse_tensor::Merger::getDependentLoops	(	TensorId	t,
		Level	lvl
	)

inline

Returns the list of loop indices which appear in the non-trivial index expression on t_l, e.g., A[i+j] => {i, j}.

Definition at line 487 of file Merger.h.

Referenced by mlir::sparse_tensor::CodegenEnv::startEmit().

◆ getLoopDefiningLvl()

std::pair<TensorId, Level> mlir::sparse_tensor::Merger::getLoopDefiningLvl ( LoopId i ) const

inline

Returns the defining [tid, lvl] for the loop.

Definition at line 493 of file Merger.h.

◆ getLoopDependentLevel()

Level mlir::sparse_tensor::Merger::getLoopDependentLevel ( TensorLoopId b ) const

inline

Definition at line 518 of file Merger.h.

References isLvlWithNonTrivialIdxExp(), loop(), and tensor().

Referenced by foreachTensorLoopId().

◆ getLoopDependentLevelType()

LevelType mlir::sparse_tensor::Merger::getLoopDependentLevelType ( TensorLoopId b ) const

inline

Definition at line 523 of file Merger.h.

References isLvlWithNonTrivialIdxExp(), loop(), and tensor().

Referenced by isSparseLvlWithNonTrivialIdxExp().

◆ getLoopId()

std::optional<LoopId> mlir::sparse_tensor::Merger::getLoopId	(	TensorId	t,
		Level	lvl
	)		const

inline

Gets the loop identifier for the lvlth level of the tth tensor.

Definition at line 409 of file Merger.h.

◆ getLvl() [1/2]

std::optional<Level> mlir::sparse_tensor::Merger::getLvl	(	TensorId	t,
		LoopId	i
	)		const

inline

Gets the level number of the the tth tensor on ith loop.

Definition at line 415 of file Merger.h.

Referenced by foreachTensorLoopId(), getLvl(), and translateBitsToTidLvlPairs().

◆ getLvl() [2/2]

std::optional<Level> mlir::sparse_tensor::Merger::getLvl ( TensorLoopId b ) const

inline

Definition at line 419 of file Merger.h.

References getLvl(), loop(), and tensor().

◆ getLvlType() [1/2]

LevelType mlir::sparse_tensor::Merger::getLvlType	(	TensorId	t,
		LoopId	i
	)		const

inline

Gets the level-type of the tth tensor on ith loop.

Definition at line 398 of file Merger.h.

Referenced by findAffine(), findDepIdxSet(), foreachTensorLoopId(), getLvlType(), hasAnySparse(), mlir::sparse_tensor::CodegenEnv::lt(), and simplifyCond().

◆ getLvlType() [2/2]

LevelType mlir::sparse_tensor::Merger::getLvlType ( TensorLoopId b ) const

inline

Gets the level-type of the TensorLoopId.

Definition at line 404 of file Merger.h.

References getLvlType(), loop(), and tensor().

◆ getNumLoops()

constexpr unsigned mlir::sparse_tensor::Merger::getNumLoops ( ) const

inlineconstexpr

Gets the total number of loops (native loops + filter loops).

Definition at line 354 of file Merger.h.

Referenced by mlir::sparse_tensor::CodegenEnv::getLoopNum().

◆ getNumTensors()

constexpr unsigned mlir::sparse_tensor::Merger::getNumTensors ( ) const

inlineconstexpr

Gets the total number of tensors (including the output-tensor and synthetic-tensor).

Definition at line 351 of file Merger.h.

Referenced by mlir::sparse_tensor::CodegenEnv::makeTensorLevel().

◆ getOutTensorID()

constexpr TensorId mlir::sparse_tensor::Merger::getOutTensorID ( ) const

inlineconstexpr

Gets the output tensor's identifier.

Definition at line 362 of file Merger.h.

Referenced by mlir::sparse_tensor::CodegenEnv::makeTensorLevel(), startLoop(), and translateBitsToTidLvlPairs().

◆ getSynTensorID()

constexpr TensorId mlir::sparse_tensor::Merger::getSynTensorID ( ) const

inlineconstexpr

Gets the synthetic tensor's identifier (used for all invariant tensor expressions).

Definition at line 366 of file Merger.h.

Referenced by mlir::sparse_tensor::CodegenEnv::makeTensorLevel(), startLoop(), startLoopSeq(), and translateBitsToTidLvlPairs().

◆ hasAnySparse()

bool mlir::sparse_tensor::Merger::hasAnySparse ( const BitVector & bits ) const

Returns true if any TensorLoopId in the bitvector corresponds to sparse level-type.

Definition at line 669 of file Merger.cpp.

References getLvlType(), hasSparseIdxReduction(), mlir::sparse_tensor::is2OutOf4LT(), mlir::sparse_tensor::isCompressedLT(), mlir::sparse_tensor::isLooseCompressedLT(), and mlir::sparse_tensor::isSingletonLT().

Referenced by onlyDenseDiff(), simplifyCond(), and startLoopSeq().

◆ hasDependentLvl()

bool mlir::sparse_tensor::Merger::hasDependentLvl	(	LoopId	i,
		TensorId	t
	)

inline

Whether the loop has dependent slice.

Definition at line 480 of file Merger.h.

Referenced by findDepIdxSet().

◆ hasExprValue()

bool mlir::sparse_tensor::Merger::hasExprValue ( ExprId e ) const

inline

Checks whether the given expression has an associated value.

Definition at line 555 of file Merger.h.

References exp(), and mlir::sparse_tensor::TensorExp::val.

◆ hasNegateOnOut()

bool mlir::sparse_tensor::Merger::hasNegateOnOut ( ExprId e ) const

Returns true if the expression contains a negation on output tensor.

I.e., - outTensor or exp - outputTensor NOTE: this is an trivial tests in that it does not handle recursive negation, i.e., it returns true when the expression is -(-tensor).

Definition at line 543 of file Merger.cpp.

References exp(), expContainsTensor(), mlir::sparse_tensor::getExpArity(), mlir::sparse_tensor::kBinary, mlir::sparse_tensor::TensorExp::kDenseOp, mlir::sparse_tensor::detail::kInvalidId, mlir::sparse_tensor::TensorExp::kNegC, mlir::sparse_tensor::TensorExp::kNegF, mlir::sparse_tensor::TensorExp::kNegI, mlir::sparse_tensor::kNullary, mlir::sparse_tensor::TensorExp::kSubC, mlir::sparse_tensor::TensorExp::kSubF, mlir::sparse_tensor::TensorExp::kSubI, and mlir::sparse_tensor::kUnary.

Referenced by mlir::sparse_tensor::CodegenEnv::isAdmissibleTensorExp().

◆ hasSparseIdxReduction()

bool mlir::sparse_tensor::Merger::hasSparseIdxReduction ( const BitVector & bits ) const

Returns true if bits contains a dependent index reduction condition on sparse levels.

Definition at line 679 of file Merger.cpp.

References isSparseLvlWithNonTrivialIdxExp().

Referenced by hasAnySparse().

◆ isLvlWithNonTrivialIdxExp()

bool mlir::sparse_tensor::Merger::isLvlWithNonTrivialIdxExp ( TensorLoopId b ) const

inline

Checks whether the TensorLoopId represents a tensor level contains non-trivial index expression.

Definition at line 500 of file Merger.h.

References loop(), and tensor().

Referenced by dumpBits(), foreachTensorLoopId(), getLoopDependentLevel(), getLoopDependentLevelType(), and isSparseLvlWithNonTrivialIdxExp().

◆ isOutTensor()

constexpr bool mlir::sparse_tensor::Merger::isOutTensor	(	TensorLoopId	b,
		LoopId	i
	)		const

inlineconstexpr

Returns true if b is the ith loop of the output tensor.

Definition at line 357 of file Merger.h.

References makeTensorLoopId().

◆ isSingleCondition()

bool mlir::sparse_tensor::Merger::isSingleCondition	(	TensorId	t,
		ExprId	e
	)		const

Returns true if given tensor iterates only in the given tensor expression.

For the output tensor, this defines a "simply dynamic" operation [Bik96]. For instance: a(i) *= 2.0 or a(i) += a(i) for sparse vector a.

Definition at line 576 of file Merger.cpp.

Referenced by mlir::sparse_tensor::CodegenEnv::isAdmissibleTensorExp().

◆ isSparseLvlWithNonTrivialIdxExp()

bool mlir::sparse_tensor::Merger::isSparseLvlWithNonTrivialIdxExp ( TensorLoopId b ) const

inline

Checks whether the TensorLoopId represents a sparse tensor level contains non-trivial index expression.

Definition at line 509 of file Merger.h.

References getLoopDependentLevelType(), mlir::sparse_tensor::is2OutOf4LT(), mlir::sparse_tensor::isCompressedLT(), mlir::sparse_tensor::isLooseCompressedLT(), isLvlWithNonTrivialIdxExp(), and mlir::sparse_tensor::isSingletonLT().

Referenced by hasSparseIdxReduction(), and simplifyCond().

◆ lat()

const LatPoint& mlir::sparse_tensor::Merger::lat ( LatPointId p ) const

inline

Definition at line 545 of file Merger.h.

Referenced by dumpLat(), foreachTensorLoopId(), mlir::sparse_tensor::CodegenEnv::lat(), and latGT().

◆ latGT()

bool mlir::sparse_tensor::Merger::latGT	(	LatPointId	p0,
		LatPointId	p1
	)		const

Returns true if p0 > p1.

Definition at line 502 of file Merger.cpp.

References mlir::sparse_tensor::LatPoint::bits, and lat().

Referenced by genStmt(), optimizeSet(), and simplifyCond().

◆ loop()

constexpr LoopId mlir::sparse_tensor::Merger::loop ( TensorLoopId b ) const

inlineconstexpr

Gets the loop-identifier of the TensorLoopId.

Definition at line 347 of file Merger.h.

Referenced by dumpBits(), genIf(), getLoopDependentLevel(), getLoopDependentLevelType(), getLvl(), getLvlType(), isLvlWithNonTrivialIdxExp(), and startLoopSeq().

◆ makeLoopId()

constexpr LoopId mlir::sparse_tensor::Merger::makeLoopId ( unsigned i ) const

inlineconstexpr

Safely converts the argument to a loop identifier.

Definition at line 248 of file Merger.h.

Referenced by findAffine(), findDepIdxSet(), and mlir::sparse_tensor::CodegenEnv::makeLoopId().

◆ makeTensorId()

constexpr TensorId mlir::sparse_tensor::Merger::makeTensorId ( unsigned t ) const

inlineconstexpr

Safely converts the argument to a tensor identifier.

Definition at line 242 of file Merger.h.

Referenced by mlir::sparse_tensor::CodegenEnv::makeTensorId().

◆ makeTensorLoopId()

constexpr TensorLoopId mlir::sparse_tensor::Merger::makeTensorLoopId	(	unsigned	t,
		unsigned	i
	)		const

inlineconstexpr

Safely converts the arguments to a pair of (tensor,loop) identifiers.

Definition at line 254 of file Merger.h.

Referenced by addLat(), isOutTensor(), and mlir::sparse_tensor::CodegenEnv::makeTensorLoopId().

◆ mapBinWithSynZeroSet()

LatSetId mlir::sparse_tensor::Merger::mapBinWithSynZeroSet	(	ExprId	e,
		LatSetId	s,
		bool	lhsZero
	)

Maps the binary operator to the same operation but with one of its operand set to zero, i.e.

each lattice point on an expression E is simply copied over, but with OP 0 E (if lhsZero == true) or OP E 0 (if lhsZero == false) as new expression. Returns the identifier of the new set.

Definition at line 412 of file Merger.cpp.

◆ mapSet()

LatSetId mlir::sparse_tensor::Merger::mapSet	(	TensorExp::Kind	kind,
		LatSetId	s,
		Value	v = `Value()`,
		Operation *	op = `nullptr`
	)

Maps the unary operator over the lattice set of the operand, i.e.

each lattice point on an expression E is simply copied over, but with OP E as new expression. Returns the identifier of the new set.

Definition at line 399 of file Merger.cpp.

Referenced by combiSet().

◆ onlyDenseDiff()

bool mlir::sparse_tensor::Merger::onlyDenseDiff	(	LatPointId	p0,
		LatPointId	p1
	)		const

Returns true if p0 and p1 only differ in dense.

Definition at line 515 of file Merger.cpp.

References hasAnySparse().

Referenced by optimizeSet().

◆ optimizeSet()

LatSetId mlir::sparse_tensor::Merger::optimizeSet ( LatSetId s )

Optimizes the iteration lattice points in the given set.

This method should be called right before code generation to avoid generating redundant loops and conditions.

Definition at line 429 of file Merger.cpp.

References addSet(), exp(), expIsTensor(), latGT(), onlyDenseDiff(), set(), and simplifyCond().

Referenced by genStmt().

◆ set()

ArrayRef<LatPointId> mlir::sparse_tensor::Merger::set ( LatSetId s ) const

inline

Definition at line 549 of file Merger.h.

Referenced by dumpSet(), optimizeSet(), mlir::sparse_tensor::CodegenEnv::set(), and simplifyCond().

◆ setExprValue()

void mlir::sparse_tensor::Merger::setExprValue	(	ExprId	e,
		Value	v
	)

inline

Sets the expression to have the associated value.

Asserts that the new value is defined, and that the expression does not already have a value.

Definition at line 559 of file Merger.h.

References exp().

Referenced by mlir::sparse_tensor::CodegenEnv::startReduc(), and mlir::sparse_tensor::CodegenEnv::updateReduc().

◆ setHasSparseOut()

void mlir::sparse_tensor::Merger::setHasSparseOut ( bool s )

inline

Sets whether the output tensor is sparse or not.

Definition at line 468 of file Merger.h.

Referenced by mlir::sparse_tensor::CodegenEnv::startEmit().

◆ setLevelAndType()

void mlir::sparse_tensor::Merger::setLevelAndType	(	TensorId	t,
		LoopId	i,
		Level	lvl,
		LevelType	lt
	)

inline

Sets the level number and level-type of the tth tensor on ith loop.

Definition at line 425 of file Merger.h.

References mlir::sparse_tensor::isValidLT().

Referenced by findAffine(), and findDepIdxSet().

◆ setLoopDependentTensorLevel()

void mlir::sparse_tensor::Merger::setLoopDependentTensorLevel	(	LoopId	i,
		TensorId	t,
		Level	lvl,
		LevelType	lt,
		unsigned	coefficient
	)

inline

Establishes the two-way map that i <-> <t, lvl, lt>.

Definition at line 471 of file Merger.h.

Referenced by findDepIdxSet().

◆ simplifyCond()

BitVector mlir::sparse_tensor::Merger::simplifyCond	(	LatSetId	s,
		LatPointId	p
	)

Simplifies the conditions in a conjunction of a given lattice point within the given set using just two basic rules: (1) multiple dense conditions are reduced to single dense, and (2) a singleton sparse/dense is reduced to sparse/random access.

Definition at line 459 of file Merger.cpp.

References getLvlType(), hasAnySparse(), mlir::sparse_tensor::is2OutOf4LT(), mlir::sparse_tensor::isCompressedLT(), mlir::sparse_tensor::isDenseLT(), mlir::sparse_tensor::isLooseCompressedLT(), mlir::sparse_tensor::isSingletonLT(), isSparseLvlWithNonTrivialIdxExp(), latGT(), and set().

Referenced by optimizeSet().

◆ tensor()

constexpr TensorId mlir::sparse_tensor::Merger::tensor ( TensorLoopId b ) const

inlineconstexpr

Gets the tensor-identifier of the TensorLoopId.

Definition at line 345 of file Merger.h.

Referenced by dumpBits(), foreachTensorLoopId(), getLoopDependentLevel(), getLoopDependentLevelType(), getLvl(), getLvlType(), and isLvlWithNonTrivialIdxExp().

The documentation for this class was generated from the following files:

include/mlir/Dialect/SparseTensor/Utils/Merger.h
lib/Dialect/SparseTensor/Utils/Merger.cpp

Public Types

Public Member Functions

Detailed Description

Member Typedef Documentation

◆ ForeachTensorLoopIdCallback

Constructor & Destructor Documentation

◆ Merger()

Member Function Documentation

◆ addExp() [1/2]

◆ addExp() [2/2]

◆ addInvariantExp()

◆ addLat() [1/2]

◆ addLat() [2/2]

◆ addLoopVarExp()

◆ addSet()

◆ addSynZeroExp()

◆ addTensorExp()

◆ buildExp()

◆ buildLattices()

◆ buildTensorExpFromLinalg()

◆ clearExprValue()

◆ combiSet()

◆ conjLat()

◆ conjSet()

◆ disjSet()

◆ disjSetWithZero()

◆ dumpBits()

◆ dumpExp()

◆ dumpLat()

◆ dumpSet()

◆ exp()

◆ expContainsTensor()

◆ expIsTensor()

◆ foreachTensorLoopId() [1/2]

◆ foreachTensorLoopId() [2/2]

◆ getDependentLoops()

◆ getLoopDefiningLvl()

◆ getLoopDependentLevel()

◆ getLoopDependentLevelType()

◆ getLoopId()

◆ getLvl() [1/2]

◆ getLvl() [2/2]

◆ getLvlType() [1/2]

◆ getLvlType() [2/2]

◆ getNumLoops()

◆ getNumTensors()

◆ getOutTensorID()

◆ getSynTensorID()

◆ hasAnySparse()

◆ hasDependentLvl()

◆ hasExprValue()

◆ hasNegateOnOut()

◆ hasSparseIdxReduction()

◆ isLvlWithNonTrivialIdxExp()

◆ isOutTensor()

◆ isSingleCondition()

◆ isSparseLvlWithNonTrivialIdxExp()

◆ lat()

◆ latGT()

◆ loop()

◆ makeLoopId()

◆ makeTensorId()

◆ makeTensorLoopId()

◆ mapBinWithSynZeroSet()

◆ mapSet()

◆ onlyDenseDiff()

◆ optimizeSet()

◆ set()

◆ setExprValue()

◆ setHasSparseOut()

◆ setLevelAndType()

◆ setLoopDependentTensorLevel()

◆ simplifyCond()

◆ tensor()