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/backward-dfa-fn.sml
ViewVC logotype

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

Parent Directory Parent Directory | Revision Log Revision Log


Revision 3349 - (view) (download)

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

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