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

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

Parent Directory Parent Directory | Revision Log Revision Log


Revision 744 - (view) (download)

1 : leunga 695 (*----------------------------------------------------------------------------
2 :     * This module rebuilds a CFG from an SSA.
3 :     * The version is another rewrite of the algorithm in PLDI '99.
4 :     *
5 :     * -- Allen (leunga@cs.nyu.edu)
6 :     *----------------------------------------------------------------------------*)
7 :     functor SSA2CFG
8 :     (structure SSA : SSA
9 :     structure InsnProps : INSN_PROPERTIES
10 :     sharing SSA.I = InsnProps.I
11 :     ) : SSA2CFG =
12 :     struct
13 :    
14 :     structure SSA = SSA
15 :     structure CFG = SSA.CFG
16 :     structure DJ = SSA.DJ
17 :     structure SP = SSA.SP
18 :     structure RP = SP.RTLProps
19 :     structure I = SSA.I
20 :     structure C = I.C
21 :     structure RTL = SSA.RTL
22 :     structure T = RTL.T
23 :     structure G = Graph
24 :     structure A = Array
25 :     structure W8A = Word8Array
26 :     structure SL = SortedList
27 :    
28 :     fun error msg = MLRiscErrorMsg.error("SSA2CFG",msg)
29 :    
30 :     val i2s = Int.toString
31 :    
32 :     exception Nothing
33 :    
34 :     (*------------------------------------------------------------------------
35 :     * Flags
36 :     *------------------------------------------------------------------------*)
37 :     val consistencyCheck = MLRiscControl.getFlag "ssa-consistency-check"
38 :     val debug = MLRiscControl.getFlag "ssa-debug-ssa->cfg"
39 :    
40 :     val propagateSource = false
41 :     val coalesceEntry = true
42 :     val propagateSink = false
43 :    
44 :     (*------------------------------------------------------------------------
45 :     * Counters
46 :     *------------------------------------------------------------------------*)
47 :     val repairCopies = MLRiscControl.getCounter "ssa-repair-copies"
48 :     val phiCopies = MLRiscControl.getCounter "ssa-phi-copies"
49 :    
50 :     (*------------------------------------------------------------------------
51 :     * Fixed physical registers
52 :     *------------------------------------------------------------------------*)
53 :     val R = C.firstPseudo
54 :     val zeroRegs = SSA.zeroRegs
55 :     fun isZero r = W8A.sub(zeroRegs,r) <> 0w0 handle _ => false
56 :     val fixedDefTbl = W8A.array(R,0w0)
57 :     val fixedUseTbl = W8A.array(R,0w0)
58 :     fun initTbl tbl = app (fn r => W8A.update(tbl,r,0w1))
59 :     val _ = initTbl fixedDefTbl SP.fixedDef
60 :     val _ = initTbl fixedUseTbl SP.fixedUse
61 :    
62 :     val _ = W8A.appi (* never rename the zero registers! *)
63 :     (fn (i,0w0) => ()
64 :     | (i,_) => (W8A.update(fixedDefTbl,i,0w1);
65 :     W8A.update(fixedUseTbl,i,0w1)))
66 :     (zeroRegs,0,NONE)
67 :     fun isDedicatedDef r = W8A.sub(fixedDefTbl,r) <> 0w0 handle _ => false
68 :     fun isDedicatedUse r = W8A.sub(fixedUseTbl,r) <> 0w0 handle _ => false
69 :     (*------------------------------------------------------------------------
70 :     * Main entry point
71 :     *------------------------------------------------------------------------*)
72 :     fun buildCFG(SSA as G.GRAPH ssa) =
73 :     let val _ = if !consistencyCheck then SSA.consistencyCheck SSA else ()
74 :     val CFG as G.GRAPH cfg = SSA.cfg SSA
75 :     val Dom as G.GRAPH dom = SSA.dom SSA
76 :     val N = #capacity cfg () (* number of blocks *)
77 :     val M = #capacity ssa () (* number of ssa ops *)
78 :     val V = SSA.maxVar SSA (* number of variables *)
79 :     val showVal = SSA.showVal SSA
80 :     val showOp = SSA.showOp SSA
81 :     val [ENTRY] = #entries cfg ()
82 :    
83 :     (* val _ = (print "Dedicated: ";
84 :     app (fn r => print(showVal r^" ")) SP.fixedPhysical;
85 :     print "\n")
86 :     *)
87 :    
88 :     (*---------------------------------------------------------------------
89 :     * Extract Various tables
90 :     *---------------------------------------------------------------------*)
91 :     val defsTbl = SSA.defsTbl SSA (* definitions *)
92 :     val usesTbl = SSA.usesTbl SSA (* uses *)
93 :     val rtlTbl = SSA.rtlTbl SSA (* rtl *)
94 :     val posTbl = SSA.posTbl SSA (* position/resource for phi*)
95 :     val succTbl = SSA.succTbl SSA (* def/use chains *)
96 :     val ssaOpTbl = SSA.ssaOpTbl SSA (* instruction *)
97 :     val defSiteTbl = SSA.defSiteTbl SSA (* definition sites *)
98 :     val blockTbl = SSA.blockTbl SSA (* block table *)
99 :     val cellKindTbl = SSA.cellKindTbl SSA (* cellkinds *)
100 : leunga 744 val cellKindOf = IntHashTable.find cellKindTbl
101 :     val cellKindOf =
102 :     fn r => case cellKindOf r of SOME k => k | NONE => C.GP
103 : leunga 695 val {sources, phis, ops, sinks} = SSA.nodes SSA (* linearized ssa *)
104 :    
105 :     (*---------------------------------------------------------------------
106 :     * Machine description information
107 :     *---------------------------------------------------------------------*)
108 :     val constOf = SSA.const SSA
109 :     val rewriteOperands = SP.rewriteOperands{const=constOf}
110 :     val mkCopies = SP.copies
111 :     val namingConstraints = SP.namingConstraints
112 :     val opnKind = RP.opnKind
113 : leunga 744 val defUse = RP.defUse(SP.OT.lookupValueNumbers
114 :     (SSA.operandTbl SSA))
115 : leunga 695 (* Should value d be in the resource r? *)
116 :     fun dstInReg(r) = isDedicatedDef r
117 :     fun opDstInReg(k,r) = k = RP.FIX orelse isDedicatedDef r
118 :    
119 :     (* Should value s be in the resource r? *)
120 :     fun srcInReg(r) = isDedicatedUse r
121 :     fun opSrcInReg(k,r) = k = RP.FIX orelse isDedicatedUse r
122 :    
123 :     (*---------------------------------------------------------------------
124 :     * Temporary data structures
125 :     *---------------------------------------------------------------------*)
126 :     val Value = A.array(V, ~1) (* current value of resources *)
127 : leunga 744 (* names of all resources *)
128 :     val Resources = IntHashTable.mkTable(32, Nothing)
129 : leunga 695 val AvailIn = A.array(N, [])
130 :    
131 :     (* Mark the value of a resource *)
132 :     fun setValue(r,v) = A.update(Value,r,v)
133 :    
134 :     (* Lookup the value of a resource *)
135 :     fun valueOf(r) = A.sub(Value,r)
136 :    
137 :     (*---------------------------------------------------------------------
138 :     * Initialization
139 :     * 1. Find out the names of all dedicated resources
140 :     * 2. Find out all places where these are defined
141 :     * 3. Compute the values of all these resources at the entry point
142 :     * of each block
143 :     *---------------------------------------------------------------------*)
144 :     fun initialization() =
145 :     let
146 :    
147 :     (* Definitions of all resources *)
148 : leunga 744 val addResource = IntHashTable.insert Resources
149 : leunga 695 val LocalAvailOut = A.array(N, [])
150 :    
151 :     (* Process a block *)
152 :     fun processBlock(X, _) =
153 :     let
154 :     (* New resources *)
155 :     fun markResource(i,r,v,R) = (setValue(r,v); r::R)
156 :    
157 :     (* Process the source nodes *)
158 :     fun doSource([i], R) =
159 :     let fun scan([], [], R) = R
160 :     | scan(d::ds, r::rs, R) =
161 :     let val k = cellKindOf r
162 :     in if k = C.MEM orelse k = C.CTRL then
163 :     scan(ds, rs, R)
164 :     else
165 :     scan(ds, rs, markResource(i,r,d,R))
166 :     end
167 :     | scan _ = error "doSource.scan"
168 :     val dst = A.sub(defsTbl, i)
169 :     val T.SOURCE{liveIn, ...} = A.sub(rtlTbl, i)
170 :     in scan(dst, liveIn, R)
171 :     end
172 :     | doSource(_, R) = R
173 :    
174 :     (* Process the phi nodes *)
175 :     fun doPhis([], R) = R
176 :     | doPhis(phi::phis, R) =
177 :     let val [d] = A.sub(defsTbl, phi)
178 :     val r = A.sub(posTbl, phi)
179 :     in doPhis(phis,
180 :     if dstInReg r then markResource(phi,r,d,R) else R)
181 :     end
182 :    
183 :     (* Process the instructions *)
184 :     fun doOps([], R) = R
185 :     | doOps(i::rest, R) =
186 :     let fun scanUse([], [], [], R) = R
187 :     | scanUse(s::ss, r::rs, k::ks, R) =
188 :     scanUse(ss, rs, ks,
189 :     if opSrcInReg(k, r)
190 :     then markResource(i,r,s,R)
191 :     else R)
192 :     | scanUse _ = error "scanUse"
193 :    
194 :     fun scanDef([], [], [], ds') = rev ds'
195 :     | scanDef(d::ds, r::rs, k::ks, ds') =
196 :     scanDef(ds, rs, ks,
197 :     if opDstInReg(k, r)
198 :     then markResource(i,r,d,R)
199 :     else R)
200 :     | scanDef _ = error "scanDef"
201 :     val dst = A.sub(defsTbl, i)
202 :     val src = A.sub(usesTbl, i)
203 :     val instr = A.sub(ssaOpTbl, i)
204 :     val (rdst, rsrc) = defUse instr
205 :     val (kdst, ksrc) = opnKind instr
206 :     val R = scanUse(src, rsrc, ksrc, R)
207 :     val R = scanDef(dst, rdst, kdst, R)
208 :     in doOps(rest, R) end
209 :    
210 :     (* Process the sink nodes *)
211 :     fun doSink([i], R) =
212 :     let fun scan([], [], R) = R
213 :     | scan(s::ss, r::rs, R) =
214 :     let val k = cellKindOf r
215 :     in if k = C.MEM orelse k = C.CTRL then
216 :     scan(ss, rs, R)
217 :     else
218 :     scan(ss, rs, markResource(i,r,s,R))
219 :     end
220 :     | scan _ = error "doSink.scan"
221 :     val src = A.sub(usesTbl, i)
222 :     val T.SINK{liveOut, ...} = A.sub(rtlTbl, i)
223 :     in scan(src, liveOut, R) end
224 :     | doSink(_, R) = R
225 :    
226 :     val R = doSource(A.sub(sources,X), [])
227 :     val R = doPhis(A.sub(phis,X), R)
228 :     val R = doOps(A.sub(ops,X), R)
229 :     val R = doSink(A.sub(sinks,X), R)
230 :    
231 :     fun collect([], localAvailOut) = localAvailOut
232 :     | collect(r::rs, localAvailOut) =
233 :     let val v = valueOf r
234 :     in if v < 0 orelse isZero r
235 :     then collect(rs, localAvailOut)
236 :     else (setValue(r, ~1);
237 :     addResource(r, true);
238 :     collect(rs, (r,v)::localAvailOut)
239 :     )
240 :     end
241 :     val localAvailOut = collect(R, [])
242 :    
243 :     (*val _ = if debug then
244 :     case localAvailOut of
245 :     [] => ()
246 :     | _ => (print("Block ["^i2s X^"]: ");
247 :     app (fn (r,v) =>
248 :     print(showVal r^"->"^showVal v^" "))
249 :     localAvailOut;
250 :     print "\n"
251 :     )
252 :     else ()
253 :     *)
254 :     in A.update(LocalAvailOut, X, localAvailOut)
255 :     end
256 :    
257 :     val _ = #forall_nodes dom processBlock
258 :    
259 :     (* Definitions indexed by resource *)
260 : leunga 744 val LocalDefs = IntHashTable.mkTable(32, Nothing)
261 :     val lookupLocalDef = IntHashTable.find LocalDefs
262 :     val lookupLocalDef =
263 :     fn r => case lookupLocalDef r of SOME d => d | NONE => []
264 :     val addLocalDef = IntHashTable.insert LocalDefs
265 : leunga 695
266 :     val _ = A.appi (fn (X, localAvailOut) =>
267 :     app (fn (r,v) =>
268 :     addLocalDef(r, (X,v)::lookupLocalDef r))
269 :     localAvailOut) (LocalAvailOut, 0, NONE)
270 :    
271 :     (* val _ = if debug then
272 :     (print "Resources=";
273 : leunga 744 IntHashTable.appi
274 :     (fn (r, _) => print(showVal r^" ")) Resources;
275 : leunga 695 print "\n"
276 :     ) else ()
277 :     *)
278 :    
279 :     (* Perform data flow analysis for each resource r *)
280 :     val bot = ~1
281 :     val top = ~2
282 :     val LocalAvailOut = A.array(N, bot)
283 :     val onWorkList = A.array(N, ~1)
284 :     val dj = DJ.DJ Dom
285 :     val IDFs = DJ.IDFs dj
286 :    
287 :     fun availAnalysis(r,_) =
288 :     let val GlobalAvailIn = A.array(N, bot)
289 :    
290 :     fun init([], defs) = defs
291 :     | init((X,v)::A, defs) =
292 :     (A.update(LocalAvailOut, X, v);
293 :     A.update(onWorkList, X, r);
294 :     init(A, X::defs)
295 :     )
296 :    
297 :     fun cleanup [] = ()
298 :     | cleanup((X,v)::A) =
299 :     (A.update(LocalAvailOut,X,bot); cleanup A)
300 :    
301 :     val localAvailOut = lookupLocalDef r
302 :    
303 :     val defSites = init(localAvailOut, [])
304 :    
305 :     fun meet([], v) = v
306 :     | meet((X,_,_)::es, v) =
307 :     let val v' = A.sub(LocalAvailOut,X)
308 :     val v' = if v' >= 0 then v' else A.sub(GlobalAvailIn,X)
309 :     in if v' = bot then v
310 :     else if v = bot then v'
311 :     else if v' = top orelse v = top then top
312 :     else if v = v' then meet(es, v)
313 :     else top
314 :     end
315 :    
316 :     fun insert([], WL) = WL
317 :     | insert((_,X,_)::es, WL) =
318 :     if A.sub(onWorkList,X) = r then insert(es, WL)
319 :     else (A.update(onWorkList,X,r); insert(es, X::WL))
320 :    
321 :     fun update(X, WL) =
322 :     let val oldV = A.sub(GlobalAvailIn, X)
323 :     val newV = meet(#in_edges cfg X, bot)
324 :     in if oldV = newV then WL
325 :     else (A.update(GlobalAvailIn,X,newV);
326 :     if A.sub(LocalAvailOut,X) < 0 then WL
327 :     else insert(#out_edges cfg X, WL)
328 :     )
329 :     end
330 :    
331 :     fun iterate [] = ()
332 :     | iterate(X::WL) =
333 :     let val _ = A.update(onWorkList, X, ~1)
334 :     in iterate(update(X, WL))
335 :     end
336 :    
337 :     fun updateInfo [] = ()
338 :     | updateInfo(X::Xs) =
339 :     let val v = A.sub(GlobalAvailIn,X)
340 :     in A.update(AvailIn, X, (r,v)::A.sub(AvailIn, X));
341 :     updateInfo Xs
342 :     end
343 :    
344 :     val () = iterate(defSites)
345 :     val IDFs = IDFs defSites
346 :    
347 :     in updateInfo IDFs;
348 :     cleanup localAvailOut
349 :     end
350 :    
351 : leunga 744 in IntHashTable.appi availAnalysis Resources
352 : leunga 695 end
353 :    
354 :     val _ = initialization()
355 :    
356 :     (* location of each SSA definition. ~1 means maps to itself *)
357 :     val defLocation = A.array(V, ~1)
358 :     fun locationOf v =
359 :     if v < 0 then v
360 :     else
361 :     let val r = A.sub(defLocation,v)
362 :     in if r < 0 then v else r end
363 :     fun setLocation(v,r) = A.update(defLocation,v,r)
364 :    
365 :     (* repair map indexed by variable *)
366 :     val defCompensation = W8A.array(V, 0w0)
367 :    
368 :     (* repair map indexed by ss_op *)
369 :     val useCompensation = A.array(M, [])
370 :    
371 :     (*---------------------------------------------------------------------
372 :     * Find conflicts
373 :     *---------------------------------------------------------------------*)
374 :     fun conflicts X =
375 :     let val valueTrail = ref []
376 :    
377 :     (* Set the current value *)
378 :     fun setValue(r, v) =
379 :     let val v' = A.sub(Value, r)
380 :     in A.update(Value, r, v);
381 :     valueTrail := (r, v') :: !valueTrail
382 :     end
383 :    
384 :     fun valueOf r = A.sub(Value, r)
385 :    
386 :     (* Lookup current location for a name v;
387 :     * Check whether compensation code is needed.
388 :     *)
389 :     fun checkUse(i,r,v) =
390 :     if valueOf(r) = v then ()
391 :     else
392 :     (if !debug then
393 :     let val j = A.sub(defSiteTbl, v) (* v is defined in j *)
394 :     val Y = A.sub(blockTbl,j)
395 :     in print("WARNING["^i2s X^"] "^
396 :     showVal v^"="^showVal(valueOf(r))^" "^
397 :     showOp i^"\n"^
398 :     "Defined in ["^i2s Y^"] "^
399 :     showOp j^"\n"
400 :     )
401 :     end
402 :     else ();
403 :     (* mark variable v as needing repair *)
404 :     W8A.update(defCompensation, v, 0w1);
405 :     (* insert compensation code v->r at use site *)
406 :     let fun addCopy([], cps') =
407 :     A.update(useCompensation, i,
408 :     {kind=cellKindOf r, src=v, dst=r}::cps')
409 :     | addCopy({src,dst,kind}::cps, cps') =
410 :     if dst=r then
411 :     if src=v then print "duplicate\n"
412 :     else error "different sources in compensation!"
413 :     else addCopy(cps, cps')
414 :     val cps = A.sub(useCompensation, i)
415 :     in addCopy(cps, cps)
416 :     end;
417 :     (* Now the value of r is v *)
418 :     setValue(r, v)
419 :     )
420 :    
421 :     (* Lookup current location for v
422 :     * Make sure that
423 :     *)
424 :     fun checkDefIsAvail(i, v) =
425 :     let val r = A.sub(defLocation, v)
426 :     in if r < 0 orelse valueOf(r) = v then ()
427 :     (* okay *)
428 :     else (* v has been mapped into r.
429 :     * we need to preserve the value of v somehow
430 :     *)
431 :     (if !debug then
432 :     let val j = A.sub(defSiteTbl, v) (* v is defined in j *)
433 :     val Y = A.sub(blockTbl,j)
434 :     in print("WARNING["^i2s X^"] "^
435 :     showVal v^" mapped to "^showVal r^
436 :     " but valueOf("^showVal r^")="^
437 :     showVal(valueOf(r))^" in "^
438 :     showOp i^"\n"^
439 :     "Defined in ["^i2s Y^"] "^
440 :     showOp j^"\n"
441 :     )
442 :     end
443 :     else ();
444 :     (* mark variable v as needing repair *)
445 :     repairCopies := !repairCopies + 1;
446 :     W8A.update(defCompensation, v, 0w1)
447 :     )
448 :     end
449 :    
450 :     (* Pop the value stack *)
451 :     fun undoValue [] = ()
452 :     | undoValue((r,v)::rs) =
453 :     (A.update(Value, r, v); undoValue rs)
454 :    
455 :     (* Process the source node *)
456 :     fun doSource [i] =
457 :     let fun scan([], []) = ()
458 :     | scan(d::ds, r::rs) =
459 :     if coalesceEntry andalso X = ENTRY orelse
460 :     propagateSource orelse dstInReg r then
461 :     (setValue(r, d); setLocation(d,r); scan(ds, rs))
462 :     else
463 :     (setValue(r, ~1); scan(ds, rs))
464 :     | scan _ = error "doSource.scan"
465 :     val dst = A.sub(defsTbl, i)
466 :     val T.SOURCE{liveIn, ...} = A.sub(rtlTbl, i)
467 :     in scan(dst, liveIn)
468 :     end
469 :     | doSource _ = ()
470 :    
471 :     (* Process the nodes *)
472 :     fun doPhysicalAvailIn X =
473 :     let fun init [] = ()
474 :     | init((r,v)::bindings) =
475 :     (setValue(r, v);
476 :     (* if debug then
477 :     print("["^i2s X^"] "^showVal r^
478 :     "="^i2s v^"\n")
479 :     else (); *)
480 :     init bindings)
481 :     val availIn = A.sub(AvailIn,X)
482 :     in init availIn
483 :     end
484 :    
485 :     (* Process the phi nodes *)
486 :     fun doPhis [] = ()
487 :     | doPhis(phi::phis) =
488 :     let val [d] = A.sub(defsTbl, phi)
489 :     val r = A.sub(posTbl, phi)
490 :     in if dstInReg r then
491 :     (setValue(r, d); setLocation(d, r)) else ();
492 :     doPhis(phis)
493 :     end
494 :    
495 :     (* Process the instructions *)
496 :     fun doOps [] = ()
497 :     | doOps(i::rest) =
498 :     let fun scanUse([], [], []) = ()
499 :     | scanUse(s::ss, r::rs, k::ks) =
500 :     (if s >= 0 then
501 :     (if opSrcInReg(k, r) then
502 :     (* If s is actually a zero register; its
503 :     * value is always available *)
504 :     if isZero r then ()
505 :     else
506 :     (checkUse(i, r, s);
507 :     checkDefIsAvail(i, s)
508 :     )
509 :     else
510 :     checkDefIsAvail(i, s)
511 :     )
512 :     else ();
513 :     scanUse(ss, rs, ks)
514 :     )
515 :    
516 :     fun scanDef([], [], []) = ()
517 :     | scanDef(d::ds, r::rs, k::ks) =
518 :     (if opDstInReg(k, r)
519 :     then (setValue(r, d); setLocation(d, r))
520 :     else ();
521 :     scanDef(ds, rs, ks)
522 :     )
523 :     | scanDef _ = error "scanDef"
524 :    
525 :     val dst = A.sub(defsTbl, i)
526 :     val src = A.sub(usesTbl, i)
527 :     val instr = A.sub(ssaOpTbl, i)
528 :     val (rdst, rsrc) = defUse instr
529 :     val (kdst, ksrc) = opnKind instr
530 :     in scanUse(src, rsrc, ksrc);
531 :     scanDef(dst, rdst, kdst);
532 :     doOps(rest)
533 :     end
534 :    
535 :     (* Process the sink node *)
536 :     fun doSink [i] =
537 :     let fun scan([], []) = ()
538 :     | scan(s::ss, r::rs) =
539 :     (if s >= 0 then
540 :     (if propagateSink orelse srcInReg(r)
541 :     then checkUse(i, r, s) else ();
542 :     checkDefIsAvail(i, s)
543 :     )
544 :     else ();
545 :     scan(ss, rs)
546 :     )
547 :     | scan _ = error "doSink.scan"
548 :    
549 :     val src = A.sub(usesTbl, i)
550 :     val T.SINK{liveOut, ...} = A.sub(rtlTbl, i)
551 :     in scan(src, liveOut)
552 :     end
553 :     | doSink(_) = ()
554 :    
555 :     in doPhysicalAvailIn X;
556 :     doSource(A.sub(sources, X));
557 :     doPhis(A.sub(phis, X));
558 :     doOps(A.sub(ops, X));
559 :     doSink(A.sub(sinks, X));
560 :     app conflicts (#succ dom X); (* walk the tree! *)
561 :     undoValue(!valueTrail)
562 :     end
563 :    
564 :     val _ = conflicts ENTRY
565 :    
566 :     (*
567 :     * How to make a set of parallel copies.
568 :     * The source can contain constants!
569 :     *)
570 :     fun makeCopies(cps) =
571 :     let fun split([], cps', loadConsts) = mkCopies cps' @ loadConsts
572 :     | split((cp as {src, dst, kind})::cps, cps', loadConsts) =
573 :     if src >= 0 then split(cps, cp::cps', loadConsts)
574 :     else
575 :     let val loadConsts =
576 :     case constOf src of
577 : leunga 744 SP.OT.INT i =>
578 : leunga 695 InsnProps.loadImmed{t=dst, immed=i}::loadConsts
579 :     | SP.OT.OPERAND opn =>
580 :     InsnProps.loadOperand{t=dst, opn=opn}::loadConsts
581 :     in split(cps, cps', loadConsts)
582 :     end
583 :     in split(cps, [], []) end
584 :    
585 :     (* renaming stack indexed by SSA variable name *)
586 :     val stacks = A.array(V, [])
587 :    
588 :     (*---------------------------------------------------------------------
589 :     * Rename and insert phi-functions.
590 :     * Also insert repair code for resources.
591 :     *---------------------------------------------------------------------*)
592 :     fun rename X =
593 :     let val renamingTrail = ref []
594 :    
595 :     (* Lookup current location for a name v;
596 :     * Check whether compensation code is needed.
597 :     *)
598 :     fun locationOf(i,v) =
599 :     if v < 0 then v (* immediate operand *)
600 :     else if W8A.sub(defCompensation,v) <> 0w0 then v
601 :     else
602 :     (case A.sub(stacks, v) of
603 :     [] => v
604 :     | v'::_ => v'
605 :     )
606 :    
607 :     (* Create a new renaming entry in the renaming stack *)
608 :     fun renameDef(v, r) =
609 :     (A.update(stacks, v, r::A.sub(stacks, v));
610 :     renamingTrail := v :: !renamingTrail
611 :     )
612 :    
613 :     (* Pop the renaming stack *)
614 :     fun undoRenaming [] = ()
615 :     | undoRenaming(r::rs) =
616 :     let val _::vs = A.sub(stacks, r)
617 :     in A.update(stacks, r, vs); undoRenaming rs end
618 :    
619 :     (* Copy a value v to a register r *)
620 :     fun copyToReg(v, r, cps) =
621 :     if v = r then cps else {kind=cellKindOf r, dst=r, src=v}::cps
622 :    
623 :     (* Copy a register r to a value v *)
624 :     fun copyFromReg(r, v, cps) =
625 :     if v = r then cps else {kind=cellKindOf r, dst=v, src=r}::cps
626 :    
627 :     fun duplicate(s,d,[]) = false
628 :     | duplicate(s,d,{src,dst,kind}::cps) =
629 :     if dst = d then
630 :     if src = s then true
631 :     else error "duplicate: different source"
632 :     else duplicate(s,d,cps)
633 :    
634 :     (* Insert repair code from r -> v at definition of v *)
635 :     fun compensation(r, v, cps) =
636 :     if W8A.sub(defCompensation,v) <> 0w0
637 :     then if duplicate(r,v,cps) then cps
638 :     else copyFromReg(r, v, cps)
639 :     else cps
640 :    
641 :     (* Get repair code at uses of instruction j *)
642 :     fun repair(j) = A.sub(useCompensation, j)
643 :    
644 :     (* Process the source node *)
645 :     fun doSource [i] =
646 :     let fun scan([], [], cps) = cps
647 :     | scan(d::ds, r::rs, cps) =
648 :     if coalesceEntry andalso X = ENTRY orelse
649 :     propagateSource orelse dstInReg r then
650 :     (renameDef(d, r);
651 :     scan(ds, rs, compensation(r, d, cps))
652 :     )
653 :     else scan(ds, rs, copyFromReg(r, d, cps))
654 :     | scan _ = error "doSource.scan"
655 :     val dst = A.sub(defsTbl, i)
656 :     val T.SOURCE{liveIn, ...} = A.sub(rtlTbl, i)
657 :     val cps = scan(dst, liveIn, [])
658 :     in cps
659 :     end
660 :     | doSource _ = []
661 :    
662 :     (* Process the phi nodes *)
663 :     fun doPhis [] = ()
664 :     | doPhis(phi::phis) =
665 :     let val [d] = A.sub(defsTbl, phi)
666 :     val r = A.sub(posTbl, phi)
667 :     in if dstInReg r then renameDef(d, r) else ();
668 :     doPhis(phis)
669 :     end
670 :    
671 :     fun notMoved(dst',[]) = true
672 :     | notMoved(dst',{dst,src,kind}::cps) =
673 :     dst<>dst' andalso notMoved(dst', cps)
674 :    
675 :     (* Process the instructions *)
676 :     fun doOps([], instrs) = instrs
677 :     | doOps(i::rest, instrs) =
678 :     let fun scanUse([], [], [], ss', cps) = (rev ss', cps)
679 :     | scanUse(s::ss, r::rs, k::ks, ss', cps) =
680 :     (* actual value of s is in resource s' *)
681 :     let val s' = locationOf(i, s)
682 :     in if opSrcInReg(k, r) then
683 :     ((* subsequent use of s now point to r *)
684 :     scanUse(ss, rs, ks, r::ss',
685 :     (* Make sure it is not copied multiple
686 :     * times *)
687 :     if notMoved(r, cps) then
688 :     copyToReg(s', r, cps) else cps)
689 :     )
690 :     else
691 :     scanUse(ss, rs, ks, s'::ss', cps)
692 :     end
693 :     | scanUse _ = error "scanUse"
694 :    
695 :     fun scanDef([], [], [], ds', cps) = (rev ds', cps)
696 :     | scanDef(d::ds, r::rs, k::ks, ds', cps) =
697 :     if opDstInReg(k, r) then
698 :     (renameDef(d, r);
699 :     (* subsequent use of d now point to r;
700 :     * may need repair code here.
701 :     *)
702 :     scanDef(ds, rs, ks, r::ds', compensation(r, d, cps))
703 :     )
704 :     else
705 :     scanDef(ds, rs, ks, d::ds', cps)
706 :     | scanDef _ = error "scanDef"
707 :    
708 :     val dst = A.sub(defsTbl, i)
709 :     val src = A.sub(usesTbl, i)
710 :     val instr = A.sub(ssaOpTbl, i)
711 :     val (rdst, rsrc) = defUse instr
712 :     val (kdst, ksrc) = opnKind instr
713 :     val (instrSrc, srcCopies) =
714 :     scanUse(src, rsrc, ksrc, [], repair(i))
715 :     val (instrDst, dstCopies) = scanDef(dst, rdst, kdst, [], [])
716 :     val instr' = rewriteOperands
717 :     {instr=instr, dst=instrDst, src=instrSrc}
718 :     (* Create instructions in in reverse order *)
719 :     val copiesIn = makeCopies srcCopies
720 :     val copiesOut = makeCopies dstCopies
721 :     val instrs =
722 :     List.revAppend(copiesOut,instr'::
723 :     List.revAppend(copiesIn, instrs))
724 :     in doOps(rest, instrs)
725 :     end
726 :    
727 :     (* Check if the block Y is an exit with a
728 :     * simple jump instruction.
729 :     *)
730 :     fun isSimpleExit Y = false
731 :     andalso
732 :     (case (A.sub(sinks,Y), A.sub(ops,Y)) of
733 :     ([_], [j]) =>
734 :     (case A.sub(usesTbl, j) of
735 :     [] => true
736 :     | _ => false
737 :     )
738 :     | _ => false
739 :     )
740 :    
741 :     (* Process the sink node *)
742 :     fun doSink([i], cps) =
743 :     if isSimpleExit X then cps
744 :     else
745 :     let fun scan([], [], cps) = cps
746 :     | scan(s::ss, r::rs, cps) =
747 :     let val s' = locationOf(i, s)
748 :     in if propagateSink orelse dstInReg r then
749 :     (* dealt with in repair later *)
750 :     scan(ss, rs, cps)
751 :     else
752 :     scan(ss, rs, copyToReg(s', r, cps))
753 :     end
754 :     | scan _ = error "doSink.scan"
755 :    
756 :     val src = A.sub(usesTbl, i)
757 :     val T.SINK{liveOut, ...} = A.sub(rtlTbl, i)
758 :     val cps = scan(src, liveOut, repair(i) @ cps)
759 :     in cps
760 :     end
761 :     | doSink(_, cps) = cps
762 :    
763 :     (* Process phi copies from all successors of X *)
764 :     fun doPhiCopies X =
765 :     let fun scan([], cps) = cps
766 :     | scan((X,Y,_)::es, cps) =
767 :     if isSimpleExit Y then scan(es, cps) (* HACK!!! *)
768 :     else
769 :     let val phis = A.sub(phis, Y)
770 :     in case phis of
771 :     [] => cps (* nothing to do *)
772 :     | i::_ =>
773 :     let val T.PHI{preds, ...} = A.sub(rtlTbl, i)
774 :     fun ith([], n) = error "doPhiCopies"
775 :     | ith(p::ps, n) = if p = X then n
776 :     else ith(ps,n+1)
777 :     val n = ith(preds, 0)
778 :     fun collect([], cps) = cps
779 :     | collect(phi::phis, cps) =
780 :     let val [d] = A.sub(defsTbl, phi)
781 :     val s = List.nth(A.sub(usesTbl, phi),n)
782 :     val r = A.sub(posTbl, phi)
783 :     val s' = locationOf(phi,s)
784 :     val d' = if dstInReg r then r else d
785 :     val cps = copyToReg(s', d', cps)
786 :     val cps = compensation(s', d, cps)
787 :     in (* renameDef(s, d'); XXX *)
788 :     collect(phis, cps)
789 :     end
790 :     in scan(es, collect(phis, cps))
791 :     end
792 :     end
793 :     val cps = scan(#out_edges cfg X, [])
794 :     in cps
795 :     end
796 :    
797 :     (*
798 :     * Stupid MLRISC hack:
799 :     * If entry copies or exit copies contain floating point,
800 :     * generate a new floating point name just to make sure
801 :     * register allocation is run.
802 :     *)
803 :     fun floatingPointHack copies =
804 :     let fun containsFP [] = false
805 :     | containsFP({kind,src,dst}::copies) =
806 :     kind = C.FP orelse containsFP copies
807 :     in if containsFP copies then (C.newFreg(); ()) else () end
808 :    
809 :     val entryCopies = doSource(A.sub(sources, X))
810 :     val _ = floatingPointHack entryCopies
811 :     val entryCopies = makeCopies entryCopies
812 :     val _ = doPhis(A.sub(phis, X))
813 :     val instrs = doOps(A.sub(ops, X), entryCopies)
814 :     val phiCopies = doPhiCopies(X)
815 :     val exitCopies = doSink(A.sub(sinks, X), phiCopies)
816 :     val _ = floatingPointHack exitCopies
817 :     (* val _ = case exitCopies of
818 :     [] => ()
819 :     | _ => (print("EXIT["^i2s X^"]=");
820 :     app (fn {src, dst, ...} =>
821 :     print(i2s src^"->"^i2s dst^" ")) exitCopies;
822 :     print "\n") *)
823 :     val exitCopies = makeCopies exitCopies
824 :    
825 :    
826 :     (* Insert the copies before the jump instruction at the
827 :     * end of the block. Copies are in normal order.
828 :     * Instructions are in reversed order
829 :     *)
830 :     fun spliceCopies(instrs, copies) =
831 :     case instrs of
832 :     [] => rev copies
833 :     | jmp::rest =>
834 :     if InsnProps.instrKind jmp = InsnProps.IK_JUMP then
835 :     jmp::List.revAppend(copies, rest)
836 :     else
837 :     List.revAppend(copies, instrs)
838 :    
839 :     val instrs = spliceCopies(instrs, exitCopies)
840 :     in
841 :     CFG.insns (#node_info cfg X) := instrs; (* update block! *)
842 :     app rename (#succ dom X); (* walk the tree! *)
843 :     undoRenaming(!renamingTrail)
844 :     end
845 :    
846 :     in rename ENTRY;
847 :     (* Move the instructions from the entry block to all its successors *)
848 :     let val entryInsns = CFG.insns (#node_info cfg ENTRY)
849 :     in case !entryInsns of
850 :     [] => () (* okay *)
851 :     | instrs =>
852 :     (print "WARNING: Instructions in ENTRY\n";
853 :     entryInsns := []; (* remove it *)
854 :     app (fn (_,Y,_) =>
855 :     let val insns = CFG.insns(#node_info cfg Y)
856 :     in insns := !insns @ map InsnProps.replicate instrs
857 :     end
858 :     ) (#out_edges cfg ENTRY)
859 :     )
860 :     end;
861 :     CFG
862 :     end
863 :    
864 :     end

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