Futhark.Optimise.ArrayShortCircuiting.TopdownAnalysis

Documentation

data TopdownEnv rep

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)

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

class TopDownHelper inner

Minimal complete definition

innerNonNegatives, innerKnownLessThan, scopeHelper

Instances

TopDownHelper (HostOp (NoOp :: Type -> Type) (Aliases GPUMem))

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))

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)

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)

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

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

fills in the TopdownEnv table

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

The topdown handler for loops.

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

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)

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)

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

isInScope :: TopdownEnv rep -> VName -> Bool

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