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

ASTLore lore => LocalScope lore (RuleM lore)

Defined in Futhark.Optimise.Simplify.Rule

Methods

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

ASTLore 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

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

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

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

Defined in Futhark.Optimise.Simplify.Rule

Associated Types

type Lore (RuleM lore)

Methods

mkExpDecM :: Pattern (Lore (RuleM lore)) -> Exp (Lore (RuleM lore)) -> RuleM lore (ExpDec (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 Rule lore

An efficient way of encoding whether a simplification rule should even be attempted.

Constructors

Simplify (RuleM lore ())

Give it a shot.

Skip

Don't bother.

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

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