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

Safe Haskell | Safe-Inferred
Language | GHC2021

Futhark.Analysis.HORep.SOAC

Contents

- SOACs
  - Converting to and from expressions
- SOAC inputs
  - Input transformations

Description

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

Synopsis

- data SOAC rep
  - = Stream SubExp [Input] [SubExp] (Lambda rep)
  - | Scatter SubExp [Input] (ScatterSpec VName) (Lambda rep)
  - | Screma SubExp [Input] (ScremaForm rep)
  - | Hist SubExp [Input] [HistOp rep] (Lambda rep)
- data ScremaForm rep = ScremaForm {
  - scremaLambda :: Lambda rep
  - scremaScans :: [Scan rep]
  - scremaReduces :: [Reduce rep]
  }
- inputs :: SOAC rep -> [Input]
- setInputs :: [Input] -> SOAC rep -> SOAC rep
- lambda :: SOAC rep -> Lambda rep
- setLambda :: Lambda rep -> SOAC rep -> SOAC rep
- typeOf :: SOAC rep -> [Type]
- width :: SOAC rep -> SubExp
- data NotSOAC = NotSOAC
- fromExp :: (Op rep ~ SOAC rep, HasScope rep m) => Exp rep -> m (Either NotSOAC (SOAC rep))
- toExp :: (MonadBuilder m, Op (Rep m) ~ SOAC (Rep m)) => SOAC (Rep m) -> m (Exp (Rep m))
- toSOAC :: MonadBuilder m => SOAC (Rep m) -> m (SOAC (Rep m))
- data Input = Input ArrayTransforms VName Type
- varInput :: HasScope t f => VName -> f Input
- inputTransforms :: Input -> ArrayTransforms
- identInput :: Ident -> Input
- isVarInput :: Input -> Maybe VName
- isVarishInput :: Input -> Maybe VName
- addTransform :: ArrayTransform -> Input -> Input
- addInitialTransforms :: ArrayTransforms -> Input -> Input
- inputArray :: Input -> VName
- inputRank :: Input -> Int
- inputType :: Input -> Type
- inputRowType :: Input -> Type
- transformRows :: ArrayTransforms -> Input -> Input
- transposeInput :: Int -> Int -> Input -> Input
- applyTransforms :: MonadBuilder m => ArrayTransforms -> VName -> m VName
- data ArrayTransforms
- noTransforms :: ArrayTransforms
- nullTransforms :: ArrayTransforms -> Bool
- (|>) :: ArrayTransforms -> ArrayTransform -> ArrayTransforms
- (<|) :: ArrayTransform -> ArrayTransforms -> ArrayTransforms
- viewf :: ArrayTransforms -> ViewF
- data ViewF
  - = EmptyF
  - | ArrayTransform :< ArrayTransforms
- viewl :: ArrayTransforms -> ViewL
- data ViewL
  - = EmptyL
  - | ArrayTransforms :> ArrayTransform
- data ArrayTransform
  - = Rearrange Certs [Int]
  - | Reshape Certs ReshapeKind Shape
  - | ReshapeOuter Certs ReshapeKind Shape
  - | ReshapeInner Certs ReshapeKind Shape
  - | Replicate Certs Shape
  - | Index Certs (Slice SubExp)
- transformFromExp :: Certs -> Exp rep -> Maybe (VName, ArrayTransform)
- transformToExp :: (Monad m, HasScope rep m) => ArrayTransform -> VName -> m (Certs, Exp rep)
- soacToStream :: (HasScope rep m, MonadFreshNames m, Buildable rep, BuilderOps rep, Op rep ~ SOAC rep) => SOAC rep -> m (SOAC rep, [Ident])

# SOACs

data SOAC rep Source #

A definite representation of a SOAC expression.

Constructors

Stream SubExp [Input] [SubExp] (Lambda rep) |
Scatter SubExp [Input] (ScatterSpec VName) (Lambda rep) |
Screma SubExp [Input] (ScremaForm rep) |
Hist SubExp [Input] [HistOp rep] (Lambda rep) |

#### Instances

Instances details

RepTypes rep => Show (SOAC rep) Source # |
Instance details Defined in Futhark.Analysis.HORep.SOAC Methods showsPrec :: Int -> SOAC rep -> ShowS Source # show :: SOAC rep -> String Source # showList :: [SOAC rep] -> ShowS Source #
RepTypes rep => Eq (SOAC rep) Source # |
Instance details Defined in Futhark.Analysis.HORep.SOAC Methods (==) :: SOAC rep -> SOAC rep -> Bool Source # (/=) :: SOAC rep -> SOAC rep -> Bool Source #
PrettyRep rep => Pretty (SOAC rep) Source # |
Instance details Defined in Futhark.Analysis.HORep.SOAC Methods pretty :: SOAC rep -> Doc ann Source # prettyList :: [SOAC rep] -> Doc ann Source #

data ScremaForm rep Source #

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

Constructors

ScremaForm |

Fields

- scremaLambda :: Lambda rep

  The "main" lambda of the Screma. For a map, this is equivalent to `isMapSOAC`. Note that the meaning of the return value of this lambda depends crucially on exactly which Screma this is. The parameters will correspond exactly to elements of the input arrays, however.

- scremaScans :: [Scan rep]
- scremaReduces :: [Reduce rep]

#### Instances

Instances details

RepTypes rep => Show (ScremaForm rep) Source # |
Instance details Defined in Futhark.IR.SOACS.SOAC Methods showsPrec :: Int -> ScremaForm rep -> ShowS Source # show :: ScremaForm rep -> String Source # showList :: [ScremaForm rep] -> ShowS Source #
ASTRep rep => FreeIn (ScremaForm rep) Source # |
Instance details Defined in Futhark.IR.SOACS.SOAC Methods freeIn' :: ScremaForm rep -> FV Source #
RepTypes rep => Eq (ScremaForm rep) Source # |
Instance details Defined in Futhark.IR.SOACS.SOAC Methods (==) :: ScremaForm rep -> ScremaForm rep -> Bool Source # (/=) :: ScremaForm rep -> ScremaForm rep -> Bool Source #
RepTypes rep => Ord (ScremaForm rep) Source # |

Instance details

Defined in Futhark.IR.SOACS.SOAC

Methods

compare :: ScremaForm rep -> ScremaForm rep -> Ordering Source #

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

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

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

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

max :: ScremaForm rep -> ScremaForm rep -> ScremaForm rep Source #

min :: ScremaForm rep -> ScremaForm rep -> ScremaForm rep Source #

inputs :: SOAC rep -> [Input] Source #

Returns the inputs used in a SOAC.

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

Set the inputs to a SOAC.

lambda :: SOAC rep -> Lambda rep Source #

The lambda used in a given SOAC.

setLambda :: Lambda rep -> SOAC rep -> SOAC rep Source #

Set the lambda used in the SOAC.

typeOf :: SOAC rep -> [Type] Source #

The return type of a SOAC.

width :: SOAC rep -> SubExp Source #

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

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

Constructors

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

#### Instances

Instances details

Show NotSOAC Source # |
Instance details Defined in Futhark.Analysis.HORep.SOAC Methods showsPrec :: Int -> NotSOAC -> ShowS Source # show :: NotSOAC -> String Source # showList :: [NotSOAC] -> ShowS Source #

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

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

Convert a SOAC to the corresponding expression.

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

Convert a SOAC to a Futhark-level SOAC.

# SOAC inputs

data Input Source #

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

Instances details

Show Input Source # |
Instance details Defined in Futhark.Analysis.HORep.SOAC Methods showsPrec :: Int -> Input -> ShowS Source # show :: Input -> String Source # showList :: [Input] -> ShowS Source #
Substitute Input Source # |
Instance details Defined in Futhark.Analysis.HORep.SOAC Methods substituteNames :: Map VName VName -> Input -> Input Source #
Eq Input Source # |
Instance details Defined in Futhark.Analysis.HORep.SOAC Methods (==) :: Input -> Input -> Bool Source # (/=) :: Input -> Input -> Bool Source #
Ord Input Source # |
Instance details Defined in Futhark.Analysis.HORep.SOAC Methods compare :: Input -> Input -> Ordering Source # (<) :: Input -> Input -> Bool Source # (<=) :: Input -> Input -> Bool Source # (>) :: Input -> Input -> Bool Source # (>=) :: Input -> Input -> Bool Source # max :: Input -> Input -> Input Source # min :: Input -> Input -> Input Source #
Pretty Input Source # |
Instance details Defined in Futhark.Analysis.HORep.SOAC Methods pretty :: Input -> Doc ann Source # prettyList :: [Input] -> Doc ann Source #

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

Create a plain array variable input with no transformations.

inputTransforms :: Input -> ArrayTransforms Source #

The transformations applied to an input.

identInput :: Ident -> Input Source #

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

isVarInput :: Input -> Maybe VName Source #

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

isVarishInput :: Input -> Maybe VName Source #

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

addTransform :: ArrayTransform -> Input -> Input Source #

Add a transformation to the end of the transformation list.

addInitialTransforms :: ArrayTransforms -> Input -> Input Source #

Add several transformations to the start of the transformation list.

inputArray :: Input -> VName Source #

Return the array name of the input.

inputRank :: Input -> Int Source #

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

inputType :: Input -> Type Source #

Return the type of an input.

inputRowType :: Input -> Type Source #

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

transformRows :: ArrayTransforms -> Input -> Input Source #

Apply the transformations to every row of the input.

transposeInput :: Int -> Int -> Input -> Input Source #

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

## Input transformations

data ArrayTransforms Source #

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

Instances details

Monoid ArrayTransforms Source # |
Instance details Defined in Futhark.Analysis.HORep.SOAC Methods mempty :: ArrayTransforms Source # mappend :: ArrayTransforms -> ArrayTransforms -> ArrayTransforms Source # mconcat :: [ArrayTransforms] -> ArrayTransforms Source #
Semigroup ArrayTransforms Source # |
Instance details Defined in Futhark.Analysis.HORep.SOAC Methods (<>) :: ArrayTransforms -> ArrayTransforms -> ArrayTransforms Source # sconcat :: NonEmpty ArrayTransforms -> ArrayTransforms Source # stimes :: Integral b => b -> ArrayTransforms -> ArrayTransforms Source #
Show ArrayTransforms Source # |
Instance details Defined in Futhark.Analysis.HORep.SOAC Methods showsPrec :: Int -> ArrayTransforms -> ShowS Source # show :: ArrayTransforms -> String Source # showList :: [ArrayTransforms] -> ShowS Source #
Substitute ArrayTransforms Source # |
Instance details Defined in Futhark.Analysis.HORep.SOAC Methods substituteNames :: Map VName VName -> ArrayTransforms -> ArrayTransforms Source #
Eq ArrayTransforms Source # |
Instance details Defined in Futhark.Analysis.HORep.SOAC Methods (==) :: ArrayTransforms -> ArrayTransforms -> Bool Source # (/=) :: ArrayTransforms -> ArrayTransforms -> Bool Source #
Ord ArrayTransforms Source # |

Instance details

Defined in Futhark.Analysis.HORep.SOAC

Methods

compare :: ArrayTransforms -> ArrayTransforms -> Ordering Source #

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

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

(>) :: ArrayTransforms -> ArrayTransforms -> Bool Source #

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

max :: ArrayTransforms -> ArrayTransforms -> ArrayTransforms Source #

min :: ArrayTransforms -> ArrayTransforms -> ArrayTransforms Source #

noTransforms :: ArrayTransforms Source #

The empty transformation list.

nullTransforms :: ArrayTransforms -> Bool Source #

Is it an empty transformation list?

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

Add a transform to the end of the transformation list.

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

Add a transform at the beginning of the transformation list.

viewf :: ArrayTransforms -> ViewF Source #

Decompose the input-end of the transformation sequence.

data ViewF Source #

A view of the first transformation to be applied.

Constructors

EmptyF |
ArrayTransform :< ArrayTransforms |

viewl :: ArrayTransforms -> ViewL Source #

Decompose the output-end of the transformation sequence.

data ViewL Source #

A view of the last transformation to be applied.

Constructors

EmptyL |
ArrayTransforms :> ArrayTransform |

data ArrayTransform Source #

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

Instances details

Show ArrayTransform Source # |
Instance details Defined in Futhark.Analysis.HORep.SOAC Methods showsPrec :: Int -> ArrayTransform -> ShowS Source # show :: ArrayTransform -> String Source # showList :: [ArrayTransform] -> ShowS Source #
Substitute ArrayTransform Source # |
Instance details Defined in Futhark.Analysis.HORep.SOAC Methods substituteNames :: Map VName VName -> ArrayTransform -> ArrayTransform Source #
Eq ArrayTransform Source # |
Instance details Defined in Futhark.Analysis.HORep.SOAC Methods (==) :: ArrayTransform -> ArrayTransform -> Bool Source # (/=) :: ArrayTransform -> ArrayTransform -> Bool Source #
Ord ArrayTransform Source # |

Instance details

Defined in Futhark.Analysis.HORep.SOAC

Methods

compare :: ArrayTransform -> ArrayTransform -> Ordering Source #

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

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

(>) :: ArrayTransform -> ArrayTransform -> Bool Source #

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

max :: ArrayTransform -> ArrayTransform -> ArrayTransform Source #

min :: ArrayTransform -> ArrayTransform -> ArrayTransform Source #

Pretty ArrayTransform Source # |
Instance details Defined in Futhark.Analysis.HORep.SOAC Methods pretty :: ArrayTransform -> Doc ann Source # prettyList :: [ArrayTransform] -> Doc ann Source #

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

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

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

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