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/SSA/mlrisc-ssa.sml
ViewVC logotype

Annotation of /sml/trunk/src/MLRISC/SSA/mlrisc-ssa.sml

Parent Directory Parent Directory | Revision Log Revision Log


Revision 228 - (view) (download)

1 : monnier 221 (*
2 :     * Basic SSA definitions, data structures, and transformations.
3 :     *)
4 :    
5 :     functor SSAFn
6 :     (structure CFG : CONTROL_FLOW_GRAPH
7 :     structure Dom : DOMINATOR_TREE
8 :     structure SP : SSA_PROPERTIES
9 :     structure P : INSN_PROPERTIES
10 :     structure FormatInsn : FORMAT_INSTRUCTION
11 :     structure GraphImpl : GRAPH_IMPLEMENTATION
12 :     sharing CFG.I = SP.I = P.I = FormatInsn.I
13 :     ) : SSA =
14 :     struct
15 :    
16 :     structure CFG = CFG
17 :     structure Dom = Dom
18 :     structure I = CFG.I
19 :     structure C = I.C
20 :     structure SP = SP
21 :     structure G = Graph
22 :     structure DA = DynamicArray
23 :     structure HA = HashArray
24 :     structure HT = HashTable
25 :     structure L = GraphLayout
26 :     structure E = SSAExp
27 :     structure A = Array
28 :     structure SU = SSAPropsUtil
29 :    
30 :     fun error msg = MLRiscErrorMsg.impossible("MLRISC_SSA."^msg)
31 :    
32 :     type value = int
33 :     type pos = int
34 :     type block = Graph.node_id
35 :     type exp = SSAExp.exp
36 :     type const = SP.const
37 :     type dom = (CFG.block,CFG.edge_info,CFG.info) Dom.dominator_tree
38 :    
39 :     datatype ssa_op =
40 :     PHI of {preds:block list,t':C.register,t:value,s:value list,b:block}
41 :     | OP of {e:exp,i:I.instruction,s:value list,t:value list,b:block,p:pos}
42 :     | SOURCE of {t:value list,t':C.register list,b:block}
43 :     | SINK of {s:value list,s':C.register list,b:block}
44 :    
45 :     datatype info =
46 :     INFO of
47 :     { cfg : CFG.cfg,
48 :     dom : CFG.cfg -> dom,
49 :     immTable : value HA.array,
50 :     labTable : (Label.label,value) HT.table,
51 :     opnTable : (I.operand,value) HT.table,
52 :     constTable : const HA.array,
53 :     defSite : Graph.node_id DA.array,
54 :     cellClass : C.cellclass DA.array,
55 :     nextImmed : int ref,
56 :     minPos : int ref,
57 :     maxPos : int ref,
58 :     nameTable : (C.register*int) HA.array (* old name/subscript *)
59 :     }
60 :    
61 :     type ssa = (ssa_op,value,info) Graph.graph
62 :    
63 :     exception NoConst
64 :     exception NoLabel
65 :     exception NoOperand
66 :     exception NoDefSite
67 :     exception NoName
68 :    
69 :     (*
70 :     * Selectors
71 :     *)
72 :     fun getInfo (G.GRAPH ssa) = let val INFO info = #graph_info ssa in info end
73 :    
74 :     fun dom SSA =
75 :     let val {cfg,dom,...} = getInfo SSA
76 :     in dom cfg end
77 :    
78 :     fun cfg SSA = #cfg(getInfo SSA)
79 :    
80 :     fun immed SSA =
81 :     let val {immTable,...} = getInfo SSA
82 :     in fn i => HA.sub(immTable,i) end
83 :    
84 :     fun label SSA =
85 :     let val {labTable,constTable,nextImmed,...} = getInfo SSA
86 :     val look = HT.lookup labTable
87 :     val ins = HT.insert labTable
88 :     fun lookup lab = look lab handle NoLabel =>
89 :     let val v = !nextImmed
90 :     val _ = nextImmed := v - 1
91 :     in HA.update(constTable,v,SP.LABEL lab); ins(lab,v); v end
92 :     in lookup end
93 :    
94 :     fun operand SSA =
95 :     let val {opnTable,constTable,nextImmed,...} = getInfo SSA
96 :     val look = HT.lookup opnTable
97 :     val ins = HT.insert opnTable
98 :     fun lookup opn = look opn handle NoOperand =>
99 :     let val v = !nextImmed
100 :     val _ = nextImmed := v - 1
101 :     in HA.update(constTable,v,SP.OPERAND opn); ins(opn,v); v end
102 :     in lookup end
103 :    
104 :     fun const SSA =
105 :     let val {constTable,...} = getInfo SSA
106 :     in fn v => HA.sub(constTable,v) end
107 :    
108 :     fun maxVar(G.GRAPH ssa) = #capacity ssa ()
109 :    
110 :     fun operands SSA =
111 :     let val {nextImmed,...} = getInfo SSA
112 :     in ~(!nextImmed) - 1 end
113 :    
114 :     fun defSite SSA =
115 :     let val {defSite,...} = getInfo SSA
116 :     in fn v => DA.sub(defSite,v) end
117 :    
118 :     fun cellClass SSA =
119 :     let val {cellClass,...} = getInfo SSA
120 :     in fn v => DA.sub(cellClass,v) end
121 :    
122 :     fun updateCellClass SSA =
123 :     let val {cellClass,...} = getInfo SSA
124 :     in fn (v,c) => DA.update(cellClass,v,c) end
125 :    
126 :     fun newVar SSA =
127 :     let val {cellClass,nameTable,...} = getInfo SSA
128 :     in fn c => let val r = C.newReg()
129 :     in DA.update(cellClass,r,c); r end
130 :     end
131 :    
132 :     fun newRenamedVar subscriptTable SSA =
133 :     let val {cellClass,nameTable,...} = getInfo SSA
134 :     fun f r =
135 :     let val r' = C.newReg()
136 :     in DA.update(cellClass,r',DA.sub(cellClass,r)); r' end
137 :     fun g subscriptTable r =
138 :     let val r' = C.newReg()
139 :     val i = A.sub(subscriptTable,r)
140 :     in DA.update(cellClass,r',DA.sub(cellClass,r));
141 :     A.update(subscriptTable,r,i+1);
142 :     (* print("[ r"^Int.toString r'^" -> "^
143 :     Int.toString r^"."^Int.toString i^"] \n"); *)
144 :     HA.update(nameTable,r',(r,i));
145 :     r'
146 :     end
147 :     in case subscriptTable of
148 :     SOME t => g t
149 :     | NONE => f
150 :     end
151 :    
152 :     (*
153 :     * Create a new SSA graph
154 :     *)
155 :     fun newSSA(CFG as G.GRAPH cfg, dom) =
156 :     let val nextImmed = ref ~1
157 :     val constTable = HA.array'(37,fn _ => raise NoConst)
158 :     fun newImmed i =
159 :     let val v = !nextImmed
160 :     val _ = nextImmed := v - 1
161 :     in HA.update(constTable,v,SP.IMMED i); v end
162 :     val immTable = HA.array''(37,newImmed)
163 :     val labTable = HashTable.create{== = SU.eqLabel,hash=SU.hashLabel,
164 :     size=37,exn=NoLabel}
165 :     val opnTable = HashTable.create{== = SP.eqOpn,hash=SP.hashOpn,
166 :     size=37,exn=NoOperand}
167 :     val ENTRY = hd(#entries cfg ())
168 :     val uninit = C.newReg()
169 :     val defSite = DA.array(37,uninit)
170 :     val cellClass = DA.array(C.maxCell(),C.GP)
171 :     val nameTable = HA.array'(13,fn _ => raise NoName)
172 :     val info = INFO{cfg = CFG,
173 :     dom = dom,
174 :     immTable = immTable,
175 :     labTable = labTable,
176 :     opnTable = opnTable,
177 :     constTable = constTable,
178 :     defSite = defSite,
179 :     cellClass = cellClass,
180 :     nextImmed = nextImmed,
181 :     minPos = ref 0,
182 :     maxPos = ref 1000000,
183 :     nameTable = nameTable
184 :     }
185 :     val G.GRAPH ssa = GraphImpl.graph("SSA",info,30)
186 :     val _ = #add_node ssa (uninit,SOURCE{b=ENTRY,t=[],t'=[]})
187 :     val _ = #set_entries ssa [uninit]
188 :     fun getDefs(OP{t,...}) = t
189 :     | getDefs(PHI{t,...}) = [t]
190 :     | getDefs(SOURCE{t,...}) = t
191 :     | getDefs(SINK _) = []
192 :     fun add_node(n,n') =
193 :     (DA.update(defSite,n,n);
194 :     app (fn r => DA.update(defSite,r,n)) (getDefs n');
195 :     #add_node ssa (n,n'))
196 :     fun node_info n = #node_info ssa (DA.sub(defSite,n))
197 :     fun remove_node n = #remove_node ssa (DA.sub(defSite,n))
198 :     fun has_node n = #has_node ssa (DA.sub(defSite,n))
199 :    
200 :     val SSA =
201 :     G.GRAPH
202 :     { name = #name ssa,
203 :     graph_info = #graph_info ssa,
204 :     new_id = #new_id ssa,
205 :     add_node = add_node,
206 :     add_edge = #add_edge ssa,
207 :     remove_node = remove_node,
208 :     set_in_edges = #set_in_edges ssa,
209 :     set_out_edges = #set_out_edges ssa,
210 :     set_entries = #set_entries ssa,
211 :     set_exits = #set_exits ssa,
212 :     garbage_collect = #garbage_collect ssa,
213 :     nodes = #nodes ssa,
214 :     edges = #edges ssa,
215 :     order = #order ssa,
216 :     size = #size ssa,
217 :     capacity = #capacity ssa,
218 :     out_edges = #out_edges ssa,
219 :     in_edges = #in_edges ssa,
220 :     succ = #succ ssa,
221 :     pred = #pred ssa,
222 :     has_edge = #has_edge ssa,
223 :     has_node = has_node,
224 :     node_info = node_info,
225 :     entries = #entries ssa,
226 :     exits = #exits ssa,
227 :     entry_edges = #entry_edges ssa,
228 :     exit_edges = #exit_edges ssa,
229 :     forall_nodes = #forall_nodes ssa,
230 :     forall_edges = #forall_edges ssa
231 :     }
232 :     val _ = app (fn i => (immed SSA i; ())) [0,1]
233 :     in SSA
234 :     end
235 :    
236 :     (*
237 :     * Signal that the SSA graph has changed
238 :     *)
239 :     fun changed SSA = ()
240 :    
241 :     (*
242 :     * Extract the nodes in an SSA graph in a table form.
243 :     * Convenient for scanning.
244 :     *)
245 :     fun nodes (SSA as G.GRAPH ssa) =
246 :     let val CFG as G.GRAPH cfg = cfg SSA
247 :     val N = #capacity cfg ()
248 :     val T = A.array(N,{source=[],phis=[],ops=[],sink=[]})
249 :     fun ins(x as (_,n')) =
250 :     case n' of
251 :     SOURCE{b,...} =>
252 :     let val {source,phis,ops,sink} = A.sub(T,b)
253 :     in A.update(T,b,{source=x::source,phis=phis,ops=ops,sink=sink})
254 :     end
255 :     | PHI{b,...} =>
256 :     let val {source,phis,ops,sink} = A.sub(T,b)
257 :     in A.update(T,b,{source=source,phis=x::phis,ops=ops,sink=sink})
258 :     end
259 :     | OP{b,...} =>
260 :     let val {source,phis,ops,sink} = A.sub(T,b)
261 :     in A.update(T,b,{source=source,phis=phis,ops=x::ops,sink=sink})
262 :     end
263 :     | SINK{b,...} =>
264 :     let val {source,phis,ops,sink} = A.sub(T,b)
265 :     in A.update(T,b,{source=source,phis=phis,ops=ops,sink=x::sink})
266 :     end
267 :     fun byPos((_,OP{p=p1,...}),(_,OP{p=p2,...})) = p1 < p2
268 :     | byPos _ = error "byPos"
269 :     fun sort {source,phis,ops,sink} =
270 :     {source=source,phis=phis,ops=Sorting.sort byPos ops,sink=sink}
271 :     in #forall_nodes ssa ins;
272 :     A.modify sort T;
273 :     T
274 :     end
275 :    
276 :     (*
277 :     * Graph viewing
278 :     *)
279 :     fun show_val SSA =
280 :     let val cellClass = cellClass SSA
281 :     val const = const SSA
282 :     val {nameTable,...} = getInfo SSA
283 :     fun lookupName v =
284 :     let val c = cellClass v
285 :     in let val (r,i) = HA.sub(nameTable,v)
286 :     in C.cellToString(r,c)^"."^Int.toString i end
287 :     handle NoName => C.cellToString(v,c)
288 :     end
289 :     fun reg v =
290 :     if v >= 0 then lookupName v
291 :     else case const v of
292 :     SP.IMMED i => if i < 0 then "-"^Int.toString(~i)
293 :     else Int.toString i
294 :     | SP.LABEL l => Label.nameOf l
295 :     | SP.OPERAND _ => "v"^Int.toString(~v)
296 :     in reg end
297 :    
298 :     fun show_op SSA =
299 :     let val show_val = show_val SSA
300 :     val regmap = CFG.regmap(cfg SSA)
301 :     val asm = FormatInsn.toString regmap
302 :     val K = 5
303 :     fun block b = "b"^Int.toString b
304 :     fun regs([b],[v]) = "["^block b^"]"^show_val v
305 :     | regs(b::bs,v::vs) = "["^block b^"]"^show_val v^","^regs(bs,vs)
306 :     | regs _ = ""
307 :     fun regs' vs =
308 :     let fun f(_,[]) = ""
309 :     | f(0,vs) = "\n "^f(K,vs)
310 :     | f(n,[v]) = show_val v
311 :     | f(n,v::vs) = show_val v ^","^f(n-1,vs)
312 :     in f(K,vs) end
313 :     fun show(OP{e,i,s,t,b,...}) =
314 :     asm i ^" ["^
315 :     (case t of
316 :     [] => ""
317 :     | _ => regs' t^" := "
318 :     )^E.toString (map show_val s) e^"]"
319 :     | show(PHI{preds,t,s,b,...}) = show_val t^" := phi("^regs(preds,s)^")"
320 :     | show(SOURCE{t,b,...}) = "source["^block b^"]("^regs' t^")"
321 :     | show(SINK{s,b,...}) = "sink["^block b^"]("^regs' s^")"
322 :     in show
323 :     end
324 :    
325 :     fun ssaStyle SSA =
326 :     let val show_op = show_op SSA
327 :     val show_val = show_val SSA
328 :     fun graph _ = []
329 :     fun node(_,bb) = [L.LABEL(show_op bb)]
330 :     fun edge(_,_,v) = [L.COLOR "red",L.LABEL(show_val v)]
331 :     in { graph = graph,
332 :     node = node,
333 :     edge = edge
334 :     }
335 :     end
336 :    
337 :     fun cfgStyle SSA =
338 :     let val {graph,node,edge} = CFG.viewStyle(cfg SSA)
339 :     val nodes = nodes SSA
340 :     val show_op = show_op SSA
341 :     fun node(b,b') =
342 :     let val {source,phis,ops,sink} = A.sub(nodes,b)
343 :     val text = String.concat(map (fn (_,i) => show_op i^"\n")
344 :     (source @ phis @ ops @ sink))
345 :     in [L.LABEL(CFG.headerText b'^text)]
346 :     end
347 :     in { graph = graph,
348 :     node = node,
349 :     edge = edge
350 :     }
351 :     end
352 :    
353 :     fun displayView(SSA as G.GRAPH ssa) =
354 :     let val defSite = defSite SSA
355 :    
356 :     fun dst(PHI{t,...}) = [t]
357 :     | dst(OP{t,...}) = t
358 :     | dst(SOURCE{t,...}) = t
359 :     | dst(SINK _) = []
360 :    
361 :     fun out_edges i =
362 :     let val defs = dst(#node_info ssa i)
363 :     in foldr (fn (d,l) => map (fn (_,j,r) => (i,j,r))
364 :     (#out_edges ssa d) @ l) [] defs
365 :     end
366 :    
367 :     fun in_edges i = map (fn (i,j,r) => (defSite i,j,r)) (#in_edges ssa i)
368 :    
369 :     fun forall_edges f = #forall_edges ssa (fn (i,j,e) => f(defSite i,j,e))
370 :    
371 :     val ssa' = G.GRAPH
372 :     { name = "SSACFG",
373 :     graph_info = #graph_info ssa,
374 :     new_id = G.unimplemented,
375 :     add_node = G.unimplemented,
376 :     add_edge = G.unimplemented,
377 :     remove_node = G.unimplemented,
378 :     set_in_edges = G.unimplemented,
379 :     set_out_edges = G.unimplemented,
380 :     set_entries = G.unimplemented,
381 :     set_exits = G.unimplemented,
382 :     garbage_collect = G.unimplemented,
383 :     nodes = #nodes ssa,
384 :     edges = #edges ssa,
385 :     order = #order ssa,
386 :     size = #size ssa,
387 :     capacity = #capacity ssa,
388 :     out_edges = out_edges,
389 :     in_edges = in_edges,
390 :     succ = fn i => map (fn (_,j,_) => j) (out_edges i),
391 :     pred = fn j => map (fn (i,_,_) => i) (in_edges j),
392 :     has_edge = G.unimplemented,
393 :     has_node = #has_node ssa,
394 :     node_info = #node_info ssa,
395 :     entries = #entries ssa,
396 :     exits = #exits ssa,
397 :     entry_edges = #entry_edges ssa,
398 :     exit_edges = #exit_edges ssa,
399 :     forall_nodes = #forall_nodes ssa,
400 :     forall_edges = forall_edges
401 :     }
402 :     in Subgraph_P_View.subgraph_p_view
403 :     (map #1 (#nodes ssa ()))
404 :     (fn _ => true)
405 :     (fn (i,j) =>
406 :     case (#node_info ssa i, #node_info ssa j) of
407 :     (SOURCE _,SINK _) => false
408 :     | _ => true)
409 :     ssa'
410 :     end
411 :    
412 :     fun viewAsSSA SSA = L.makeLayout (ssaStyle SSA) (displayView SSA)
413 :     fun viewAsCFG SSA = L.makeLayout (cfgStyle SSA) (cfg SSA)
414 :    
415 :     (*
416 :     * Function that replaces all uses of one value with another.
417 :     * The instruction that defines the original value is still around
418 :     * undeleted, but can be deleted subsequently with dead code elimination.
419 :     *)
420 :     fun replaceAllUses(G.GRAPH ssa) =
421 :     let fun replace{from,to} =
422 :     let fun rn regs = map (fn r => if r = from then to else r) regs
423 :     fun upd(OP{s,t,i,e,p,b}) = OP{s=rn s,t=t,i=i,e=e,p=p,b=b}
424 :     | upd(PHI{preds,s,t,t',b}) = PHI{preds=preds,s=rn s,t=t,t'=t',b=b}
425 :     | upd(SINK{b,s,s'}) = SINK{b=b,s=rn s,s'=s'}
426 :     | upd(SOURCE _) = error "replaceAllUses"
427 :     fun renameUse(_,j,x) =
428 :     let val ssa_op = #node_info ssa j
429 :     in #add_edge ssa (to,j,to);
430 :     #add_node ssa (j,upd ssa_op)
431 :     end
432 :     in app renameUse (#out_edges ssa from);
433 :     #set_out_edges ssa (from,[]);
434 :     true
435 :     end
436 :     in replace
437 :     end
438 :    
439 :     (*
440 :     * Function that replaces all uses of one value by a copy of another.
441 :     *)
442 :     fun replaceByCopy (G.GRAPH ssa) =
443 :     let fun replace{from,to} =
444 :     if from = to then false
445 :     else
446 :     let val INFO{cellClass,minPos,maxPos,...} = #graph_info ssa
447 :     val (pos,block,ok) =
448 :     case #node_info ssa from of
449 :     OP{p,b,t=[_],...} => (p,b,true)
450 :     | PHI{b,...} => (!minPos,b,true) before minPos := !minPos - 1
451 :     | OP{p,b,...} => (p,b,false)
452 :     | SOURCE{b,...} => (0,b,false)
453 :     | SINK{b,...} => error "replaceByCopy"
454 :     in ok andalso
455 :     let val copy = hd(SP.copies[{class=DA.sub(cellClass,from),
456 :     src=to,dst=from}])
457 :     val ssa_op = OP{i=copy,e=E.COPY,s=[to],t=[from],b=block,p=pos}
458 :     in #add_node ssa (from,ssa_op); true
459 :     end
460 :     end
461 :     in replace
462 :     end
463 :    
464 :     (*
465 :     * Fold constant value
466 :     *)
467 :     fun foldConstant(SSA as G.GRAPH ssa) =
468 :     let val INFO{constTable,defSite,...} = #graph_info ssa
469 :     val show_op = show_op SSA
470 :     val {low,high} = SP.immedRange
471 :     fun fold{value,const} =
472 :     case HA.sub(constTable,const) of
473 :     SP.IMMED k =>
474 :     let val i = DA.sub(defSite,value)
475 :     in case #node_info ssa i of
476 :     OP{e=E.LI,...} => false (* already a constant *)
477 :     | i' as OP{t=[_],p,b,...} =>
478 :     if low <= k andalso k <= high then
479 :     let val i'' = OP{e=E.LI,t=[value],s=[const],p=p,b=b,
480 :     i=SP.loadImmed{immed=k,t=value}
481 :     }
482 :     in #set_in_edges ssa (value,[]);
483 :     #add_node ssa (value,i'');
484 :     true
485 :     end
486 :     else false
487 :     | _ => false
488 :     end
489 :     | _ => false
490 :     in fold
491 :     end
492 :    
493 :     (*
494 :     * Set conditional branch
495 :     *)
496 :     fun setBranch(SSA as G.GRAPH ssa) =
497 :     let val label = label SSA
498 :     fun set{jmp=(i,OP{e=E.BRANCH _,b,p,...}),cond} =
499 :     let val CFG as G.GRAPH cfg = cfg SSA
500 :     fun change([],es',target,elim) = (es',target,elim)
501 :     | change((i,j,CFG.EDGE{k=CFG.BRANCH cond',w,a})::es,es',x,y) =
502 :     if cond' = cond then
503 :     change(es,(i,j,CFG.EDGE{k=CFG.JUMP,w=w,a=a})::es',j,y)
504 :     else
505 :     change(es,es',x,j)
506 :     | change _ = error "change"
507 :     val outEdges = #out_edges cfg b
508 :     val (outEdges',target,elim) = change(outEdges,[],~1,~1)
509 :     val lab=CFG.defineLabel(#node_info cfg target)
510 :     val jmp=OP{e=E.JMP(E.ID 0),i=P.jump lab,s=[label lab],t=[],b=b,p=p}
511 :     in if elim < 0 then error "setBranch: bad edges" else ();
512 :     #add_node ssa (i,jmp);
513 :     #set_in_edges ssa (b,[]);
514 :     #set_out_edges ssa (b,[]);
515 :     #set_out_edges cfg (b,outEdges');
516 :     CFG.changed CFG
517 :     end
518 :     | set _ = error "setBranch"
519 :     in set
520 :     end
521 :    
522 :     (*
523 :     * Move instruction from one block to another
524 :     *)
525 :     fun move(SSA as G.GRAPH ssa) =
526 :     let val INFO{dom,cfg,minPos,maxPos,...} = #graph_info ssa
527 :     val dom = dom cfg
528 :     val dominates = #dominates(Dom.methods dom)
529 :     fun mv{i=(id,OP{e,i,p,b,s,t}),block} =
530 :     if b = block then ()
531 :     else let val pos =
532 :     if dominates(block,b) then (* move upward? *)
533 :     (maxPos := !maxPos + 1; !maxPos)
534 :     else
535 :     (minPos := !minPos - 1; !minPos)
536 :     val i' = OP{e=e,i=i,p=pos,b=block,s=s,t=t}
537 :     in #add_node ssa (id,i')
538 :     end
539 :     | mv _ = error "move"
540 :     in mv
541 :     end
542 :     end
543 :    
544 :     (*
545 : monnier 227 * $Log$
546 : monnier 221 *)

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