| Safe Haskell | Trustworthy |
|---|---|
| Language | Haskell2010 |
Futhark.Optimise.Simplify.Rule
Description
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.
Synopsis
- data RuleM lore a
- cannotSimplify :: RuleM lore a
- liftMaybe :: Maybe a -> RuleM lore a
- data Rule lore
- data SimplificationRule lore a
- = 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 -> Rule lore
- type RuleBasicOp lore a = a -> Pattern lore -> StmAux (ExpDec lore) -> BasicOp -> Rule lore
- type RuleIf lore a = a -> Pattern lore -> StmAux (ExpDec lore) -> (SubExp, BodyT lore, BodyT lore, IfDec (BranchType lore)) -> Rule lore
- type RuleDoLoop lore a = a -> Pattern lore -> StmAux (ExpDec lore) -> ([(FParam lore, SubExp)], [(FParam lore, SubExp)], LoopForm lore, BodyT lore) -> Rule lore
- type TopDown lore = SymbolTable lore
- 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)
- type BottomUp lore = (SymbolTable lore, UsageTable)
- 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)
- data RuleBook lore
- ruleBook :: [TopDownRule m] -> [BottomUpRule m] -> RuleBook m
- topDownSimplifyStm :: (MonadFreshNames m, HasScope lore m) => RuleBook lore -> SymbolTable lore -> Stm lore -> m (Maybe (Stms lore))
- bottomUpSimplifyStm :: (MonadFreshNames m, HasScope lore m) => RuleBook lore -> (SymbolTable lore, UsageTable) -> Stm lore -> m (Maybe (Stms lore))
The rule monad
The monad in which simplification rules are evaluated.
Instances
cannotSimplify :: RuleM lore a Source #
Rule definition
An efficient way of encoding whether a simplification rule should even be attempted.
data SimplificationRule lore a Source #
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 -> Rule lore Source #
type RuleBasicOp lore a = a -> Pattern lore -> StmAux (ExpDec lore) -> BasicOp -> Rule lore Source #
type RuleIf lore a = a -> Pattern lore -> StmAux (ExpDec lore) -> (SubExp, BodyT lore, BodyT lore, IfDec (BranchType lore)) -> Rule lore Source #
type RuleDoLoop lore a = a -> Pattern lore -> StmAux (ExpDec lore) -> ([(FParam lore, SubExp)], [(FParam lore, SubExp)], LoopForm lore, BodyT lore) -> Rule lore Source #
Top-down rules
type TopDown lore = SymbolTable lore Source #
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) Source #
type TopDownRuleGeneric lore = RuleGeneric lore (TopDown lore) Source #
type TopDownRuleBasicOp lore = RuleBasicOp lore (TopDown lore) Source #
type TopDownRuleIf lore = RuleIf lore (TopDown lore) Source #
type TopDownRuleDoLoop lore = RuleDoLoop lore (TopDown lore) Source #
type TopDownRuleOp lore = RuleOp lore (TopDown lore) Source #
Bottom-up rules
type BottomUp lore = (SymbolTable lore, UsageTable) Source #
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) Source #
type BottomUpRuleGeneric lore = RuleGeneric lore (BottomUp lore) Source #
type BottomUpRuleBasicOp lore = RuleBasicOp lore (BottomUp lore) Source #
type BottomUpRuleIf lore = RuleIf lore (BottomUp lore) Source #
type BottomUpRuleDoLoop lore = RuleDoLoop lore (BottomUp lore) Source #
type BottomUpRuleOp lore = RuleOp lore (BottomUp lore) Source #
Assembling rules
A collection of both top-down and bottom-up rules.
ruleBook :: [TopDownRule m] -> [BottomUpRule m] -> RuleBook m Source #
Construct a rule book from a collection of rules.
Applying rules
topDownSimplifyStm :: (MonadFreshNames m, HasScope lore m) => RuleBook lore -> SymbolTable lore -> Stm lore -> m (Maybe (Stms lore)) Source #
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) => RuleBook lore -> (SymbolTable lore, UsageTable) -> Stm lore -> m (Maybe (Stms lore)) Source #
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.