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
• ixfunContig :: Bool

  ignoring permutations, is the index function contiguous?

Instances

Functor IxFun

Defined in Futhark.IR.Mem.IxFun

Methods

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

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

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)

Eq num => Eq (IxFun num)

Defined in Futhark.IR.Mem.IxFun

Methods

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

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

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

Generic (IxFun num)

Defined in Futhark.IR.Mem.IxFun

Associated Types

type Rep (IxFun num) :: Type -> Type

Methods

from :: IxFun num -> Rep (IxFun num) x

to :: Rep (IxFun num) x -> IxFun num

Pretty num => Pretty (IxFun num)

Defined in Futhark.IR.Mem.IxFun

Methods

ppr :: IxFun num -> Doc

pprPrec :: Int -> IxFun num -> Doc

pprList :: [IxFun num] -> Doc

SexpIso num => SexpIso (IxFun num)

Defined in Futhark.IR.Mem.IxFun

Methods

sexpIso :: SexpGrammar (IxFun num)

FreeIn num => FreeIn (IxFun num)

Defined in Futhark.IR.Mem.IxFun

Methods

freeIn' :: IxFun num -> FV

Substitute num => Substitute (IxFun num)

Defined in Futhark.IR.Mem.IxFun

Methods

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

Substitute num => Rename (IxFun num)

Defined in Futhark.IR.Mem.IxFun

Methods

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

type Rep (IxFun num)

Defined in Futhark.IR.Mem.IxFun

type Rep (IxFun num)

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.

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.

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

Rotate an index function.

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

Reshape an index function.

slice :: (Eq num, IntegralExp num) => IxFun num -> Slice num -> IxFun num

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

Shape of an index function.

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.

leastGeneralGeneralization :: Eq v => IxFun (PrimExp v) -> IxFun (PrimExp v) -> Maybe (IxFun (PrimExp (Ext v)), [(PrimExp v, PrimExp v)])

Generalization (anti-unification)

Anti-unification of two index functions is supported under the following conditions: 0. Both index functions are represented by ONE lmad (assumed common case!) 1. The support array of the two indexfuns have the same dimensionality (we can relax this condition if we use a 1D support, as we probably should!) 2. The contiguous property and the per-dimension monotonicity are the same (otherwise we might loose important information; this can be relaxed!) 3. Most importantly, both index functions correspond to the same permutation (since the permutation is represented by INTs, this restriction cannot be relaxed, unless we move to a gated-LMAD representation!)

existentialize :: (IntExp t, Eq v, Pretty v) => IxFun (TPrimExp t v) -> State [TPrimExp t v] (Maybe (IxFun (TPrimExp t (Ext v))))

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.