compiler/cmm/Dataflow.hs

   1 module Dataflow (
   2         fixedpoint
   3   ) where
   4
   5 -----------------------------------------------------------------------------
   6 -- | Solve the fixed-point of a dataflow problem.
   7 --
   8 -- Complexity: O(N+H*E) calls to 'update' where
   9 --   N = number of nodes,
  10 --   E = number of edges,
  11 --   H = maximum height of the lattice for any particular node.
  12 --
  13 -- Sketch for proof of complexity:
  14 -- Note that the state is threaded through the entire execution.
  15 -- Also note that the height of the latice at any particular node
  16 -- is the number of times 'update' can return non-Nothing for a
  17 -- particular node.  Every call (except for the top level one)
  18 -- must be caused by a non-Nothing result and each non-Nothing
  19 -- result causes as many calls as it has out-going edges.
  20 -- Thus any particular node, n, may cause in total at
  21 -- most H*out(n) further calls.  When summed over all nodes,
  22 -- that is H*E.  The N term of the complexity is from the initial call
  23 -- when 'update' will be passed 'Nothing'.
  24 fixedpoint ::
  25     (node -> [node])            -- ^ map from nodes to those who's
  26                                 -- value depend on the argument node
  27     -> (node -> Maybe node -> s -> Maybe s)
  28                                 -- ^ Given the node which needs to be
  29                                 -- updated, and which node caused that node
  30                                 -- to need to be updated, update the state.
  31                                 --
  32                                 -- The causing node will be 'Nothing' if
  33                                 -- this is the initial/bootstrapping update.
  34                                 --
  35                                 -- Must return 'Nothing' if no change,
  36                                 -- otherwise returrn 'Just' of the new state.
  37
  38     -> [node]                   -- ^ Nodes that should initially be updated
  39
  40     -> s                        -- ^ Initial state
  41                                 -- (usually a map from node to
  42                                 -- the value for that node)
  43
  44     -> s                        -- ^ Final state
  45 fixedpoint dependants update nodes state =
  46     foldr (fixedpoint' Nothing) state nodes where
  47         -- Use a depth first traversal of nodes based on the update graph.
  48         -- Terminate the traversal when the update doesn't change anything.
  49         fixedpoint' cause node state =
  50             case update node cause state of
  51               Nothing -> state
  52               Just state' ->
  53                   foldr (fixedpoint' (Just node)) state' (dependants node)