Futhark.Analysis.DataDependencies

Facilities for inspecting the data dependencies of a program.

Documentation

type Dependencies = Map VName Names

A mapping from a variable name v, to those variables on which the value of v is dependent. The intuition is that we could remove all other variables, and v would still be computable. This also includes names bound in loops or by lambdas.

dataDependencies :: ASTLore lore => Body lore -> Dependencies

Compute the data dependencies for an entire body.

findNecessaryForReturned :: (Param dec -> Bool) -> [(Param dec, SubExp)] -> Map VName Names -> Names

findNecessaryForReturned p merge deps computes which of the loop parameters (merge) are necessary for the result of the loop, where p given a loop parameter indicates whether the final value of that parameter is live after the loop. deps is the data dependencies of the loop body. This is computed by straightforward fixpoint iteration.