Documentation Listing

bandmask

A mask for a banded tensor, bandmask[i, j, k] = j <= i <= k. Note that this specializes each column for the cases where i < j, j <= i <= k, and k < i.

diagmask

A mask for a diagonal tensor, diagmask[i, j] = i == j. Note that this specializes each column for the cases where i < j, i == j, and i > j. For a diagonal with offset k, use diagmask[i, j - k].

lotrimask

A mask for a lower triangular tensor, lotrimask[i, j] = i >= j. Note that this specializes each column for the cases where i < j and i >= j. For a lower triangle with offset k, use lotrimask[i, j - k].

paircarrymask

A mask for carrying partial pair sums, paircarrymask[i, j] = 2j <= i <= 2j + 1. The first row is false. Each column specializes the interval containing its two true entries.

pairsummask

A mask for summing adjacent pairs, pairsummask[i, j] = 2i - 1 <= j <= 2i. Each column contains a single true entry at i = cld(j, 2).

uptrimask

A mask for an upper triangular tensor, uptrimask[i, j] = i <= j. Note that this specializes each column for the cases where i <= j and i > j. For an upper triangle with offset k, use uptrimask[i, j - k].

Array(arr::Union{Tensor, SwizzleArray})

Construct an array from a tensor or swizzle. May reuse memory, will usually densify the tensor.

AbstractDevice

A datatype representing a device on which tasks can be executed.

AbstractTask

An individual processing unit on a device, responsible for running code.

AtomicElementLevel{Vf, [Tv=typeof(Vf)], [Tp=Int], [Val]}()

Like an ElementLevel, but updates to the level are performed atomically.

julia> tensor_tree(Tensor(Dense(AtomicElement(0.0)), [1, 2, 3]))
3-Tensor
└─ Dense [1:3]
   ├─ [1]: 1.0
   ├─ [2]: 2.0
   └─ [3]: 3.0

CPU(n)

A device that represents a CPU with n threads.

CoalesceLevel{device, Lvl}()

CoalesceLevel uses an internal Coalesced representation, but unified the result into a single Tensor when entering read-only mode.

julia> tensor_tree(Tensor(Dense(Coalesce(cpu(:t, 2), Element(0.0))), 4))
4-Tensor
└─ Dense [1:4]
   ├─ [1]: Coalesce(1) -> 
   ├─ [2]: Coalesce(2) -> 
   ├─ [3]: Coalesce(3) -> 
   └─ [4]: Coalesce(4) -> 

DenseData(lvl)

Represents a tensor A where each A[:, ..., :, i] is represented by lvl.

DenseLevel{[Ti=Int]}(lvl, [dim])

A subfiber of a dense level is an array which stores every slice A[:, ..., :, i] as a distinct subfiber in lvl. Optionally, dim is the size of the last dimension. Ti is the type of the indices used to index the level.

julia> ndims(Tensor(Dense(Element(0.0))))
1

julia> ndims(Tensor(Dense(Dense(Element(0.0)))))
2

julia> tensor_tree(Tensor(Dense(Dense(Element(0.0))), [1 2; 3 4]))
2×2-Tensor
└─ Dense [:,1:2]
   ├─ [:, 1]: Dense [1:2]
   │  ├─ [1]: 1.0
   │  └─ [2]: 3.0
   └─ [:, 2]: Dense [1:2]
      ├─ [1]: 2.0
      └─ [2]: 4.0

DeviceGlobal()

From the device, load the global view of the tensor.

DeviceLocal()

From the device, load the local version of the tensor.

DeviceShared()

From the device, load the shared view of the tensor.

ElementData(fill_value, eltype)

Represents a scalar element of type eltype and fillvalue `fillvalue`.

ElementLevel{Vf, [Tv=typeof(Vf)], [Tp=Int], [Val]}()

A subfiber of an element level is a scalar of type Tv, initialized to Vf. Vf may optionally be given as the first argument.

The data is stored in a vector of type Val with eltype(Val) = Tv. The type Tp is the index type used to access Val.

julia> tensor_tree(Tensor(Dense(Element(0.0)), [1, 2, 3]))
3-Tensor
└─ Dense [1:3]
   ├─ [1]: 1.0
   ├─ [2]: 2.0
   └─ [3]: 3.0

ExtrudeData(lvl)

Represents a tensor A where A[:, ..., :, 1] is the only slice, and is represented by lvl.

FinchCompiler

The core compiler for Finch, lowering canonicalized Finch IR to Julia code.

HollowData(lvl)

Represents a tensor which is represented by lvl but is sometimes entirely fill_value(lvl).

HostGlobal()

From the host, distribute the tensor to device global memory.

HostLocal()

From the host, distribute the tensor to device local memory.

HostShared()

From the host, distribute the tensor to device shared memory.

Infintesimal(s)

The Infintesimal type represents an infinitestimal number. The sign field is used to represent positive, negative, or zero in this number system.

```jl-doctest julia> tiny() +0

julia> positive_tiny() +ϵ

julia> negative_tiny() -ϵ

julia> positivetiny() + negativetiny() +0

julia> positive_tiny() * 2 +ϵ

julia> positivetiny() * negativetiny() -ϵ

InitMax{D}(x, y)

Returns max(x, y, D). Used to add an init parameter to a maximum operation.

InitMin{D}(x, y)

Returns min(x, y, D). Used to add an init parameter to a minimum operation.

JuliaContext

A context for compiling Julia code, managing side effects, parallelism, and variable names in the generated code of the executing environment.

Limit{T}(x, s)

The Limit type represents endpoints of closed and open intervals. The val field is the value of the endpoint. The sign field is used to represent the openness/closedness of the interval endpoint, using an Infinitesmal.

```jl-doctest julia> limit(1.0) 1.0+0

julia> plus_eps(1.0) 1.0+ϵ

julia> minus_eps(1.0) 1.0-ϵ

julia> pluseps(1.0) + minuseps(1.0) 2.0+0.0

julia> plus_eps(1.0) * 2 2.0+2.0ϵ

julia> pluseps(1.0) * minuseps(1.0) 1.0-1.0ϵ

julia> pluseps(-1.0) * minuseps(1.0) -1.0+2.0ϵ

julia> 1.0 < plus_eps(1.0) true

julia> 1.0 < minus_eps(1.0) false

MinusOneVector(data, [fields])

A vector whose entries are the entries of data minus one, e.g. to view 1-based indices as 0-based ones. When the entries are tuples, only the fields listed in fields are offset; by default, every field is.

MutexLevel{Val, Lvl}()

Mutex Level Protects the level directly below it with atomics

Each position in the level below the Mutex level is protected by a lock.

julia> tensor_tree(Tensor(Dense(Mutex(Element(0.0))), [1, 2, 3]))
3-Tensor
└─ Dense [1:3]
   ├─ [1]: Mutex ->
   │  └─ 1.0
   ├─ [2]: Mutex ->
   │  └─ 2.0
   └─ [3]: Mutex ->
      └─ 3.0

Namespace

A namespace for managing variable names and aesthetic fresh variable generation.

ParallelSparseDictLevel{[Ti=Int], [Tp=Int], [Ptr, Idx, Val, Tbl, Pool=Dict]}(lvl, [dim])

A subfiber of a sparse level does not need to represent slices A[:, ..., :, i] which are entirely fill_value. Instead, only potentially non-fill slices are stored as subfibers in lvl. A datastructure specified by Tbl is used to record which slices are stored. Optionally, dim is the size of the last dimension.

Ti is the type of the last fiber index, and Tp is the type used for positions in the level. The types Ptr and Idx are the types of the arrays used to store positions and indicies.

julia> tensor_tree(Tensor(Dense(SparseDict(Element(0.0))), [10 0 20; 30 0 0; 0 0 40]))
3×3-Tensor
└─ Dense [:,1:3]
   ├─ [:, 1]: SparseDict (0.0) [1:3]
   │  ├─ [1]: 10.0
   │  └─ [2]: 30.0
   ├─ [:, 2]: SparseDict (0.0) [1:3]
   └─ [:, 3]: SparseDict (0.0) [1:3]
      ├─ [1]: 20.0
      └─ [3]: 40.0

julia> tensor_tree(Tensor(SparseDict(SparseDict(Element(0.0))), [10 0 20; 30 0 0; 0 0 40]))
3×3-Tensor
└─ SparseDict (0.0) [:,1:3]
   ├─ [:, 1]: SparseDict (0.0) [1:3]
   │  ├─ [1]: 10.0
   │  └─ [2]: 30.0
   └─ [:, 3]: SparseDict (0.0) [1:3]
      ├─ [1]: 20.0
      └─ [3]: 40.0

PatternLevel{[Tp=Int]}()

A subfiber of a pattern level is the Boolean value true, but it's fill_value is false. PatternLevels are used to create tensors that represent which values are stored by other fibers. See pattern! for usage examples.

julia> tensor_tree(Tensor(Dense(Pattern()), 3))
3-Tensor
└─ Dense [1:3]
   ├─ [1]: true
   ├─ [2]: true
   └─ [3]: true

PlusOneVector(data, [fields])

A vector whose entries are the entries of data plus one, e.g. to view 0-based indices as 1-based ones. When the entries are tuples, only the fields listed in fields are offset; by default, every field is.

RepeatData(lvl)

Represents a tensor A where A[:, ..., :, i] is sometimes entirely fill_value(lvl) and is sometimes represented by repeated runs of lvl.

RunListLevel{[Ti=Int], [Ptr, Right]}(lvl, [dim], [merge = true])

The RunListLevel represent runs of equivalent slices A[:, ..., :, i]. A sorted list is used to record the right endpoint of each run. Optionally, dim is the size of the last dimension.

Ti is the type of the last tensor index, and Tp is the type used for positions in the level. The types Ptr and Right are the types of the arrays used to store positions and endpoints.

The merge keyword argument is used to specify whether the level should merge duplicate consecutive runs.

julia> tensor_tree(Tensor(Dense(RunListLevel(Element(0.0))), [10 0 20; 30 0 0; 0 0 40]))
3×3-Tensor
└─ Dense [:,1:3]
   ├─ [:, 1]: RunList (0.0) [1:3]
   │  ├─ [1:1]: 10.0
   │  ├─ [2:2]: 30.0
   │  └─ [3:3]: 0.0
   ├─ [:, 2]: RunList (0.0) [1:3]
   │  └─ [1:3]: 0.0
   └─ [:, 3]: RunList (0.0) [1:3]
      ├─ [1:1]: 20.0
      ├─ [2:2]: 0.0
      └─ [3:3]: 40.0

ScopeContext

A context for managing variable bindings and tensor modes.

SeparateLevel{Lvl, [Val]}()

A subfiber of a Separate level is a separate tensor of type Lvl, in it's own memory space.

Each sublevel is stored in a vector of type Val with eltype(Val) = Lvl.

julia> tensor_tree(Tensor(Dense(Separate(Element(0.0))), [1, 2, 3]))
3-Tensor
└─ Dense [1:3]
   ├─ [1]: Pointer ->
   │  └─ 1.0
   ├─ [2]: Pointer ->
   │  └─ 2.0
   └─ [3]: Pointer ->
      └─ 3.0

Serial()

A device that represents a serial CPU execution.

SerialTask()

A Task that represents a serial CPU execution.

ShardLevel{Lvl}()

Each subfiber of a Shard level is stored in a thread-specific tensor of type Lvl, managed by MultiChannelMemory.

julia> tensor_tree(Tensor(Dense(Shard(cpu(1,2),Element(0.0))), 4))
4-Tensor
└─ Dense [1:4]
   ├─ [1]: shard(?) -> ?
   ├─ [2]: shard(?) -> ?
   ├─ [3]: shard(?) -> ?
   └─ [4]: shard(?) -> ?

SparseBandLevel{[Ti=Int], [Idx, Ofs]}(lvl, [dim])

Like the SparseBlockListLevel, but stores only a single block, and fills in zeros.

julia> tensor_tree(Tensor(Dense(SparseBand(Element(0.0))), [10 0 20; 30 40 0; 0 0 50]))
3×3-Tensor
└─ Dense [:,1:3]
   ├─ [:, 1]: SparseBand (0.0) [1:3]
   │  ├─ [1]: 10.0
   │  └─ [2]: 30.0
   ├─ [:, 2]: SparseBand (0.0) [1:3]
   │  └─ [2]: 40.0
   └─ [:, 3]: SparseBand (0.0) [1:3]
      ├─ [1]: 20.0
      ├─ [2]: 0.0
      └─ [3]: 50.0

SparseBlockListLevel{[Ti=Int], [Ptr, Idx, Ofs]}(lvl, [dim])

Like the SparseListLevel, but contiguous subfibers are stored together in blocks.

julia> tensor_tree(Tensor(Dense(SparseBlockList(Element(0.0))), [10 0 20; 30 0 0; 0 0 40]))
3×3-Tensor
└─ Dense [:,1:3]
   ├─ [:, 1]: SparseBlockList (0.0) [1:3]
   │  ├─ [1]: 10.0
   │  └─ [2]: 30.0
   ├─ [:, 2]: SparseBlockList (0.0) [1:3]
   └─ [:, 3]: SparseBlockList (0.0) [1:3]
      ├─ [1]: 20.0
      └─ [3]: 40.0

julia> tensor_tree(Tensor(SparseBlockList(SparseBlockList(Element(0.0))), [10 0 20; 30 0 0; 0 0 40]))
3×3-Tensor
└─ SparseBlockList (0.0) [:,1:3]
   ├─ [:, 1]: SparseBlockList (0.0) [1:3]
   │  ├─ [1]: 10.0
   │  └─ [2]: 30.0
   └─ [:, 3]: SparseBlockList (0.0) [1:3]
      ├─ [1]: 20.0
      └─ [3]: 40.0

SparseByteMapLevel{[Ti=Int], [Ptr, Tbl]}(lvl, [dims])

Like the SparseListLevel, but a dense bitmap is used to encode which slices are stored. This allows the ByteMap level to support random access.

Ti is the type of the last tensor index, and Tp is the type used for positions in the level.

julia> tensor_tree(Tensor(Dense(SparseByteMap(Element(0.0))), [10 0 20; 30 0 0; 0 0 40]))
3×3-Tensor
└─ Dense [:,1:3]
   ├─ [:, 1]: SparseByteMap (0.0) [1:3]
   │  ├─ [1]: 10.0
   │  └─ [2]: 30.0
   ├─ [:, 2]: SparseByteMap (0.0) [1:3]
   └─ [:, 3]: SparseByteMap (0.0) [1:3]
      ├─ [1]: 20.0
      └─ [3]: 40.0

julia> tensor_tree(Tensor(SparseByteMap(SparseByteMap(Element(0.0))), [10 0 20; 30 0 0; 0 0 40]))
3×3-Tensor
└─ SparseByteMap (0.0) [:,1:3]
   ├─ [:, 1]: SparseByteMap (0.0) [1:3]
   │  ├─ [1]: 10.0
   │  └─ [2]: 30.0
   └─ [:, 3]: SparseByteMap (0.0) [1:3]
      ├─ [1]: 20.0
      └─ [3]: 40.0

SparseCOOLevel{[N], [TI=Tuple{Int...}], [Ptr, Tbl]}(lvl, [dims])

A subfiber of a sparse level does not need to represent slices which are entirely fill_value. Instead, only potentially non-fill slices are stored as subfibers in lvl. The sparse coo level corresponds to N indices in the subfiber, so fibers in the sublevel are the slices A[:, ..., :, i_1, ..., i_n]. A set of N lists (one for each index) are used to record which slices are stored. The coordinates (sets of N indices) are sorted in column major order. Optionally, dims are the sizes of the last dimensions.

TI is the type of the last N tensor indices, and Tp is the type used for positions in the level.

The type Tbl is an NTuple type where each entry k is a subtype AbstractVector{TI[k]}.

The type Ptr is the type for the pointer array.

julia> tensor_tree(Tensor(Dense(SparseCOO{1}(Element(0.0))), [10 0 20; 30 0 0; 0 0 40]))
3×3-Tensor
└─ Dense [:,1:3]
   ├─ [:, 1]: SparseCOO{1} (0.0) [1:3]
   │  ├─ [1]: 10.0
   │  └─ [2]: 30.0
   ├─ [:, 2]: SparseCOO{1} (0.0) [1:3]
   └─ [:, 3]: SparseCOO{1} (0.0) [1:3]
      ├─ [1]: 20.0
      └─ [3]: 40.0

julia> tensor_tree(Tensor(SparseCOO{2}(Element(0.0)), [10 0 20; 30 0 0; 0 0 40]))
3×3-Tensor
└─ SparseCOO{2} (0.0) [:,1:3]
   ├─ [1, 1]: 10.0
   ├─ [2, 1]: 30.0
   ├─ [1, 3]: 20.0
   └─ [3, 3]: 40.0

SparseData(lvl)

Represents a tensor A where A[:, ..., :, i] is sometimes entirely fill_value(lvl) and is sometimes represented by lvl.

SparseDictLevel{[Ti=Int], [Tp=Int], [Ptr, Idx, Val, Tbl, Pool=Dict]}(lvl, [dim])

A subfiber of a sparse level does not need to represent slices A[:, ..., :, i] which are entirely fill_value. Instead, only potentially non-fill slices are stored as subfibers in lvl. A datastructure specified by Tbl is used to record which slices are stored. Optionally, dim is the size of the last dimension.

Ti is the type of the last fiber index, and Tp is the type used for positions in the level. The types Ptr and Idx are the types of the arrays used to store positions and indicies.

julia> tensor_tree(Tensor(Dense(SparseDict(Element(0.0))), [10 0 20; 30 0 0; 0 0 40]))
3×3-Tensor
└─ Dense [:,1:3]
   ├─ [:, 1]: SparseDict (0.0) [1:3]
   │  ├─ [1]: 10.0
   │  └─ [2]: 30.0
   ├─ [:, 2]: SparseDict (0.0) [1:3]
   └─ [:, 3]: SparseDict (0.0) [1:3]
      ├─ [1]: 20.0
      └─ [3]: 40.0

julia> tensor_tree(Tensor(SparseDict(SparseDict(Element(0.0))), [10 0 20; 30 0 0; 0 0 40]))
3×3-Tensor
└─ SparseDict (0.0) [:,1:3]
   ├─ [:, 1]: SparseDict (0.0) [1:3]
   │  ├─ [1]: 10.0
   │  └─ [2]: 30.0
   └─ [:, 3]: SparseDict (0.0) [1:3]
      ├─ [1]: 20.0
      └─ [3]: 40.0

SparseHashLevel{[Ti=Int]}(lvl, [dim], [subtables=1], [pos_multiplier])

A subfiber of a sparse level does not need to represent slices A[:, ..., :, i] which are entirely fill_value. Instead, only potentially non-fill slices are stored as subfibers in lvl. A hash table records which slices are stored. Optionally, dim is the size of the last dimension, and subtables, a power of two, splits the table into buckets that parallel merges fill independently.

pos_multiplier is an odd UInt stored with the table. It defaults to a shared random value. Preserve it alongside the buffers when serializing or reconstructing a level; shards and their merge destination must use the same multiplier.

Ti is the type of the last fiber index. Up to 127 overlapping logical writers can share a tentative entry within one task.

Implementation invariants:

• An entry is keyed by (p, i), a parent position and an index, and owns a stable child position q. Its record is key[q] == (p, i, state): 0x00 means free, 0x01:0x7f count pending writers, and 0x80 means retained. Exceeding 127 pending writers per entry throws an error.
• tbl_ctrl and tbl form a linear-probing table, split into subtables contiguous buckets. Every occupied slot, tentative or retained, has the high bit of tbl_ctrl[h] set, seven hash fingerprint bits below it, and tbl[h] == q. 0x00 marks an empty slot, which ends a probe. Probes wrap within their bucket.
• Keys hash as x = a * p + hash(i), where a = pos_multiplier is an odd multiplier stored in the level. The high log2(subtables) bits of x pick the bucket, as in multiply-shift hashing, so parents spread across buckets even when they share their low bits. Shifting parents by delta adds a * delta to x, which moves a bucket up by the high bits of a * delta, or by one more where the low bits carry. x is linear in p, and linear probing clusters on linear hashes of structured parents, so the rest comes from y = hash(x): its low seven bits are the fingerprint, and the bits above them pick the starting slot.
• tbl_count[b] counts the entries in bucket b, plus keys still pending during assembly, which grows the table before any bucket is more than half full. Frozen, tbl_count holds checkpoints every subtables ranks of perm: block j, tbl_count[(j - 1) * subtables .+ b], counts the entries in each bucket b of rank at least (j - 1) * subtables + 1. Block 1 is the bucket totals, and the last block is past the last rank. Counts from any rank are a checkpoint plus fewer than subtables entries. A merge's output holds only the totals.
• Frozen, length(key) is the extent of child positions, ptr[p]:(ptr[p + 1] - 1) indexes perm, and perm[r] is a child position. Each parent's range is sorted by index.
• While assembling, length(key) is the child capacity. Only positions through the allocated child extent are initialized. A new key gets its child position and is inserted tentatively before its child is written. The first dirty writer marks the child record retained; later writers cannot discard it. Otherwise, the last writer backward-shift deletes the table entry, marks the record free, and pushes its position onto a local free_head chain, storing the next link in the free record's parent field. Counts stay at stable child positions across growth and deletion; only final deletion needs a slot lookup.
• Rehash and freeze scan the child records directly, skipping free positions. Coalesce workers initialize holes in their own child ranges. Freeze trims free tails. Thaw rebuilds the free chain when the frozen level has interior holes.
• Declaration retains table capacity. It clears control bytes through the frozen permutation when occupancy is very low, or fills the control array otherwise.

julia> tensor_tree(Tensor(Dense(SparseHash(Element(0.0))), [10 0 20; 30 0 0; 0 0 40]))
3×3-Tensor
└─ Dense [:,1:3]
   ├─ [:, 1]: SparseHash (0.0) [1:3]
   │  ├─ [1]: 10.0
   │  └─ [2]: 30.0
   ├─ [:, 2]: SparseHash (0.0) [1:3]
   └─ [:, 3]: SparseHash (0.0) [1:3]
      ├─ [1]: 20.0
      └─ [3]: 40.0

julia> tensor_tree(Tensor(SparseHash(SparseHash(Element(0.0))), [10 0 20; 30 0 0; 0 0 40]))
3×3-Tensor
└─ SparseHash (0.0) [:,1:3]
   ├─ [:, 1]: SparseHash (0.0) [1:3]
   │  ├─ [1]: 10.0
   │  └─ [2]: 30.0
   └─ [:, 3]: SparseHash (0.0) [1:3]
      ├─ [1]: 20.0
      └─ [3]: 40.0

SparseIntervalLevel{[Ti=Int], [Left, Right]}(lvl, [dim])

The SparseIntervalLevel represent runs of equivalent slices A[:, ..., :, i] which are not entirely fill_value. A main difference compared to SparseRunList level is that SparseInterval level only stores a 'single' non-fill run. It emits an error if the program tries to write multiple (>=2) runs into SparseInterval.

Ti is the type of the last tensor index. The types Left, and 'Right' are the types of the arrays used to store positions and endpoints.

julia> tensor_tree(Tensor(SparseInterval(Element(0)), [0, 10, 0]))
3-Tensor
└─ SparseInterval (0) [1:3]
   └─ [2:2]: 10

julia> x = Tensor(SparseInterval(Element(0)), 10);

julia> @finch begin for i = extent(3,6); x[~i] = 1 end end;

julia> tensor_tree(x)
10-Tensor
└─ SparseInterval (0) [1:10]
   └─ [3:6]: 1

SparseListLevel{[Ti=Int], [Ptr, Idx]}(lvl, [dim])

A subfiber of a sparse level does not need to represent slices A[:, ..., :, i] which are entirely fill_value. Instead, only potentially non-fill slices are stored as subfibers in lvl. A sorted list is used to record which slices are stored. Optionally, dim is the size of the last dimension.

Ti is the type of the last tensor index, and Tp is the type used for positions in the level. The types Ptr and Idx are the types of the arrays used to store positions and indicies.

julia> tensor_tree(Tensor(Dense(SparseList(Element(0.0))), [10 0 20; 30 0 0; 0 0 40]))
3×3-Tensor
└─ Dense [:,1:3]
   ├─ [:, 1]: SparseList (0.0) [1:3]
   │  ├─ [1]: 10.0
   │  └─ [2]: 30.0
   ├─ [:, 2]: SparseList (0.0) [1:3]
   └─ [:, 3]: SparseList (0.0) [1:3]
      ├─ [1]: 20.0
      └─ [3]: 40.0

julia> tensor_tree(Tensor(SparseList(SparseList(Element(0.0))), [10 0 20; 30 0 0; 0 0 40]))
3×3-Tensor
└─ SparseList (0.0) [:,1:3]
   ├─ [:, 1]: SparseList (0.0) [1:3]
   │  ├─ [1]: 10.0
   │  └─ [2]: 30.0
   └─ [:, 3]: SparseList (0.0) [1:3]
      ├─ [1]: 20.0
      └─ [3]: 40.0

SparsePointLevel{[Ti=Int], [Idx]}(lvl, [dim])

A subfiber of a SparsePoint level does not need to represent slices A[:, ..., :, i] which are entirely fill_value. Instead, only potentially non-fill slices are stored as subfibers in lvl. A main difference compared to SparseList level is that SparsePoint level only stores a 'single' non-fill slice. It emits an error if the program tries to write multiple (>=2) coordinates into SparsePoint.

Ti is the type of the last tensor index. The types Ptr and Idx are the types of the arrays used to store positions and indicies.

julia> tensor_tree(Tensor(Dense(SparsePoint(Element(0.0))), [10 0 0; 0 20 0; 0 0 30]))
3×3-Tensor
└─ Dense [:,1:3]
   ├─ [:, 1]: SparsePoint (0.0) [1:3]
   │  └─ [1]: 10.0
   ├─ [:, 2]: SparsePoint (0.0) [1:3]
   │  └─ [2]: 20.0
   └─ [:, 3]: SparsePoint (0.0) [1:3]
      └─ [3]: 30.0

julia> tensor_tree(Tensor(SparsePoint(Dense(Element(0.0))), [0 0 0; 0 0 30; 0 0 30]))
3×3-Tensor
└─ SparsePoint (0.0) [:,1:3]
   └─ [:, 3]: Dense [1:3]
      ├─ [1]: 0.0
      ├─ [2]: 30.0
      └─ [3]: 30.0

SparseRunListLevel{[Ti=Int], [Ptr, Left, Right]}(lvl, [dim]; [merge = true])

The SparseRunListLevel represent runs of equivalent slices A[:, ..., :, i] which are not entirely fill_value. A sorted list is used to record the left and right endpoints of each run. Optionally, dim is the size of the last dimension.

Ti is the type of the last tensor index, and Tp is the type used for positions in the level. The types Ptr, Left, and Right are the types of the arrays used to store positions and endpoints.

The merge keyword argument is used to specify whether the level should merge duplicate consecutive runs.

julia> tensor_tree(Tensor(Dense(SparseRunListLevel(Element(0.0))), [10 0 20; 30 0 0; 0 0 40]))
3×3-Tensor
└─ Dense [:,1:3]
   ├─ [:, 1]: SparseRunList (0.0) [1:3]
   │  ├─ [1:1]: 10.0
   │  └─ [2:2]: 30.0
   ├─ [:, 2]: SparseRunList (0.0) [1:3]
   └─ [:, 3]: SparseRunList (0.0) [1:3]
      ├─ [1:1]: 20.0
      └─ [3:3]: 40.0

StaticHash

A hash function which is static, i.e. the hashes are the same when objects are hashed in the same order. The hash is used to memoize the results of simplification and proof rules.

SubFiber(lvl, pos)

SubFiber represents a tensor at position pos within lvl.

SymbolicContext

A compiler context for symbolic computation, defined on an algebra.

Tensor(lvl, arr)

Construct a Tensor and initialize it to the contents of arr. To explicitly copy into a tensor, use @ref[copyto!]

Tensor(lvl, [undef], dims...)

Construct a Tensor of size dims, and initialize to undef, potentially allocating memory. Here undef is the UndefInitializer singleton type. dims... may be a variable number of dimensions or a tuple of dimensions, but it must correspond to the number of dimensions in lvl.

Tensor(lvl)

Construct a Tensor using the tensor level storage lvl. No initialization of storage is performed, it is assumed that position 1 of lvl corresponds to a valid tensor, and lvl will be wrapped as-is. Call a different constructor to initialize the storage.

Tensor(tns::Tensor)

Copy tns into a new Tensor with the same format.

Tensor(arr, [init = zero(eltype(arr))])

Copy an array-like object arr into a corresponding, similar Tensor datastructure. Uses init as an initial value. May reuse memory when possible. To explicitly copy into a tensor, use @ref[copyto!].

Examples

julia> println(summary(Tensor(sparse([1 0; 0 1]))))
2×2 Tensor(Dense(SparseList(Element(0))))

julia> println(summary(Tensor(ones(3, 2, 4))))
3×2×4 Tensor(Dense(Dense(Dense(Element(0.0)))))

Tensor{Lvl} <: AbstractFiber{Lvl}

The multidimensional array type used by Finch. Tensor is a thin wrapper around the hierarchical level storage of type Lvl.

collect(tns::AbstractTensor)

Construct an array from a tensor or swizzle, densifying it as Array does.

copy(tns::AbstractTensor)

Construct a tensor with the same format and contents as tns, sharing no storage with it.

resize!(fbr, dims...)

Set the shape of fbr equal to dims. May reuse memory and render the original tensor unusable when modified.

transpose(arr::AbstractTensor)

Transpose a 2-dimensional tensor, returning a new tensor (equivalent to permutedims).

ByteMapFormat(N, z = 0.0, T = typeof(z))

A byte-map based format with a fill value of z.

COOFormat(N, z = 0.0, T = typeof(z))

An N-dimensional COO format with a fill value of z. COO stores a sparse tensor as a list of coordinates.

CSCFormat(z = 0.0, T = typeof(z))

A CSC format with a fill value of z. CSC stores a sparse matrix as a dense array of lists.

CSFFormat(N, z = 0.0, T = typeof(z))

An N-dimensional CSC format with a fill value of z. CSF supports random access in the rightmost index, and uses a tree structure to store the rest of the data.

DCSCFormat(z = 0.0, T = typeof(z))

A DCSC format with a fill value of z. DCSC stores a sparse matrix as a list of lists.

DCSFFormat(z = 0.0, T = typeof(z))

A DCSF format with a fill value of z. DCSF stores a sparse tensor as a list of lists of lists.

DenseFormat(N, z = 0.0, T = typeof(z))

A dense format with a fill value of z.

HashFormat(N, z = 0.0, T = typeof(z))

A hash-table based format with a fill value of z.

aquire_lock!(dev::AbstractDevice, val)

Lock the lock, val, on the device dev, waiting until it can acquire lock.

assemble_level!(ctx, lvl, pos, new_pos)

Assemble and positions pos+1:new_pos in lvl, assuming positions 1:pos were previously assembled.

bspread(::AbstractString) bspread(::HDF5.File) bspread(::NPYPath)

Read the Binsparse file into a Finch tensor.

The file version must have the same major and minor versions as BINSPARSE_VERSION and an equal or lower patch version.

Supported file extensions are:

• .bsp.h5: HDF5 file format (HDF5 must be loaded)
• .bspnpy: NumPy and JSON directory format (NPZ must be loaded)

The Binsparse spec is under development. Additionally, this function may not be fully conformant. Please file bug reports if you see anything amiss.

bspwrite(::AbstractString, tns)
bspwrite(::HDF5.File, tns)
bspwrite(::NPYPath, tns)

Write the Finch tensor to a file using Binsparse file format.

Supported file extensions are:

• .bsp.h5: HDF5 file format (HDF5 must be loaded)
• .bspnpy: NumPy and JSON directory format (NPZ must be loaded)

The alias keyword controls whether a predefined format name (e.g. "CSR") is used for the output. When alias=false, the output always uses a "custom" format. Otherwise (alias=true or alias=nothing), a predefined format name is used whenever one describes the tensor's layout.

choose(z)(a, b)

choose(z) is a function which returns whichever of a or b is not isequal to z. If neither are z, then return a. Useful for getting the first nonfill value in a sparse array.

julia> a = Tensor(SparseList(Element(0.0)), [0, 1.1, 0, 4.4, 0])
5 Tensor{SparseListLevel{Int64, Vector{Int64}, Vector{Int64}, ElementLevel{0.0, Float64, Int64, Vector{Float64}}}}:
 0.0
 1.1
 0.0
 4.4
 0.0

julia> x = Scalar(0.0); @finch for i=_; x[] <<choose(0.0)>>= a[i] end;

julia> x[]
1.1

chunkmask(n, b)

A mask to evenly divide n indices into regions of size b. If m = chunkmask(b, n), then m[i, j] = b * (j - 1) < i <= b * j. Note that this specializes for the cleanup case at the end of the range.

julia> chunkmask(10, 3)
10×4 Finch.ChunkMask{Int64}:
 1  0  0  0
 1  0  0  0
 1  0  0  0
 0  1  0  0
 0  1  0  0
 0  1  0  0
 0  0  1  0
 0  0  1  0
 0  0  1  0
 0  0  0  1

cld_nothrow(x, y)

Returns cld(x, y) normally, returns zero and issues a warning if y is zero.

coalesce_shards!(src, dst, P, max_pos, bands)

Merge the P shards of src into dst. Shards must be ordered and disjoint: everything shard p stores precedes, in outermost-first index order, everything shard p + 1 stores. The result is their concatenation. The only overlap is at a band boundary, where neighboring shards can both store the same parent entry; the earlier shard owns it, and both shards' children land under it. Dense blocks can overlap too, since every shard stores fill values outside its band, so values merge by copying only non-fill values into a destination of fill.

bands[tid] is the band (lb, ub) of index tuples shard tid holds, or bands is nothing if unknown. Bands keep each shard from copying the dense storage outside its band, so shards that both store an entry split its children.

Merging first plans storage. setup_coalesce!(lvl, max_pos, dst, P, splits, offsets, overlap) sizes dst and returns a plan saying where each shard's positions land, which local child position is shared (shared[p], or 0), its destination (shared_dst[p]), and whether shards' leaves can overlap below. Then, in parallel, the ranges in plan.init are initialized. After initialization finishes, coalesce_shard!(tid, plan, lvl, dst, runs, lb, ub) copies each shard in parallel. runs iterates ranges of lvl's own positions to copy, in the same terms as splits, and no run straddles two of a shard's ranges. The band starts within position lb[1] at index tuple lb[2] and stops within position ub[1] at ub[2]; a position below 1 bounds nothing. Each level copies its metadata and passes its child runs of child positions, and bounds at the children of its bounding entries: a dense level scales runs by its shape, cutting out the children outside the band, and a sparse level passes its entries' child positions. Every worker must reach every level, even with an empty shard: worker tid also inserts a hash's output buckets tid:P:B.

collapse_rep(tns)

Normalize a trait object to collapse subfiber information into the parent tensor.

collapsed(algebra, f, idx, ext, node)

Return collapsed expression with respect to f.

combinedim(ctx, a, b)

Combine the two dimensions a and b. To avoid ambiguity, only define one of

combinedim(ctx, ::A, ::B)
combinedim(ctx, ::B, ::A)

concordize(ctx, root)

A raw index is an index expression consisting of a single index node (i.e. A[i] as opposed to A[i + 1]). A Finch program is concordant when all indices are raw and column major with respect to the program loop ordering. The concordize transformation ensures that tensor indices are concordant by inserting loops and lifting index expressions or transposed indices into the loop bounds.

For example,

@finch for i = :
    b[] += A[f(i)]
end

becomes

@finch for i = :
    t = f(i)
    for s = t:t
        b[] += A[s]
    end
end

and

@finch for i = :, j = :
    b[] += A[i, j]
end

becomes

@finch for i = :, j = :, s = i:i
    b[] += A[s, j]
end

contain(f, ctx)

Call f on a subcontext of ctx and return the result. Variable bindings, preambles, and epilogues defined in the subcontext will not escape the call to contain.

countstored(arr)

Return the number of stored elements in arr. If there are explicitly stored fill elements, they are counted too.

See also: SparseArrays.nnz and Base.summarysize

data_rep(tns)

Return a trait object representing everything that can be learned about the data based on the storage format (type) of the tensor

dataflow(ex)

Run dead code elimination and constant propagation. ex is the target Julia expression.

declare!(ctx, tns, init)

Declare the read-only virtual tensor tns in the context ctx with a starting value of init and return it. Afterwards the tensor is update-only.

declare_level!(ctx, lvl, pos, init)

Initialize and thaw all fibers within lvl, assuming positions 1:pos were previously assembled and frozen. The resulting level has no assembled positions.

dimensionalize!(prgm, ctx)

A program traversal which coordinates dimensions based on shared indices. In particular, loops and declaration statements have dimensions. Accessing a tensor with a raw index hints that the loop should have a dimension corresponding to the tensor axis. Accessing a tensor on the left hand side with a raw index also hints that the tensor declaration should have a dimension corresponding to the loop axis. All hints inside a loop body are used to evaluate loop dimensions, and all hints after a declaration until the first freeze are used to evaluate declaration dimensions. One may refer to the automatically determined dimension using a variable named _ or :. Index sharing is transitive, so A[i] = B[i] and B[j] = C[j] will induce a gathering of the dimensions of A, B, and C into one.

The dimensions are semantically evaluated just before the corresponding loop or declaration statement. The program is assumed to be scoped, so that all loops have unique index names.

See also: virtual_size, virtual_resize!, combinedim

distribute(ctx, arr, device, diff, style)

If the virtual array is not on the given device, copy the array to that device. This function may modify underlying data arrays, but cannot change the virtual itself. This function is used to move data to the device before a kernel is launched. Since this function may modify the root node, iterators in-progress may need to be updated. We can store new root objects in the diff dictionary.

dropfills!(dst, src)

Copy only the non-fill values from src into dst.

dropfills(src)

Drop the fill values from src and return a new tensor with the same shape and format.

enforce_lifecycles(prgm)

A transformation which adds freeze and thaw statements automatically to tensor roots, depending on whether they appear on the left or right hand side.

enforce_scopes(prgm)

A transformation which gives all loops unique index names and enforces that tensor roots are declared in a containing scope and enforces that variables are declared once within their scope. Note that loop and sieve both introduce new scopes.

ensure_concurrent(root, ctx)

Ensures that all nonlocal assignments to the tensor root are consistently accessed with the same indices and associative operator. Also ensures that the tensor is either atomic, or accessed by i and concurrent and injective on i.

evaluate_partial(ctx, root)

This pass evaluates tags, global variable definitions, and foldable functions into the context bindings.

exit_on_yieldbind(prgm)

This pass rewrites the program so that yieldbind expressions are only present at the end of a block. It also adds a yieldbind if not present already.

eye_python(m, n, k, z)

Return a matrix of size m by n, in COO format with a diagonal offset by k, with fill value z.

See also: python.eye

ffindnz(arr)

Return the nonzero elements of arr, as Finch understands arr. Returns (I..., V), where I are the coordinate vectors, one for each mode of arr, and V is a vector of corresponding nonzero values, which can be passed to fsparse.

See also: findnz

fiber_ctr(tns, args...)

Return an expression that would construct a tensor suitable to hold data with a representation described by tns. Assumes representation is collapsed.

fill_value(arr)

Return the initializer for arr. For SparseArrays, this is 0. Often, the "fill" value becomes the "background" value of a tensor.

filterop(z)(cond, arg)

filterop(z) is a function which returns ifelse(cond, arg, z). This operation is handy for filtering out values based on a mask or a predicate. map(filterop(0), cond, arg) is analogous to filter(x -> cond ? x: z, arg).

julia> a = Tensor(SparseList(Element(0.0)), [0, 1.1, 0, 4.4, 0])
5 Tensor{SparseListLevel{Int64, Vector{Int64}, Vector{Int64}, ElementLevel{0.0, Float64, Int64, Vector{Float64}}}}:
 0.0
 1.1
 0.0
 4.4
 0.0

julia> x = Tensor(SparseList(Element(0.0)));

julia> c = Tensor(SparseList(Element(false)), [false, false, false, true, false]);

julia> @finch (x .= 0; for i=_; x[i] = filterop(0)(c[i], a[i]) end)
(x = Tensor(SparseList{Int64}(Element{0.0, Float64, Int64}([4.4]), 5, [1, 2], [4])),)

julia> x
5 Tensor{SparseListLevel{Int64, Vector{Int64}, Vector{Int64}, ElementLevel{0.0, Float64, Int64, Vector{Float64}}}}:
 0.0
 0.0
 0.0
 4.4
 0.0

finch_kernel(fname, args, prgm; options...)

Return a function definition for which can execute a Finch program of type prgm. Here, fname is the name of the function and args is a iterable of argument name => type pairs.

See also: @finch

fld1_nothrow(x, y)

Returns fld1(x, y) normally, returns one and issues a warning if y is zero.

fld_nothrow(x, y)

Returns fld(x, y) normally, returns zero and issues a warning if y is zero.

fread(filename::AbstractString)

Read the Finch tensor from a file using a file format determined by the file extension. The following file extensions are supported:

• .bsp.h5: Binsparse HDF5 file format
• .bspnpy: Binsparse NumPy and JSON subdirectory format
• .mtx: MatrixMarket .mtx text file format
• .ttx: TensorMarket .ttx text file format
• .tns: FROSTT .tns text file format

freeze!(ctx, tns)

Freeze the update-only virtual tensor tns in the context ctx and return it. This may involve trimming any excess overallocated memory. Afterwards, the tensor is read-only.

freeze_level!(ctx, lvl, pos)

Freeze all fibers in lvl. Positions 1:pos need freezing.

these two are no-ops, we instead do these on distribute

freeze_level!(ctx, lvl, pos, init)

Given the last reference position, pos, freeze all fibers within lvl assuming that we have potentially updated 1:pos.

freshen(ctx, tags...)

Return a fresh variable in the current context named after Symbol(tags...)

fsparse!(I..., V,[ M::Tuple]; fill_value=zero(eltype(V)))

Like fsparse, but the coordinates must be sorted and unique, and memory is reused.

fsparse(I..., V,[ M::Tuple, combine]; fill_value=zero(eltype(V)))

Create a sparse COO tensor S such that size(S) == M and S[(i[q] for i in I)...] = V[q]. The combine function is used to combine duplicates. If M is not specified, it is set to map(maximum, I). If the combine function is not supplied, combine defaults to + unless the elements of V are Booleans in which case combine defaults to |. All elements of I must satisfy 1 <= I[n][q] <= M[n]. Numerical zeros are retained as structural nonzeros; to drop numerical zeros use dropfills.

See also: sparse

Examples

julia> I = ([1, 2, 3], [1, 2, 3], [1, 2, 3]);

julia> V = [1.0, 2.0, 3.0];

julia> fsparse(I..., V)
3×3×3 Tensor{SparseCOOLevel{3, Tuple{Int64, Int64, Int64}, Vector{Int64}, Tuple{Vector{Int64}, Vector{Int64}, Vector{Int64}}, ElementLevel{0.0, Float64, Int64, Vector{Float64}}}}:
[:, :, 1] =
 1.0  0.0  0.0
 0.0  0.0  0.0
 0.0  0.0  0.0

[:, :, 2] =
 0.0  0.0  0.0
 0.0  2.0  0.0
 0.0  0.0  0.0

[:, :, 3] =
 0.0  0.0  0.0
 0.0  0.0  0.0
 0.0  0.0  3.0

fspeye(dims...)

Return a Boolean identity matrix of size dims, in COO format.

See also: mat.speye

fsprand([rng], [type], M..., p, [rfn])

Create a random sparse tensor of size m in COO format. There are two cases:

• If p is a floating point number, the probability of any element being nonzero is independently given by p (and hence the expected density of nonzeros is also p).
• If p is an integer, exactly p nonzeros are distributed uniformly at random throughout the tensor (and hence the density of nonzeros is exactly p / prod(M)).

Nonzero values are sampled from the distribution specified by rfn and have the type type. The uniform distribution is used in case rfn is not specified. The optional rng argument specifies a random number generator.

See also: sprand

Examples

julia> fsprand(Bool, 3, 3, 0.5)
3×3 Tensor{SparseCOOLevel{2, Tuple{Int64, Int64}, Vector{Int64}, Tuple{Vector{Int64}, Vector{Int64}}, ElementLevel{false, Bool, Int64, Vector{Bool}}}}
:
 0  0  0
 1  0  1
 0  0  1

julia> fsprand(Float64, 2, 2, 2, 0.5)
2×2×2 Tensor{SparseCOOLevel{3, Tuple{Int64, Int64, Int64}, Vector{Int64}, Tuple{Vector{Int64}, Vector{Int64}, Vector{Int64}}, ElementLevel{0.0, Float64, Int64, Vector{Float64}}}}:
[:, :, 1] =
 0.0       0.598969
 0.963969  0.0

[:, :, 2] =
 0.337409  0.0
 0.0       0.0

fspzeros([type], M...)

Create a zero tensor of size M, with elements of type type. The tensor is in COO format.

See also: spzeros

Examples

julia> A = fspzeros(Bool, 3, 3)
3×3 Tensor{SparseCOOLevel{2, Tuple{Int64, Int64}, Vector{Int64}, Tuple{Vector{Int64}, Vector{Int64}}, ElementLevel{false, Bool, Int64, Vector{Bool}}}}:
 0  0  0
 0  0  0
 0  0  0

julia> countstored(A)
0

julia> B = fspzeros(Float64, 2, 2, 2)
2×2×2 Tensor{SparseCOOLevel{3, Tuple{Int64, Int64, Int64}, Vector{Int64}, Tuple{Vector{Int64}, Vector{Int64}, Vector{Int64}}, ElementLevel{0.0, Float64, Int64, Vector{Float64}}}}:
[:, :, 1] =
 0.0  0.0
 0.0  0.0

[:, :, 2] =
 0.0  0.0
 0.0  0.0

julia> countstored(B)
0

ftnsread(filename)

Read the contents of the FROSTT .tns file 'filename' into a Finch COO Tensor.

TensorMarket must be loaded for this function to be available.

See also: tnsread

ftnswrite(filename, tns)

Write a sparse Finch tensor to a FROSTT .tns file.

TensorMarket must be loaded for this function to be available.

See also: tnswrite

fttread(filename, infoonly=false, retcoord=false)

Read the TensorMarket file into a Finch tensor. The tensor will be dense or COO depending on the format of the file.

TensorMarket must be loaded for this function to be available.

See also: ttread

fttwrite(filename, tns)

Write a sparse Finch tensor to a TensorMarket file.

TensorMarket must be loaded for this function to be available.

See also: ttwrite

fwrite(filename::AbstractString, tns::Finch.Tensor)

Write the Finch tensor to a file using a file format determined by the file extension. The following file extensions are supported:

• .bsp.h5: Binsparse HDF5 file format
• .bspnpy: Binsparse NumPy and JSON subdirectory format
• .mtx: MatrixMarket .mtx text file format
• .ttx: TensorMarket .ttx text file format
• .tns: FROSTT .tns text file format

get_algebra(ctx)

get the algebra used in the current context

get_binding!(ctx, var, val)

Get the binding of a variable in the context, or set it to a default value.

get_binding(ctx, var, val)

Get the binding of a variable in the context, or return a default value.

get_binding(ctx, var)

Get the binding of a variable in the context.

get_device(task::AbstractTask)

Return the device that task is running on.

get_lock(dev::AbstractDevice, arr, idx, ty)

Given a device, an array of elements of type ty, and an index to the array, idx, gets a lock of type ty associated to arr[idx] on dev.

get_mode_flag(ctx)

Return the mode flag given in @finch mode = ?.

get_num_tasks(dev::AbstractDevice)

Return the number of tasks on the device dev.

get_parent_task(task::AbstractTask)

Return the task which spawned task.

get_prove_rules(alg, shash)

Return the bound rule set for Finch. One can dispatch on the alg trait to specialize the rule set for different algebras. shash is an object that can be called to return a static hash value. This rule set is used to analyze loop bounds in Finch.

get_result(ctx)

Return a variable which evaluates to the result of the program which should be returned to the user.

get_simplify_rules(alg, shash)

Return the program rule set for Finch. One can dispatch on the alg trait to specialize the rule set for different algebras. Defaults to a collection of straightforward rules that use the algebra to check properties of functions like associativity, commutativity, etc. shash is an object that can be called to return a static hash value. This rule set simplifies, normalizes, and propagates constants, and is the basis for how Finch understands sparsity.

get_static_hash(ctx)

Return an object which can be called as a hash function. The hashes are the same when objects are hashed in the same order.

get_style(ctx, root)

return the style to use for lowering root in ctx. This method is used to determine which pass should be used to lower a given node. The default implementation returns DefaultStyle(). Overload the three argument form of this method, get_style(ctx, node, root) and specialize on node.

get_task(ctx)

Get the task which will execute code in this context

get_task_num(task::AbstractTask)

Return the task number of task.

get_tensor_mode(ctx, var)

Get the mode of a tensor variable in the context.

get_wrapper_rules(ctx, depth, alg)

Return the wrapperizing rule set for Finch, which converts expressions like `A[i

• 1]to array combinator expressions likeOffsetArray(A, (1,))`. The rules have

access to the algebra alg and the depth lookup depthOne can dispatch on thealg` trait to specialize the rule set for different algebras. These rules run after simplification so one can expect constants to be folded.

getindex_rep(tns, idxs...)

Return a trait object representing the result of calling getindex(tns, idxs...) on the tensor represented by tns. Assumes traits are in collapsed form.

getunbound(stmt)

Return an iterator over the indices in a Finch program that have yet to be bound.

julia> getunbound(@finch_program for i=_; :a[i, j] += 2 end)
[j]
julia> getunbound(@finch_program i + j * 2 * i)
[i, j]

global_memory(dev::AbstractDevice)

Return the default global memory space of dev.

has_binding(ctx, var)

Check if a variable is bound in the context.

instantiate!(ctx, prgm)

A transformation to call instantiate on tensors before executing an expression.

instantiate(ctx, tns, mode)

Process the tensor tns in the context ctx, just after it has been unfurled, declared, or thawed. The earliest opportunity to process tns.

assemble: mapping is pos -> task, ptr. task says which task has it, ptr says which position in that task has it.

read: read from pos to task, ptr. simple.

write: allocate something for this task on that position, assemble on the task itself on demand. Complain if the task is wrong.

The outer level needs to be concurrent, like denselevel.

assemble: mapping is pos -> task, ptr. task says which task has it, ptr says which position in that task has it.

read: read from pos to task, ptr. simple.

write: allocate something for this task on that position, assemble on the task itself on demand. Complain if the task is wrong.

The outer level needs to be concurrent, like denselevel.

is_atomic(ctx, tns)

Returns a tuple (atomicities, overall) where atomicities is a vector, indicating which indices have an atomic that guards them,
and overall is a boolean that indicates is the last level had an atomic guarding it.

is_concurrent(ctx, tns)

Returns a vector of booleans, one for each dimension of the tensor, indicating
whether the index can be written to without any execution state. So if a matrix returns [true, false],
then we can write to A[i, j] and A[i_2, j] without any shared execution state between the two, but
we can't write to A[i, j] and A[i, j_2] without carrying over execution state.

is_injective(ctx, tns)

Returns a vector of booleans, one for each dimension of the tensor, indicating whether the access is injective in that dimension. A dimension is injective if each index in that dimension maps to a different memory space in the underlying array.

isannihilator(algebra, f, x)

Return true when f(a..., x, b...) = x in algebra.

isassociative(algebra, f)

Return true when f(a..., f(b...), c...) = f(a..., b..., c...) in algebra.

iscommutative(algebra, f)

Return true when for all permutations p, f(a...) = f(a[p]...) in algebra.

isdistributive(algebra, f, g)

Return true when f(a, g(b, c)) = g(f(a, b), f(a, c)) in algebra.

isidempotent(algebra, f)

Return true when f(a, b) = f(f(a, b), b) in algebra.

isidentity(algebra, f, x)

Return true when f(a..., x, b...) = f(a..., b...) in algebra.

isinverse(algebra, f, g)

Return true when f(a, g(a)) is the identity under f in algebra.

isinvolution(algebra, f)

Return true when f(f(a)) = a in algebra.

labelled_children(node)

Return the children of node in a LabelledTree. You may label the children by returning a LabelledTree(key, value), which will be shown as key: value a.

labelled_show(node)

Show the node in a LabelledTree.

level_axes(lvl)

The result of level_axes(lvl) defines the axes of all subfibers in the level lvl.

level_eltype(::Type{Lvl})

The result of level_eltype(Lvl) defines eltype for all subfibers in a level of type Lvl.

level_fill_value(::Type{Lvl})

The result of level_fill_value(Lvl) defines fill_value for all subfibers in a level of type Lvl.

level_ndims(::Type{Lvl})

The result of level_ndims(Lvl) defines ndims for all subfibers in a level of type Lvl.

level_size(lvl)

The result of level_size(lvl) defines the size of all subfibers in the level lvl.

local_memory(dev::AbstractDevice)

Return the default local memory space of dev.

lower_global(ctx, prgm)

lower the program prgm at global scope in the context ctx.

make_lock(ty)

Makes a lock of type ty.

maxby(a, b)

Return the max of a or b, comparing them by a[1] and b[1], and breaking ties to the left. Useful for implementing argmax operations:

julia> a = [7.7, 3.3, 9.9, 3.3, 9.9]; x = Scalar(-Inf => 0);

julia> @finch for i=_; x[] <<maxby>>= a[i] => i end;

julia> x[]
9.9 => 3

minby(a, b)

Return the min of a or b, comparing them by a[1] and b[1], and breaking ties to the left. Useful for implementing argmin operations:

julia> a = [7.7, 3.3, 9.9, 3.3, 9.9]; x = Scalar(Inf => 0);

julia> @finch for i=_; x[] <<minby>>= a[i] => i end;

julia> x[]
3.3 => 2

mod1_nothrow(x, y)

Returns mod1(x, y) normally, returns one and issues a warning if y is zero.

mod_nothrow(x, y)

Returns mod(x, y) normally, returns zero and issues a warning if y is zero.

oddevenmergesortlowermask(n, p, k)

A vector mask selecting the left endpoints of the compare-exchanges in oddevenmergesortpartnermask(n, p, k). These endpoints receive the smaller value. Both p and k must be positive.

oddevenmergesortpartnermask(n, p, k)

A mask mapping each index to its compare-exchange partner in an odd-even merge sort stage of length n. With zero-based position r = i - 1 and offset = mod(k, p), i is a left endpoint when r + k < n, r >= offset, mod(r - offset, 2k) < k, and fld(r, 2p) == fld(r + k, 2p). Partners exchange i and i + k; unpaired indices map to themselves. Both p and k must be positive. The row extent is inferred.

offset(tns, delta...)

Create an OffsetArray such that offset(tns, delta...)[i...] == tns[i .+ delta...]. The dimensions declared by an OffsetArray are shifted, so that size(offset(tns, delta...)) == size(tns) .+ delta.

onehotmask(index)

A vector mask with a single true entry, onehotmask(index)[i] = i == index. The index is one-based and the extent is inferred from other tensors or loop bounds. An index outside that extent produces an all-false mask.

open_scope(f, ctx)

Call the function f(ctx_2) in a new scope ctx_2.

parallel(ext, device=CPU(nthreads()), schedule=static_schedule())

A dimension ext that is parallelized over device using the schedule. The ext field is usually _, or dimensionless, but can be any standard dimension argument.

paritymask(parity=0)

A vector mask selecting alternating entries, paritymask(parity)[i] = mod(i - 1, 2) == parity. Parity refers to the zero-based position: 0 selects Julia indices 1, 3, 5, … and 1 selects 2, 4, 6, …. Other values produce an all-false mask. The extent is inferred.

pattern!(fbr)

Return the pattern of fbr. That is, return a tensor which is true wherever fbr is structurally unequal to its fill value. May reuse memory and render the original tensor unusable when modified.

julia> A = Tensor(SparseList(Element(0.0), 10), [2.0, 0.0, 3.0, 0.0, 4.0, 0.0, 5.0, 0.0, 6.0, 0.0])
10 Tensor{SparseListLevel{Int64, Vector{Int64}, Vector{Int64}, ElementLevel{0.0, Float64, Int64, Vector{Float64}}}}:
 2.0
 0.0
 3.0
 0.0
 4.0
 0.0
 5.0
 0.0
 6.0
 0.0

julia> pattern!(A)
10 Tensor{SparseListLevel{Int64, Vector{Int64}, Vector{Int64}, PatternLevel{Int64}}}:
 1
 0
 1
 0
 1
 0
 1
 0
 1
 0

permissive(tns, dims...)

Create an PermissiveArray where permissive(tns, dims...)[i...] is missing if i[n] is not in the bounds of tns when dims[n] is true. This wrapper allows all permissive dimensions to be exempt from dimension checks, and is useful when we need to access an array out of bounds, or for padding. More formally,

permissive(tns, dims...)[i...] =
    if any(n -> dims[n] && !(i[n] in axes(tns)[n]))
        missing
    else
        tns[i...]
    end

permutedims_rep(tns, perm)

Return a trait object representing the result of permuting a tensor represented by tns to the permutation perm.

postype(lvl)

Return a position type with the same flavor as those used to store the positions of the fibers contained in lvl. The name position descends from the pos or position or pointer arrays found in many definitions of CSR or CSC. In Finch, positions should be data used to access either a subfiber or some other similar auxiliary data. Thus, we often end up iterating over positions.

pretty(ex)

Make ex prettier. Shorthand for ex |> unblock |> striplines |> regensym.

products(tns, dim)

Create a ProductArray such that

products(tns, dim)[i...] == tns[i[1:dim-1]..., i[dim] * i[dim + 1], i[dim + 2:end]...]

This is like toeplitz but with times instead of plus.

protocolize(tns, protos...)

Create a ProtocolizedArray that accesses dimension n with protocol protos[n], if protos[n] is not nothing. See the documention for Iteration Protocols for more information. For example, to gallop along the inner dimension of a matrix A, we write A[gallop(i), j], which becomes protocolize(A, gallop, nothing)[i, j].

prove(ctx, root; verbose = false)

use the rules in ctx to attempt to prove that the program root is true. Return false if the program cannot be shown to be true.

push_epilogue!(ctx, thunk)

Push the thunk onto the epilogue in the currently executing context. The epilogue will be evaluated after the code returned by the given function in the context.

push_preamble!(ctx, thunk)

Push the thunk onto the preamble in the currently executing context. The preamble will be evaluated before the code returned by the given function in the context.

randommask([rng], shape, p; seed=nothing)

A Boolean mask with reproducible random-looking entries and an approximate true fraction of p. shape is a tuple of nonnegative dimensions, or an integer for a vector. An empty tuple gives a scalar. The probability is stored as Float64 and must lie in [0, 1]; p = 0 and p = 1 give constant masks.

An indexed mask starts with a mixed 64-bit seed, then XORs in each one-based coordinate and mixes again, from the last axis to the first. The high 53 bits of the result are converted to a value in [0, 1) and compared with p. This is a pseudorandom hash construction; it does not promise n-wise independence. Scalar masks convert the seed directly to a value in [0, 1) and compare with p. Each read specializes into separate true and false branches.

Reads consume no randomness and are independent of traversal order. The same seed and coordinates give the same entry even when the shape changes. There is no limit on the product of the dimensions, since coordinates are never flattened. Only the shape, probability, and one seed are stored.

Pass seed as an integer in [0, typemax(UInt64)] to reproduce a mask directly. If omitted, one seed is drawn from rng (the default RNG if omitted).

For example, mask = randommask((100, 200), 0.1; seed=42) creates a matrix mask that can be read as mask[i, j] inside @finch.

reassemble_level!(lvl, ctx, pos_start, pos_end)

Set the previously assempled positions from pos_start to pos_end to level_fill_value(lvl). Not avaliable on all level types as this presumes updating.

redistribute(ctx, node, diff)

When the root node is distributed, several iterators may need to be updated.

The redistribute function traverses tns and updates it based on the updated objects in the diff dictionary.

Finch.refresh()

Finch caches the code for kernels as soon as they are run. If you modify the Finch compiler after running a kernel, you'll need to invalidate the Finch caches to reflect these changes by calling Finch.refresh(). This function should only be called at global scope, and never during precompilation.

regensym(ex)

Give gensyms prettier names by renumbering them. ex is the target Julia expression.

release_lock!(dev::AbstractDevice, val)

Release the lock, val, on the device dev.

rem_nothrow(x, y)

Returns rem(x, y) normally, returns zero and issues a warning if y is zero.

rep_construct(tns, args...)

Construct a tensor suitable to hold data with a representation described by tns. Assumes representation is collapsed.

repeatmask(k=0)

A mask for repeating each entry k times, repeatmask(k)[i, j] = k > 0 && j == fld(i - 1, k) + 1. Each column specializes the interval k * (j - 1) < i <= k * j. For k <= 0, all entries are false. Both extents are inferred.

reshapemask(old_shape, new_shape)

A mask relating coordinates with equal row-major linear positions in two shapes. The axes are (old_shape..., new_shape...); the last axis of each shape varies fastest, matching the Python pattern. Coordinates are one-based. The shapes must have equal products. Empty tuples represent scalars.

For example, reshapemask((2, 3), (3, 2))[i, j, k, l] is true when 3(i - 1) + j - 1 == 2(k - 1) + l - 1.

return_type(algebra, f, arg_types...)

Give the return type of f when applied to arguments of types arg_types... in algebra. Used to determine output types of functions in the high-level interface. This function falls back to Base.promote_op.

reversemask(n)

A mask for reversing an axis of length n, reversemask(n)[i, j] = j == n - i + 1. Each column specializes its single true entry. The row extent is inferred from other tensors or the loop bounds.

rollmask(n, k=0)

A mask for rolling an axis of length n by k, rollmask(n, k)[i, j] = n > 0 && j == mod(i - k - 1, n) + 1. The row extent is inferred. Each column steps through its true entries with period n, so rectangular uses may contain multiple true entries per column.

scale(tns, delta...)

Create a ScaleArray such that scale(tns, delta...)[i...] == tns[i .* delta...]. The dimensions declared by an OffsetArray are shifted, so that size(scale(tns, delta...)) == size(tns) .* delta. This is only supported on tensors with real-valued dimensions.

scansearch(v, x, lo, hi)

return the first value of v greater than or equal to x, within the range lo:hi. Return hi+1 if all values are less than x. This implemantation uses an exponential search strategy which involves two steps: 1) searching for binary search bounds via exponential steps rightward 2) binary searching within those bounds.

scansearch_perm(v, perm, x, lo, hi)

Like scansearch, but compares v[perm[p]] instead of v[p].

set_binding!(ctx, var, val)

Set the binding of a variable in the context.

set_declared!(ctx, var, val, op)

Mark a tensor variable as declared in the context.

set_fill_value!(fbr, init)

Return a tensor which is equal to fbr, but with the fill (implicit) value set to init. May reuse memory and render the original tensor unusable when modified.

julia> A = Tensor(SparseList(Element(0.0), 10), [2.0, 0.0, 3.0, 0.0, 4.0, 0.0, 5.0, 0.0, 6.0, 0.0])
10 Tensor{SparseListLevel{Int64, Vector{Int64}, Vector{Int64}, ElementLevel{0.0, Float64, Int64, Vector{Float64}}}}:
 2.0
 0.0
 3.0
 0.0
 4.0
 0.0
 5.0
 0.0
 6.0
 0.0

julia> set_fill_value!(A, Inf)
10 Tensor{SparseListLevel{Int64, Vector{Int64}, Vector{Int64}, ElementLevel{Inf, Float64, Int64, Vector{Float64}}}}:
  2.0
 Inf
  3.0
 Inf
  4.0
 Inf
  5.0
 Inf
  6.0
 Inf

set_frozen!(ctx, var, val)

Mark a tensor variable as frozen in the context.

set_thawed!(ctx, var, val, op)

Mark a tensor variable as thawed in the context.

setup_coalesce!(lvl, max_pos, dst, P, splits, offsets, overlap)

Allocate destination storage and plan the merge of P ordered shards. max_pos is the destination parent-position extent. Shard p's local parent positions splits[p][r]:(splits[p][r + 1] - 1) land in the merged output starting at offsets[p][r]; a hash permutes child positions, so a shard below one can need several ranges. overlap indicates that leaves may overlap, so elements copy only values other than fill.

Sparse plans report shared[p], the local child position whose index metadata is already owned by an earlier shard, or 0 when all indices must be written. shared_dst[p] is that child's destination position, also 0 when unshared. These are positions, not Boolean flags or permutation ranks: a list uses an idx position, a byte map uses a position stored in srt, and a hash uses the q in its (parent, index, q) entry. Empty shards do not change ownership.

Skip only the shared entry's index metadata. Its children still contribute to shared_dst[p]. Ordinary child positions use the child plan's offset; a hash passes its shared position to its child as a range of its own. Count shared entries with shared[p] != 0, never by subtracting the position itself.

nnz counts all owned entries, and list plans also report off[p], the owned index entries of earlier shards. Dense and element plans have no sparse index ownership fields; dense plans delegate through child, and element plans use overlap when copying.

init lists (buffer, start, value) ranges, including child storage. Setup allocates serially; initialize these ranges before calling coalesce_shard!.

shard_runs(splits, offsets, rank, parent)

Order the entries of a sparse level's shards for merging. rank(t, p) is shard t's first entry whose parent is at least p, and parent(t, r) is the parent of its entry r. Return runs (t, lo, hi, delta) of shard t's entries lo:hi, in destination order, whose parents all move by delta.

Each range of a shard moves as a block. A hash's shared entry keeps an arbitrary child position, so below a hash, a range can land inside an earlier shard's range. Cutting every range wherever any range lands leaves runs that meet only under a parent two shards share, where band order puts the earlier shard's entries first. A run that continues the one before it merges into it.

shared_memory(dev::AbstractDevice)

Return the default shared memory space of dev.

simplify(ctx, node)

simplify the program node using the rules in ctx

splitmask(n, P)

A mask to evenly divide n indices into P regions. If M = splitmask(P, n), then M[i, j] = fld(n * (j - 1), P) <= i < fld(n * j, P).

julia> splitmask(10, 3)
10×3 Finch.SplitMask{Int64}:
 1  0  0
 1  0  0
 1  0  0
 0  1  0
 0  1  0
 0  1  0
 0  0  1
 0  0  1
 0  0  1
 0  0  1

striplines(ex)

Remove line numbers. ex is the target Julia expression

swizzle(tns, dims...)

Create a SwizzleArray to transpose any tensor tns such that

swizzle(tns, dims...)[i...] == tns[(i[d] for d in dims)...]

tensor_tree(tns; nmax = 2)

Print a tree representation of the tensor tns to the standard output. nmax is half the maximum number of children to show before truncating.

tensor_tree(io::IO, tns; nmax = 2)

Print a tree representation of the tensor tns to io. nmax is half the maximum number of children to show before truncating.

thaw!(ctx, tns)

Thaw the read-only virtual tensor tns in the context ctx and return it. Afterwards, the tensor is update-only.

thaw_level!(ctx, lvl, pos, init)

Given the last reference position, pos, thaw all fibers within lvl assuming that we have previously assembled and frozen 1:pos.

toeplitz(tns, dim)

Create a ToeplitzArray such that

toeplitz(tns, dim)[i...] == tns[i[1:dim-1]..., i[dim] + i[dim + 1], i[dim + 2:end]...]

The ToplitzArray can be thought of as adding a dimension that shifts another dimension of the original tensor.

transfer(device, arr)

If the array is not on the given device, it creates a new version of this array on that device and copies the data in to it, according to the device trait. If the device is simply a data buffer, we copy the array into the buffer.

tuplemask

Similar to bandmask, but instead compares tuples, tuplemask[i, j, k] = j <= i <= k. Note that unlike bandmask, i, j, and k are all tuples, and comparison happens lexiographically. Comparison is reverse-ordered; meaning that the most significant digits start on the rightmost end of the tuple. For example, (4, 1, 6) < (1, 1, 7) because 6 < 7.

unblock(ex)

Flatten any redundant blocks into a single block, over the whole expression. ex is the target Julia expression.

unfurl(ctx, tns, ext, proto)

Return an array object (usually a looplet nest) for lowering the outermost dimension of virtual tensor tns. ext is the extent of the looplet. proto is the protocol that should be used for this index, but one doesn't need to unfurl all the indices at once.

unquote_literals(ex)

unquote QuoteNodes when this doesn't change the semantic meaning. ex is the target Julia expression.

unresolve(ex)

Unresolve function literals into function symbols. ex is the target Julia expression.

virtual_call(ctx, f, args...)

Given the virtual arguments args..., and a literal function f, return a virtual object representing the result of the function call. If the function is not foldable, return nothing. This function is used so that we can call e.g. tensor wrapper constructors and dimension constructors in finch code. Implementations should overload virtual_call_def to provide the actual implementation.

virtual_eltype(arr)

Return the element type of the virtual tensor arr.

virtual fill_value(arr)

Return the initializer for virtual array arr.

virtual_resize!(ctx, tns, dims...)

Resize tns in the context ctx. This is a function similar in spirit to Base.resize!.

virtual_size(ctx, tns)

Return a tuple of the dimensions of tns in the context ctx. This is a function similar in spirit to Base.axes.

virtual_type(ctx, algebra, arg)

Return the narrowest type constraint on the argument arg that is compatible with the algebra.

virtualize(ctx, ex, T, [tag])

Return the virtual program corresponding to the Julia expression ex of type T in the JuliaContext ctx. Implementaters may support the optional tag argument is used to name the resulting virtual variable.

window(tns, dims)

Create a WindowedArray which represents a view into another tensor

window(tns, dims)[i...] == tns[dim[1][i], dim[2][i], ...]

The windowed array restricts the new dimension to the dimension of valid indices of each dim. The dims may also be nothing to represent a full view of the underlying dimension.

wrapperize(ctx, root)

Convert index expressions in the program root to wrapper arrays, according to the rules in get_wrapper_rules. By default, the following transformations are performed:

A[i - j] => A[i + (-j)]
A[3 * i] => ScaleArray(A, (3,))[i]
A[i * j] => ProductArray(A, 1)[i, j]
A[i + 1] => OffsetArray(A, (1,))[i]
A[i + j] => ToeplitzArray(A, 1)[i, j]
A[~i] => PermissiveArray(A, 1)[i]

The loop binding order may be used to determine which index comes first in an expression like A[i + j]. Thus, for i=:,j=:; ... A[i + j] will result in ToeplitzArray(A, 1)[j, i], but for j=:,i=:; ... A[i + j] results in ToeplitzArray(A, 1)[i, j]. wrapperize runs before dimensionalization, so resulting raw indices may participate in dimensionalization according to the semantics of the wrapper.

@barrier args... ex

Evaluate ex in a closure whose free variables are bound in a let just before it. Generated code wraps every construct that creates a closure, such as Threads.@threads or a comprehension, so the closure captures only those single-assignment bindings: rebinding a variable elsewhere never boxes it.

@closure closure_expression

Wrap the closure definition closure_expression in a let block to encourage the julia compiler to generate improved type information. For example:

callfunc(f) = f()

function foo(n)
   for i=1:n
       if i >= n
           # Unlikely event - should be fast.  However, capture of `i` inside
           # the closure confuses the julia-0.6 compiler and causes it to box
           # the variable `i`, leading to a 100x performance hit if you remove
           # the `@closure`.
           callfunc(@closure ()->println("Hello $i"))
       end
   end
end

There's nothing nice about this - it's a heuristic workaround for some inefficiencies in the type information inferred by the julia 0.6 compiler. However, it can result in large speedups in many cases, without the need to restructure the code to avoid the closure.

@finch [options...] prgm

Run a finch program prgm. The syntax for a finch program is a set of nested loops, statements, and branches over pointwise array assignments. For example, the following program computes the sum of two arrays A = B + C:

@finch begin
    A .= 0
    for i = _
        A[i] = B[i] + C[i]
    end
    return A
end

Finch programs are composed using the following syntax:

• arr .= 0: an array declaration initializing arr to zero.
• arr[inds...]: an array access, the array must be a variable and each index may be another finch expression.
• x + y, f(x, y): function calls, where x and y are finch expressions.
• arr[inds...] = ex: an array assignment expression, setting arr[inds] to the value of ex.
• arr[inds...] += ex: an incrementing array expression, adding ex to arr[inds]. *, &, |, are supported.
• arr[inds...] <<min>>= ex: a incrementing array expression with a custom operator, e.g. <<min>> is the minimum operator.
• for i = _ body end: a loop over the index i, where _ is computed from array access with i in body.
• if cond body end: a conditional branch that executes only iterations where cond is true.
• return (tnss...,): at global scope, exit the program and return the tensors tnss with their new dimensions. By default, any tensor declared in global scope is returned.

Symbols are used to represent variables, and their values are taken from the environment. Loops introduce index variables into the scope of their bodies.

Finch uses the types of the arrays and symbolic analysis to discover program optimizations. If B and C are sparse array types, the program will only run over the nonzeros of either.

Semantically, Finch programs execute every iteration. However, Finch can use sparsity information to reliably skip iterations when possible.

options are optional keyword arguments:

• algebra: the algebra to use for the program. The default is DefaultAlgebra().
• mode: the optimization mode to use for the program. Possible modes are:
  • :debug: run the program in debug mode, with bounds checking and better error handling.
  • :safe: run the program in safe mode, with modest checks for performance and correctness.
  • :fast: run the program in fast mode, with no checks or warnings, this mode is for power users.
  The default is :safe.

See also: @finch_code

@finch_code [options...] prgm

Return the code that would be executed in order to run a finch program prgm.

See also: @finch

@finch_kernel [options...] fname(args...) = prgm

Return a definition for a function named fname which executes @finch prgm on the arguments args. args should be a list of variables holding representative argument instances.

See also: @finch

Finch.@staged

This function is used internally in Finch in lieu of @generated functions. It ensures the first Finch invocation runs in the latest world, and leaves hooks so that subsequent calls to Finch.refresh can update the world and invalidate old versions. If the body contains closures, this macro uses an eval and invokelatest strategy. Otherwise, it uses a generated function. This macro does not support type parameters, varargs, or keyword arguments.

access(tns, mode, idx...)

Finch AST expression representing the value of tensor tns at the indices idx.... The mode differentiates between reads or updates and whether the access is in-place.

assign(lhs, op, rhs)

Finch AST statement that updates the value of lhs to op(lhs, rhs). Overwriting is accomplished with the function overwrite(lhs, rhs) = rhs.

block(bodies...)

Finch AST statement that executes each of it's arguments in turn.

cached(val, ref)

Finch AST expression val, equivalent to the quoted expression ref

call(op, args...)

Finch AST expression for the result of calling the function op on args....

declare(tns, init, op)

Finch AST statement that declares tns with an initial value init reduced with op in the current scope.

define(lhs, rhs, body)

Finch AST statement that defines lhs as having the value rhs in body. A new scope is introduced to evaluate body.

freeze(tns, op)

Finch AST statement that freezes tns in the current scope after modifications with op, moving the tensor from update-only mode to read-only mode.

index(name)

Finch AST expression for an index named name. Each index must be quantified by a corresponding loop which iterates over all values of the index.

literal(val)

Finch AST expression for the literal value val.

loop(idx, ext, body)

Finch AST statement that runs body for each value of idx in ext. Tensors in body must have ranges that agree with ext. A new scope is introduced to evaluate body.

reader()

Finch AST expression representing a read-only mode for a tensor access. Declare, freeze, and thaw statements can change the mode of a tensor.

sieve(cond, body)

Finch AST statement that only executes body if cond is true. A new scope is introduced to evaluate body.

tag(var, bind)

Finch AST expression for a global variable var with the value bind. Because the finch compiler cannot pass variable state from the program domain to the type domain directly, the tag type represents a value bind referred to by a variable named bind. All tag in the same program must agree on the value of variables, and only one value will be virtualized.

thaw(tns, op)

Finch AST statement that thaws tns in the current scope, moving the tensor from read-only mode to update-only mode with a reduction operator op.

updater(op)

Finch AST expression representing an update-only mode for a tensor access, using the reduction operator op. Declare, freeze, and thaw statements can change the mode of a tensor.

value(val, type)

Finch AST expression for host code val expected to evaluate to a value of type type.

variable(name)

Finch AST expression for a variable named name. The variable can be looked up in the context.

virtual(val)

Finch AST expression for an object val which has special meaning to the compiler. This type is typically used for tensors, as it allows users to specify the tensor's shape and data type.

yieldbind(args...)

Finch AST statement that sets the result of the program to the values of variables args.... Subsequent statements will not affect the result of the program.

Auto()

A singleton type representing the lack of a dimension. This is used in place of a dimension when we want to avoid dimensionality checks. In the @finch macro, you can write Auto() with an underscore as for i = _, allowing finch to pick up the loop bounds from the tensors automatically.

FinchNode

A Finch IR node, used to represent an imperative, physical Finch program.

The FinchNode struct represents many different Finch IR nodes. The nodes are differentiated by a FinchNotation.FinchNodeKind enum.

extrude(i)

The extrude protocol declares that the tensor update happens in order and only once, so that reduction loops occur below the extrude loop. It is not usually necessary to declare an extrude protocol, but it is used internally to reason about tensor format requirements.

finch_leaf(x)

Return a terminal finch node wrapper around x. A convenience function to determine whether x should be understood by default as a literal, value, or virtual.

follow(i)

The follow protocol ignores the structure of the tensor. By itself, the follow protocol iterates over each value of the tensor in order, looking it up with random access. The follow protocol may specialize on e.g. the zero value of the tensor, but does not specialize on the structure of the tensor. This enables efficient random access and avoids large code sizes.

gallop(i)

The gallop protocol iterates over each pattern element of a tensor, leading the iteration and superceding the priority of other tensors. Mutual leading is possible, where we fast-forward to the largest step between either leader.

initwrite(z)(a, b)

initwrite(z) is a function which may assert that a isequal to z, and returnsb. By default,lhs[] = rhsis equivalent tolhs[] <<initwrite(fill_value(lhs))>>= rhs`.

isconstant(node)

Returns true if the node can be expected to be constant within the current finch context

isindex(node)

Returns true if the node is a finch index

isliteral(node)

Returns true if the node is a finch literal

isstateful(node)

Returns true if the node is a finch statement, and false if the node is an index expression. Typically, statements specify control flow and expressions describe values.

isvalue(node)

Returns true if the node is a finch value

isvariable(node)

Returns true if the node is a finch variable

isvirtual(node)

Returns true if the node is a finch virtual

laminate(i)

The laminate protocol declares that the tensor update may happen out of order and multiple times. It is not usually necessary to declare a laminate protocol, but it is used internally to reason about tensor format requirements.

overwrite(z)(a, b)

overwrite(z) is a function which returns b always. lhs[] := rhs is equivalent to lhs[] <<overwrite>>= rhs.

julia> a = Tensor(SparseList(Element(0.0)), [0, 1.1, 0, 4.4, 0])
5 Tensor{SparseListLevel{Int64, Vector{Int64}, Vector{Int64}, ElementLevel{0.0, Float64, Int64, Vector{Float64}}}}:
 0.0
 1.1
 0.0
 4.4
 0.0

julia> x = Scalar(0.0); @finch for i=_; x[] <<overwrite>>= a[i] end;

julia> x[]
0.0

walk(i)

The walk protocol usually iterates over each pattern element of a tensor in order. Note that the walk protocol "imposes" the structure of its argument on the kernel, so that we specialize the kernel to the structure of the tensor.