From 77cc133da7af6961add020cab1ba9eadee3a0b67 Mon Sep 17 00:00:00 2001 From: "Michael D. Adams" Date: Tue, 22 May 2007 13:53:05 +0000 Subject: [PATCH] A small move of the comments in ./compiler/cmm/Dataflow.hs --- compiler/cmm/Dataflow.hs | 10 ++++++---- 1 file changed, 6 insertions(+), 4 deletions(-) diff --git a/compiler/cmm/Dataflow.hs b/compiler/cmm/Dataflow.hs index 7f9d0dc..0b84016 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 -- 1.7.10.4