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

SCM Repository

[diderot] Annotation of /trunk/src/compiler/IL/backward-dfa-fn.sml
ViewVC logotype

Annotation of /trunk/src/compiler/IL/backward-dfa-fn.sml

Parent Directory Parent Directory | Revision Log Revision Log


Revision 414 - (view) (download)

1 : jhr 258 (* backward-dfa-fn.sml
2 :     *
3 :     * COPYRIGHT (c) 2010 The Diderot Project (http://diderot.cs.uchicago.edu)
4 :     * All rights reserved.
5 :     *
6 :     * Backward data-flow analysis for IL code.
7 :     *)
8 :    
9 :     functor BackwardDFAFn (D : DOMAIN) :> sig
10 :    
11 :     structure D : DOMAIN
12 :    
13 : jhr 414 (* given a function for defining out values for exits and the root node, do the
14 :     * backward DFA on the CFG and return the list of nodes analysed.
15 : jhr 258 *)
16 : jhr 414 val analyse : (D.IL.node -> D.t) * D.IL.stmt -> D.IL.node list
17 : jhr 258
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 258
22 :     (* scrub results to reclaim space *)
23 : jhr 414 val scrub : D.IL.node list -> unit
24 : jhr 258
25 :     end = struct
26 :    
27 :     structure D = D
28 :     structure IL = D.IL
29 :    
30 : jhr 414 val {setFn=setIn, getFn=getIn, clrFn= clrIn, ...} =
31 : jhr 258 PropList.newProp (fn (IL.ND{props, ...}) => props, fn _ => D.bottom)
32 : jhr 414 val {setFn=setOut, getFn=getOut, clrFn=clrOut, ...} =
33 :     PropList.newProp (fn (IL.ND{props, ...}) => props, fn _ => D.bottom)
34 : jhr 258
35 : jhr 414 fun clear node = (clrIn node; clrOut node)
36 :    
37 : jhr 258 fun analyse (exitVal, stm) = let
38 :     (* use DFS order to get quicker convergence *)
39 :     val nodes = IL.sortNodes stm
40 :     (* set initial values for exit nodes *)
41 : jhr 414 val _ = List.app (fn nd => if IL.Node.hasSucc nd then () else setIn(nd, exitVal nd)) nodes
42 : jhr 258 fun iterate () = let
43 :     val anyChange = ref false
44 :     fun doNode nd = let
45 : jhr 414 val outValue = D.join (List.map getIn (IL.Node.succs nd))
46 : jhr 258 in
47 : jhr 414 if D.same(getOut nd, outValue)
48 :     then ()(* output unchanged, so output will be unchanged *)
49 :     else let
50 :     val inValue = D.transfer (outValue, nd)
51 :     in
52 :     anyChange := true;
53 :     setOut (nd, outValue);
54 :     if D.same(getIn nd, inValue)
55 :     then ()
56 :     else setIn(nd, inValue)
57 :     end
58 : jhr 258 end
59 :     in
60 :     List.app doNode nodes;
61 :     if !anyChange then iterate() else ()
62 :     end
63 :     in
64 :     iterate (); nodes
65 :     end
66 :    
67 : jhr 414 fun inValue nd = getIn nd
68 :     fun outValue nd = getOut nd
69 : jhr 258
70 : jhr 414 fun scrub nodes = List.app clear nodes
71 : jhr 258
72 :     end

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