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

SCM Repository

[smlnj] Annotation of /sml/trunk/src/MLRISC/ir-moved/dominance-frontier.sml
ViewVC logotype

Annotation of /sml/trunk/src/MLRISC/ir-moved/dominance-frontier.sml

Parent Directory Parent Directory | Revision Log Revision Log


Revision 411 - (view) (download)
Original Path: sml/branches/SMLNJ/src/MLRISC/ir-moved/dominance-frontier.sml

1 : monnier 245 (* Computation of the dominance frontier using the algorithm
2 :     * of Cytron, Ferrante, Rosen, Wegman and Zadeck in TOPLAS 91
3 : monnier 411 *
4 :     * -- Allen
5 : monnier 245 *)
6 :    
7 :     functor DominanceFrontiersFn (Dom : DOMINATOR_TREE)
8 :     : DOMINANCE_FRONTIERS =
9 :     struct
10 :    
11 :     structure Dom = Dom
12 :     structure G = Graph
13 :     structure A = Array
14 :    
15 :     type dominance_frontiers = G.node_id list A.array
16 :    
17 :     fun DFs (Dom as G.GRAPH dom) =
18 :     let val N = #capacity dom ()
19 :     val DF = A.array(N,[]) : dominance_frontiers
20 :     val G.GRAPH cfg = Dom.cfg Dom
21 :     val methods = Dom.methods Dom
22 :     val immediately_dominates = #immediately_dominates methods
23 :     fun computeDF X =
24 :     let (* the successors in X that are not strictly dominated by X *)
25 :     val S = foldr (fn ((_,Y,_),S) =>
26 :     if immediately_dominates(X,Y)
27 :     then S else Y::S) [] (#out_edges cfg X)
28 :     (* Nodes in the dominance frontier of n that are not
29 :     * dominated by n's immediate dominator
30 :     *)
31 :     fun computeChild((_,Z,_),S) =
32 :     let val DF_Z = computeDF Z
33 :     val S = foldr (fn (Y,S) =>
34 :     if immediately_dominates(X,Y)
35 :     then S else Y::S) S DF_Z
36 :     in S
37 :     end
38 :     val S = foldl computeChild S (#out_edges dom X)
39 :     in
40 :     A.update(DF,X,S);
41 :     S
42 :     end
43 :    
44 :     val [root] = #entries dom ()
45 :     val _ = computeDF root
46 :     in
47 :     DF
48 :     end
49 :    
50 :     end
51 :    

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