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

Safe Haskell | Safe-Inferred
Language | GHC2021

Futhark.IR.Aliases

Contents

- The representation definition
- Module re-exports
- Adding aliases
- Removing aliases
- Tracking aliases

Description

A representation where all patterns are annotated with aliasing information. It also records consumption of variables in bodies.

Note that this module is mostly not concerned with actually computing the aliasing information; only with shuffling it around and providing some basic building blocks. See modules such as Futhark.Analysis.Alias for computing the aliases in the first place.

Synopsis

- data Aliases (rep :: Type)
- newtype AliasDec = AliasDec {
  - unAliases :: Names
  }
- type VarAliases = AliasDec
- type ConsumedInExp = AliasDec
- type BodyAliasing = ([VarAliases], ConsumedInExp)
- module Futhark.IR.Prop.Aliases
- module Futhark.IR.Prop
- module Futhark.IR.Traversals
- module Futhark.IR.Pretty
- module Futhark.IR.Syntax
- mkAliasedBody :: (ASTRep rep, AliasedOp (OpC rep), ASTConstraints (OpC rep (Aliases rep))) => BodyDec rep -> Stms (Aliases rep) -> Result -> Body (Aliases rep)
- mkAliasedPat :: (Aliased rep, Typed dec) => Pat dec -> Exp rep -> Pat (VarAliases, dec)
- mkBodyAliasing :: Aliased rep => Stms rep -> Result -> BodyAliasing
- class CanBeAliased op where
  - addOpAliases :: AliasableRep rep => AliasTable -> op rep -> op (Aliases rep)
- type AliasableRep rep = (ASTRep rep, RephraseOp (OpC rep), CanBeAliased (OpC rep), AliasedOp (OpC rep), ASTConstraints (OpC rep (Aliases rep)))
- removeProgAliases :: RephraseOp (OpC rep) => Prog (Aliases rep) -> Prog rep
- removeFunDefAliases :: RephraseOp (OpC rep) => FunDef (Aliases rep) -> FunDef rep
- removeExpAliases :: RephraseOp (OpC rep) => Exp (Aliases rep) -> Exp rep
- removeStmAliases :: RephraseOp (OpC rep) => Stm (Aliases rep) -> Stm rep
- removeBodyAliases :: RephraseOp (OpC rep) => Body (Aliases rep) -> Body rep
- removeLambdaAliases :: RephraseOp (OpC rep) => Lambda (Aliases rep) -> Lambda rep
- removePatAliases :: Pat (AliasDec, a) -> Pat a
- removeScopeAliases :: Scope (Aliases rep) -> Scope rep
- type AliasesAndConsumed = (Map VName Names, Names)
- trackAliases :: Aliased rep => AliasesAndConsumed -> Stm rep -> AliasesAndConsumed
- mkStmsAliases :: Aliased rep => Stms rep -> Result -> ([Names], Names)
- consumedInStms :: Aliased rep => Stms rep -> Names

# The representation definition

data Aliases (rep :: Type) Source #

The rep for the basic representation.

#### Instances

Instances details

(ASTRep rep, AliasedOp (OpC rep), Buildable (Aliases rep)) => BuilderOps (Aliases rep) Source # |

Instance details

Defined in Futhark.IR.Aliases

Methods

mkExpDecB :: (MonadBuilder m, Rep m ~ Aliases rep) => Pat (LetDec (Aliases rep)) -> Exp (Aliases rep) -> m (ExpDec (Aliases rep)) Source #

mkBodyB :: (MonadBuilder m, Rep m ~ Aliases rep) => Stms (Aliases rep) -> Result -> m (Body (Aliases rep)) Source #

mkLetNamesB :: (MonadBuilder m, Rep m ~ Aliases rep) => [VName] -> Exp (Aliases rep) -> m (Stm (Aliases rep)) Source #

(Buildable rep, AliasedOp (OpC rep), ASTConstraints (OpC rep (Aliases rep))) => Buildable (Aliases rep) Source # |

Instance details

Defined in Futhark.IR.Aliases

Methods

mkExpPat :: [Ident] -> Exp (Aliases rep) -> Pat (LetDec (Aliases rep)) Source #

mkExpDec :: Pat (LetDec (Aliases rep)) -> Exp (Aliases rep) -> ExpDec (Aliases rep) Source #

mkBody :: Stms (Aliases rep) -> Result -> Body (Aliases rep) Source #

mkLetNames :: (MonadFreshNames m, HasScope (Aliases rep) m) => [VName] -> Exp (Aliases rep) -> m (Stm (Aliases rep)) Source #

(ASTRep rep, AliasedOp (OpC rep), ASTConstraints (OpC rep (Aliases rep))) => PrettyRep (Aliases rep) Source # |
Instance details Defined in Futhark.IR.Aliases Methods ppExpDec :: ExpDec (Aliases rep) -> Exp (Aliases rep) -> Maybe (Doc a) Source #
(ASTRep rep, AliasedOp (OpC rep), ASTConstraints (OpC rep (Aliases rep))) => ASTRep (Aliases rep) Source # |
Instance details Defined in Futhark.IR.Aliases Methods expTypesFromPat :: (HasScope (Aliases rep) m, Monad m) => Pat (LetDec (Aliases rep)) -> m [BranchType (Aliases rep)] Source #
(ASTRep rep, AliasedOp (OpC rep), ASTConstraints (OpC rep (Aliases rep))) => Aliased (Aliases rep) Source # |
Instance details Defined in Futhark.IR.Aliases Methods bodyAliases :: Body (Aliases rep) -> [Names] Source # consumedInBody :: Body (Aliases rep) -> Names Source #
(RepTypes rep, ASTConstraints (OpC rep (Aliases rep))) => RepTypes (Aliases rep) Source # |
Instance details Defined in Futhark.IR.Aliases Associated Types type LetDec (Aliases rep) Source # type ExpDec (Aliases rep) Source # type BodyDec (Aliases rep) Source # type FParamInfo (Aliases rep) Source # type LParamInfo (Aliases rep) Source # type RetType (Aliases rep) Source # type BranchType (Aliases rep) Source # type OpC (Aliases rep) :: Type -> Type Source #
HasMemBlock (Aliases GPUMem) Source # |
Instance details Defined in Futhark.Optimise.ArrayShortCircuiting.DataStructs Methods getScopeMemInfo :: VName -> Scope (Aliases GPUMem) -> Maybe ArrayMemBound Source #
HasMemBlock (Aliases MCMem) Source # |
Instance details Defined in Futhark.Optimise.ArrayShortCircuiting.DataStructs Methods getScopeMemInfo :: VName -> Scope (Aliases MCMem) -> Maybe ArrayMemBound Source #
HasMemBlock (Aliases SeqMem) Source # |
Instance details Defined in Futhark.Optimise.ArrayShortCircuiting.DataStructs Methods getScopeMemInfo :: VName -> Scope (Aliases SeqMem) -> Maybe ArrayMemBound Source #
(AliasableRep rep, CSEInOp (Op (Aliases rep))) => CSEInOp (SOAC (Aliases rep)) Source # |
Instance details Defined in Futhark.Optimise.CSE Methods cseInOp :: SOAC (Aliases rep) -> CSEM rep0 (SOAC (Aliases rep))
Checkable rep => HasScope (Aliases rep) (TypeM rep) Source # |
Instance details Defined in Futhark.IR.TypeCheck Methods lookupType :: VName -> TypeM rep Type Source # lookupInfo :: VName -> TypeM rep (NameInfo (Aliases rep)) Source # askScope :: TypeM rep (Scope (Aliases rep)) Source # asksScope :: (Scope (Aliases rep) -> a) -> TypeM rep a Source #
TopDownHelper (HostOp (NoOp :: Type -> Type) (Aliases GPUMem)) Source # |
Instance details Defined in Futhark.Optimise.ArrayShortCircuiting.TopdownAnalysis Methods innerNonNegatives :: [VName] -> HostOp NoOp (Aliases GPUMem) -> Names innerKnownLessThan :: HostOp NoOp (Aliases GPUMem) -> [(VName, PrimExp VName)] scopeHelper :: HostOp NoOp (Aliases GPUMem) -> Scope rep
TopDownHelper (inner (Aliases MCMem)) => TopDownHelper (MCOp inner (Aliases MCMem)) Source # |
Instance details Defined in Futhark.Optimise.ArrayShortCircuiting.TopdownAnalysis Methods innerNonNegatives :: [VName] -> MCOp inner (Aliases MCMem) -> Names innerKnownLessThan :: MCOp inner (Aliases MCMem) -> [(VName, PrimExp VName)] scopeHelper :: MCOp inner (Aliases MCMem) -> Scope rep
type BodyDec (Aliases rep) Source # |
Instance details Defined in Futhark.IR.Aliases type BodyDec (Aliases rep) = (BodyAliasing, BodyDec rep)
type BranchType (Aliases rep) Source # |
Instance details Defined in Futhark.IR.Aliases type BranchType (Aliases rep) = BranchType rep
type ExpDec (Aliases rep) Source # |
Instance details Defined in Futhark.IR.Aliases type ExpDec (Aliases rep) = (ConsumedInExp, ExpDec rep)
type FParamInfo (Aliases rep) Source # |
Instance details Defined in Futhark.IR.Aliases type FParamInfo (Aliases rep) = FParamInfo rep
type LParamInfo (Aliases rep) Source # |
Instance details Defined in Futhark.IR.Aliases type LParamInfo (Aliases rep) = LParamInfo rep
type LetDec (Aliases rep) Source # |
Instance details Defined in Futhark.IR.Aliases type LetDec (Aliases rep) = (VarAliases, LetDec rep)
type OpC (Aliases rep) Source # |
Instance details Defined in Futhark.IR.Aliases type OpC (Aliases rep) = OpC rep
type RetType (Aliases rep) Source # |
Instance details Defined in Futhark.IR.Aliases type RetType (Aliases rep) = RetType rep

newtype AliasDec Source #

A wrapper around `AliasDec` to get around the fact that we need an `Ord` instance, which 'AliasDec does not have.

Constructors

AliasDec |

Fields

- unAliases :: Names

#### Instances

Instances details

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

type VarAliases = AliasDec Source #

The aliases of the let-bound variable.

type ConsumedInExp = AliasDec Source #

Everything consumed in the expression.

type BodyAliasing = ([VarAliases], ConsumedInExp) Source #

The aliases of what is returned by the `Body`, and what is consumed inside of it.

module Futhark.IR.Prop.Aliases

# Module re-exports

module Futhark.IR.Prop

module Futhark.IR.Traversals

module Futhark.IR.Pretty

module Futhark.IR.Syntax

# Adding aliases

mkAliasedBody :: (ASTRep rep, AliasedOp (OpC rep), ASTConstraints (OpC rep (Aliases rep))) => BodyDec rep -> Stms (Aliases rep) -> Result -> Body (Aliases rep) Source #

Augment a body decoration with aliasing information provided by the statements and result of that body.

mkAliasedPat :: (Aliased rep, Typed dec) => Pat dec -> Exp rep -> Pat (VarAliases, dec) Source #

Augment a pattern with aliasing information provided by the expression the pattern is bound to.

mkBodyAliasing :: Aliased rep => Stms rep -> Result -> BodyAliasing Source #

Given statements (with aliasing information) and a body result, produce aliasing information for the corresponding body as a whole. The aliasing includes names bound in the body, i.e. which are not in scope outside of it. Note that this does *not* include aliases of results that are not bound in the statements!

class CanBeAliased op where Source #

The class of operations that can be given aliasing information. This is a somewhat subtle concept that is only used in the simplifier and when using "rep adapters".

Methods

addOpAliases :: AliasableRep rep => AliasTable -> op rep -> op (Aliases rep) Source #

Add aliases to this op.

#### Instances

Instances details

CanBeAliased SOAC Source # |
Instance details Defined in Futhark.IR.SOACS.SOAC Methods addOpAliases :: AliasableRep rep => AliasTable -> SOAC rep -> SOAC (Aliases rep) Source #
CanBeAliased op => CanBeAliased (HostOp op) Source # |
Instance details Defined in Futhark.IR.GPU.Op Methods addOpAliases :: AliasableRep rep => AliasTable -> HostOp op rep -> HostOp op (Aliases rep) Source #
CanBeAliased op => CanBeAliased (MCOp op) Source # |
Instance details Defined in Futhark.IR.MC.Op Methods addOpAliases :: AliasableRep rep => AliasTable -> MCOp op rep -> MCOp op (Aliases rep) Source #
CanBeAliased inner => CanBeAliased (MemOp inner) Source # |
Instance details Defined in Futhark.IR.Mem Methods addOpAliases :: AliasableRep rep => AliasTable -> MemOp inner rep -> MemOp inner (Aliases rep) Source #
CanBeAliased (NoOp :: Type -> Type) Source # |
Instance details Defined in Futhark.IR.Aliases Methods addOpAliases :: AliasableRep rep => AliasTable -> NoOp rep -> NoOp (Aliases rep) Source #
CanBeAliased (SegOp lvl) Source # |
Instance details Defined in Futhark.IR.SegOp Methods addOpAliases :: AliasableRep rep => AliasTable -> SegOp lvl rep -> SegOp lvl (Aliases rep) Source #

type AliasableRep rep = (ASTRep rep, RephraseOp (OpC rep), CanBeAliased (OpC rep), AliasedOp (OpC rep), ASTConstraints (OpC rep (Aliases rep))) Source #

What we require of an aliasable representation.

# Removing aliases

removeProgAliases :: RephraseOp (OpC rep) => Prog (Aliases rep) -> Prog rep Source #

Remove alias information from a program.

removeFunDefAliases :: RephraseOp (OpC rep) => FunDef (Aliases rep) -> FunDef rep Source #

Remove alias information from a function.

removeExpAliases :: RephraseOp (OpC rep) => Exp (Aliases rep) -> Exp rep Source #

Remove alias information from an expression.

removeStmAliases :: RephraseOp (OpC rep) => Stm (Aliases rep) -> Stm rep Source #

Remove alias information from statements.

removeBodyAliases :: RephraseOp (OpC rep) => Body (Aliases rep) -> Body rep Source #

Remove alias information from body.

removeLambdaAliases :: RephraseOp (OpC rep) => Lambda (Aliases rep) -> Lambda rep Source #

Remove alias information from lambda.

removePatAliases :: Pat (AliasDec, a) -> Pat a Source #

Remove alias information from pattern.

removeScopeAliases :: Scope (Aliases rep) -> Scope rep Source #

Remove alias information from an aliased scope.

# Tracking aliases

type AliasesAndConsumed = (Map VName Names, Names) Source #

A tuple of a mapping from variable names to their aliases, and the names of consumed variables.

trackAliases :: Aliased rep => AliasesAndConsumed -> Stm rep -> AliasesAndConsumed Source #

A helper function for computing the aliases of a sequence of statements. You'd use this while recursing down the statements from first to last. The `AliasesAndConsumed` parameter is the current "state" of aliasing, and the function then returns a new state. The main thing this function provides is proper handling of transitivity and "reverse" aliases.

mkStmsAliases :: Aliased rep => Stms rep -> Result -> ([Names], Names) Source #

The aliases of the result and everything consumed in the given statements.

consumedInStms :: Aliased rep => Stms rep -> Names Source #

The variables consumed in these statements.