Feldspar.DSL.Sharing

Common sub-expression elimination and variable hoisting for Lam expressions.

Documentation

substitute

Arguments

:: (ExprEq expr, Typeable ra, Typeable a, Typeable rb, Typeable b)

=> Lam expr ra a

Sub-expression to be replaced

-> Lam expr ra a

Replacing sub-expression

-> Lam expr rb b

Whole expression

-> Lam expr rb b

Substituting a sub-expression

count

Arguments

:: (ExprEq expr, Typeable ra, Typeable a, Typeable rb, Typeable b)

=> Lam expr ra a

Sub-expression

-> Lam expr rb b

Whole expression

-> Integer

Count the number of occurrences of a sub-expression

countM :: (ExprEq expr, Typeable ra, Typeable a, Typeable rb, Typeable b) => Lam expr ra a -> Lam expr rb b -> State Integer Integer

countNonEq :: (ExprEq expr, Typeable ra, Typeable a, Typeable rb, Typeable b) => Lam expr ra a -> Lam expr rb b -> State Integer Integer

data SomeLam expr

Constructors

forall ra a . (Typeable ra, Typeable a) => SomeLam (Lam expr ra a)

data Params expr

Custom parameters to sharing transformation. The necessary predicate gives a necessary condition for lifting an expression, and sufficient gives a sufficient condition. Note that necessary takes precedence over sufficient.

The sharingPoint field determines whether the expression is a valid point for introducing a Let.

Constructors

Params

Fields

necessary :: SomeLam expr -> Bool

sufficient :: SomeLam expr -> Bool

sharingPoint :: SomeLam expr -> Bool

data Env expr

Constructors

Env

Fields

inLambda :: Bool

Whether the current expression is inside a lambda

subExpr :: Bool

Whether the current expression is a sub-expression

counter :: SomeLam expr -> Integer

Counting the number of occurrences of an expression in the environment

simpleParams :: Params expr

initEnv :: (ExprEq expr, Typeable ra, Typeable a) => Lam expr ra a -> Env expr

compound :: Lam expr ra a -> Bool

Checks whether an expression is compound

independent :: Lam expr ra a -> Bool

Checks if the expression does not contain any PLACEHOLDER variables

liftable :: (Typeable ra, Typeable a) => Params expr -> Env expr -> Lam expr ra a -> Bool

Checks whether a sub-expression in a given environment can be lifted out

choose :: (Typeable ra, Typeable a) => Params expr -> Env expr -> Lam expr ra a -> Maybe (SomeLam expr)

Chooses a sub-expression to lift out

sharing :: forall expr ra a. (ExprEq expr, Typeable ra, Typeable a) => Params expr -> Lam expr ra a -> Lam expr ra a

Perform common sub-expression elimination and variable hoisting

descend :: (ExprEq expr, Typeable ra, Typeable a) => Params expr -> Lam expr ra a -> Lam expr ra a

simpleSharing :: (ExprEq expr, Typeable ra, Typeable a) => Lam expr ra a -> Lam expr ra a

isFunction :: forall expr ra a. Typeable a => Lam expr ra a -> Bool

Checks if the expression computes a function. Can be used in the parameters passed to sharing.