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

1 : george 906 (*
2 :     * The control flow graph representation used for optimizations.
3 :     *
4 :     * -- Allen
5 :     *)
6 :     functor ControlFlowGraph
7 : george 984 (structure I : INSTRUCTIONS
8 : george 906 structure GraphImpl : GRAPH_IMPLEMENTATION
9 :     structure InsnProps : INSN_PROPERTIES
10 : george 933 where I = I
11 : george 984 structure Asm : INSTRUCTION_EMITTER where I = I
12 :    
13 : george 906 ) : CONTROL_FLOW_GRAPH =
14 :     struct
15 :    
16 :     structure I = I
17 : george 984 structure P = Asm.S.P
18 : george 906 structure C = I.C
19 :     structure W = Freq
20 :     structure G = Graph
21 :     structure A = Annotations
22 :     structure S = Asm.S
23 :    
24 :     type weight = W.freq
25 :    
26 :     datatype block_kind =
27 :     START (* entry node *)
28 :     | STOP (* exit node *)
29 :     | NORMAL (* normal node *)
30 :     | HYPERBLOCK (* hyperblock *)
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 :     and edge_kind = ENTRY (* entry edge *)
44 :     | EXIT (* exit edge *)
45 :     | JUMP (* unconditional jump *)
46 :     | FALLSTHRU (* falls through to next block *)
47 :     | BRANCH of bool (* branch *)
48 :     | SWITCH of int (* computed goto *)
49 :     | SIDEEXIT of int (* side exit *)
50 :    
51 :     and edge_info = EDGE of { k : edge_kind, (* edge kind *)
52 :     w : weight ref, (* edge freq *)
53 :     a : Annotations.annotations ref (* annotations *)
54 :     }
55 :    
56 :     type edge = edge_info Graph.edge
57 :     type node = block Graph.node
58 :    
59 :     datatype info =
60 :     INFO of { annotations : Annotations.annotations ref,
61 :     firstBlock : int ref,
62 : george 984 reorder : bool ref,
63 :     data : P.pseudo_op list ref
64 : george 906 }
65 :    
66 :     type cfg = (block,edge_info,info) Graph.graph
67 :    
68 :     fun error msg = MLRiscErrorMsg.error("ControlFlowGraph",msg)
69 :    
70 :     (*========================================================================
71 :     *
72 :     * Various kinds of annotations
73 :     *
74 :     *========================================================================*)
75 :     (* escaping live out information *)
76 :     val LIVEOUT = Annotations.new
77 :     (SOME(fn c => "Liveout: "^
78 :     (LineBreak.lineBreak 75
79 :     (CellsBasis.CellSet.toString c))))
80 :     exception Changed of string * (unit -> unit)
81 :     val CHANGED = Annotations.new'
82 :     {create=Changed,
83 :     get=fn Changed x => x | e => raise e,
84 :     toString=fn (name,_) => "CHANGED:"^name
85 :     }
86 :    
87 :     (*========================================================================
88 :     *
89 :     * Methods for manipulating basic blocks
90 :     *
91 :     *========================================================================*)
92 :     fun defineLabel(BLOCK{labels=ref(l::_),...}) = l
93 : george 984 | defineLabel(BLOCK{labels, ...}) = let
94 : george 906 val l = Label.anon ()
95 :     in
96 :     labels := [l];
97 :     l
98 :     end
99 :     fun insns(BLOCK{insns, ...}) = insns
100 :     fun freq(BLOCK{freq, ...}) = freq
101 :    
102 :     fun newBlock'(id,kind,insns,freq) =
103 :     BLOCK{ id = id,
104 :     kind = kind,
105 :     freq = freq,
106 :     labels = ref [],
107 :     insns = ref insns,
108 : george 984 align = ref NONE,
109 : george 906 annotations = ref []
110 :     }
111 :    
112 : george 984 fun copyBlock(id,BLOCK{kind,freq,align,labels,insns,annotations,...}) =
113 : george 906 BLOCK{ id = id,
114 :     kind = kind,
115 :     freq = ref (!freq),
116 :     labels = ref [],
117 : george 984 align = ref (!align),
118 : george 906 insns = ref (!insns),
119 :     annotations = ref (!annotations)
120 :     }
121 :    
122 :     fun newBlock(id,freq) = newBlock'(id,NORMAL,[],freq)
123 :     fun newStart(id,freq) = newBlock'(id,START,[],freq)
124 :     fun newStop(id,freq) = newBlock'(id,STOP,[],freq)
125 :    
126 :     fun branchOf(EDGE{k=BRANCH b,...}) = SOME b
127 :     | branchOf _ = NONE
128 :     fun edgeDir(_,_,e) = branchOf e
129 :    
130 :     (*========================================================================
131 :     *
132 :     * Emit a basic block
133 :     *
134 :     *========================================================================*)
135 :     fun kindName START = "START"
136 :     | kindName STOP = "STOP"
137 :     | kindName HYPERBLOCK = "Hyperblock"
138 :     | kindName NORMAL = "Block"
139 :    
140 :     fun nl() = TextIO.output(!AsmStream.asmOutStream,"\n")
141 :    
142 :     fun emitHeader (S.STREAM{comment,annotation,...})
143 :     (BLOCK{id,kind,freq,annotations,...}) =
144 :     (comment(kindName kind ^"["^Int.toString id^
145 :     "] ("^W.toString (!freq)^")");
146 :     nl();
147 :     app annotation (!annotations)
148 :     )
149 :    
150 :     fun emitFooter (S.STREAM{comment,...}) (BLOCK{annotations,...}) =
151 :     (case #get LIVEOUT (!annotations) of
152 :     SOME s =>
153 :     let val regs = String.tokens Char.isSpace(CellsBasis.CellSet.toString s)
154 :     val K = 7
155 :     fun f(_,[],s,l) = s::l
156 :     | f(0,vs,s,l) = f(K,vs," ",s::l)
157 :     | f(n,[v],s,l) = v^s::l
158 :     | f(n,v::vs,s,l) = f(n-1,vs,s^" "^v,l)
159 :     val text = rev(f(K,regs,"",[]))
160 :     in app (fn c => (comment c; nl())) text
161 :     end
162 :     | NONE => ()
163 :     ) handle Overflow => print("Bad footer\n")
164 :    
165 :     fun emitStuff outline annotations
166 : george 984 (block as BLOCK{insns,labels,...}) =
167 : george 906 let val S as S.STREAM{pseudoOp,defineLabel,emit,...} =
168 :     Asm.makeStream annotations
169 :     in emitHeader S block;
170 : george 959 app defineLabel (!labels);
171 : george 906 if outline then () else app emit (rev (!insns));
172 :     emitFooter S block
173 :     end
174 :    
175 :     val emit = emitStuff false
176 :     val emitOutline = emitStuff true []
177 :    
178 :     (*========================================================================
179 :     *
180 :     * Methods for manipulating CFG
181 :     *
182 :     *========================================================================*)
183 :     fun cfg info = GraphImpl.graph("CFG",info,10)
184 :     fun new() =
185 :     let val info = INFO{ annotations = ref [],
186 :     firstBlock = ref 0,
187 : george 984 reorder = ref false,
188 :     data = ref []
189 : george 906 }
190 :     in cfg info end
191 :    
192 :     fun subgraph(CFG as G.GRAPH{graph_info=INFO graph_info,...}) =
193 :     let val info = INFO{ annotations = ref [],
194 :     firstBlock = #firstBlock graph_info,
195 : george 984 reorder = #reorder graph_info,
196 :     data = #data graph_info
197 : george 906 }
198 :     in UpdateGraphInfo.update CFG info end
199 :    
200 :     fun init(G.GRAPH cfg) =
201 :     (case #entries cfg () of
202 :     [] =>
203 :     let val i = #new_id cfg ()
204 :     val start = newStart(i,ref 0)
205 :     val _ = #add_node cfg (i,start)
206 :     val j = #new_id cfg ()
207 :     val stop = newStop(j,ref 0)
208 :     val _ = #add_node cfg (j,stop)
209 :     in (* #add_edge cfg (i,j,EDGE{k=ENTRY,w=ref 0,a=ref []}); *)
210 :     #set_entries cfg [i];
211 :     #set_exits cfg [j]
212 :     end
213 :     | _ => ()
214 :     )
215 :    
216 :     fun changed(G.GRAPH{graph_info=INFO{reorder,annotations,...},...}) =
217 :     let fun signal [] = ()
218 :     | signal(Changed(_,f)::an) = (f (); signal an)
219 :     | signal(_::an) = signal an
220 :     in signal(!annotations);
221 :     reorder := true
222 :     end
223 :    
224 :     fun annotations(G.GRAPH{graph_info=INFO{annotations=a,...},...}) = a
225 :    
226 :     fun liveOut (BLOCK{annotations, ...}) =
227 :     case #get LIVEOUT (!annotations) of
228 :     SOME s => s
229 :     | NONE => C.empty
230 :     fun fallsThruFrom(G.GRAPH cfg,b) =
231 :     let fun f [] = NONE
232 :     | f((i,_,EDGE{k=BRANCH false,...})::_) = SOME i
233 :     | f((i,_,EDGE{k=FALLSTHRU,...})::_) = SOME i
234 :     | f(_::es) = f es
235 :     in f(#in_edges cfg b)
236 :     end
237 :     fun fallsThruTo(G.GRAPH cfg,b) =
238 :     let fun f [] = NONE
239 :     | f((_,j,EDGE{k=BRANCH false,...})::_) = SOME j
240 :     | f((_,j,EDGE{k=FALLSTHRU,...})::_) = SOME j
241 :     | f(_::es) = f es
242 :     in f(#out_edges cfg b)
243 :     end
244 :     fun removeEdge CFG (i,j,EDGE{a,...}) =
245 :     Graph.remove_edge' CFG (i,j,fn EDGE{a=a',...} => a = a')
246 :    
247 :     fun setBranch (CFG as G.GRAPH cfg,b,cond) =
248 :     let fun loop((i,j,EDGE{k=BRANCH cond',w,a})::es,es',x,y) =
249 :     if cond' = cond then
250 :     loop(es, (i,j,EDGE{k=JUMP,w=w,a=a})::es',j,y)
251 :     else
252 :     loop(es, es', x, j)
253 :     | loop([],es',target,elim) = (es',target,elim)
254 :     | loop _ = error "setBranch"
255 :     val outEdges = #out_edges cfg b
256 :     val (outEdges',target,elim) = loop(outEdges,[],~1,~1)
257 :     val _ = if elim < 0 then error "setBranch: bad edges" else ();
258 :     val lab = defineLabel(#node_info cfg target)
259 :     val jmp = InsnProps.jump lab
260 :     val insns = insns(#node_info cfg b)
261 :     in #set_out_edges cfg (b,outEdges');
262 :     case !insns of
263 :     [] => error "setBranch: missing branch"
264 :     | branch::rest =>
265 :     case InsnProps.instrKind branch of
266 :     InsnProps.IK_JUMP => insns := jmp::rest
267 :     | _ => error "setBranch: bad branch instruction";
268 :     jmp
269 :     end
270 :    
271 :     (*========================================================================
272 :     *
273 :     * Miscellaneous
274 :     *
275 :     *========================================================================*)
276 :     fun cdgEdge(EDGE{k, ...}) =
277 :     case k of
278 :     (JUMP | FALLSTHRU) => false
279 :     | _ => true
280 :    
281 :     (*========================================================================
282 :     *
283 :     * Pretty Printing and Viewing
284 :     *
285 :     *========================================================================*)
286 :     fun show_edge(EDGE{k,w,a,...}) =
287 :     let val kind = case k of
288 :     JUMP => ""
289 :     | FALLSTHRU => "fallsthru"
290 :     | BRANCH b => Bool.toString b
291 :     | SWITCH i => Int.toString i
292 :     | ENTRY => "entry"
293 :     | EXIT => "exit"
294 :     | SIDEEXIT i => "sideexit("^Int.toString i^")"
295 :     val weight = "(" ^ W.toString (!w) ^ ")"
296 :     in kind ^ weight
297 :     end
298 :    
299 :     fun getString f x =
300 :     let val buffer = StringOutStream.mkStreamBuf()
301 :     val S = StringOutStream.openStringOut buffer
302 :     val _ = AsmStream.withStream S f x
303 :     in StringOutStream.getString buffer end
304 :    
305 :     fun show_block an block =
306 :     let val text = getString (emit an) block
307 :     in foldr (fn (x,"") => x | (x,y) => x^" "^y) ""
308 :     (String.tokens (fn #" " => true | _ => false) text)
309 :     end
310 :     end
311 :    

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