MLIR
18.0.0git
|
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... | |
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.
using mlir::sparse_tensor::Merger::ForeachTensorLoopIdCallback = function_ref<void( TensorLoopId, TensorId, std::optional<Level>, LevelType, bool)> |
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.
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.
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.
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.
LatPointId mlir::sparse_tensor::Merger::addLat | ( | const BitVector & | bits, |
ExprId | e | ||
) |
Definition at line 300 of file Merger.cpp.
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().
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.
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().
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.
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.
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.
References mlir::sparse_tensor::buildBinaryOverlap(), 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::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().
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().
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().
|
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().
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.
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.
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().
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.
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().
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().
void mlir::sparse_tensor::Merger::dumpExp | ( | ExprId | e | ) | const |
Print methods (for debugging).
Definition at line 796 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::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().
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().
void mlir::sparse_tensor::Merger::dumpSet | ( | LatSetId | s | ) | const |
Definition at line 906 of file Merger.cpp.
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().
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().
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().
|
inline |
Definition at line 447 of file Merger.h.
References getLoopDependentLevel(), getLvl(), getLvlType(), isLvlWithNonTrivialIdxExp(), lat(), and tensor().
|
inline |
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.
Definition at line 441 of file Merger.h.
Referenced by genIf(), startLoopSeq(), and translateBitsToTidLvlPairs().
|
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().
|
inline |
Definition at line 518 of file Merger.h.
References isLvlWithNonTrivialIdxExp(), loop(), and tensor().
Referenced by foreachTensorLoopId().
|
inline |
Definition at line 523 of file Merger.h.
References isLvlWithNonTrivialIdxExp(), loop(), and tensor().
Referenced by isSparseLvlWithNonTrivialIdxExp().
Gets the level number of the the t
th tensor on i
th loop.
Definition at line 415 of file Merger.h.
Referenced by foreachTensorLoopId(), getLvl(), and translateBitsToTidLvlPairs().
|
inline |
Gets the level-type of the t
th tensor on i
th loop.
Definition at line 398 of file Merger.h.
Referenced by findAffine(), findDepIdxSet(), foreachTensorLoopId(), getLvlType(), hasAnySparse(), mlir::sparse_tensor::CodegenEnv::lt(), and simplifyCond().
|
inline |
Gets the level-type of the TensorLoopId.
Definition at line 404 of file Merger.h.
References getLvlType(), loop(), and tensor().
|
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().
|
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().
|
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().
|
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().
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().
Whether the loop has dependent slice.
Definition at line 480 of file Merger.h.
Referenced by findDepIdxSet().
|
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.
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().
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().
|
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().
|
inlineconstexpr |
Returns true if b
is the i
th loop of the output tensor.
Definition at line 357 of file Merger.h.
References makeTensorLoopId().
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.
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::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().
|
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().
|
inline |
Definition at line 545 of file Merger.h.
Referenced by dumpLat(), foreachTensorLoopId(), mlir::sparse_tensor::CodegenEnv::lat(), and 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().
|
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().
|
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().
|
inlineconstexpr |
Safely converts the argument to a tensor identifier.
Definition at line 242 of file Merger.h.
Referenced by mlir::sparse_tensor::CodegenEnv::makeTensorId().
|
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().
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.
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().
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().
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().
|
inline |
Definition at line 549 of file Merger.h.
Referenced by dumpSet(), optimizeSet(), mlir::sparse_tensor::CodegenEnv::set(), and simplifyCond().
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().
|
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().
|
inline |
Sets the level number and level-type of the t
th tensor on i
th loop.
Definition at line 425 of file Merger.h.
References mlir::sparse_tensor::isValidLT().
Referenced by findAffine(), and findDepIdxSet().
|
inline |
Establishes the two-way map that i <-> <t, lvl, lt>.
Definition at line 471 of file Merger.h.
Referenced by findDepIdxSet().
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().
|
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().