futhark-0.25.32: An optimising compiler for a functional, array-oriented language.

Safe Haskell | None
Language | GHC2021

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 rep a
- cannotSimplify :: RuleM rep a
- liftMaybe :: Maybe a -> RuleM rep a
- data Rule rep
  - = Simplify (RuleM rep ())
  - | Skip
- data SimplificationRule rep a
  - = 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
- type TopDown rep = SymbolTable rep
- 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)
- type BottomUp rep = (SymbolTable rep, UsageTable)
- 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)
- data RuleBook rep
- ruleBook :: [TopDownRule m] -> [BottomUpRule m] -> RuleBook m
- topDownSimplifyStm :: (MonadFreshNames m, HasScope rep m, PrettyRep rep) => RuleBook rep -> SymbolTable rep -> Stm rep -> m (Maybe (Stms rep))
- bottomUpSimplifyStm :: (MonadFreshNames m, HasScope rep m, PrettyRep rep) => RuleBook rep -> (SymbolTable rep, UsageTable) -> Stm rep -> m (Maybe (Stms rep))

# The rule monad

data RuleM rep a Source #

The monad in which simplification rules are evaluated.

#### Instances

Instances details

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 #
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 #
BuilderOps rep => MonadBuilder (RuleM rep) Source # |

Instance details

Defined in Futhark.Optimise.Simplify.Rule

Associated Types

type Rep (RuleM rep) |
Instance details Defined in Futhark.Optimise.Simplify.Rule type Rep (RuleM rep) = rep

Methods

mkExpDecM :: Pat (LetDec (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 #

MonadFreshNames (RuleM rep) Source # |
Instance details Defined in Futhark.Optimise.Simplify.Rule Methods getNameSource :: RuleM rep VNameSource Source # putNameSource :: VNameSource -> RuleM rep () Source #
Applicative (RuleM rep) Source # |
Instance details Defined in Futhark.Optimise.Simplify.Rule Methods pure :: a -> RuleM rep a Source # (<*>) :: RuleM rep (a -> b) -> RuleM rep a -> RuleM rep b Source # liftA2 :: (a -> b -> c) -> RuleM rep a -> RuleM rep b -> RuleM rep c Source # (*>) :: RuleM rep a -> RuleM rep b -> RuleM rep b Source # (<*) :: RuleM rep a -> RuleM rep b -> RuleM rep a Source #
Functor (RuleM rep) Source # |
Instance details Defined in Futhark.Optimise.Simplify.Rule Methods fmap :: (a -> b) -> RuleM rep a -> RuleM rep b Source # (<$) :: a -> RuleM rep b -> 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 Source # (>>) :: RuleM rep a -> RuleM rep b -> RuleM rep b Source # return :: a -> RuleM rep a Source #
type Rep (RuleM rep) Source # |
Instance details Defined in Futhark.Optimise.Simplify.Rule type Rep (RuleM rep) = rep

cannotSimplify :: RuleM rep a Source #

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) |
RuleMatch (RuleMatch rep a) |
RuleLoop (RuleLoop rep a) |
RuleOp (RuleOp rep a) |

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

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

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

type RuleLoop rep a = a -> Pat (LetDec rep) -> StmAux (ExpDec rep) -> ([(FParam rep, SubExp)], LoopForm, Body 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 TopDownRule rep = SimplificationRule rep (TopDown rep) Source #

type TopDownRuleGeneric rep = RuleGeneric rep (TopDown rep) Source #

type TopDownRuleBasicOp rep = RuleBasicOp rep (TopDown rep) Source #

type TopDownRuleMatch rep = RuleMatch rep (TopDown rep) Source #

type TopDownRuleLoop rep = RuleLoop 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 BottomUpRule rep = SimplificationRule rep (BottomUp rep) Source #

type BottomUpRuleGeneric rep = RuleGeneric rep (BottomUp rep) Source #

type BottomUpRuleBasicOp rep = RuleBasicOp rep (BottomUp rep) Source #

type BottomUpRuleMatch rep = RuleMatch rep (BottomUp rep) Source #

type BottomUpRuleLoop rep = RuleLoop 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

Monoid (RuleBook rep) Source # |
Instance details Defined in Futhark.Optimise.Simplify.Rule Methods mempty :: RuleBook rep Source # mappend :: RuleBook rep -> RuleBook rep -> RuleBook rep Source # mconcat :: [RuleBook rep] -> RuleBook rep Source #
Semigroup (RuleBook rep) Source # |
Instance details Defined in Futhark.Optimise.Simplify.Rule Methods (<>) :: RuleBook rep -> RuleBook rep -> RuleBook rep Source # sconcat :: NonEmpty (RuleBook rep) -> RuleBook rep Source # stimes :: Integral b => b -> RuleBook rep -> RuleBook rep Source #

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, PrettyRep rep) => 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, PrettyRep rep) => 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.