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 245 - (view) (download)
Original Path: sml/branches/SMLNJ/src/MLRISC/ir-moved/idefs2.sml

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

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