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

trunk/src/compiler/IL/backward-dfa-fn.sml revision 258, Mon Aug 9 18:36:44 2010 UTC branches/pure-cfg/src/compiler/IL/backward-dfa-fn.sml revision 740, Mon Apr 4 02:07:42 2011 UTC
# Line 1  Line 1 
1  (* backward-dfa-fn.sml  (* backward-dfa-fn.sml
2   *   *
3   * COPYRIGHT (c) 2010 The Diderot Project (http://diderot.cs.uchicago.edu)   * COPYRIGHT (c) 2010 The Diderot Project (http://diderot-language.cs.uchicago.edu)
4   * All rights reserved.   * All rights reserved.
5   *   *
6   * Backward data-flow analysis for IL code.   * Backward data-flow analysis for IL code.
# 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.cfg -> 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 analyse (exitVal, stm) = let      fun clear node = (clrIn node; clrOut node)
36          (* use DFS order to get quicker convergence *)  
37            val nodes = IL.sortNodes stm      fun analyse (exitVal, cfg) = let
38          (* set initial values for exit nodes *)          (* use reverse DFS order to get quicker convergence *)
39            val _ = List.app (fn nd => if IL.Node.hasSucc nd then () else setFn(nd, exitVal nd)) nodes            val nodes = List.rev (IL.CFG.sort cfg)
40            (* the first pass does not do change propagation, since we haven't computed anything yet *)
41              fun initNode nd = if IL.Node.hasSucc nd
42                    then let
43                      val outValue = D.join (List.map getIn (IL.Node.succs nd))
44                      val inValue = D.transfer (outValue, nd)
45                      in
46                        setOut (nd, outValue);
47                        setIn (nd, inValue)
48                      end
49                    else setIn(nd, exitVal nd)  (* exit node *)
50            (* once nodes are initialized, we iterate until we reach a fixed point *)
51            fun iterate () = let            fun iterate () = let
52                  val anyChange = ref false                  val anyChange = ref false
53                  fun doNode nd = let                  fun doNode nd = let
54                        val outValue = D.join (List.map getFn (IL.Node.succs nd))                        val outValue = D.join (List.map getIn (IL.Node.succs nd))
55                          in
56                            if D.same(getOut nd, outValue)
57                              then ()(* output unchanged, so input will be unchanged *)
58                              else let
59                        val inValue = D.transfer (outValue, nd)                        val inValue = D.transfer (outValue, nd)
60                        in                        in
61                          if D.same(getFn nd, inValue)                                anyChange := true;
62                                  setOut (nd, outValue);
63                                  if D.same(getIn nd, inValue)
64                            then ()                            then ()
65                            else (setFn(nd, inValue); anyChange := true)                                  else setIn(nd, inValue)
66                                end
67                        end                        end
68                  in                  in
69                    List.app doNode nodes;                    List.app doNode nodes;
70                    if !anyChange then iterate() else ()                    if !anyChange then iterate() else ()
71                  end                  end
72            in            in
73              iterate (); nodes            (* initialize the rest of the nodes *)
74                List.app initNode nodes;
75              (* iterate to a fixed point *)
76                iterate ();
77                nodes
78            end            end
79    
80      fun inValue (_, nd) = getFn nd      fun inValue nd = getIn nd
81        fun outValue nd = getOut nd
82    
83      fun scrub nodes = List.app clrFn nodes      fun scrub nodes = List.app clear nodes
84    
85    end    end

Legend:
Removed from v.258  
changed lines
  Added in v.740

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