futhark-0.19.5: An optimising compiler for a functional, array-oriented language.
Safe HaskellSafe-Inferred
LanguageHaskell2010

Futhark.IR.Mem.IxFun

Description

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

Synopsis

Documentation

data IxFun num Source #

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

Instances

Instances details
Functor IxFun Source # 
Instance details

Defined in Futhark.IR.Mem.IxFun

Methods

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

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

Foldable IxFun Source # 
Instance details

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 Source # 
Instance details

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) Source # 
Instance details

Defined in Futhark.IR.Mem.IxFun

Methods

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

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

Show num => Show (IxFun num) Source # 
Instance details

Defined in Futhark.IR.Mem.IxFun

Methods

showsPrec :: Int -> IxFun num -> ShowS #

show :: IxFun num -> String #

showList :: [IxFun num] -> ShowS #

Pretty num => Pretty (IxFun num) Source # 
Instance details

Defined in Futhark.IR.Mem.IxFun

Methods

ppr :: IxFun num -> Doc #

pprPrec :: Int -> IxFun num -> Doc #

pprList :: [IxFun num] -> Doc #

FreeIn num => FreeIn (IxFun num) Source # 
Instance details

Defined in Futhark.IR.Mem.IxFun

Methods

freeIn' :: IxFun num -> FV Source #

Substitute num => Substitute (IxFun num) Source # 
Instance details

Defined in Futhark.IR.Mem.IxFun

Methods

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

Substitute num => Rename (IxFun num) Source # 
Instance details

Defined in Futhark.IR.Mem.IxFun

Methods

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

data LMAD num Source #

LMAD's representation consists of a general offset and for each dimension a stride, rotate factor, 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

Instances

Instances details
Functor LMAD Source # 
Instance details

Defined in Futhark.IR.Mem.IxFun

Methods

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

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

Foldable LMAD Source # 
Instance details

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 Source # 
Instance details

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

Eq num => Eq (LMAD num) Source # 
Instance details

Defined in Futhark.IR.Mem.IxFun

Methods

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

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

Show num => Show (LMAD num) Source # 
Instance details

Defined in Futhark.IR.Mem.IxFun

Methods

showsPrec :: Int -> LMAD num -> ShowS #

show :: LMAD num -> String #

showList :: [LMAD num] -> ShowS #

Pretty num => Pretty (LMAD num) Source # 
Instance details

Defined in Futhark.IR.Mem.IxFun

Methods

ppr :: LMAD num -> Doc #

pprPrec :: Int -> LMAD num -> Doc #

pprList :: [LMAD num] -> Doc #

FreeIn num => FreeIn (LMAD num) Source # 
Instance details

Defined in Futhark.IR.Mem.IxFun

Methods

freeIn' :: LMAD num -> FV Source #

Substitute num => Substitute (LMAD num) Source # 
Instance details

Defined in Futhark.IR.Mem.IxFun

Methods

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

Substitute num => Rename (LMAD num) Source # 
Instance details

Defined in Futhark.IR.Mem.IxFun

Methods

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

data LMADDim num Source #

Constructors

LMADDim 

Fields

Instances

Instances details
Eq num => Eq (LMADDim num) Source # 
Instance details

Defined in Futhark.IR.Mem.IxFun

Methods

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

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

Show num => Show (LMADDim num) Source # 
Instance details

Defined in Futhark.IR.Mem.IxFun

Methods

showsPrec :: Int -> LMADDim num -> ShowS #

show :: LMADDim num -> String #

showList :: [LMADDim num] -> ShowS #

data Monotonicity Source #

Constructors

Inc 
Dec 
Unknown

monotonously increasing, decreasing or unknown

Instances

Instances details
Eq Monotonicity Source # 
Instance details

Defined in Futhark.IR.Mem.IxFun

Show Monotonicity Source # 
Instance details

Defined in Futhark.IR.Mem.IxFun

Pretty Monotonicity Source # 
Instance details

Defined in Futhark.IR.Mem.IxFun

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.

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

iota.

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

iota with offset.

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

Permute dimensions.

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

Rotate an index function.

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

Reshape an index function.

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

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 #

Shape of an index function.

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.

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

Is this is a row-major array?

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.

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

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)))) Source #

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.