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

Safe Haskell | Safe-Inferred
Language | GHC2021

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 rep a
- runSimpleM :: SimpleM rep a -> SimpleOps rep -> Env rep -> VNameSource -> ((a, Bool), VNameSource)
- data SimpleOps rep = SimpleOps {
  - 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))
  - opUsageS :: Op (Wise rep) -> UsageTable
  - simplifyOpS :: SimplifyOp rep (Op (Wise rep))
  }
- 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
- emptyEnv :: RuleBook (Wise rep) -> HoistBlockers rep -> Env rep
- data HoistBlockers rep = HoistBlockers {
  - blockHoistPar :: BlockPred (Wise rep)
  - blockHoistSeq :: BlockPred (Wise rep)
  - blockHoistBranch :: BlockPred (Wise rep)
  - 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)
- 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
- type SimplifiableRep rep = (ASTRep rep, Simplifiable (LetDec rep), Simplifiable (FParamInfo rep), Simplifiable (LParamInfo rep), Simplifiable (RetType rep), Simplifiable (BranchType rep), TraverseOpStms (Wise rep), CanBeWise (OpC rep), IndexOp (Op (Wise rep)), IsOp (OpC rep), ASTConstraints (OpC rep (Wise rep)), AliasedOp (OpC (Wise rep)), RephraseOp (OpC rep), BuilderOps (Wise rep), IsOp (OpC rep))
- class Simplifiable e where
  - simplify :: SimplifiableRep rep => e -> SimpleM rep e
- 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 => Names -> 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))
- data 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))
- enterLoop :: SimpleM rep a -> SimpleM rep a
- constructBody :: SimplifiableRep rep => Stms (Wise rep) -> Result -> SimpleM rep (Body (Wise rep))
- module Futhark.Optimise.Simplify.Rep

# Monadic interface

data SimpleM rep a Source #

#### Instances

Instances details

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

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

data SimpleOps rep Source #

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
- simplifyOpS :: SimplifyOp rep (Op (Wise rep))

#### Instances

Instances details

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

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

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

data Env rep Source #

#### Instances

Instances details

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

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

data HoistBlockers rep Source #

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 Source #

noExtraHoistBlockers :: HoistBlockers rep Source #

neverHoist :: HoistBlockers rep Source #

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

orIf :: BlockPred rep -> BlockPred rep -> BlockPred rep Source #

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

isConsumed :: BlockPred rep Source #

isConsuming :: Aliased rep => BlockPred rep Source #

isFalse :: Bool -> BlockPred rep Source #

isOp :: BlockPred rep Source #

isNotSafe :: ASTRep rep => BlockPred rep Source #

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

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

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

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

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

# 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 (OpC rep), IndexOp (Op (Wise rep)), IsOp (OpC rep), ASTConstraints (OpC rep (Wise rep)), AliasedOp (OpC (Wise rep)), RephraseOp (OpC rep), BuilderOps (Wise rep), IsOp (OpC rep)) Source #

class Simplifiable e where Source #

Methods

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

#### Instances

Instances details

Simplifiable KernelGrid Source # |
Instance details Defined in Futhark.IR.GPU.Op Methods simplify :: SimplifiableRep rep => KernelGrid -> SimpleM rep KernelGrid Source #
Simplifiable SegLevel Source # |
Instance details Defined in Futhark.IR.GPU.Op Methods simplify :: SimplifiableRep rep => SegLevel -> SimpleM rep SegLevel Source #
Simplifiable MemBind Source # |
Instance details Defined in Futhark.IR.Mem Methods simplify :: SimplifiableRep rep => MemBind -> SimpleM rep MemBind Source #
Simplifiable MemReturn Source # |
Instance details Defined in Futhark.IR.Mem Methods simplify :: SimplifiableRep rep => MemReturn -> SimpleM rep MemReturn Source #
Simplifiable KernelResult Source # |
Instance details Defined in Futhark.IR.SegOp Methods simplify :: SimplifiableRep rep => KernelResult -> SimpleM rep KernelResult Source #
Simplifiable SegSpace Source # |
Instance details Defined in Futhark.IR.SegOp Methods simplify :: SimplifiableRep rep => SegSpace -> SimpleM rep SegSpace Source #
Simplifiable SubExpRes Source # |
Instance details Defined in Futhark.Optimise.Simplify.Engine Methods simplify :: SimplifiableRep rep => SubExpRes -> SimpleM rep SubExpRes Source #
Simplifiable Certs Source # |
Instance details Defined in Futhark.Optimise.Simplify.Engine Methods simplify :: SimplifiableRep rep => Certs -> SimpleM rep Certs Source #
Simplifiable ExtSize Source # |
Instance details Defined in Futhark.Optimise.Simplify.Engine Methods simplify :: SimplifiableRep rep => ExtSize -> SimpleM rep ExtSize Source #
Simplifiable Space Source # |
Instance details Defined in Futhark.Optimise.Simplify.Engine Methods simplify :: SimplifiableRep rep => Space -> SimpleM rep Space Source #
Simplifiable SubExp Source # |
Instance details Defined in Futhark.Optimise.Simplify.Engine Methods simplify :: SimplifiableRep rep => SubExp -> SimpleM rep SubExp Source #
Simplifiable VName Source # |
Instance details Defined in Futhark.Optimise.Simplify.Engine Methods simplify :: SimplifiableRep rep => VName -> SimpleM rep VName Source #
Simplifiable PrimType Source # |
Instance details Defined in Futhark.Optimise.Simplify.Engine Methods simplify :: SimplifiableRep rep => PrimType -> SimpleM rep PrimType Source #
Simplifiable () Source # |
Instance details Defined in Futhark.Optimise.Simplify.Engine Methods simplify :: SimplifiableRep rep => () -> SimpleM rep () Source #
Simplifiable Int Source # |
Instance details Defined in Futhark.Optimise.Simplify.Engine Methods simplify :: SimplifiableRep rep => Int -> SimpleM rep Int Source #
Simplifiable d => Simplifiable (DimIndex d) Source # |
Instance details Defined in Futhark.Optimise.Simplify.Engine Methods simplify :: SimplifiableRep rep => DimIndex d -> SimpleM rep (DimIndex d) Source #
Simplifiable d => Simplifiable (ShapeBase d) Source # |
Instance details Defined in Futhark.Optimise.Simplify.Engine Methods simplify :: SimplifiableRep rep => ShapeBase d -> SimpleM rep (ShapeBase d) Source #
Simplifiable d => Simplifiable (Slice d) Source # |
Instance details Defined in Futhark.Optimise.Simplify.Engine Methods simplify :: SimplifiableRep rep => Slice d -> SimpleM rep (Slice d) Source #
Simplifiable a => Simplifiable (Maybe a) Source # |
Instance details Defined in Futhark.Optimise.Simplify.Engine Methods simplify :: SimplifiableRep rep => Maybe a -> SimpleM rep (Maybe a) Source #
Simplifiable [FunReturns] Source # |
Instance details Defined in Futhark.IR.Mem Methods simplify :: SimplifiableRep rep => [FunReturns] -> SimpleM rep [FunReturns] Source #
Simplifiable a => Simplifiable [a] Source # |
Instance details Defined in Futhark.Optimise.Simplify.Engine Methods simplify :: SimplifiableRep rep => [a] -> SimpleM rep [a] Source #
Simplifiable shape => Simplifiable (TypeBase shape u) Source # |
Instance details Defined in Futhark.Optimise.Simplify.Engine Methods simplify :: SimplifiableRep rep => TypeBase shape u -> SimpleM rep (TypeBase shape u) Source #
(Simplifiable a, Simplifiable b) => Simplifiable (a, b) Source # |
Instance details Defined in Futhark.Optimise.Simplify.Engine Methods simplify :: SimplifiableRep rep => (a, b) -> SimpleM rep (a, b) Source #
(Simplifiable d, Simplifiable ret) => Simplifiable (MemInfo d u ret) Source # |
Instance details Defined in Futhark.IR.Mem Methods simplify :: SimplifiableRep rep => MemInfo d u ret -> SimpleM rep (MemInfo d u ret) Source #
(Simplifiable a, Simplifiable b, Simplifiable c) => Simplifiable (a, b, c) Source # |
Instance details Defined in Futhark.Optimise.Simplify.Engine Methods simplify :: SimplifiableRep rep => (a, b, c) -> SimpleM rep (a, b, c) Source #

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

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

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

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

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

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

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

Simplify a single body.

data SymbolTable rep Source #

#### Instances

Instances details

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

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

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

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

Block hoisting of `Index` statements introduced by migration.

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

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

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

module Futhark.Optimise.Simplify.Rep