futhark-0.9.1: An optimising compiler for a functional, array-oriented language.

Safe HaskellNone
LanguageHaskell2010

Futhark.Representation.ExplicitMemory

Contents

Description

This representation requires that every array is given information about which memory block is it based in, and how array elements map to memory block offsets. The representation is based on the kernels representation, so nested parallelism does not occur.

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.

Synopsis

The Lore definition

data ExplicitMemory Source #

A lore containing explicit memory information.

Instances
Annotations ExplicitMemory Source # 
Instance details

Defined in Futhark.Representation.ExplicitMemory

PrettyLore ExplicitMemory Source # 
Instance details

Defined in Futhark.Representation.ExplicitMemory

Attributes ExplicitMemory Source # 
Instance details

Defined in Futhark.Representation.ExplicitMemory

BinderOps ExplicitMemory Source # 
Instance details

Defined in Futhark.Pass.ExplicitAllocations

Checkable ExplicitMemory Source # 
Instance details

Defined in Futhark.Representation.ExplicitMemory

CheckableOp ExplicitMemory Source # 
Instance details

Defined in Futhark.Representation.ExplicitMemory

FullWalkAliases ExplicitMemory Source # 
Instance details

Defined in Futhark.Optimise.MemoryBlockMerging.Miscellaneous

FullWalk ExplicitMemory Source # 
Instance details

Defined in Futhark.Optimise.MemoryBlockMerging.Miscellaneous

FullMap ExplicitMemory Source # 
Instance details

Defined in Futhark.Optimise.MemoryBlockMerging.Miscellaneous

BinderOps (Wise ExplicitMemory) Source # 
Instance details

Defined in Futhark.Pass.ExplicitAllocations

type LetAttr ExplicitMemory Source # 
Instance details

Defined in Futhark.Representation.ExplicitMemory

type ExpAttr ExplicitMemory Source # 
Instance details

Defined in Futhark.Representation.ExplicitMemory

type BodyAttr ExplicitMemory Source # 
Instance details

Defined in Futhark.Representation.ExplicitMemory

type FParamAttr ExplicitMemory Source # 
Instance details

Defined in Futhark.Representation.ExplicitMemory

type LParamAttr ExplicitMemory Source # 
Instance details

Defined in Futhark.Representation.ExplicitMemory

type RetType ExplicitMemory Source # 
Instance details

Defined in Futhark.Representation.ExplicitMemory

type BranchType ExplicitMemory Source # 
Instance details

Defined in Futhark.Representation.ExplicitMemory

type Op ExplicitMemory Source # 
Instance details

Defined in Futhark.Representation.ExplicitMemory

data InKernel Source #

Instances
Annotations InKernel Source # 
Instance details

Defined in Futhark.Representation.ExplicitMemory

PrettyLore InKernel Source # 
Instance details

Defined in Futhark.Representation.ExplicitMemory

Attributes InKernel Source # 
Instance details

Defined in Futhark.Representation.ExplicitMemory

Checkable InKernel Source # 
Instance details

Defined in Futhark.Representation.ExplicitMemory

CheckableOp InKernel Source # 
Instance details

Defined in Futhark.Representation.ExplicitMemory

FullWalkAliases InKernel Source # 
Instance details

Defined in Futhark.Optimise.MemoryBlockMerging.Miscellaneous

FullWalk InKernel Source # 
Instance details

Defined in Futhark.Optimise.MemoryBlockMerging.Miscellaneous

FullMap InKernel Source # 
Instance details

Defined in Futhark.Optimise.MemoryBlockMerging.Miscellaneous

type LetAttr InKernel Source # 
Instance details

Defined in Futhark.Representation.ExplicitMemory

type ExpAttr InKernel Source # 
Instance details

Defined in Futhark.Representation.ExplicitMemory

type ExpAttr InKernel = ()
type BodyAttr InKernel Source # 
Instance details

Defined in Futhark.Representation.ExplicitMemory

type BodyAttr InKernel = ()
type FParamAttr InKernel Source # 
Instance details

Defined in Futhark.Representation.ExplicitMemory

type LParamAttr InKernel Source # 
Instance details

Defined in Futhark.Representation.ExplicitMemory

type RetType InKernel Source # 
Instance details

Defined in Futhark.Representation.ExplicitMemory

type BranchType InKernel Source # 
Instance details

Defined in Futhark.Representation.ExplicitMemory

type Op InKernel Source # 
Instance details

Defined in Futhark.Representation.ExplicitMemory

data MemOp inner 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
Eq inner => Eq (MemOp inner) Source # 
Instance details

Defined in Futhark.Representation.ExplicitMemory

Methods

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

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

Ord inner => Ord (MemOp inner) Source # 
Instance details

Defined in Futhark.Representation.ExplicitMemory

Methods

compare :: MemOp inner -> MemOp inner -> Ordering #

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

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

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

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

max :: MemOp inner -> MemOp inner -> MemOp inner #

min :: MemOp inner -> MemOp inner -> MemOp inner #

Show inner => Show (MemOp inner) Source # 
Instance details

Defined in Futhark.Representation.ExplicitMemory

Methods

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

show :: MemOp inner -> String #

showList :: [MemOp inner] -> ShowS #

Pretty inner => Pretty (MemOp inner) Source # 
Instance details

Defined in Futhark.Representation.ExplicitMemory

Methods

ppr :: MemOp inner -> Doc #

pprPrec :: Int -> MemOp inner -> Doc #

pprList :: [MemOp inner] -> Doc #

FreeIn inner => FreeIn (MemOp inner) Source # 
Instance details

Defined in Futhark.Representation.ExplicitMemory

Methods

freeIn :: MemOp inner -> Names Source #

TypedOp inner => TypedOp (MemOp inner) Source # 
Instance details

Defined in Futhark.Representation.ExplicitMemory

Methods

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

Substitute inner => Substitute (MemOp inner) Source # 
Instance details

Defined in Futhark.Representation.ExplicitMemory

Methods

substituteNames :: Map VName VName -> MemOp inner -> MemOp inner Source #

Rename inner => Rename (MemOp inner) Source # 
Instance details

Defined in Futhark.Representation.ExplicitMemory

Methods

rename :: MemOp inner -> RenameM (MemOp inner) Source #

IsOp inner => IsOp (MemOp inner) Source # 
Instance details

Defined in Futhark.Representation.ExplicitMemory

Methods

safeOp :: MemOp inner -> Bool Source #

cheapOp :: MemOp inner -> Bool Source #

CanBeAliased inner => CanBeAliased (MemOp inner) Source # 
Instance details

Defined in Futhark.Representation.ExplicitMemory

Associated Types

type OpWithAliases (MemOp inner) :: Type Source #

AliasedOp inner => AliasedOp (MemOp inner) Source # 
Instance details

Defined in Futhark.Representation.ExplicitMemory

Methods

opAliases :: MemOp inner -> [Names] Source #

consumedInOp :: MemOp inner -> Names Source #

UsageInOp inner => UsageInOp (MemOp inner) Source # 
Instance details

Defined in Futhark.Representation.ExplicitMemory

Methods

usageInOp :: MemOp inner -> UsageTable Source #

OpMetrics inner => OpMetrics (MemOp inner) Source # 
Instance details

Defined in Futhark.Representation.ExplicitMemory

Methods

opMetrics :: MemOp inner -> MetricsM () Source #

CanBeRanged inner => CanBeRanged (MemOp inner) Source # 
Instance details

Defined in Futhark.Representation.ExplicitMemory

Associated Types

type OpWithRanges (MemOp inner) :: Type Source #

Methods

removeOpRanges :: OpWithRanges (MemOp inner) -> MemOp inner Source #

addOpRanges :: MemOp inner -> OpWithRanges (MemOp inner) Source #

RangedOp inner => RangedOp (MemOp inner) Source # 
Instance details

Defined in Futhark.Representation.ExplicitMemory

Methods

opRanges :: MemOp inner -> [Range] Source #

CanBeWise inner => CanBeWise (MemOp inner) Source # 
Instance details

Defined in Futhark.Representation.ExplicitMemory

Associated Types

type OpWithWisdom (MemOp inner) :: Type Source #

Methods

removeOpWisdom :: OpWithWisdom (MemOp inner) -> MemOp inner Source #

IndexOp inner => IndexOp (MemOp inner) Source # 
Instance details

Defined in Futhark.Representation.ExplicitMemory

Methods

indexOp :: (Attributes lore, IndexOp (Op lore)) => SymbolTable lore -> Int -> MemOp inner -> [PrimExp VName] -> Maybe (PrimExp VName, Certificates) Source #

CSEInOp op => CSEInOp (MemOp op) Source # 
Instance details

Defined in Futhark.Optimise.CSE

Methods

cseInOp :: MemOp op -> CSEM lore (MemOp op)

type OpWithAliases (MemOp inner) Source # 
Instance details

Defined in Futhark.Representation.ExplicitMemory

type OpWithAliases (MemOp inner) = MemOp (OpWithAliases inner)
type OpWithRanges (MemOp inner) Source # 
Instance details

Defined in Futhark.Representation.ExplicitMemory

type OpWithRanges (MemOp inner) = MemOp (OpWithRanges inner)
type OpWithWisdom (MemOp inner) Source # 
Instance details

Defined in Futhark.Representation.ExplicitMemory

type OpWithWisdom (MemOp inner) = MemOp (OpWithWisdom inner)

data MemInfo d u ret Source #

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

Defined in Futhark.Representation.ExplicitMemory

IsBodyType BodyReturns Source # 
Instance details

Defined in Futhark.Representation.ExplicitMemory

Pretty (PatElemT (MemInfo SubExp NoUniqueness ret)) Source # 
Instance details

Defined in Futhark.Representation.ExplicitMemory

Pretty (Param (MemInfo SubExp Uniqueness ret)) Source # 
Instance details

Defined in Futhark.Representation.ExplicitMemory

Pretty (Param (MemInfo SubExp NoUniqueness ret)) Source # 
Instance details

Defined in Futhark.Representation.ExplicitMemory

(Pretty u, Pretty r) => PrettyAnnot (PatElemT (MemInfo SubExp u r)) Source # 
Instance details

Defined in Futhark.Representation.ExplicitMemory

(Pretty u, Pretty r) => PrettyAnnot (ParamT (MemInfo SubExp u r)) Source # 
Instance details

Defined in Futhark.Representation.ExplicitMemory

Simplifiable [FunReturns] Source # 
Instance details

Defined in Futhark.Representation.ExplicitMemory

(Eq d, Eq u, Eq ret) => Eq (MemInfo d u ret) Source # 
Instance details

Defined in Futhark.Representation.ExplicitMemory

Methods

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

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

(Ord d, Ord u, Ord ret) => Ord (MemInfo d u ret) Source # 
Instance details

Defined in Futhark.Representation.ExplicitMemory

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 #

(Show d, Show u, Show ret) => Show (MemInfo d u ret) Source # 
Instance details

Defined in Futhark.Representation.ExplicitMemory

Methods

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

show :: MemInfo d u ret -> String #

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

(Pretty (TypeBase (ShapeBase d) u), Pretty d, Pretty u, Pretty ret) => Pretty (MemInfo d u ret) Source # 
Instance details

Defined in Futhark.Representation.ExplicitMemory

Methods

ppr :: MemInfo d u ret -> Doc #

pprPrec :: Int -> MemInfo d u ret -> Doc #

pprList :: [MemInfo d u ret] -> Doc #

FixExt ret => FixExt (MemInfo ExtSize u ret) Source # 
Instance details

Defined in Futhark.Representation.ExplicitMemory

Methods

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

FixExt ret => DeclExtTyped (MemInfo ExtSize Uniqueness ret) Source # 
Instance details

Defined in Futhark.Representation.ExplicitMemory

FixExt ret => ExtTyped (MemInfo ExtSize NoUniqueness ret) Source # 
Instance details

Defined in Futhark.Representation.ExplicitMemory

DeclTyped (MemInfo SubExp Uniqueness ret) Source # 
Instance details

Defined in Futhark.Representation.ExplicitMemory

Typed (MemInfo SubExp Uniqueness ret) Source # 
Instance details

Defined in Futhark.Representation.ExplicitMemory

Typed (MemInfo SubExp NoUniqueness ret) Source # 
Instance details

Defined in Futhark.Representation.ExplicitMemory

(FreeIn d, FreeIn ret) => FreeIn (MemInfo d u ret) Source # 
Instance details

Defined in Futhark.Representation.ExplicitMemory

Methods

freeIn :: MemInfo d u ret -> Names Source #

(Substitute d, Substitute ret) => Substitute (MemInfo d u ret) Source # 
Instance details

Defined in Futhark.Representation.ExplicitMemory

Methods

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

(Substitute d, Substitute ret) => Rename (MemInfo d u ret) Source # 
Instance details

Defined in Futhark.Representation.ExplicitMemory

Methods

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

(Simplifiable d, Simplifiable ret) => Simplifiable (MemInfo d u ret) Source # 
Instance details

Defined in Futhark.Representation.ExplicitMemory

Methods

simplify :: SimplifiableLore lore => MemInfo d u ret -> SimpleM lore (MemInfo d u ret) Source #

data MemBind Source #

Memory information for an array bound somewhere in the program.

Constructors

ArrayIn VName IxFun

Located in this memory block with this index function.

Instances
Eq MemBind Source # 
Instance details

Defined in Futhark.Representation.ExplicitMemory

Methods

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

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

Ord MemBind Source # 
Instance details

Defined in Futhark.Representation.ExplicitMemory

Show MemBind Source # 
Instance details

Defined in Futhark.Representation.ExplicitMemory

Pretty MemBind Source # 
Instance details

Defined in Futhark.Representation.ExplicitMemory

Methods

ppr :: MemBind -> Doc #

pprPrec :: Int -> MemBind -> Doc #

pprList :: [MemBind] -> Doc #

FreeIn MemBind Source # 
Instance details

Defined in Futhark.Representation.ExplicitMemory

Methods

freeIn :: MemBind -> Names Source #

Substitute MemBind Source # 
Instance details

Defined in Futhark.Representation.ExplicitMemory

Rename MemBind Source # 
Instance details

Defined in Futhark.Representation.ExplicitMemory

Simplifiable MemBind Source # 
Instance details

Defined in Futhark.Representation.ExplicitMemory

data MemReturn Source #

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 ExtSize ExtIxFun

The operation returns a new (existential) block, with an existential or known size.

Instances
Eq MemReturn Source # 
Instance details

Defined in Futhark.Representation.ExplicitMemory

Ord MemReturn Source # 
Instance details

Defined in Futhark.Representation.ExplicitMemory

Show MemReturn Source # 
Instance details

Defined in Futhark.Representation.ExplicitMemory

Pretty MemReturn Source # 
Instance details

Defined in Futhark.Representation.ExplicitMemory

Methods

ppr :: MemReturn -> Doc #

pprPrec :: Int -> MemReturn -> Doc #

pprList :: [MemReturn] -> Doc #

FixExt MemReturn Source # 
Instance details

Defined in Futhark.Representation.ExplicitMemory

IsRetType FunReturns Source # 
Instance details

Defined in Futhark.Representation.ExplicitMemory

IsBodyType BodyReturns Source # 
Instance details

Defined in Futhark.Representation.ExplicitMemory

FreeIn MemReturn Source # 
Instance details

Defined in Futhark.Representation.ExplicitMemory

Substitute MemReturn Source # 
Instance details

Defined in Futhark.Representation.ExplicitMemory

Rename MemReturn Source # 
Instance details

Defined in Futhark.Representation.ExplicitMemory

Simplifiable MemReturn Source # 
Instance details

Defined in Futhark.Representation.ExplicitMemory

Simplifiable [FunReturns] Source # 
Instance details

Defined in Futhark.Representation.ExplicitMemory

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.

type ExplicitMemorish lore = (SameScope lore ExplicitMemory, RetType lore ~ FunReturns, BranchType lore ~ BodyReturns, CanBeAliased (Op lore), Attributes lore, Annotations lore, Checkable lore, OpReturns lore) Source #

expReturns :: (Monad m, HasScope lore m, ExplicitMemorish 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.

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

Is an array of the given shape stored fully flat row-major with the given index function?

Module re-exports