Documentation

An index function is a mapping from a multidimensional array index space (the domain) to a one-dimensional memory index space. Essentially, it explains where the element at position [i,j,p] of some array is stored inside the flat one-dimensional array that constitutes its memory. For example, we can use this to distinguish row-major and column-major representations.

An index function is represented as an LMAD.

The shape of an index function.

LMAD's representation consists of a general offset and for each dimension a stride, number of elements (or shape), and permutation. Note that the permutation is not strictly necessary in that the permutation can be performed directly on LMAD dimensions, but then it is difficult to extract the permutation back from an LMAD.

LMAD algebra is closed under composition w.r.t. operators such as permute, index and slice. However, other operations, such as reshape, cannot always be represented inside the LMAD algebra.

It follows that the general representation of an index function is a list of LMADS, in which each following LMAD in the list implicitly corresponds to an irregular reshaping operation.

However, we expect that the common case is when the index function is one LMAD -- we call this the "nice" representation.

Finally, the list of LMADs is kept in an IxFun together with the shape of the original array, and a bit to indicate whether the index function is contiguous, i.e., if we instantiate all the points of the current index function, do we get a contiguous memory interval?

By definition, the LMAD \( \sigma + \{ (n_1, s_1), \ldots, (n_k, s_k) \} \), where \(n\) and \(s\) denote the shape and stride of each dimension, denotes the set of points:

\[ \{ ~ \sigma + i_1 * s_1 + \ldots + i_m * s_m ~ | ~ 0 \leq i_1 < n_1, \ldots, 0 \leq i_m < n_m ~ \} \]

A single dimension in an LMAD.

Compute the flat memory index for a complete set inds of array indices and a certain element size elem_size.

Create a single-LMAD index function that is existential in everything, with the provided permutation.

iota.

Permute dimensions.

Reshape an index function.

There are four conditions that all must hold for the result of a reshape operation to remain in the one-LMAD domain:

1. the permutation of the underlying LMAD must leave unchanged the LMAD dimensions that were *not* reshape coercions.
2. the repetition of dimensions of the underlying LMAD must refer only to the coerced-dimensions of the reshape operation.

If any of these conditions do not hold, then the reshape operation will conservatively add a new LMAD to the list, leading to a representation that provides less opportunities for further analysis

Coerce an index function to look like it has a new shape. Dynamically the shape must be the same.

Slice an index function.

Flat-slice an index function.

Conceptually expand index function to be a particular slice of another by adjusting the offset and strides. Used for memory expansion.

The index space of the index function. This is the same as the shape of arrays that the index function supports.

The number of dimensions in the domain of the input function.

Is this is a row-major array?

Substitute a name with a PrimExp in an index function.

Substitute a name with a PrimExp in an LMAD.

Turn all the leaves of the index function into Exts. We require that there's only one LMAD, that the index function is contiguous, and the base shape has only one dimension.

When comparing index functions as part of the type check in KernelsMem, we may run into problems caused by the simplifier. As index functions can be generalized over if-then-else expressions, the simplifier might hoist some of the code from inside the if-then-else (computing the offset of an array, for instance), but now the type checker cannot verify that the generalized index function is valid, because some of the existentials are computed somewhere else. To Work around this, we've had to relax the KernelsMem type-checker a bit, specifically, we've introduced this function to verify whether two index functions are "close enough" that we can assume that they match. We use this instead of `ixfun1 == ixfun2` and hope that it's good enough.

Returns True if the two LMADs could be proven disjoint.

Uses some best-approximation heuristics to determine disjointness. For two 1-dimensional arrays, we can guarantee whether or not they are disjoint, but as soon as more than one dimension is involved, things get more tricky. Currently, we try to conservativelyFlatten any LMAD with more than one dimension.