Home My Page Projects Code Snippets Project Openings diderot
Summary Activity Tracker Tasks SCM

SCM Repository

[diderot] Annotation of /branches/pure-cfg/src/compiler/IL/forward-dfa-fn.sml
ViewVC logotype

Annotation of /branches/pure-cfg/src/compiler/IL/forward-dfa-fn.sml

Parent Directory Parent Directory | Revision Log Revision Log


Revision 508 - (view) (download)

1 : jhr 257 (* forward-dfa-fn.sml
2 :     *
3 : jhr 435 * COPYRIGHT (c) 2010 The Diderot Project (http://diderot-language.cs.uchicago.edu)
4 : jhr 257 * All rights reserved.
5 :     *
6 :     * Forward data-flow analysis for IL code.
7 :     *)
8 :    
9 :     functor ForwardDFAFn (D : DOMAIN) :> sig
10 :    
11 : jhr 417 structure D : DOMAIN = D
12 : jhr 257
13 : jhr 414 (* given the entry value and root statement, do the forward DFA on the CFG and
14 : jhr 508 * return the list of nodes that were analysed.
15 : jhr 414 *)
16 : jhr 488 val analyse : D.t * D.IL.cfg -> D.IL.node list
17 : jhr 257
18 : jhr 414 (* get results for a node *)
19 :     val inValue : D.IL.node -> D.t
20 :     val outValue : D.IL.node -> D.t
21 : jhr 257
22 : jhr 258 (* scrub results to reclaim space *)
23 : jhr 414 val scrub : D.IL.node list -> unit
24 : jhr 257
25 :     end = struct
26 :    
27 :     structure D = D
28 :     structure IL = D.IL
29 :    
30 :     type result = IL.node list
31 :    
32 : jhr 414 val {setFn=setIn, getFn=getIn, clrFn= clrIn, ...} =
33 : jhr 257 PropList.newProp (fn (IL.ND{props, ...}) => props, fn _ => D.bottom)
34 : jhr 414 val {setFn=setOut, getFn=getOut, clrFn=clrOut, ...} =
35 :     PropList.newProp (fn (IL.ND{props, ...}) => props, fn _ => D.bottom)
36 : jhr 257
37 : jhr 414 fun clear node = (clrIn node; clrOut node)
38 :    
39 : jhr 488 fun analyse (entryVal, cfg) = let
40 : jhr 508 (* use DFS order to get quicker convergence *)
41 :     val nodes as entry::rest = IL.CFG.sort cfg
42 :     (* the first pass does not do change propagation, since we haven't computed anything yet *)
43 :     fun initNode nd = let
44 :     val inValue = D.join (List.map getOut (IL.Node.preds nd))
45 :     val outValue = D.transfer (inValue, nd)
46 :     in
47 :     setIn (nd, inValue);
48 :     setOut (nd, outValue)
49 :     end
50 :     (* once nodes are initialized, we iterate until we reach a fixed point *)
51 : jhr 257 fun iterate () = let
52 :     val anyChange = ref false
53 :     fun doNode nd = let
54 : jhr 414 val inValue = D.join (List.map getOut (IL.Node.preds nd))
55 : jhr 257 in
56 : jhr 414 if D.same(getIn nd, inValue)
57 :     then () (* input unchanged, so output will be unchanged *)
58 :     else let
59 :     val outValue = D.transfer (inValue, nd)
60 :     in
61 :     anyChange := true;
62 :     setIn (nd, inValue);
63 :     if D.same(getOut nd, outValue)
64 : jhr 417 then ()
65 :     else setOut(nd, outValue)
66 : jhr 414 end
67 : jhr 257 end
68 :     in
69 : jhr 508 List.app doNode rest;
70 : jhr 257 if !anyChange then iterate() else ()
71 :     end
72 :     in
73 : jhr 508 (* initialize the output of the CFG entry node *)
74 :     setOut (entry, entryVal);
75 :     (* initialize the rest of the nodes *)
76 :     List.app initNode rest;
77 :     (* iterate to a fixed point *)
78 :     iterate ();
79 :     nodes
80 : jhr 257 end
81 :    
82 : jhr 414 fun inValue nd = getIn nd
83 :     fun outValue nd = getOut nd
84 : jhr 257
85 : jhr 414 fun scrub nodes = List.app clear nodes
86 : jhr 257
87 :     end

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