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

SCM Repository

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

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

Parent Directory Parent Directory | Revision Log Revision Log


Revision 258 - (view) (download)

1 : jhr 257 (* forward-dfa-fn.sml
2 :     *
3 :     * COPYRIGHT (c) 2010 The Diderot Project (http://diderot.cs.uchicago.edu)
4 :     * All rights reserved.
5 :     *
6 :     * Forward data-flow analysis for IL code.
7 :     *)
8 :    
9 :     functor ForwardDFAFn (D : DOMAIN) :> sig
10 :    
11 :     structure D : DOMAIN
12 :    
13 : jhr 258 (* abstract representation of analysis results *)
14 : jhr 257 type result
15 :    
16 : jhr 258 (* given the entry value and root statement, do the forward DFA on the CFG *)
17 : jhr 257 val analyse : D.t * D.IL.stmt -> result
18 :    
19 : jhr 258 (* get result for a node *)
20 : jhr 257 val outValue : result * D.IL.node -> D.t
21 :    
22 : jhr 258 (* scrub results to reclaim space *)
23 : jhr 257 val scrub : result -> unit
24 :    
25 :     end = struct
26 :    
27 :     structure D = D
28 :     structure IL = D.IL
29 :    
30 :     type result = IL.node list
31 :    
32 :     val {setFn, getFn, clrFn, ...} =
33 :     PropList.newProp (fn (IL.ND{props, ...}) => props, fn _ => D.bottom)
34 :    
35 :     fun analyse (entryVal, stm) = let
36 :     val _ = setFn(IL.Stmt.entry stm, entryVal)
37 :     (* use reverse DFS order to get quicker convergence *)
38 :     val nodes = List.rev (IL.sortNodes stm)
39 :     fun iterate () = let
40 :     val anyChange = ref false
41 :     fun doNode nd = let
42 :     val inValue = D.join (List.map getFn (IL.Node.preds nd))
43 :     val outValue = D.transfer (inValue, nd)
44 :     in
45 :     if D.same(getFn nd, outValue)
46 :     then ()
47 :     else (setFn(nd, outValue); anyChange := true)
48 :     end
49 :     in
50 :     List.app doNode nodes;
51 :     if !anyChange then iterate() else ()
52 :     end
53 :     in
54 :     iterate (); nodes
55 :     end
56 :    
57 :     fun outValue (_, nd) = getFn nd
58 :    
59 :     fun scrub nodes = List.app clrFn nodes
60 :    
61 :     end

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