Safe Haskell	Safe-Inferred
Language	GHC2021

Futhark.Analysis.AccessPattern

Synopsis

analyseDimAccesses :: Analyse rep => Prog rep -> IndexTable rep
analyseFunction :: Analyse rep => FunDef rep -> IndexTable rep
vnameFromSegOp :: SegOpName -> VName
analysisPropagateByTransitivity :: IndexTable rep -> IndexTable rep
isInvariant :: DimAccess rep -> Bool
class Analyse rep
type IndexTable rep = Map SegOpName (Map ArrayName (Map IndexExprName [DimAccess rep]))
type ArrayName = (VName, [BodyType], [Int])
data DimAccess rep = DimAccess {
- dependencies :: Map VName Dependency
- originalVar :: Maybe VName
}
type IndexExprName = VName
data BodyType
- = SegOpName SegOpName
- | LoopBodyName VName
- | CondBodyName VName
data SegOpName
- = SegmentedMap VName
- | SegmentedRed VName
- | SegmentedScan VName
- | SegmentedHist VName
data Context rep = Context {
- assignments :: Map VName (VariableInfo rep)
- slices :: Map IndexExprName (ArrayName, [VName], [DimAccess rep])
- parents :: [BodyType]
- currentLevel :: Int
}
analyseIndex :: Context rep -> [VName] -> VName -> [DimIndex SubExp] -> (Context rep, IndexTable rep)
data VariableInfo rep = VariableInfo {
- deps :: Names
- level :: Int
- parents_nest :: [BodyType]
- variableType :: VarType
}
data VarType
- = ConstType
- | Variable
- | ThreadID
- | LoopVar
isCounter :: VarType -> Bool
data Dependency = Dependency {
- lvl :: Int
- varType :: VarType
}

Documentation

analyseDimAccesses :: Analyse rep => Prog rep -> IndexTable rep Source #

Analyse each entry and accumulate the results.

analyseFunction :: Analyse rep => FunDef rep -> IndexTable rep Source #

Analyse each statement in a function body.

vnameFromSegOp :: SegOpName -> VName Source #

analysisPropagateByTransitivity :: IndexTable rep -> IndexTable rep Source #

Make segops on arrays transitive, ie. if > let A = segmap (..) xs -- A indexes into xs > let B = segmap (..) A -- B indexes into A Then B also derives all A's array-accesses, like xs. Runs in n²

isInvariant :: DimAccess rep -> Bool Source #

class Analyse rep Source #

A representation where we can analyse access patterns.

Minimal complete definition

analyseOp

Instances

Instances details

Analyse GPU Source #
Instance details Defined in Futhark.Analysis.AccessPattern Methods analyseOp :: Op GPU -> Context GPU -> [VName] -> (Context GPU, IndexTable GPU)
Analyse GPUMem Source #
Instance details Defined in Futhark.Analysis.AccessPattern Methods analyseOp :: Op GPUMem -> Context GPUMem -> [VName] -> (Context GPUMem, IndexTable GPUMem)
Analyse MC Source #
Instance details Defined in Futhark.Analysis.AccessPattern Methods analyseOp :: Op MC -> Context MC -> [VName] -> (Context MC, IndexTable MC)
Analyse MCMem Source #
Instance details Defined in Futhark.Analysis.AccessPattern Methods analyseOp :: Op MCMem -> Context MCMem -> [VName] -> (Context MCMem, IndexTable MCMem)
Analyse SOACS Source #
Instance details Defined in Futhark.Analysis.AccessPattern Methods analyseOp :: Op SOACS -> Context SOACS -> [VName] -> (Context SOACS, IndexTable SOACS)
Analyse Seq Source #
Instance details Defined in Futhark.Analysis.AccessPattern Methods analyseOp :: Op Seq -> Context Seq -> [VName] -> (Context Seq, IndexTable Seq)
Analyse SeqMem Source #
Instance details Defined in Futhark.Analysis.AccessPattern Methods analyseOp :: Op SeqMem -> Context SeqMem -> [VName] -> (Context SeqMem, IndexTable SeqMem)

type IndexTable rep = Map SegOpName (Map ArrayName (Map IndexExprName [DimAccess rep])) Source #

For each array access in a program, this data structure stores the dependencies of each dimension in the access, the array name, and the name of the SegOp that the access is contained in. Each DimAccess element corresponds to an access to a given dimension in the given array, in the same order of the dimensions.

type ArrayName = (VName, [BodyType], [Int]) Source #

Stores the name of an array, the nest of loops, kernels, conditionals in which it is constructed, and the existing layout of the array. The latter is currently largely unused and not trustworthy, but might be useful in the future.

data DimAccess rep Source #

Collect all features of access to a specific dimension of an array.

Constructors

DimAccess
Fields dependencies :: Map VName Dependency Set of VNames of iteration variables (gtids, loop counters, etc.) that some access is variant to. An empty set indicates that the access is invariant. originalVar :: Maybe VName Used to store the name of the original expression from which `dependencies` was computed. `Nothing` if it is a constant.

Instances

Instances details

Monoid (DimAccess rep) Source #
Instance details Defined in Futhark.Analysis.AccessPattern Methods mempty :: DimAccess rep # mappend :: DimAccess rep -> DimAccess rep -> DimAccess rep # mconcat :: [DimAccess rep] -> DimAccess rep #
Semigroup (DimAccess rep) Source #
Instance details Defined in Futhark.Analysis.AccessPattern Methods (<>) :: DimAccess rep -> DimAccess rep -> DimAccess rep # sconcat :: NonEmpty (DimAccess rep) -> DimAccess rep # stimes :: Integral b => b -> DimAccess rep -> DimAccess rep #
Show (DimAccess rep) Source #
Instance details Defined in Futhark.Analysis.AccessPattern Methods showsPrec :: Int -> DimAccess rep -> ShowS # show :: DimAccess rep -> String # showList :: [DimAccess rep] -> ShowS #
Eq (DimAccess rep) Source #
Instance details Defined in Futhark.Analysis.AccessPattern Methods (==) :: DimAccess rep -> DimAccess rep -> Bool # (/=) :: DimAccess rep -> DimAccess rep -> Bool #
Pretty (DimAccess rep) Source #
Instance details Defined in Futhark.Analysis.AccessPattern Methods pretty :: DimAccess rep -> Doc ann # prettyList :: [DimAccess rep] -> Doc ann #
Pretty (IndexTable rep) Source #
Instance details Defined in Futhark.Analysis.AccessPattern Methods pretty :: IndexTable rep -> Doc ann # prettyList :: [IndexTable rep] -> Doc ann #

type IndexExprName = VName Source #

Name of an array indexing expression. Taken from the pattern of the expression.

data BodyType Source #

Constructors

SegOpName SegOpName
LoopBodyName VName
CondBodyName VName

Instances

Instances details

Show BodyType Source #
Instance details Defined in Futhark.Analysis.AccessPattern Methods showsPrec :: Int -> BodyType -> ShowS # show :: BodyType -> String # showList :: [BodyType] -> ShowS #
Eq BodyType Source #
Instance details Defined in Futhark.Analysis.AccessPattern Methods (==) :: BodyType -> BodyType -> Bool # (/=) :: BodyType -> BodyType -> Bool #
Ord BodyType Source #
Instance details Defined in Futhark.Analysis.AccessPattern Methods compare :: BodyType -> BodyType -> Ordering # (<) :: BodyType -> BodyType -> Bool # (<=) :: BodyType -> BodyType -> Bool # (>) :: BodyType -> BodyType -> Bool # (>=) :: BodyType -> BodyType -> Bool # max :: BodyType -> BodyType -> BodyType # min :: BodyType -> BodyType -> BodyType #
Pretty BodyType Source #
Instance details Defined in Futhark.Analysis.AccessPattern Methods pretty :: BodyType -> Doc ann # prettyList :: [BodyType] -> Doc ann #
Pretty (IndexTable rep) Source #
Instance details Defined in Futhark.Analysis.AccessPattern Methods pretty :: IndexTable rep -> Doc ann # prettyList :: [IndexTable rep] -> Doc ann #

data SegOpName Source #

Name of a SegOp, used to identify the SegOp that an array access is contained in.

Constructors

SegmentedMap VName
SegmentedRed VName
SegmentedScan VName
SegmentedHist VName

Instances

Instances details

Show SegOpName Source #
Instance details Defined in Futhark.Analysis.AccessPattern Methods showsPrec :: Int -> SegOpName -> ShowS # show :: SegOpName -> String # showList :: [SegOpName] -> ShowS #
Eq SegOpName Source #
Instance details Defined in Futhark.Analysis.AccessPattern Methods (==) :: SegOpName -> SegOpName -> Bool # (/=) :: SegOpName -> SegOpName -> Bool #
Ord SegOpName Source #
Instance details Defined in Futhark.Analysis.AccessPattern Methods compare :: SegOpName -> SegOpName -> Ordering # (<) :: SegOpName -> SegOpName -> Bool # (<=) :: SegOpName -> SegOpName -> Bool # (>) :: SegOpName -> SegOpName -> Bool # (>=) :: SegOpName -> SegOpName -> Bool # max :: SegOpName -> SegOpName -> SegOpName # min :: SegOpName -> SegOpName -> SegOpName #
Pretty SegOpName Source #
Instance details Defined in Futhark.Analysis.AccessPattern Methods pretty :: SegOpName -> Doc ann # prettyList :: [SegOpName] -> Doc ann #
Pretty (IndexTable rep) Source #
Instance details Defined in Futhark.Analysis.AccessPattern Methods pretty :: IndexTable rep -> Doc ann # prettyList :: [IndexTable rep] -> Doc ann #

data Context rep Source #

Used during the analysis to keep track of the dependencies of patterns encountered so far.

Constructors

Context

Fields

assignments :: Map VName (VariableInfo rep)
A mapping from patterns occuring in Let expressions to their dependencies and iteration types.
slices :: Map IndexExprName (ArrayName, [VName], [DimAccess rep])
Maps from sliced arrays to their respective access patterns.
parents :: [BodyType]
A list of the segMaps encountered during the analysis in the order they were encountered.
currentLevel :: Int
Current level of recursion, also just `length parents`

Instances

Instances details

Monoid (Context rep) Source #
Instance details Defined in Futhark.Analysis.AccessPattern Methods mempty :: Context rep # mappend :: Context rep -> Context rep -> Context rep # mconcat :: [Context rep] -> Context rep #
Semigroup (Context rep) Source #
Instance details Defined in Futhark.Analysis.AccessPattern Methods (<>) :: Context rep -> Context rep -> Context rep # sconcat :: NonEmpty (Context rep) -> Context rep # stimes :: Integral b => b -> Context rep -> Context rep #
Show (Context rep) Source #
Instance details Defined in Futhark.Analysis.AccessPattern Methods showsPrec :: Int -> Context rep -> ShowS # show :: Context rep -> String # showList :: [Context rep] -> ShowS #
Eq (Context rep) Source #
Instance details Defined in Futhark.Analysis.AccessPattern Methods (==) :: Context rep -> Context rep -> Bool # (/=) :: Context rep -> Context rep -> Bool #

analyseIndex :: Context rep -> [VName] -> VName -> [DimIndex SubExp] -> (Context rep, IndexTable rep) Source #

Gets the dependencies of each dimension and either returns a result, or adds a slice to the context.

data VariableInfo rep Source #

Context Value (VariableInfo) is the type used in the context to categorize assignments. For example, a pattern might depend on a function parameter, a gtid, or some other pattern.

Constructors

VariableInfo
Fields deps :: Names level :: Int parents_nest :: [BodyType] variableType :: VarType

Instances

Instances details

Show (VariableInfo rep) Source #
Instance details Defined in Futhark.Analysis.AccessPattern Methods showsPrec :: Int -> VariableInfo rep -> ShowS # show :: VariableInfo rep -> String # showList :: [VariableInfo rep] -> ShowS #
Eq (VariableInfo rep) Source #
Instance details Defined in Futhark.Analysis.AccessPattern Methods (==) :: VariableInfo rep -> VariableInfo rep -> Bool # (/=) :: VariableInfo rep -> VariableInfo rep -> Bool #

data VarType Source #

Constructors

ConstType
Variable
ThreadID
LoopVar

Instances

Instances details

Show VarType Source #
Instance details Defined in Futhark.Analysis.AccessPattern Methods showsPrec :: Int -> VarType -> ShowS # show :: VarType -> String # showList :: [VarType] -> ShowS #
Eq VarType Source #
Instance details Defined in Futhark.Analysis.AccessPattern Methods (==) :: VarType -> VarType -> Bool # (/=) :: VarType -> VarType -> Bool #
Pretty VarType Source #
Instance details Defined in Futhark.Analysis.AccessPattern Methods pretty :: VarType -> Doc ann # prettyList :: [VarType] -> Doc ann #

isCounter :: VarType -> Bool Source #

data Dependency Source #

Tuple of patternName and nested level it index occurred at, as well as what the actual iteration type is.

Constructors

Dependency
Fields lvl :: Int varType :: VarType

Instances

Instances details

Show Dependency Source #
Instance details Defined in Futhark.Analysis.AccessPattern Methods showsPrec :: Int -> Dependency -> ShowS # show :: Dependency -> String # showList :: [Dependency] -> ShowS #
Eq Dependency Source #
Instance details Defined in Futhark.Analysis.AccessPattern Methods (==) :: Dependency -> Dependency -> Bool # (/=) :: Dependency -> Dependency -> Bool #