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 rep a

Instances

SimplifiableRep rep => HasScope (Wise rep :: Type) (SimpleM rep)

Defined in Futhark.Optimise.Simplify.Engine

Methods

lookupType :: VName -> SimpleM rep Type0

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

askScope :: SimpleM rep (Scope (Wise rep))

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

SimplifiableRep rep => LocalScope (Wise rep :: Type) (SimpleM rep)

Defined in Futhark.Optimise.Simplify.Engine

Methods

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

Applicative (SimpleM rep)

Defined in Futhark.Optimise.Simplify.Engine

Methods

pure :: a -> SimpleM rep a

(<*>) :: SimpleM rep (a -> b) -> SimpleM rep a -> SimpleM rep b

liftA2 :: (a -> b -> c) -> SimpleM rep a -> SimpleM rep b -> SimpleM rep c

(*>) :: SimpleM rep a -> SimpleM rep b -> SimpleM rep b

(<*) :: SimpleM rep a -> SimpleM rep b -> SimpleM rep a

Functor (SimpleM rep)

Defined in Futhark.Optimise.Simplify.Engine

Methods

fmap :: (a -> b) -> SimpleM rep a -> SimpleM rep b

(<$) :: a -> SimpleM rep b -> SimpleM rep a

Monad (SimpleM rep)

Defined in Futhark.Optimise.Simplify.Engine

Methods

(>>=) :: SimpleM rep a -> (a -> SimpleM rep b) -> SimpleM rep b

(>>) :: SimpleM rep a -> SimpleM rep b -> SimpleM rep b

return :: a -> SimpleM rep a

MonadFreshNames (SimpleM rep)

Defined in Futhark.Optimise.Simplify.Engine

Methods

getNameSource :: SimpleM rep VNameSource

putNameSource :: VNameSource -> SimpleM rep ()

MonadReader (SimpleOps rep, Env rep) (SimpleM rep)

Defined in Futhark.Optimise.Simplify.Engine

Methods

ask :: SimpleM rep (SimpleOps rep, Env rep)

local :: ((SimpleOps rep, Env rep) -> (SimpleOps rep, Env rep)) -> SimpleM rep a -> SimpleM rep a

reader :: ((SimpleOps rep, Env rep) -> a) -> SimpleM rep a

MonadState (VNameSource, Bool, Certs) (SimpleM rep)

Defined in Futhark.Optimise.Simplify.Engine

Methods

get :: SimpleM rep (VNameSource, Bool, Certs)

put :: (VNameSource, Bool, Certs) -> SimpleM rep ()

state :: ((VNameSource, Bool, Certs) -> (a, (VNameSource, Bool, Certs))) -> SimpleM rep a

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

data SimpleOps rep

Constructors

SimpleOps

Fields

• mkExpDecS :: SymbolTable (Wise rep) -> Pat (LetDec (Wise rep)) -> Exp (Wise rep) -> SimpleM rep (ExpDec (Wise rep))
• mkBodyS :: SymbolTable (Wise rep) -> Stms (Wise rep) -> Result -> SimpleM rep (Body (Wise rep))
• protectHoistedOpS :: Protect (Builder (Wise rep))

  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 rep) -> UsageTable
• simplifyPatFromExpS :: Pat (LetDec rep) -> Exp (Wise rep) -> SimpleM rep (Pat (LetDec rep))
• simplifyOpS :: SimplifyOp rep (Op (Wise rep))

Instances

MonadReader (SimpleOps rep, Env rep) (SimpleM rep)

Defined in Futhark.Optimise.Simplify.Engine

Methods

ask :: SimpleM rep (SimpleOps rep, Env rep)

local :: ((SimpleOps rep, Env rep) -> (SimpleOps rep, Env rep)) -> SimpleM rep a -> SimpleM rep a

reader :: ((SimpleOps rep, Env rep) -> a) -> SimpleM rep a

type SimplifyOp rep op = op -> SimpleM rep (op, Stms (Wise rep))

bindableSimpleOps :: (SimplifiableRep rep, Buildable rep) => SimplifyOp rep (Op (Wise rep)) -> SimpleOps rep

data Env rep

Instances

MonadReader (SimpleOps rep, Env rep) (SimpleM rep)

Defined in Futhark.Optimise.Simplify.Engine

Methods

ask :: SimpleM rep (SimpleOps rep, Env rep)

local :: ((SimpleOps rep, Env rep) -> (SimpleOps rep, Env rep)) -> SimpleM rep a -> SimpleM rep a

reader :: ((SimpleOps rep, Env rep) -> a) -> SimpleM rep a

emptyEnv :: RuleBook (Wise rep) -> HoistBlockers rep -> Env rep

data HoistBlockers rep

Constructors

HoistBlockers

Fields

• blockHoistPar :: BlockPred (Wise rep)

  Blocker for hoisting out of parallel loops.

• blockHoistSeq :: BlockPred (Wise rep)

  Blocker for hoisting out of sequential loops.

• blockHoistBranch :: BlockPred (Wise rep)

  Blocker for hoisting out of branches.

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

neverBlocks :: BlockPred rep

noExtraHoistBlockers :: HoistBlockers rep

neverHoist :: HoistBlockers rep

type BlockPred rep = SymbolTable rep -> UsageTable -> Stm rep -> Bool

orIf :: BlockPred rep -> BlockPred rep -> BlockPred rep

hasFree :: ASTRep rep => Names -> BlockPred rep

isConsumed :: BlockPred rep

isConsuming :: Aliased rep => BlockPred rep

isFalse :: Bool -> BlockPred rep

isOp :: BlockPred rep

isNotSafe :: ASTRep rep => BlockPred rep

isDeviceMigrated :: SimplifiableRep rep => BlockPred (Wise rep)

Statement is a scalar read from a single element array of rank one.

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

askVtable :: SimpleM rep (SymbolTable (Wise rep))

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

Building blocks

type SimplifiableRep rep = (ASTRep rep, Simplifiable (LetDec rep), Simplifiable (FParamInfo rep), Simplifiable (LParamInfo rep), Simplifiable (RetType rep), Simplifiable (BranchType rep), TraverseOpStms (Wise rep), CanBeWise (Op rep), IndexOp (OpWithWisdom (Op rep)), BuilderOps (Wise rep), IsOp (Op rep))

class Simplifiable e where

Methods

simplify :: SimplifiableRep rep => e -> SimpleM rep e

Instances

Simplifiable SegLevel

Defined in Futhark.IR.GPU.Op

Methods

simplify :: forall {k} (rep :: k). SimplifiableRep rep => SegLevel -> SimpleM rep SegLevel

Simplifiable MemBind

Defined in Futhark.IR.Mem

Methods

simplify :: forall {k} (rep :: k). SimplifiableRep rep => MemBind -> SimpleM rep MemBind

Simplifiable MemReturn

Defined in Futhark.IR.Mem

Methods

simplify :: forall {k} (rep :: k). SimplifiableRep rep => MemReturn -> SimpleM rep MemReturn

Simplifiable KernelResult

Defined in Futhark.IR.SegOp

Methods

simplify :: forall {k} (rep :: k). SimplifiableRep rep => KernelResult -> SimpleM rep KernelResult

Simplifiable SegSpace

Defined in Futhark.IR.SegOp

Methods

simplify :: forall {k} (rep :: k). SimplifiableRep rep => SegSpace -> SimpleM rep SegSpace

Simplifiable SubExpRes

Defined in Futhark.Optimise.Simplify.Engine

Methods

simplify :: forall {k} (rep :: k). SimplifiableRep rep => SubExpRes -> SimpleM rep SubExpRes

Simplifiable Certs

Defined in Futhark.Optimise.Simplify.Engine

Methods

simplify :: forall {k} (rep :: k). SimplifiableRep rep => Certs -> SimpleM rep Certs

Simplifiable ExtSize

Defined in Futhark.Optimise.Simplify.Engine

Methods

simplify :: forall {k} (rep :: k). SimplifiableRep rep => ExtSize -> SimpleM rep ExtSize

Simplifiable Space

Defined in Futhark.Optimise.Simplify.Engine

Methods

simplify :: forall {k} (rep :: k). SimplifiableRep rep => Space -> SimpleM rep Space

Simplifiable SubExp

Defined in Futhark.Optimise.Simplify.Engine

Methods

simplify :: forall {k} (rep :: k). SimplifiableRep rep => SubExp -> SimpleM rep SubExp

Simplifiable VName

Defined in Futhark.Optimise.Simplify.Engine

Methods

simplify :: forall {k} (rep :: k). SimplifiableRep rep => VName -> SimpleM rep VName

Simplifiable PrimType

Defined in Futhark.Optimise.Simplify.Engine

Methods

simplify :: forall {k} (rep :: k). SimplifiableRep rep => PrimType -> SimpleM rep PrimType

Simplifiable ()

Defined in Futhark.Optimise.Simplify.Engine

Methods

simplify :: forall {k} (rep :: k). SimplifiableRep rep => () -> SimpleM rep ()

Simplifiable Int

Defined in Futhark.Optimise.Simplify.Engine

Methods

simplify :: forall {k} (rep :: k). SimplifiableRep rep => Int -> SimpleM rep Int

Simplifiable d => Simplifiable (DimIndex d)

Defined in Futhark.Optimise.Simplify.Engine

Methods

simplify :: forall {k} (rep :: k). SimplifiableRep rep => DimIndex d -> SimpleM rep (DimIndex d)

Simplifiable d => Simplifiable (ShapeBase d)

Defined in Futhark.Optimise.Simplify.Engine

Methods

simplify :: forall {k} (rep :: k). SimplifiableRep rep => ShapeBase d -> SimpleM rep (ShapeBase d)

Simplifiable d => Simplifiable (Slice d)

Defined in Futhark.Optimise.Simplify.Engine

Methods

simplify :: forall {k} (rep :: k). SimplifiableRep rep => Slice d -> SimpleM rep (Slice d)

Simplifiable a => Simplifiable (Maybe a)

Defined in Futhark.Optimise.Simplify.Engine

Methods

simplify :: forall {k} (rep :: k). SimplifiableRep rep => Maybe a -> SimpleM rep (Maybe a)

Simplifiable [FunReturns]

Defined in Futhark.IR.Mem

Methods

simplify :: forall {k} (rep :: k). SimplifiableRep rep => [FunReturns] -> SimpleM rep [FunReturns]

Simplifiable a => Simplifiable [a]

Defined in Futhark.Optimise.Simplify.Engine

Methods

simplify :: forall {k} (rep :: k). SimplifiableRep rep => [a] -> SimpleM rep [a]

Simplifiable shape => Simplifiable (TypeBase shape u)

Defined in Futhark.Optimise.Simplify.Engine

Methods

simplify :: forall {k} (rep :: k). SimplifiableRep rep => TypeBase shape u -> SimpleM rep (TypeBase shape u)

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

Defined in Futhark.Optimise.Simplify.Engine

Methods

simplify :: forall {k} (rep :: k). SimplifiableRep rep => (a, b) -> SimpleM rep (a, b)

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

Defined in Futhark.IR.Mem

Methods

simplify :: forall {k} (rep :: k). SimplifiableRep rep => MemInfo d u ret -> SimpleM rep (MemInfo d u ret)

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

Defined in Futhark.Optimise.Simplify.Engine

Methods

simplify :: forall {k} (rep :: k). SimplifiableRep rep => (a, b, c) -> SimpleM rep (a, b, c)

simplifyFun :: SimplifiableRep rep => FunDef (Wise rep) -> SimpleM rep (FunDef (Wise rep))

simplifyStms :: SimplifiableRep rep => Stms (Wise rep) -> SimpleM rep (Stms (Wise rep))

simplifyStmsWithUsage :: SimplifiableRep rep => UsageTable -> Stms (Wise rep) -> SimpleM rep (Stms (Wise rep))

simplifyLambda :: SimplifiableRep rep => Lambda (Wise rep) -> SimpleM rep (Lambda (Wise rep), Stms (Wise rep))

simplifyLambdaNoHoisting :: SimplifiableRep rep => Lambda (Wise rep) -> SimpleM rep (Lambda (Wise rep))

bindLParams :: SimplifiableRep rep => [LParam (Wise rep)] -> SimpleM rep a -> SimpleM rep a

simplifyBody :: SimplifiableRep rep => BlockPred (Wise rep) -> UsageTable -> [Usages] -> Body (Wise rep) -> SimpleM rep (Stms (Wise rep), Body (Wise rep))

Simplify a single body.

data SymbolTable rep

Instances

Monoid (SymbolTable rep)

Defined in Futhark.Analysis.SymbolTable

Methods

mempty :: SymbolTable rep

mappend :: SymbolTable rep -> SymbolTable rep -> SymbolTable rep

mconcat :: [SymbolTable rep] -> SymbolTable rep

Semigroup (SymbolTable rep)

Defined in Futhark.Analysis.SymbolTable

Methods

(<>) :: SymbolTable rep -> SymbolTable rep -> SymbolTable rep

sconcat :: NonEmpty (SymbolTable rep) -> SymbolTable rep

stimes :: Integral b => b -> SymbolTable rep -> SymbolTable rep

hoistStms :: SimplifiableRep rep => RuleBook (Wise rep) -> BlockPred (Wise rep) -> Stms (Wise rep) -> SimpleM rep (a, UsageTable) -> SimpleM rep (a, Stms (Wise rep), Stms (Wise rep))

blockIf :: SimplifiableRep rep => BlockPred (Wise rep) -> Stms (Wise rep) -> SimpleM rep (a, UsageTable) -> SimpleM rep (a, Stms (Wise rep), Stms (Wise rep))

blockMigrated :: SimplifiableRep rep => SimpleM rep (Lambda (Wise rep), Stms (Wise rep)) -> SimpleM rep (Lambda (Wise rep), Stms (Wise rep))

Block hoisting of Index statements introduced by migration.

enterLoop :: SimpleM rep a -> SimpleM rep a

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

constructBody :: SimplifiableRep rep => Stms (Wise rep) -> Result -> SimpleM rep (Body (Wise rep))

module Futhark.Optimise.Simplify.Rep