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

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