futhark-0.20.2: An optimising compiler for a functional, array-oriented language.
Safe HaskellTrustworthy
LanguageHaskell2010

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

The rule monad

data RuleM rep a Source #

The monad in which simplification rules are evaluated.

Instances

Instances details
ASTRep rep => LocalScope rep (RuleM rep) Source # 
Instance details

Defined in Futhark.Optimise.Simplify.Rule

Methods

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

ASTRep rep => HasScope rep (RuleM rep) Source # 
Instance details

Defined in Futhark.Optimise.Simplify.Rule

Methods

lookupType :: VName -> RuleM rep Type Source #

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

askScope :: RuleM rep (Scope rep) Source #

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

Monad (RuleM rep) Source # 
Instance details

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 #

Functor (RuleM rep) Source # 
Instance details

Defined in Futhark.Optimise.Simplify.Rule

Methods

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

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

Applicative (RuleM rep) Source # 
Instance details

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 #

MonadFreshNames (RuleM rep) Source # 
Instance details

Defined in Futhark.Optimise.Simplify.Rule

(ASTRep rep, BuilderOps rep) => MonadBuilder (RuleM rep) Source # 
Instance details

Defined in Futhark.Optimise.Simplify.Rule

Associated Types

type Rep (RuleM rep) Source #

Methods

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

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

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

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

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

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

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

type Rep (RuleM rep) Source # 
Instance details

Defined in Futhark.Optimise.Simplify.Rule

type Rep (RuleM rep) = rep

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

Rule definition

data Rule rep Source #

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

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

Constructors

RuleGeneric (RuleGeneric rep a) 
RuleBasicOp (RuleBasicOp rep a) 
RuleIf (RuleIf rep a) 
RuleDoLoop (RuleDoLoop rep a) 
RuleOp (RuleOp rep a) 

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

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

type RuleIf rep a = a -> Pat rep -> StmAux (ExpDec rep) -> (SubExp, BodyT rep, BodyT rep, IfDec (BranchType rep)) -> Rule rep Source #

type RuleDoLoop rep a = a -> Pat rep -> StmAux (ExpDec rep) -> ([(FParam rep, SubExp)], LoopForm rep, BodyT rep) -> Rule rep Source #

Top-down rules

type TopDown rep = SymbolTable rep Source #

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

type TopDownRuleIf rep = RuleIf rep (TopDown rep) Source #

type TopDownRuleOp rep = RuleOp rep (TopDown rep) Source #

Bottom-up rules

type BottomUp rep = (SymbolTable rep, UsageTable) Source #

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

type BottomUpRuleIf rep = RuleIf rep (BottomUp rep) Source #

type BottomUpRuleOp rep = RuleOp rep (BottomUp rep) Source #

Assembling rules

data RuleBook rep Source #

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

Instances

Instances details
Semigroup (RuleBook rep) Source # 
Instance details

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 #

Monoid (RuleBook rep) Source # 
Instance details

Defined in Futhark.Optimise.Simplify.Rule

Methods

mempty :: RuleBook rep #

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

mconcat :: [RuleBook rep] -> RuleBook rep #

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

Construct a rule book from a collection of rules.

Applying rules

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

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) => RuleBook rep -> (SymbolTable rep, UsageTable) -> Stm rep -> m (Maybe (Stms rep)) Source #

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.