Merge in new code generator branch.

[ghc-hetmet.git] / compiler / cmm / Dataflow.hs

diff --git a/compiler/cmm/Dataflow.hs b/compiler/cmm/Dataflow.hs
deleted file mode 100644 (file)
index fc1b576..0000000
--- a/compiler/cmm/Dataflow.hs
+++ /dev/null
@@ -1,55 +0,0 @@
-{-# OPTIONS -Wall -fno-warn-name-shadowing #-}
-
-module Dataflow (
-        fixedpoint
-  ) where
-
------------------------------------------------------------------------------
--- | Solve the fixed-point of a dataflow problem.
---
--- Complexity: O(N+H*E) calls to the update function 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
--- is the number of times 'update' can return non-Nothing for a
--- particular node.  Every call (except for the top level one)
--- must be caused by a non-Nothing result and each non-Nothing
--- result causes as many calls as it has out-going edges.
--- Thus any particular node, n, may cause in total at
--- most H*out(n) further calls.  When summed over all nodes,
--- that is H*E.  The N term of the complexity is from the initial call
--- when 'update' will be passed 'Nothing'.
-fixedpoint ::
-    (node -> [node])            -- map from nodes to those who's
-                                -- value depend on the argument node
-    -> (node -> Maybe node -> s -> Maybe s)
-                                -- Given the node which needs to be
-                                -- updated, and which node caused that node
-                                -- to need to be updated, update the state.
-                                --
-                                -- The causing node will be 'Nothing' if
-                                -- this is the initial/bootstrapping update.
-                                --
-                                -- Must return 'Nothing' if no change,
-                                -- otherwise returrn 'Just' of the new state.
-
-    -> [node]                   -- Nodes that should initially be updated
-
-    -> s                        -- Initial state
-                                -- (usually a map from node to
-                                -- the value for that node)
-
-    -> s                        -- Final state
-fixedpoint dependants update nodes state =
-    foldr (fixedpoint' Nothing) state nodes where
-        -- Use a depth first traversal of nodes based on the update graph.
-        -- Terminate the traversal when the update doesn't change anything.
-        fixedpoint' cause node state =
-            case update node cause state of
-              Nothing -> state
-              Just state' ->
-                  foldr (fixedpoint' (Just node)) state' (dependants node)