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 /MLRISC/trunk/scheduling/listScheduler.sml
ViewVC logotype

Annotation of /MLRISC/trunk/scheduling/listScheduler.sml

Parent Directory Parent Directory | Revision Log Revision Log


Revision 2126 - (view) (download)

1 : leunga 695 (* Disclaimer...
2 :     * =============
3 :     *
4 :     * I've written and re-written many global schedulers thru the years.
5 :     * It is always hard to get right. Hopefully this is the last time I have
6 :     * to write/rewrite one for a long while...
7 :     *
8 :     * A parameterizable list scheduler.
9 :     * ================================
10 :     * This list scheduler does a few things:
11 :     * 1. Works on a region at a time instead of one basic block
12 :     * 2. Can perform replication
13 :     * 3. Can perform register renaming to get around of anti-/output- dependences
14 :     * 4. Recognizes the distinction between initializations (which can be
15 :     * speculation) versus stores (which cannot be).
16 :     *
17 :     * Some notes on how the list scheduling algorithm work:
18 :     * 1. (Side)-entries and (side)-exits are cfg edges that come into and out of
19 :     * the current region.
20 :     * 2. The region to be scheduled has to be acyclic. Cyclic edges are cut
21 :     * arbitrarily (by the region forming combinator.)
22 :     * 3. Every block that has side-entries has an "live-in" node that summaries
23 :     * all the values that are defined coming in the side-entires. Similarly,
24 :     * for all blocks with side-exits we have "live-out" nodes.
25 :     * 4. During list scheduling, multiple blocks may be "open" at the same time.
26 :     * Instructions can only be placed within open blocks.
27 :     * 5. Once every instruction (that appears in the block originally)
28 :     * has been scheduled, the block is then "closed".
29 :     * 6. A new block is opened if all its predecessors is closed.
30 :     * 7. "Ready" instructions, i.e. instructions with all its predecessors
31 :     * schedules are put onto a priority list. The priority list is ranked
32 :     * by the execution frequency of the instruction.
33 :     * 8. At each step, an instruction i is chosen from the priority list to
34 :     * be scheduled. This instruction has to be placed at "all" open blocks
35 :     * that reaches the block where instruction originates. This may involve
36 :     * replicating the instruction. For this transformation to be legal,
37 :     * structural and profitability checks have to be performed.
38 :     *
39 :     * a. Structural check determines whether it is semantics preserving
40 :     * to put this instruction into the set of open blocks.
41 :     * b. Profitability check determines whether it is profitable, i.e. is
42 :     * it okay to put this instruction to these blocks or should we delay
43 :     * it.
44 :     *
45 :     * Instructions that fail these criteria are moved into a pending queue.
46 :     * 9. Instructions from the pending queue are released back into the ready
47 :     * queue whenever the set of open blocks change.
48 :     * 10. BUT ... this is not the entire story. When scheduling dags, the
49 :     * dependency graph initially built is insufficient to summarize all
50 :     * dependences. For that to work, incremental liveness computation
51 :     * must also be performed. This is how it works:
52 :     *
53 :     * a. Each open block keeps track of what registers are live at the
54 :     * current time. Liveness can be inferred via the dependence dag
55 :     *
56 :     * -- Allen (leunga@cs.nyu.edu) 6/1/00
57 :     *)
58 :     functor ListScheduler
59 :     (structure DDG : SCHEDULER_DDG
60 :     structure IR : MLRISC_IR
61 :     structure InsnProps : INSN_PROPERTIES
62 :     structure FormatInsn : FORMAT_INSTRUCTION
63 :     (* structure Rewrite : REWRITE_INSTRUCTIONS *)
64 :     sharing DDG.I = InsnProps.I = IR.I = (* = Rewrite.I *)
65 :     FormatInsn.I
66 :     ) : LIST_SCHEDULER =
67 :     struct
68 :    
69 :     structure IR = IR
70 :     structure CFG = IR.CFG
71 :     structure DDG = DDG
72 :     structure I = DDG.I
73 :     structure SchedProps = DDG.SchedProps
74 :     structure G = Graph
75 :     structure A = Array
76 :     structure DA = DynArray
77 :     structure W8A = Word8Array
78 :     structure PQ = PriorityQueue
79 :    
80 :     fun error msg = MLRiscErrorMsg.error("ListScheduler",msg)
81 :    
82 :     val debug = true
83 :     val verbose = true
84 :     val safetyCheck = true
85 :    
86 :     val i2s = Int.toString
87 :    
88 :     exception NotOpened
89 :     exception NotLive
90 :    
91 :     val dummyJump = (~1,DDG.NODE{instr=InsnProps.nop(),defs=[],uses=[],b= ~1})
92 :    
93 :     (* data structure to hold info about a block *)
94 :     datatype openBlock =
95 :     OPEN_BLOCK of
96 :     {bid : int, (* block id *)
97 :     reachables : W8A.array, (* reachable set *)
98 :     rt : SchedProps.reservation_table, (* reservation table *)
99 :     sigma : I.instruction list DA.array,
100 : leunga 744 liveSet : DDG.edge G.edge list IntHashTable.hash_table,
101 : leunga 695 jumpScheduled : bool ref,
102 :     jumpTime : int ref,
103 :     jumpNode : DDG.node G.node ref
104 :     }
105 :    
106 :     val profitabilityRatio = 0.5
107 :    
108 :     fun listScheduler{ranking, cpu_info, blockIdTbl, cfg, region, ddg} =
109 :     let
110 :     (* Extract architecture info from the data base *)
111 :     val SchedProps.CPU_INFO{newTable, findSlot, pipeline, insert, ...} =
112 :     cpu_info
113 :    
114 :     (* The data structures:
115 :     * succ, pred --- adjacency lists
116 :     * blockMap --- mapping from internal block id -> real block id
117 :     * liveInMap --- mapping from internal block id -> live in node
118 :     * liveOutMap --- mapping from internal block id -> live out node
119 :     * issueTimeTbl --- node id --> its issue time
120 :     * inDegsTbl --- node id --> its current in-degree
121 :     * insnCountTbl --- internal block id --> number of unscheduled instrs
122 :     *)
123 :     val DDG as G.GRAPH ddg = ddg
124 :     val CFG as G.GRAPH cfg = cfg
125 :     val Region as G.GRAPH region = region
126 :     val {succ, pred, ...} = DDG.internalInfo DDG
127 :     val SOME{blockMap, liveInMap, liveOutMap, ...} = !(DDG.globalInfo DDG)
128 :     val N = #capacity ddg () (* number of instructions *)
129 :     val M = #order region () (* number of blocks in the region *)
130 :    
131 :     (* Internal tables indexed by instruction id *)
132 :     val issueTimeTbl = A.array(N,~1) (* issue times of instructions *)
133 :     val inDegsTbl = A.array(N,0) (* in-degree of a node *)
134 :    
135 :     (* Internal tables indexed by block id *)
136 :     val insnCountTbl = A.array(M, 0) (* number of instructions per block *)
137 :     val freqTbl = A.array(M, 0) (* execution frequency of blocks *)
138 :     val predCountTbl = A.array(M, 0) (* in degree of blocks *)
139 :     val rtTbl = A.array(M,newTable 0)
140 :     val startTimeTbl = A.array(M, 0)
141 :     val maxTimeTbl = A.array(M, 0)
142 :     val isLegalTbl = A.array(M, 0) (* is it legal to schedule
143 :     block id at this time *)
144 :     val isProfitableTbl = A.array(M, 0)
145 :     val profitabilityTbl = A.array(M, 0.0) (* priority of block *)
146 : leunga 744 val liveSetTbl = A.array(M, IntHashTable.mkTable(0, NotLive))
147 : leunga 695
148 :     val stampCounter = ref 0
149 :     fun newStamp() =
150 :     let val st = !stampCounter + 1
151 :     in stampCounter := st; st end
152 :    
153 :     (* Linearize the schedule *)
154 :     fun linearize sigma =
155 :     DA.foldl (fn (instrs,l) => instrs @ l) [] sigma
156 :    
157 :     (* It is okay to move an instruction from block id *)
158 :     fun isLegalMove id = A.sub(isLegalTbl, id) = !stampCounter
159 :     fun isProfitableMove id = A.sub(isProfitableTbl, id) = !stampCounter
160 :    
161 :     val showInsn = FormatInsn.toString [] (I.C.lookup (CFG.regmap CFG))
162 :     fun showOp(DDG.NODE{instr,b,...}) =
163 :     showInsn instr^" ["^i2s(A.sub(blockMap,b))^"]"
164 :    
165 :     fun isJump instr =
166 :     case InsnProps.instrKind instr of
167 :     InsnProps.IK_JUMP => true
168 :     | _ => false
169 :    
170 :     (* Real priority function *)
171 :     fun priorityFun(I as (i,DDG.NODE{b=b_i,...}),
172 :     J as (j,DDG.NODE{b=b_j,...})) =
173 :     let val p_i = A.sub(profitabilityTbl,b_i)
174 :     val p_j = A.sub(profitabilityTbl,b_j)
175 :     in case Real.compare(p_i,p_j) of
176 :     EQUAL => ranking(I,J)
177 :     | GREATER => true
178 :     | LESS => false
179 :     end
180 :    
181 :    
182 :     (* Initialization steps:
183 :     * 1. Initialize the frequency array
184 :     * 2. Count the number of predecessors of each block in the region
185 :     * 3. Count the number of non-special instructions
186 :     * 4. Initialize the pending queue
187 :     *)
188 :     fun initialize() =
189 :     let (* Initialize the frequencies *)
190 :     val _ =
191 :     A.appi (fn (id,b) =>
192 :     let val CFG.BLOCK{freq, ...} = #node_info region b
193 :     in A.update(freqTbl, id, !freq);
194 :     A.update(predCountTbl, id, length(#in_edges region b))
195 :     end) (blockMap, 0, NONE)
196 :     val pendingNodes =
197 :     foldr
198 :     (fn ((i,i'),pending) =>
199 :     let val inEdges = #in_edges ddg i
200 :     val n = length inEdges
201 :     val DDG.NODE{b, instr, ...} = i'
202 :     fun addToPending() =
203 :     if n = 0
204 :     then (i, i')::pending
205 :     else (A.update(inDegsTbl, i, n); pending)
206 :     in case InsnProps.instrKind instr of
207 :     InsnProps.IK_SINK => pending
208 :     | InsnProps.IK_SOURCE => pending
209 :     | _ =>
210 :     (A.update(insnCountTbl, b, A.sub(insnCountTbl, b) + 1);
211 :     addToPending()
212 :     )
213 :     end
214 :     ) [] (#nodes ddg ())
215 :     in pendingNodes
216 :     end
217 :    
218 :     (* Queues *)
219 :     val readyQueue = PQ.create priorityFun
220 :     val enqueue = PQ.insert readyQueue
221 :     val pending = ref(initialize())
222 :     (*
223 :     val enqueue = if debug then
224 :     (fn (i,i') => (print("QUEUEING "^showOp i'^"\n"); enqueue (i,i')))
225 :     else enqueue
226 :     *)
227 :    
228 :     (* === Incremental liveness computation routines === *)
229 :    
230 :     (*
231 :     * Add an instruction into the current live set of block bid.
232 :     *)
233 :     fun addInstrToLiveSet(i, i' as DDG.NODE{defs, uses, ...}, liveSet) =
234 : leunga 744 let val lookupLiveSet = IntHashTable.find liveSet
235 :     val lookupLiveSet = fn b => case lookupLiveSet b of SOME x => x
236 :     | NONE => []
237 :     val updateLiveSet = IntHashTable.insert liveSet
238 : leunga 695
239 :     fun rmvUse r =
240 :     let fun loop([], es') = es'
241 :     | loop((e as (j,k,_))::es, es') =
242 :     if i = k then loop(es, es') else loop(es, e::es')
243 :     val es = lookupLiveSet r
244 :     val es = loop(es, [])
245 :     in updateLiveSet(r, es) end
246 :    
247 :     fun rmvUses [] = ()
248 :     | rmvUses(r::uses) = (rmvUse r; rmvUses uses)
249 :    
250 :     fun addDef(r, e) = updateLiveSet(r, e::lookupLiveSet r)
251 :    
252 :     fun addDefs [] = ()
253 :     | addDefs((edge as (i,j,e as DDG.EDGE{r,d,...}))::es) =
254 :     ((* print(i2s i^" -> "^i2s j^" "^DDG.edgeToString e^"\n"); *)
255 :     if r >= 0 then addDef(r, edge) else ();
256 :     addDefs es
257 :     )
258 :    
259 :     in rmvUses uses;
260 :     addDefs (A.sub(succ, i))
261 :     end
262 :    
263 :     (*
264 :     * Check whether it is a legal code motion to move an instruction i
265 :     * from block "from" to block "to". Instruction i must have no
266 :     * unscheduled predecessors at this point.
267 :     *)
268 :     fun isIllegalCodeMotion(i, i' as DDG.NODE{defs, ...}, liveSet) =
269 :     let (* Check whether instruction i defines a register r
270 :     * that is currently live. If so, the associated code motion is
271 :     * illegal (without renaming)
272 :     *)
273 : leunga 744 val lookupLiveSet = IntHashTable.find liveSet
274 :     val lookupLiveSet = fn b => case lookupLiveSet b of SOME x => x
275 :     | NONE => []
276 : leunga 695 (*
277 :     * Add an output- dependence edge between two nodes
278 :     *)
279 :     fun addOutputDepEdge(i,j,r) =
280 :     (#add_edge ddg (i,j, DDG.EDGE{l= ~1, d=DDG.OUTPUT, r=r});
281 :     A.update(inDegsTbl, j, A.sub(inDegsTbl, j) + 1)
282 :     )
283 :    
284 :     fun isLiveReg r =
285 :     let fun loop [] = false
286 :     | loop((j,k:int,e)::es) =
287 :     if i = k then loop es else
288 :     (if debug then
289 :     print("BAD: "^i2s j^" -> "^i2s k^" "^
290 :     DDG.edgeToString e^
291 :     " "^showOp(#node_info ddg j)^" -> "^
292 :     " "^showOp(#node_info ddg k)^"\n"
293 :     )
294 :     else ();
295 :     true
296 :     )
297 :     (* if i = k then i is the use of r so it doesn't count *)
298 :     in loop(lookupLiveSet r)
299 :     end
300 :     fun canKillLiveValues [] = false
301 :     | canKillLiveValues((r,_)::defs) =
302 :     isLiveReg r orelse canKillLiveValues defs
303 :     in canKillLiveValues defs
304 :     end
305 :    
306 :     (* Find out the time slot to insert the instruction j in
307 :     * reservation table rt (from block id)
308 :     *)
309 :     fun findScheduleSlot(bid, rt, p, j, j') =
310 :     let fun earliest([], t) = t
311 :     | earliest((i,j,e as DDG.EDGE{l,...})::es, t) =
312 :     let val t' = A.sub(issueTimeTbl,i)
313 :     val t'' = t' + l + 1
314 :     in (* if debug then
315 :     print(i2s i^" -> "^i2s j^" "^DDG.edgeToString e^
316 :     " t'="^i2s t'^" t''="^i2s t''^"\n")
317 :     else (); *)
318 :     earliest(es, Int.max(t, t''))
319 :     end
320 :     val t_min = earliest(A.sub(pred, j), A.sub(startTimeTbl, bid))
321 :     in findSlot(rt, t_min, p)
322 :     end
323 :    
324 :     (* Release an instruction when all its predecessors
325 :     * have been scheduled. Note that fake sink and source instructions
326 :     * must be treated specially and so we don't release them onto the queue.
327 :     *)
328 :     fun releaseInstr j =
329 :     let val j' as DDG.NODE{instr,b,...} = #node_info ddg j
330 :     in case InsnProps.instrKind instr of
331 :     InsnProps.IK_SOURCE => ()
332 :     | _ => if isProfitableMove b then enqueue(j,j')
333 :     else pending := (j,j') :: !pending
334 :     end
335 :    
336 :     (* Release the successors of an instruction
337 :     * after it has been scheduled
338 :     *)
339 :     fun updateSucc(i) =
340 :     let fun loop [] = ()
341 :     | loop((i,j,_)::es) =
342 :     let val n = A.sub(inDegsTbl, j)
343 :     in A.update(inDegsTbl, j, n-1);
344 :     if n = 1 then releaseInstr j else ();
345 :     loop es
346 :     end
347 :     in loop(A.sub(succ, i))
348 :     end
349 :    
350 :     (* Release the live-in node for block id *)
351 :     fun releaseLiveIn(bid,liveSet) =
352 : leunga 744 let val liveInNode as (j,j') = IntHashTable.lookup liveInMap bid
353 : leunga 695 in if A.sub(issueTimeTbl, j) < 0 then
354 :     (addInstrToLiveSet(j,j',liveSet);
355 :     A.update(issueTimeTbl, j, 0);
356 :     updateSucc j;
357 :     if debug then print("LIVEIN "^showOp j'^"\n") else ()
358 :     )
359 :     else ()
360 :     end handle _ => () (* no live-in node, so don't bother *)
361 :    
362 :     (* Release the live-out node for block id *)
363 :     fun releaseLiveOut(bid, liveSet) =
364 :     let val liveOutNode as (j,j' as DDG.NODE{instr,...}) =
365 : leunga 744 IntHashTable.lookup liveOutMap bid
366 : leunga 695 in case InsnProps.instrKind instr of
367 :     InsnProps.IK_SINK =>
368 :     (addInstrToLiveSet(j,j',liveSet);
369 :     A.update(issueTimeTbl, j, 0);
370 :     updateSucc j;
371 :     if debug then print("LIVEOUT "^showOp j'^"\n") else ()
372 :     )
373 :     | _ => error("releaseLiveOut "^showOp j')
374 :     end handle _ => () (* no live-out node, so don't bother *)
375 :    
376 :     fun printOpenBlocks blocks =
377 :     "[ "^
378 :     foldr (fn (OPEN_BLOCK{bid,...},l) =>
379 :     i2s(A.sub(blockMap,bid))^" "^l) "" blocks
380 :     ^"]"
381 :    
382 :     (* Move legal pending nodes from the pending queue and the ready queue
383 :     * to the ready queue.
384 :     *)
385 :     fun moveLegalPendingToReady() =
386 :     let fun scan([], pending) = pending
387 :     | scan((node as (j,DDG.NODE{b,...}))::nodes, pending) =
388 :     if isProfitableMove b then
389 :     (enqueue node; scan(nodes, pending))
390 :     else
391 :     scan(nodes, node::pending)
392 :     val waiting = List.revAppend(PQ.toList readyQueue, !pending)
393 :     in PQ.clear readyQueue;
394 :     pending := scan(waiting, [])
395 :     end
396 :    
397 :    
398 :     (* Given a set of openBlocks, compute the set of legal blocks
399 :     * and profitable blocks that can be scheduled at the current time.
400 :     * At this point, we also compute the profitability of moving
401 :     * an instruction from bid to the openBlockList.
402 :     * Move instructions from pending queue to the priority queue.
403 :     *)
404 :     fun updatePermittableCodeMotion openBlockList =
405 :     let val stamp = newStamp()
406 :    
407 :     (* What is the cost of moving an instruction from block source to
408 :     * the blocks in openBlockList?
409 :     *)
410 :     fun codeMotionCost(source) =
411 :     let fun loop([], C) = C
412 :     | loop(OPEN_BLOCK{reachables, bid=target, ...}::L, C) =
413 :     if W8A.sub(reachables, source) = 0w0 then loop(L, C)
414 :     else let val freq = A.sub(freqTbl, target)
415 :     in loop(L, C+freq) end
416 :     in loop(openBlockList, 0)
417 :     end
418 :    
419 :     (* Check whether it is profitable to move an instruction from
420 :     * block source. 1.0 means non-speculative. < 1.0 means
421 :     * speculative
422 :     *)
423 :     fun isProfitable(source) =
424 :     let val origCost = A.sub(freqTbl, source)
425 :     val moveCost = codeMotionCost(source)
426 :     val profitability = real origCost / real moveCost
427 :     in A.update(profitabilityTbl,source,profitability);
428 :     profitability >= profitabilityRatio
429 :     end
430 :    
431 :     fun markLegal([]) = ()
432 :     | markLegal(bid::Xs) =
433 :     if A.sub(isLegalTbl, bid) = stamp then markLegal Xs else
434 :     (A.update(isLegalTbl, bid, stamp);
435 :     if debug then print(i2s(A.sub(blockMap,bid))) else ();
436 :     if isProfitable bid then
437 :     (if debug then print "+" else ();
438 :     A.update(isProfitableTbl, bid, stamp)
439 :     )
440 :     else ();
441 :     if debug then print " " else ();
442 :     markLegal
443 :     (markSucc(#out_edges region (A.sub(blockMap, bid)), Xs))
444 :     )
445 :     and markSucc([], Xs) = Xs
446 :     | markSucc((_,Y,_)::es, Xs) =
447 :     if predAllLegal Y then markSucc(es, A.sub(blockIdTbl,Y)::Xs)
448 :     else markSucc(es, Xs)
449 :    
450 :     and predAllLegal X =
451 :     let fun loop [] = true
452 :     | loop((Y,_,_)::es) =
453 :     A.sub(isLegalTbl, A.sub(blockIdTbl, Y)) = stamp
454 :     andalso loop es
455 :     in (* IMPORTANT: prevent hoisting past side entries! *)
456 :     case #entry_edges region X of
457 :     [] => loop(#in_edges region X)
458 :     | _ => false
459 :     end
460 :     in if debug then print("LEGAL: ") else ();
461 :     markLegal(map (fn OPEN_BLOCK{bid,...} => bid) openBlockList);
462 :     if debug then print("\n") else ();
463 :     moveLegalPendingToReady();
464 :     openBlockList
465 :     end
466 :    
467 :     (* Open a new block b.
468 :     * Mark all blocks that b reaches.
469 :     *)
470 :     fun openBlock(b, openBlockList) =
471 :     let val bid = A.sub(blockIdTbl, b)
472 :     in if A.sub(isLegalTbl, bid) < 0 then (* closed permenantly! *)
473 :     openBlockList
474 :     else openBlock'(bid, b, openBlockList)
475 :     end
476 :    
477 :     and openBlock'(bid, b, openBlockList) =
478 :     let val reachables = W8A.array(M,0w0)
479 :     fun markReachables b =
480 :     let val bid = A.sub(blockIdTbl, b)
481 :     in if W8A.sub(reachables, bid) = 0w0 then
482 :     (W8A.update(reachables, bid, 0w1);
483 :     app markReachables (#succ region b)
484 :     )
485 :     else ()
486 :     end
487 :     val _ = markReachables b
488 :     fun mergeIncomingBlocks() =
489 : leunga 744 let val liveSet = IntHashTable.mkTable(32,NotLive)
490 :     val lookupLiveSet = IntHashTable.find liveSet
491 :     val lookupLiveSet =
492 :     fn b => case lookupLiveSet b of SOME x => x | NONE => []
493 :     val addLiveSet = IntHashTable.insert liveSet
494 : leunga 695 fun merge([], NONE) = (newTable 5, 0)
495 :     | merge([], SOME(_,t,rt)) = (rt, t+1)
496 :     | merge((Y,_,CFG.EDGE{w,...})::es,rt) =
497 :     let val Y_id = A.sub(blockIdTbl, Y)
498 :     val liveSet_Y = A.sub(liveSetTbl, Y_id)
499 :     val rt =
500 :     case rt of
501 :     NONE => SOME(!w,
502 :     A.sub(maxTimeTbl,Y_id),
503 :     A.sub(rtTbl,Y_id))
504 :     | SOME(w',_,rt') =>
505 :     if !w > w' then
506 :     SOME(!w,
507 :     A.sub(maxTimeTbl,Y_id),
508 :     A.sub(rtTbl,Y_id))
509 :     else rt
510 : leunga 744 in IntHashTable.appi (fn (r,es) =>
511 : leunga 695 addLiveSet(r, List.revAppend(es, lookupLiveSet r)))
512 :     liveSet_Y;
513 :     merge(es, rt)
514 :     end
515 :     val (rt, startTime) = merge (#in_edges region b, NONE)
516 :     in A.update(rtTbl, bid, rt);
517 :     A.update(startTimeTbl, bid, startTime);
518 :     A.update(liveSetTbl, bid, liveSet);
519 :     (liveSet, rt)
520 :     end
521 :     val _ = if debug then
522 :     print("OPENING "^i2s b^" "^printOpenBlocks openBlockList^
523 :     "("^i2s(A.sub(insnCountTbl,bid))^" insns)\n")
524 :     else ();
525 :     val (liveSet,rt) = mergeIncomingBlocks()
526 :     (* release live-in anchor of block b *)
527 :     val _ = releaseLiveIn(bid, liveSet)
528 :     val openBlock =
529 :     OPEN_BLOCK{bid=bid, rt=rt,
530 :     reachables=reachables,
531 :     liveSet=liveSet,
532 :     jumpScheduled=ref false,
533 :     sigma=DA.array(5,[]),
534 :     jumpTime=ref 10000000,
535 :     jumpNode=ref dummyJump
536 :     }
537 :     val openBlockList =
538 :     updatePermittableCodeMotion(openBlock::openBlockList)
539 :     in if A.sub(insnCountTbl, bid) = 0 then
540 :     closeBlock(bid, openBlockList)
541 :     else
542 :     openBlockList
543 :     end
544 :    
545 :     (* Close a block *)
546 :     and closeBlock(bid, openBlockList) =
547 :     let fun rmv((x as OPEN_BLOCK{bid=bid',rt,jumpScheduled,jumpTime,liveSet,
548 :     jumpNode=ref(j,j'),sigma,...})::L, L') =
549 :     if bid = bid' then
550 :     let val b = A.sub(blockMap, bid)
551 :     val CFG.BLOCK{insns, ...} = #node_info region b
552 :     val instrs = linearize sigma
553 :     val instrs = if !jumpScheduled then
554 :     let val DDG.NODE{instr=jmp,...} = j'
555 :     in addInstrToLiveSet(j, j', liveSet);
556 :     jmp :: instrs
557 :     end
558 :     else instrs
559 :     val _ = insns := instrs;
560 :     (* release live-in anchor of block id if it hasn't already
561 :     been released *)
562 :     val _ = releaseLiveIn(bid, liveSet);
563 :     (* release live-out anchor of block id *)
564 :     val _ = releaseLiveOut(bid, liveSet);
565 :     val n = A.sub(insnCountTbl, bid)
566 :     in if n > 0 then
567 :     print("WARNING block "^i2s b^" has "^i2s n^
568 :     " instruction(s) left over\n")
569 :     else ();
570 :     List.revAppend(L',L)
571 :     end
572 :     else rmv(L, x::L')
573 :     | rmv([], _) = raise NotOpened (* not found, it's okay *)
574 :     fun decCounts([], openBlockList) = openBlockList
575 :     | decCounts((_,Y,_)::es, openBlockList) =
576 :     let val bid_Y = A.sub(blockIdTbl, Y)
577 :     val n = A.sub(predCountTbl, bid_Y) - 1
578 :     in A.update(predCountTbl, bid_Y, n);
579 :     if n = 0 then decCounts(es, openBlock(Y, openBlockList))
580 :     else decCounts(es, openBlockList)
581 :     end
582 :     val openBlockList = rmv(openBlockList, [])
583 :     val _ = if debug then
584 :     print("CLOSING "^i2s(A.sub(blockMap, bid))^" "^
585 :     printOpenBlocks openBlockList^"\n")
586 :     else ()
587 :     val out_edges = #out_edges region (A.sub(blockMap, bid))
588 :    
589 :     val openBlockList = decCounts(out_edges, openBlockList)
590 :     in (* mark this block as closed forever *)
591 :     A.update(isLegalTbl, bid, ~1);
592 :     updatePermittableCodeMotion openBlockList
593 :     end handle NotOpened => openBlockList
594 :    
595 :     (* Close all blocks that have jump instruction scheduled *)
596 :     fun closeAllJumpedBlocks openBlockList =
597 :     let fun loop([], L') = L'
598 :     | loop((B as OPEN_BLOCK{bid, jumpScheduled,...})::L, L') =
599 :     if !jumpScheduled then loop(L, closeBlock(bid, B::L'))
600 :     else loop(L, B::L')
601 :     in loop(openBlockList, []) end
602 :    
603 :     (* Schedule an instruction:
604 :     * Given an instruction and a set of openBlocks, find out where
605 :     * the instruction has to be inserted at.
606 :     *)
607 :     fun scheduleInstr(openBlockList, j, j' as DDG.NODE{instr,b,...}) =
608 :     let val isJump = isJump instr
609 :     (* val blockName = #create MLRiscAnnotations.COMMENT
610 :     (i2s(A.sub(blockMap, bid))) *)
611 :    
612 :     val pipeline = pipeline instr
613 :    
614 :     (* Pass one: find out where to perform the code motion
615 :     * and whether it is legal
616 :     *)
617 :     fun pass1([], insertionPoints) = pass2(insertionPoints, 0)
618 :     | pass1((B as OPEN_BLOCK{rt,bid,reachables,liveSet,jumpTime,...})::
619 :     openBlocks, insertionPoints) =
620 :     if W8A.sub(reachables, b) = 0w0 (* unreachable! *)
621 :     then pass1(openBlocks, insertionPoints)
622 :     else if bid <> b andalso
623 :     isIllegalCodeMotion(j, j', liveSet) then
624 :     (* this is illegal; put instruction back to the
625 :     * pending queue.
626 :     *)
627 :     (if debug then print("ILLEGAL "^showOp j'^"\n") else ();
628 :     pending := (j,j') :: !pending;
629 :     openBlockList
630 :     )
631 :     else let val time = findScheduleSlot(bid, rt, pipeline, j, j')
632 :     in if time > !jumpTime then
633 :     (* Can't schedule this instruction because
634 :     * it must follow the jump instruction!
635 :     * Close this block instead.
636 :     *)
637 :     (pending := (j,j') :: !pending;
638 :     closeBlock(bid, openBlockList)
639 :     )
640 :     else
641 :     pass1(openBlocks, (time, B)::insertionPoints)
642 :     end
643 :    
644 :    
645 :     (* Pass two: perform the actual insertion *)
646 :     and pass2([], replicationCount) = finish()
647 :     | pass2((time,
648 :     OPEN_BLOCK{bid, rt, reachables, liveSet, sigma,
649 :     jumpScheduled, jumpTime, jumpNode, ...})::
650 :     insertionPoints, replicationCount) =
651 :     (* a copy of instruction j has to be placed in reservation
652 :     * table rt.
653 :     *)
654 :     let val instr = if replicationCount > 0 then
655 :     InsnProps.replicate instr else instr
656 :     (* val instr = if bid <> b then
657 :     InsnProps.annotate(instr,blockName)
658 :     else instr *)
659 :     in insert(rt, time, pipeline);
660 :     A.update(issueTimeTbl, j,
661 :     Int.max(time, A.sub(issueTimeTbl, j)));
662 :     A.update(maxTimeTbl, bid,
663 :     Int.max(time, A.sub(maxTimeTbl, bid)));
664 :     if debug andalso (verbose orelse b <> bid) then
665 :     print(
666 :     "Time "^i2s time^
667 :     (if replicationCount > 0 then
668 :     " ("^i2s replicationCount^")"
669 :     else "")^
670 :     " "^showInsn instr^
671 :     " ["^i2s(A.sub(blockMap,b))^
672 :     "] scheduled in block "^i2s(A.sub(blockMap,bid))^
673 :     (if b <> bid then " ***" else "")^
674 :     (if !jumpScheduled then "!!!" else "")^
675 :     "\n")
676 :     else ();
677 :     (* Jump processing *)
678 :     if isJump then
679 :     (jumpScheduled := true;
680 :     jumpTime := time;
681 :     jumpNode := (j, j')
682 :     )
683 :     else
684 :     (addInstrToLiveSet(j, j', liveSet);
685 :     DA.update(sigma, time, instr::DA.sub(sigma, time))
686 :     );
687 :     pass2(insertionPoints, replicationCount+1)
688 :     end
689 :    
690 :     (* Do these things after successfully scheduled an instruction *)
691 :     and finish() =
692 :     let val _ = updateSucc j;
693 :     val n = A.sub(insnCountTbl, b) - 1
694 :     in A.update(insnCountTbl, b, n);
695 :     (* if we have run out instructions or else
696 :     * we have scheduled the jump instruction, we can
697 :     * close the current block.
698 :     * At this point we wait until we can't find any instructions
699 :     * that be scheduled ahead of the current jump instruction.
700 :     *)
701 :     if isJump then openBlockList
702 :     else if n = 0 then closeBlock(b, openBlockList)
703 :     else openBlockList
704 :     end
705 :    
706 :     in pass1(openBlockList, [])
707 :     end
708 :    
709 :     (* Main loop *)
710 :     fun schedule(openBlockList) =
711 :     if PQ.isEmpty readyQueue then
712 :     let val L = closeAllJumpedBlocks openBlockList
713 :     val L = updatePermittableCodeMotion L
714 :     in case L of
715 :     [] => ()
716 :     | _ => schedule L
717 :     end
718 :     else
719 :     let val (j, j' as DDG.NODE{b,...}) = PQ.deleteMin readyQueue
720 :     val openBlockList = scheduleInstr(openBlockList,j,j')
721 :     in schedule openBlockList
722 :     end
723 :    
724 :     fun scheduleAll() =
725 :     let val entries = #entries region ()
726 :     (* find blocks without predecessors in the region *)
727 :     val openBlockList = foldr
728 :     (fn (b,L) => if A.sub(predCountTbl, A.sub(blockIdTbl, b)) = 0
729 :     then openBlock(b,L) else L
730 :     ) [] entries
731 :     in case openBlockList of
732 :     [] => error "cyclic region"
733 :     | _ => schedule(updatePermittableCodeMotion openBlockList)
734 :     end
735 :    
736 :     fun sanityCheck() =
737 :     let val ok = ref true
738 :     in #forall_nodes ddg
739 :     (fn (i,i') =>
740 :     if A.sub(issueTimeTbl,i) < 0 then
741 :     (print("UNSCHEDULED "^showOp i'^
742 :     " |pred|="^i2s(A.sub(inDegsTbl, i))^"\n");
743 :     app (fn (j,i,e) =>
744 :     if A.sub(issueTimeTbl,j) < 0 then
745 :     (print("\t"^i2s j^" -> "^i2s i^" "^
746 :     DDG.edgeToString e);
747 :     print("\t"^showOp(#node_info ddg j)^"\n")
748 :     )
749 :     else ()) (#in_edges ddg i);
750 :     print "\n";
751 :     ok := false
752 :     )
753 :     else ()
754 :     );
755 :     if !ok then () else error "Scheduling error"
756 :     end
757 :    
758 :     in (* #forall_edges ddg (fn (i,j,e) =>
759 :     print(showOp(#node_info ddg i)^" -> "^showOp(#node_info ddg j)^" "^
760 :     DDG.edgeToString e^"\n")); *)
761 :     scheduleAll();
762 :     if safetyCheck then sanityCheck() else ()
763 :     end
764 :    
765 :     end

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