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 430 - (view) (download)

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 : monnier 429 val immediately_dominates = Dom.immediately_dominates Dom
22 : monnier 245 fun computeDF X =
23 :     let (* the successors in X that are not strictly dominated by X *)
24 :     val S = foldr (fn ((_,Y,_),S) =>
25 :     if immediately_dominates(X,Y)
26 :     then S else Y::S) [] (#out_edges cfg X)
27 :     (* Nodes in the dominance frontier of n that are not
28 :     * dominated by n's immediate dominator
29 :     *)
30 :     fun computeChild((_,Z,_),S) =
31 :     let val DF_Z = computeDF Z
32 :     val S = foldr (fn (Y,S) =>
33 :     if immediately_dominates(X,Y)
34 :     then S else Y::S) S DF_Z
35 :     in S
36 :     end
37 :     val S = foldl computeChild S (#out_edges dom X)
38 :     in
39 :     A.update(DF,X,S);
40 :     S
41 :     end
42 :    
43 :     val [root] = #entries dom ()
44 :     val _ = computeDF root
45 :     in
46 :     DF
47 :     end
48 :    
49 :     end
50 :    

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