Safe Haskell	None
Language	Haskell2010

Futhark.Optimise.Simplify.Rule

Contents

The rule monad
Rule definition
Top-down rules
Bottom-up rules
Assembling rules
Applying rules

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 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 -> 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 ()
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, BinderOps lore) => RuleBook lore -> SymbolTable lore -> Stm lore -> m (Maybe (Stms lore))
bottomUpSimplifyStm :: (MonadFreshNames m, HasScope lore m, BinderOps lore) => RuleBook lore -> (SymbolTable lore, UsageTable) -> Stm lore -> m (Maybe (Stms lore))

The rule monad

data RuleM lore a Source #

The monad in which simplification rules are evaluated.

Instances

Attributes lore => LocalScope lore (RuleM lore) Source #
Instance details Defined in Futhark.Optimise.Simplify.Rule Methods localScope :: Scope lore -> RuleM lore a -> RuleM lore a Source #
Attributes lore => HasScope lore (RuleM lore) Source #
Instance details Defined in Futhark.Optimise.Simplify.Rule Methods lookupType :: VName -> RuleM lore Type Source # lookupInfo :: VName -> RuleM lore (NameInfo lore) Source # askScope :: RuleM lore (Scope lore) Source # asksScope :: (Scope lore -> a) -> RuleM lore a Source #
Monad (RuleM lore) Source #
Instance details 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) Source #
Instance details 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) Source #
Instance details Defined in Futhark.Optimise.Simplify.Rule Methods fail :: String -> RuleM lore a #
Applicative (RuleM lore) Source #
Instance details 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) Source #
Instance details Defined in Futhark.Optimise.Simplify.Rule Methods getNameSource :: RuleM lore VNameSource Source # putNameSource :: VNameSource -> RuleM lore () Source #
(Attributes lore, BinderOps lore) => MonadBinder (RuleM lore) Source #
Instance details Defined in Futhark.Optimise.Simplify.Rule Associated Types type Lore (RuleM lore) :: Type Source # Methods mkExpAttrM :: Pattern (Lore (RuleM lore)) -> Exp (Lore (RuleM lore)) -> RuleM lore (ExpAttr (Lore (RuleM lore))) Source # mkBodyM :: Stms (Lore (RuleM lore)) -> Result -> RuleM lore (Body (Lore (RuleM lore))) Source # mkLetNamesM :: [VName] -> Exp (Lore (RuleM lore)) -> RuleM lore (Stm (Lore (RuleM lore))) Source # addStm :: Stm (Lore (RuleM lore)) -> RuleM lore () Source # addStms :: Stms (Lore (RuleM lore)) -> RuleM lore () Source # collectStms :: RuleM lore a -> RuleM lore (a, Stms (Lore (RuleM lore))) Source # certifying :: Certificates -> RuleM lore a -> RuleM lore a Source #
type Lore (RuleM lore) Source #
Instance details Defined in Futhark.Optimise.Simplify.Rule type Lore (RuleM lore) = lore

cannotSimplify :: RuleM lore a Source #

liftMaybe :: Maybe a -> RuleM lore a Source #

Rule definition

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 -> RuleM lore () Source #

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

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

type RuleDoLoop lore a = a -> Pattern lore -> StmAux (ExpAttr lore) -> ([(FParam lore, SubExp)], [(FParam lore, SubExp)], LoopForm lore, BodyT lore) -> RuleM 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

data RuleBook lore Source #

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

Instances

Semigroup (RuleBook lore) Source #
Instance details 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) Source #
Instance details 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 Source #

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)) 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, BinderOps lore) => 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.