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

SCM Repository

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

Diff of /branches/pure-cfg/src/compiler/IL/backward-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 a function for defining out values for exits and the root node, do the
14      type result     * backward DFA on the CFG and return the list of nodes analysed.
   
   (* given a function for defining out values for exis and the root statement, do the  
    * backward DFA on the CFG  
15     *)     *)
16      val analyse : (D.IL.node -> D.t) * D.IL.stmt -> result      val analyse : (D.IL.node -> D.t) * D.IL.stmt -> D.IL.node list
17    
18    (* get result for a node *)    (* get results for a node *)
19      val inValue : result * D.IL.node -> D.t      val inValue : D.IL.node -> D.t
20        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    
27      structure D = D      structure D = D
28      structure IL = D.IL      structure IL = D.IL
29    
30      type result = IL.node list      val {setFn=setIn, getFn=getIn, clrFn= clrIn, ...} =
31              PropList.newProp (fn (IL.ND{props, ...}) => props, fn _ => D.bottom)
32      val {setFn, getFn, clrFn, ...} =      val {setFn=setOut, getFn=getOut, clrFn=clrOut, ...} =
33            PropList.newProp (fn (IL.ND{props, ...}) => props, fn _ => D.bottom)            PropList.newProp (fn (IL.ND{props, ...}) => props, fn _ => D.bottom)
34    
35        fun clear node = (clrIn node; clrOut node)
36    
37      fun analyse (exitVal, stm) = let      fun analyse (exitVal, stm) = let
38          (* use DFS order to get quicker convergence *)          (* use DFS order to get quicker convergence *)
39            val nodes = IL.sortNodes stm            val nodes = IL.sortNodes stm
40          (* set initial values for exit nodes *)          (* set initial values for exit nodes *)
41            val _ = List.app (fn nd => if IL.Node.hasSucc nd then () else setFn(nd, exitVal nd)) nodes            val _ = List.app (fn nd => if IL.Node.hasSucc nd then () else setIn(nd, exitVal nd)) nodes
42            fun iterate () = let            fun iterate () = let
43                  val anyChange = ref false                  val anyChange = ref false
44                  fun doNode nd = let                  fun doNode nd = let
45                        val outValue = D.join (List.map getFn (IL.Node.succs nd))                        val outValue = D.join (List.map getIn (IL.Node.succs nd))
46                          in
47                            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)                        val inValue = D.transfer (outValue, nd)
51                        in                        in
52                          if D.same(getFn nd, inValue)                                anyChange := true;
53                                  setOut (nd, outValue);
54                                  if D.same(getIn nd, inValue)
55                            then ()                            then ()
56                            else (setFn(nd, inValue); anyChange := true)                                  else setIn(nd, inValue)
57                                end
58                        end                        end
59                  in                  in
60                    List.app doNode nodes;                    List.app doNode nodes;
# Line 57  Line 64 
64              iterate (); nodes              iterate (); nodes
65            end            end
66    
67      fun inValue (_, nd) = getFn nd      fun inValue nd = getIn nd
68        fun outValue nd = getOut nd
69    
70      fun scrub nodes = List.app clrFn nodes      fun scrub nodes = List.app clear nodes
71    
72    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