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

Safe Haskell | Safe-Inferred
Language | GHC2021

Futhark.Optimise.ArrayShortCircuiting.TopdownAnalysis

Synopsis

- data TopdownEnv rep = TopdownEnv {
  - alloc :: AllocTab
  - scope :: ScopeTab rep
  - inhibited :: InhibitTab
  - v_alias :: VarAliasTab
  - m_alias :: MemAliasTab
  - nonNegatives :: Names
  - scalarTable :: Map VName (PrimExp VName)
  - knownLessThan :: [(VName, PrimExp VName)]
  - td_asserts :: [SubExp]
  }
- type ScopeTab rep = Scope (Aliases rep)
- class TopDownHelper inner
- type InhibitTab = Map VName Names
- updateTopdownEnv :: (ASTRep rep, Op rep ~ MemOp inner rep, TopDownHelper (inner (Aliases rep))) => TopdownEnv rep -> Stm (Aliases rep) -> TopdownEnv rep
- updateTopdownEnvLoop :: TopdownEnv rep -> [(FParam rep, SubExp)] -> LoopForm -> TopdownEnv rep
- getDirAliasedIxfn :: HasMemBlock (Aliases rep) => TopdownEnv rep -> CoalsTab -> VName -> Maybe (VName, VName, LMAD)
- getDirAliasedIxfn' :: HasMemBlock (Aliases rep) => TopdownEnv rep -> CoalsTab -> VName -> Maybe (VName, VName, LMAD)
- addInvAliasesVarTab :: HasMemBlock (Aliases rep) => TopdownEnv rep -> Map VName Coalesced -> VName -> Maybe (Map VName Coalesced)
- areAnyAliased :: TopdownEnv rep -> VName -> [VName] -> Bool
- isInScope :: TopdownEnv rep -> VName -> Bool
- nonNegativesInPat :: Typed rep => Pat rep -> Names

# Documentation

data TopdownEnv rep Source #

Constructors

TopdownEnv |

Fields

- alloc :: AllocTab

  contains the already allocated memory blocks

- scope :: ScopeTab rep

  variable info, including var-to-memblock assocs

- inhibited :: InhibitTab

  the inherited inhibitions from the previous try

- v_alias :: VarAliasTab

  for statements such as transpose, reshape, index, etc., that alias an array variable: maps var-names to pair of aliased var name and index function transformation. For example, for `let b = a[slc]` it should add the binding `b |-> (a, `slice` slc )`

- m_alias :: MemAliasTab

  keeps track of memory block aliasing. this needs to be implemented

- nonNegatives :: Names

  Contains symbol information about the variables in the program. Used to determine if a variable is non-negative.

- scalarTable :: Map VName (PrimExp VName)
- knownLessThan :: [(VName, PrimExp VName)]

  A list of known relations of the form `VName` `<` `BasicOp`, typically gotten from `LoopForm` and `SegSpace`.

- td_asserts :: [SubExp]

  A list of the asserts encountered so far

type ScopeTab rep = Scope (Aliases rep) Source #

maps array-variable names to various info, including types, memory block and index function, etc.

class TopDownHelper inner Source #

Minimal complete definition

innerNonNegatives, innerKnownLessThan, scopeHelper

#### Instances

Instances details

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
TopDownHelper (NoOp rep) Source # |
Instance details Defined in Futhark.Optimise.ArrayShortCircuiting.TopdownAnalysis Methods innerNonNegatives :: [VName] -> NoOp rep -> Names innerKnownLessThan :: NoOp rep -> [(VName, PrimExp VName)] scopeHelper :: NoOp rep -> Scope rep0
TopDownHelper (SegOp lvl rep) Source # |
Instance details Defined in Futhark.Optimise.ArrayShortCircuiting.TopdownAnalysis Methods innerNonNegatives :: [VName] -> SegOp lvl rep -> Names innerKnownLessThan :: SegOp lvl rep -> [(VName, PrimExp VName)] scopeHelper :: SegOp lvl rep -> Scope rep0

type InhibitTab = Map VName Names Source #

inhibited memory-block mergings from the key (memory block) to the value (set of memory blocks).

updateTopdownEnv :: (ASTRep rep, Op rep ~ MemOp inner rep, TopDownHelper (inner (Aliases rep))) => TopdownEnv rep -> Stm (Aliases rep) -> TopdownEnv rep Source #

fills in the TopdownEnv table

updateTopdownEnvLoop :: TopdownEnv rep -> [(FParam rep, SubExp)] -> LoopForm -> TopdownEnv rep Source #

The topdown handler for loops.

getDirAliasedIxfn :: HasMemBlock (Aliases rep) => TopdownEnv rep -> CoalsTab -> VName -> Maybe (VName, VName, LMAD) Source #

Get direct aliased index function. Returns a triple of current memory block to be coalesced, the destination memory block and the index function of the access in the space of the destination block.

getDirAliasedIxfn' :: HasMemBlock (Aliases rep) => TopdownEnv rep -> CoalsTab -> VName -> Maybe (VName, VName, LMAD) Source #

Like `getDirAliasedIxfn`, but this version returns `Nothing` if the value is not currently subject to coalescing.

addInvAliasesVarTab :: HasMemBlock (Aliases rep) => TopdownEnv rep -> Map VName Coalesced -> VName -> Maybe (Map VName Coalesced) Source #

We assume `x` is in `vartab` and we add the variables that `x` aliases for as long as possible following a chain of direct-aliasing operators, i.e., without considering aliasing of if-then-else, loops, etc. For example: `x0 = if c then ... else ...` `x1 = rearrange r1 x0` `x2 = reverse x1` `y[slc] = x2` We assume `vartab` constains a binding for `x2`, and calling this function with `x2` as argument should also insert entries for `x1` and `x0` to `vartab`, of course if their aliasing operations are invertible. We assume inverting aliases has been performed by the top-down pass.

areAnyAliased :: TopdownEnv rep -> VName -> [VName] -> Bool Source #

isInScope :: TopdownEnv rep -> VName -> Bool Source #

nonNegativesInPat :: Typed rep => Pat rep -> Names Source #