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 /MLRISC/trunk/IR/mlrisc-cfg2cluster.sml
ViewVC logotype

Annotation of /MLRISC/trunk/IR/mlrisc-cfg2cluster.sml

Parent Directory Parent Directory | Revision Log Revision Log


Revision 744 - (view) (download)
Original Path: sml/trunk/src/MLRISC/IR/mlrisc-cfg2cluster.sml

1 : monnier 245 (*
2 :     * Convert the new control flow graph format back into the old cluster format
3 : monnier 411 *
4 :     * -- Allen
5 : monnier 245 *)
6 :    
7 :     signature CFG2CLUSTER =
8 :     sig
9 :     structure CFG : CONTROL_FLOW_GRAPH
10 :     structure F : FLOWGRAPH
11 :     sharing CFG.I = F.I
12 :     sharing CFG.P = F.P
13 :    
14 :     (*
15 :     * If relayout is true, then always use the layout algorithm.
16 :     * Otherwise, try to preserve the original layout if possible.
17 :     *)
18 :     val cfg2cluster : { cfg : CFG.cfg,
19 :     relayout : bool
20 :     } -> F.cluster
21 :    
22 :     end
23 :    
24 : george 545 functor CFG2Cluster
25 :     (structure CFG : CONTROL_FLOW_GRAPH
26 :     structure Flowgraph : FLOWGRAPH
27 :     sharing CFG.I = Flowgraph.I
28 :     sharing CFG.P = Flowgraph.P
29 : monnier 245 ) : CFG2CLUSTER =
30 :     struct
31 :    
32 :     structure CFG = CFG
33 :     structure W = CFG.W
34 : george 545 structure F = Flowgraph
35 : monnier 245 structure G = Graph
36 :     structure Q = PriorityQueue
37 :     structure Set = BitSet
38 :     structure A = Array
39 :    
40 : monnier 411 fun error msg = MLRiscErrorMsg.error("CFG2Cluster",msg)
41 : monnier 245
42 : monnier 429 val dummyNode = F.LABEL(Label.Label{id= ~1, addr=ref ~1, name=""})
43 :    
44 : monnier 245 fun pseudo_op (CFG.LABEL l) = F.LABEL l
45 :     | pseudo_op (CFG.PSEUDO p) = F.PSEUDO p
46 :    
47 :     (* create a new BBLOCK with id i *)
48 :     fun bblock M (i,b as
49 : monnier 469 CFG.BLOCK{kind,freq,annotations,insns,labels,data,...}) =
50 : monnier 245 let val labels = map F.LABEL (!labels)
51 :     in case kind of
52 :     CFG.STOP => map pseudo_op (!data)
53 :     | _ =>
54 : monnier 469 let val block = F.BBLOCK{blknum = i,
55 : monnier 411 freq = freq,
56 : monnier 469 annotations = ref(#rmv CFG.LIVEOUT
57 :     (!annotations)),
58 : monnier 411 insns = insns,
59 :     liveIn = ref F.C.empty,
60 :     liveOut = ref (CFG.liveOut b),
61 :     pred = ref [],
62 :     succ = ref []
63 : monnier 245 }
64 :     in A.update(M,i,block);
65 :     map pseudo_op (!data) @ labels @ [block]
66 :     end
67 :     end
68 :    
69 :     fun bblock' (M,M',M'') =
70 :     let val bblock = bblock M
71 :     in fn (i,b as CFG.BLOCK{id,...}) =>
72 :     let val block = bblock(i,b)
73 :     in A.update(M',i,id); A.update(M'',id,i); block end
74 :     end
75 :    
76 :     (* create a new ENTRY with id i *)
77 : monnier 411 fun entry(M,i,freq) =
78 :     let val entry = F.ENTRY{succ=ref [], blknum=i, freq=freq}
79 : monnier 245 in A.update(M,i,entry);
80 :     entry
81 :     end
82 :    
83 : monnier 411 fun entry'(M,M',M'',i,id,freq) =
84 :     let val entry = entry(M,i,freq)
85 : monnier 245 in A.update(M',i,id); A.update(M'',id,i); entry
86 :     end
87 :    
88 :     (* create a new EXIT with id i *)
89 : monnier 411 fun exit(M,i,freq) =
90 :     let val exit = F.EXIT{pred=ref [], blknum=i, freq=freq}
91 : monnier 245 in A.update(M,i,exit);
92 :     exit
93 :     end
94 :    
95 : monnier 411 fun exit'(M,M',M'',i,id,freq) =
96 :     let val exit = exit(M,i,freq)
97 : monnier 245 in A.update(M',i,id); A.update(M'',id,i); exit
98 :     end
99 :    
100 :     fun id_of(F.BBLOCK{blknum,...}) = blknum
101 :     | id_of(F.ENTRY{blknum,...}) = blknum
102 :     | id_of(F.EXIT{blknum,...}) = blknum
103 :    
104 :     fun remove_entry_to_exit (ENTRY,EXIT,CFG) =
105 :     Graph.remove_edge CFG (ENTRY,EXIT)
106 :    
107 : monnier 411 fun freqOf (G.GRAPH cfg) id =
108 :     let val CFG.BLOCK{freq,...} = #node_info cfg id in freq end
109 :    
110 : monnier 245 (*
111 :     * Convert cfg -> cluster, assuming the layout is unchanged
112 :     *)
113 :     fun computeOldLayout (CFG as G.GRAPH cfg) =
114 :     let val M = #capacity cfg ()
115 : monnier 411 val ENTRY = case #entries cfg () of
116 :     [ENTRY] => ENTRY
117 :     | _ => raise Graph.NotSingleEntry
118 :     val EXIT = case #exits cfg () of
119 :     [EXIT] => EXIT
120 :     | _ => raise Graph.NotSingleExit
121 : leunga 744 val CFG.INFO{annotations,...} = #graph_info cfg
122 : monnier 245 val _ = remove_entry_to_exit(ENTRY,EXIT,CFG)
123 : monnier 429 val A = A.array(M,dummyNode)
124 : monnier 245 val nodes = List.filter(fn (i,CFG.BLOCK{kind,...}) =>
125 : leunga 624 i <> ENTRY andalso i <> EXIT)
126 : monnier 245 (#nodes cfg ())
127 :     val blocks = List.concat(
128 :     map (bblock A) (nodes @ [(EXIT,#node_info cfg EXIT)]))
129 : monnier 411 val entry = entry (A,ENTRY,freqOf CFG ENTRY)
130 :     val exit = exit (A,EXIT,freqOf CFG EXIT)
131 :     fun succs i = map (fn (_,i,CFG.EDGE{w,...}) => (A.sub(A,i),w))
132 :     (#out_edges cfg i)
133 :     fun preds i = map (fn (i,_,CFG.EDGE{w,...}) => (A.sub(A,i),w))
134 :     (#in_edges cfg i)
135 : monnier 245 fun set_links(F.BBLOCK{blknum,pred,succ,insns,...}) =
136 :     (pred := preds blknum; succ := succs blknum)
137 :     | set_links(F.ENTRY{blknum,succ,...}) = succ := succs blknum
138 :     | set_links(F.EXIT{blknum,pred,...}) = pred := preds blknum
139 :     | set_links _ = ()
140 :     val _ = A.app set_links A
141 : monnier 411 in F.CLUSTER{ blkCounter = ref M,
142 :     blocks = blocks,
143 :     entry = entry,
144 :     exit = exit,
145 :     annotations = annotations
146 : monnier 245 }
147 :     end
148 :    
149 :     (*
150 :     * Convert cfg -> cluster, while computing a new code layout.
151 :     *)
152 :     fun computeNewLayout (CFG as G.GRAPH cfg) =
153 :     let val M = #capacity cfg ()
154 : monnier 411 val ENTRY = case #entries cfg () of
155 :     [ENTRY] => ENTRY
156 :     | _ => raise Graph.NotSingleEntry
157 :     val EXIT = case #exits cfg () of
158 :     [EXIT] => EXIT
159 :     | _ => raise Graph.NotSingleExit
160 : leunga 744 val CFG.INFO{firstBlock,annotations,...} =
161 : monnier 411 #graph_info cfg
162 : monnier 429 val A = A.array(M,dummyNode) (* new id -> F.block *)
163 : monnier 245 val A' = A.array(M,~1) (* new id -> old id *)
164 :     val A'' = A.array(M,~1) (* old id -> new id *)
165 :     val min_pred = A.array(M,10000000)
166 :     val in_degs = A.tabulate(M,fn i => length(#in_edges cfg i))
167 :     val nodes = GraphTopsort.topsort CFG (ENTRY::map #1 (#nodes cfg ()))
168 :    
169 :     fun higher_freq(i,j) =
170 :     let val CFG.BLOCK{freq=w1,...} = #node_info cfg i
171 :     val CFG.BLOCK{freq=w2,...} = #node_info cfg j
172 : monnier 411 in !w1 > !w2
173 : monnier 245 end
174 :    
175 :     fun older(i,j) = A.sub(min_pred,i) < A.sub(min_pred,j)
176 :    
177 :     val marked = Set.create M
178 :     val node_queue = Q.create (* older *) higher_freq
179 :     val insert_node = Q.insert node_queue
180 :    
181 :     fun node b = (b,#node_info cfg b)
182 :    
183 :     val make_a_block = bblock' (A,A',A'')
184 :     fun make_block(id,B as CFG.BLOCK{id=i,
185 :     insns=ref [],data,labels,...}) =
186 :     (case #in_edges cfg i of
187 :     [] => map pseudo_op (!data) @ map F.LABEL (!labels)
188 :     | _ => make_a_block(id,B)
189 :     )
190 :     | make_block(id,B) = make_a_block(id,B)
191 :    
192 :     fun update_succs (id,[]) = ()
193 :     | update_succs (id,((i,j,_)::es)) =
194 :     let val count = A.sub(in_degs,j) - 1
195 :     in A.update(min_pred,j,Int.min(id,A.sub(min_pred,j)));
196 :     A.update(in_degs,j,count);
197 :     if count = 0 andalso
198 :     j <> EXIT andalso
199 :     (case CFG.fallsThruFrom(CFG,j) of SOME _ => false
200 :     | NONE => true) then
201 :     insert_node j
202 :     else ();
203 :     update_succs(id,es)
204 :     end
205 :    
206 :     fun layout(id,(i,B),waiting,blocks) =
207 :     if Set.markAndTest(marked,i) then
208 :     layout_all(id,waiting,blocks)
209 :     else let val blocks = make_block(id,B)::blocks
210 :     in update_succs(id,#out_edges cfg i);
211 :     case CFG.fallsThruTo(CFG,i) of
212 :     SOME j => layout(id+1,node j,waiting,blocks)
213 :     | NONE => layout_all(id+1,waiting,blocks)
214 :     end
215 :    
216 :     and layout_all(id,waiting,blocks) =
217 :     if Q.isEmpty node_queue then
218 :     layout_waiting(id,waiting,blocks)
219 :     else
220 :     let val b = Q.deleteMin node_queue
221 :     in layout(id,node b,waiting,blocks)
222 :     end
223 :    
224 :     and layout_waiting(id,[],blocks) =
225 :     (id,List.concat(rev blocks))
226 :     | layout_waiting(id,n::waiting,blocks) =
227 :     case CFG.fallsThruFrom(CFG,n) of
228 :     SOME _ => layout_waiting(id,waiting,blocks)
229 :     | NONE => layout(id,node n,waiting,blocks)
230 :    
231 :     val _ = Set.set(marked,ENTRY)
232 :     val _ = Set.set(marked,EXIT)
233 :     val (id,blocks) = layout_all(0,(!firstBlock)::nodes,[])
234 :     (*val _ = print("M="^Int.toString M^ " id="^Int.toString id^"\n")*)
235 :    
236 : monnier 411 val exit = exit'(A,A',A'',id,EXIT,freqOf CFG EXIT)
237 :     val entry = entry'(A,A',A'',id+1,ENTRY,freqOf CFG ENTRY)
238 : monnier 245 val blocks = blocks @ bblock A (EXIT,#node_info cfg EXIT)
239 : monnier 411 fun succs i = map (fn (_,i,CFG.EDGE{w,...}) =>
240 :     (A.sub(A,A.sub(A'',i)),w))
241 :     (#out_edges cfg (A.sub(A',i)))
242 :     fun preds i = map (fn (i,_,CFG.EDGE{w,...}) =>
243 :     (A.sub(A,A.sub(A'',i)),w))
244 :     (#in_edges cfg (A.sub(A',i)))
245 : monnier 245 fun set_links(F.BBLOCK{blknum,pred,succ,insns,...}) =
246 : monnier 411 let fun isBackwardBranch((F.BBLOCK{blknum=next,...},_)::bs) =
247 : monnier 245 next <= blknum orelse isBackwardBranch bs
248 :     | isBackwardBranch(_::bs) = isBackwardBranch bs
249 :     | isBackwardBranch [] = false
250 :     in pred := preds blknum;
251 : monnier 411 succ := succs blknum
252 : monnier 245 end
253 :     | set_links(F.ENTRY{blknum,succ,...}) = succ := succs blknum
254 :     | set_links(F.EXIT{blknum,pred,...}) = pred := preds blknum
255 :     | set_links _ = ()
256 :     val _ = A.app set_links A
257 : monnier 411 in F.CLUSTER{ blkCounter = ref(id+2),
258 :     blocks = blocks,
259 :     entry = entry,
260 :     exit = exit,
261 :     annotations = annotations
262 : monnier 245 }
263 :     end
264 :    
265 :     fun cfg2cluster {cfg=CFG as G.GRAPH cfg,relayout} =
266 :     let val CFG.INFO{reorder,...} = #graph_info cfg
267 :     in if !reorder orelse relayout then computeNewLayout CFG
268 :     else computeOldLayout CFG
269 :     end
270 :    
271 :     end
272 :    

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