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/idefs2.sml
ViewVC logotype

Annotation of /sml/trunk/src/MLRISC/ir-moved/idefs2.sml

Parent Directory Parent Directory | Revision Log Revision Log


Revision 651 - (view) (download)

1 : monnier 411 (*
2 :     * This is Reif and Tarjan's algorithm (SIAM J Computing 1981)
3 :     * for computing approximate birthpoints for expressions.
4 :     * For each basic block B,
5 :     * idef(x) = { defs(v_i) | i = 1 ... n in all paths
6 :     * idom(x) v_1 v_2 ... v_n x where n >= 1 and
7 :     * v_i <> idom(x) for all 1 <= i <= n
8 :     * }
9 :     * -- Allen
10 :     *)
11 :    
12 : monnier 245 structure IDefs : IDEFS =
13 :     struct
14 :    
15 :     structure G = Graph
16 : monnier 429 structure SL = SortedList
17 : monnier 245 structure A = Array
18 :     structure Rev = ReversedGraphView
19 :    
20 :     type var = int
21 :    
22 :     fun compute_idefs {def_use, cfg} =
23 :     let val CFG as G.GRAPH cfg = cfg
24 :     val N = #capacity cfg ()
25 : monnier 429 val DU = A.array(N,([],[]))
26 : monnier 245 val _ = #forall_nodes cfg
27 :     (fn (b,b') => let val (d,u) = def_use(b,b')
28 : monnier 429 in A.update(DU,b,(SL.uniq d,SL.uniq u))
29 : monnier 245 end)
30 :     fun dump(name,a) =
31 :     (print(name^"=");
32 :     A.appi (fn (i,v) =>
33 :     print(Int.toString i ^ "=" ^Int.toString v^" "))
34 :     (a,0,NONE);
35 :     print "\n")
36 :    
37 :     fun tarjan_lengauer(G.GRAPH cfg) =
38 :     let val [ENTRY] = #entries cfg ()
39 :     val vertex = A.array(N,~1)
40 :     val parent = A.array(N,~1)
41 :     val semi = A.array(N,~1)
42 :     val bucket = A.array(N,[])
43 :     val dom = A.array(N,~1)
44 : monnier 429 val sdefuse = A.array(N,([],[]))
45 :     val idefuse = A.array(N,([],[]))
46 : monnier 245 val ancestor = A.array(N,~1)
47 :     val treeparent = A.array(N,~1)
48 :     val label = A.array(N,~1)
49 :     fun dfs(p,n,i) =
50 :     if A.sub(semi,i) <> ~1 then n
51 :     else
52 :     (A.update(parent,i,p);
53 :     A.update(semi,i,n);
54 :     A.update(vertex,n,i);
55 :     A.update(label,i,i);
56 :     dfs'(i,n+1,#succ cfg i)
57 :     )
58 :     and dfs'(p,n,[]) = n
59 :     | dfs'(p,n,i::is) = dfs'(p,dfs(p,n,i),is)
60 :     val n = dfs(~1,0,ENTRY)
61 :    
62 :     fun COMPRESS v =
63 :     if A.sub(ancestor,A.sub(ancestor,v)) <> ~1 then
64 :     (COMPRESS(A.sub(ancestor,v));
65 :     let val label_ancestor_v = A.sub(label,A.sub(ancestor,v))
66 :     val label_v = A.sub(label,v)
67 :     in if A.sub(semi,label_ancestor_v) <
68 :     A.sub(semi,label_v) then
69 :     A.update(label,v,label_ancestor_v)
70 :     else ()
71 :     end;
72 :     A.update(ancestor,v,A.sub(ancestor,A.sub(ancestor,v)))
73 :     )
74 :     else ()
75 :    
76 :     fun LINK(v,w) = (A.update(ancestor,w,v);
77 :     A.update(treeparent,w,v))
78 :     fun EVAL v =
79 :     if A.sub(ancestor,v) = ~1 then v
80 :     else (COMPRESS v; A.sub(label,v))
81 :     fun EVALDEFUSE v =
82 :     let fun up(v,D,U) =
83 :     let val p = A.sub(treeparent,v)
84 :     in if p = ~1 then (D,U)
85 :     else let val (d,u) = A.sub(DU,v)
86 :     val (d',u') = A.sub(sdefuse,v)
87 : monnier 429 in up(p,SL.merge(d,SL.merge(d',D)),
88 :     SL.merge(u,SL.merge(u',U)))
89 : monnier 245 end
90 :     end
91 :     in
92 : monnier 429 up(v,[],[])
93 : monnier 245 end
94 :     fun step2_3 0 = ()
95 :     | step2_3 i =
96 :     let val w = A.sub(vertex,i)
97 :     val parent_w = A.sub(parent,w)
98 :     fun step2 [] = ()
99 :     | step2 ((v,_,_)::vs) =
100 :     let val u = EVAL v
101 :     val semi_u = A.sub(semi,u)
102 :     in if semi_u < A.sub(semi,w) then
103 :     A.update(semi,w,semi_u)
104 :     else ();
105 :     let val (d,u) = EVALDEFUSE v
106 :     val (d',u') = A.sub(sdefuse,w)
107 : monnier 429 in A.update(sdefuse,w,(SL.merge(d,d'),
108 :     SL.merge(u,u')))
109 : monnier 245 end;
110 :     step2 vs
111 :     end
112 :     val _ = step2(#in_edges cfg w)
113 :     val vertex_semi_w = A.sub(vertex,A.sub(semi,w))
114 :     val _ = A.update(bucket,vertex_semi_w,
115 :     w::A.sub(bucket,vertex_semi_w))
116 :     val _ = LINK(parent_w,w)
117 :     fun step3 [] = ()
118 :     | step3 (v::vs) =
119 :     let val u = EVAL v
120 :     in A.update(dom,v,if A.sub(semi,u) < A.sub(semi,v)
121 :     then u else parent_w);
122 :     let val (d,u) = A.sub(sdefuse,v)
123 :     val (d',u') = EVALDEFUSE(A.sub(parent,v))
124 : monnier 429 in A.update(idefuse,v,(SL.merge(d,d'),
125 :     SL.merge(u,u')))
126 : monnier 245 end;
127 :     step3 vs
128 :     end
129 :     val _ = step3 (A.sub(bucket,parent_w))
130 :     val _ = A.update(bucket,parent_w,[])
131 :     in step2_3(i-1)
132 :     end
133 :     val _ = step2_3(n-1)
134 :     (*
135 :     val _ = print("n = "^Int.toString n^"\n")
136 :     val _ = dump("vertex",vertex)
137 :     val _ = dump("parent",parent)
138 :     val _ = dump("semi",semi)
139 :     val _ = dump("dom",dom)
140 :     val _ = dump("ancestor",ancestor)
141 :     val _ = dump("label",label)
142 :     *)
143 :     fun step4 i =
144 :     if i = n then ()
145 :     else let val w = A.sub(vertex,i)
146 :     in if A.sub(dom,w) <> A.sub(vertex,A.sub(semi,w)) then
147 :     let val (d,u) = A.sub(idefuse,A.sub(dom,w))
148 :     val (d',u') = A.sub(idefuse,w)
149 : monnier 429 in A.update(idefuse,w,(SL.merge(d,d'),
150 :     SL.merge(u,u')));
151 : monnier 245 A.update(dom,w,A.sub(dom,A.sub(dom,w)))
152 :     end
153 :     else ();
154 :     step4(i+1)
155 :     end
156 :     val _ = step4 1
157 :     in idefuse
158 :     end
159 :     in
160 :     {idefuse = fn _ => tarjan_lengauer(CFG),
161 :     ipostdefuse = fn _ => tarjan_lengauer(Rev.rev_view CFG)
162 :     }
163 :     end
164 :    
165 :     end
166 :    

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