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

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

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

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

MonadState (VNameSource, Bool, Certificates) (SimpleM lore)

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)

data SimpleOps lore

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

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

bindableSimpleOps :: (SimplifiableLore lore, Bindable lore) => SimplifyOp lore (Op 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.

• 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

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))

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 ()

Defined in Futhark.Optimise.Simplify.Engine

Methods

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

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 Space

Defined in Futhark.Optimise.Simplify.Engine

Methods

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

Simplifiable ExtSize

Defined in Futhark.Optimise.Simplify.Engine

Methods

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

Simplifiable MemReturn

Defined in Futhark.IR.Mem

Methods

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

Simplifiable MemBind

Defined in Futhark.IR.Mem

Methods

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

Simplifiable SegSpace

Defined in Futhark.IR.SegOp

Methods

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

Simplifiable KernelResult

Defined in Futhark.IR.SegOp

Methods

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

Simplifiable SplitOrdering

Defined in Futhark.IR.SegOp

Methods

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

Simplifiable SegLevel

Defined in Futhark.IR.Kernels.Kernel

Methods

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

Simplifiable a => Simplifiable [a]

Defined in Futhark.Optimise.Simplify.Engine

Methods

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

Simplifiable [FunReturns]

Defined in Futhark.IR.Mem

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.IR.Mem

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 -> 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)

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))

data SymbolTable lore

Instances

Semigroup (SymbolTable lore)

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)

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))

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

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

module Futhark.Optimise.Simplify.Lore