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

SCM Repository

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

Diff of /trunk/src/compiler/IL/forward-dfa-fn.sml

Parent Directory Parent Directory | Revision Log Revision Log | View Patch Patch

revision 413, Sat Oct 16 15:39:31 2010 UTC revision 414, Sat Oct 16 18:00:43 2010 UTC
# Line 10  Line 10 
10    
11      structure D : DOMAIN      structure D : DOMAIN
12    
13    (* abstract representation of analysis results *)    (* given the entry value and root statement, do the forward DFA on the CFG and
14      type result     * return the list of nodes analysed.
15       *)
16    (* given the entry value and root statement, do the forward DFA on the CFG *)      val analyse : D.t * D.IL.stmt -> D.IL.node list
17      val analyse : D.t * D.IL.stmt -> result  
18      (* get results for a node *)
19    (* get result for a node *)      val inValue : D.IL.node -> D.t
20      val outValue : result * D.IL.node -> D.t      val outValue : D.IL.node -> D.t
21    
22    (* scrub results to reclaim space *)    (* scrub results to reclaim space *)
23      val scrub : result -> unit      val scrub : D.IL.node list -> unit
24    
25    end = struct    end = struct
26    
# Line 29  Line 29 
29    
30      type result = IL.node list      type result = IL.node list
31    
32      val {setFn, getFn, clrFn, ...} =      val {setFn=setIn, getFn=getIn, clrFn= clrIn, ...} =
33            PropList.newProp (fn (IL.ND{props, ...}) => props, fn _ => D.bottom)            PropList.newProp (fn (IL.ND{props, ...}) => props, fn _ => D.bottom)
34        val {setFn=setOut, getFn=getOut, clrFn=clrOut, ...} =
35              PropList.newProp (fn (IL.ND{props, ...}) => props, fn _ => D.bottom)
36    
37        fun clear node = (clrIn node; clrOut node)
38    
39      fun analyse (entryVal, stm) = let      fun analyse (entryVal, stm) = let
40            val _ = setFn(IL.Stmt.entry stm, entryVal)            val _ = setOut(IL.Stmt.entry stm, entryVal)
41          (* use reverse DFS order to get quicker convergence *)          (* use reverse DFS order to get quicker convergence *)
42            val nodes = List.rev (IL.sortNodes stm)            val nodes = List.rev (IL.sortNodes stm)
43            fun iterate () = let            fun iterate () = let
44                  val anyChange = ref false                  val anyChange = ref false
45                  fun doNode nd = let                  fun doNode nd = let
46                        val inValue = D.join (List.map getFn (IL.Node.preds nd))                        val inValue = D.join (List.map getOut (IL.Node.preds nd))
47                        val outValue = D.transfer (inValue, nd)                        val outValue = D.transfer (inValue, nd)
48                        in                        in
49                          if D.same(getFn nd, outValue)                          if D.same(getIn nd, inValue)
50                            then ()                            then () (* input unchanged, so output will be unchanged *)
51                            else (setFn(nd, outValue); anyChange := true)                            else let
52                                val outValue = D.transfer (inValue, nd)
53                                in
54                                  anyChange := true;
55                                  setIn (nd, inValue);
56                                  if D.same(getOut nd, outValue)
57                                    then setOut(nd, outValue)
58                                    else ()
59                                end
60                        end                        end
61                  in                  in
62                    List.app doNode nodes;                    List.app doNode nodes;
# Line 54  Line 66 
66              iterate (); nodes              iterate (); nodes
67            end            end
68    
69      fun outValue (_, nd) = getFn nd      fun inValue nd = getIn nd
70        fun outValue nd = getOut nd
71    
72      fun scrub nodes = List.app clrFn nodes      fun scrub nodes = List.app clear nodes
73    
74    end    end

Legend:
Removed from v.413  
changed lines
  Added in v.414

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