Futhark.Optimise.Simplify.Engine

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.

Monadic interface

data SimpleM lore a

Instances

MonadWriter Certificates (SimpleM lore)

Defined in Futhark.Optimise.Simplify.Engine

Methods

writer :: (a, Certificates) -> SimpleM lore a

tell :: Certificates -> SimpleM lore ()

listen :: SimpleM lore a -> SimpleM lore (a, Certificates)

pass :: SimpleM lore (a, Certificates -> Certificates) -> SimpleM lore a

Monad (SimpleM lore)

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

fail :: String -> SimpleM lore a

Functor (SimpleM lore)

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)

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)

Defined in Futhark.Optimise.Simplify.Engine

Methods

getNameSource :: SimpleM lore VNameSource

putNameSource :: VNameSource -> SimpleM lore ()

SimplifiableLore lore => LocalScope (Wise lore) (SimpleM lore)

Defined in Futhark.Optimise.Simplify.Engine

Methods

localScope :: Scope (Wise lore) -> SimpleM lore a -> SimpleM lore a

SimplifiableLore lore => HasScope (Wise lore) (SimpleM lore)

Defined in Futhark.Optimise.Simplify.Engine

Methods

lookupType :: VName -> SimpleM lore Type

lookupInfo :: VName -> SimpleM lore (NameInfo (Wise lore))

askScope :: SimpleM lore (Scope (Wise lore))

asksScope :: (Scope (Wise lore) -> a) -> SimpleM lore a

MonadState (VNameSource, Bool) (SimpleM lore)

Defined in Futhark.Optimise.Simplify.Engine

Methods

get :: SimpleM lore (VNameSource, Bool)

put :: (VNameSource, Bool) -> SimpleM lore ()

state :: ((VNameSource, Bool) -> (a, (VNameSource, Bool))) -> SimpleM lore a

MonadReader (SimpleOps lore, Env lore) (SimpleM lore)

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

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

subSimpleM :: (MonadFreshNames m, SameScope outerlore lore, ExpAttr outerlore ~ ExpAttr lore, BodyAttr outerlore ~ BodyAttr lore, RetType outerlore ~ RetType lore, BranchType outerlore ~ BranchType lore) => SimpleOps lore -> Env lore -> SymbolTable (Wise outerlore) -> SimpleM lore a -> m (a, Bool)

data SimpleOps lore

Constructors

SimpleOps

Fields

• mkExpAttrS :: SymbolTable (Wise lore) -> Pattern (Wise lore) -> Exp (Wise lore) -> SimpleM lore (ExpAttr (Wise lore))
• mkBodyS :: SymbolTable (Wise lore) -> Stms (Wise lore) -> Result -> SimpleM lore (Body (Wise lore))
• mkLetNamesS :: SymbolTable (Wise lore) -> [VName] -> Exp (Wise lore) -> SimpleM lore (Stm (Wise lore), Stms (Wise lore))
• simplifyOpS :: SimplifyOp lore

Instances

MonadReader (SimpleOps lore, Env lore) (SimpleM lore)

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 lore -> SimpleM lore (OpWithWisdom (Op lore), Stms (Wise lore))

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

data Env lore

Instances

MonadReader (SimpleOps lore, Env lore) (SimpleM lore)

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

data HoistBlockers lore

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.

• getArraySizes :: Stm (Wise lore) -> Names

  gets the sizes of arrays from a binding.

• isAllocation :: Stm (Wise lore) -> Bool

neverBlocks :: BlockPred lore

noExtraHoistBlockers :: HoistBlockers lore

type BlockPred lore = UsageTable -> Stm lore -> Bool

orIf :: BlockPred lore -> BlockPred lore -> BlockPred lore

hasFree :: Attributes lore => Names -> BlockPred lore

isConsumed :: BlockPred lore

isFalse :: Bool -> BlockPred lore

isOp :: BlockPred lore

isNotSafe :: Attributes lore => BlockPred lore

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

changed :: SimpleM lore ()

Mark that we have changed something and it would be a good idea to re-run the simplifier.

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

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

Building blocks

type SimplifiableLore lore = (Attributes lore, Simplifiable (LetAttr lore), Simplifiable (FParamAttr lore), Simplifiable (LParamAttr lore), Simplifiable (RetType lore), Simplifiable (BranchType lore), CanBeWise (Op lore), IndexOp (OpWithWisdom (Op lore)), BinderOps (Wise lore), IsOp (Op lore))

class Simplifiable e where

Methods

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

Instances

Simplifiable Int

Defined in Futhark.Optimise.Simplify.Engine

Methods

simplify :: SimplifiableLore lore => Int -> SimpleM lore Int

Simplifiable VName

Defined in Futhark.Optimise.Simplify.Engine

Methods

simplify :: SimplifiableLore lore => VName -> SimpleM lore VName

Simplifiable SubExp

Defined in Futhark.Optimise.Simplify.Engine

Methods

simplify :: SimplifiableLore lore => SubExp -> SimpleM lore SubExp

Simplifiable Certificates

Defined in Futhark.Optimise.Simplify.Engine

Methods

simplify :: SimplifiableLore lore => Certificates -> SimpleM lore Certificates

Simplifiable ExtSize

Defined in Futhark.Optimise.Simplify.Engine

Methods

simplify :: SimplifiableLore lore => ExtSize -> SimpleM lore ExtSize

Simplifiable CombineSpace

Defined in Futhark.Representation.Kernels.Simplify

Methods

simplify :: SimplifiableLore lore => CombineSpace -> SimpleM lore CombineSpace

Simplifiable SplitOrdering

Defined in Futhark.Representation.Kernels.Simplify

Methods

simplify :: SimplifiableLore lore => SplitOrdering -> SimpleM lore SplitOrdering

Simplifiable WhichThreads

Defined in Futhark.Representation.Kernels.Simplify

Methods

simplify :: SimplifiableLore lore => WhichThreads -> SimpleM lore WhichThreads

Simplifiable KernelResult

Defined in Futhark.Representation.Kernels.Simplify

Methods

simplify :: SimplifiableLore lore => KernelResult -> SimpleM lore KernelResult

Simplifiable SpaceStructure

Defined in Futhark.Representation.Kernels.Simplify

Methods

simplify :: SimplifiableLore lore => SpaceStructure -> SimpleM lore SpaceStructure

Simplifiable KernelSpace

Defined in Futhark.Representation.Kernels.Simplify

Methods

simplify :: SimplifiableLore lore => KernelSpace -> SimpleM lore KernelSpace

Simplifiable MemReturn

Defined in Futhark.Representation.ExplicitMemory

Methods

simplify :: SimplifiableLore lore => MemReturn -> SimpleM lore MemReturn

Simplifiable MemBind

Defined in Futhark.Representation.ExplicitMemory

Methods

simplify :: SimplifiableLore lore => MemBind -> SimpleM lore MemBind

Simplifiable a => Simplifiable [a]

Defined in Futhark.Optimise.Simplify.Engine

Methods

simplify :: SimplifiableLore lore => [a] -> SimpleM lore [a]

Simplifiable [FunReturns]

Defined in Futhark.Representation.ExplicitMemory

Methods

simplify :: SimplifiableLore lore => [FunReturns] -> SimpleM lore [FunReturns]

Simplifiable a => Simplifiable (Maybe a)

Defined in Futhark.Optimise.Simplify.Engine

Methods

simplify :: SimplifiableLore lore => Maybe a -> SimpleM lore (Maybe a)

Simplifiable d => Simplifiable (DimIndex d)

Defined in Futhark.Optimise.Simplify.Engine

Methods

simplify :: SimplifiableLore lore => DimIndex d -> SimpleM lore (DimIndex d)

Simplifiable d => Simplifiable (ShapeBase d)

Defined in Futhark.Optimise.Simplify.Engine

Methods

simplify :: SimplifiableLore lore => ShapeBase d -> SimpleM lore (ShapeBase d)

(Simplifiable a, Simplifiable b) => Simplifiable (a, b)

Defined in Futhark.Optimise.Simplify.Engine

Methods

simplify :: SimplifiableLore lore => (a, b) -> SimpleM lore (a, b)

Simplifiable shape => Simplifiable (TypeBase shape u)

Defined in Futhark.Optimise.Simplify.Engine

Methods

simplify :: SimplifiableLore lore => TypeBase shape u -> SimpleM lore (TypeBase shape u)

(Simplifiable a, Simplifiable b, Simplifiable c) => Simplifiable (a, b, c)

Defined in Futhark.Optimise.Simplify.Engine

Methods

simplify :: SimplifiableLore lore => (a, b, c) -> SimpleM lore (a, b, c)

(Simplifiable d, Simplifiable ret) => Simplifiable (MemInfo d u ret)

Defined in Futhark.Representation.ExplicitMemory

Methods

simplify :: SimplifiableLore lore => MemInfo d u ret -> SimpleM lore (MemInfo d u ret)

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 -> [Maybe VName] -> SimpleM lore (Lambda (Wise lore), Stms (Wise lore))

simplifyLambdaSeq :: SimplifiableLore lore => Lambda lore -> [Maybe VName] -> SimpleM lore (Lambda (Wise lore), Stms (Wise lore))

simplifyLambdaNoHoisting :: SimplifiableLore lore => Lambda lore -> [Maybe VName] -> SimpleM lore (Lambda (Wise lore))

simplifyParam :: (attr -> SimpleM lore attr) -> ParamT attr -> SimpleM lore (ParamT attr)

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

bindChunkLParams :: SimplifiableLore lore => VName -> [(LParam (Wise lore), VName)] -> SimpleM lore a -> SimpleM lore a

bindLoopVar :: SimplifiableLore lore => VName -> IntType -> SubExp -> SimpleM lore a -> SimpleM lore a

enterLoop :: SimpleM lore a -> SimpleM lore a

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

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

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

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

constructBody :: SimplifiableLore lore => Stms (Wise lore) -> Result -> SimpleM lore (Body (Wise lore))

protectIf :: MonadBinder m => (Exp (Lore m) -> Bool) -> SubExp -> Stm (Lore m) -> m ()

module Futhark.Optimise.Simplify.Lore