MLIR  19.0.0git
Public Types | Public Member Functions | List of all members
mlir::sparse_tensor::Merger Class Reference

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, Attribute attr=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 ith 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 tth tensor on ith loop. More...
 
LevelType getLvlType (TensorLoopId b) const
 Gets the level-type of the TensorLoopId. More...
 
std::optional< LoopIdgetLoopId (TensorId t, Level lvl) const
 Gets the loop identifier for the lvlth level of the tth tensor. More...
 
std::optional< LevelgetLvl (TensorId t, LoopId i) const
 Gets the level number of the the tth tensor on ith loop. More...
 
std::optional< LevelgetLvl (TensorLoopId b) const
 
void setLevelAndType (TensorId t, LoopId i, Level lvl, LevelType lt)
 Sets the level number and level-type of the tth tensor on ith loop. More...
 
void foreachTensorLoopId (LatPointId p, ForeachTensorLoopIdCallback callback) const
 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. 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, LevelgetLoopDefiningLvl (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 TensorExpexp (ExprId e) const
 Convenience getters to immediately access the stored nodes. More...
 
const LatPointlat (LatPointId p) const
 
ArrayRef< LatPointIdset (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< ExprIdbuildTensorExpFromLinalg (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 225 of file Merger.h.

Member Typedef Documentation

◆ ForeachTensorLoopIdCallback

Definition at line 435 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 224 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 285 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 277 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 263 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 302 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 293 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 255 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 309 of file Merger.cpp.

Referenced by optimizeSet().

◆ addSynZeroExp()

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

Constructs a new synthetic zero expression.

Definition at line 270 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 247 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 1618 of file Merger.cpp.

References mlir::sparse_tensor::buildBinaryOverlap(), mlir::sparse_tensor::buildRelu(), mlir::sparse_tensor::buildUnaryPresent(), mlir::OpBuilder::clone(), mlir::OpBuilder::create(), exp(), mlir::OpBuilder::getBlock(), mlir::Operation::getNumOperands(), mlir::Operation::getOperand(), mlir::Block::getParent(), mlir::Operation::getResult(), mlir::Value::getType(), mlir::Builder::getZeroAttr(), mlir::sparse_tensor::insertYieldOp(), mlir::sparse_tensor::TensorExp::kAbsC, mlir::sparse_tensor::TensorExp::kAbsF, mlir::sparse_tensor::TensorExp::kAbsI, mlir::sparse_tensor::TensorExp::kAddC, mlir::sparse_tensor::TensorExp::kAddF, mlir::sparse_tensor::TensorExp::kAddI, mlir::sparse_tensor::TensorExp::kAndI, mlir::sparse_tensor::TensorExp::kBinary, mlir::sparse_tensor::TensorExp::kBinaryBranch, mlir::sparse_tensor::TensorExp::kBitCast, mlir::sparse_tensor::TensorExp::kCastFS, mlir::sparse_tensor::TensorExp::kCastFU, mlir::sparse_tensor::TensorExp::kCastIdx, mlir::sparse_tensor::TensorExp::kCastS, mlir::sparse_tensor::TensorExp::kCastSF, mlir::sparse_tensor::TensorExp::kCastU, mlir::sparse_tensor::TensorExp::kCastUF, mlir::sparse_tensor::TensorExp::kCeilF, mlir::sparse_tensor::TensorExp::kCIm, mlir::sparse_tensor::TensorExp::kCmpF, mlir::sparse_tensor::TensorExp::kCmpI, mlir::sparse_tensor::TensorExp::kCRe, mlir::sparse_tensor::TensorExp::kDenseOp, mlir::sparse_tensor::TensorExp::kDivC, mlir::sparse_tensor::TensorExp::kDivF, mlir::sparse_tensor::TensorExp::kDivS, mlir::sparse_tensor::TensorExp::kDivU, mlir::sparse_tensor::TensorExp::kExpm1C, mlir::sparse_tensor::TensorExp::kExpm1F, mlir::sparse_tensor::TensorExp::kExtF, mlir::sparse_tensor::TensorExp::kFloorF, mlir::sparse_tensor::TensorExp::kInvariant, mlir::sparse_tensor::TensorExp::kLog1pC, mlir::sparse_tensor::TensorExp::kLog1pF, mlir::sparse_tensor::TensorExp::kLoopVar, mlir::sparse_tensor::TensorExp::kMulC, mlir::sparse_tensor::TensorExp::kMulF, mlir::sparse_tensor::TensorExp::kMulI, mlir::sparse_tensor::TensorExp::kNegC, mlir::sparse_tensor::TensorExp::kNegF, mlir::sparse_tensor::TensorExp::kNegI, mlir::sparse_tensor::TensorExp::kOrI, mlir::sparse_tensor::TensorExp::kReduce, mlir::sparse_tensor::TensorExp::kRelu, mlir::sparse_tensor::TensorExp::kSelect, mlir::sparse_tensor::TensorExp::kShlI, mlir::sparse_tensor::TensorExp::kShrS, mlir::sparse_tensor::TensorExp::kShrU, mlir::sparse_tensor::TensorExp::kSinC, mlir::sparse_tensor::TensorExp::kSinF, mlir::sparse_tensor::TensorExp::kSqrtC, mlir::sparse_tensor::TensorExp::kSqrtF, mlir::sparse_tensor::TensorExp::kSubC, mlir::sparse_tensor::TensorExp::kSubF, mlir::sparse_tensor::TensorExp::kSubI, mlir::sparse_tensor::TensorExp::kSynZero, mlir::sparse_tensor::TensorExp::kTanhC, mlir::sparse_tensor::TensorExp::kTanhF, mlir::sparse_tensor::TensorExp::kTensor, mlir::sparse_tensor::TensorExp::kTruncF, mlir::sparse_tensor::TensorExp::kTruncI, mlir::sparse_tensor::TensorExp::kUnary, mlir::sparse_tensor::TensorExp::kXorI, and mlir::IRMapping::map().

◆ 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 940 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 1193 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 380 of file Merger.cpp.

References mlir::sparse_tensor::TensorExp::attr, conjSet(), exp(), 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 315 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 329 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 338 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 356 of file Merger.cpp.

References exp().

◆ dumpBits()

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

Definition at line 920 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 799 of file Merger.cpp.

References exp(), mlir::sparse_tensor::TensorExp::kAbsC, mlir::sparse_tensor::TensorExp::kAbsF, mlir::sparse_tensor::TensorExp::kAbsI, mlir::sparse_tensor::TensorExp::kAddC, mlir::sparse_tensor::TensorExp::kAddF, mlir::sparse_tensor::TensorExp::kAddI, mlir::sparse_tensor::TensorExp::kAndI, mlir::sparse_tensor::TensorExp::kBinary, mlir::sparse_tensor::TensorExp::kBinaryBranch, mlir::sparse_tensor::TensorExp::kBitCast, mlir::sparse_tensor::TensorExp::kCastFS, mlir::sparse_tensor::TensorExp::kCastFU, mlir::sparse_tensor::TensorExp::kCastIdx, mlir::sparse_tensor::TensorExp::kCastS, mlir::sparse_tensor::TensorExp::kCastSF, mlir::sparse_tensor::TensorExp::kCastU, mlir::sparse_tensor::TensorExp::kCastUF, mlir::sparse_tensor::TensorExp::kCeilF, mlir::sparse_tensor::TensorExp::kCIm, mlir::sparse_tensor::TensorExp::kCmpF, mlir::sparse_tensor::TensorExp::kCmpI, mlir::sparse_tensor::TensorExp::kCRe, mlir::sparse_tensor::TensorExp::kDenseOp, mlir::sparse_tensor::TensorExp::kDivC, mlir::sparse_tensor::TensorExp::kDivF, mlir::sparse_tensor::TensorExp::kDivS, mlir::sparse_tensor::TensorExp::kDivU, mlir::sparse_tensor::TensorExp::kExpm1C, mlir::sparse_tensor::TensorExp::kExpm1F, mlir::sparse_tensor::TensorExp::kExtF, mlir::sparse_tensor::TensorExp::kFloorF, mlir::sparse_tensor::kindToOpSymbol(), mlir::sparse_tensor::detail::kInvalidId, mlir::sparse_tensor::TensorExp::kInvariant, mlir::sparse_tensor::TensorExp::kLog1pC, mlir::sparse_tensor::TensorExp::kLog1pF, mlir::sparse_tensor::TensorExp::kLoopVar, mlir::sparse_tensor::TensorExp::kMulC, mlir::sparse_tensor::TensorExp::kMulF, mlir::sparse_tensor::TensorExp::kMulI, mlir::sparse_tensor::TensorExp::kNegC, mlir::sparse_tensor::TensorExp::kNegF, mlir::sparse_tensor::TensorExp::kNegI, mlir::sparse_tensor::TensorExp::kOrI, mlir::sparse_tensor::TensorExp::kReduce, mlir::sparse_tensor::TensorExp::kRelu, mlir::sparse_tensor::TensorExp::kSelect, mlir::sparse_tensor::TensorExp::kShlI, mlir::sparse_tensor::TensorExp::kShrS, mlir::sparse_tensor::TensorExp::kShrU, mlir::sparse_tensor::TensorExp::kSinC, mlir::sparse_tensor::TensorExp::kSinF, mlir::sparse_tensor::TensorExp::kSqrtC, mlir::sparse_tensor::TensorExp::kSqrtF, mlir::sparse_tensor::TensorExp::kSubC, mlir::sparse_tensor::TensorExp::kSubF, mlir::sparse_tensor::TensorExp::kSubI, mlir::sparse_tensor::TensorExp::kSynZero, mlir::sparse_tensor::TensorExp::kTanhC, mlir::sparse_tensor::TensorExp::kTanhF, mlir::sparse_tensor::TensorExp::kTensor, mlir::sparse_tensor::TensorExp::kTruncF, mlir::sparse_tensor::TensorExp::kTruncI, mlir::sparse_tensor::TensorExp::kUnary, and mlir::sparse_tensor::TensorExp::kXorI.

Referenced by dumpLat().

◆ dumpLat()

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

Definition at line 899 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 910 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(), combiSet(), 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 522 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 370 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

◆ 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 442 of file Merger.h.

Referenced by genIf(), and getAllTidLvlsInLatPoints().

◆ 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 488 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 494 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 410 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 416 of file Merger.h.

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

◆ getLvl() [2/2]

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

Definition at line 420 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 399 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 405 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 355 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 352 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 363 of file Merger.h.

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

◆ 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 367 of file Merger.h.

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

◆ 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 671 of file Merger.cpp.

References getLvlType(), and hasSparseIdxReduction().

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 481 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

◆ 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 680 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 501 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 358 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 577 of file Merger.cpp.

References exp(), mlir::sparse_tensor::TensorExp::kAbsC, mlir::sparse_tensor::TensorExp::kAbsF, mlir::sparse_tensor::TensorExp::kAbsI, mlir::sparse_tensor::TensorExp::kAddC, mlir::sparse_tensor::TensorExp::kAddF, mlir::sparse_tensor::TensorExp::kAddI, mlir::sparse_tensor::TensorExp::kAndI, mlir::sparse_tensor::TensorExp::kBinary, mlir::sparse_tensor::TensorExp::kBinaryBranch, mlir::sparse_tensor::TensorExp::kBitCast, mlir::sparse_tensor::TensorExp::kCastFS, mlir::sparse_tensor::TensorExp::kCastFU, mlir::sparse_tensor::TensorExp::kCastIdx, mlir::sparse_tensor::TensorExp::kCastS, mlir::sparse_tensor::TensorExp::kCastSF, mlir::sparse_tensor::TensorExp::kCastU, mlir::sparse_tensor::TensorExp::kCastUF, mlir::sparse_tensor::TensorExp::kCeilF, mlir::sparse_tensor::TensorExp::kCIm, mlir::sparse_tensor::TensorExp::kCmpF, mlir::sparse_tensor::TensorExp::kCmpI, mlir::sparse_tensor::TensorExp::kCRe, mlir::sparse_tensor::TensorExp::kDenseOp, mlir::sparse_tensor::TensorExp::kDivC, mlir::sparse_tensor::TensorExp::kDivF, mlir::sparse_tensor::TensorExp::kDivS, mlir::sparse_tensor::TensorExp::kDivU, mlir::sparse_tensor::TensorExp::kExpm1C, mlir::sparse_tensor::TensorExp::kExpm1F, mlir::sparse_tensor::TensorExp::kExtF, mlir::sparse_tensor::TensorExp::kFloorF, mlir::sparse_tensor::TensorExp::kInvariant, mlir::sparse_tensor::TensorExp::kLog1pC, mlir::sparse_tensor::TensorExp::kLog1pF, mlir::sparse_tensor::TensorExp::kLoopVar, mlir::sparse_tensor::TensorExp::kMulC, mlir::sparse_tensor::TensorExp::kMulF, mlir::sparse_tensor::TensorExp::kMulI, mlir::sparse_tensor::TensorExp::kNegC, mlir::sparse_tensor::TensorExp::kNegF, mlir::sparse_tensor::TensorExp::kNegI, mlir::sparse_tensor::TensorExp::kOrI, mlir::sparse_tensor::TensorExp::kReduce, mlir::sparse_tensor::TensorExp::kRelu, mlir::sparse_tensor::TensorExp::kSelect, mlir::sparse_tensor::TensorExp::kShlI, mlir::sparse_tensor::TensorExp::kShrS, mlir::sparse_tensor::TensorExp::kShrU, mlir::sparse_tensor::TensorExp::kSinC, mlir::sparse_tensor::TensorExp::kSinF, mlir::sparse_tensor::TensorExp::kSqrtC, mlir::sparse_tensor::TensorExp::kSqrtF, mlir::sparse_tensor::TensorExp::kSubC, mlir::sparse_tensor::TensorExp::kSubF, mlir::sparse_tensor::TensorExp::kSubI, mlir::sparse_tensor::TensorExp::kSynZero, mlir::sparse_tensor::TensorExp::kTanhC, mlir::sparse_tensor::TensorExp::kTanhF, mlir::sparse_tensor::TensorExp::kTensor, mlir::sparse_tensor::TensorExp::kTruncF, mlir::sparse_tensor::TensorExp::kTruncI, mlir::sparse_tensor::TensorExp::kUnary, and mlir::sparse_tensor::TensorExp::kXorI.

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 510 of file Merger.h.

References getLoopDependentLevelType(), and isLvlWithNonTrivialIdxExp().

Referenced by hasSparseIdxReduction(), and simplifyCond().

◆ lat()

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

◆ latGT()

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

Returns true if p0 > p1.

Definition at line 503 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 348 of file Merger.h.

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

◆ makeLoopId()

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

Safely converts the argument to a loop identifier.

Definition at line 249 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 243 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 255 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 414 of file Merger.cpp.

◆ mapSet()

LatSetId mlir::sparse_tensor::Merger::mapSet ( TensorExp::Kind  kind,
LatSetId  s,
Value  v = Value(),
Operation op = nullptr,
Attribute  attr = 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 401 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 516 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 431 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 469 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 426 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 472 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 461 of file Merger.cpp.

References getLvlType(), hasAnySparse(), 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 346 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: