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

Annotation of /sml/trunk/src/MLRISC/ra/cluster-ra.sml

Parent Directory Parent Directory | Revision Log Revision Log


Revision 624 - (view) (download)

1 : monnier 467 (*
2 :     * This module provides services for the new RA when using the cluster
3 :     * representation.
4 : monnier 475 * The algorithm is adapted from
5 :     * Algorithm 19.17 from Appel, Modern Compiler Implementation in ML,
6 :     * Calculation of live ranges in SSA form. We don't directly use SSA
7 :     * here but the principles are the same.
8 : monnier 467 *
9 :     * -- Allen
10 :     *)
11 :    
12 :     functor ClusterRA
13 :     (structure Flowgraph : FLOWGRAPH
14 :     structure Asm : INSTRUCTION_EMITTER
15 :     structure InsnProps : INSN_PROPERTIES
16 : monnier 498 sharing Flowgraph.I = InsnProps.I = Asm.I
17 : monnier 467 sharing Asm.P = Flowgraph.P
18 :     ) : RA_FLOWGRAPH =
19 :     struct
20 :     structure F = Flowgraph
21 :     structure I = F.I
22 :     structure W = F.W
23 :     structure C = I.C
24 :     structure G = RAGraph
25 :     structure Props = InsnProps
26 :     structure Core = RACore
27 :     structure A = Array
28 :     structure UA = Unsafe.Array (* okay, I'm cheating a bit here *)
29 : monnier 498 structure Spill = RASpill(structure InsnProps = InsnProps
30 :     structure Asm = Asm
31 :     )
32 : monnier 467
33 : george 545 structure PrintCluster = PrintCluster
34 : monnier 467 (structure Flowgraph = F
35 :     structure Asm = Asm
36 :     )
37 :    
38 :     open G
39 :    
40 : monnier 498 fun isOn(flag,mask) = Word.andb(flag,mask) <> 0w0
41 :    
42 : monnier 467 type flowgraph = F.cluster (* flowgraph is a cluster *)
43 :    
44 :     fun error msg = MLRiscErrorMsg.error("ClusterRA", msg)
45 : monnier 498
46 :     val mode = 0w0
47 : monnier 467
48 :     fun regmap(F.CLUSTER{regmap, ...}) = regmap
49 :    
50 :     fun dumpFlowgraph(msg, cluster, stream) =
51 :     PrintCluster.printCluster stream
52 :     ("------------------ "^msg^" ------------------") cluster
53 :    
54 :     exception NotThere
55 :    
56 : monnier 498 (*
57 : monnier 467 val Asm.S.STREAM{emit, ...} = Asm.makeStream []
58 : monnier 498 *)
59 : monnier 467
60 :     val dummyLabel = F.LABEL(Label.Label{id= ~1, addr=ref ~1, name=""})
61 :    
62 : monnier 498 fun x + y = Word.toIntX(Word.+(Word.fromInt x, Word.fromInt y))
63 : monnier 467
64 :     fun length l =
65 :     let fun loop([],n) = n
66 : monnier 498 | loop(_::l,n) = loop(l,n+1)
67 : monnier 467 in loop(l,0) end
68 :    
69 :     fun services(cluster as F.CLUSTER{regmap, blocks, blkCounter, ...}) =
70 :     let (* Create a graph based view of cluster *)
71 : leunga 585 val N = !blkCounter
72 : monnier 467
73 : monnier 498 fun computeShift(0w0, max) = 0w31-max
74 :     | computeShift(N, max) = computeShift(Word.>>(N, 0w1), Word.+(max,0w1))
75 :     val shift = computeShift(Word.>>(Word.fromInt N, 0w15), 0w15)
76 :     val mask = Word.<<(0w1, shift) - 0w1
77 :    
78 :     (*
79 :     * Construct program point
80 :     *)
81 :     fun progPt(blknum, instrId) =
82 :     Word.toIntX(Word.+(Word.<<(Word.fromInt blknum, shift),
83 :     Word.fromInt instrId))
84 :     fun blockNum pt = Word.toIntX(Word.>>(Word.fromInt pt, shift))
85 :     fun instrNum pt = Word.toIntX(Word.andb(Word.fromInt pt, mask))
86 :    
87 : george 545 (* blocks indexed by block id *)
88 : monnier 467 val blockTable = A.array(N, dummyLabel)
89 :    
90 : george 545 fun fillBlockTable [] = ()
91 :     | fillBlockTable((b as F.BBLOCK{blknum, ...})::blocks) =
92 :     (UA.update(blockTable, blknum, b); fillBlockTable blocks)
93 :     | fillBlockTable(_::blocks) = fillBlockTable blocks
94 :     val _ = fillBlockTable blocks
95 : monnier 467
96 :     (*
97 : george 545 * Building the interference graph
98 :     *)
99 :     fun buildIt (cellkind, regmap,
100 :     G as GRAPH{nodes, dedicated, mode, span, copyTmps, ...}) =
101 : monnier 467
102 : george 545 let (* definitions indexed by block id+instruction id *)
103 :     val defsTable = A.array(N, A.array(0, [] : node list))
104 :     val marked = A.array(N, ~1)
105 : leunga 624
106 :     (* copies indexed by source *)
107 :     val copyTable = Intmap.new(N, NotThere)
108 :     val lookupCopy = Intmap.mapWithDefault(copyTable, [])
109 :     val addCopy = Intmap.add copyTable
110 :    
111 :    
112 : george 545 val stamp = ref 0
113 :    
114 :     (* Allocate the arrays *)
115 :     fun alloc [] = ()
116 :     | alloc((b as F.BBLOCK{blknum, insns, ...})::blocks) =
117 :     let val n = length(!insns)
118 :     val m = n+1
119 :     in UA.update(defsTable, blknum, A.array(m, []));
120 :     alloc blocks
121 :     end
122 :     | alloc(_::blocks) = alloc blocks
123 :     val _ = alloc blocks
124 :    
125 :     (*
126 :     * Remove pseudo use generated by copy temporaries
127 :     *)
128 :     fun rmPseudoUses [] = ()
129 :     | rmPseudoUses(NODE{uses,...}::ns) = (uses := []; rmPseudoUses ns)
130 :    
131 :     (*
132 : leunga 624 * Initialize the definitions before computing the liveness for v.
133 : george 545 *)
134 : leunga 624 fun initialize(v,v',useSites) =
135 :     let (* First we remove all definitions for all copies
136 :     * with v as source.
137 :     *)
138 :     fun markCopies([], trail) = trail
139 :     | markCopies({pt, dst}::copies, trail) =
140 :     let val b = blockNum pt
141 :     val i = instrNum pt
142 :     val defs = UA.sub(defsTable, b)
143 :     val nodes = UA.sub(defs, i)
144 :     fun revAppend([], nodes) = nodes
145 :     | revAppend(n::ns, nodes) = revAppend(ns, n::nodes)
146 :     fun removeDst([], nodes') = nodes'
147 :     | removeDst((d as NODE{number=r,...})::nodes, nodes')=
148 :     if r = dst then revAppend(nodes', nodes)
149 :     else removeDst(nodes, d::nodes')
150 :     val nodes' = removeDst(nodes, [])
151 :     in UA.update(defs, i, nodes');
152 :     markCopies(copies, (defs, i, nodes)::trail)
153 : george 545 end
154 : leunga 624
155 :     (*
156 :     * Then we mark all use sites of v
157 :     *)
158 :     fun markUseSites([], trail) = trail
159 :     | markUseSites(pt::pts, trail) =
160 :     let val b = blockNum pt
161 :     val i = instrNum pt
162 :     val defs = UA.sub(defsTable, b)
163 :     val nodes = UA.sub(defs, i)
164 :     in UA.update(defs, i, v'::nodes);
165 :     markUseSites(pts, (defs, i, nodes)::trail)
166 : george 545 end
167 : leunga 624
168 :     val copies = lookupCopy v
169 :     val trail = markCopies(copies, [])
170 :     val trail = markUseSites(useSites, trail)
171 :     in trail end
172 : george 545
173 : leunga 624 fun cleanup [] = ()
174 :     | cleanup ((defs, i, nodes)::trail) =
175 :     (UA.update(defs, i, nodes); cleanup trail)
176 : george 545 (*
177 :     * Perform incremental liveness analysis on register v
178 :     * and compute the span
179 :     *)
180 : leunga 624 fun liveness(v, v' as NODE{uses, ...}, addEdge) =
181 : george 545 let val st = !stamp
182 :     val _ = stamp := st + 1
183 :     fun foreachUseSite([], span) = span
184 :     | foreachUseSite(u::uses, span) =
185 :     let val b = blockNum u
186 :     val i = instrNum u
187 :     in case UA.sub(blockTable, b) of
188 :     block as F.BBLOCK{freq, ...} =>
189 :     let val span =
190 :     if i = 0 then
191 :     liveOutAtBlock(block, span) (* live out *)
192 :     else
193 :     let val f = !freq
194 : leunga 624 val defs = UA.sub(defsTable, b)
195 :     in liveOutAtStmt(block, A.length defs,
196 :     defs, i+1, f, span+f)
197 : george 545 end;
198 :     in foreachUseSite(uses, span)
199 :     end
200 :     | _ => error "liveness2"
201 :     end
202 :    
203 :     and visitPred(block, span) =
204 :     let fun foreachPred([], span) = span
205 :     | foreachPred((b, _)::pred, span) =
206 :     let val span = liveOutAtBlock(b, span)
207 :     in foreachPred(pred, span) end
208 :     in case block of
209 :     F.BBLOCK{pred, ...} => foreachPred(!pred, span)
210 :     | _ => error "visitPred"
211 :     end
212 :    
213 : leunga 624 and liveOutAtStmt(block, nDefs, defs, pos, freq, span) =
214 : george 545 (* v is live out *)
215 : leunga 624 if pos < nDefs then
216 : george 545 let fun foreachDef([], true) = span
217 :     | foreachDef([], false) =
218 : leunga 624 liveOutAtStmt(block, nDefs, defs,
219 :     pos+1, freq, span+freq)
220 : george 545 | foreachDef((d as NODE{number=r, ...})::ds, kill) =
221 :     if r = v then foreachDef(ds, true)
222 :     else (addEdge(d, v'); foreachDef(ds, kill))
223 :     in foreachDef(UA.sub(defs, pos), false)
224 :     end
225 :     else visitPred(block, span)
226 :    
227 :     and liveOutAtBlock(block as F.BBLOCK{blknum, freq, ...}, span) =
228 :     (* v is live out at the current block *)
229 :     if UA.sub(marked, blknum) = st then span
230 :     else
231 :     (UA.update(marked, blknum, st);
232 : leunga 624 let val defs = UA.sub(defsTable, blknum)
233 :     in liveOutAtStmt(block, A.length defs, defs,
234 :     1, !freq, span)
235 :     end
236 : george 545 )
237 :     | liveOutAtBlock(_, span) = span
238 : leunga 624
239 :     val useSites = SortedList.uniq(!uses)
240 :     val trail = initialize(v, v', useSites)
241 : george 545 val span = foreachUseSite (useSites, 0)
242 : leunga 624 val _ = cleanup trail
243 :     in span
244 : george 545 end
245 :    
246 :     val newNodes = Core.newNodes G
247 : monnier 467 val getnode = Intmap.map nodes
248 :     val insnDefUse = Props.defUse cellkind
249 :     val getCell = C.getCell cellkind
250 :    
251 :     fun isDedicated r =
252 : leunga 624 Word.fromInt r < Word.fromInt(A.length dedicated)
253 :     andalso UA.sub(dedicated, r)
254 : monnier 467
255 : monnier 498 (* Remove all dedicated or spilled registers from the list *)
256 : monnier 467 fun rmvDedicated regs =
257 :     let fun loop([], rs') = rs'
258 :     | loop(r::rs, rs') =
259 :     let val r = regmap r
260 :     in loop(rs, if isDedicated r then rs' else r::rs') end
261 :     in loop(regs, []) end
262 :    
263 :     (*
264 :     * Create parallel move
265 :     *)
266 : leunga 624 fun mkMoves(insn, pt, dst, src, cost, mv, tmps) =
267 : monnier 467 if Props.moveInstr insn then
268 :     let val (dst, tmps) =
269 :     case (Props.moveTmpR insn, dst) of
270 :     (SOME r, _::dst) =>
271 :     (* Add a pseudo use for tmpR *)
272 : monnier 498 let fun chase(NODE{color=ref(ALIASED n), ...}) =
273 :     chase n
274 :     | chase n = n
275 : george 545 in case chase(getnode r) of
276 :     tmp as NODE{uses,defs=ref [d],...} =>
277 :     (uses := [d-1]; (dst, tmp::tmps))
278 :     | _ => error "mkMoves"
279 :     end
280 : monnier 467 | (_, dst) => (dst, tmps)
281 :     fun moves([], [], mv) = mv
282 :     | moves(d::ds, s::ss, mv) =
283 :     if isDedicated d orelse isDedicated s
284 :     then moves(ds, ss, mv)
285 :     else
286 : monnier 498 let fun chases(NODE{color=ref(ALIASED src), ...}, dst) =
287 :     chases(src, dst)
288 :     | chases(src, dst) = chases'(src, dst)
289 :     and chases'(src, NODE{color=ref(ALIASED dst), ...}) =
290 :     chases'(src, dst)
291 :     | chases'(src, dst) = (src, dst)
292 :     val (src as NODE{number=s, ...},
293 :     dst as NODE{number=d, ...}) =
294 :     chases(getnode s, getnode d)
295 : monnier 467 in if d = s then moves(ds, ss, mv)
296 : leunga 624 else (addCopy(s, {dst=d, pt=pt}::lookupCopy s);
297 :     moves(ds, ss, MV{dst=dst, src=src,
298 : monnier 467 status=ref WORKLIST,
299 : monnier 498 hicount=ref 0,
300 : monnier 467 (* kind=REG_TO_REG, *)
301 :     cost=cost}::mv)
302 : leunga 624 )
303 : monnier 467 end
304 :     | moves _ = error "moves"
305 :     in (moves(dst, src, mv), tmps) end
306 :     else (mv, tmps)
307 :    
308 :     (* Add the nodes first *)
309 :     fun mkNodes([], mv, tmps) = (mv, tmps)
310 :     | mkNodes(F.BBLOCK{blknum, insns, succ, freq=ref w,
311 :     liveOut, ...}::blks, mv, tmps)=
312 :     let val dtab = A.sub(defsTable, blknum)
313 :     fun scan([], pt, i, mv, tmps) = (pt, i, mv, tmps)
314 : leunga 624 | scan(insn::rest, pt, i, mv, tmps) =
315 : monnier 467 let val (d, u) = insnDefUse insn
316 :     val defs = rmvDedicated d
317 :     val uses = rmvDedicated u
318 :     val defs = newNodes{cost=w, pt=pt,
319 :     defs=defs, uses=uses}
320 :     val _ = UA.update(dtab, i, defs)
321 : leunga 624 val (mv, tmps) = mkMoves(insn, pt, d, u, w, mv, tmps)
322 : monnier 498 in scan(rest, pt+1, i+1, mv, tmps)
323 : monnier 467 end
324 :     val (pt, i, mv, tmps) =
325 :     scan(!insns, progPt(blknum,1), 1, mv, tmps)
326 :     val _ = if pt >= progPt(blknum+1, 0) then
327 : monnier 498 error("mkNodes: too many instructions")
328 : monnier 467 else ()
329 : leunga 585 in (* If the block is escaping, then all liveout
330 : monnier 467 * registers are considered used here.
331 :     *)
332 :     case !succ of
333 :     [(F.EXIT _, _)] =>
334 :     let val liveSet = rmvDedicated(getCell(!liveOut))
335 :     in newNodes{cost=w, pt=progPt(blknum, 0),
336 :     defs=[], uses=liveSet}; ()
337 :     end
338 :     | _ => ()
339 :     ;
340 :     mkNodes(blks, mv, tmps)
341 :     end
342 :     | mkNodes(_::blks, mv, tmps) = mkNodes(blks, mv, tmps)
343 :    
344 :     (* Add the edges *)
345 :    
346 :     val (moves, tmps) = mkNodes(blocks, [], [])
347 : monnier 498 val addEdge = Core.addEdge G
348 :     in Intmap.app
349 : leunga 624 (let val setSpan =
350 :     if isOn(mode,Core.COMPUTE_SPAN) then
351 :     let val spanMap = Intmap.new(Intmap.elems nodes, NotThere)
352 :     val setSpan = Intmap.add spanMap
353 :     val _ = span := SOME spanMap
354 :     in setSpan end
355 :     else fn _ => ()
356 :     in fn (v, v' as NODE{color=ref(PSEUDO | COLORED _), ...}) =>
357 :     setSpan(v, liveness(v, v', addEdge))
358 :     | (v, v' as NODE{color=ref(SPILLED c), ...}) =>
359 :     if c >= 0 then setSpan(v, liveness(v, v', addEdge)) else ()
360 :     | _ => ()
361 :     end
362 : monnier 498 ) nodes;
363 :     if isOn(Core.SAVE_COPY_TEMPS, mode) then copyTmps := tmps else ();
364 : monnier 467 rmPseudoUses tmps;
365 :     moves
366 :     end
367 :    
368 :     (*
369 :     * Build the interference graph initially.
370 :     *)
371 :     fun build(G, cellkind) = buildIt(cellkind, C.lookup regmap, G)
372 :    
373 :     (*
374 :     * Rebuild the interference graph;
375 :     * We'll just do it from scratch for now.
376 :     *)
377 :     fun rebuild(cellkind, G) =
378 : leunga 579 (Core.clearNodes G;
379 :     buildIt(cellkind, Core.regmap G, G)
380 :     )
381 : monnier 467
382 :     (*
383 :     * Spill a set of nodes and rewrite the flowgraph
384 :     *)
385 : monnier 498 fun spill{copyInstr, spill, spillSrc, spillCopyTmp,
386 :     reload, reloadDst, renameSrc, graph as G.GRAPH{regmap, ...},
387 : monnier 467 cellkind, nodes=nodesToSpill} =
388 : leunga 579 let (* Remove the interference graph now *)
389 :     val _ = Core.clearGraph graph
390 :    
391 : monnier 467 (* maps program point to registers to be spilled *)
392 :     val spillSet = Intmap.new(32, NotThere) : C.cell list Intmap.intmap
393 :    
394 :     (* maps program point to registers to be reloaded *)
395 :     val reloadSet = Intmap.new(32, NotThere) : C.cell list Intmap.intmap
396 :    
397 :     (* maps program point to registers to be killed *)
398 :     val killSet = Intmap.new(32, NotThere) : C.cell list Intmap.intmap
399 :    
400 : monnier 498 val spillRewrite = Spill.spillRewrite
401 :     { graph=graph,
402 :     spill=spill,
403 :     spillSrc=spillSrc,
404 :     spillCopyTmp=spillCopyTmp,
405 :     reload=reload,
406 :     reloadDst=reloadDst,
407 :     renameSrc=renameSrc,
408 :     copyInstr=copyInstr,
409 :     cellkind=cellkind,
410 :     spillSet=spillSet,
411 :     reloadSet=reloadSet,
412 :     killSet=killSet
413 :     }
414 :    
415 : monnier 467 (* set of basic blocks that are affected *)
416 :     val affectedBlocks = Intmap.new(32, NotThere) : bool Intmap.intmap
417 :    
418 :     val addAffectedBlocks = Intmap.add affectedBlocks
419 :    
420 :     fun ins set =
421 :     let val add = Intmap.add set
422 :     val look = Intmap.mapWithDefault(set, [])
423 : leunga 579 fun enter(r, []) = ()
424 :     | enter(r, pt::pts) =
425 :     (add (pt, r::look pt);
426 :     addAffectedBlocks (blockNum pt, true);
427 :     enter(r, pts)
428 :     )
429 :     in enter
430 : monnier 467 end
431 :    
432 :     val insSpillSet = ins spillSet
433 :     val insReloadSet = ins reloadSet
434 :     val insKillSet =
435 :     let val add = Intmap.add killSet
436 :     val look = Intmap.mapWithDefault(killSet, [])
437 : leunga 579 fun enter(r, []) = ()
438 :     | enter(r, pt::pts) = (add(pt, r::look pt); enter(r, pts))
439 :     in enter
440 :     end
441 : monnier 467
442 : monnier 498 (* Mark all spill/reload locations *)
443 : leunga 579 fun markSpills [] = ()
444 :     | markSpills(
445 :     G.NODE{color, number, defs as ref d, uses as ref u, ...}::ns) =
446 : monnier 498 let fun spillIt(defs, uses) =
447 : leunga 579 (insSpillSet(number, defs);
448 :     insReloadSet(number, uses);
449 : monnier 498 (* Definitions but no use! *)
450 :     case uses of
451 : leunga 579 [] => insKillSet(number, defs)
452 : monnier 498 | _ => ()
453 :     )
454 :     in case !color of
455 : leunga 579 G.SPILLED c => spillIt(d, u)
456 :     | G.PSEUDO => spillIt(d, u)
457 :     | _ => ();
458 :     markSpills ns
459 : monnier 498 end
460 :     val _ = markSpills nodesToSpill
461 : monnier 467
462 :     (* Rewrite all affected blocks *)
463 :     fun rewriteAll (blknum, _) =
464 : george 545 case A.sub(blockTable, blknum) of
465 :     F.BBLOCK{annotations, insns as ref instrs, ...} =>
466 :     let val instrs =
467 :     spillRewrite{pt=progPt(blknum, length instrs),
468 :     instrs=instrs,
469 :     annotations=annotations}
470 :     in insns := instrs
471 :     end
472 :     | _ => error "rewriteAll"
473 : monnier 467
474 :     in Intmap.app rewriteAll affectedBlocks;
475 : monnier 498 let val spilledMarker = SPILLED ~2
476 : leunga 579 fun mark [] = ()
477 :     | mark(G.NODE{number, color as ref(SPILLED c), ...}::rest)=
478 :     (if number <> c then color := spilledMarker else ();
479 :     mark rest)
480 :     | mark(G.NODE{color as ref PSEUDO, ...}::rest) =
481 :     (color := spilledMarker; mark rest)
482 :     | mark(_::rest) = mark rest
483 :     in mark nodesToSpill
484 : monnier 498 end;
485 : monnier 467 rebuild(cellkind, graph)
486 :     end
487 :    
488 : monnier 498 in {build=build, spill=spill,
489 :     programPoint=fn{block,instr} => progPt(block,instr),
490 :     blockNum=blockNum,
491 :     instrNum=instrNum
492 :     }
493 : monnier 467 end
494 :    
495 :     end

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