| |||||||||||||||||||

| |||||||||||||||||||

Description | |||||||||||||||||||

A graph representation of core programs. A graph is a flat structure that can be viewed as a program with a global scope. For example, the Haskell program main x = f 1 where f y = g 2 where g z = x + z might be represented by the following flat graph: graph = Graph { graphNodes = [ Node { nodeId = 0 , function = Input , input = Tup [] , inputType = Tup [] , outputType = intType } , Node { nodeId = 1 , function = Input , input = Tup [] , inputType = Tup [] , outputType = intType } , Node { nodeId = 2 , function = Input , input = Tup [] , inputType = Tup [] , outputType = intType } , Node { nodeId = 3 , function = Function "(+)" , input = Tup [One (Variable (0,[])), One (Variable (2,[]))] , inputType = intPairType , outputType = intType } , Node { nodeId = 4 , function = NoInline "f" (Interface 1 (One (Variable (5,[]))) intType intType) , input = One (Constant (IntData 1)) , inputType = intType , outputType = intType } , Node { nodeId = 5 , function = NoInline "g" (Interface 2 (One (Variable (3,[]))) intType intType) , input = One (Constant (IntData 2)) , inputType = intType , outputType = intType } ] , graphInterface = Interface { interfaceInput = 0 , interfaceOutput = One (Variable (4,[])) , interfaceInputType = intType , interfaceOutputType = intType } } where intType = result (typeOf :: Res [[[Int]]] (Tuple StorableType)) intPairType = result (typeOf :: Res (Int,Int) (Tuple StorableType)) XXX Check above code again which corresponds to the following flat program main v0 = v4 f v1 = v5 g v2 = v3 v3 = v0 + v2 v4 = f 1 v5 = g 2 There are a few assumptions on graphs: - All nodes have unique identifiers.
- There are no cycles.
- The
`input`and`inputType`tuples of each node should have the same shape. - Each
`interfaceInput`(including the top-level one) refers to an`Input`node not referred to by any other interface. - All
`Variable`references are valid (i.e. refer only to those variables implicitly defined by each node). - There should not be any cycles in the constraints introduced by
`findLocalities`. (XXX Is this even possible?) - Sub-function interfaces should be "consistent" with the input/output type of the node. For example, the body of a while loop should have the same type as the whole loop.
In the original program,
- Nodes that have associated interfaces (
`NoInline`,`IfThenElse`,`While`and`Parallel`) are said to contain*sub-functions*. These nodes are called*super nodes*. In the above program, the super node`v4`contains the sub-function`f`, and`v5`contains the sub-function`g`. - A definition
`d`is*local*to a definition`e`iff.`d`is placed somewhere within the definition of`e`(i.e. inside an arbitrarily deeply nested`where`clause). - A definition
`d`is*owned*by a definition`e`iff.`d`is placed immediately under the top-most`where`clause of`e`. A definition may have at most one owner.
The definition hierarchy thus specifies ownership between the definitions in the program. There are two types of ownership: - A super node is always the owner of its sub-functions.
- A sub-function may be the owner of some node definitions.
Assigning nodes to sub-functions in a useful way takes some work. It is done by first finding out for each node which sub-functions it must be local to. Each locality constraint gives an upper bound on where in the definition hierarchy the node may be placed. There is one principle for introducing a locality constraint: - If node
`v`depends on the input of sub-function`f`, then`v`must be local to`f`.
The locality constraints for a graph can thus be found be tracing each
sub-function input in order to find the nodes that depend on it (see function
main v0 = v4 where v4 = f 1 where f v1 = v5 v5 = g 2 where g v2 = v3 where v3 = v0 + v2 which is syntactically valid Haskell. Note that this program is slightly
different from the original which defined There is one caveat with the above method. Consider the following flat program: main v0 = v4 f v1 = v5 g v2 = v3 v3 = v1 + 2 v4 = f 0 v5 = g 1 Here, we get the locality constraint: | |||||||||||||||||||

Synopsis | |||||||||||||||||||

Documentation | |||||||||||||||||||

| |||||||||||||||||||

Node identifier | |||||||||||||||||||

| |||||||||||||||||||

Variable represented by a node id and a tuple path. For example, in a definition (given in Haskell syntax) ((a,b),c) = f x the variable | |||||||||||||||||||

| |||||||||||||||||||

| |||||||||||||||||||

| |||||||||||||||||||

| |||||||||||||||||||

| |||||||||||||||||||

| |||||||||||||||||||

| |||||||||||||||||||

| |||||||||||||||||||

| |||||||||||||||||||

| |||||||||||||||||||

| |||||||||||||||||||

| |||||||||||||||||||

| |||||||||||||||||||

| |||||||||||||||||||

| |||||||||||||||||||

A node that contains a sub-function | |||||||||||||||||||

| |||||||||||||||||||

| |||||||||||||||||||

| |||||||||||||||||||

| |||||||||||||||||||

| |||||||||||||||||||

Returns the nodes in a source tuple. | |||||||||||||||||||

| |||||||||||||||||||

The fanout of each node in a graph. Nodes that are not in the map are assumed to have no fanout. | |||||||||||||||||||

| |||||||||||||||||||

Look up a node in the graph | |||||||||||||||||||

| |||||||||||||||||||

Lists all sub-functions in the graph. | |||||||||||||||||||

| |||||||||||||||||||

Lists all locality constraints of the graph. | |||||||||||||||||||

| |||||||||||||||||||

Returns a total ordering between all super nodes in a graph, such that if
node v is local to sub-function f, then v maps to a lower number than
the owner of f. The converse is not necessarily true. The second argument
gives the locality constraints for each node in the graph (top-level nodes
may be left undefined).
| |||||||||||||||||||

| |||||||||||||||||||

Returns the minimal sub-function according to the given owner ordering. | |||||||||||||||||||

| |||||||||||||||||||

Sorts the nodes by their id. | |||||||||||||||||||

| |||||||||||||||||||

Makes a hierarchical graph from a flat one. The node lists in the hierarchy are always sorted according to node id. | |||||||||||||||||||

| |||||||||||||||||||

| |||||||||||||||||||

| |||||||||||||||||||

Produced by Haddock version 2.6.1 |