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

SCM Repository

[diderot] Diff of /branches/vis15/src/compiler/cfg-ir/forward-dfa-fn.sml
ViewVC logotype

Diff of /branches/vis15/src/compiler/cfg-ir/forward-dfa-fn.sml

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

revision 3474, Wed Dec 2 18:26:40 2015 UTC revision 3475, Wed Dec 2 18:48:58 2015 UTC
# Line 5  Line 5 
5   * COPYRIGHT (c) 2015 The University of Chicago   * COPYRIGHT (c) 2015 The University of Chicago
6   * All rights reserved.   * All rights reserved.
7   *   *
8   * Forward data-flow analysis for IL code.   * Forward data-flow analysis for IR code.
9   *)   *)
10    
11  functor ForwardDFAFn (D : DOMAIN) :> sig  functor ForwardDFAFn (D : DOMAIN) :> sig
# Line 15  Line 15 
15    (* given the entry value and root statement, do the forward DFA on the CFG and    (* given the entry value and root statement, do the forward DFA on the CFG and
16     * return the list of nodes that were analysed.     * return the list of nodes that were analysed.
17     *)     *)
18      val analyse : D.t * D.IL.cfg -> D.IL.node list      val analyse : D.t * D.IR.cfg -> D.IR.node list
19    
20    (* get results for a node *)    (* get results for a node *)
21      val inValue : D.IL.node -> D.t      val inValue : D.IR.node -> D.t
22      val outValue : D.IL.node -> D.t      val outValue : D.IR.node -> D.t
23    
24    (* scrub results to reclaim space *)    (* scrub results to reclaim space *)
25      val scrub : D.IL.node list -> unit      val scrub : D.IR.node list -> unit
26    
27    end = struct    end = struct
28    
29      structure D = D      structure D = D
30      structure IL = D.IL      structure IR = D.IR
31    
32      type result = IL.node list      type result = IR.node list
33    
34      val {setFn=setIn, getFn=getIn, clrFn= clrIn, ...} =      val {setFn=setIn, getFn=getIn, clrFn= clrIn, ...} =
35            PropList.newProp (fn (IL.ND{props, ...}) => props, fn _ => D.bottom)            PropList.newProp (fn (IR.ND{props, ...}) => props, fn _ => D.bottom)
36      val {setFn=setOut, getFn=getOut, clrFn=clrOut, ...} =      val {setFn=setOut, getFn=getOut, clrFn=clrOut, ...} =
37            PropList.newProp (fn (IL.ND{props, ...}) => props, fn _ => D.bottom)            PropList.newProp (fn (IR.ND{props, ...}) => props, fn _ => D.bottom)
38    
39      fun clear node = (clrIn node; clrOut node)      fun clear node = (clrIn node; clrOut node)
40    
41      fun analyse (entryVal, cfg) = let      fun analyse (entryVal, cfg) = let
42  (* DEBUG val t = Timer.startCPUTimer()*)  (* DEBUG val t = Timer.startCPUTimer()*)
43          (* use DFS order to get quicker convergence *)          (* use DFS order to get quicker convergence *)
44            val nodes as entry::rest = IL.CFG.sort cfg            val nodes as entry::rest = IR.CFG.sort cfg
45  (*DEBUG val nIters = ref 0*)  (*DEBUG val nIters = ref 0*)
46  (*DEBUG val nVisits = ref 0*)  (*DEBUG val nVisits = ref 0*)
47          (* the first pass does not do change propagation, since we haven't computed anything yet *)          (* the first pass does not do change propagation, since we haven't computed anything yet *)
48            fun initNode nd = let            fun initNode nd = let
49                  val inValue = D.join (List.map getOut (IL.Node.preds nd))                  val inValue = D.join (List.map getOut (IR.Node.preds nd))
50                  val outValue = D.transfer (inValue, nd)                  val outValue = D.transfer (inValue, nd)
51                  in                  in
52  (*DEBUG nVisits := !nVisits + 1;*)  (*DEBUG nVisits := !nVisits + 1;*)
# Line 57  Line 57 
57            fun iterate () = let            fun iterate () = let
58                  val anyChange = ref false                  val anyChange = ref false
59                  fun doNode nd = let                  fun doNode nd = let
60                        val inValue = D.join (List.map getOut (IL.Node.preds nd))                        val inValue = D.join (List.map getOut (IR.Node.preds nd))
61                        in                        in
62                          if D.same(getIn nd, inValue)                          if D.same(getIn nd, inValue)
63                            then () (* input unchanged, so output will be unchanged *)                            then () (* input unchanged, so output will be unchanged *)
# Line 88  Line 88 
88  let val gcTime = Timer.checkGCTime t  let val gcTime = Timer.checkGCTime t
89  val {usr, sys} = Timer.checkCPUTimer t  val {usr, sys} = Timer.checkCPUTimer t
90  in  in
91  print(concat[IL.ilName, " DFA: cpu = ", Time.toString(Time.+(usr, sys)),  print(concat[IR.ilName, " DFA: cpu = ", Time.toString(Time.+(usr, sys)),
92  " seconds, gc = ", Time.toString gcTime, " seconds, ",  " seconds, gc = ", Time.toString gcTime, " seconds, ",
93  Int.toString(List.length rest + 1), " nodes, ",  Int.toString(List.length rest + 1), " nodes, ",
94  Int.toString(!nVisits), " visits, ",  Int.toString(!nVisits), " visits, ",

Legend:
Removed from v.3474  
changed lines
  Added in v.3475

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