Safe Haskell	None
Language	Haskell2010

Futhark.Optimise.Simplify.Engine

Contents

Monadic interface
Building blocks

Description

Perform general rule-based simplification based on data dependency information. This module will:

Perform common-subexpression elimination (CSE).
Hoist expressions out of loops (including lambdas) and branches. This is done as aggressively as possible.
Apply simplification rules (see Futhark.Optimise.Simplification.Rules).

If you just want to run the simplifier as simply as possible, you may prefer to use the Futhark.Optimise.Simplify module.

Synopsis

data SimpleM lore a
runSimpleM :: SimpleM lore a -> SimpleOps lore -> Env lore -> VNameSource -> ((a, Bool), VNameSource)
data SimpleOps lore = SimpleOps {
- mkExpDecS :: SymbolTable (Wise lore) -> Pattern (Wise lore) -> Exp (Wise lore) -> SimpleM lore (ExpDec (Wise lore))
- mkBodyS :: SymbolTable (Wise lore) -> Stms (Wise lore) -> Result -> SimpleM lore (Body (Wise lore))
- protectHoistedOpS :: Protect (Binder (Wise lore))
- opUsageS :: Op (Wise lore) -> UsageTable
- simplifyOpS :: SimplifyOp lore (Op lore)
}
type SimplifyOp lore op = op -> SimpleM lore (OpWithWisdom op, Stms (Wise lore))
bindableSimpleOps :: (SimplifiableLore lore, Bindable lore) => SimplifyOp lore (Op lore) -> SimpleOps lore
data Env lore
emptyEnv :: RuleBook (Wise lore) -> HoistBlockers lore -> Env lore
data HoistBlockers lore = HoistBlockers {
- blockHoistPar :: BlockPred (Wise lore)
- blockHoistSeq :: BlockPred (Wise lore)
- blockHoistBranch :: BlockPred (Wise lore)
- isAllocation :: Stm (Wise lore) -> Bool
}
neverBlocks :: BlockPred lore
noExtraHoistBlockers :: HoistBlockers lore
neverHoist :: HoistBlockers lore
type BlockPred lore = SymbolTable lore -> UsageTable -> Stm lore -> Bool
orIf :: BlockPred lore -> BlockPred lore -> BlockPred lore
hasFree :: ASTLore lore => Names -> BlockPred lore
isConsumed :: BlockPred lore
isFalse :: Bool -> BlockPred lore
isOp :: BlockPred lore
isNotSafe :: ASTLore lore => BlockPred lore
asksEngineEnv :: (Env lore -> a) -> SimpleM lore a
askVtable :: SimpleM lore (SymbolTable (Wise lore))
localVtable :: (SymbolTable (Wise lore) -> SymbolTable (Wise lore)) -> SimpleM lore a -> SimpleM lore a
type SimplifiableLore lore = (ASTLore lore, Simplifiable (LetDec lore), Simplifiable (FParamInfo lore), Simplifiable (LParamInfo lore), Simplifiable (RetType lore), Simplifiable (BranchType lore), CanBeWise (Op lore), IndexOp (OpWithWisdom (Op lore)), BinderOps (Wise lore), IsOp (Op lore))
class Simplifiable e where
- simplify :: SimplifiableLore lore => e -> SimpleM lore e
simplifyStms :: SimplifiableLore lore => Stms lore -> SimpleM lore (a, Stms (Wise lore)) -> SimpleM lore (a, Stms (Wise lore))
simplifyFun :: SimplifiableLore lore => FunDef lore -> SimpleM lore (FunDef (Wise lore))
simplifyLambda :: SimplifiableLore lore => Lambda lore -> SimpleM lore (Lambda (Wise lore), Stms (Wise lore))
simplifyLambdaNoHoisting :: SimplifiableLore lore => Lambda lore -> SimpleM lore (Lambda (Wise lore))
bindLParams :: SimplifiableLore lore => [LParam (Wise lore)] -> SimpleM lore a -> SimpleM lore a
simplifyBody :: SimplifiableLore lore => [Diet] -> Body lore -> SimpleM lore (SimplifiedBody lore Result)
type SimplifiedBody lore a = ((a, UsageTable), Stms (Wise lore))
data SymbolTable lore
hoistStms :: SimplifiableLore lore => RuleBook (Wise lore) -> BlockPred (Wise lore) -> SymbolTable (Wise lore) -> UsageTable -> Stms (Wise lore) -> SimpleM lore (Stms (Wise lore), Stms (Wise lore))
blockIf :: SimplifiableLore lore => BlockPred (Wise lore) -> SimpleM lore (SimplifiedBody lore a) -> SimpleM lore ((Stms (Wise lore), a), Stms (Wise lore))
enterLoop :: SimpleM lore a -> SimpleM lore a
module Futhark.Optimise.Simplify.Lore

Monadic interface

data SimpleM lore a Source #

Instances

Instances details

Monad (SimpleM lore) Source #
Instance details Defined in Futhark.Optimise.Simplify.Engine Methods (>>=) :: SimpleM lore a -> (a -> SimpleM lore b) -> SimpleM lore b # (>>) :: SimpleM lore a -> SimpleM lore b -> SimpleM lore b # return :: a -> SimpleM lore a #
Functor (SimpleM lore) Source #
Instance details Defined in Futhark.Optimise.Simplify.Engine Methods fmap :: (a -> b) -> SimpleM lore a -> SimpleM lore b # (<$) :: a -> SimpleM lore b -> SimpleM lore a #
Applicative (SimpleM lore) Source #
Instance details Defined in Futhark.Optimise.Simplify.Engine Methods pure :: a -> SimpleM lore a # (<>) :: SimpleM lore (a -> b) -> SimpleM lore a -> SimpleM lore b # liftA2 :: (a -> b -> c) -> SimpleM lore a -> SimpleM lore b -> SimpleM lore c # (>) :: SimpleM lore a -> SimpleM lore b -> SimpleM lore b # (<*) :: SimpleM lore a -> SimpleM lore b -> SimpleM lore a #
MonadFreshNames (SimpleM lore) Source #
Instance details Defined in Futhark.Optimise.Simplify.Engine Methods getNameSource :: SimpleM lore VNameSource Source # putNameSource :: VNameSource -> SimpleM lore () Source #
SimplifiableLore lore => LocalScope (Wise lore) (SimpleM lore) Source #
Instance details Defined in Futhark.Optimise.Simplify.Engine Methods localScope :: Scope (Wise lore) -> SimpleM lore a -> SimpleM lore a Source #
SimplifiableLore lore => HasScope (Wise lore) (SimpleM lore) Source #
Instance details Defined in Futhark.Optimise.Simplify.Engine Methods lookupType :: VName -> SimpleM lore Type Source # lookupInfo :: VName -> SimpleM lore (NameInfo (Wise lore)) Source # askScope :: SimpleM lore (Scope (Wise lore)) Source # asksScope :: (Scope (Wise lore) -> a) -> SimpleM lore a Source #
MonadReader (SimpleOps lore, Env lore) (SimpleM lore) Source #
Instance details Defined in Futhark.Optimise.Simplify.Engine Methods ask :: SimpleM lore (SimpleOps lore, Env lore) # local :: ((SimpleOps lore, Env lore) -> (SimpleOps lore, Env lore)) -> SimpleM lore a -> SimpleM lore a # reader :: ((SimpleOps lore, Env lore) -> a) -> SimpleM lore a #
MonadState (VNameSource, Bool, Certificates) (SimpleM lore) Source #
Instance details Defined in Futhark.Optimise.Simplify.Engine Methods get :: SimpleM lore (VNameSource, Bool, Certificates) # put :: (VNameSource, Bool, Certificates) -> SimpleM lore () # state :: ((VNameSource, Bool, Certificates) -> (a, (VNameSource, Bool, Certificates))) -> SimpleM lore a #

runSimpleM :: SimpleM lore a -> SimpleOps lore -> Env lore -> VNameSource -> ((a, Bool), VNameSource) Source #

data SimpleOps lore Source #

Constructors

SimpleOps

Fields

mkExpDecS :: SymbolTable (Wise lore) -> Pattern (Wise lore) -> Exp (Wise lore) -> SimpleM lore (ExpDec (Wise lore))
mkBodyS :: SymbolTable (Wise lore) -> Stms (Wise lore) -> Result -> SimpleM lore (Body (Wise lore))
protectHoistedOpS :: Protect (Binder (Wise lore))
Make a hoisted Op safe. The SubExp is a boolean that is true when the value of the statement will actually be used.
opUsageS :: Op (Wise lore) -> UsageTable
simplifyOpS :: SimplifyOp lore (Op lore)

Instances

Instances details

MonadReader (SimpleOps lore, Env lore) (SimpleM lore) Source #
Instance details Defined in Futhark.Optimise.Simplify.Engine Methods ask :: SimpleM lore (SimpleOps lore, Env lore) # local :: ((SimpleOps lore, Env lore) -> (SimpleOps lore, Env lore)) -> SimpleM lore a -> SimpleM lore a # reader :: ((SimpleOps lore, Env lore) -> a) -> SimpleM lore a #

type SimplifyOp lore op = op -> SimpleM lore (OpWithWisdom op, Stms (Wise lore)) Source #

bindableSimpleOps :: (SimplifiableLore lore, Bindable lore) => SimplifyOp lore (Op lore) -> SimpleOps lore Source #

data Env lore Source #

Instances

Instances details

MonadReader (SimpleOps lore, Env lore) (SimpleM lore) Source #
Instance details Defined in Futhark.Optimise.Simplify.Engine Methods ask :: SimpleM lore (SimpleOps lore, Env lore) # local :: ((SimpleOps lore, Env lore) -> (SimpleOps lore, Env lore)) -> SimpleM lore a -> SimpleM lore a # reader :: ((SimpleOps lore, Env lore) -> a) -> SimpleM lore a #

emptyEnv :: RuleBook (Wise lore) -> HoistBlockers lore -> Env lore Source #

data HoistBlockers lore Source #

Constructors

HoistBlockers
Fields blockHoistPar :: BlockPred (Wise lore) Blocker for hoisting out of parallel loops. blockHoistSeq :: BlockPred (Wise lore) Blocker for hoisting out of sequential loops. blockHoistBranch :: BlockPred (Wise lore) Blocker for hoisting out of branches. isAllocation :: Stm (Wise lore) -> Bool

neverBlocks :: BlockPred lore Source #

noExtraHoistBlockers :: HoistBlockers lore Source #

neverHoist :: HoistBlockers lore Source #

type BlockPred lore = SymbolTable lore -> UsageTable -> Stm lore -> Bool Source #

orIf :: BlockPred lore -> BlockPred lore -> BlockPred lore Source #

hasFree :: ASTLore lore => Names -> BlockPred lore Source #

isConsumed :: BlockPred lore Source #

isFalse :: Bool -> BlockPred lore Source #

isOp :: BlockPred lore Source #

isNotSafe :: ASTLore lore => BlockPred lore Source #

asksEngineEnv :: (Env lore -> a) -> SimpleM lore a Source #

askVtable :: SimpleM lore (SymbolTable (Wise lore)) Source #

localVtable :: (SymbolTable (Wise lore) -> SymbolTable (Wise lore)) -> SimpleM lore a -> SimpleM lore a Source #

Building blocks

type SimplifiableLore lore = (ASTLore lore, Simplifiable (LetDec lore), Simplifiable (FParamInfo lore), Simplifiable (LParamInfo lore), Simplifiable (RetType lore), Simplifiable (BranchType lore), CanBeWise (Op lore), IndexOp (OpWithWisdom (Op lore)), BinderOps (Wise lore), IsOp (Op lore)) Source #

class Simplifiable e where Source #

Methods

simplify :: SimplifiableLore lore => e -> SimpleM lore e Source #

Instances

Instances details

Simplifiable Int Source #
Instance details Defined in Futhark.Optimise.Simplify.Engine Methods simplify :: SimplifiableLore lore => Int -> SimpleM lore Int Source #
Simplifiable () Source #
Instance details Defined in Futhark.Optimise.Simplify.Engine Methods simplify :: SimplifiableLore lore => () -> SimpleM lore () Source #
Simplifiable PrimType Source #
Instance details Defined in Futhark.Optimise.Simplify.Engine Methods simplify :: SimplifiableLore lore => PrimType -> SimpleM lore PrimType Source #
Simplifiable VName Source #
Instance details Defined in Futhark.Optimise.Simplify.Engine Methods simplify :: SimplifiableLore lore => VName -> SimpleM lore VName Source #
Simplifiable SubExp Source #
Instance details Defined in Futhark.Optimise.Simplify.Engine Methods simplify :: SimplifiableLore lore => SubExp -> SimpleM lore SubExp Source #
Simplifiable Certificates Source #
Instance details Defined in Futhark.Optimise.Simplify.Engine Methods simplify :: SimplifiableLore lore => Certificates -> SimpleM lore Certificates Source #
Simplifiable Space Source #
Instance details Defined in Futhark.Optimise.Simplify.Engine Methods simplify :: SimplifiableLore lore => Space -> SimpleM lore Space Source #
Simplifiable ExtSize Source #
Instance details Defined in Futhark.Optimise.Simplify.Engine Methods simplify :: SimplifiableLore lore => ExtSize -> SimpleM lore ExtSize Source #
Simplifiable MemReturn Source #
Instance details Defined in Futhark.IR.Mem Methods simplify :: SimplifiableLore lore => MemReturn -> SimpleM lore MemReturn Source #
Simplifiable MemBind Source #
Instance details Defined in Futhark.IR.Mem Methods simplify :: SimplifiableLore lore => MemBind -> SimpleM lore MemBind Source #
Simplifiable SegSpace Source #
Instance details Defined in Futhark.IR.SegOp Methods simplify :: SimplifiableLore lore => SegSpace -> SimpleM lore SegSpace Source #
Simplifiable KernelResult Source #
Instance details Defined in Futhark.IR.SegOp Methods simplify :: SimplifiableLore lore => KernelResult -> SimpleM lore KernelResult Source #
Simplifiable SplitOrdering Source #
Instance details Defined in Futhark.IR.SegOp Methods simplify :: SimplifiableLore lore => SplitOrdering -> SimpleM lore SplitOrdering Source #
Simplifiable SegLevel Source #
Instance details Defined in Futhark.IR.Kernels.Kernel Methods simplify :: SimplifiableLore lore => SegLevel -> SimpleM lore SegLevel Source #
Simplifiable a => Simplifiable [a] Source #
Instance details Defined in Futhark.Optimise.Simplify.Engine Methods simplify :: SimplifiableLore lore => [a] -> SimpleM lore [a] Source #
Simplifiable [FunReturns] Source #
Instance details Defined in Futhark.IR.Mem Methods simplify :: SimplifiableLore lore => [FunReturns] -> SimpleM lore [FunReturns] Source #
Simplifiable a => Simplifiable (Maybe a) Source #
Instance details Defined in Futhark.Optimise.Simplify.Engine Methods simplify :: SimplifiableLore lore => Maybe a -> SimpleM lore (Maybe a) Source #
Simplifiable d => Simplifiable (DimIndex d) Source #
Instance details Defined in Futhark.Optimise.Simplify.Engine Methods simplify :: SimplifiableLore lore => DimIndex d -> SimpleM lore (DimIndex d) Source #
Simplifiable d => Simplifiable (ShapeBase d) Source #
Instance details Defined in Futhark.Optimise.Simplify.Engine Methods simplify :: SimplifiableLore lore => ShapeBase d -> SimpleM lore (ShapeBase d) Source #
(Simplifiable a, Simplifiable b) => Simplifiable (a, b) Source #
Instance details Defined in Futhark.Optimise.Simplify.Engine Methods simplify :: SimplifiableLore lore => (a, b) -> SimpleM lore (a, b) Source #
Simplifiable shape => Simplifiable (TypeBase shape u) Source #
Instance details Defined in Futhark.Optimise.Simplify.Engine Methods simplify :: SimplifiableLore lore => TypeBase shape u -> SimpleM lore (TypeBase shape u) Source #
(Simplifiable a, Simplifiable b, Simplifiable c) => Simplifiable (a, b, c) Source #
Instance details Defined in Futhark.Optimise.Simplify.Engine Methods simplify :: SimplifiableLore lore => (a, b, c) -> SimpleM lore (a, b, c) Source #
(Simplifiable d, Simplifiable ret) => Simplifiable (MemInfo d u ret) Source #
Instance details Defined in Futhark.IR.Mem Methods simplify :: SimplifiableLore lore => MemInfo d u ret -> SimpleM lore (MemInfo d u ret) Source #

simplifyStms :: SimplifiableLore lore => Stms lore -> SimpleM lore (a, Stms (Wise lore)) -> SimpleM lore (a, Stms (Wise lore)) Source #

simplifyFun :: SimplifiableLore lore => FunDef lore -> SimpleM lore (FunDef (Wise lore)) Source #

simplifyLambda :: SimplifiableLore lore => Lambda lore -> SimpleM lore (Lambda (Wise lore), Stms (Wise lore)) Source #

simplifyLambdaNoHoisting :: SimplifiableLore lore => Lambda lore -> SimpleM lore (Lambda (Wise lore)) Source #

bindLParams :: SimplifiableLore lore => [LParam (Wise lore)] -> SimpleM lore a -> SimpleM lore a Source #

simplifyBody :: SimplifiableLore lore => [Diet] -> Body lore -> SimpleM lore (SimplifiedBody lore Result) Source #

Simplify a single body. The [Diet] only covers the value elements, because the context cannot be consumed.

type SimplifiedBody lore a = ((a, UsageTable), Stms (Wise lore)) Source #

data SymbolTable lore Source #

Instances

Instances details

Semigroup (SymbolTable lore) Source #
Instance details Defined in Futhark.Analysis.SymbolTable Methods (<>) :: SymbolTable lore -> SymbolTable lore -> SymbolTable lore # sconcat :: NonEmpty (SymbolTable lore) -> SymbolTable lore # stimes :: Integral b => b -> SymbolTable lore -> SymbolTable lore #
Monoid (SymbolTable lore) Source #
Instance details Defined in Futhark.Analysis.SymbolTable Methods mempty :: SymbolTable lore # mappend :: SymbolTable lore -> SymbolTable lore -> SymbolTable lore # mconcat :: [SymbolTable lore] -> SymbolTable lore #

hoistStms :: SimplifiableLore lore => RuleBook (Wise lore) -> BlockPred (Wise lore) -> SymbolTable (Wise lore) -> UsageTable -> Stms (Wise lore) -> SimpleM lore (Stms (Wise lore), Stms (Wise lore)) Source #

blockIf :: SimplifiableLore lore => BlockPred (Wise lore) -> SimpleM lore (SimplifiedBody lore a) -> SimpleM lore ((Stms (Wise lore), a), Stms (Wise lore)) Source #

enterLoop :: SimpleM lore a -> SimpleM lore a Source #

Indicate in the symbol table that we have descended into a loop.

module Futhark.Optimise.Simplify.Lore