compiler/cmm/Dataflow.hs

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