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

Annotation of /sml/trunk/src/MLRISC/flowgraph/cfg.sml

Parent Directory Parent Directory | Revision Log Revision Log


Revision 1125 - (view) (download)

1 : jhr 1104 (* cfg.sml
2 :     *
3 :     * COPYRIGHT (c) 2002 Bell Labs, Lucent Technologies
4 :     *
5 : george 906 * The control flow graph representation used for optimizations.
6 :     *
7 :     * -- Allen
8 :     *)
9 : jhr 1104
10 : george 906 functor ControlFlowGraph
11 : george 984 (structure I : INSTRUCTIONS
12 : george 906 structure GraphImpl : GRAPH_IMPLEMENTATION
13 : jhr 1084 structure InsnProps : INSN_PROPERTIES where I = I
14 : george 984 structure Asm : INSTRUCTION_EMITTER where I = I
15 : george 906 ) : CONTROL_FLOW_GRAPH =
16 :     struct
17 :    
18 :     structure I = I
19 : george 984 structure P = Asm.S.P
20 : george 906 structure C = I.C
21 :     structure G = Graph
22 :     structure A = Annotations
23 :     structure S = Asm.S
24 :    
25 : jhr 1125 type weight = real
26 :    
27 : george 906 datatype block_kind =
28 :     START (* entry node *)
29 :     | STOP (* exit node *)
30 :     | NORMAL (* normal node *)
31 :    
32 : george 984 and block =
33 : george 906 BLOCK of
34 :     { id : int, (* block id *)
35 :     kind : block_kind, (* block kind *)
36 :     freq : weight ref, (* execution frequency *)
37 :     labels : Label.label list ref, (* labels on blocks *)
38 :     insns : I.instruction list ref, (* in rev order *)
39 : george 984 align : P.pseudo_op option ref, (* alignment only *)
40 : george 906 annotations : Annotations.annotations ref (* annotations *)
41 :     }
42 :    
43 : jhr 1084 and edge_kind (* edge kinds (see cfg.sig for more info) *)
44 :     = ENTRY (* entry edge *)
45 :     | EXIT (* exit edge *)
46 :     | JUMP (* unconditional jump *)
47 :     | FALLSTHRU (* falls through to next block *)
48 :     | BRANCH of bool (* branch *)
49 :     | SWITCH of int (* computed goto *)
50 :     | FLOWSTO (* FLOW_TO edge *)
51 : george 906
52 : jhr 1084 and edge_info = EDGE of {
53 :     k : edge_kind, (* edge kind *)
54 :     w : weight ref, (* edge freq *)
55 :     a : Annotations.annotations ref (* annotations *)
56 :     }
57 : george 906
58 :     type edge = edge_info Graph.edge
59 :     type node = block Graph.node
60 :    
61 :     datatype info =
62 :     INFO of { annotations : Annotations.annotations ref,
63 :     firstBlock : int ref,
64 : george 984 reorder : bool ref,
65 :     data : P.pseudo_op list ref
66 : george 906 }
67 :    
68 :     type cfg = (block,edge_info,info) Graph.graph
69 :    
70 :     fun error msg = MLRiscErrorMsg.error("ControlFlowGraph",msg)
71 :    
72 :     (*========================================================================
73 :     *
74 :     * Various kinds of annotations
75 :     *
76 :     *========================================================================*)
77 :     (* escaping live out information *)
78 :     val LIVEOUT = Annotations.new
79 :     (SOME(fn c => "Liveout: "^
80 :     (LineBreak.lineBreak 75
81 :     (CellsBasis.CellSet.toString c))))
82 :     exception Changed of string * (unit -> unit)
83 :     val CHANGED = Annotations.new'
84 :     {create=Changed,
85 :     get=fn Changed x => x | e => raise e,
86 :     toString=fn (name,_) => "CHANGED:"^name
87 :     }
88 :    
89 :     (*========================================================================
90 :     *
91 :     * Methods for manipulating basic blocks
92 :     *
93 :     *========================================================================*)
94 :     fun defineLabel(BLOCK{labels=ref(l::_),...}) = l
95 : george 984 | defineLabel(BLOCK{labels, ...}) = let
96 : george 906 val l = Label.anon ()
97 :     in
98 :     labels := [l];
99 :     l
100 :     end
101 :     fun insns(BLOCK{insns, ...}) = insns
102 :     fun freq(BLOCK{freq, ...}) = freq
103 :    
104 :     fun newBlock'(id,kind,insns,freq) =
105 :     BLOCK{ id = id,
106 :     kind = kind,
107 :     freq = freq,
108 :     labels = ref [],
109 :     insns = ref insns,
110 : george 984 align = ref NONE,
111 : george 906 annotations = ref []
112 :     }
113 :    
114 : george 984 fun copyBlock(id,BLOCK{kind,freq,align,labels,insns,annotations,...}) =
115 : george 906 BLOCK{ id = id,
116 :     kind = kind,
117 :     freq = ref (!freq),
118 :     labels = ref [],
119 : george 984 align = ref (!align),
120 : george 906 insns = ref (!insns),
121 :     annotations = ref (!annotations)
122 :     }
123 :    
124 :     fun newBlock(id,freq) = newBlock'(id,NORMAL,[],freq)
125 :     fun newStart(id,freq) = newBlock'(id,START,[],freq)
126 :     fun newStop(id,freq) = newBlock'(id,STOP,[],freq)
127 :    
128 :     fun branchOf(EDGE{k=BRANCH b,...}) = SOME b
129 :     | branchOf _ = NONE
130 :     fun edgeDir(_,_,e) = branchOf e
131 :    
132 :     (*========================================================================
133 :     *
134 :     * Emit a basic block
135 :     *
136 :     *========================================================================*)
137 :     fun kindName START = "START"
138 :     | kindName STOP = "STOP"
139 :     | kindName NORMAL = "Block"
140 :    
141 :     fun nl() = TextIO.output(!AsmStream.asmOutStream,"\n")
142 :    
143 :     fun emitHeader (S.STREAM{comment,annotation,...})
144 :     (BLOCK{id,kind,freq,annotations,...}) =
145 :     (comment(kindName kind ^"["^Int.toString id^
146 : jhr 1125 "] ("^Real.toString (!freq)^")");
147 : george 906 nl();
148 :     app annotation (!annotations)
149 :     )
150 :    
151 :     fun emitFooter (S.STREAM{comment,...}) (BLOCK{annotations,...}) =
152 :     (case #get LIVEOUT (!annotations) of
153 :     SOME s =>
154 :     let val regs = String.tokens Char.isSpace(CellsBasis.CellSet.toString s)
155 :     val K = 7
156 :     fun f(_,[],s,l) = s::l
157 :     | f(0,vs,s,l) = f(K,vs," ",s::l)
158 :     | f(n,[v],s,l) = v^s::l
159 :     | f(n,v::vs,s,l) = f(n-1,vs,s^" "^v,l)
160 :     val text = rev(f(K,regs,"",[]))
161 :     in app (fn c => (comment c; nl())) text
162 :     end
163 :     | NONE => ()
164 :     ) handle Overflow => print("Bad footer\n")
165 :    
166 :     fun emitStuff outline annotations
167 : george 984 (block as BLOCK{insns,labels,...}) =
168 : george 906 let val S as S.STREAM{pseudoOp,defineLabel,emit,...} =
169 :     Asm.makeStream annotations
170 :     in emitHeader S block;
171 : george 959 app defineLabel (!labels);
172 : george 906 if outline then () else app emit (rev (!insns));
173 :     emitFooter S block
174 :     end
175 :    
176 :     val emit = emitStuff false
177 :     val emitOutline = emitStuff true []
178 :    
179 :     (*========================================================================
180 :     *
181 :     * Methods for manipulating CFG
182 :     *
183 :     *========================================================================*)
184 :     fun cfg info = GraphImpl.graph("CFG",info,10)
185 :     fun new() =
186 :     let val info = INFO{ annotations = ref [],
187 :     firstBlock = ref 0,
188 : george 984 reorder = ref false,
189 :     data = ref []
190 : george 906 }
191 :     in cfg info end
192 :    
193 :     fun subgraph(CFG as G.GRAPH{graph_info=INFO graph_info,...}) =
194 :     let val info = INFO{ annotations = ref [],
195 :     firstBlock = #firstBlock graph_info,
196 : george 984 reorder = #reorder graph_info,
197 :     data = #data graph_info
198 : george 906 }
199 :     in UpdateGraphInfo.update CFG info end
200 :    
201 :     fun init(G.GRAPH cfg) =
202 :     (case #entries cfg () of
203 :     [] =>
204 :     let val i = #new_id cfg ()
205 : jhr 1125 val start = newStart(i,ref 0.0)
206 : george 906 val _ = #add_node cfg (i,start)
207 :     val j = #new_id cfg ()
208 : jhr 1125 val stop = newStop(j,ref 0.0)
209 : george 906 val _ = #add_node cfg (j,stop)
210 :     in (* #add_edge cfg (i,j,EDGE{k=ENTRY,w=ref 0,a=ref []}); *)
211 :     #set_entries cfg [i];
212 :     #set_exits cfg [j]
213 :     end
214 :     | _ => ()
215 :     )
216 :    
217 :     fun changed(G.GRAPH{graph_info=INFO{reorder,annotations,...},...}) =
218 :     let fun signal [] = ()
219 :     | signal(Changed(_,f)::an) = (f (); signal an)
220 :     | signal(_::an) = signal an
221 :     in signal(!annotations);
222 :     reorder := true
223 :     end
224 :    
225 :     fun annotations(G.GRAPH{graph_info=INFO{annotations=a,...},...}) = a
226 :    
227 :     fun liveOut (BLOCK{annotations, ...}) =
228 :     case #get LIVEOUT (!annotations) of
229 :     SOME s => s
230 :     | NONE => C.empty
231 :     fun fallsThruFrom(G.GRAPH cfg,b) =
232 :     let fun f [] = NONE
233 :     | f((i,_,EDGE{k=BRANCH false,...})::_) = SOME i
234 :     | f((i,_,EDGE{k=FALLSTHRU,...})::_) = SOME i
235 :     | f(_::es) = f es
236 :     in f(#in_edges cfg b)
237 :     end
238 :     fun fallsThruTo(G.GRAPH cfg,b) =
239 :     let fun f [] = NONE
240 :     | f((_,j,EDGE{k=BRANCH false,...})::_) = SOME j
241 :     | f((_,j,EDGE{k=FALLSTHRU,...})::_) = SOME j
242 :     | f(_::es) = f es
243 :     in f(#out_edges cfg b)
244 :     end
245 :     fun removeEdge CFG (i,j,EDGE{a,...}) =
246 :     Graph.remove_edge' CFG (i,j,fn EDGE{a=a',...} => a = a')
247 :    
248 :     fun setBranch (CFG as G.GRAPH cfg,b,cond) =
249 :     let fun loop((i,j,EDGE{k=BRANCH cond',w,a})::es,es',x,y) =
250 :     if cond' = cond then
251 :     loop(es, (i,j,EDGE{k=JUMP,w=w,a=a})::es',j,y)
252 :     else
253 :     loop(es, es', x, j)
254 :     | loop([],es',target,elim) = (es',target,elim)
255 :     | loop _ = error "setBranch"
256 :     val outEdges = #out_edges cfg b
257 :     val (outEdges',target,elim) = loop(outEdges,[],~1,~1)
258 :     val _ = if elim < 0 then error "setBranch: bad edges" else ();
259 :     val lab = defineLabel(#node_info cfg target)
260 :     val jmp = InsnProps.jump lab
261 :     val insns = insns(#node_info cfg b)
262 :     in #set_out_edges cfg (b,outEdges');
263 :     case !insns of
264 :     [] => error "setBranch: missing branch"
265 :     | branch::rest =>
266 :     case InsnProps.instrKind branch of
267 :     InsnProps.IK_JUMP => insns := jmp::rest
268 :     | _ => error "setBranch: bad branch instruction";
269 :     jmp
270 :     end
271 :    
272 :     (*========================================================================
273 :     *
274 :     * Miscellaneous
275 :     *
276 :     *========================================================================*)
277 :     fun cdgEdge(EDGE{k, ...}) =
278 :     case k of
279 :     (JUMP | FALLSTHRU) => false
280 :     | _ => true
281 :    
282 :     (*========================================================================
283 :     *
284 :     * Pretty Printing and Viewing
285 :     *
286 :     *========================================================================*)
287 :    
288 : jhr 1104 structure F = Format
289 : george 906
290 : jhr 1104 fun show_edge (EDGE{k,w,a,...}) = let
291 :     val kind = (case k
292 :     of JUMP => "jump"
293 :     | FALLSTHRU => "fallsthru"
294 :     | BRANCH b => Bool.toString b
295 :     | SWITCH i => Int.toString i
296 :     | ENTRY => "entry"
297 :     | EXIT => "exit"
298 :     | FLOWSTO => "flowsto"
299 :     (* end case *))
300 :     in
301 : jhr 1125 F.format "%s(%d)" [F.STR kind, F.REAL(!w)]
302 : jhr 1104 end
303 :    
304 :     fun getString f x = let
305 :     val buffer = StringOutStream.mkStreamBuf()
306 :     val S = StringOutStream.openStringOut buffer
307 :     val _ = AsmStream.withStream S f x
308 :     in
309 :     StringOutStream.getString buffer
310 :     end
311 :    
312 :     fun show_block an block = let
313 :     val text = getString (emit an) block
314 :     in
315 :     foldr (fn (x,"") => x | (x,y) => x^" "^y) ""
316 :     (String.tokens (fn #" " => true | _ => false) text)
317 :     end
318 :    
319 : jhr 1118 fun dumpBlock (outS, cfg as G.GRAPH g) = let
320 : jhr 1104 fun pr str = TextIO.output(outS, str)
321 :     fun prList [] = ()
322 :     | prList [i] = pr i
323 :     | prList (h::t) = (pr (h ^ ", "); prList t)
324 : jhr 1118 val Asm.S.STREAM{emit,defineLabel,annotation,...} =
325 :     AsmStream.withStream outS Asm.makeStream []
326 : jhr 1125 fun showFreq (ref w) = F.format "[%f]" [F.REAL w]
327 : jhr 1104 fun showEdge (blknum,e) =
328 :     F.format "%d:%s" [F.INT blknum, F.STR(show_edge e)]
329 :     fun showSucc (_, x, e) = showEdge(x,e)
330 :     fun showPred (x, _, e) = showEdge(x,e)
331 :     fun showSuccs b = (
332 :     pr "\tsucc: ";
333 :     prList (map showSucc (#out_edges g b));
334 :     pr "\n")
335 :     fun showPreds b = (
336 :     pr "\tpred: ";
337 :     prList (map showPred (#in_edges g b));
338 :     pr "\n")
339 :     fun printBlock (_, BLOCK{kind=START, id, freq, ...}) = (
340 :     pr (F.format "ENTRY %d %s\n" [F.INT id, F.STR(showFreq freq)]);
341 :     showSuccs id)
342 :     | printBlock (_, BLOCK{kind=STOP, id, freq, ...}) = (
343 :     pr (F.format "EXIT %d %s\n" [F.INT id, F.STR(showFreq freq)]);
344 :     showPreds id)
345 :     | printBlock (
346 :     _, BLOCK{id, align, freq, insns, annotations, labels, ...}
347 :     ) = (
348 :     pr (F.format "BLOCK %d %s\n" [F.INT id, F.STR(showFreq freq)]);
349 :     case !align of NONE => () | SOME p => (pr (P.toString p ^ "\n"));
350 : jhr 1118 List.app annotation (!annotations);
351 :     List.app defineLabel (!labels);
352 : jhr 1104 showSuccs id;
353 :     showPreds id;
354 :     List.app emit (List.rev (!insns)))
355 : jhr 1118 in
356 :     printBlock
357 :     end
358 :    
359 :     fun dump (outS, title, cfg as G.GRAPH g) = let
360 :     fun pr str = TextIO.output(outS, str)
361 :     val annotations = !(annotations cfg)
362 :     val Asm.S.STREAM{annotation, ...} =
363 :     AsmStream.withStream outS Asm.makeStream annotations
364 : jhr 1104 fun printData () = let
365 :     val INFO{data, ...} = #graph_info g
366 :     in
367 :     List.app (pr o P.toString) (rev(!data))
368 :     end
369 :     in
370 :     pr(F.format "[ %s ]\n" [F.STR title]);
371 :     List.app annotation annotations;
372 :     (* printBlock entry; *)
373 : jhr 1118 AsmStream.withStream outS (#forall_nodes g) (dumpBlock (outS, cfg));
374 : jhr 1104 (* printBlock exit; *)
375 :     AsmStream.withStream outS printData ();
376 :     TextIO.flushOut outS
377 :     end
378 :    
379 : george 906 end
380 :    

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