Futhark.Optimise.ArrayShortCircuiting.MemRefAggreg

Documentation

recordMemRefUses :: (CanBeAliased (Op rep), RepTypes rep, Op rep ~ MemOp inner, HasMemBlock (Aliases rep)) => TopdownEnv rep -> BotUpEnv -> Stm (Aliases rep) -> (CoalsTab, InhibitTab)

This function: 1. computes the written and read memory references for the current statement (by calling getUseSumFromStm) 2. fails the entries in active coalesced table for which the write set overlaps the uses of the destination (to that point)

freeVarSubstitutions :: FreeIn a => ScopeTab rep -> ScalarTab -> a -> Maybe FreeVarSubsts

Checks whether the index function can be translated at the current program point and also returns the substitutions. It comes down to answering the question: "can one perform enough substitutions (from the bottom-up scalar table) until all vars appearing in the index function are defined in the current scope?"

translateAccessSummary :: ScopeTab rep -> ScalarTab -> AccessSummary -> AccessSummary

Translates free variables in an access summary

aggSummaryLoopTotal :: MonadFreshNames m => ScopeTab rep -> ScopeTab rep -> ScalarTab -> Maybe (VName, (TPrimExp Int64 VName, TPrimExp Int64 VName)) -> AccessSummary -> m AccessSummary

Computes the total aggregated access summary for a loop by expanding the access summary given according to the iterator variable and bounds of the loop.

Corresponds to:

\[ \bigcup_{j=0}^{j<n} Access_j \]

aggSummaryLoopPartial :: MonadFreshNames m => ScalarTab -> Maybe (VName, (TPrimExp Int64 VName, TPrimExp Int64 VName)) -> AccessSummary -> m AccessSummary

For a given iteration of the loop $i$, computes the aggregated loop access summary of all later iterations.

Corresponds to:

\[ \bigcup_{j=i+1}^{j<n} Access_j \]

aggSummaryMapPartial :: MonadFreshNames m => ScalarTab -> [(VName, SubExp)] -> LmadRef -> m AccessSummary

For a given map with $k$ dimensions and an index $i$ for each dimension, compute the aggregated access summary of all other threads.

For the innermost dimension, this corresponds to

\[ \bigcup_{j=0}^{j<i} Access_j \cup \bigcup_{j=i+1}^{j<n} Access_j \]

where $Access_j$ describes the point accesses in the map. As we move up in dimensionality, the previous access summaries are kept, in addition to the total aggregation of the inner dimensions. For outer dimensions, the equation is the same, the point accesses in $Access_j$ are replaced with the total aggregation of the inner dimensions.

aggSummaryMapTotal :: MonadFreshNames m => ScalarTab -> [(VName, SubExp)] -> AccessSummary -> m AccessSummary

Computes to total access summary over a multi-dimensional map.

noMemOverlap :: (CanBeAliased (Op rep), RepTypes rep) => TopdownEnv rep -> AccessSummary -> AccessSummary -> Bool

Check for memory overlap of two access summaries.

This check is conservative, so unless we can guarantee that there is no overlap, we return False.