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

Parent Directory | 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