Futhark.Optimise.Simplify.Rule

This module defines the concept of a simplification rule for bindings. The intent is that you pass some context (such as symbol table) and a binding, and is given back a sequence of bindings that compute the same result, but are "better" in some sense.

These rewrite rules are "local", in that they do not maintain any state or look at the program as a whole. Compare this to the fusion algorithm in Futhark.Optimise.Fusion.Fusion, which must be implemented as its own pass.

The rule monad

data RuleM lore a

The monad in which simplification rules are evaluated.

Instances

Attributes lore => LocalScope lore (RuleM lore)

Defined in Futhark.Optimise.Simplify.Rule

Methods

localScope :: Scope lore -> RuleM lore a -> RuleM lore a

Attributes lore => HasScope lore (RuleM lore)

Defined in Futhark.Optimise.Simplify.Rule

Methods

lookupType :: VName -> RuleM lore Type

lookupInfo :: VName -> RuleM lore (NameInfo lore)

askScope :: RuleM lore (Scope lore)

asksScope :: (Scope lore -> a) -> RuleM lore a

Monad (RuleM lore)

Defined in Futhark.Optimise.Simplify.Rule

Methods

(>>=) :: RuleM lore a -> (a -> RuleM lore b) -> RuleM lore b

(>>) :: RuleM lore a -> RuleM lore b -> RuleM lore b

return :: a -> RuleM lore a

fail :: String -> RuleM lore a

Functor (RuleM lore)

Defined in Futhark.Optimise.Simplify.Rule

Methods

fmap :: (a -> b) -> RuleM lore a -> RuleM lore b

(<$) :: a -> RuleM lore b -> RuleM lore a

MonadFail (RuleM lore)

Defined in Futhark.Optimise.Simplify.Rule

Methods

fail :: String -> RuleM lore a

Applicative (RuleM lore)

Defined in Futhark.Optimise.Simplify.Rule

Methods

pure :: a -> RuleM lore a

(<*>) :: RuleM lore (a -> b) -> RuleM lore a -> RuleM lore b

liftA2 :: (a -> b -> c) -> RuleM lore a -> RuleM lore b -> RuleM lore c

(*>) :: RuleM lore a -> RuleM lore b -> RuleM lore b

(<*) :: RuleM lore a -> RuleM lore b -> RuleM lore a

MonadFreshNames (RuleM lore)

Defined in Futhark.Optimise.Simplify.Rule

Methods

getNameSource :: RuleM lore VNameSource

putNameSource :: VNameSource -> RuleM lore ()

(Attributes lore, BinderOps lore) => MonadBinder (RuleM lore)

Defined in Futhark.Optimise.Simplify.Rule

Associated Types

type Lore (RuleM lore) :: Type

Methods

mkExpAttrM :: Pattern (Lore (RuleM lore)) -> Exp (Lore (RuleM lore)) -> RuleM lore (ExpAttr (Lore (RuleM lore)))

mkBodyM :: Stms (Lore (RuleM lore)) -> Result -> RuleM lore (Body (Lore (RuleM lore)))

mkLetNamesM :: [VName] -> Exp (Lore (RuleM lore)) -> RuleM lore (Stm (Lore (RuleM lore)))

addStm :: Stm (Lore (RuleM lore)) -> RuleM lore ()

addStms :: Stms (Lore (RuleM lore)) -> RuleM lore ()

collectStms :: RuleM lore a -> RuleM lore (a, Stms (Lore (RuleM lore)))

certifying :: Certificates -> RuleM lore a -> RuleM lore a

type Lore (RuleM lore)

Defined in Futhark.Optimise.Simplify.Rule

type Lore (RuleM lore) = lore

cannotSimplify :: RuleM lore a

liftMaybe :: Maybe a -> RuleM lore a

Rule definition

data SimplificationRule lore a

A simplification rule takes some argument and a statement, and tries to simplify the statement.

Constructors

RuleGeneric (RuleGeneric lore a)

RuleBasicOp (RuleBasicOp lore a)

RuleIf (RuleIf lore a)

RuleDoLoop (RuleDoLoop lore a)

RuleOp (RuleOp lore a)

type RuleGeneric lore a = a -> Stm lore -> RuleM lore ()

type RuleBasicOp lore a = a -> Pattern lore -> StmAux (ExpAttr lore) -> BasicOp lore -> RuleM lore ()

type RuleIf lore a = a -> Pattern lore -> StmAux (ExpAttr lore) -> (SubExp, BodyT lore, BodyT lore, IfAttr (BranchType lore)) -> RuleM lore ()

type RuleDoLoop lore a = a -> Pattern lore -> StmAux (ExpAttr lore) -> ([(FParam lore, SubExp)], [(FParam lore, SubExp)], LoopForm lore, BodyT lore) -> RuleM lore ()

Top-down rules

type TopDown lore = SymbolTable lore

Context for a rule applied during top-down traversal of the program. Takes a symbol table as argument.

type TopDownRule lore = SimplificationRule lore (TopDown lore)

type TopDownRuleGeneric lore = RuleGeneric lore (TopDown lore)

type TopDownRuleBasicOp lore = RuleBasicOp lore (TopDown lore)

type TopDownRuleIf lore = RuleIf lore (TopDown lore)

type TopDownRuleDoLoop lore = RuleDoLoop lore (TopDown lore)

type TopDownRuleOp lore = RuleOp lore (TopDown lore)

Bottom-up rules

type BottomUp lore = (SymbolTable lore, UsageTable)

Context for a rule applied during bottom-up traversal of the program. Takes a symbol table and usage table as arguments.

type BottomUpRule lore = SimplificationRule lore (BottomUp lore)

type BottomUpRuleGeneric lore = RuleGeneric lore (BottomUp lore)

type BottomUpRuleBasicOp lore = RuleBasicOp lore (BottomUp lore)

type BottomUpRuleIf lore = RuleIf lore (BottomUp lore)

type BottomUpRuleDoLoop lore = RuleDoLoop lore (BottomUp lore)

type BottomUpRuleOp lore = RuleOp lore (BottomUp lore)

Assembling rules

data RuleBook lore

A collection of both top-down and bottom-up rules.

Instances

Semigroup (RuleBook lore)

Defined in Futhark.Optimise.Simplify.Rule

Methods

(<>) :: RuleBook lore -> RuleBook lore -> RuleBook lore

sconcat :: NonEmpty (RuleBook lore) -> RuleBook lore

stimes :: Integral b => b -> RuleBook lore -> RuleBook lore

Monoid (RuleBook lore)

Defined in Futhark.Optimise.Simplify.Rule

Methods

mempty :: RuleBook lore

mappend :: RuleBook lore -> RuleBook lore -> RuleBook lore

mconcat :: [RuleBook lore] -> RuleBook lore

ruleBook :: [TopDownRule m] -> [BottomUpRule m] -> RuleBook m

Construct a rule book from a collection of rules.

Applying rules

topDownSimplifyStm :: (MonadFreshNames m, HasScope lore m, BinderOps lore) => RuleBook lore -> SymbolTable lore -> Stm lore -> m (Maybe (Stms lore))

simplifyStm lookup bnd performs simplification of the binding bnd. If simplification is possible, a replacement list of bindings is returned, that bind at least the same names as the original binding (and possibly more, for intermediate results).

bottomUpSimplifyStm :: (MonadFreshNames m, HasScope lore m, BinderOps lore) => RuleBook lore -> (SymbolTable lore, UsageTable) -> Stm lore -> m (Maybe (Stms lore))

simplifyStm uses bnd performs simplification of the binding bnd. If simplification is possible, a replacement list of bindings is returned, that bind at least the same names as the original binding (and possibly more, for intermediate results). The first argument is the set of names used after this binding.