Safe Haskell	None
Language	GHC2021

Futhark.IR.SOACS.SOAC

Contents

Utility
Generic traversal

Description

Definition of Second-Order Array Combinators (SOACs), which are the main form of parallelism in the early stages of the compiler.

Synopsis

data SOAC rep
- = Stream SubExp [VName] [SubExp] (Lambda rep)
- | Hist SubExp [VName] [HistOp rep] (Lambda rep)
- | JVP Shape [SubExp] [SubExp] (Lambda rep)
- | VJP Shape [SubExp] [SubExp] (Lambda rep)
- | WithVJP [SubExp] (Lambda rep) (Lambda rep)
- | Screma SubExp [VName] (ScremaForm rep)
- | FlatMap SubExp [VName] (ExtLambda rep)
data ScremaForm rep = ScremaForm {
- scremaLambda :: Lambda rep
- scremaScans :: [Scan rep]
- scremaReduces :: [Reduce rep]
- scremaPostLambda :: Lambda rep
}
data HistOp rep = HistOp {
- histShape :: Shape
- histRaceFactor :: SubExp
- histDest :: [VName]
- histNeutral :: [SubExp]
- histOp :: Lambda rep
}
data Scan rep = Scan {
- scanLambda :: Lambda rep
- scanNeutral :: [SubExp]
}
scanResults :: [Scan rep] -> Int
singleScan :: Buildable rep => [Scan rep] -> Scan rep
data Reduce rep = Reduce {
- redComm :: Commutativity
- redLambda :: Lambda rep
- redNeutral :: [SubExp]
}
redResults :: [Reduce rep] -> Int
singleReduce :: Buildable rep => [Reduce rep] -> Reduce rep
composeBinds :: (Buildable rep, Ord a) => Lambda rep -> [a] -> [a] -> Lambda rep -> Stms rep
scremaType :: SubExp -> ScremaForm rep -> [Type]
soacType :: Typed (LParamInfo rep) => SOAC rep -> [ExtType]
flatMapNonuniform :: ExtType -> Bool
flatMapRowTypes :: ExtLambda rep -> [Type]
flatMapUniformTypes :: ExtLambda rep -> [Type]
flatMapSplitMeta :: [a] -> ((a, a, a, a), [a])
flatMapSplitValues :: ExtLambda rep -> [a] -> ([a], [a])
typeCheckSOAC :: Checkable rep => SOAC (Aliases rep) -> TypeM rep ()
mkIdentityLambda :: (Buildable rep, MonadFreshNames m) => [Type] -> m (Lambda rep)
nilFn :: Buildable rep => Lambda rep
maposcanomapSOAC :: (Buildable rep, MonadFreshNames m) => Lambda rep -> [Scan rep] -> Lambda rep -> m (ScremaForm rep)
scanomapSOAC :: (Buildable rep, MonadFreshNames m) => [Scan rep] -> Lambda rep -> m (ScremaForm rep)
redomapSOAC :: (Buildable rep, MonadFreshNames m) => [Reduce rep] -> Lambda rep -> m (ScremaForm rep)
scanSOAC :: (Buildable rep, MonadFreshNames m) => [Scan rep] -> m (ScremaForm rep)
reduceSOAC :: (Buildable rep, MonadFreshNames m) => [Reduce rep] -> m (ScremaForm rep)
mapSOAC :: (Buildable rep, MonadFreshNames m) => Lambda rep -> m (ScremaForm rep)
isMaposcanomapSOAC :: ScremaForm rep -> Maybe (Lambda rep, [Scan rep], Lambda rep)
isScanomapSOAC :: ScremaForm rep -> Maybe ([Scan rep], Lambda rep)
isRedomapSOAC :: ScremaForm rep -> Maybe ([Reduce rep], Lambda rep)
isScanSOAC :: ScremaForm rep -> Maybe [Scan rep]
isReduceSOAC :: ScremaForm rep -> Maybe [Reduce rep]
isMapSOAC :: ScremaForm rep -> Maybe (Lambda rep)
ppScrema :: (PrettyRep rep, Pretty inp) => SubExp -> [inp] -> ScremaForm rep -> Doc ann
ppHist :: (PrettyRep rep, Pretty inp) => SubExp -> [inp] -> [HistOp rep] -> Lambda rep -> Doc ann
ppStream :: (PrettyRep rep, Pretty inp) => SubExp -> [inp] -> [SubExp] -> Lambda rep -> Doc ann
data SOACMapper frep trep (m :: Type -> Type) = SOACMapper {
- mapOnSOACSubExp :: SubExp -> m SubExp
- mapOnSOACLambda :: Lambda frep -> m (Lambda trep)
- mapOnSOACExtLambda :: ExtLambda frep -> m (ExtLambda trep)
- mapOnSOACVName :: VName -> m VName
}
identitySOACMapper :: forall rep (m :: Type -> Type). Monad m => SOACMapper rep rep m
mapSOACM :: Monad m => SOACMapper frep trep m -> SOAC frep -> m (SOAC trep)
traverseSOACStms :: Monad m => OpStmsTraverser m (SOAC rep) rep

Documentation

data SOAC rep Source #

A second-order array combinator (SOAC).

Constructors

Stream SubExp [VName] [SubExp] (Lambda rep)
Hist SubExp [VName] [HistOp rep] (Lambda rep)	Hist length arrays dest-arrays-and-ops fun The final lambda produces indexes and values for the `HistOp`s.
JVP Shape [SubExp] [SubExp] (Lambda rep)
VJP Shape [SubExp] [SubExp] (Lambda rep)
WithVJP [SubExp] (Lambda rep) (Lambda rep)
Screma SubExp [VName] (ScremaForm rep)	A combination of scan, reduction, and map. The first `SubExp` is the size of the input arrays.
FlatMap SubExp [VName] (ExtLambda rep)	Nonuniform map where the nonuniform results are implicitly concatenated. The `ExtLambda` first returns a size `k`, then its value results, each of which is either nonuniform (an array with `k` as its outermost size) or uniform (not mentioning `k` at all). The size `k` may be used only as an outermost dimension. For input of length `n` returns the following: An integer `m` denoting the size of the data arrays. The "shape array" of type `[n]i64`, giving the size of each segment. This array sums to `m`. The "flag array" of type `[m]bool`, indicating for each element when a new segment begins. The "offset array" of type `[n]i64`, indicating for each segment where its values begin in the data array. Finally one array per value result of the lambda, in the same order: a nonuniform result becomes its concatenation across all iterations, of outer size `[m]`, and a uniform result the collection of its values, of outer size `[n]`.

Instances

Instances details

CanBeAliased SOAC Source #
Instance details Defined in Futhark.IR.SOACS.SOAC Methods addOpAliases :: AliasableRep rep => AliasTable -> SOAC rep -> SOAC (Aliases rep) Source #
IsOp SOAC Source #
Instance details Defined in Futhark.IR.SOACS.SOAC Methods safeOp :: ASTRep rep => SOAC rep -> Bool Source # cheapOp :: ASTRep rep => SOAC rep -> Bool Source # opDependencies :: ASTRep rep => SOAC rep -> [Names] Source #
AliasedOp SOAC Source #
Instance details Defined in Futhark.IR.SOACS.SOAC Methods opAliases :: Aliased rep => SOAC rep -> [Names] Source # consumedInOp :: Aliased rep => SOAC rep -> Names Source #
TypedOp SOAC Source #
Instance details Defined in Futhark.IR.SOACS.SOAC Methods opType :: HasScope rep m => SOAC rep -> m [ExtType] Source #
RephraseOp SOAC Source #
Instance details Defined in Futhark.IR.SOACS.SOAC Methods rephraseInOp :: Monad m => Rephraser m from to -> SOAC from -> m (SOAC to) Source #
CanBeWise SOAC Source #
Instance details Defined in Futhark.IR.SOACS.SOAC Methods addOpWisdom :: Informing rep => SOAC rep -> SOAC (Wise rep) Source #
OpMetrics (Op rep) => OpMetrics (SOAC rep) Source #
Instance details Defined in Futhark.IR.SOACS.SOAC Methods opMetrics :: SOAC rep -> MetricsM () Source #
RepTypes rep => IndexOp (SOAC rep) Source #
Instance details Defined in Futhark.IR.SOACS.SOAC Methods indexOp :: (ASTRep rep0, IndexOp (Op rep0)) => SymbolTable rep0 -> Int -> SOAC rep -> [TPrimExp Int64 VName] -> Maybe Indexed Source #
ASTRep rep => FreeIn (SOAC rep) Source #
Instance details Defined in Futhark.IR.SOACS.SOAC Methods freeIn' :: SOAC rep -> FV Source #
(AliasableRep rep, CSEInOp (Op (Aliases rep))) => CSEInOp (SOAC (Aliases rep)) Source #
Instance details Defined in Futhark.Optimise.CSE Methods cseInOp :: SOAC (Aliases rep) -> CSEM rep0 (SOAC (Aliases rep))
ASTRep rep => Rename (SOAC rep) Source #
Instance details Defined in Futhark.IR.SOACS.SOAC Methods rename :: SOAC rep -> RenameM (SOAC rep) Source #
ASTRep rep => Substitute (SOAC rep) Source #
Instance details Defined in Futhark.IR.SOACS.SOAC Methods substituteNames :: Map VName VName -> SOAC rep -> SOAC rep Source #
RepTypes rep => Show (SOAC rep) Source #
Instance details Defined in Futhark.IR.SOACS.SOAC Methods showsPrec :: Int -> SOAC rep -> ShowS # show :: SOAC rep -> String # showList :: [SOAC rep] -> ShowS #
RepTypes rep => Eq (SOAC rep) Source #
Instance details Defined in Futhark.IR.SOACS.SOAC Methods (==) :: SOAC rep -> SOAC rep -> Bool # (/=) :: SOAC rep -> SOAC rep -> Bool #
RepTypes rep => Ord (SOAC rep) Source #
Instance details Defined in Futhark.IR.SOACS.SOAC Methods compare :: SOAC rep -> SOAC rep -> Ordering # (<) :: SOAC rep -> SOAC rep -> Bool # (<=) :: SOAC rep -> SOAC rep -> Bool # (>) :: SOAC rep -> SOAC rep -> Bool # (>=) :: SOAC rep -> SOAC rep -> Bool # max :: SOAC rep -> SOAC rep -> SOAC rep # min :: SOAC rep -> SOAC rep -> SOAC rep #
PrettyRep rep => Pretty (SOAC rep) Source #
Instance details Defined in Futhark.IR.SOACS.SOAC Methods pretty :: SOAC rep -> Doc ann # prettyList :: [SOAC rep] -> Doc ann #

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] scremaPostLambda :: Lambda rep

Instances

Instances details

ASTRep rep => FreeIn (ScremaForm rep) Source #
Instance details Defined in Futhark.IR.SOACS.SOAC Methods freeIn' :: ScremaForm rep -> FV Source #
RepTypes rep => Show (ScremaForm rep) Source #
Instance details Defined in Futhark.IR.SOACS.SOAC Methods showsPrec :: Int -> ScremaForm rep -> ShowS # show :: ScremaForm rep -> String # showList :: [ScremaForm rep] -> ShowS #
RepTypes rep => Eq (ScremaForm rep) Source #
Instance details Defined in Futhark.IR.SOACS.SOAC Methods (==) :: ScremaForm rep -> ScremaForm rep -> Bool # (/=) :: ScremaForm rep -> ScremaForm rep -> Bool #
RepTypes rep => Ord (ScremaForm rep) Source #
Instance details 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 #
PrettyRep rep => Pretty (ScremaForm rep) Source #
Instance details Defined in Futhark.IR.SOACS.SOAC Methods pretty :: ScremaForm rep -> Doc ann # prettyList :: [ScremaForm rep] -> Doc ann #

data HistOp rep Source #

Information about computing a single histogram.

Constructors

HistOp
Fields histShape :: Shape histRaceFactor :: SubExp Race factor `RF` means that only `1/RF` bins are used. histDest :: [VName] histNeutral :: [SubExp] histOp :: Lambda rep

Instances

Instances details

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

data Scan rep Source #

How to compute a single scan result.

Constructors

Scan
Fields scanLambda :: Lambda rep scanNeutral :: [SubExp]

Instances

Instances details

ASTRep rep => FreeIn (Scan rep) Source #
Instance details Defined in Futhark.IR.SOACS.SOAC Methods freeIn' :: Scan rep -> FV Source #
RepTypes rep => Show (Scan rep) Source #
Instance details Defined in Futhark.IR.SOACS.SOAC Methods showsPrec :: Int -> Scan rep -> ShowS # show :: Scan rep -> String # showList :: [Scan rep] -> ShowS #
RepTypes rep => Eq (Scan rep) Source #
Instance details Defined in Futhark.IR.SOACS.SOAC Methods (==) :: Scan rep -> Scan rep -> Bool # (/=) :: Scan rep -> Scan rep -> Bool #
RepTypes rep => Ord (Scan rep) Source #
Instance details Defined in Futhark.IR.SOACS.SOAC Methods compare :: Scan rep -> Scan rep -> Ordering # (<) :: Scan rep -> Scan rep -> Bool # (<=) :: Scan rep -> Scan rep -> Bool # (>) :: Scan rep -> Scan rep -> Bool # (>=) :: Scan rep -> Scan rep -> Bool # max :: Scan rep -> Scan rep -> Scan rep # min :: Scan rep -> Scan rep -> Scan rep #
PrettyRep rep => Pretty (Scan rep) Source #
Instance details Defined in Futhark.IR.SOACS.SOAC Methods pretty :: Scan rep -> Doc ann # prettyList :: [Scan rep] -> Doc ann #

scanResults :: [Scan rep] -> Int Source #

How many reduction results are produced by these Scans?

singleScan :: Buildable rep => [Scan rep] -> Scan rep Source #

Combine multiple scan operators to a single operator.

data Reduce rep Source #

How to compute a single reduction result.

Constructors

Reduce
Fields redComm :: Commutativity redLambda :: Lambda rep redNeutral :: [SubExp]

Instances

Instances details

ASTRep rep => FreeIn (Reduce rep) Source #
Instance details Defined in Futhark.IR.SOACS.SOAC Methods freeIn' :: Reduce rep -> FV Source #
RepTypes rep => Show (Reduce rep) Source #
Instance details Defined in Futhark.IR.SOACS.SOAC Methods showsPrec :: Int -> Reduce rep -> ShowS # show :: Reduce rep -> String # showList :: [Reduce rep] -> ShowS #
RepTypes rep => Eq (Reduce rep) Source #
Instance details Defined in Futhark.IR.SOACS.SOAC Methods (==) :: Reduce rep -> Reduce rep -> Bool # (/=) :: Reduce rep -> Reduce rep -> Bool #
RepTypes rep => Ord (Reduce rep) Source #
Instance details Defined in Futhark.IR.SOACS.SOAC Methods compare :: Reduce rep -> Reduce rep -> Ordering # (<) :: Reduce rep -> Reduce rep -> Bool # (<=) :: Reduce rep -> Reduce rep -> Bool # (>) :: Reduce rep -> Reduce rep -> Bool # (>=) :: Reduce rep -> Reduce rep -> Bool # max :: Reduce rep -> Reduce rep -> Reduce rep # min :: Reduce rep -> Reduce rep -> Reduce rep #
PrettyRep rep => Pretty (Reduce rep) Source #
Instance details Defined in Futhark.IR.SOACS.SOAC Methods pretty :: Reduce rep -> Doc ann # prettyList :: [Reduce rep] -> Doc ann #

redResults :: [Reduce rep] -> Int Source #

How many reduction results are produced by these Reduces?

singleReduce :: Buildable rep => [Reduce rep] -> Reduce rep Source #

Combine multiple reduction operators to a single operator.

Utility

composeBinds Source #

Arguments

:: (Buildable rep, Ord a)
=> Lambda rep	Producer lambda
-> [a]	Producer outputs to match
-> [a]	Consumer inputs to match
-> Lambda rep	Consumer lambda
-> Stms rep	Let-bindings connecting them

Creates let-bindings to compose two lambda functions (producer → consumer).

When composing two operations where the outputs of one lambda (producer) flow into the inputs of another lambda (consumer), this function generates the necessary let-bindings that connect matching outputs to inputs.

The function looks for outputs from the producer that correspond to inputs expected by the consumer, and creates bindings like: let consumer_param = producer_result

This allows the two lambdas to be composed into a operation.

Returns: Statements containing let-bindings for each matched producer output → consumer input pair. Preserves certificates from the producer results.

Example: If out_p[i] == inp_c[j], then producer's result[i] is bound to consumer's parameter[j]. Unmatched outputs (producer results not consumed) are omitted.

scremaType :: SubExp -> ScremaForm rep -> [Type] Source #

The types produced by a single Screma, given the size of the input array.

soacType :: Typed (LParamInfo rep) => SOAC rep -> [ExtType] Source #

The type of a SOAC.

flatMapNonuniform :: ExtType -> Bool Source #

Is this the type of an irregular result of a FlatMap lambda - one that is concatenated with the results of the other iterations, rather than merely collected? These are exactly the results whose outermost size is the existential size returned by the lambda.

flatMapRowTypes :: ExtLambda rep -> [Type] Source #

The element types of the irregular (concatenated) arrays produced by a FlatMap lambda, with the existential outer dimension stripped. The remaining dimensions are never existential.

flatMapUniformTypes :: ExtLambda rep -> [Type] Source #

The types of the regular results of a FlatMap lambda - the ones that are collected rather than concatenated. These never have existential sizes.

flatMapSplitMeta :: [a] -> ((a, a, a, a), [a]) Source #

Split a list with one element per result of a FlatMap into its metadata results - the size, the shape array, the flag array, and the offset array - and its value results.

flatMapSplitValues :: ExtLambda rep -> [a] -> ([a], [a]) Source #

Split a list with one element per value result of a FlatMap lambda into the irregular and the regular parts.

typeCheckSOAC :: Checkable rep => SOAC (Aliases rep) -> TypeM rep () Source #

Type-check a SOAC.

mkIdentityLambda :: (Buildable rep, MonadFreshNames m) => [Type] -> m (Lambda rep) Source #

Construct a lambda that takes parameters of the given types and simply returns them unchanged.

nilFn :: Buildable rep => Lambda rep Source #

A lambda with no parameters that returns no values.

maposcanomapSOAC :: (Buildable rep, MonadFreshNames m) => Lambda rep -> [Scan rep] -> Lambda rep -> m (ScremaForm rep) Source #

Construct a Screma with possibly multiple scans, the given map function, and a given post lambda.

scanomapSOAC :: (Buildable rep, MonadFreshNames m) => [Scan rep] -> Lambda rep -> m (ScremaForm rep) Source #

Construct a Screma with possibly multiple scans, and the given map function.

redomapSOAC :: (Buildable rep, MonadFreshNames m) => [Reduce rep] -> Lambda rep -> m (ScremaForm rep) Source #

Construct a Screma with possibly multiple reductions, and the given map function.

scanSOAC :: (Buildable rep, MonadFreshNames m) => [Scan rep] -> m (ScremaForm rep) Source #

Construct a Screma with possibly multiple scans, and identity map function.

reduceSOAC :: (Buildable rep, MonadFreshNames m) => [Reduce rep] -> m (ScremaForm rep) Source #

Construct a Screma with possibly multiple reductions, and identity map function.

mapSOAC :: (Buildable rep, MonadFreshNames m) => Lambda rep -> m (ScremaForm rep) Source #

Construct a Screma corresponding to a map.

isMaposcanomapSOAC :: ScremaForm rep -> Maybe (Lambda rep, [Scan rep], Lambda rep) Source #

isScanomapSOAC :: ScremaForm rep -> Maybe ([Scan rep], Lambda rep) Source #

Does this Screma correspond to a scan-map composition?

isRedomapSOAC :: ScremaForm rep -> Maybe ([Reduce rep], Lambda rep) Source #

Does this Screma correspond to a reduce-map composition?

isScanSOAC :: ScremaForm rep -> Maybe [Scan rep] Source #

Does this Screma correspond to pure scan?

isReduceSOAC :: ScremaForm rep -> Maybe [Reduce rep] Source #

Does this Screma correspond to a pure reduce?

isMapSOAC :: ScremaForm rep -> Maybe (Lambda rep) Source #

Does this Screma correspond to a simple map, without any reduction or scan results?

ppScrema :: (PrettyRep rep, Pretty inp) => SubExp -> [inp] -> ScremaForm rep -> Doc ann Source #

Prettyprint the given Screma.

ppHist :: (PrettyRep rep, Pretty inp) => SubExp -> [inp] -> [HistOp rep] -> Lambda rep -> Doc ann Source #

Prettyprint the given histogram operation.

ppStream :: (PrettyRep rep, Pretty inp) => SubExp -> [inp] -> [SubExp] -> Lambda rep -> Doc ann Source #

Prettyprint the given Stream.

Generic traversal

data SOACMapper frep trep (m :: Type -> Type) Source #

Like Mapper, but just for SOACs.

Constructors

SOACMapper
Fields mapOnSOACSubExp :: SubExp -> m SubExp mapOnSOACLambda :: Lambda frep -> m (Lambda trep) mapOnSOACExtLambda :: ExtLambda frep -> m (ExtLambda trep) mapOnSOACVName :: VName -> m VName

identitySOACMapper :: forall rep (m :: Type -> Type). Monad m => SOACMapper rep rep m Source #

A mapper that simply returns the SOAC verbatim.

mapSOACM :: Monad m => SOACMapper frep trep m -> SOAC frep -> m (SOAC trep) Source #

Map a monadic action across the immediate children of a SOAC. The mapping does not descend recursively into subexpressions and is done left-to-right.

traverseSOACStms :: Monad m => OpStmsTraverser m (SOAC rep) rep Source #

A helper for defining TraverseOpStms.