blob: 78ec01819bd4f571e6987a133e1df2326b3f36d3 (
plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
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]
|
