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

The monad in which simplification rules are evaluated.

Instances

ASTRep rep => HasScope rep (RuleM rep)

Defined in Futhark.Optimise.Simplify.Rule

Methods

lookupType :: VName -> RuleM rep Type

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

askScope :: RuleM rep (Scope rep)

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

ASTRep rep => LocalScope rep (RuleM rep)

Defined in Futhark.Optimise.Simplify.Rule

Methods

localScope :: Scope rep -> RuleM rep a -> RuleM rep a

Applicative (RuleM rep)

Defined in Futhark.Optimise.Simplify.Rule

Methods

pure :: a -> RuleM rep a

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

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

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

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

Functor (RuleM rep)

Defined in Futhark.Optimise.Simplify.Rule

Methods

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

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

Monad (RuleM rep)

Defined in Futhark.Optimise.Simplify.Rule

Methods

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

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

return :: a -> RuleM rep a

BuilderOps rep => MonadBuilder (RuleM rep)

Defined in Futhark.Optimise.Simplify.Rule

Associated Types

type Rep (RuleM rep)

Methods

mkExpDecM :: Pat (LetDec (Rep (RuleM rep))) -> Exp (Rep (RuleM rep)) -> RuleM rep (ExpDec (Rep (RuleM rep)))

mkBodyM :: Stms (Rep (RuleM rep)) -> Result -> RuleM rep (Body (Rep (RuleM rep)))

mkLetNamesM :: [VName] -> Exp (Rep (RuleM rep)) -> RuleM rep (Stm (Rep (RuleM rep)))

addStm :: Stm (Rep (RuleM rep)) -> RuleM rep ()

addStms :: Stms (Rep (RuleM rep)) -> RuleM rep ()

collectStms :: RuleM rep a -> RuleM rep (a, Stms (Rep (RuleM rep)))

certifying :: Certs -> RuleM rep a -> RuleM rep a

MonadFreshNames (RuleM rep)

Defined in Futhark.Optimise.Simplify.Rule

Methods

getNameSource :: RuleM rep VNameSource

putNameSource :: VNameSource -> RuleM rep ()

type Rep (RuleM rep)

Defined in Futhark.Optimise.Simplify.Rule

type Rep (RuleM rep) = rep

cannotSimplify :: RuleM rep a

liftMaybe :: Maybe a -> RuleM rep a

Rule definition

data Rule rep

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

Constructors

Simplify (RuleM rep ())

Give it a shot.

Skip

Don't bother.

data SimplificationRule rep a

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

Constructors

RuleGeneric (RuleGeneric rep a)

RuleBasicOp (RuleBasicOp rep a)

RuleMatch (RuleMatch rep a)

RuleLoop (RuleLoop rep a)

RuleOp (RuleOp rep a)

type RuleGeneric rep a = a -> Stm rep -> Rule rep

type RuleBasicOp rep a = a -> Pat (LetDec rep) -> StmAux (ExpDec rep) -> BasicOp -> Rule rep

type RuleMatch rep a = a -> Pat (LetDec rep) -> StmAux (ExpDec rep) -> ([SubExp], [Case (Body rep)], Body rep, MatchDec (BranchType rep)) -> Rule rep

type RuleLoop rep a = a -> Pat (LetDec rep) -> StmAux (ExpDec rep) -> ([(FParam rep, SubExp)], LoopForm, Body rep) -> Rule rep

Top-down rules

type TopDown rep = SymbolTable rep

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

type TopDownRule rep = SimplificationRule rep (TopDown rep)

type TopDownRuleGeneric rep = RuleGeneric rep (TopDown rep)

type TopDownRuleBasicOp rep = RuleBasicOp rep (TopDown rep)

type TopDownRuleMatch rep = RuleMatch rep (TopDown rep)

type TopDownRuleLoop rep = RuleLoop rep (TopDown rep)

type TopDownRuleOp rep = RuleOp rep (TopDown rep)

Bottom-up rules

type BottomUp rep = (SymbolTable rep, UsageTable)

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

type BottomUpRule rep = SimplificationRule rep (BottomUp rep)

type BottomUpRuleGeneric rep = RuleGeneric rep (BottomUp rep)

type BottomUpRuleBasicOp rep = RuleBasicOp rep (BottomUp rep)

type BottomUpRuleMatch rep = RuleMatch rep (BottomUp rep)

type BottomUpRuleLoop rep = RuleLoop rep (BottomUp rep)

type BottomUpRuleOp rep = RuleOp rep (BottomUp rep)

Assembling rules

data RuleBook rep

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

Instances

Monoid (RuleBook rep)

Defined in Futhark.Optimise.Simplify.Rule

Methods

mempty :: RuleBook rep

mappend :: RuleBook rep -> RuleBook rep -> RuleBook rep

mconcat :: [RuleBook rep] -> RuleBook rep

Semigroup (RuleBook rep)

Defined in Futhark.Optimise.Simplify.Rule

Methods

(<>) :: RuleBook rep -> RuleBook rep -> RuleBook rep

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

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

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

Construct a rule book from a collection of rules.

Applying rules

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

simplifyStm lookup stm performs simplification of the binding stm. 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 rep m, PrettyRep rep) => RuleBook rep -> (SymbolTable rep, UsageTable) -> Stm rep -> m (Maybe (Stms rep))

simplifyStm uses stm performs simplification of the binding stm. 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.