Home My Page Projects Code Snippets Project Openings SML/NJ
Summary Activity Forums Tracker Lists Tasks Docs Surveys News SCM Files

SCM Repository

[smlnj] Annotation of /sml/branches/SMLNJ/src/MLRISC/IR/dataflow.sml
ViewVC logotype

Annotation of /sml/branches/SMLNJ/src/MLRISC/IR/dataflow.sml

Parent Directory Parent Directory | Revision Log Revision Log


Revision 411 - (view) (download)

1 : monnier 411 (*
2 :     * This is just a very simple worklist based data analyzer.
3 :     * Parameterized by the dataflow problem.
4 :     *
5 :     * -- Allen
6 :     *)
7 :    
8 : monnier 245 functor DataflowFn(P : DATAFLOW_PROBLEM) : DATAFLOW_ANALYZER =
9 :     struct
10 :     structure G = Graph
11 :     structure A = Array
12 :     structure CFG = P.CFG
13 :    
14 :     type dataflow_info = P.dataflow_info
15 :    
16 :     fun analyze (CFG, info) =
17 : monnier 411 let val G' as G.GRAPH cfg = if P.forward then CFG
18 :     else ReversedGraphView.rev_view CFG
19 : monnier 245 val N = #capacity cfg ()
20 : monnier 411 val ENTRY = case #entries cfg () of
21 :     [ENTRY] => ENTRY
22 :     | _ => raise Graph.NotSingleEntry
23 : monnier 245 val inputs = A.array(N, P.bot)
24 :     val outputs = A.array(N, P.bot)
25 :     val transfers = A.array(N, fn _ => P.bot)
26 :     val prologue = P.prologue(CFG,info)
27 :     val _ = #forall_nodes cfg
28 :     (fn (n,n') =>
29 :     let val {input,output,transfer} = prologue(n,n')
30 :     in A.update(inputs,n,input);
31 :     A.update(outputs,n,output);
32 :     A.update(transfers,n,transfer)
33 :     end
34 :     )
35 :    
36 :     abstype worklist = WL of int list * int list
37 :     with
38 :     exception EmptyQueue
39 :     val on_queue = A.array(N,false)
40 :     val empty = WL([],[])
41 :     val empty = WL([],[])
42 :     fun enque(wl as WL(b,f),i) =
43 :     if A.sub(on_queue,i) then wl else
44 :     (A.update(on_queue,i,true); WL(i::b,f))
45 :     fun deque(WL([],[])) = raise EmptyQueue
46 :     | deque(WL(b,[])) = deque(WL([],rev b))
47 :     | deque(WL(b,i::f)) = (A.update(on_queue,i,false); (WL(b,f),i))
48 :     fun insert(wl,[]) = wl
49 :     | insert(wl,(_,n,_)::es) = insert(enque(wl,n),es)
50 : monnier 411 fun insert'(wl,[]) = wl
51 :     | insert'(wl,n::ns) = insert'(enque(wl,n),ns)
52 : monnier 245 end
53 :    
54 :     fun propagate worklist =
55 :     let val (worklist, i) = deque worklist
56 :     val new_input =
57 :     case #in_edges cfg i of
58 :     [(p,_,_)] => if p = ENTRY then A.sub(inputs,i)
59 :     else A.sub(outputs,p)
60 :     | x => P.join(map (fn(i,_,_) => A.sub(outputs,i)) x)
61 :     val old_output = A.sub(outputs,i)
62 :     val f = A.sub(transfers,i)
63 :     val new_output = f new_input
64 :     in A.update(inputs,i,new_input);
65 :     if P.==(old_output, new_output) then propagate worklist
66 :     else (A.update(outputs,i,new_output);
67 :     propagate(insert(worklist,#out_edges cfg i)))
68 :     end
69 :    
70 : monnier 411 val nodes = GraphTopsort.topsort G' (#entries cfg ())
71 :     val _ = propagate(insert'(empty,nodes)) handle EmptyQueue => ()
72 : monnier 245 val epilogue = P.epilogue(CFG,info)
73 :     val _ = #forall_nodes cfg
74 :     (fn (n,n') => epilogue{input = A.sub(inputs,n),
75 :     output = A.sub(outputs,n),
76 :     node = (n,n')})
77 :     in
78 :     info
79 :     end
80 :    
81 :     end
82 :    

root@smlnj-gforge.cs.uchicago.edu
ViewVC Help
Powered by ViewVC 1.0.0