Futhark.Optimise.ArrayShortCircuiting.DataStructs

Documentation

data Coalesced

Coalesced Access Entry

Constructors

Coalesced

Fields

• CoalescedKind

  the kind of coalescing

• ArrayMemBound

  destination mem_block info f_m_x[i] (must be ArrayMem) (Maybe IxFun) -- the inverse ixfun of a coalesced array, such that -- ixfuns can be correctly constructed for aliases;

• FreeVarSubsts

  substitutions for free vars in index function

Instances

Pretty Coalesced

Defined in Futhark.Optimise.ArrayShortCircuiting.DataStructs

Methods

pretty :: Coalesced -> Doc ann

prettyList :: [Coalesced] -> Doc ann

data CoalescedKind

Constructors

CopyCoal

let x = copy b^{lu}

InPlaceCoal

let x[i] = b^{lu}

ConcatCoal

let x = concat(a, b^{lu})

TransitiveCoal

transitive, i.e., other variables aliased with b.

MapCoal

Instances

Pretty CoalescedKind

Defined in Futhark.Optimise.ArrayShortCircuiting.DataStructs

Methods

pretty :: CoalescedKind -> Doc ann

prettyList :: [CoalescedKind] -> Doc ann

data ArrayMemBound

Information about a memory block: type, shape, name and ixfun.

Constructors

MemBlock

Fields

• primType :: PrimType
• shape :: Shape
• memName :: VName
• ixfun :: LMAD

Instances

Pretty ArrayMemBound

Defined in Futhark.Optimise.ArrayShortCircuiting.DataStructs

Methods

pretty :: ArrayMemBound -> Doc ann

prettyList :: [ArrayMemBound] -> Doc ann

type AllocTab = Map VName Space

the allocatted memory blocks

class HasMemBlock rep

Minimal complete definition

getScopeMemInfo

Instances

HasMemBlock (Aliases GPUMem)

Defined in Futhark.Optimise.ArrayShortCircuiting.DataStructs

Methods

getScopeMemInfo :: VName -> Scope (Aliases GPUMem) -> Maybe ArrayMemBound

HasMemBlock (Aliases MCMem)

Defined in Futhark.Optimise.ArrayShortCircuiting.DataStructs

Methods

getScopeMemInfo :: VName -> Scope (Aliases MCMem) -> Maybe ArrayMemBound

HasMemBlock (Aliases SeqMem)

Defined in Futhark.Optimise.ArrayShortCircuiting.DataStructs

Methods

getScopeMemInfo :: VName -> Scope (Aliases SeqMem) -> Maybe ArrayMemBound

type ScalarTab = Map VName (PrimExp VName)

maps a variable name to its PrimExp scalar expression

type CoalsTab = Map VName CoalsEntry

maps a memory-block name to a CoalsEntry. Among other things, it contains vartab, a map in which each variable associated to that memory block is bound to its Coalesced info.

type ScopeTab rep = Scope (Aliases rep)

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

data CoalsEntry

Constructors

CoalsEntry

Fields

• dstmem :: VName

  destination memory block

• dstind :: LMAD

  index function of the destination (used for rebasing)

• alsmem :: Names

  aliased destination memory blocks can appear due to repeated (optimistic) coalescing.

• vartab :: Map VName Coalesced

  per variable-name coalesced entries

• optdeps :: Map VName VName

  keys are variable names, values are memblock names; it records optimistically added coalesced nodes, e.g., in the case of if-then-else expressions. For example: x = map f a .. use of y .. b = map g a x[i] = b y[k] = x the coalescing of b in x[i] succeeds, but is dependent of the success of the coalescing of x in y[k], which fails in this case because y is used before the new array creation of x = map f. Hence optdeps of the m_b CoalsEntry records x -> m_x and at the end of analysis it is removed from the successfully coalesced table if m_x is unsuccessful. Storing m_x would probably be sufficient if memory would not be reused--e.g., by register allocation on arrays--the x discriminates between memory being reused across semantically different arrays (searched in vartab field).

• memrefs :: MemRefs

  Access summaries of uses and writes of destination and source respectively.

• certs :: Certs

  Certificates of the destination, which must be propagated to the source. When short-circuiting reaches the array creation point, we must check whether the certs are in scope for short-circuiting to succeed.

Instances

Pretty CoalsEntry

Defined in Futhark.Optimise.ArrayShortCircuiting.DataStructs

Methods

pretty :: CoalsEntry -> Doc ann

prettyList :: [CoalsEntry] -> Doc ann

Pretty CoalsTab

Defined in Futhark.Optimise.ArrayShortCircuiting.DataStructs

Methods

pretty :: CoalsTab -> Doc ann

prettyList :: [CoalsTab] -> Doc ann

type FreeVarSubsts = Map VName (TPrimExp Int64 VName)

Free variable substitutions

type LmadRef = LMAD (TPrimExp Int64 VName)

An LMAD specialized to TPrimExps (a typed primexp)

data MemRefs

Constructors

MemRefs

Fields

• dstrefs :: AccessSummary

  The access summary of all references (reads and writes) to the destination of a coalescing entry

• srcwrts :: AccessSummary

  The access summary of all writes to the source of a coalescing entry

Instances

Monoid MemRefs

Defined in Futhark.Optimise.ArrayShortCircuiting.DataStructs

Methods

mempty :: MemRefs

mappend :: MemRefs -> MemRefs -> MemRefs

mconcat :: [MemRefs] -> MemRefs

Semigroup MemRefs

Defined in Futhark.Optimise.ArrayShortCircuiting.DataStructs

Methods

(<>) :: MemRefs -> MemRefs -> MemRefs

sconcat :: NonEmpty MemRefs -> MemRefs

stimes :: Integral b => b -> MemRefs -> MemRefs

Pretty MemRefs

Defined in Futhark.Optimise.ArrayShortCircuiting.DataStructs

Methods

pretty :: MemRefs -> Doc ann

prettyList :: [MemRefs] -> Doc ann

data AccessSummary

Summary of all memory accesses at a given point in the code

Constructors

Undeterminable

The access summary was statically undeterminable, for instance by having multiple lmads. In this case, we should conservatively avoid all coalescing.

Set (Set LmadRef)

A conservative estimate of the set of accesses up until this point.

Instances

Monoid AccessSummary

Defined in Futhark.Optimise.ArrayShortCircuiting.DataStructs

Methods

mempty :: AccessSummary

mappend :: AccessSummary -> AccessSummary -> AccessSummary

mconcat :: [AccessSummary] -> AccessSummary

Semigroup AccessSummary

Defined in Futhark.Optimise.ArrayShortCircuiting.DataStructs

Methods

(<>) :: AccessSummary -> AccessSummary -> AccessSummary

sconcat :: NonEmpty AccessSummary -> AccessSummary

stimes :: Integral b => b -> AccessSummary -> AccessSummary

FreeIn AccessSummary

Defined in Futhark.Optimise.ArrayShortCircuiting.DataStructs

Methods

freeIn' :: AccessSummary -> FV

Pretty AccessSummary

Defined in Futhark.Optimise.ArrayShortCircuiting.DataStructs

Methods

pretty :: AccessSummary -> Doc ann

prettyList :: [AccessSummary] -> Doc ann

data BotUpEnv

Constructors

BotUpEnv

Fields

• scals :: ScalarTab

  maps scalar variables to theirs PrimExp expansion

• activeCoals :: CoalsTab

  Optimistic coalescing info. We are currently trying to coalesce these memory blocks.

• successCoals :: CoalsTab

  Committed (successfull) coalescing info. These memory blocks have been successfully coalesced.

• inhibit :: InhibitTab

  The coalescing failures from this pass. We will no longer try to merge these memory blocks.

type InhibitTab = Map VName Names

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

unionCoalsEntry :: CoalsEntry -> CoalsEntry -> CoalsEntry

Compute the union of two CoalsEntry. If two CoalsEntry do not refer to the same destination memory and use the same index function, the first CoalsEntry is returned.

vnameToPrimExp :: AliasableRep rep => ScopeTab rep -> ScalarTab -> VName -> Maybe (PrimExp VName)

Attempt to convert a VName to a PrimExp.

First look in ScalarTab to see if we have recorded the scalar value of the argument. Otherwise look up the type of the argument and return a LeafExp if it is a PrimType.

getArrMemAssocFParam :: [Param FParamMem] -> [(VName, Uniqueness, ArrayMemBound)]

Get the names of arrays in a list of FParam and the corresponding ArrayMemBound information for each array.

getScopeMemInfo :: HasMemBlock rep => VName -> Scope rep -> Maybe ArrayMemBound

Looks up VName in the given scope. If it is a MemArray, return the ArrayMemBound information for the array.

createsNewArrOK :: Exp rep -> Bool

True if the expression returns a "fresh" array.

getArrMemAssoc :: Pat (aliases, LetDecMem) -> [(VName, ArrayMemBound)]

Get the names of array PatElems in a Pat and the corresponding ArrayMemBound information for each array.

getUniqueMemFParam :: [Param FParamMem] -> Map VName Space

Get memory blocks in a list of FParam that are used for unique arrays in the same list of FParam.

markFailedCoal :: (CoalsTab, InhibitTab) -> VName -> (CoalsTab, InhibitTab)

Memory-block removal from active-coalescing table should only be handled via this function, it is easy to run into infinite execution problem; i.e., the fix-pointed iteration of coalescing transformation assumes that whenever a coalescing fails it is recorded in the inhibit table.

accessSubtract :: AccessSummary -> AccessSummary -> AccessSummary

markSuccessCoal :: (CoalsTab, CoalsTab) -> VName -> CoalsEntry -> (CoalsTab, CoalsTab)

promotion from active-to-successful coalescing tables should be handled with this function (for clarity).