diff options
| -rw-r--r-- | compiler/cmm/Dataflow.hs | 10 |
1 files changed, 6 insertions, 4 deletions
diff --git a/compiler/cmm/Dataflow.hs b/compiler/cmm/Dataflow.hs index 7f9d0dc202..0b84016a0f 100644 --- a/compiler/cmm/Dataflow.hs +++ b/compiler/cmm/Dataflow.hs @@ -5,10 +5,7 @@ module Dataflow ( -------------------------------------------------------------------------------- -- Solve a fixed-point of a dataflow problem. --- O(N+H*E) calls to update where --- N = number of nodes, --- E = number of edges, --- H = maximum height of the lattice for any particular node. +-- -- dependants: map from nodes to those who's value depend on the argument node -- update: -- Given the node which needs to be updated, and @@ -21,6 +18,11 @@ module Dataflow ( -- state: some sort of state (usually a map) -- containing the initial value for each node -- +-- Complexity: O(N+H*E) calls to 'update' where +-- N = number of nodes, +-- E = number of edges, +-- H = maximum height of the lattice for any particular node. +-- -- Sketch for proof of complexity: -- Note that the state is threaded through the entire execution. -- Also note that the height of the latice at any particular node |