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

Safe Haskell | Safe-Inferred
Language | GHC2021

Futhark.Analysis.SymbolTable

Contents

- Entries
- Lookup
- Insertion
- Misc

Synopsis

- data SymbolTable rep
- empty :: SymbolTable rep
- fromScope :: ASTRep rep => Scope rep -> SymbolTable rep
- toScope :: SymbolTable rep -> Scope rep
- data Entry rep
- deepen :: SymbolTable rep -> SymbolTable rep
- entryAccInput :: Entry rep -> Maybe (WithAccInput rep)
- entryDepth :: Entry rep -> Int
- entryLetBoundDec :: Entry rep -> Maybe (LetDec rep)
- entryIsSize :: Entry rep -> Bool
- entryStm :: Entry rep -> Maybe (Stm rep)
- entryFParam :: Entry rep -> Maybe (FParamInfo rep)
- entryLParam :: Entry rep -> Maybe (LParamInfo rep)
- elem :: VName -> SymbolTable rep -> Bool
- lookup :: VName -> SymbolTable rep -> Maybe (Entry rep)
- lookupStm :: VName -> SymbolTable rep -> Maybe (Stm rep)
- lookupExp :: VName -> SymbolTable rep -> Maybe (Exp rep, Certs)
- lookupBasicOp :: VName -> SymbolTable rep -> Maybe (BasicOp, Certs)
- lookupType :: ASTRep rep => VName -> SymbolTable rep -> Maybe Type
- lookupSubExp :: VName -> SymbolTable rep -> Maybe (SubExp, Certs)
- lookupAliases :: VName -> SymbolTable rep -> Names
- lookupLoopVar :: VName -> SymbolTable rep -> Maybe SubExp
- lookupLoopParam :: VName -> SymbolTable rep -> Maybe (SubExp, SubExp)
- aliases :: VName -> VName -> SymbolTable rep -> Bool
- available :: VName -> SymbolTable rep -> Bool
- subExpAvailable :: SubExp -> SymbolTable rep -> Bool
- consume :: VName -> SymbolTable rep -> SymbolTable rep
- index :: VName -> [SubExp] -> SymbolTable rep -> Maybe Indexed
- index' :: VName -> [TPrimExp Int64 VName] -> SymbolTable rep -> Maybe Indexed
- data Indexed
  - = Indexed Certs (PrimExp VName)
  - | IndexedArray Certs VName [TPrimExp Int64 VName]
- indexedAddCerts :: Certs -> Indexed -> Indexed
- class IndexOp op where
  - indexOp :: (ASTRep rep, IndexOp (Op rep)) => SymbolTable rep -> Int -> op -> [TPrimExp Int64 VName] -> Maybe Indexed
- insertStm :: (IndexOp (Op rep), Aliased rep) => Stm rep -> SymbolTable rep -> SymbolTable rep
- insertStms :: (IndexOp (Op rep), Aliased rep) => Stms rep -> SymbolTable rep -> SymbolTable rep
- insertFParams :: ASTRep rep => [FParam rep] -> SymbolTable rep -> SymbolTable rep
- insertLParam :: ASTRep rep => LParam rep -> SymbolTable rep -> SymbolTable rep
- insertLoopVar :: ASTRep rep => VName -> IntType -> SubExp -> SymbolTable rep -> SymbolTable rep
- insertLoopMerge :: ASTRep rep => [(FParam rep, SubExp, SubExpRes)] -> SymbolTable rep -> SymbolTable rep
- hideCertified :: Names -> SymbolTable rep -> SymbolTable rep
- noteAccTokens :: [(VName, WithAccInput rep)] -> SymbolTable rep -> SymbolTable rep

# Documentation

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 #

empty :: SymbolTable rep Source #

fromScope :: ASTRep rep => Scope rep -> SymbolTable rep Source #

toScope :: SymbolTable rep -> Scope rep Source #

# Entries

data Entry rep Source #

#### Instances

Instances details

ASTRep rep => Typed (Entry rep) Source # |
Instance details Defined in Futhark.Analysis.SymbolTable Methods typeOf :: Entry rep -> Type Source #

deepen :: SymbolTable rep -> SymbolTable rep Source #

entryAccInput :: Entry rep -> Maybe (WithAccInput rep) Source #

For names that are tokens of an accumulator, this is the corresponding combining function and neutral element.

entryDepth :: Entry rep -> Int Source #

entryLetBoundDec :: Entry rep -> Maybe (LetDec rep) Source #

entryIsSize :: Entry rep -> Bool Source #

True if this name has been used as an array size, implying that it is non-negative.

entryStm :: Entry rep -> Maybe (Stm rep) Source #

entryFParam :: Entry rep -> Maybe (FParamInfo rep) Source #

entryLParam :: Entry rep -> Maybe (LParamInfo rep) Source #

# Lookup

elem :: VName -> SymbolTable rep -> Bool Source #

You almost always want `available` instead of this one.

lookup :: VName -> SymbolTable rep -> Maybe (Entry rep) Source #

lookupStm :: VName -> SymbolTable rep -> Maybe (Stm rep) Source #

lookupExp :: VName -> SymbolTable rep -> Maybe (Exp rep, Certs) Source #

lookupBasicOp :: VName -> SymbolTable rep -> Maybe (BasicOp, Certs) Source #

lookupType :: ASTRep rep => VName -> SymbolTable rep -> Maybe Type Source #

lookupSubExp :: VName -> SymbolTable rep -> Maybe (SubExp, Certs) Source #

lookupAliases :: VName -> SymbolTable rep -> Names Source #

lookupLoopVar :: VName -> SymbolTable rep -> Maybe SubExp Source #

If the given variable name is the name of a `ForLoop` parameter, then return the bound of that loop.

lookupLoopParam :: VName -> SymbolTable rep -> Maybe (SubExp, SubExp) Source #

Look up the initial value and eventual result of a loop parameter. Note that the result almost certainly refers to something that is not part of the symbol table.

aliases :: VName -> VName -> SymbolTable rep -> Bool Source #

Do these two names alias each other? This is expected to be a commutative relationship, so the order of arguments does not matter.

available :: VName -> SymbolTable rep -> Bool Source #

In symbol table and not consumed.

subExpAvailable :: SubExp -> SymbolTable rep -> Bool Source #

Constant or `available`

consume :: VName -> SymbolTable rep -> SymbolTable rep Source #

index :: VName -> [SubExp] -> SymbolTable rep -> Maybe Indexed Source #

`index arr is vtable` fully indexes the array `arr` at position `is` using information in `vtable`, and produces the symbolic result of the indexing if it can be expressed. This is essentially a form of pull-array indexing.

index' :: VName -> [TPrimExp Int64 VName] -> SymbolTable rep -> Maybe Indexed Source #

data Indexed Source #

The result of indexing a delayed array.

Constructors

Indexed Certs (PrimExp VName) | A PrimExp based on the indexes (that is, without accessing any actual array).
IndexedArray Certs VName [TPrimExp Int64 VName] | The indexing corresponds to another (perhaps more advantageous) array.

#### Instances

Instances details

FreeIn Indexed Source # |
Instance details Defined in Futhark.Analysis.SymbolTable Methods freeIn' :: Indexed -> FV Source #

indexedAddCerts :: Certs -> Indexed -> Indexed Source #

class IndexOp op where Source #

Minimal complete definition

Nothing

Methods

indexOp :: (ASTRep rep, IndexOp (Op rep)) => SymbolTable rep -> Int -> op -> [TPrimExp Int64 VName] -> Maybe Indexed Source #

#### Instances

Instances details

RepTypes rep => IndexOp (SOAC rep) Source # |
Instance details Defined in Futhark.IR.SOACS.SOAC Methods indexOp :: (ASTRep rep0, IndexOp (Op rep0)) => SymbolTable rep0 -> Int -> SOAC rep -> [TPrimExp Int64 VName] -> Maybe Indexed Source #
(ASTRep rep, IndexOp (op rep)) => IndexOp (HostOp op rep) Source # |
Instance details Defined in Futhark.IR.GPU.Op Methods indexOp :: (ASTRep rep0, IndexOp (Op rep0)) => SymbolTable rep0 -> Int -> HostOp op rep -> [TPrimExp Int64 VName] -> Maybe Indexed Source #
(ASTRep rep, IndexOp (op rep)) => IndexOp (MCOp op rep) Source # |
Instance details Defined in Futhark.IR.MC.Op Methods indexOp :: (ASTRep rep0, IndexOp (Op rep0)) => SymbolTable rep0 -> Int -> MCOp op rep -> [TPrimExp Int64 VName] -> Maybe Indexed Source #
IndexOp (inner rep) => IndexOp (MemOp inner rep) Source # |
Instance details Defined in Futhark.IR.Mem Methods indexOp :: (ASTRep rep0, IndexOp (Op rep0)) => SymbolTable rep0 -> Int -> MemOp inner rep -> [TPrimExp Int64 VName] -> Maybe Indexed Source #
IndexOp (NoOp rep) Source # |
Instance details Defined in Futhark.Analysis.SymbolTable Methods indexOp :: (ASTRep rep0, IndexOp (Op rep0)) => SymbolTable rep0 -> Int -> NoOp rep -> [TPrimExp Int64 VName] -> Maybe Indexed Source #
ASTRep rep => IndexOp (SegOp lvl rep) Source # |
Instance details Defined in Futhark.IR.SegOp Methods indexOp :: (ASTRep rep0, IndexOp (Op rep0)) => SymbolTable rep0 -> Int -> SegOp lvl rep -> [TPrimExp Int64 VName] -> Maybe Indexed Source #

# Insertion

insertStm :: (IndexOp (Op rep), Aliased rep) => Stm rep -> SymbolTable rep -> SymbolTable rep Source #

insertStms :: (IndexOp (Op rep), Aliased rep) => Stms rep -> SymbolTable rep -> SymbolTable rep Source #

insertFParams :: ASTRep rep => [FParam rep] -> SymbolTable rep -> SymbolTable rep Source #

insertLParam :: ASTRep rep => LParam rep -> SymbolTable rep -> SymbolTable rep Source #

insertLoopVar :: ASTRep rep => VName -> IntType -> SubExp -> SymbolTable rep -> SymbolTable rep Source #

insertLoopMerge :: ASTRep rep => [(FParam rep, SubExp, SubExpRes)] -> SymbolTable rep -> SymbolTable rep Source #

Insert entries corresponding to the parameters of a loop (not distinguishing contect and value part). Apart from the parameter itself, we also insert the initial value and the subexpression providing the final value. Note that the latter is likely not in scope in the symbol at this point. This is OK, and can still be used to help some loop optimisations detect invariant loop parameters.

# Misc

hideCertified :: Names -> SymbolTable rep -> SymbolTable rep Source #

Hide these definitions, if they are protected by certificates in the set of names.

noteAccTokens :: [(VName, WithAccInput rep)] -> SymbolTable rep -> SymbolTable rep Source #

Note that these names are tokens for the corresponding accumulators. The names must already be present in the symbol table.