From b6720c744c642048f93e04a3a2d4b6895d8b2c83 Mon Sep 17 00:00:00 2001
From: tomsmeding <tom.smeding@gmail.com>
Date: Sun, 28 Apr 2019 17:56:08 +0200
Subject: WIP dataflow analysis for lifetime analysis

---
 DataFlow.hs | 38 ++++++++++++++++++++++++++++++++++++++
 1 file changed, 38 insertions(+)
 create mode 100644 DataFlow.hs

(limited to 'DataFlow.hs')

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]
-- 
cgit v1.2.3-70-g09d2