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

SCM Repository

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

Annotation of /branches/pure-cfg/src/compiler/IL/backward-dfa-fn.sml

Parent Directory Parent Directory | Revision Log Revision Log


Revision 258 - (view) (download)
Original Path: trunk/src/compiler/IL/backward-dfa-fn.sml

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

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