diff options
| author | Michael D. Adams <t-madams@microsoft.com> | 2007-05-22 13:53:05 +0000 |
|---|---|---|
| committer | Michael D. Adams <t-madams@microsoft.com> | 2007-05-22 13:53:05 +0000 |
| commit | 77cc133da7af6961add020cab1ba9eadee3a0b67 (patch) | |
| tree | 4de68fb979ac0bb445cc09f920b0089130d07dbc /compiler/cmm/Dataflow.hs | |
| parent | 3de1c72b6fdc52cd9c1938f21b8d284cc3cdbbc9 (diff) | |
| download | haskell-77cc133da7af6961add020cab1ba9eadee3a0b67.tar.gz | |
A small move of the comments in ./compiler/cmm/Dataflow.hs
Diffstat (limited to 'compiler/cmm/Dataflow.hs')
| -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 |