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

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