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/trunk/src/MLRISC/IR/dataflow.sml
ViewVC logotype

Annotation of /sml/trunk/src/MLRISC/IR/dataflow.sml

Parent Directory Parent Directory | Revision Log Revision Log


Revision 245 - (view) (download)
Original Path: sml/branches/SMLNJ/src/MLRISC/IR/dataflow.sml

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

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