compiler/cmm/Dataflow.hs

   1 module Dataflow (
   2         fixedpoint
   3   ) where
   4
   5 --------------------------------------------------------------------------------
   6
   7 -- Solve a fixed-point of a dataflow problem.
   8 -- 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 -- dependants: map from nodes to those who's value depend on the argument node
  13 -- update:
  14 --   Given the node which needs to be updated, and
  15 --   which node caused that node to need to be updated,
  16 --   update the state.
  17 --   (The causing node will be 'Nothing' if this is the initial update.)
  18 --   Must return 'Nothing' if no change,
  19 --   otherwise returrn 'Just' of the new state
  20 -- nodes: a set of nodes that initially need updating
  21 -- state: some sort of state (usually a map)
  22 --        containing the initial value for each node
  23 --
  24 -- Sketch for proof of complexity:
  25 -- Note that the state is threaded through the entire execution.
  26 -- Also note that the height of the latice at any particular node
  27 -- is the number of times 'update' can return non-Nothing for a particular node.
  28 -- Every call (except for the top level one) must be caused by a non-Nothing
  29 -- result and each non-Nothing result causes as many calls as it has
  30 -- out-going edges.  Thus any particular node, n, may cause in total
  31 -- at most H*out(n) further calls.  When summed over all nodes,
  32 -- that is H*E.  The N term of the complexity is from the initial call
  33 -- when 'update' will be passed 'Nothing'.
  34 fixedpoint ::
  35     (node -> [node])
  36     -> (node -> Maybe node -> s -> Maybe s)
  37     -> [node] -> s -> s
  38 fixedpoint dependants update nodes state =
  39     foldr (fixedpoint' Nothing) state nodes where
  40         fixedpoint' cause node state =
  41             case update node cause state of
  42               Nothing -> state
  43               Just state' ->
  44                   foldr (fixedpoint' (Just node)) state' (dependants node)