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 [SubExp] [SubExp] (Lambda rep)
- | VJP [SubExp] [SubExp] (Lambda rep)
- | Screma SubExp [VName] (ScremaForm rep)
data ScremaForm rep = ScremaForm {
- scremaLambda :: Lambda rep
- scremaScans :: [Scan rep]
- scremaReduces :: [Reduce 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
scremaType :: SubExp -> ScremaForm rep -> [Type]
soacType :: Typed (LParamInfo rep) => SOAC rep -> [Type]
typeCheckSOAC :: Checkable rep => SOAC (Aliases rep) -> TypeM rep ()
mkIdentityLambda :: (Buildable rep, MonadFreshNames m) => [Type] -> m (Lambda rep)
isIdentityLambda :: Lambda rep -> Bool
nilFn :: Buildable rep => Lambda rep
scanomapSOAC :: [Scan rep] -> Lambda rep -> ScremaForm rep
redomapSOAC :: [Reduce rep] -> Lambda rep -> ScremaForm rep
scanSOAC :: (Buildable rep, MonadFreshNames m) => [Scan rep] -> m (ScremaForm rep)
reduceSOAC :: (Buildable rep, MonadFreshNames m) => [Reduce rep] -> m (ScremaForm rep)
mapSOAC :: Lambda rep -> ScremaForm 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)
- 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 [SubExp] [SubExp] (Lambda rep)
VJP [SubExp] [SubExp] (Lambda rep)
Screma SubExp [VName] (ScremaForm rep)	A combination of scan, reduction, and map. The first `SubExp` is the size of the input arrays.

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 #
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 #
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 => 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]

Instances

Instances details

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 #
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 # (/=) :: 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 #

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

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 #
ASTRep rep => FreeIn (HistOp rep) Source #
Instance details Defined in Futhark.IR.SOACS.SOAC Methods freeIn' :: HistOp rep -> FV Source #
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

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 #
ASTRep rep => FreeIn (Scan rep) Source #
Instance details Defined in Futhark.IR.SOACS.SOAC Methods freeIn' :: Scan rep -> FV Source #
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

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 #
ASTRep rep => FreeIn (Reduce rep) Source #
Instance details Defined in Futhark.IR.SOACS.SOAC Methods freeIn' :: Reduce rep -> FV Source #
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

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 -> [Type] Source #

The type of a SOAC.

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.

isIdentityLambda :: Lambda rep -> Bool Source #

Is the given lambda an identity lambda?

nilFn :: Buildable rep => Lambda rep Source #

A lambda with no parameters that returns no values.

scanomapSOAC :: [Scan rep] -> Lambda rep -> ScremaForm rep Source #

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

redomapSOAC :: [Reduce rep] -> Lambda rep -> 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 :: Lambda rep -> ScremaForm rep Source #

Construct a Screma corresponding to a map.

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) 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.