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

Safe Haskell | None
Language | GHC2021

Futhark.Analysis.DataDependencies

Description

Facilities for inspecting the data dependencies of a program.

Synopsis

- type Dependencies = Map VName Names
- dataDependencies :: ASTRep rep => Body rep -> Dependencies
- depsOf :: Dependencies -> SubExp -> Names
- depsOf' :: SubExp -> Names
- depsOfArrays :: SubExp -> [VName] -> [Names]
- depsOfShape :: Shape -> Names
- lambdaDependencies :: ASTRep rep => Dependencies -> Lambda rep -> [Names] -> [Names]
- reductionDependencies :: ASTRep rep => Dependencies -> Lambda rep -> [SubExp] -> [Names] -> [Names]
- findNecessaryForReturned :: (Param dec -> Bool) -> [(Param dec, SubExp)] -> Map VName Names -> Names

# Documentation

type Dependencies = Map VName Names Source #

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 :: ASTRep rep => Body rep -> Dependencies Source #

Compute the data dependencies for an entire body.

depsOf :: Dependencies -> SubExp -> Names Source #

depsOf' :: SubExp -> Names Source #

depsOfArrays :: SubExp -> [VName] -> [Names] Source #

depsOfShape :: Shape -> Names Source #

lambdaDependencies :: ASTRep rep => Dependencies -> Lambda rep -> [Names] -> [Names] Source #

Determine the variables on which the results of applying anonymous function `lam` to `inputs` depend.

reductionDependencies :: ASTRep rep => Dependencies -> Lambda rep -> [SubExp] -> [Names] -> [Names] Source #

Like `lambdaDependencies`, but `lam` is a binary operation with a neutral element.

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

`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.