Futhark.IR.Mem

Building blocks for defining representations where every array is given information about which memory block is it based in, and how array elements map to memory block offsets.

There are two primary concepts you will need to understand:

1. Memory blocks, which are Futhark values of type Mem (parametrized with their size). These correspond to arbitrary blocks of memory, and are created using the Alloc operation.
2. Index functions, which describe a mapping from the index space of an array (eg. a two-dimensional space for an array of type [[int]]) to a one-dimensional offset into a memory block. Thus, index functions describe how arbitrary-dimensional arrays are mapped to the single-dimensional world of memory.

At a conceptual level, imagine that we have a two-dimensional array a of 32-bit integers, consisting of n rows of m elements each. This array could be represented in classic row-major format with an index function like the following:

  f(i,j) = i * m + j

When we want to know the location of element a[2,3], we simply call the index function as f(2,3) and obtain 2*m+3. We could also have chosen another index function, one that represents the array in column-major (or "transposed") format:

  f(i,j) = j * n + i

Index functions are not Futhark-level functions, but a special construct that the final code generator will eventually use to generate concrete access code. By modifying the index functions we can change how an array is represented in memory, which can permit memory access pattern optimisations.

Every time we bind an array, whether in a let-binding, loop merge parameter, or lambda parameter, we have an annotation specifying a memory block and an index function. In some cases, such as let-bindings for many expressions, we are free to specify an arbitrary index function and memory block - for example, we get to decide where Copy stores its result - but in other cases the type rules of the expression chooses for us. For example, Index always produces an array in the same memory block as its input, and with the same index function, except with some indices fixed.

Documentation

type LetDecMem = MemInfo SubExp NoUniqueness MemBind

type FParamMem = MemInfo SubExp Uniqueness MemBind

type LParamMem = MemInfo SubExp NoUniqueness MemBind

type RetTypeMem = FunReturns

type BranchTypeMem = BodyReturns

data MemOp (inner :: Type -> Type) (rep :: Type)

Constructors

Alloc SubExp Space

Allocate a memory block.

Inner (inner rep)

Instances

CanBeAliased inner => CanBeAliased (MemOp inner)

Defined in Futhark.IR.Mem

Methods

addOpAliases :: AliasableRep rep => AliasTable -> MemOp inner rep -> MemOp inner (Aliases rep)

RephraseOp inner => RephraseOp (MemOp inner)

Defined in Futhark.IR.Mem

Methods

rephraseInOp :: Monad m => Rephraser m from to -> MemOp inner from -> m (MemOp inner to)

CanBeWise inner => CanBeWise (MemOp inner)

Defined in Futhark.IR.Mem

Methods

addOpWisdom :: Informing rep => MemOp inner rep -> MemOp inner (Wise rep)

Show (inner rep) => Show (MemOp inner rep)

Defined in Futhark.IR.Mem

Methods

showsPrec :: Int -> MemOp inner rep -> ShowS

show :: MemOp inner rep -> String

showList :: [MemOp inner rep] -> ShowS

OpMetrics (inner rep) => OpMetrics (MemOp inner rep)

Defined in Futhark.IR.Mem

Methods

opMetrics :: MemOp inner rep -> MetricsM ()

IndexOp (inner rep) => IndexOp (MemOp inner rep)

Defined in Futhark.IR.Mem

Methods

indexOp :: (ASTRep rep0, IndexOp (Op rep0)) => SymbolTable rep0 -> Int -> MemOp inner rep -> [TPrimExp Int64 VName] -> Maybe Indexed

OpReturns (inner rep) => OpReturns (MemOp inner rep)

Defined in Futhark.IR.Mem

Methods

opReturns :: forall rep0 (inner0 :: Type -> Type) m. (Mem rep0 inner0, Monad m, HasScope rep0 m) => MemOp inner rep -> m [ExpReturns]

IsOp (inner rep) => IsOp (MemOp inner rep)

Defined in Futhark.IR.Mem

Methods

safeOp :: MemOp inner rep -> Bool

cheapOp :: MemOp inner rep -> Bool

opDependencies :: MemOp inner rep -> [Names]

AliasedOp (inner rep) => AliasedOp (MemOp inner rep)

Defined in Futhark.IR.Mem

Methods

opAliases :: MemOp inner rep -> [Names]

consumedInOp :: MemOp inner rep -> Names

FreeIn (inner rep) => FreeIn (MemOp inner rep)

Defined in Futhark.IR.Mem

Methods

freeIn' :: MemOp inner rep -> FV

TypedOp (inner rep) => TypedOp (MemOp inner rep)

Defined in Futhark.IR.Mem

Methods

opType :: HasScope t m => MemOp inner rep -> m [ExtType]

CSEInOp (op rep) => CSEInOp (MemOp op rep)

Defined in Futhark.Optimise.CSE

Methods

cseInOp :: MemOp op rep -> CSEM rep0 (MemOp op rep)

SizeSubst (op rep) => SizeSubst (MemOp op rep)

Defined in Futhark.Pass.ExplicitAllocations

Methods

opIsConst :: MemOp op rep -> Bool

Rename (inner rep) => Rename (MemOp inner rep)

Defined in Futhark.IR.Mem

Methods

rename :: MemOp inner rep -> RenameM (MemOp inner rep)

Substitute (inner rep) => Substitute (MemOp inner rep)

Defined in Futhark.IR.Mem

Methods

substituteNames :: Map VName VName -> MemOp inner rep -> MemOp inner rep

Eq (inner rep) => Eq (MemOp inner rep)

Defined in Futhark.IR.Mem

Methods

(==) :: MemOp inner rep -> MemOp inner rep -> Bool

(/=) :: MemOp inner rep -> MemOp inner rep -> Bool

Ord (inner rep) => Ord (MemOp inner rep)

Defined in Futhark.IR.Mem

Methods

compare :: MemOp inner rep -> MemOp inner rep -> Ordering

(<) :: MemOp inner rep -> MemOp inner rep -> Bool

(<=) :: MemOp inner rep -> MemOp inner rep -> Bool

(>) :: MemOp inner rep -> MemOp inner rep -> Bool

(>=) :: MemOp inner rep -> MemOp inner rep -> Bool

max :: MemOp inner rep -> MemOp inner rep -> MemOp inner rep

min :: MemOp inner rep -> MemOp inner rep -> MemOp inner rep

Pretty (inner rep) => Pretty (MemOp inner rep)

Defined in Futhark.IR.Mem

Methods

pretty :: MemOp inner rep -> Doc ann

prettyList :: [MemOp inner rep] -> Doc ann

traverseMemOpStms :: Monad m => OpStmsTraverser m (inner rep) rep -> OpStmsTraverser m (MemOp inner rep) rep

A helper for defining TraverseOpStms.

data MemInfo d u ret

A summary of the memory information for every let-bound identifier, function parameter, and return value. Parameterisered over uniqueness, dimension, and auxiliary array information.

Constructors

MemPrim PrimType

A primitive value.

MemMem Space

A memory block.

MemArray PrimType (ShapeBase d) u ret

The array is stored in the named memory block, and with the given index function. The index function maps indices in the array to element offset, not byte offsets! To translate to byte offsets, multiply the offset with the size of the array element type.

MemAcc VName Shape [Type] u

An accumulator, which is not stored anywhere.

Instances

HasLetDecMem LetDecMem

Defined in Futhark.IR.Mem

Methods

letDecMem :: LetDecMem -> LetDecMem

IsBodyType BodyReturns

Defined in Futhark.IR.Mem

Methods

primBodyType :: PrimType -> BodyReturns

IsRetType FunReturns

Defined in Futhark.IR.Mem

Methods

primRetType :: PrimType -> FunReturns

applyRetType :: Typed dec => [FunReturns] -> [Param dec] -> [(SubExp, Type)] -> Maybe [FunReturns]

Simplifiable [FunReturns]

Defined in Futhark.IR.Mem

Methods

simplify :: SimplifiableRep rep => [FunReturns] -> SimpleM rep [FunReturns]

(Show d, Show ret, Show u) => Show (MemInfo d u ret)

Defined in Futhark.IR.Mem

Methods

showsPrec :: Int -> MemInfo d u ret -> ShowS

show :: MemInfo d u ret -> String

showList :: [MemInfo d u ret] -> ShowS

(FreeIn d, FreeIn ret) => FreeIn (MemInfo d u ret)

Defined in Futhark.IR.Mem

Methods

freeIn' :: MemInfo d u ret -> FV

FixExt ret => DeclExtTyped (MemInfo ExtSize Uniqueness ret)

Defined in Futhark.IR.Mem

Methods

declExtTypeOf :: MemInfo ExtSize Uniqueness ret -> DeclExtType

DeclTyped (MemInfo SubExp Uniqueness ret)

Defined in Futhark.IR.Mem

Methods

declTypeOf :: MemInfo SubExp Uniqueness ret -> DeclType

FixExt ret => ExtTyped (MemInfo ExtSize NoUniqueness ret)

Defined in Futhark.IR.Mem

Methods

extTypeOf :: MemInfo ExtSize NoUniqueness ret -> ExtType

FixExt ret => ExtTyped (MemInfo ExtSize Uniqueness ret)

Defined in Futhark.IR.Mem

Methods

extTypeOf :: MemInfo ExtSize Uniqueness ret -> ExtType

FixExt ret => FixExt (MemInfo ExtSize u ret)

Defined in Futhark.IR.Mem

Methods

fixExt :: Int -> SubExp -> MemInfo ExtSize u ret -> MemInfo ExtSize u ret

Typed (MemInfo SubExp NoUniqueness ret)

Defined in Futhark.IR.Mem

Methods

typeOf :: MemInfo SubExp NoUniqueness ret -> Type

Typed (MemInfo SubExp Uniqueness ret)

Defined in Futhark.IR.Mem

Methods

typeOf :: MemInfo SubExp Uniqueness ret -> Type

(Simplifiable d, Simplifiable ret) => Simplifiable (MemInfo d u ret)

Defined in Futhark.IR.Mem

Methods

simplify :: SimplifiableRep rep => MemInfo d u ret -> SimpleM rep (MemInfo d u ret)

(Substitute d, Substitute ret) => Rename (MemInfo d u ret)

Defined in Futhark.IR.Mem

Methods

rename :: MemInfo d u ret -> RenameM (MemInfo d u ret)

(Substitute d, Substitute ret) => Substitute (MemInfo d u ret)

Defined in Futhark.IR.Mem

Methods

substituteNames :: Map VName VName -> MemInfo d u ret -> MemInfo d u ret

(Eq d, Eq ret, Eq u) => Eq (MemInfo d u ret)

Defined in Futhark.IR.Mem

Methods

(==) :: MemInfo d u ret -> MemInfo d u ret -> Bool

(/=) :: MemInfo d u ret -> MemInfo d u ret -> Bool

(Ord d, Ord ret, Ord u) => Ord (MemInfo d u ret)

Defined in Futhark.IR.Mem

Methods

compare :: MemInfo d u ret -> MemInfo d u ret -> Ordering

(<) :: MemInfo d u ret -> MemInfo d u ret -> Bool

(<=) :: MemInfo d u ret -> MemInfo d u ret -> Bool

(>) :: MemInfo d u ret -> MemInfo d u ret -> Bool

(>=) :: MemInfo d u ret -> MemInfo d u ret -> Bool

max :: MemInfo d u ret -> MemInfo d u ret -> MemInfo d u ret

min :: MemInfo d u ret -> MemInfo d u ret -> MemInfo d u ret

(Pretty (ShapeBase d), Pretty (TypeBase (ShapeBase d) u), Pretty d, Pretty u, Pretty ret) => Pretty (MemInfo d u ret)

Defined in Futhark.IR.Mem

Methods

pretty :: MemInfo d u ret -> Doc ann

prettyList :: [MemInfo d u ret] -> Doc ann

type MemBound u = MemInfo SubExp u MemBind

data MemBind

Memory information for an array bound somewhere in the program.

Constructors

ArrayIn VName IxFun

Located in this memory block with this index function.

Instances

Show MemBind

Defined in Futhark.IR.Mem

Methods

showsPrec :: Int -> MemBind -> ShowS

show :: MemBind -> String

showList :: [MemBind] -> ShowS

HasLetDecMem LetDecMem

Defined in Futhark.IR.Mem

Methods

letDecMem :: LetDecMem -> LetDecMem

FreeIn MemBind

Defined in Futhark.IR.Mem

Methods

freeIn' :: MemBind -> FV

Simplifiable MemBind

Defined in Futhark.IR.Mem

Methods

simplify :: SimplifiableRep rep => MemBind -> SimpleM rep MemBind

Rename MemBind

Defined in Futhark.IR.Mem

Methods

rename :: MemBind -> RenameM MemBind

Substitute MemBind

Defined in Futhark.IR.Mem

Methods

substituteNames :: Map VName VName -> MemBind -> MemBind

Eq MemBind

Defined in Futhark.IR.Mem

Methods

(==) :: MemBind -> MemBind -> Bool

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

Ord MemBind

Defined in Futhark.IR.Mem

Methods

compare :: MemBind -> MemBind -> Ordering

(<) :: MemBind -> MemBind -> Bool

(<=) :: MemBind -> MemBind -> Bool

(>) :: MemBind -> MemBind -> Bool

(>=) :: MemBind -> MemBind -> Bool

max :: MemBind -> MemBind -> MemBind

min :: MemBind -> MemBind -> MemBind

Pretty MemBind

Defined in Futhark.IR.Mem

Methods

pretty :: MemBind -> Doc ann

prettyList :: [MemBind] -> Doc ann

data MemReturn

A description of the memory properties of an array being returned by an operation.

Constructors

ReturnsInBlock VName ExtIxFun

The array is located in a memory block that is already in scope.

ReturnsNewBlock Space Int ExtIxFun

The operation returns a new (existential) memory block.

Instances

Show MemReturn

Defined in Futhark.IR.Mem

Methods

showsPrec :: Int -> MemReturn -> ShowS

show :: MemReturn -> String

showList :: [MemReturn] -> ShowS

FreeIn MemReturn

Defined in Futhark.IR.Mem

Methods

freeIn' :: MemReturn -> FV

FixExt MemReturn

Defined in Futhark.IR.Mem

Methods

fixExt :: Int -> SubExp -> MemReturn -> MemReturn

IsBodyType BodyReturns

Defined in Futhark.IR.Mem

Methods

primBodyType :: PrimType -> BodyReturns

IsRetType FunReturns

Defined in Futhark.IR.Mem

Methods

primRetType :: PrimType -> FunReturns

applyRetType :: Typed dec => [FunReturns] -> [Param dec] -> [(SubExp, Type)] -> Maybe [FunReturns]

Simplifiable MemReturn

Defined in Futhark.IR.Mem

Methods

simplify :: SimplifiableRep rep => MemReturn -> SimpleM rep MemReturn

Rename MemReturn

Defined in Futhark.IR.Mem

Methods

rename :: MemReturn -> RenameM MemReturn

Substitute MemReturn

Defined in Futhark.IR.Mem

Methods

substituteNames :: Map VName VName -> MemReturn -> MemReturn

Eq MemReturn

Defined in Futhark.IR.Mem

Methods

(==) :: MemReturn -> MemReturn -> Bool

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

Ord MemReturn

Defined in Futhark.IR.Mem

Methods

compare :: MemReturn -> MemReturn -> Ordering

(<) :: MemReturn -> MemReturn -> Bool

(<=) :: MemReturn -> MemReturn -> Bool

(>) :: MemReturn -> MemReturn -> Bool

(>=) :: MemReturn -> MemReturn -> Bool

max :: MemReturn -> MemReturn -> MemReturn

min :: MemReturn -> MemReturn -> MemReturn

Pretty MemReturn

Defined in Futhark.IR.Mem

Methods

pretty :: MemReturn -> Doc ann

prettyList :: [MemReturn] -> Doc ann

Simplifiable [FunReturns]

Defined in Futhark.IR.Mem

Methods

simplify :: SimplifiableRep rep => [FunReturns] -> SimpleM rep [FunReturns]

type IxFun = IxFun (TPrimExp Int64 VName)

The index function representation used for memory annotations.

type ExtIxFun = IxFun (TPrimExp Int64 (Ext VName))

An index function that may contain existential variables.

type LMAD = LMAD (TPrimExp Int64 VName)

The LMAD representation used for memory annotations.

isStaticIxFun :: ExtIxFun -> Maybe IxFun

type ExpReturns = MemInfo ExtSize NoUniqueness (Maybe MemReturn)

The memory return of an expression. An array is annotated with Maybe MemReturn, which can be interpreted as the expression either dictating exactly where the array is located when it is returned (if Just), or able to put it whereever the binding prefers (if Nothing).

This is necessary to capture the difference between an expression that is just an array-typed variable, in which the array being "returned" is located where it already is, and a copy expression, whose entire purpose is to store an existing array in some arbitrary location. This is a consequence of the design decision never to have implicit memory copies.

type BodyReturns = MemInfo ExtSize NoUniqueness MemReturn

The return of a body, which must always indicate where returned arrays are located.

type FunReturns = MemInfo ExtSize Uniqueness MemReturn

The memory return of a function, which must always indicate where returned arrays are located.

noUniquenessReturns :: MemInfo d u r -> MemInfo d NoUniqueness r

bodyReturnsToExpReturns :: BodyReturns -> ExpReturns

type Mem rep inner = (FParamInfo rep ~ FParamMem, LParamInfo rep ~ LParamMem, HasLetDecMem (LetDec rep), RetType rep ~ RetTypeMem, BranchType rep ~ BranchTypeMem, ASTRep rep, OpReturns (inner rep), RephraseOp inner, Op rep ~ MemOp inner rep)

class HasLetDecMem t where

The class of pattern element decorators that contain memory information.

Methods

letDecMem :: t -> LetDecMem

Instances

HasLetDecMem LetDecMem

Defined in Futhark.IR.Mem

Methods

letDecMem :: LetDecMem -> LetDecMem

HasLetDecMem b => HasLetDecMem (a, b)

Defined in Futhark.IR.Mem

Methods

letDecMem :: (a, b) -> LetDecMem

class IsOp op => OpReturns op where

Minimal complete definition

Nothing

Methods

opReturns :: (Mem rep inner, Monad m, HasScope rep m) => op -> m [ExpReturns]

Instances

OpReturns (HostOp (NoOp :: Type -> Type) (Aliases GPUMem))

Defined in Futhark.IR.GPUMem

Methods

opReturns :: forall rep (inner :: Type -> Type) m. (Mem rep inner, Monad m, HasScope rep m) => HostOp NoOp (Aliases GPUMem) -> m [ExpReturns]

OpReturns (HostOp (NoOp :: Type -> Type) GPUMem)

Defined in Futhark.IR.GPUMem

Methods

opReturns :: forall rep (inner :: Type -> Type) m. (Mem rep inner, Monad m, HasScope rep m) => HostOp NoOp GPUMem -> m [ExpReturns]

OpReturns (HostOp (NoOp :: Type -> Type) (Wise GPUMem))

Defined in Futhark.IR.GPUMem

Methods

opReturns :: forall rep (inner :: Type -> Type) m. (Mem rep inner, Monad m, HasScope rep m) => HostOp NoOp (Wise GPUMem) -> m [ExpReturns]

OpReturns (MCOp (NoOp :: Type -> Type) (Aliases MCMem))

Defined in Futhark.IR.MCMem

Methods

opReturns :: forall rep (inner :: Type -> Type) m. (Mem rep inner, Monad m, HasScope rep m) => MCOp NoOp (Aliases MCMem) -> m [ExpReturns]

OpReturns (MCOp (NoOp :: Type -> Type) MCMem)

Defined in Futhark.IR.MCMem

Methods

opReturns :: forall rep (inner :: Type -> Type) m. (Mem rep inner, Monad m, HasScope rep m) => MCOp NoOp MCMem -> m [ExpReturns]

OpReturns (MCOp (NoOp :: Type -> Type) (Wise MCMem))

Defined in Futhark.IR.MCMem

Methods

opReturns :: forall rep (inner :: Type -> Type) m. (Mem rep inner, Monad m, HasScope rep m) => MCOp NoOp (Wise MCMem) -> m [ExpReturns]

OpReturns (inner rep) => OpReturns (MemOp inner rep)

Defined in Futhark.IR.Mem

Methods

opReturns :: forall rep0 (inner0 :: Type -> Type) m. (Mem rep0 inner0, Monad m, HasScope rep0 m) => MemOp inner rep -> m [ExpReturns]

OpReturns (NoOp rep)

Defined in Futhark.IR.Mem

Methods

opReturns :: forall rep0 (inner :: Type -> Type) m. (Mem rep0 inner, Monad m, HasScope rep0 m) => NoOp rep -> m [ExpReturns]

varReturns :: (HasScope rep m, Monad m, Mem rep inner) => VName -> m ExpReturns

expReturns :: (LocalScope rep m, Mem rep inner) => Exp rep -> m (Maybe [ExpReturns])

The return information of an expression. This can be seen as the "return type with memory annotations" of the expression.

This can produce Nothing, which signifies that the result is an array layout that is not expressible as an index function.

extReturns :: [ExtType] -> [ExpReturns]

lookupMemInfo :: (HasScope rep m, Mem rep inner) => VName -> m (MemInfo SubExp NoUniqueness MemBind)

subExpMemInfo :: (HasScope rep m, Mem rep inner) => SubExp -> m (MemInfo SubExp NoUniqueness MemBind)

lookupArraySummary :: (Mem rep inner, HasScope rep m, Monad m) => VName -> m (VName, IxFun (TPrimExp Int64 VName))

lookupMemSpace :: (Mem rep inner, HasScope rep m, Monad m) => VName -> m Space

existentialiseIxFun :: [VName] -> IxFun -> ExtIxFun

Type checking parts

matchBranchReturnType :: (Mem rep inner, Checkable rep) => [BodyReturns] -> Body (Aliases rep) -> TypeM rep ()

matchPatToExp :: (Mem rep inner, LetDec rep ~ LetDecMem, Checkable rep) => Pat (LetDec (Aliases rep)) -> Exp (Aliases rep) -> TypeM rep ()

matchFunctionReturnType :: (Mem rep inner, Checkable rep) => [FunReturns] -> Result -> TypeM rep ()

matchLoopResultMem :: (Mem rep inner, Checkable rep) => [FParam (Aliases rep)] -> Result -> TypeM rep ()

bodyReturnsFromPat :: Pat (MemBound NoUniqueness) -> [(VName, BodyReturns)]

checkMemInfo :: Checkable rep => VName -> MemInfo SubExp u MemBind -> TypeM rep ()

Module re-exports

module Futhark.IR.Prop

module Futhark.IR.Traversals

module Futhark.IR.Pretty

module Futhark.IR.Syntax

module Futhark.Analysis.PrimExp.Convert