WIP dataflow analysis for lifetime analysis

2 files changed, 39 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]
diff --git a/lisphs.cabal b/lisphs.cabal
index c608571..66dc3c8 100644
--- a/lisphs.cabal
+++ b/lisphs.cabal
@@ -16,6 +16,7 @@ executable            lisp
     other-modules:
         AST
         Compiler
+        DataFlow
         Intermediate
         Lower
         Optimiser