Safe Haskell | Safe-Inferred |
---|---|
Language | Haskell2010 |
This module contains a representation for the index function based on linear-memory accessor descriptors; see Zhu, Hoeflinger and David work.
Synopsis
- data IxFun num = IxFun {
- ixfunLMADs :: NonEmpty (LMAD num)
- base :: Shape num
- contiguous :: Bool
- type Shape num = [num]
- data LMAD num = LMAD {
- lmadOffset :: num
- lmadDims :: [LMADDim num]
- data LMADDim num = LMADDim {}
- data Monotonicity
- index :: (IntegralExp num, Eq num) => IxFun num -> Indices num -> num
- mkExistential :: Int -> [(Int, Monotonicity)] -> Bool -> Int -> IxFun (Ext a)
- iota :: IntegralExp num => Shape num -> IxFun num
- iotaOffset :: IntegralExp num => num -> Shape num -> IxFun num
- permute :: IntegralExp num => IxFun num -> Permutation -> IxFun num
- reshape :: (Eq num, IntegralExp num) => IxFun num -> Shape num -> IxFun num
- coerce :: (Eq num, IntegralExp num) => IxFun num -> Shape num -> IxFun num
- slice :: (Eq num, IntegralExp num) => IxFun num -> Slice num -> IxFun num
- flatSlice :: (Eq num, IntegralExp num) => IxFun num -> FlatSlice num -> IxFun num
- rebase :: (Eq num, IntegralExp num) => IxFun num -> IxFun num -> IxFun num
- shape :: (Eq num, IntegralExp num) => IxFun num -> Shape num
- lmadShape :: (Eq num, IntegralExp num) => LMAD num -> Shape num
- rank :: IntegralExp num => IxFun num -> Int
- linearWithOffset :: (Eq num, IntegralExp num) => IxFun num -> num -> Maybe num
- rearrangeWithOffset :: (Eq num, IntegralExp num) => IxFun num -> num -> Maybe (num, [(Int, num)])
- isDirect :: (Eq num, IntegralExp num) => IxFun num -> Bool
- isLinear :: (Eq num, IntegralExp num) => IxFun num -> Bool
- substituteInIxFun :: Ord a => Map a (TPrimExp t a) -> IxFun (TPrimExp t a) -> IxFun (TPrimExp t a)
- substituteInLMAD :: Ord a => Map a (TPrimExp t a) -> LMAD (TPrimExp t a) -> LMAD (TPrimExp t a)
- existentialize :: IxFun (TPrimExp Int64 a) -> IxFun (TPrimExp Int64 (Ext b))
- closeEnough :: IxFun num -> IxFun num -> Bool
- equivalent :: Eq num => IxFun num -> IxFun num -> Bool
- hasOneLmad :: IxFun num -> Bool
- permuteInv :: Permutation -> [a] -> [a]
- conservativeFlatten :: LMAD (TPrimExp Int64 VName) -> Maybe (LMAD (TPrimExp Int64 VName))
- disjoint :: [(VName, PrimExp VName)] -> Names -> LMAD (TPrimExp Int64 VName) -> LMAD (TPrimExp Int64 VName) -> Bool
- disjoint2 :: scope -> asserts -> [(VName, PrimExp VName)] -> Names -> LMAD (TPrimExp Int64 VName) -> LMAD (TPrimExp Int64 VName) -> Bool
- disjoint3 :: Map VName Type -> [PrimExp VName] -> [(VName, PrimExp VName)] -> [PrimExp VName] -> LMAD (TPrimExp Int64 VName) -> LMAD (TPrimExp Int64 VName) -> Bool
- dynamicEqualsLMAD :: Eq num => LMAD (TPrimExp t num) -> LMAD (TPrimExp t num) -> TPrimExp Bool num
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 a sequence of LMAD
s.
IxFun | |
|
Instances
Foldable IxFun Source # | |
Defined in Futhark.IR.Mem.IxFun fold :: Monoid m => IxFun m -> m # foldMap :: Monoid m => (a -> m) -> IxFun a -> m # foldMap' :: Monoid m => (a -> m) -> IxFun a -> m # foldr :: (a -> b -> b) -> b -> IxFun a -> b # foldr' :: (a -> b -> b) -> b -> IxFun a -> b # foldl :: (b -> a -> b) -> b -> IxFun a -> b # foldl' :: (b -> a -> b) -> b -> IxFun a -> b # foldr1 :: (a -> a -> a) -> IxFun a -> a # foldl1 :: (a -> a -> a) -> IxFun a -> a # elem :: Eq a => a -> IxFun a -> Bool # maximum :: Ord a => IxFun a -> a # minimum :: Ord a => IxFun a -> a # | |
Traversable IxFun Source # | |
Functor IxFun Source # | |
Show num => Show (IxFun num) Source # | |
FreeIn num => FreeIn (IxFun num) Source # | |
Substitute num => Rename (IxFun num) Source # | |
Substitute num => Substitute (IxFun num) Source # | |
Defined in Futhark.IR.Mem.IxFun | |
Eq num => Eq (IxFun num) Source # | |
Pretty num => Pretty (IxFun num) Source # | |
Defined in Futhark.IR.Mem.IxFun |
LMAD's representation consists of a general offset and for each dimension a stride, number of elements (or shape), permutation, and monotonicity. 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 ~ \} \]
LMAD | |
|
Instances
Foldable LMAD Source # | |
Defined in Futhark.IR.Mem.IxFun fold :: Monoid m => LMAD m -> m # foldMap :: Monoid m => (a -> m) -> LMAD a -> m # foldMap' :: Monoid m => (a -> m) -> LMAD a -> m # foldr :: (a -> b -> b) -> b -> LMAD a -> b # foldr' :: (a -> b -> b) -> b -> LMAD a -> b # foldl :: (b -> a -> b) -> b -> LMAD a -> b # foldl' :: (b -> a -> b) -> b -> LMAD a -> b # foldr1 :: (a -> a -> a) -> LMAD a -> a # foldl1 :: (a -> a -> a) -> LMAD a -> a # elem :: Eq a => a -> LMAD a -> Bool # maximum :: Ord a => LMAD a -> a # | |
Traversable LMAD Source # | |
Functor LMAD Source # | |
Show num => Show (LMAD num) Source # | |
FreeIn num => FreeIn (LMAD num) Source # | |
Substitute num => Rename (LMAD num) Source # | |
Substitute num => Substitute (LMAD num) Source # | |
Defined in Futhark.IR.Mem.IxFun | |
Eq num => Eq (LMAD num) Source # | |
Ord num => Ord (LMAD num) Source # | |
Defined in Futhark.IR.Mem.IxFun | |
Pretty num => Pretty (LMAD num) Source # | |
Defined in Futhark.IR.Mem.IxFun |
A single dimension in an LMAD
.
Instances
Show num => Show (LMADDim num) Source # | |
FreeIn num => FreeIn (LMADDim num) Source # | |
Eq num => Eq (LMADDim num) Source # | |
Ord num => Ord (LMADDim num) Source # | |
Defined in Futhark.IR.Mem.IxFun |
data Monotonicity Source #
The physical element ordering alongside a dimension, i.e. the sign of the stride.
Instances
Show Monotonicity Source # | |
Defined in Futhark.IR.Mem.IxFun showsPrec :: Int -> Monotonicity -> ShowS # show :: Monotonicity -> String # showList :: [Monotonicity] -> ShowS # | |
Eq Monotonicity Source # | |
Defined in Futhark.IR.Mem.IxFun (==) :: Monotonicity -> Monotonicity -> Bool # (/=) :: Monotonicity -> Monotonicity -> Bool # | |
Ord Monotonicity Source # | |
Defined in Futhark.IR.Mem.IxFun compare :: Monotonicity -> Monotonicity -> Ordering # (<) :: Monotonicity -> Monotonicity -> Bool # (<=) :: Monotonicity -> Monotonicity -> Bool # (>) :: Monotonicity -> Monotonicity -> Bool # (>=) :: Monotonicity -> Monotonicity -> Bool # max :: Monotonicity -> Monotonicity -> Monotonicity # min :: Monotonicity -> Monotonicity -> Monotonicity # | |
Pretty Monotonicity Source # | |
Defined in Futhark.IR.Mem.IxFun pretty :: Monotonicity -> Doc ann # prettyList :: [Monotonicity] -> Doc ann # |
index :: (IntegralExp num, Eq num) => IxFun num -> Indices num -> num Source #
Compute the flat memory index for a complete set inds
of array indices
and a certain element size elem_size
.
mkExistential :: Int -> [(Int, Monotonicity)] -> Bool -> Int -> IxFun (Ext a) Source #
Create a contiguous single-LMAD index function that is existential in everything, with the provided permutation, monotonicity, and contiguousness.
iotaOffset :: IntegralExp num => num -> Shape num -> IxFun num Source #
iota with offset.
reshape :: (Eq num, IntegralExp num) => IxFun num -> Shape num -> IxFun num Source #
Reshape an index function.
coerce :: (Eq num, IntegralExp num) => IxFun num -> Shape num -> IxFun num Source #
Coerce an index function to look like it has a new shape. Dynamically the shape must be the same.
slice :: (Eq num, IntegralExp num) => IxFun num -> Slice num -> IxFun num Source #
Slice an index function.
flatSlice :: (Eq num, IntegralExp num) => IxFun num -> FlatSlice num -> IxFun num Source #
Flat-slice an index function.
rebase :: (Eq num, IntegralExp num) => IxFun num -> IxFun num -> IxFun num Source #
Rebase an index function on top of a new base.
shape :: (Eq num, IntegralExp num) => IxFun num -> Shape num Source #
The index space of the index function. This is the same as the shape of arrays that the index function supports.
rank :: IntegralExp num => IxFun num -> Int Source #
The number of dimensions in the domain of the input function.
linearWithOffset :: (Eq num, IntegralExp num) => IxFun num -> num -> Maybe num Source #
If the memory support of the index function is contiguous and row-major (i.e., no transpositions, repetitions, rotates, etc.), then this should return the offset from which the memory-support of this index function starts.
rearrangeWithOffset :: (Eq num, IntegralExp num) => IxFun num -> num -> Maybe (num, [(Int, num)]) Source #
Similar restrictions to linearWithOffset
except for transpositions, which
are returned together with the offset.
isLinear :: (Eq num, IntegralExp num) => IxFun num -> Bool Source #
Is this a row-major array starting at offset zero?
substituteInIxFun :: Ord a => Map a (TPrimExp t a) -> IxFun (TPrimExp t a) -> IxFun (TPrimExp t a) Source #
Substitute a name with a PrimExp in an index function.
substituteInLMAD :: Ord a => Map a (TPrimExp t a) -> LMAD (TPrimExp t a) -> LMAD (TPrimExp t a) Source #
Substitute a name with a PrimExp in an LMAD.
existentialize :: IxFun (TPrimExp Int64 a) -> IxFun (TPrimExp Int64 (Ext b)) Source #
Turn all the leaves of the index function into Ext
s. We
require that there's only one LMAD, that the index function is
contiguous, and the base shape has only one dimension.
closeEnough :: IxFun num -> IxFun num -> Bool Source #
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.
equivalent :: Eq num => IxFun num -> IxFun num -> Bool Source #
Returns true if two IxFun
s are equivalent.
Equivalence in this case is defined as having the same number of LMADs, with each pair of LMADs matching in permutation, offsets, strides and rotations.
hasOneLmad :: IxFun num -> Bool Source #
Is index function "analyzable", i.e., consists of one LMAD
permuteInv :: Permutation -> [a] -> [a] Source #
conservativeFlatten :: LMAD (TPrimExp Int64 VName) -> Maybe (LMAD (TPrimExp Int64 VName)) Source #
Conservatively flatten a list of LMAD dimensions
Since not all LMADs can actually be flattened, we try to overestimate the flattened array instead. This means that any "holes" in betwen dimensions will get filled out. conservativeFlatten :: (IntegralExp e, Ord e, Pretty e) => LMAD e -> LMAD e
disjoint :: [(VName, PrimExp VName)] -> Names -> LMAD (TPrimExp Int64 VName) -> LMAD (TPrimExp Int64 VName) -> Bool Source #
Returns True
if the two LMAD
s 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.
disjoint2 :: scope -> asserts -> [(VName, PrimExp VName)] -> Names -> LMAD (TPrimExp Int64 VName) -> LMAD (TPrimExp Int64 VName) -> Bool Source #