Futhark.Analysis.HORep.SOAC

High-level representation of SOACs. When performing SOAC-transformations, operating on normal Exp values is somewhat of a nuisance, as they can represent terms that are not proper SOACs. In contrast, this module exposes a SOAC representation that does not enable invalid representations (except for type errors).

Furthermore, while standard normalised Futhark requires that the inputs to a SOAC are variables or constants, the representation in this module also supports various index-space transformations, like replicate or rearrange. This is also very convenient when implementing transformations.

The names exported by this module conflict with the standard Futhark syntax tree constructors, so you are advised to use a qualified import:

import Futhark.Analysis.HORep.SOAC (SOAC)
import qualified Futhark.Analysis.HORep.SOAC as SOAC

SOACs

data SOAC rep

A definite representation of a SOAC expression.

Constructors

Stream SubExp (Lambda rep) [SubExp] [Input]

Scatter SubExp (Lambda rep) [Input] [(Shape, Int, VName)]

Screma SubExp (ScremaForm rep) [Input]

Hist SubExp [HistOp rep] (Lambda rep) [Input]

Instances

RepTypes rep => Show (SOAC rep)

Defined in Futhark.Analysis.HORep.SOAC

Methods

showsPrec :: Int -> SOAC rep -> ShowS

show :: SOAC rep -> String

showList :: [SOAC rep] -> ShowS

RepTypes rep => Eq (SOAC rep)

Defined in Futhark.Analysis.HORep.SOAC

Methods

(==) :: SOAC rep -> SOAC rep -> Bool

(/=) :: SOAC rep -> SOAC rep -> Bool

PrettyRep rep => Pretty (SOAC rep)

Defined in Futhark.Analysis.HORep.SOAC

Methods

pretty :: SOAC rep -> Doc ann

prettyList :: [SOAC rep] -> Doc ann

data ScremaForm rep

The essential parts of a Screma factored out (everything except the input arrays).

Constructors

ScremaForm [Scan rep] [Reduce rep] (Lambda rep)

Instances

RepTypes rep => Show (ScremaForm rep)

Defined in Futhark.IR.SOACS.SOAC

Methods

showsPrec :: Int -> ScremaForm rep -> ShowS

show :: ScremaForm rep -> String

showList :: [ScremaForm rep] -> ShowS

ASTRep rep => FreeIn (ScremaForm rep)

Defined in Futhark.IR.SOACS.SOAC

Methods

freeIn' :: ScremaForm rep -> FV

RepTypes rep => Eq (ScremaForm rep)

Defined in Futhark.IR.SOACS.SOAC

Methods

(==) :: ScremaForm rep -> ScremaForm rep -> Bool

(/=) :: ScremaForm rep -> ScremaForm rep -> Bool

RepTypes rep => Ord (ScremaForm rep)

Defined in Futhark.IR.SOACS.SOAC

Methods

compare :: ScremaForm rep -> ScremaForm rep -> Ordering

(<) :: ScremaForm rep -> ScremaForm rep -> Bool

(<=) :: ScremaForm rep -> ScremaForm rep -> Bool

(>) :: ScremaForm rep -> ScremaForm rep -> Bool

(>=) :: ScremaForm rep -> ScremaForm rep -> Bool

max :: ScremaForm rep -> ScremaForm rep -> ScremaForm rep

min :: ScremaForm rep -> ScremaForm rep -> ScremaForm rep

inputs :: SOAC rep -> [Input]

Returns the inputs used in a SOAC.

setInputs :: [Input] -> SOAC rep -> SOAC rep

Set the inputs to a SOAC.

lambda :: SOAC rep -> Lambda rep

The lambda used in a given SOAC.

setLambda :: Lambda rep -> SOAC rep -> SOAC rep

Set the lambda used in the SOAC.

typeOf :: SOAC rep -> [Type]

The return type of a SOAC.

width :: SOAC rep -> SubExp

The "width" of a SOAC is the expected outer size of its array inputs _after_ input-transforms have been carried out.

Converting to and from expressions

data NotSOAC

The reason why some expression cannot be converted to a SOAC value.

Constructors

NotSOAC

The expression is not a (tuple-)SOAC at all.

Instances

Show NotSOAC

Defined in Futhark.Analysis.HORep.SOAC

Methods

showsPrec :: Int -> NotSOAC -> ShowS

show :: NotSOAC -> String

showList :: [NotSOAC] -> ShowS

fromExp :: (Op rep ~ SOAC rep, HasScope rep m) => Exp rep -> m (Either NotSOAC (SOAC rep))

Either convert an expression to the normalised SOAC representation, or a reason why the expression does not have the valid form.

toExp :: (MonadBuilder m, Op (Rep m) ~ SOAC (Rep m)) => SOAC (Rep m) -> m (Exp (Rep m))

Convert a SOAC to the corresponding expression.

toSOAC :: MonadBuilder m => SOAC (Rep m) -> m (SOAC (Rep m))

Convert a SOAC to a Futhark-level SOAC.

SOAC inputs

data Input

One array input to a SOAC - a SOAC may have multiple inputs, but all are of this form. Only the array inputs are expressed with this type; other arguments, such as initial accumulator values, are plain expressions. The transforms are done left-to-right, that is, the first element of the ArrayTransform list is applied first.

Constructors

Input ArrayTransforms VName Type

Instances

Show Input

Defined in Futhark.Analysis.HORep.SOAC

Methods

showsPrec :: Int -> Input -> ShowS

show :: Input -> String

showList :: [Input] -> ShowS

Substitute Input

Defined in Futhark.Analysis.HORep.SOAC

Methods

substituteNames :: Map VName VName -> Input -> Input

Eq Input

Defined in Futhark.Analysis.HORep.SOAC

Methods

(==) :: Input -> Input -> Bool

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

Ord Input

Defined in Futhark.Analysis.HORep.SOAC

Methods

compare :: Input -> Input -> Ordering

(<) :: Input -> Input -> Bool

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

(>) :: Input -> Input -> Bool

(>=) :: Input -> Input -> Bool

max :: Input -> Input -> Input

min :: Input -> Input -> Input

Pretty Input

Defined in Futhark.Analysis.HORep.SOAC

Methods

pretty :: Input -> Doc ann

prettyList :: [Input] -> Doc ann

varInput :: HasScope t f => VName -> f Input

Create a plain array variable input with no transformations.

inputTransforms :: Input -> ArrayTransforms

The transformations applied to an input.

identInput :: Ident -> Input

Create a plain array variable input with no transformations, from an Ident.

isVarInput :: Input -> Maybe VName

If the given input is a plain variable input, with no transforms, return the variable.

isVarishInput :: Input -> Maybe VName

If the given input is a plain variable input, with no non-vacuous transforms, return the variable.

addTransform :: ArrayTransform -> Input -> Input

Add a transformation to the end of the transformation list.

addInitialTransforms :: ArrayTransforms -> Input -> Input

Add several transformations to the start of the transformation list.

inputArray :: Input -> VName

Return the array name of the input.

inputRank :: Input -> Int

Return the array rank (dimensionality) of an input. Just a convenient alias.

inputType :: Input -> Type

Return the type of an input.

inputRowType :: Input -> Type

Return the row type of an input. Just a convenient alias.

transformRows :: ArrayTransforms -> Input -> Input

Apply the transformations to every row of the input.

transposeInput :: Int -> Int -> Input -> Input

Add to the input a Rearrange transform that performs an (k,n) transposition. The new transform will be at the end of the current transformation list.

applyTransforms :: MonadBuilder m => ArrayTransforms -> VName -> m VName

Input transformations

data ArrayTransforms

A sequence of array transformations, heavily inspired by Data.Seq. You can decompose it using viewf and viewl, and grow it by using |> and <|. These correspond closely to the similar operations for sequences, except that appending will try to normalise and simplify the transformation sequence.

The data type is opaque in order to enforce normalisation invariants. Basically, when you grow the sequence, the implementation will try to coalesce neighboring permutations, for example by composing permutations and removing identity transformations.

Instances

Monoid ArrayTransforms

Defined in Futhark.Analysis.HORep.SOAC

Methods

mempty :: ArrayTransforms

mappend :: ArrayTransforms -> ArrayTransforms -> ArrayTransforms

mconcat :: [ArrayTransforms] -> ArrayTransforms

Semigroup ArrayTransforms

Defined in Futhark.Analysis.HORep.SOAC

Methods

(<>) :: ArrayTransforms -> ArrayTransforms -> ArrayTransforms

sconcat :: NonEmpty ArrayTransforms -> ArrayTransforms

stimes :: Integral b => b -> ArrayTransforms -> ArrayTransforms

Show ArrayTransforms

Defined in Futhark.Analysis.HORep.SOAC

Methods

showsPrec :: Int -> ArrayTransforms -> ShowS

show :: ArrayTransforms -> String

showList :: [ArrayTransforms] -> ShowS

Substitute ArrayTransforms

Defined in Futhark.Analysis.HORep.SOAC

Methods

substituteNames :: Map VName VName -> ArrayTransforms -> ArrayTransforms

Eq ArrayTransforms

Defined in Futhark.Analysis.HORep.SOAC

Methods

(==) :: ArrayTransforms -> ArrayTransforms -> Bool

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

Ord ArrayTransforms

Defined in Futhark.Analysis.HORep.SOAC

Methods

compare :: ArrayTransforms -> ArrayTransforms -> Ordering

(<) :: ArrayTransforms -> ArrayTransforms -> Bool

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

(>) :: ArrayTransforms -> ArrayTransforms -> Bool

(>=) :: ArrayTransforms -> ArrayTransforms -> Bool

max :: ArrayTransforms -> ArrayTransforms -> ArrayTransforms

min :: ArrayTransforms -> ArrayTransforms -> ArrayTransforms

noTransforms :: ArrayTransforms

The empty transformation list.

nullTransforms :: ArrayTransforms -> Bool

Is it an empty transformation list?

(|>) :: ArrayTransforms -> ArrayTransform -> ArrayTransforms

Add a transform to the end of the transformation list.

(<|) :: ArrayTransform -> ArrayTransforms -> ArrayTransforms

Add a transform at the beginning of the transformation list.

viewf :: ArrayTransforms -> ViewF

Decompose the input-end of the transformation sequence.

data ViewF

A view of the first transformation to be applied.

Constructors

EmptyF

ArrayTransform :< ArrayTransforms

viewl :: ArrayTransforms -> ViewL

Decompose the output-end of the transformation sequence.

data ViewL

A view of the last transformation to be applied.

Constructors

EmptyL

ArrayTransforms :> ArrayTransform

data ArrayTransform

A single, simple transformation. If you want several, don't just create a list, use ArrayTransforms instead.

Constructors

Rearrange Certs [Int]

A permutation of an otherwise valid input.

Reshape Certs ReshapeKind Shape

A reshaping of an otherwise valid input.

ReshapeOuter Certs ReshapeKind Shape

A reshaping of the outer dimension.

ReshapeInner Certs ReshapeKind Shape

A reshaping of everything but the outer dimension.

Replicate Certs Shape

Replicate the rows of the array a number of times.

Index Certs (Slice SubExp)

An array indexing operation.

Instances

Show ArrayTransform

Defined in Futhark.Analysis.HORep.SOAC

Methods

showsPrec :: Int -> ArrayTransform -> ShowS

show :: ArrayTransform -> String

showList :: [ArrayTransform] -> ShowS

Substitute ArrayTransform

Defined in Futhark.Analysis.HORep.SOAC

Methods

substituteNames :: Map VName VName -> ArrayTransform -> ArrayTransform

Eq ArrayTransform

Defined in Futhark.Analysis.HORep.SOAC

Methods

(==) :: ArrayTransform -> ArrayTransform -> Bool

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

Ord ArrayTransform

Defined in Futhark.Analysis.HORep.SOAC

Methods

compare :: ArrayTransform -> ArrayTransform -> Ordering

(<) :: ArrayTransform -> ArrayTransform -> Bool

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

(>) :: ArrayTransform -> ArrayTransform -> Bool

(>=) :: ArrayTransform -> ArrayTransform -> Bool

max :: ArrayTransform -> ArrayTransform -> ArrayTransform

min :: ArrayTransform -> ArrayTransform -> ArrayTransform

Pretty ArrayTransform

Defined in Futhark.Analysis.HORep.SOAC

Methods

pretty :: ArrayTransform -> Doc ann

prettyList :: [ArrayTransform] -> Doc ann

transformFromExp :: Certs -> Exp rep -> Maybe (VName, ArrayTransform)

Given an expression, determine whether the expression represents an input transformation of an array variable. If so, return the variable and the transformation. Only Rearrange and Reshape are possible to express this way.

transformToExp :: (Monad m, HasScope rep m) => ArrayTransform -> VName -> m (Certs, Exp rep)

Turn an array transform on an array back into an expression.

soacToStream :: (HasScope rep m, MonadFreshNames m, Buildable rep, BuilderOps rep, Op rep ~ SOAC rep) => SOAC rep -> m (SOAC rep, [Ident])

To-Stream translation of SOACs. Returns the Stream SOAC and the extra-accumulator body-result ident if any.