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

Safe Haskell | Safe-Inferred
Language | GHC2021

Futhark.IR.Prop.Names

Contents

- Free names
- Class
- Specialised Functions
- Bound Names
- Efficient computation

Description

Facilities for determining which names are used in some syntactic construct. The most important interface is the `FreeIn` class and its instances, but for reasons related to the Haskell type system, some constructs have specialised functions.

Synopsis

- data Names
- namesIntMap :: Names -> IntMap VName
- namesIntSet :: Names -> IntSet
- nameIn :: VName -> Names -> Bool
- notNameIn :: VName -> Names -> Bool
- oneName :: VName -> Names
- namesFromList :: [VName] -> Names
- namesToList :: Names -> [VName]
- namesIntersection :: Names -> Names -> Names
- namesIntersect :: Names -> Names -> Bool
- namesSubtract :: Names -> Names -> Names
- mapNames :: (VName -> VName) -> Names -> Names
- class FreeIn a where
  - freeIn' :: a -> FV
- freeIn :: FreeIn a => a -> Names
- freeInStmsAndRes :: (FreeIn (Op rep), FreeIn (LetDec rep), FreeIn (LParamInfo rep), FreeIn (FParamInfo rep), FreeDec (BodyDec rep), FreeIn (RetType rep), FreeIn (BranchType rep), FreeDec (ExpDec rep)) => Stms rep -> Result -> FV
- boundInBody :: Body rep -> Names
- boundByStm :: Stm rep -> Names
- boundByStms :: Stms rep -> Names
- boundByLambda :: Lambda rep -> [VName]
- class FreeIn dec => FreeDec dec where
  - precomputed :: dec -> FV -> FV
- data FV
- fvBind :: Names -> FV -> FV
- fvName :: VName -> FV
- fvNames :: Names -> FV

# Free names

data Names Source #

A set of names. Note that the `Ord` instance is a dummy that treats everything as `EQ` if `==`, and otherwise `LT`.

#### Instances

Instances details

Monoid Names Source # |
Instance details Defined in Futhark.IR.Prop.Names Methods mempty :: Names Source # mappend :: Names -> Names -> Names Source # mconcat :: [Names] -> Names Source #
Semigroup Names Source # |
Instance details Defined in Futhark.IR.Prop.Names Methods (<>) :: Names -> Names -> Names Source # sconcat :: NonEmpty Names -> Names Source # stimes :: Integral b => b -> Names -> Names Source #
Show Names Source # |
Instance details Defined in Futhark.IR.Prop.Names Methods showsPrec :: Int -> Names -> ShowS Source # show :: Names -> String Source # showList :: [Names] -> ShowS Source #
AliasesOf Names Source # |
Instance details Defined in Futhark.IR.Prop.Aliases Methods aliasesOf :: Names -> Names Source #
FreeDec Names Source # |
Instance details Defined in Futhark.IR.Prop.Names Methods precomputed :: Names -> FV -> FV Source #
FreeIn Names Source # |
Instance details Defined in Futhark.IR.Prop.Names Methods freeIn' :: Names -> FV Source #
Rename Names Source # |
Instance details Defined in Futhark.Transform.Rename Methods rename :: Names -> RenameM Names Source #
Substitute Names Source # |
Instance details Defined in Futhark.Transform.Substitute Methods substituteNames :: Map VName VName -> Names -> Names Source #
Eq Names Source # |
Instance details Defined in Futhark.IR.Prop.Names Methods (==) :: Names -> Names -> Bool Source # (/=) :: Names -> Names -> Bool Source #
Ord Names Source # |
Instance details Defined in Futhark.IR.Prop.Names Methods compare :: Names -> Names -> Ordering Source # (<) :: Names -> Names -> Bool Source # (<=) :: Names -> Names -> Bool Source # (>) :: Names -> Names -> Bool Source # (>=) :: Names -> Names -> Bool Source # max :: Names -> Names -> Names Source # min :: Names -> Names -> Names Source #
Pretty Names Source # |
Instance details Defined in Futhark.IR.Prop.Names Methods pretty :: Names -> Doc ann Source # prettyList :: [Names] -> Doc ann Source #

namesIntMap :: Names -> IntMap VName Source #

Retrieve the data structure underlying the names representation.

namesIntSet :: Names -> IntSet Source #

Retrieve the set of tags in the names set.

nameIn :: VName -> Names -> Bool Source #

Does the set of names contain this name?

notNameIn :: VName -> Names -> Bool Source #

Does the set of names not contain this name?

oneName :: VName -> Names Source #

Construct a name set from a single name.

namesFromList :: [VName] -> Names Source #

Construct a name set from a list. Slow.

namesToList :: Names -> [VName] Source #

Turn a name set into a list of names. Slow.

namesIntersection :: Names -> Names -> Names Source #

The intersection of two name sets.

namesIntersect :: Names -> Names -> Bool Source #

Do the two name sets intersect?

namesSubtract :: Names -> Names -> Names Source #

Subtract the latter name set from the former.

mapNames :: (VName -> VName) -> Names -> Names Source #

Map over the names in a set.

# Class

class FreeIn a where Source #

A class indicating that we can obtain free variable information from values of this type.

Minimal complete definition

Nothing

Methods

freeIn' :: a -> FV Source #

#### Instances

Instances details

FreeIn Indexed Source # |
Instance details Defined in Futhark.Analysis.SymbolTable Methods freeIn' :: Indexed -> FV Source #
FreeIn Arg Source # |
Instance details Defined in Futhark.CodeGen.ImpCode Methods freeIn' :: Arg -> FV Source #
FreeIn EntryPoint Source # |
Instance details Defined in Futhark.CodeGen.ImpCode Methods freeIn' :: EntryPoint -> FV Source #
FreeIn ExternalValue Source # |
Instance details Defined in Futhark.CodeGen.ImpCode Methods freeIn' :: ExternalValue -> FV Source #
FreeIn ValueDesc Source # |
Instance details Defined in Futhark.CodeGen.ImpCode Methods freeIn' :: ValueDesc -> FV Source #
FreeIn AtomicOp Source # |
Instance details Defined in Futhark.CodeGen.ImpCode.GPU Methods freeIn' :: AtomicOp -> FV Source #
FreeIn HostOp Source # |
Instance details Defined in Futhark.CodeGen.ImpCode.GPU Methods freeIn' :: HostOp -> FV Source #
FreeIn Kernel Source # |
Instance details Defined in Futhark.CodeGen.ImpCode.GPU Methods freeIn' :: Kernel -> FV Source #
FreeIn KernelConst Source # |
Instance details Defined in Futhark.CodeGen.ImpCode.GPU Methods freeIn' :: KernelConst -> FV Source #
FreeIn KernelOp Source # |
Instance details Defined in Futhark.CodeGen.ImpCode.GPU Methods freeIn' :: KernelOp -> FV Source #
FreeIn AtomicOp Source # |
Instance details Defined in Futhark.CodeGen.ImpCode.Multicore Methods freeIn' :: AtomicOp -> FV Source #
FreeIn Multicore Source # |
Instance details Defined in Futhark.CodeGen.ImpCode.Multicore Methods freeIn' :: Multicore -> FV Source #
FreeIn ParallelTask Source # |
Instance details Defined in Futhark.CodeGen.ImpCode.Multicore Methods freeIn' :: ParallelTask -> FV Source #
FreeIn SchedulerInfo Source # |
Instance details Defined in Futhark.CodeGen.ImpCode.Multicore Methods freeIn' :: SchedulerInfo -> FV Source #
FreeIn Sequential Source # |
Instance details Defined in Futhark.CodeGen.ImpCode.Sequential Methods freeIn' :: Sequential -> FV Source #
FreeIn AliasDec Source # |
Instance details Defined in Futhark.IR.Aliases Methods freeIn' :: AliasDec -> FV Source #
FreeIn KernelGrid Source # |
Instance details Defined in Futhark.IR.GPU.Op Methods freeIn' :: KernelGrid -> FV Source #
FreeIn SegLevel Source # |
Instance details Defined in Futhark.IR.GPU.Op Methods freeIn' :: SegLevel -> FV Source #
FreeIn SizeOp Source # |
Instance details Defined in Futhark.IR.GPU.Op Methods freeIn' :: SizeOp -> FV Source #
FreeIn MemBind Source # |
Instance details Defined in Futhark.IR.Mem Methods freeIn' :: MemBind -> FV Source #
FreeIn MemReturn Source # |
Instance details Defined in Futhark.IR.Mem Methods freeIn' :: MemReturn -> FV Source #
FreeIn Interval Source # |
Instance details Defined in Futhark.IR.Mem.Interval Methods freeIn' :: Interval -> FV Source #
FreeIn FV Source # |
Instance details Defined in Futhark.IR.Prop.Names Methods freeIn' :: FV -> FV Source #
FreeIn Names Source # |
Instance details Defined in Futhark.IR.Prop.Names Methods freeIn' :: Names -> FV Source #
FreeIn KernelResult Source # |
Instance details Defined in Futhark.IR.SegOp Methods freeIn' :: KernelResult -> FV Source #
FreeIn LoopForm Source # |
Instance details Defined in Futhark.IR.Prop.Names Methods freeIn' :: LoopForm -> FV Source #
FreeIn SubExpRes Source # |
Instance details Defined in Futhark.IR.Prop.Names Methods freeIn' :: SubExpRes -> FV Source #
FreeIn Attrs Source # |
Instance details Defined in Futhark.IR.Prop.Names Methods freeIn' :: Attrs -> FV Source #
FreeIn Certs Source # |
Instance details Defined in Futhark.IR.Prop.Names Methods freeIn' :: Certs -> FV Source #
FreeIn Ident Source # |
Instance details Defined in Futhark.IR.Prop.Names Methods freeIn' :: Ident -> FV Source #
FreeIn Space Source # |
Instance details Defined in Futhark.IR.Prop.Names Methods freeIn' :: Space -> FV Source #
FreeIn SubExp Source # |
Instance details Defined in Futhark.IR.Prop.Names Methods freeIn' :: SubExp -> FV Source #
FreeIn AccessSummary Source # |
Instance details Defined in Futhark.Optimise.ArrayShortCircuiting.DataStructs Methods freeIn' :: AccessSummary -> FV Source #
FreeIn ExpWisdom Source # |
Instance details Defined in Futhark.Optimise.Simplify.Rep Methods freeIn' :: ExpWisdom -> FV Source #
FreeIn VarWisdom Source # |
Instance details Defined in Futhark.Optimise.Simplify.Rep Methods freeIn' :: VarWisdom -> FV Source #
FreeIn LoopNesting Source # |
Instance details Defined in Futhark.Pass.ExtractKernels.Distribution Methods freeIn' :: LoopNesting -> FV Source #
FreeIn VName Source # |
Instance details Defined in Futhark.IR.Prop.Names Methods freeIn' :: VName -> FV Source #
FreeIn PrimType Source # |
Instance details Defined in Futhark.IR.Prop.Names Methods freeIn' :: PrimType -> FV Source #
FreeIn () Source # |
Instance details Defined in Futhark.IR.Prop.Names Methods freeIn' :: () -> FV Source #
FreeIn Bool Source # |
Instance details Defined in Futhark.IR.Prop.Names Methods freeIn' :: Bool -> FV Source #
FreeIn Int Source # |
Instance details Defined in Futhark.IR.Prop.Names Methods freeIn' :: Int -> FV Source #
FreeIn a => FreeIn (Set a) Source # |
Instance details Defined in Futhark.IR.Prop.Names Methods freeIn' :: Set a -> FV Source #
FreeIn v => FreeIn (PrimExp v) Source # |
Instance details Defined in Futhark.Analysis.PrimExp Methods freeIn' :: PrimExp v -> FV Source #
FreeIn a => FreeIn (Code a) Source # |
Instance details Defined in Futhark.CodeGen.ImpCode Methods freeIn' :: Code a -> FV Source #
FreeIn a => FreeIn (Functions a) Source # |
Instance details Defined in Futhark.CodeGen.ImpCode Methods freeIn' :: Functions a -> FV Source #
FreeIn num => FreeIn (LMAD num) Source # |
Instance details Defined in Futhark.IR.Mem.LMAD Methods freeIn' :: LMAD num -> FV Source #
FreeIn num => FreeIn (LMADDim num) Source # |
Instance details Defined in Futhark.IR.Mem.LMAD Methods freeIn' :: LMADDim num -> FV Source #
ASTRep rep => FreeIn (HistOp rep) Source # |
Instance details Defined in Futhark.IR.SOACS.SOAC Methods freeIn' :: HistOp rep -> FV Source #
ASTRep rep => FreeIn (Reduce rep) Source # |
Instance details Defined in Futhark.IR.SOACS.SOAC Methods freeIn' :: Reduce rep -> FV Source #
ASTRep rep => FreeIn (SOAC rep) Source # |
Instance details Defined in Futhark.IR.SOACS.SOAC Methods freeIn' :: SOAC rep -> FV Source #
ASTRep rep => FreeIn (Scan rep) Source # |
Instance details Defined in Futhark.IR.SOACS.SOAC Methods freeIn' :: Scan rep -> FV Source #
ASTRep rep => FreeIn (ScremaForm rep) Source # |
Instance details Defined in Futhark.IR.SOACS.SOAC Methods freeIn' :: ScremaForm rep -> FV Source #
ASTRep rep => FreeIn (KernelBody rep) Source # |
Instance details Defined in Futhark.IR.SegOp Methods freeIn' :: KernelBody rep -> FV Source #
(FreeDec (ExpDec rep), FreeDec (BodyDec rep), FreeIn (FParamInfo rep), FreeIn (LParamInfo rep), FreeIn (LetDec rep), FreeIn (RetType rep), FreeIn (BranchType rep), FreeIn (Op rep)) => FreeIn (Body rep) Source # |
Instance details Defined in Futhark.IR.Prop.Names Methods freeIn' :: Body rep -> FV Source #
FreeIn body => FreeIn (Case body) Source # |
Instance details Defined in Futhark.IR.Prop.Names Methods freeIn' :: Case body -> FV Source #
(FreeDec (ExpDec rep), FreeDec (BodyDec rep), FreeIn (FParamInfo rep), FreeIn (LParamInfo rep), FreeIn (LetDec rep), FreeIn (RetType rep), FreeIn (BranchType rep), FreeIn (Op rep)) => FreeIn (Exp rep) Source # |
Instance details Defined in Futhark.IR.Prop.Names Methods freeIn' :: Exp rep -> FV Source #
(FreeDec (ExpDec rep), FreeDec (BodyDec rep), FreeIn (FParamInfo rep), FreeIn (LParamInfo rep), FreeIn (LetDec rep), FreeIn (RetType rep), FreeIn (BranchType rep), FreeIn (Op rep)) => FreeIn (FunDef rep) Source # |
Instance details Defined in Futhark.IR.Prop.Names Methods freeIn' :: FunDef rep -> FV Source #
(FreeDec (ExpDec rep), FreeDec (BodyDec rep), FreeIn (FParamInfo rep), FreeIn (LParamInfo rep), FreeIn (LetDec rep), FreeIn (RetType rep), FreeIn (BranchType rep), FreeIn (Op rep)) => FreeIn (Lambda rep) Source # |
Instance details Defined in Futhark.IR.Prop.Names Methods freeIn' :: Lambda rep -> FV Source #
FreeIn a => FreeIn (MatchDec a) Source # |
Instance details Defined in Futhark.IR.Prop.Names Methods freeIn' :: MatchDec a -> FV Source #
FreeIn dec => FreeIn (Pat dec) Source # |
Instance details Defined in Futhark.IR.Prop.Names Methods freeIn' :: Pat dec -> FV Source #
(FreeDec (ExpDec rep), FreeDec (BodyDec rep), FreeIn (FParamInfo rep), FreeIn (LParamInfo rep), FreeIn (LetDec rep), FreeIn (RetType rep), FreeIn (BranchType rep), FreeIn (Op rep)) => FreeIn (Stm rep) Source # |
Instance details Defined in Futhark.IR.Prop.Names Methods freeIn' :: Stm rep -> FV Source #
FreeIn dec => FreeIn (StmAux dec) Source # |
Instance details Defined in Futhark.IR.Prop.Names Methods freeIn' :: StmAux dec -> FV Source #
FreeIn (Stm rep) => FreeIn (Stms rep) Source # |
Instance details Defined in Futhark.IR.Prop.Names Methods freeIn' :: Stms rep -> FV Source #
FreeIn d => FreeIn (DimIndex d) Source # |
Instance details Defined in Futhark.IR.Prop.Names Methods freeIn' :: DimIndex d -> FV Source #
FreeIn d => FreeIn (Ext d) Source # |
Instance details Defined in Futhark.IR.Prop.Names Methods freeIn' :: Ext d -> FV Source #
FreeIn d => FreeIn (FlatDimIndex d) Source # |
Instance details Defined in Futhark.IR.Prop.Names Methods freeIn' :: FlatDimIndex d -> FV Source #
FreeIn d => FreeIn (FlatSlice d) Source # |
Instance details Defined in Futhark.IR.Prop.Names Methods freeIn' :: FlatSlice d -> FV Source #
FreeIn dec => FreeIn (Param dec) Source # |
Instance details Defined in Futhark.IR.Prop.Names Methods freeIn' :: Param dec -> FV Source #
FreeIn dec => FreeIn (PatElem dec) Source # |
Instance details Defined in Futhark.IR.Prop.Names Methods freeIn' :: PatElem dec -> FV Source #
FreeIn d => FreeIn (ShapeBase d) Source # |
Instance details Defined in Futhark.IR.Prop.Names Methods freeIn' :: ShapeBase d -> FV Source #
FreeIn d => FreeIn (Slice d) Source # |
Instance details Defined in Futhark.IR.Prop.Names Methods freeIn' :: Slice d -> FV Source #
FreeIn a => FreeIn (Maybe a) Source # |
Instance details Defined in Futhark.IR.Prop.Names Methods freeIn' :: Maybe a -> FV Source #
FreeIn a => FreeIn [a] Source # |
Instance details Defined in Futhark.IR.Prop.Names Methods freeIn' :: [a] -> FV Source #
(FreeIn a, FreeIn b) => FreeIn (Either a b) Source # |
Instance details Defined in Futhark.IR.Prop.Names Methods freeIn' :: Either a b -> FV Source #
(ASTRep rep, FreeIn (op rep)) => FreeIn (HostOp op rep) Source # |
Instance details Defined in Futhark.IR.GPU.Op Methods freeIn' :: HostOp op rep -> FV Source #
(ASTRep rep, FreeIn (op rep)) => FreeIn (MCOp op rep) Source # |
Instance details Defined in Futhark.IR.MC.Op Methods freeIn' :: MCOp op rep -> FV Source #
FreeIn (inner rep) => FreeIn (MemOp inner rep) Source # |
Instance details Defined in Futhark.IR.Mem Methods freeIn' :: MemOp inner rep -> FV Source #
FreeIn (NoOp rep) Source # |
Instance details Defined in Futhark.IR.Prop.Names Methods freeIn' :: NoOp rep -> FV Source #
(ASTRep rep, FreeIn lvl) => FreeIn (SegOp lvl rep) Source # |
Instance details Defined in Futhark.IR.SegOp Methods freeIn' :: SegOp lvl rep -> FV Source #
FreeIn shape => FreeIn (TypeBase shape u) Source # |
Instance details Defined in Futhark.IR.Prop.Names Methods freeIn' :: TypeBase shape u -> FV Source #
(FreeIn a, FreeIn b) => FreeIn (a, b) Source # |
Instance details Defined in Futhark.IR.Prop.Names Methods freeIn' :: (a, b) -> FV Source #
FreeIn v => FreeIn (TPrimExp t v) Source # |
Instance details Defined in Futhark.Analysis.PrimExp Methods freeIn' :: TPrimExp t v -> FV Source #
FreeIn e => FreeIn (Count u e) Source # |
Instance details Defined in Futhark.IR.GPU.Sizes Methods freeIn' :: Count u e -> FV Source #
(FreeIn d, FreeIn ret) => FreeIn (MemInfo d u ret) Source # |
Instance details Defined in Futhark.IR.Mem Methods freeIn' :: MemInfo d u ret -> FV Source #
(FreeIn a, FreeIn b, FreeIn c) => FreeIn (a, b, c) Source # |
Instance details Defined in Futhark.IR.Prop.Names Methods freeIn' :: (a, b, c) -> FV Source #
(FreeIn a, FreeIn b, FreeIn c, FreeIn d) => FreeIn (a, b, c, d) Source # |
Instance details Defined in Futhark.IR.Prop.Names Methods freeIn' :: (a, b, c, d) -> FV Source #

freeIn :: FreeIn a => a -> Names Source #

The free variables of some syntactic construct.

# Specialised Functions

freeInStmsAndRes :: (FreeIn (Op rep), FreeIn (LetDec rep), FreeIn (LParamInfo rep), FreeIn (FParamInfo rep), FreeDec (BodyDec rep), FreeIn (RetType rep), FreeIn (BranchType rep), FreeDec (ExpDec rep)) => Stms rep -> Result -> FV Source #

Return the set of variable names that are free in the given statements and result. Filters away the names that are bound by the statements.

# Bound Names

boundInBody :: Body rep -> Names Source #

The names bound by the bindings immediately in a `Body`.

boundByStm :: Stm rep -> Names Source #

The names bound by a binding.

boundByStms :: Stms rep -> Names Source #

The names bound by the bindings.

boundByLambda :: Lambda rep -> [VName] Source #

The names of the lambda parameters plus the index parameter.

# Efficient computation

class FreeIn dec => FreeDec dec where Source #

Either return precomputed free names stored in the attribute, or the freshly computed names. Relies on lazy evaluation to avoid the work.

Minimal complete definition

Nothing

Methods

precomputed :: dec -> FV -> FV Source #

#### Instances

Instances details

FreeDec AliasDec Source # |
Instance details Defined in Futhark.IR.Aliases Methods precomputed :: AliasDec -> FV -> FV Source #
FreeDec Names Source # |
Instance details Defined in Futhark.IR.Prop.Names Methods precomputed :: Names -> FV -> FV Source #
FreeDec ExpWisdom Source # |
Instance details Defined in Futhark.Optimise.Simplify.Rep Methods precomputed :: ExpWisdom -> FV -> FV Source #
FreeDec () Source # |
Instance details Defined in Futhark.IR.Prop.Names Methods precomputed :: () -> FV -> FV Source #
FreeDec a => FreeDec (Maybe a) Source # |
Instance details Defined in Futhark.IR.Prop.Names Methods precomputed :: Maybe a -> FV -> FV Source #
FreeDec a => FreeDec [a] Source # |
Instance details Defined in Futhark.IR.Prop.Names Methods precomputed :: [a] -> FV -> FV Source #
(FreeDec a, FreeIn b) => FreeDec (a, b) Source # |
Instance details Defined in Futhark.IR.Prop.Names Methods precomputed :: (a, b) -> FV -> FV Source #

data FV Source #

A computation to build a free variable set.

#### Instances

Instances details

Monoid FV Source # |
Instance details Defined in Futhark.IR.Prop.Names Methods mempty :: FV Source # mappend :: FV -> FV -> FV Source # mconcat :: [FV] -> FV Source #
Semigroup FV Source # |
Instance details Defined in Futhark.IR.Prop.Names Methods (<>) :: FV -> FV -> FV Source # sconcat :: NonEmpty FV -> FV Source # stimes :: Integral b => b -> FV -> FV Source #
FreeIn FV Source # |
Instance details Defined in Futhark.IR.Prop.Names Methods freeIn' :: FV -> FV Source #
Substitute FV Source # |
Instance details Defined in Futhark.Transform.Substitute Methods substituteNames :: Map VName VName -> FV -> FV Source #

fvBind :: Names -> FV -> FV Source #

Consider a variable to be bound in the given `FV` computation.

fvName :: VName -> FV Source #

Take note of a variable reference.

fvNames :: Names -> FV Source #

Take note of a set of variable references.