Futhark.IR.Mem.IxFun

This module contains a representation for the index function based on linear-memory accessor descriptors; see Zhu, Hoeflinger and David work.

Documentation

data IxFun num

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 LMADs.

Constructors

IxFun

Fields

• ixfunLMADs :: NonEmpty (LMAD num)
• base :: Shape num

  the shape of the support array, i.e., the original array that birthed (is the start point) of this index function.

• contiguous :: Bool

  ignoring permutations, is the index function contiguous?

Instances

Foldable IxFun

Defined in Futhark.IR.Mem.IxFun

Methods

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

toList :: IxFun a -> [a]

null :: IxFun a -> Bool

length :: IxFun a -> Int

elem :: Eq a => a -> IxFun a -> Bool

maximum :: Ord a => IxFun a -> a

minimum :: Ord a => IxFun a -> a

sum :: Num a => IxFun a -> a

product :: Num a => IxFun a -> a

Traversable IxFun

Defined in Futhark.IR.Mem.IxFun

Methods

traverse :: Applicative f => (a -> f b) -> IxFun a -> f (IxFun b)

sequenceA :: Applicative f => IxFun (f a) -> f (IxFun a)

mapM :: Monad m => (a -> m b) -> IxFun a -> m (IxFun b)

sequence :: Monad m => IxFun (m a) -> m (IxFun a)

Functor IxFun

Defined in Futhark.IR.Mem.IxFun

Methods

fmap :: (a -> b) -> IxFun a -> IxFun b

(<$) :: a -> IxFun b -> IxFun a

Show num => Show (IxFun num)

Defined in Futhark.IR.Mem.IxFun

Methods

showsPrec :: Int -> IxFun num -> ShowS

show :: IxFun num -> String

showList :: [IxFun num] -> ShowS

FreeIn num => FreeIn (IxFun num)

Defined in Futhark.IR.Mem.IxFun

Methods

freeIn' :: IxFun num -> FV

Substitute num => Rename (IxFun num)

Defined in Futhark.IR.Mem.IxFun

Methods

rename :: IxFun num -> RenameM (IxFun num)

Substitute num => Substitute (IxFun num)

Defined in Futhark.IR.Mem.IxFun

Methods

substituteNames :: Map VName VName -> IxFun num -> IxFun num

Eq num => Eq (IxFun num)

Defined in Futhark.IR.Mem.IxFun

Methods

(==) :: IxFun num -> IxFun num -> Bool

(/=) :: IxFun num -> IxFun num -> Bool

Pretty num => Pretty (IxFun num)

Defined in Futhark.IR.Mem.IxFun

Methods

pretty :: IxFun num -> Doc ann

prettyList :: [IxFun num] -> Doc ann

type Shape num = [num]

The shape of an index function.

data LMAD num

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 denotes the set of points (simplified):

{ o + Sigma_{j=0}^{k} ((i_j+r_j) mod n_j)*s_j, forall i_j such that 0<=i_j<n_j, j=1..k }

Constructors

LMAD

Fields

• lmadOffset :: num
• lmadDims :: [LMADDim num]

Instances

Foldable LMAD

Defined in Futhark.IR.Mem.IxFun

Methods

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

toList :: LMAD a -> [a]

null :: LMAD a -> Bool

length :: LMAD a -> Int

elem :: Eq a => a -> LMAD a -> Bool

maximum :: Ord a => LMAD a -> a

minimum :: Ord a => LMAD a -> a

sum :: Num a => LMAD a -> a

product :: Num a => LMAD a -> a

Traversable LMAD

Defined in Futhark.IR.Mem.IxFun

Methods

traverse :: Applicative f => (a -> f b) -> LMAD a -> f (LMAD b)

sequenceA :: Applicative f => LMAD (f a) -> f (LMAD a)

mapM :: Monad m => (a -> m b) -> LMAD a -> m (LMAD b)

sequence :: Monad m => LMAD (m a) -> m (LMAD a)

Functor LMAD

Defined in Futhark.IR.Mem.IxFun

Methods

fmap :: (a -> b) -> LMAD a -> LMAD b

(<$) :: a -> LMAD b -> LMAD a

Show num => Show (LMAD num)

Defined in Futhark.IR.Mem.IxFun

Methods

showsPrec :: Int -> LMAD num -> ShowS

show :: LMAD num -> String

showList :: [LMAD num] -> ShowS

FreeIn num => FreeIn (LMAD num)

Defined in Futhark.IR.Mem.IxFun

Methods

freeIn' :: LMAD num -> FV

Substitute num => Rename (LMAD num)

Defined in Futhark.IR.Mem.IxFun

Methods

rename :: LMAD num -> RenameM (LMAD num)

Substitute num => Substitute (LMAD num)

Defined in Futhark.IR.Mem.IxFun

Methods

substituteNames :: Map VName VName -> LMAD num -> LMAD num

Eq num => Eq (LMAD num)

Defined in Futhark.IR.Mem.IxFun

Methods

(==) :: LMAD num -> LMAD num -> Bool

(/=) :: LMAD num -> LMAD num -> Bool

Ord num => Ord (LMAD num)

Defined in Futhark.IR.Mem.IxFun

Methods

compare :: LMAD num -> LMAD num -> Ordering

(<) :: LMAD num -> LMAD num -> Bool

(<=) :: LMAD num -> LMAD num -> Bool

(>) :: LMAD num -> LMAD num -> Bool

(>=) :: LMAD num -> LMAD num -> Bool

max :: LMAD num -> LMAD num -> LMAD num

min :: LMAD num -> LMAD num -> LMAD num

Pretty num => Pretty (LMAD num)

Defined in Futhark.IR.Mem.IxFun

Methods

pretty :: LMAD num -> Doc ann

prettyList :: [LMAD num] -> Doc ann

data LMADDim num

A single dimension in an LMAD.

Constructors

LMADDim

Fields

• ldStride :: num
• ldShape :: num
• ldPerm :: Int
• ldMon :: Monotonicity

Instances

Show num => Show (LMADDim num)

Defined in Futhark.IR.Mem.IxFun

Methods

showsPrec :: Int -> LMADDim num -> ShowS

show :: LMADDim num -> String

showList :: [LMADDim num] -> ShowS

FreeIn num => FreeIn (LMADDim num)

Defined in Futhark.IR.Mem.IxFun

Methods

freeIn' :: LMADDim num -> FV

Eq num => Eq (LMADDim num)

Defined in Futhark.IR.Mem.IxFun

Methods

(==) :: LMADDim num -> LMADDim num -> Bool

(/=) :: LMADDim num -> LMADDim num -> Bool

Ord num => Ord (LMADDim num)

Defined in Futhark.IR.Mem.IxFun

Methods

compare :: LMADDim num -> LMADDim num -> Ordering

(<) :: LMADDim num -> LMADDim num -> Bool

(<=) :: LMADDim num -> LMADDim num -> Bool

(>) :: LMADDim num -> LMADDim num -> Bool

(>=) :: LMADDim num -> LMADDim num -> Bool

max :: LMADDim num -> LMADDim num -> LMADDim num

min :: LMADDim num -> LMADDim num -> LMADDim num

data Monotonicity

The physical element ordering alongside a dimension, i.e. the sign of the stride.

Constructors

Inc

Increasing.

Dec

Decreasing.

Unknown

Unknown.

Instances

Show Monotonicity

Defined in Futhark.IR.Mem.IxFun

Methods

showsPrec :: Int -> Monotonicity -> ShowS

show :: Monotonicity -> String

showList :: [Monotonicity] -> ShowS

Eq Monotonicity

Defined in Futhark.IR.Mem.IxFun

Methods

(==) :: Monotonicity -> Monotonicity -> Bool

(/=) :: Monotonicity -> Monotonicity -> Bool

Ord Monotonicity

Defined in Futhark.IR.Mem.IxFun

Methods

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

Defined in Futhark.IR.Mem.IxFun

Methods

pretty :: Monotonicity -> Doc ann

prettyList :: [Monotonicity] -> Doc ann

index :: (IntegralExp num, Eq num) => IxFun num -> Indices num -> num

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)

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

iota :: IntegralExp num => Shape num -> IxFun num

iota.

iotaOffset :: IntegralExp num => num -> Shape num -> IxFun num

iota with offset.

permute :: IntegralExp num => IxFun num -> Permutation -> IxFun num

Permute dimensions.

reshape :: (Eq num, IntegralExp num) => IxFun num -> Shape num -> IxFun num

Reshape an index function.

coerce :: (Eq num, IntegralExp num) => IxFun num -> Shape num -> IxFun num

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

Slice an index function.

flatSlice :: (Eq num, IntegralExp num) => IxFun num -> FlatSlice num -> IxFun num

Flat-slice an index function.

rebase :: (Eq num, IntegralExp num) => IxFun num -> IxFun num -> IxFun num

Rebase an index function on top of a new base.

shape :: (Eq num, IntegralExp num) => IxFun num -> Shape num

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

lmadShape :: (Eq num, IntegralExp num) => LMAD num -> Shape num

Shape of an LMAD.

rank :: IntegralExp num => IxFun num -> Int

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

linearWithOffset :: (Eq num, IntegralExp num) => IxFun num -> num -> Maybe num

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)])

Similar restrictions to linearWithOffset except for transpositions, which are returned together with the offset.

isDirect :: (Eq num, IntegralExp num) => IxFun num -> Bool

Is this is a row-major array?

isLinear :: (Eq num, IntegralExp num) => IxFun num -> Bool

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)

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)

Substitute a name with a PrimExp in an LMAD.

existentialize :: IxFun (TPrimExp Int64 a) -> IxFun (TPrimExp Int64 (Ext b))

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.

closeEnough :: IxFun num -> IxFun num -> Bool

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

Returns true if two IxFuns 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

Is index function "analyzable", i.e., consists of one LMAD

permuteInv :: Permutation -> [a] -> [a]

conservativeFlatten :: LMAD (TPrimExp Int64 VName) -> Maybe (LMAD (TPrimExp Int64 VName))

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

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.

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

Dynamically determine if two LMAD are equal.

True if offset and constituent LMADDim are equal.