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

SCM Repository

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

Annotation of /branches/vis15/src/compiler/cfg-ir/forward-dfa-fn.sml

Parent Directory Parent Directory | Revision Log Revision Log


Revision 4317 - (view) (download)

1 : jhr 3470 (* forward-dfa-fn.sml
2 :     *
3 :     * This code is part of the Diderot Project (http://diderot-language.cs.uchicago.edu)
4 :     *
5 :     * COPYRIGHT (c) 2015 The University of Chicago
6 :     * All rights reserved.
7 :     *
8 : jhr 3475 * Forward data-flow analysis for IR code.
9 : jhr 3470 *)
10 :    
11 : jhr 3726 functor ForwardDFAFn (D : DOMAIN) : sig
12 : jhr 3470
13 : jhr 3726 structure D : DOMAIN
14 : jhr 3470
15 :     (* given the entry value and root statement, do the forward DFA on the CFG and
16 :     * return the list of nodes that were analysed.
17 :     *)
18 : jhr 3475 val analyse : D.t * D.IR.cfg -> D.IR.node list
19 : jhr 3470
20 :     (* get results for a node *)
21 : jhr 3475 val inValue : D.IR.node -> D.t
22 :     val outValue : D.IR.node -> D.t
23 : jhr 3470
24 :     (* scrub results to reclaim space *)
25 : jhr 3475 val scrub : D.IR.node list -> unit
26 : jhr 3470
27 :     end = struct
28 :    
29 :     structure D = D
30 : jhr 3475 structure IR = D.IR
31 : jhr 3470
32 : jhr 3475 type result = IR.node list
33 : jhr 3470
34 :     val {setFn=setIn, getFn=getIn, clrFn= clrIn, ...} =
35 : jhr 4317 PropList.newProp (fn (IR.ND{props, ...}) => props, fn _ => D.bottom)
36 : jhr 3470 val {setFn=setOut, getFn=getOut, clrFn=clrOut, ...} =
37 : jhr 4317 PropList.newProp (fn (IR.ND{props, ...}) => props, fn _ => D.bottom)
38 : jhr 3470
39 :     fun clear node = (clrIn node; clrOut node)
40 :    
41 :     fun analyse (entryVal, cfg) = let
42 :     (* DEBUG val t = Timer.startCPUTimer()*)
43 : jhr 4317 (* use DFS order to get quicker convergence *)
44 :     val nodes as entry::rest = IR.CFG.sort cfg
45 : jhr 3470 (*DEBUG val nIters = ref 0*)
46 :     (*DEBUG val nVisits = ref 0*)
47 : jhr 4317 (* the first pass does not do change propagation, since we haven't computed anything yet *)
48 :     fun initNode nd = let
49 :     val inValue = D.join (List.map getOut (IR.Node.preds nd))
50 :     val outValue = D.transfer (inValue, nd)
51 :     in
52 : jhr 3470 (*DEBUG nVisits := !nVisits + 1;*)
53 : jhr 4317 setIn (nd, inValue);
54 :     setOut (nd, outValue)
55 :     end
56 :     (* once nodes are initialized, we iterate until we reach a fixed point *)
57 :     fun iterate () = let
58 :     val anyChange = ref false
59 :     fun doNode nd = let
60 :     val inValue = D.join (List.map getOut (IR.Node.preds nd))
61 :     in
62 :     if D.same(getIn nd, inValue)
63 :     then () (* input unchanged, so output will be unchanged *)
64 :     else let
65 :     val outValue = D.transfer (inValue, nd)
66 :     in
67 : jhr 3470 (*DEBUG nVisits := !nVisits + 1;*)
68 : jhr 4317 anyChange := true;
69 :     setIn (nd, inValue);
70 :     if D.same(getOut nd, outValue)
71 :     then ()
72 :     else setOut(nd, outValue)
73 :     end
74 :     end
75 :     in
76 : jhr 3470 (*DEBUG nIters := !nIters + 1;*)
77 : jhr 4317 List.app doNode rest;
78 :     if !anyChange then iterate() else ()
79 :     end
80 :     in
81 :     (* initialize the output of the CFG entry node *)
82 :     setOut (entry, entryVal);
83 :     (* initialize the rest of the nodes *)
84 :     List.app initNode rest;
85 :     (* iterate to a fixed point *)
86 :     iterate ();
87 : jhr 3470 (*DEBUG*
88 :     let val gcTime = Timer.checkGCTime t
89 :     val {usr, sys} = Timer.checkCPUTimer t
90 :     in
91 : jhr 3508 print(concat[IR.irName, " DFA: cpu = ", Time.toString(Time.+(usr, sys)),
92 : jhr 3470 " seconds, gc = ", Time.toString gcTime, " seconds, ",
93 :     Int.toString(List.length rest + 1), " nodes, ",
94 :     Int.toString(!nVisits), " visits, ",
95 :     Int.toString(!nIters), " iterations\n"])
96 :     end;
97 :     *DEBUG*)
98 : jhr 4317 nodes
99 :     end
100 : jhr 3470
101 :     fun inValue nd = getIn nd
102 :     fun outValue nd = getOut nd
103 :    
104 :     fun scrub nodes = List.app clear nodes
105 :    
106 :     end

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