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

Annotation of /sml/trunk/src/MLRISC/SSA/cfg2ssa.sml

Parent Directory Parent Directory | Revision Log Revision Log


Revision 744 - (view) (download)

1 : leunga 695 (*----------------------------------------------------------------------
2 :     * This module constructs an SSA graph from an control flow graph.
3 :     * The control flow graph is kept abstract so that we can specialize
4 :     * this module to various representations.
5 :     *
6 :     * Some improvements:
7 :     * 1. This implementation uses a variant Sreedhar et al.'s DJ-graph to compute
8 :     * the iterated dominance frontier. This variant computes liveness
9 :     * by demand at the same time DF^+ is computed. So there is no need
10 :     * to computing liveness using iterative dataflow analysis. The advantage
11 :     * is that |DF^+(S) \intersect Liveness| can be substantially smaller
12 :     * than |DF^+(S)| + |Liveness|, so in some situations much less work
13 :     * is performed.
14 :     * 2. We identify those registers that are only defined once in the
15 :     * compilation unit. These registers will not be given new names.
16 :     * This way we eliminate a lot of unncessary renaming!
17 :     * This is particular important since each renaming has to propagate
18 :     * along all the information associated with cellkinds (and/or gc types).
19 :     *
20 :     * -- Allen (leunga@cs.nyu.edu)
21 :     *----------------------------------------------------------------------*)
22 :     functor CFG2SSA
23 :     (structure SSA : SSA
24 :     structure InsnProps : INSN_PROPERTIES
25 :     sharing SSA.I = InsnProps.I
26 :     ) : CFG2SSA =
27 :     struct
28 :     structure SSA = SSA
29 :     structure CFG = SSA.CFG
30 :     structure Dom = SSA.Dom
31 :     structure SP = SSA.SP
32 :     structure RTL = SSA.RTL
33 :     structure T = RTL.T
34 :     structure P = SP.RTLProps
35 :     structure C = SSA.C
36 :     structure SL = SortedList
37 :     structure DJ = SSA.DJ
38 :     structure G = Graph
39 :     structure A = Array
40 :     structure W8A = Word8Array
41 : leunga 744 structure CDJ = CompressedDJGraph(Dom)
42 : leunga 695
43 :     fun error msg = MLRiscErrorMsg.error("CFG2SSA", msg)
44 :    
45 :     (*----------------------------------------------------------------------
46 :     * Common flags
47 :     *----------------------------------------------------------------------*)
48 :     val copyProp = MLRiscControl.getFlag "ssa-copy-prop"
49 :     val keepName = MLRiscControl.getFlag "ssa-keep-name"
50 :     val removeUselessPhis = MLRiscControl.getFlag "ssa-remove-useless-phis"
51 :     val consistencyCheck = MLRiscControl.getFlag "ssa-consistency-check"
52 :     val debugSSA = MLRiscControl.getFlag "ssa-debug"
53 :     val ssaStats = MLRiscControl.getFlag "ssa-stats"
54 :     val _ = copyProp := true (* by default, perform copy propagation *)
55 :     val _ = removeUselessPhis := true (* by default, remove useless phi-nodes *)
56 :     val debug = false
57 :    
58 : leunga 744 datatype ssa_variant =
59 :     MINIMAL | SEMI_PRUNED | PRUNED
60 :     | C_MINIMAL | C_PRUNED
61 :     val ssa_variant = C_PRUNED
62 : leunga 695 val add_entry = true
63 : leunga 744 val sanity_check = true
64 : leunga 695
65 :     (*
66 :     * Counters
67 :     *)
68 :     val phi_nodes = MLRiscControl.getCounter "phi-nodes"
69 :     val ssa_nodes = MLRiscControl.getCounter "ssa-nodes"
70 :    
71 :     exception NoName
72 :     exception NoLiveIn
73 :    
74 :     (*------------------------------------------------------------------
75 :     * Hacks to deal with zero registers in the architecture
76 :     *------------------------------------------------------------------*)
77 :     val zeroRegs = SSA.zeroRegs
78 :     fun isZero r = W8A.sub(zeroRegs,r) <> 0w0 handle _ => false
79 :    
80 :     (*------------------------------------------------------------------
81 :     * Deal with pinned resources
82 :     *------------------------------------------------------------------*)
83 :     val pinnedUseTbl = SSA.pinnedUseTbl
84 :     val pinnedDefTbl = SSA.pinnedDefTbl
85 :     fun isPinnedUse r = W8A.sub(pinnedUseTbl,r) <> 0w0 handle _ => false
86 :     fun isPinnedDef r = W8A.sub(pinnedDefTbl,r) <> 0w0 handle _ => false
87 :     fun hasPinnedUse [] = false
88 :     | hasPinnedUse (r::rs) = isPinnedUse r orelse hasPinnedUse rs
89 :     fun hasPinnedDef [] = false
90 :     | hasPinnedDef (r::rs) = isPinnedDef r orelse hasPinnedDef rs
91 :    
92 :     (*------------------------------------------------------------------
93 :     * Check if a variable is live in Entry
94 :     *------------------------------------------------------------------*)
95 :     fun addEntry(G.GRAPH cfg) =
96 :     if add_entry then
97 :     let val N = #capacity cfg ()
98 :     val liveIn = A.array(N, ~1)
99 :     val in_alpha = A.array(N, ~1)
100 :     val [ENTRY] = #entries cfg ()
101 :     val counter = ref 0
102 :     fun addEntry f {defs, localLiveIn} =
103 :     let val v = !counter
104 :     val _ = counter := !counter + 1
105 :     fun markLiveIn(b) =
106 :     let fun markPred [] = ()
107 :     | markPred((j,_,_)::es) =
108 :     (if A.sub(liveIn,j) <> v andalso
109 :     A.sub(in_alpha,j) <> v then
110 :     markLiveIn j
111 :     else ();
112 :     markPred es
113 :     )
114 :     in A.update(liveIn,b,v);
115 :     markPred(#in_edges cfg b)
116 :     end
117 :     fun markDef b = A.update(in_alpha, b, v)
118 :     fun addEntries([],defs) = defs
119 :     | addEntries((_,b,_)::es,defs) =
120 :     if A.sub(liveIn,b) = v then addEntries(es, b::defs)
121 :     else addEntries(es, defs)
122 :     in app markDef defs;
123 :     app markLiveIn localLiveIn;
124 :     f (addEntries(#out_edges cfg ENTRY, defs))
125 :     end
126 :     in addEntry
127 :     end
128 :     else (fn f => fn {defs, localLiveIn} => f defs)
129 :    
130 :    
131 :     (*----------------------------------------------------------------------
132 :     * Main function
133 :     *----------------------------------------------------------------------*)
134 :     fun buildSSA{cfg, dom} =
135 :     let (*------------------------------------------------------------------
136 :     * Flags
137 :     *------------------------------------------------------------------*)
138 :     val copyProp = !copyProp
139 :     val keepName = !keepName
140 :    
141 :     (* extracts the gc map *)
142 :     val gcmap = #get SSA.GCMap.GCMAP (!(CFG.annotations cfg))
143 :    
144 :     (* create a name table if we want to keep around the original name *)
145 : leunga 744 val nameTbl = if keepName then
146 :     SOME(IntHashTable.mkTable(37, NoName)) else NONE
147 : leunga 695 val SSA = SSA.newSSA{cfg=cfg, dom=dom,
148 :     nameTbl=nameTbl, gcmap=gcmap}
149 :     val cellKindTbl = SSA.cellKindTbl SSA
150 : leunga 744 val addCellKind = IntHashTable.insert cellKindTbl
151 : leunga 695 val regmap = C.lookup (CFG.regmap cfg)
152 :     val maxPos = SSA.maxPos SSA
153 :    
154 :     (*------------------------------------------------------------------
155 :     * Graph structures and tables
156 :     *------------------------------------------------------------------*)
157 :     val Dom as G.GRAPH dom = dom cfg
158 :     val N = #capacity dom () (* number of blocks *)
159 :     val V = C.maxCell() (* max variable id *)
160 :     val CFG as G.GRAPH cfg = Dom.cfg Dom
161 :     val DU = A.array(N, [])
162 :     val localLiveIn = A.array(V, [])
163 :     val G.GRAPH ssa = SSA
164 :     val startId = #order ssa ()
165 :     val ssaOpsCount = ref startId
166 :     val showOp = SSA.showOp SSA
167 :     val showVal = SSA.showVal SSA
168 :     val [ENTRY] = #entries cfg ()
169 :     val [EXIT] = #exits cfg ()
170 :    
171 :     (*------------------------------------------------------------------
172 :     * Special instructions
173 :     *------------------------------------------------------------------*)
174 :     val phiOp = SP.phi
175 :     val sinkOp = SP.sink
176 :     val sourceOp = SP.source
177 :    
178 :     (*------------------------------------------------------------------
179 :     * Propagate gc info
180 :     *------------------------------------------------------------------*)
181 :     val propagateGCInfo =
182 :     case gcmap of
183 :     NONE => (fn _ => ())
184 :     | SOME map =>
185 : leunga 744 let val lookup = IntHashTable.lookup map
186 :     val add = IntHashTable.insert map
187 : leunga 695 in fn {from, to} =>
188 :     (lookup to; ()) handle _ =>
189 :     (add(to, lookup from) handle _ => ())
190 :     end
191 :    
192 :     (*------------------------------------------------------------------
193 :     * Check for initial and terminal blocks
194 :     *------------------------------------------------------------------*)
195 :     fun isInitial b = b = ENTRY orelse b <> EXIT andalso
196 :     List.exists(fn (i, _, _) => i=ENTRY) (#in_edges cfg b)
197 :     fun isTerminal b = b <> ENTRY andalso
198 :     List.exists(fn (_, i, _) => i=EXIT) (#out_edges cfg b)
199 :     fun hasSource b = List.exists(fn (i, _, _) => i=ENTRY) (#in_edges cfg b)
200 :    
201 :     (*------------------------------------------------------------------
202 :     * Initialize cellkinds of physical registers
203 :     *------------------------------------------------------------------*)
204 :     fun initCellKinds() =
205 :     app (fn k =>
206 :     let val {low, high} = C.cellRange k
207 :     fun loop r =
208 :     if r <= high then (addCellKind(r,k); loop(r+1))
209 :     else ()
210 :     in loop low end
211 :     handle _ => ()
212 :     ) C.cellkinds
213 :    
214 :     (*------------------------------------------------------------------
215 :     * How to get the live out of an exit block.
216 :     * Remove all zero registers from the liveOut!
217 :     *------------------------------------------------------------------*)
218 :     fun getLiveOut(b,block) =
219 :     SL.uniq(
220 :     List.foldr
221 :     (fn (r,S) =>
222 :     let val r = regmap r
223 :     in if isZero r then S else r::S end)
224 : leunga 744 [] (C.CellSet.toCellList(CFG.liveOut block))
225 : leunga 695 )
226 :    
227 :     (*------------------------------------------------------------------
228 :     * Initialize all the special tables
229 :     *------------------------------------------------------------------*)
230 :     fun initTables() =
231 : leunga 744 let val getOperands =
232 :     P.defUse(SP.OT.makeNewValueNumbers(SSA.operandTbl SSA))
233 : leunga 695 fun getRegs([], rs) = rs
234 :     | getRegs(v::vs, rs) = getRegs(vs, if v >= 0 then v::rs else rs)
235 :     val updateCellKind = P.updateCellKind{update=addCellKind}
236 :    
237 :     (* A source node for each entry, and a sink node for each exit *)
238 :     val _ = ssaOpsCount := !ssaOpsCount +
239 :     length(#entries cfg ()) +
240 :     length(#exits cfg ()) +
241 :     1 (* ENTRY node *)
242 :    
243 :     (* Compute def/use
244 :     * Also, create the instructions.
245 :     *)
246 :     fun defUse(b,b') =
247 :     let fun scan([], du, def, use) = (du, def, use)
248 :     | scan(insn::insns, du, def, use) =
249 :     (updateCellKind insn;
250 :     let val (d,u) = getOperands insn
251 :     val d' = SL.uniq d
252 :     val u' = SL.uniq(getRegs(u,[]))
253 :     val use = SL.merge(SL.difference(use,d'),u')
254 :     val def = SL.difference(SL.merge(def,d'),u')
255 :     in scan(insns, (d,u)::du, def, use) end
256 :     )
257 :     val liveOut = getLiveOut(b,b')
258 :     val (du, def, use) = scan(!(CFG.insns b'),[],[],liveOut)
259 :     in A.update(DU, b, du);
260 :     ssaOpsCount := !ssaOpsCount + length du; (* count the instrs *)
261 :     (def, use)
262 :     end
263 :    
264 :     fun enterLocalLiveInInfo(b,b') =
265 :     let fun mark [] = ()
266 :     | mark(r::rs) =
267 :     (A.update(localLiveIn,r,b::A.sub(localLiveIn,r)); mark rs)
268 :     val (_,use) = defUse(b,b')
269 :     in mark use
270 :     end
271 :    
272 :     in #forall_nodes cfg enterLocalLiveInInfo
273 :     end
274 :    
275 :     (*------------------------------------------------------------------
276 :     * Definitions inside a block.
277 :     *------------------------------------------------------------------*)
278 :     fun defsOf(b) =
279 :     let val defs =
280 :     foldr (fn ((d,_),l) => List.revAppend(d,l)) [] (A.sub(DU,b))
281 :     in SL.uniq defs
282 :     end
283 :    
284 :     (*------------------------------------------------------------------
285 :     * How to rename a variable
286 :     *------------------------------------------------------------------*)
287 :     val renameVar = SSA.newRenamedVar SSA
288 :    
289 :     (*------------------------------------------------------------------
290 :     * Compute the locations of all phi-functions based on the
291 :     * definition site information. We also prune out non-live phi
292 :     * functions at the same time. Note that even after pruning the
293 :     * set of phi-functions may still be an overestimate, because of
294 :     * copy propagation.
295 :     *------------------------------------------------------------------*)
296 :     fun placePhiFunctions() =
297 :     let val defSites = A.array(V, []) (* variable -> blocks *)
298 :     val phis = A.array(N, []) (* block -> phi functions *)
299 :     val prList = List.foldr (fn (r,"") => Int.toString r
300 :     | (r,s) => Int.toString r^","^s) ""
301 :     val _ = #forall_nodes cfg
302 :     (fn (b,_) =>
303 :     app (fn v => A.update(defSites,v,b::A.sub(defSites,v)))
304 :     (defsOf b))
305 :     val LiveIDFs =
306 :     case ssa_variant of
307 : leunga 744 MINIMAL => let val IDFs = DJ.IDFs(DJ.DJ Dom)
308 : leunga 695 val addEntry = addEntry CFG
309 :     in addEntry IDFs end
310 :     | SEMI_PRUNED => let val IDFs = DJ.IDFs(DJ.DJ Dom)
311 :     in fn {defs,localLiveIn=[]} => []
312 :     | {defs,localLiveIn} => IDFs defs
313 :     end
314 :     | PRUNED => DJ.LiveIDFs(DJ.DJ Dom)
315 : leunga 744 | C_MINIMAL => let val IDFs = CDJ.IDFs(CDJ.DJ Dom)
316 :     val addEntry = addEntry CFG
317 :     in addEntry IDFs end
318 :     | C_PRUNED => if sanity_check then
319 :     let val dj1 = CDJ.LiveIDFs(CDJ.DJ Dom)
320 : leunga 695 val dj2 = DJ.LiveIDFs(DJ.DJ Dom)
321 :     in fn x =>
322 :     let val idf1 = dj1 x
323 :     val idf2 = dj2 x
324 :     fun pr s = foldr (fn (x,l) =>
325 :     Int.toString x^" "^l) "" s
326 :     in if SL.uniq idf1 = SL.uniq idf2 then idf1
327 :     else (print("IDF1="^pr idf1^"\n");
328 :     print("IDF2="^pr idf2^"\n");
329 :     idf1)
330 :     end
331 :     end
332 : leunga 744 else CDJ.LiveIDFs(CDJ.DJ Dom)
333 : leunga 695 fun insertPhi(v, [], n) = n
334 :     | insertPhi(v, defSites, n) =
335 :     let fun insert([], n) = n
336 :     | insert(b::bs, n) =
337 :     (A.update(phis, b, (v,v,[])::A.sub(phis, b));
338 :     insert(bs, n+1)
339 :     )
340 :     val blocks = LiveIDFs{defs=defSites,
341 :     localLiveIn=A.sub(localLiveIn,v)}
342 :     (* val _ = print("r"^Int.toString v^" defs="^prList defSites
343 :     ^" IDF="^prList blocks^"\n")*)
344 :     in insert(blocks, n)
345 :     end
346 :     in ssaOpsCount :=
347 :     A.foldri insertPhi (!ssaOpsCount) (defSites,0,NONE);
348 :     phis
349 :     end
350 :    
351 :     (*------------------------------------------------------------------
352 :     * Compute the SSA form by walking the dominator tree and renaming
353 :     * all definitions in the program. We also do a few things in the
354 :     * process:
355 :     *
356 :     * (1) Keep track of live in variables in each entry point.
357 :     * These are found by looking at the renaming stack. If
358 :     * the renaming stack is empty at the time of lookup, the
359 :     * value being looked up is a live in value.
360 :     *
361 :     *------------------------------------------------------------------*)
362 :     fun walkTree() =
363 :     let val phis = placePhiFunctions() (* compute the phi functions *)
364 :     val stacks = A.array(V, []) (* renaming stack *)
365 :     val preds = A.array(N, []) (* predecessors of block N;
366 :     must be in the same order as the
367 :     arguments of phi-functions *)
368 : leunga 744 val liveInSets = IntHashTable.mkTable(3, NoLiveIn)
369 :     val lookupLiveInSet = IntHashTable.lookup liveInSets
370 : leunga 695
371 :     val dominatingEntries = Dom.entryPos Dom
372 :    
373 :     (* Create the liveIn sets *)
374 :     val _ = app (fn Z =>
375 : leunga 744 IntHashTable.insert liveInSets
376 :     (Z, IntHashTable.mkTable(32,NoLiveIn))
377 : leunga 695 ) (#succ dom ENTRY)
378 :    
379 :     val defCounts = W8A.array(V, 0w1) (* count # of definitions *)
380 :    
381 :     (* Various tables *)
382 :     val _ = SSA.reserve SSA (!ssaOpsCount); (* reserve space *)
383 :     val newOp = SSA.newOp SSA
384 :    
385 :     (* Get a new name *)
386 :     fun newName v =
387 :     if W8A.sub(defCounts,v) = 0w0
388 :     then (W8A.update(defCounts,v,0w1); v)
389 :     else renameVar v
390 :    
391 :     (* Reset the renaming stack *)
392 :     fun reset [] = ()
393 :     | reset(v::vs) =
394 :     let val _::tl = A.sub(stacks,v)
395 :     in A.update(stacks, v, tl);
396 :     reset vs
397 :     end
398 :    
399 :     val SOME infPos = Int.maxInt
400 :     val SOME neginfPos = Int.minInt
401 :    
402 :     (* Add a new live in register r with new name v in block Y.
403 :     * We either have to add a new entry in the liveInSet or insert
404 :     * a new phi-node.
405 :     *)
406 :     fun addLiveIn(r,Y) =
407 :     let val L = lookupLiveInSet Y
408 : leunga 744 in IntHashTable.lookup L r handle _ =>
409 : leunga 695 let val v = newName r
410 : leunga 744 val _ = IntHashTable.insert L (r,v)
411 : leunga 695 in if isInitial Y then ()
412 :     else (* Y is not an ENTRY; add phi node *)
413 :     let fun addPreds([], vs') = rev vs'
414 :     | addPreds(Z::Zs, vs') =
415 :     let val W = A.sub(dominatingEntries, Z)
416 :     val v' = addLiveIn(r,W)
417 :     in addPreds(Zs, v'::vs')
418 :     end
419 :     val preds = A.sub(preds, Y)
420 :     val vs' = addPreds(preds, [])
421 :     in (* print("["^Int.toString Y^"] live in phi "^
422 :     showVal r^"\n"); *)
423 :     A.update(phis, Y, (r, v, vs')::A.sub(phis, Y));
424 :     ssaOpsCount := !ssaOpsCount + 1
425 :     end;
426 :     v
427 :     end
428 :     end
429 :    
430 :     (* Add live in at entry *)
431 :     (* val addLiveIn = fn(r,Y) => addLiveIn(r,ENTRY) *)
432 :    
433 :     (* Rename block X.
434 :     * Y is the block that is immediately dominated by ENTRY and
435 :     * dominates X.
436 :     *)
437 :     fun walk(X, Y, ssa_id) =
438 :     let val oldDefs = ref []
439 :    
440 :     (* Lookup the current name for v *)
441 :     fun lookup v =
442 :     case A.sub(stacks,v) of
443 :     [] => addLiveIn(v, Y) (* v is live in *)
444 :     | v'::_ => v'
445 :    
446 :     (* Rename uses by looking up from the renaming stack *)
447 :     and renameUse v = if v < 0 then v else lookup v
448 :     and renameUses [] = []
449 :     | renameUses (v::vs) = renameUse v::renameUses vs
450 :    
451 :     (* Rename a definition of v.
452 :     * We'll try to keep the original name whenever possible.
453 :     * For example, if the original name has only one definition;
454 :     * then we don't have to rename it at all.
455 :     *
456 :     * For zero registers, make sure we don't create a new definition
457 :     *)
458 :     and renameDef v =
459 :     let val v' = newName v
460 :     in if isZero v then v'
461 :     else
462 :     let val vs = A.sub(stacks,v)
463 :     in A.update(stacks,v,v'::vs);
464 :     oldDefs := v :: !oldDefs;
465 :     v'
466 :     end
467 :     end
468 :    
469 :     and renameDefs [] = []
470 :     | renameDefs (v::vs) = renameDef v::renameDefs vs
471 :    
472 :     fun copyDef(dst,src) =
473 :     (propagateGCInfo{from=dst,to=src};
474 :     A.update(stacks,dst,src::A.sub(stacks,dst));
475 :     oldDefs := dst :: !oldDefs
476 :     )
477 :    
478 :     (* parallel copies *)
479 :     fun copy{dst, src} =
480 :     ((* print("Copying ");
481 :     app (fn r => print(Int.toString r^" ")) dst;
482 :     print "<- ";
483 :     app (fn r => print(Int.toString r^" ")) src;
484 :     print "\n"; *)
485 :     ListPair.app copyDef (dst, map lookup src)
486 :     )
487 :    
488 :     (* rename the definition of a phi function *)
489 :     fun renamePhiDef X =
490 :     let fun rn [] = []
491 :     | rn((v',v,uses)::rest) = (v',renameDef v,uses)::rn rest
492 :     in A.update(phis, X, rn(A.sub(phis,X))) end
493 :    
494 :     (* simplify parallel copies *)
495 :     fun simplifyCopies(dst, src) =
496 :     let fun loop(d::ds, s::ss, dst, src) =
497 :     if d = s then loop(ds, ss, dst, src)
498 :     else loop(ds, ss, d::dst, s::src)
499 :     | loop(_, _, dst, src) = (dst, src)
500 :     in loop(dst, src, [], []) end
501 :    
502 :     (*
503 :     * Insert a sink node into the ssa graph
504 :     *)
505 :     fun addSink(id, block) =
506 :     let val liveOut = getLiveOut(X, block)
507 :     val uses = renameUses liveOut
508 :     in newOp{id=id, instr=sinkOp, pos=infPos,
509 :     block=X, defs=[], uses=uses,
510 :     rtl=T.SINK{block=X, liveOut=liveOut}
511 :     };
512 :     if debug then print("new "^showOp id^"\n") else ();
513 :     #set_exits ssa (id:: #exits ssa ());
514 :     id + 1
515 :     end
516 :    
517 :     (* rename the instructions in block X *)
518 :     fun renameBlock(X, ssa_id) =
519 :     let (* scan blocks, rename instructions and add new ssa ops *)
520 :     fun scan(id, i::insns, pos, (defs, uses)::DU) =
521 :     let fun addOp(instr,defs,uses,p) =
522 :     let val rtl = P.rtl instr
523 :     val rtl = if hasPinnedUse uses orelse
524 :     hasPinnedDef defs then
525 :     RTL.pin rtl else rtl
526 :     val uses = renameUses uses
527 :     val defs = renameDefs defs
528 :     in newOp{id=id,instr=instr,defs=defs,uses=uses,
529 :     rtl=rtl, block=X, pos=p};
530 :     if debug then print("new "^showOp id^"\n")
531 :     else ();
532 :     scan(id+1, insns, pos+128, DU)
533 :     end
534 :     in case InsnProps.instrKind i of
535 :     InsnProps.IK_COPY =>
536 : leunga 744 (* copy propagation *)
537 : leunga 695 (copy{dst=defs, src=uses};
538 :     scan(id, insns, pos, DU)
539 :     )
540 :     | InsnProps.IK_JUMP => addOp(i,defs,uses,infPos)
541 :     | _ => addOp(i,defs,uses,pos)
542 :     end
543 :     | scan(id, _, pos, _) = (id, pos)
544 :    
545 :     val block = #node_info cfg X
546 :     val insns = !(CFG.insns block)
547 :     val DU = A.sub(DU,X)
548 :    
549 :     val (ssa_id, pos) = scan(ssa_id, rev insns, 0, DU)
550 :     val ssa_id = if isTerminal X then addSink(ssa_id, block)
551 :     else ssa_id
552 :     in maxPos := Int.max(!maxPos, pos);
553 :     ssa_id
554 :     end
555 :    
556 :     (* rename the uses of a phi function *)
557 :     fun renamePhiUse X =
558 :     let fun rename_phi_of_Y (e as (X,Y,_)) =
559 :     let val Y_phis = A.sub(phis, Y)
560 :     fun insertUses [] = []
561 :     | insertUses((v',v,uses)::rest) =
562 :     ((*print("["^Int.toString X^"->"^Int.toString Y^
563 :     "] Renaming phi "^Int.toString v'^"\n");*)
564 :     (v',v,renameUse v'::uses)::insertUses rest)
565 :     in A.update(preds,Y,X::A.sub(preds,Y));
566 :     A.update(phis,Y,insertUses Y_phis)
567 :     end
568 :     in app rename_phi_of_Y (#out_edges cfg X) end
569 :    
570 :     val _ = renamePhiDef X
571 :     val ssa_id = renameBlock(X, ssa_id)
572 :     val _ = renamePhiUse X
573 :    
574 :     fun walkSucc([], _, ssa_id) = ssa_id
575 :     | walkSucc(X::Xs, Y, ssa_id) =
576 :     walkSucc(Xs, Y, walk(X, Y, ssa_id))
577 :    
578 :     val ssa_id = walkSucc(#succ dom X, Y, ssa_id)
579 :     in reset (!oldDefs);
580 :     ssa_id
581 :     end
582 :    
583 :     fun walkAll([], ssa_id) = ssa_id
584 :     | walkAll(X::Xs, ssa_id) = walkAll(Xs, walk(X, X, ssa_id))
585 :    
586 :     (*
587 :     * Insert a source definitions for all zero registers
588 :     *)
589 :     fun addZeroRegs(ENTRY) =
590 : leunga 744 let val L = IntHashTable.mkTable(16,NoLiveIn)
591 :     val add = IntHashTable.insert L
592 : leunga 695 fun defineZero(k) =
593 :     case C.zeroReg k of
594 :     SOME r => let val v = newName r
595 :     in add(r,v);
596 :     A.update(stacks,r,[v])
597 :     end
598 :     | NONE => ()
599 : leunga 744 in IntHashTable.insert liveInSets (ENTRY, L);
600 : leunga 695 app defineZero C.cellkinds
601 :     end
602 :    
603 :     val _ = addZeroRegs ENTRY
604 :    
605 :     (* Insert all normal nodes first *)
606 :     val ssa_id = ref(walkAll(#succ dom ENTRY, startId))
607 :    
608 :     (*
609 :     * Insert a source node into the ssa graph.
610 :     *)
611 :     fun addSource(X, liveInSet) =
612 :     if isInitial X then
613 : leunga 744 let val LiveIn = IntHashTable.listItemsi liveInSet
614 : leunga 695 val liveInSet =
615 :     ListMergeSort.sort (fn ((i,_),(j,_)) => i < j) LiveIn
616 :    
617 :     fun mark([], regs, defs) = (regs, defs)
618 :     | mark((r,d)::l, regs, defs) =
619 :     mark(l, r::regs, d::defs)
620 :    
621 :     val (regs, defs) = mark(liveInSet, [], [])
622 :     val id = !ssa_id
623 :    
624 :     in (* print("LiveIn["^Int.toString X^"] = ");
625 :     app (fn (r,v) =>
626 :     print(Int.toString r^" "^showVal r^" "^Int.toString v^","))
627 :     liveInSet;
628 :     print "\n"; *)
629 :     newOp{id=id, instr=sourceOp, pos=neginfPos,
630 :     block=X, defs=defs, uses=[],
631 :     rtl=T.SOURCE{block=X, liveIn=regs}
632 :     };
633 :     if debug then print("new "^showOp id^"\n") else ();
634 :     #set_entries ssa (id:: #entries ssa ());
635 :     ssa_id := !ssa_id + 1
636 :     end
637 :     else ()
638 :    
639 : leunga 744 val _ = IntHashTable.appi addSource liveInSets
640 : leunga 695
641 :     (* Now reserve space for extra phi nodes for live-in values *)
642 :     val _ = SSA.reserve SSA (!ssaOpsCount); (* reserve space *)
643 :     val newOp = SSA.newOp SSA
644 :    
645 :     (* Place phi functions *)
646 :     fun placePhi (B as (b,block)) =
647 :     let val preds = A.sub(preds, b)
648 :     val phis = A.sub(phis, b)
649 :     val phiRTL = T.PHI{preds=preds, block=b}
650 :     fun newPhi(id, []) = id
651 :     | newPhi(id,(t',t,s)::phis) =
652 :     (newOp{id=id, defs=[t], uses=s, rtl=phiRTL,
653 :     instr=phiOp, block=b, pos=t'};
654 :     if debug then print("new phi "^showOp id^"\n") else ();
655 :     newPhi(id+1, phis)
656 :     )
657 :    
658 :     in ssa_id := newPhi(!ssa_id, phis)
659 :     end
660 :    
661 :     in #forall_nodes cfg placePhi
662 :     end
663 :    
664 :     fun computeStatistics(G.GRAPH ssa) =
665 :     (#forall_nodes ssa (fn (i,i') =>
666 :     case InsnProps.instrKind i' of
667 :     InsnProps.IK_PHI => phi_nodes := !phi_nodes + 1
668 :     | _ => ());
669 :     ssa_nodes := !ssa_nodes + #order ssa ()
670 :     )
671 :    
672 :     in initCellKinds();
673 :     initTables();
674 :     walkTree();
675 :     SSA.computeDefUseChains SSA;
676 :     if !ssaStats then computeStatistics SSA else ();
677 :     if !removeUselessPhis then SSA.removeUselessPhiFunctions SSA else ();
678 :     if !consistencyCheck then SSA.consistencyCheck SSA else ();
679 :     if !debugSSA then
680 :     print("[SSA: "^Int.toString(!ssaOpsCount)^" nodes "^
681 :     Int.toString(N)^" blocks]\n")
682 :     else ();
683 :     SSA
684 :     end
685 :    
686 :     end

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