Home My Page Projects Code Snippets Project Openings SML/NJ
Summary Activity Forums Tracker Lists Tasks Docs Surveys News SCM Files

SCM Repository

[smlnj] Diff of /sml/trunk/src/MLRISC/IR/dataflow.sml
ViewVC logotype

Diff of /sml/trunk/src/MLRISC/IR/dataflow.sml

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

revision 245, Sat Apr 17 18:47:12 1999 UTC revision 411, Fri Sep 3 00:25:03 1999 UTC
# Line 1  Line 1 
1    (*
2     * This is just a very simple worklist based data analyzer.
3     * Parameterized by the dataflow problem.
4     *
5     * -- Allen
6     *)
7    
8  functor DataflowFn(P : DATAFLOW_PROBLEM) : DATAFLOW_ANALYZER =  functor DataflowFn(P : DATAFLOW_PROBLEM) : DATAFLOW_ANALYZER =
9  struct  struct
10     structure G   = Graph     structure G   = Graph
# Line 7  Line 14 
14     type dataflow_info = P.dataflow_info     type dataflow_info = P.dataflow_info
15    
16     fun analyze (CFG, info) =     fun analyze (CFG, info) =
17     let val G.GRAPH cfg = if P.forward then CFG     let val G' as G.GRAPH cfg = if P.forward then CFG
18                           else ReversedGraphView.rev_view CFG                           else ReversedGraphView.rev_view CFG
19         val N         = #capacity cfg ()         val N         = #capacity cfg ()
20           val ENTRY     = case #entries cfg () of
21                             [ENTRY] => ENTRY
22                           | _ => raise Graph.NotSingleEntry
23         val inputs    = A.array(N, P.bot)         val inputs    = A.array(N, P.bot)
24         val outputs   = A.array(N, P.bot)         val outputs   = A.array(N, P.bot)
25         val transfers = A.array(N, fn _ => P.bot)         val transfers = A.array(N, fn _ => P.bot)
# Line 22  Line 32 
32                                 A.update(transfers,n,transfer)                                 A.update(transfers,n,transfer)
33                             end                             end
34                            )                            )
        val [ENTRY]  = #entries cfg ()  
        val entries  = #out_edges cfg ENTRY  
35    
36         abstype worklist = WL of int list * int list         abstype worklist = WL of int list * int list
37         with         with
# Line 39  Line 47 
47                | deque(WL(b,i::f)) = (A.update(on_queue,i,false); (WL(b,f),i))                | deque(WL(b,i::f)) = (A.update(on_queue,i,false); (WL(b,f),i))
48             fun insert(wl,[]) = wl             fun insert(wl,[]) = wl
49               | insert(wl,(_,n,_)::es) = insert(enque(wl,n),es)               | insert(wl,(_,n,_)::es) = insert(enque(wl,n),es)
50               fun insert'(wl,[]) = wl
51                 | insert'(wl,n::ns) = insert'(enque(wl,n),ns)
52         end         end
53    
54         fun propagate worklist =         fun propagate worklist =
# Line 57  Line 67 
67                   propagate(insert(worklist,#out_edges cfg i)))                   propagate(insert(worklist,#out_edges cfg i)))
68         end         end
69    
70         val _        = propagate(insert(empty,entries)) handle EmptyQueue => ()         val nodes    = GraphTopsort.topsort G' (#entries cfg ())
71           val _        = propagate(insert'(empty,nodes)) handle EmptyQueue => ()
72         val epilogue = P.epilogue(CFG,info)         val epilogue = P.epilogue(CFG,info)
73         val _        = #forall_nodes cfg         val _        = #forall_nodes cfg
74                           (fn (n,n') => epilogue{input  = A.sub(inputs,n),                           (fn (n,n') => epilogue{input  = A.sub(inputs,n),
# Line 69  Line 80 
80    
81  end  end
82    
 (*  
  * $Log$  
  *)  

Legend:
Removed from v.245  
changed lines
  Added in v.411

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