MLIR  15.0.0git
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 Member Functions

 Merger (unsigned t, unsigned l)
 Constructs a merger for the given number of tensors and loops. More...
 
unsigned addExp (Kind k, unsigned e0, unsigned e1=-1u, Value v=Value(), Operation *op=nullptr)
 Adds a tensor expression. Returns its index. More...
 
unsigned addExp (Kind k, unsigned e, Value v, Operation *op=nullptr)
 
unsigned addExp (Kind k, Value v, Operation *op=nullptr)
 
unsigned addLat (unsigned t, unsigned i, unsigned e)
 Adds an iteration lattice point. Returns its index. More...
 
unsigned addSet ()
 Adds a new, initially empty, set. Returns its index. More...
 
unsigned conjLatPoint (Kind kind, unsigned p0, unsigned p1, Operation *op=nullptr)
 Computes a single conjunction of two lattice points by taking the "union" of loop indices (effectively constructing a larger "intersection" of those indices) with a newly constructed tensor (sub)expression of given kind. More...
 
unsigned takeConj (Kind kind, unsigned s0, unsigned s1, Operation *op=nullptr)
 Conjunctive merge of two lattice sets L0 and L1 is conjunction of cartesian product. More...
 
unsigned takeDisj (Kind kind, unsigned s0, unsigned s1, Operation *op=nullptr)
 Disjunctive merge of two lattice sets L0 and L1 is (L0 /_op L1, L0, L1). More...
 
unsigned takeCombi (Kind kind, unsigned s0, unsigned s1, Operation *orig, bool includeLeft, Kind ltrans, Operation *opleft, bool includeRight, Kind rtrans, Operation *opright)
 Disjunctive merge of two lattice sets L0 and L1 with custom handling of the overlap, left, and right regions. More...
 
unsigned mapSet (Kind kind, unsigned s0, Value v=Value(), Operation *op=nullptr)
 Maps the unary operator over the lattice set of the operand, i.e. More...
 
unsigned optimizeSet (unsigned s0)
 Optimizes the iteration lattice points in the given set. More...
 
BitVector simplifyCond (unsigned s0, unsigned p0)
 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 (unsigned i, unsigned j) const
 Returns true if Li > Lj. More...
 
bool onlyDenseDiff (unsigned i, unsigned j)
 Returns true if Li and Lj only differ in dense. More...
 
unsigned tensor (unsigned b) const
 Bit translation. More...
 
unsigned index (unsigned b) const
 
bool isDim (unsigned b, Dim d) const
 Returns true if bit corresponds to queried dim. More...
 
bool isOutTensor (unsigned b, unsigned i) const
 Returns true if bit corresponds to index of output tensor. More...
 
bool isDim (unsigned t, unsigned i, Dim d) const
 Returns true if tensor access at given index has queried dim. More...
 
bool hasAnyDimOf (const BitVector &bits, Dim d) const
 Returns true if any set bit corresponds to queried dim. More...
 
bool isSingleCondition (unsigned t, unsigned e) const
 Returns true if given tensor iterates only in the given tensor expression. More...
 
void setDim (unsigned t, unsigned i, Dim d)
 Dimension setter. More...
 
void setHasSparseOut (bool s)
 
TensorExpexp (unsigned e)
 Convenience getters to immediately access the stored nodes. More...
 
LatPointlat (unsigned l)
 
SmallVector< unsigned, 16 > & set (unsigned s)
 
void dumpExp (unsigned e) const
 Print methods (for debugging). More...
 
void dumpLat (unsigned p) const
 
void dumpSet (unsigned s) const
 
void dumpBits (const BitVector &bits) const
 
unsigned buildLattices (unsigned e, unsigned i)
 Builds the iteration lattices in a bottom-up traversal given the remaining tensor (sub)expression and the next loop index in the iteration graph. More...
 
Optional< unsignedbuildTensorExpFromLinalg (linalg::GenericOp op)
 Builds a tensor expression from the given Linalg operation. More...
 
Value buildExp (RewriterBase &rewriter, Location loc, unsigned e, Value v0, Value v1)
 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 145 of file Merger.h.

Constructor & Destructor Documentation

◆ Merger()

mlir::sparse_tensor::Merger::Merger ( unsigned  t,
unsigned  l 
)
inline

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.

Definition at line 152 of file Merger.h.

References mlir::sparse_tensor::Children::e0, and mlir::sparse_tensor::Children::e1.

Member Function Documentation

◆ addExp() [1/3]

unsigned mlir::sparse_tensor::Merger::addExp ( Kind  k,
unsigned  e0,
unsigned  e1 = -1u,
Value  v = Value(),
Operation op = nullptr 
)

Adds a tensor expression. Returns its index.

Definition at line 111 of file Merger.cpp.

◆ addExp() [2/3]

unsigned mlir::sparse_tensor::Merger::addExp ( Kind  k,
unsigned  e,
Value  v,
Operation op = nullptr 
)
inline

Definition at line 159 of file Merger.h.

◆ addExp() [3/3]

unsigned mlir::sparse_tensor::Merger::addExp ( Kind  k,
Value  v,
Operation op = nullptr 
)
inline

Definition at line 162 of file Merger.h.

◆ addLat()

unsigned mlir::sparse_tensor::Merger::addLat ( unsigned  t,
unsigned  i,
unsigned  e 
)

Adds an iteration lattice point. Returns its index.

Definition at line 118 of file Merger.cpp.

References mlir::sparse_tensor::LatPoint::LatPoint().

◆ addSet()

unsigned mlir::sparse_tensor::Merger::addSet ( )

Adds a new, initially empty, set. Returns its index.

Definition at line 125 of file Merger.cpp.

◆ buildExp()

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

Rebuilds SSA format from a tensor expression.

Definition at line 934 of file Merger.cpp.

Referenced by genExp().

◆ buildLattices()

unsigned mlir::sparse_tensor::Merger::buildLattices ( unsigned  e,
unsigned  i 
)

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

Returns index of the root expression.

Definition at line 530 of file Merger.cpp.

◆ buildTensorExpFromLinalg()

Optional< unsigned > mlir::sparse_tensor::Merger::buildTensorExpFromLinalg ( linalg::GenericOp  op)

Builds a tensor expression from the given Linalg operation.

Returns index of the root expression on success.

Definition at line 713 of file Merger.cpp.

References mlir::Operation::getOperand().

◆ conjLatPoint()

unsigned mlir::sparse_tensor::Merger::conjLatPoint ( Kind  kind,
unsigned  p0,
unsigned  p1,
Operation op = nullptr 
)

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

Returns the index of the new lattice point.

Definition at line 131 of file Merger.cpp.

◆ dumpBits()

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

◆ dumpExp()

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

Print methods (for debugging).

Definition at line 433 of file Merger.cpp.

◆ dumpLat()

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

◆ dumpSet()

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

Definition at line 491 of file Merger.cpp.

◆ exp()

TensorExp& mlir::sparse_tensor::Merger::exp ( unsigned  e)
inline

Convenience getters to immediately access the stored nodes.

Typically it is inadvisible to keep the reference around, as in "TensorExpr &te = merger.exp(e))", since insertions into the merger may cause data movement and invalidate the underlying memory address.

Definition at line 256 of file Merger.h.

Referenced by genExp(), genIndexValue(), genInvariants(), genInvariantValue(), genTensorLoad(), and updateReduc().

◆ hasAnyDimOf()

bool mlir::sparse_tensor::Merger::hasAnyDimOf ( const BitVector &  bits,
Dim  d 
) const

Returns true if any set bit corresponds to queried dim.

Definition at line 271 of file Merger.cpp.

Referenced by startLoopSeq().

◆ index()

unsigned mlir::sparse_tensor::Merger::index ( unsigned  b) const
inline

Definition at line 221 of file Merger.h.

Referenced by genFor(), genIf(), genInit(), genLocals(), genWhile(), and genWhileInduction().

◆ isDim() [1/2]

bool mlir::sparse_tensor::Merger::isDim ( unsigned  b,
Dim  d 
) const
inline

Returns true if bit corresponds to queried dim.

Definition at line 224 of file Merger.h.

References isDim().

Referenced by computeIterationGraph(), findAffine(), genBuffers(), genFor(), genIf(), genInit(), genLocals(), genWhile(), genWhileInduction(), and isDim().

◆ isDim() [2/2]

bool mlir::sparse_tensor::Merger::isDim ( unsigned  t,
unsigned  i,
Dim  d 
) const
inline

Returns true if tensor access at given index has queried dim.

Definition at line 232 of file Merger.h.

◆ isOutTensor()

bool mlir::sparse_tensor::Merger::isOutTensor ( unsigned  b,
unsigned  i 
) const
inline

Returns true if bit corresponds to index of output tensor.

Definition at line 227 of file Merger.h.

Referenced by genLocals().

◆ isSingleCondition()

bool mlir::sparse_tensor::Merger::isSingleCondition ( unsigned  t,
unsigned  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 278 of file Merger.cpp.

◆ lat()

LatPoint& mlir::sparse_tensor::Merger::lat ( unsigned  l)
inline

Definition at line 257 of file Merger.h.

Referenced by endLoop(), startLoop(), and startLoopSeq().

◆ latGT()

bool mlir::sparse_tensor::Merger::latGT ( unsigned  i,
unsigned  j 
) const

Returns true if Li > Lj.

Definition at line 252 of file Merger.cpp.

◆ mapSet()

unsigned mlir::sparse_tensor::Merger::mapSet ( Kind  kind,
unsigned  s0,
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 index of the new set.

Definition at line 189 of file Merger.cpp.

◆ onlyDenseDiff()

bool mlir::sparse_tensor::Merger::onlyDenseDiff ( unsigned  i,
unsigned  j 
)

Returns true if Li and Lj only differ in dense.

Definition at line 265 of file Merger.cpp.

References mlir::sparse_tensor::kSparse.

◆ optimizeSet()

unsigned mlir::sparse_tensor::Merger::optimizeSet ( unsigned  s0)

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

◆ set()

SmallVector<unsigned, 16>& mlir::sparse_tensor::Merger::set ( unsigned  s)
inline

Definition at line 258 of file Merger.h.

Referenced by startLoopSeq().

◆ setDim()

void mlir::sparse_tensor::Merger::setDim ( unsigned  t,
unsigned  i,
Dim  d 
)
inline

Dimension setter.

Definition at line 247 of file Merger.h.

Referenced by findAffine().

◆ setHasSparseOut()

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

Definition at line 250 of file Merger.h.

◆ simplifyCond()

BitVector mlir::sparse_tensor::Merger::simplifyCond ( unsigned  s0,
unsigned  p0 
)

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

References mlir::sparse_tensor::kSparse, and mlir::sparse_tensor::LatPoint::simple.

◆ takeCombi()

unsigned mlir::sparse_tensor::Merger::takeCombi ( Kind  kind,
unsigned  s0,
unsigned  s1,
Operation orig,
bool  includeLeft,
Kind  ltrans,
Operation opleft,
bool  includeRight,
Kind  rtrans,
Operation opright 
)

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

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

Definition at line 168 of file Merger.cpp.

◆ takeConj()

unsigned mlir::sparse_tensor::Merger::takeConj ( Kind  kind,
unsigned  s0,
unsigned  s1,
Operation op = nullptr 
)

Conjunctive merge of two lattice sets L0 and L1 is conjunction of cartesian product.

Returns the index of the new set.

Definition at line 141 of file Merger.cpp.

◆ takeDisj()

unsigned mlir::sparse_tensor::Merger::takeDisj ( Kind  kind,
unsigned  s0,
unsigned  s1,
Operation op = nullptr 
)

Disjunctive merge of two lattice sets L0 and L1 is (L0 /_op L1, L0, L1).

Returns the index of the new set.

Definition at line 149 of file Merger.cpp.

◆ tensor()

unsigned mlir::sparse_tensor::Merger::tensor ( unsigned  b) const
inline

Bit translation.

Definition at line 220 of file Merger.h.

Referenced by genFor(), genIf(), genInit(), genLocals(), genWhile(), and genWhileInduction().


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