diff options
Diffstat (limited to 'DataFlow.hs')
-rw-r--r-- | DataFlow.hs | 38 |
1 files changed, 38 insertions, 0 deletions
diff --git a/DataFlow.hs b/DataFlow.hs new file mode 100644 index 0000000..78ec018 --- /dev/null +++ b/DataFlow.hs @@ -0,0 +1,38 @@ +module DataFlow(dataFlowAnalysis, Direction(..)) where + +import Data.Function +import Data.List +import qualified Data.Map.Strict as Map + + +data Direction = Forwards | Backwards + deriving (Show, Eq) + +dataFlowAnalysis + :: Ord id + -- | The direction of the dataflow analysis + => Direction + -- | The control flow graph of basic blocks + -> Map.Map id [id] + -- | The initial values + -> (id -> state) + -- | The transfer function; note that the meaning of the states + -- depends on the direction + -> (state -> id -> state) + -- | For each block, the incoming state and the outgoing state + -> Map.Map id (state, state) +dataFlowAnalysis Backwards cfg initF transF = + Map.map (\(a, b) -> (b, a)) $ + dataFlowAnalysis Forwards (reverseGraph cfg) initF transF +dataFlowAnalysis Forwards cfg initF transF = undefined + + +reverseGraph :: Ord a => Map.Map a [a] -> Map.Map a [a] +reverseGraph graph = + Map.fromList + . map ((,) <$> (fst . head) <*> map snd) + . groupBy ((==) `on` fst) + . sortBy (compare `on` fst) + $ [(to, from) + | (from, tos) <- Map.assocs graph + , to <- tos] |