| Safe Haskell | None |
|---|---|
| Language | Haskell2010 |
Futhark.IR.Mem
Description
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:
- Memory blocks, which are Futhark values of type
Mem(parametrized with their size). These correspond to arbitrary blocks of memory, and are created using theAllocoperation. - 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.
Synopsis
- 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
- data MemInfo d u ret
- type MemBound u = MemInfo SubExp u MemBind
- data MemBind = ArrayIn VName IxFun
- data MemReturn
- type IxFun = IxFun (PrimExp VName)
- type ExtIxFun = IxFun (PrimExp (Ext VName))
- isStaticIxFun :: ExtIxFun -> Maybe IxFun
- type ExpReturns = MemInfo ExtSize NoUniqueness (Maybe MemReturn)
- type BodyReturns = MemInfo ExtSize NoUniqueness MemReturn
- type FunReturns = MemInfo ExtSize Uniqueness MemReturn
- noUniquenessReturns :: MemInfo d u r -> MemInfo d NoUniqueness r
- bodyReturnsToExpReturns :: BodyReturns -> ExpReturns
- type Mem lore = (AllocOp (Op lore), FParamInfo lore ~ FParamMem, LParamInfo lore ~ LParamMem, LetDec lore ~ LetDecMem, RetType lore ~ RetTypeMem, BranchType lore ~ BranchTypeMem, CanBeAliased (Op lore), ASTLore lore, Decorations lore, Checkable lore, OpReturns lore)
- class AllocOp op where
- class TypedOp (Op lore) => OpReturns lore where
- opReturns :: (Monad m, HasScope lore m) => Op lore -> m [ExpReturns]
- varReturns :: (HasScope lore m, Monad m, Mem lore) => VName -> m ExpReturns
- expReturns :: (Monad m, HasScope lore m, Mem lore) => Exp lore -> m [ExpReturns]
- extReturns :: [ExtType] -> [ExpReturns]
- lookupMemInfo :: (HasScope lore m, Mem lore) => VName -> m (MemInfo SubExp NoUniqueness MemBind)
- subExpMemInfo :: (HasScope lore m, Monad m, Mem lore) => SubExp -> m (MemInfo SubExp NoUniqueness MemBind)
- lookupArraySummary :: (Mem lore, HasScope lore m, Monad m) => VName -> m (VName, IxFun (PrimExp VName))
- existentialiseIxFun :: [VName] -> IxFun -> ExtIxFun
- matchBranchReturnType :: Mem lore => [BodyReturns] -> Body (Aliases lore) -> TypeM lore ()
- matchPatternToExp :: Mem lore => Pattern (Aliases lore) -> Exp (Aliases lore) -> TypeM lore ()
- matchFunctionReturnType :: Mem lore => [FunReturns] -> Result -> TypeM lore ()
- matchLoopResultMem :: Mem lore => [FParam (Aliases lore)] -> [FParam (Aliases lore)] -> [SubExp] -> TypeM lore ()
- bodyReturnsFromPattern :: PatternT (MemBound NoUniqueness) -> ([(VName, BodyReturns)], [(VName, BodyReturns)])
- checkMemInfo :: Checkable lore => VName -> MemInfo SubExp u MemBind -> TypeM lore ()
- module Futhark.IR.Prop
- module Futhark.IR.Traversals
- module Futhark.IR.Pretty
- module Futhark.IR.Syntax
- module Futhark.Analysis.PrimExp.Convert
Documentation
type RetTypeMem = FunReturns Source #
type BranchTypeMem = BodyReturns Source #
Constructors
| Alloc SubExp Space | Allocate a memory block. This really should not be an expression, but what are you gonna do... |
| Inner inner |
Instances
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. |
Instances
Memory information for an array bound somewhere in the program.
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
| Eq MemReturn Source # | |
| Ord MemReturn Source # | |
| Show MemReturn Source # | |
| Pretty MemReturn Source # | |
| FixExt MemReturn Source # | |
| IsRetType FunReturns Source # | |
Defined in Futhark.IR.Mem Methods primRetType :: PrimType -> FunReturns Source # applyRetType :: Typed dec => [FunReturns] -> [Param dec] -> [(SubExp, Type)] -> Maybe [FunReturns] Source # | |
| IsBodyType BodyReturns Source # | |
Defined in Futhark.IR.Mem Methods primBodyType :: PrimType -> BodyReturns Source # | |
| FreeIn MemReturn Source # | |
| Substitute MemReturn Source # | |
Defined in Futhark.IR.Mem | |
| Rename MemReturn Source # | |
| Simplifiable MemReturn Source # | |
Defined in Futhark.IR.Mem | |
| Simplifiable [FunReturns] Source # | |
Defined in Futhark.IR.Mem Methods simplify :: SimplifiableLore lore => [FunReturns] -> SimpleM lore [FunReturns] Source # | |
type IxFun = IxFun (PrimExp VName) Source #
The index function representation used for memory annotations.
type ExtIxFun = IxFun (PrimExp (Ext VName)) Source #
An index function that may contain existential variables.
type ExpReturns = MemInfo ExtSize NoUniqueness (Maybe MemReturn) Source #
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 Source #
The return of a body, which must always indicate where returned arrays are located.
type FunReturns = MemInfo ExtSize Uniqueness MemReturn Source #
The memory return of a function, which must always indicate where returned arrays are located.
noUniquenessReturns :: MemInfo d u r -> MemInfo d NoUniqueness r Source #
type Mem lore = (AllocOp (Op lore), FParamInfo lore ~ FParamMem, LParamInfo lore ~ LParamMem, LetDec lore ~ LetDecMem, RetType lore ~ RetTypeMem, BranchType lore ~ BranchTypeMem, CanBeAliased (Op lore), ASTLore lore, Decorations lore, Checkable lore, OpReturns lore) Source #
class TypedOp (Op lore) => OpReturns lore where Source #
Minimal complete definition
Nothing
Instances
| OpReturns SeqMem Source # | |
Defined in Futhark.IR.SeqMem | |
| OpReturns KernelsMem Source # | |
Defined in Futhark.IR.KernelsMem Methods opReturns :: (Monad m, HasScope KernelsMem m) => Op KernelsMem -> m [ExpReturns] Source # | |
varReturns :: (HasScope lore m, Monad m, Mem lore) => VName -> m ExpReturns Source #
expReturns :: (Monad m, HasScope lore m, Mem lore) => Exp lore -> m [ExpReturns] Source #
The return information of an expression. This can be seen as the "return type with memory annotations" of the expression.
extReturns :: [ExtType] -> [ExpReturns] Source #
lookupMemInfo :: (HasScope lore m, Mem lore) => VName -> m (MemInfo SubExp NoUniqueness MemBind) Source #
subExpMemInfo :: (HasScope lore m, Monad m, Mem lore) => SubExp -> m (MemInfo SubExp NoUniqueness MemBind) Source #
lookupArraySummary :: (Mem lore, HasScope lore m, Monad m) => VName -> m (VName, IxFun (PrimExp VName)) Source #
Type checking parts
matchBranchReturnType :: Mem lore => [BodyReturns] -> Body (Aliases lore) -> TypeM lore () Source #
matchPatternToExp :: Mem lore => Pattern (Aliases lore) -> Exp (Aliases lore) -> TypeM lore () Source #
matchFunctionReturnType :: Mem lore => [FunReturns] -> Result -> TypeM lore () Source #
matchLoopResultMem :: Mem lore => [FParam (Aliases lore)] -> [FParam (Aliases lore)] -> [SubExp] -> TypeM lore () Source #
bodyReturnsFromPattern :: PatternT (MemBound NoUniqueness) -> ([(VName, BodyReturns)], [(VName, BodyReturns)]) Source #
Module re-exports
module Futhark.IR.Prop
module Futhark.IR.Traversals
module Futhark.IR.Pretty
module Futhark.IR.Syntax