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

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

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

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 Source # show :: SegOpName -> String Source # showList :: [SegOpName] -> ShowS Source #
Eq SegOpName Source # |
Instance details Defined in Futhark.Analysis.AccessPattern Methods (==) :: SegOpName -> SegOpName -> Bool Source # (/=) :: SegOpName -> SegOpName -> Bool Source #
Ord SegOpName Source # |

Instance details

Defined in Futhark.Analysis.AccessPattern

Methods

compare :: SegOpName -> SegOpName -> Ordering Source #

(<) :: SegOpName -> SegOpName -> Bool Source #

(<=) :: SegOpName -> SegOpName -> Bool Source #

(>) :: SegOpName -> SegOpName -> Bool Source #

(>=) :: SegOpName -> SegOpName -> Bool Source #

max :: SegOpName -> SegOpName -> SegOpName Source #

min :: SegOpName -> SegOpName -> SegOpName Source #

Pretty SegOpName Source # |
Instance details Defined in Futhark.Analysis.AccessPattern Methods pretty :: SegOpName -> Doc ann Source # prettyList :: [SegOpName] -> Doc ann Source #
Pretty (IndexTable rep) Source # |
Instance details Defined in Futhark.Analysis.AccessPattern Methods pretty :: IndexTable rep -> Doc ann Source # prettyList :: [IndexTable rep] -> Doc ann Source #

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

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 Source # show :: VariableInfo rep -> String Source # showList :: [VariableInfo rep] -> ShowS Source #
Eq (VariableInfo rep) Source # |
Instance details Defined in Futhark.Analysis.AccessPattern Methods (==) :: VariableInfo rep -> VariableInfo rep -> Bool Source # (/=) :: VariableInfo rep -> VariableInfo rep -> Bool Source #

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 Source # show :: VarType -> String Source # showList :: [VarType] -> ShowS Source #
Eq VarType Source # |
Instance details Defined in Futhark.Analysis.AccessPattern Methods (==) :: VarType -> VarType -> Bool Source # (/=) :: VarType -> VarType -> Bool Source #
Pretty VarType Source # |
Instance details Defined in Futhark.Analysis.AccessPattern Methods pretty :: VarType -> Doc ann Source # prettyList :: [VarType] -> Doc ann Source #

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 Source # show :: Dependency -> String Source # showList :: [Dependency] -> ShowS Source #
Eq Dependency Source # |
Instance details Defined in Futhark.Analysis.AccessPattern Methods (==) :: Dependency -> Dependency -> Bool Source # (/=) :: Dependency -> Dependency -> Bool Source #