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

Annotation of /sml/trunk/src/MLRISC/backpatch/spanDep.sml

Parent Directory Parent Directory | Revision Log Revision Log


Revision 1124 - (view) (download)

1 : monnier 247 (*
2 :     * This version of the span dependency resolution also fill delay slots
3 : george 1000 * using a few simple strategies.
4 :     *
5 :     * Assumption: Instructions are 32bits.
6 : monnier 247 *
7 :     * Allen
8 :     *)
9 :    
10 :     functor SpanDependencyResolution
11 : george 984 (structure Emitter : INSTRUCTION_EMITTER
12 :     structure CFG : CONTROL_FLOW_GRAPH
13 :     where I = Emitter.I
14 :     and P = Emitter.S.P
15 : george 909 structure Jumps : SDI_JUMPS
16 : george 933 where I = CFG.I
17 : monnier 247 structure DelaySlot : DELAY_SLOT_PROPERTIES
18 : george 933 where I = CFG.I
19 : george 909 structure Props : INSN_PROPERTIES
20 : george 933 where I = CFG.I
21 :     ) : BBSCHED =
22 : monnier 247 struct
23 :    
24 : george 909 structure CFG = CFG
25 : monnier 411 structure E = Emitter
26 : george 909 structure I = CFG.I
27 : monnier 247 structure C = I.C
28 :     structure J = Jumps
29 : george 909 structure P = CFG.P
30 : monnier 247 structure D = DelaySlot
31 : george 909 structure G = Graph
32 : monnier 247 structure A = Array
33 :    
34 : george 1124 structure DefaultPlacement = DefaultBlockPlacement(CFG)
35 :     structure WeightedPlacement =
36 :     WeightedBlockPlacementFn(structure CFG = CFG structure InsnProps = Props)
37 :    
38 :     val placementFlag = MLRiscControl.getFlag "weighted-block-placement"
39 :     val blockPlacement =
40 :     if !placementFlag then WeightedPlacement.blockPlacement
41 :     else DefaultPlacement.blockPlacement
42 :    
43 : monnier 411 fun error msg = MLRiscErrorMsg.error("SpanDependencyResolution",msg)
44 : monnier 247
45 :     datatype code =
46 :     SDI of {size : int ref, (* variable sized *)
47 :     insn : I.instruction}
48 :     | FIXED of {size: int, (* size of fixed instructions *)
49 :     insns: I.instruction list}
50 :     | BRANCH of {insn : code list, (* instruction with delay slot*)
51 :     branchSize : int,
52 :     fillSlot : bool ref}
53 :     | DELAYSLOT of {insn : code list, (* instruction in delay slot *)
54 :     fillSlot : bool ref}
55 :     | CANDIDATE of (* two alternatives *)
56 :     { oldInsns : code list, (* without delay slot filling *)
57 :     newInsns : code list, (* when delay slot is filled *)
58 :     fillSlot : bool ref (* should we fill the delay slot? *)
59 :     }
60 :    
61 :     datatype compressed =
62 :     PSEUDO of P.pseudo_op
63 :     | LABEL of Label.label
64 :     | CODE of Label.label * code list
65 : george 1000
66 :     datatype cluster = CLUSTER of {comp : compressed list}
67 : monnier 247
68 : george 1000 val clusterList : cluster list ref = ref []
69 : george 984 val dataList : P.pseudo_op list ref = ref []
70 :     fun cleanUp() = (clusterList := []; dataList := [])
71 : monnier 247
72 : george 909 fun bbsched(cfg as G.GRAPH graph) = let
73 :     fun maxBlockId (CFG.BLOCK{id, ...}::rest, curr) =
74 :     if id > curr then maxBlockId(rest, id) else maxBlockId(rest, curr)
75 :     | maxBlockId([], curr) = curr
76 : george 1124 val blocks = map #2 (blockPlacement(cfg))
77 : george 909 val N = maxBlockId(blocks, #capacity graph ())
78 : monnier 247
79 : george 909 (* Order of blocks in code layout *)
80 :     val blkOrder = Array.array(N, 0)
81 : monnier 247
82 : george 909 (* Maps blknum -> label at the position of the second instruction *)
83 :     (* This is incase the first instruction gets used to fill a delay slot *)
84 :     val dummy = Label.anon ()
85 :     val labelMap = A.array(N, dummy)
86 : monnier 247
87 : george 909 (* enter labels into the labelMap *)
88 :     fun enterLabels(blocks) =
89 :     List.app
90 :     (fn CFG.BLOCK{id, ...} => Array.update(labelMap, id, Label.anon ()))
91 :     blocks
92 : monnier 247
93 : george 909 (* create block order *)
94 :     fun blockOrder(blocks) = let
95 :     fun order(CFG.BLOCK{id, ...}, n) = (Array.update(blkOrder, id, n); n+1)
96 :     in List.foldl order 0 blocks
97 :     end
98 : monnier 411
99 : george 909 fun isFallthrough(blk1, blk2) =
100 :     Array.sub(blkOrder, blk1) + 1 = Array.sub(blkOrder, blk2)
101 :    
102 :     fun isBackwards(blk1, blk2) =
103 :     Array.sub(blkOrder, blk2) <= Array.sub(blkOrder, blk1)
104 :    
105 :     (* zero length copy instruction *)
106 :     fun isEmptyCopy instr =
107 :     Props.instrKind(instr) = Props.IK_COPY
108 :     andalso J.sdiSize(instr, Label.addrOf, 0) = 0
109 :    
110 :     (* Find the target of a block, and return the first instruction and
111 :     * its associated label.
112 :     *)
113 :     fun findTarget(blknum, [CFG.BLOCK{id=id1, insns=insns1, ...},
114 :     CFG.BLOCK{id=id2, insns=insns2, ...}]) = let
115 :     fun extract(blknum, insns) = let
116 :     (* skip over empty copies *)
117 :     fun find [] = NONE
118 :     | find(instrs as instr::rest) =
119 :     if isEmptyCopy instr then find rest else find' rest
120 :    
121 :     (* Okay, we are now guaranteed that the remaining
122 :     * instructions will not be used in the delay slot of
123 :     * the current block. Find the first instruction.
124 :     *)
125 :     and find' [first] = SOME(first, A.sub(labelMap,blknum))
126 :     | find' [] = NONE
127 :     | find' (_::rest) = find' rest
128 :     in
129 :     case insns
130 :     of jmp::rest =>
131 :     if Props.instrKind jmp = Props.IK_JUMP then find rest
132 :     else find insns
133 :     | [] => NONE (* no first instruction *)
134 : monnier 247 end
135 : george 909 in
136 :     if isFallthrough(blknum, id1) then extract(id2, !insns2)
137 :     else if isFallthrough(blknum, id2) then extract(id1, !insns1)
138 :     else NONE
139 :     end
140 :     | findTarget _ = NONE
141 : monnier 247
142 :    
143 :    
144 : george 909 fun compress [] = []
145 : george 984 | compress (CFG.BLOCK{id, align, labels, insns, ...}::rest) = let
146 : monnier 411
147 : george 909 val succ = map (#node_info graph) (#succ graph id)
148 : monnier 247
149 : george 909 val backward =
150 :     List.exists
151 :     (fn CFG.BLOCK{id=id1, ...} => isBackwards(id, id1))
152 :     succ
153 : monnier 247
154 : george 909 (* build the code list *)
155 :     fun scan([],nonSdiInstrs,nonSdiSize,code) =
156 :     group(nonSdiSize,nonSdiInstrs,code)
157 :     | scan(instr::instrs,nonSdiInstrs,nonSdiSize,code) =
158 :     let val {n,nOn,nOff,nop} = D.delaySlot{instr=instr,backward=backward}
159 :     in case (nOff,instrs) of
160 :     (D.D_ALWAYS,delaySlot::rest) =>
161 :     if D.delaySlotCandidate{jmp=instr,
162 :     delaySlot=delaySlot} andalso
163 :     not(D.conflict{src=delaySlot,dst=instr})
164 :     then scan(rest,[],0,
165 :     mkCandidate1(instr,delaySlot)::
166 :     group(nonSdiSize,nonSdiInstrs,code))
167 :     else scanSdi(instr,instrs,nonSdiInstrs,nonSdiSize,code)
168 :     | _ => scanSdi(instr,instrs,nonSdiInstrs,nonSdiSize,code)
169 :     end
170 :     and scanSdi(instr,instrs,nonSdiInstrs,nonSdiSize,code) =
171 :     let val s = J.minSize instr
172 :     in if J.isSdi instr then
173 :     scan(instrs,[],0,SDI{size=ref s,insn=instr}::
174 :     group(nonSdiSize,nonSdiInstrs,code))
175 :     else scan(instrs,instr::nonSdiInstrs,nonSdiSize+s,code)
176 :     end
177 :     and group(0,[],code) = code
178 :     | group(size,insns,code) = FIXED{size=size,insns=insns}::code
179 : monnier 247
180 : george 909 and buildList instrs = scan'(instrs,[],0,[])
181 : monnier 247
182 : george 909 and scan'([],nonSdiInstrs,nonSdiSize,code) =
183 :     group(nonSdiSize,nonSdiInstrs,code)
184 :     | scan'(instr::instrs,nonSdiInstrs,nonSdiSize,code) =
185 :     let val s = J.minSize instr
186 :     in if J.isSdi instr then
187 :     scan'(instrs,[],0,SDI{size=ref s,insn=instr}::
188 :     group(nonSdiSize,nonSdiInstrs,code))
189 :     else scan'(instrs,instr::nonSdiInstrs,nonSdiSize+s,code)
190 :     end
191 : monnier 247
192 : george 909 (*
193 :     * Create a branch delay slot candidate sequence.
194 :     * jmp is the normal jump instruction; jmp' is the
195 :     * jump instruction when the delay slot is active.
196 :     *)
197 :     and mkCandidate1(jmp,delaySlot) =
198 :     let val fillSlot = ref true
199 :     val jmp' = D.enableDelaySlot{n=false,nop=false,instr=jmp}
200 :     in CANDIDATE{newInsns=
201 :     [BRANCH{branchSize=J.minSize jmp',
202 :     insn=buildList [jmp'],
203 :     fillSlot=fillSlot},
204 :     DELAYSLOT{insn=buildList [delaySlot],
205 :     fillSlot=fillSlot}],
206 :     oldInsns=buildList [jmp,delaySlot],
207 :     fillSlot=fillSlot}
208 :     end
209 : monnier 411
210 : george 909 (*
211 :     * Create a branch delay slot candidate sequence.
212 :     * jmp is the normal jump instruction; jmp' is the
213 :     * jump instruction when the delay slot is active.
214 :     *)
215 :     and mkCandidate2(jmp,delaySlot,label) =
216 :     let val fillSlot = ref true
217 :     val jmp' = D.setTarget(
218 :     D.enableDelaySlot{n=true,nop=false,instr=jmp},
219 :     label)
220 :     in CANDIDATE{newInsns=
221 :     [BRANCH{branchSize=J.minSize jmp',
222 :     insn=buildList [jmp'],
223 :     fillSlot=fillSlot},
224 :     DELAYSLOT{insn=buildList [delaySlot],
225 :     fillSlot=fillSlot}],
226 :     oldInsns=buildList [jmp],
227 :     fillSlot=fillSlot}
228 :     end
229 : monnier 411
230 : george 909 (*
231 :     * Try different strategies for delay slot filling
232 :     *)
233 :     and fitDelaySlot(jmp,body) =
234 :     (case body of (* remove empty copies *)
235 :     [] => fitDelaySlot'(jmp,body)
236 :     | prev::rest =>
237 :     if isEmptyCopy prev
238 :     then fitDelaySlot(jmp,rest)
239 :     else fitDelaySlot'(jmp,body)
240 :     )
241 : monnier 411
242 : george 909 and fitDelaySlot'(jmp,body) =
243 :     let val {n,nOn,nOff,nop} = D.delaySlot{instr=jmp,backward=backward}
244 :     (*
245 :     * Use the previous instruction to fill the delay slot
246 :     *)
247 :     fun strategy1() =
248 :     case (nOff,body) of
249 :     (D.D_ALWAYS,delaySlot::body) =>
250 :     if not(D.delaySlotCandidate{jmp=jmp,
251 :     delaySlot=delaySlot}) orelse
252 :     D.conflict{src=delaySlot,dst=jmp}
253 :     then strategy2()
254 :     else scan(body,[],0,
255 :     [mkCandidate1(eliminateNop jmp,delaySlot)])
256 :     | _ => strategy2()
257 :     (*
258 :     * Use the first instruction in the target block to fill
259 :     * the delay slot.
260 :     * BUG FIX: note this is unsafe if this first instruction
261 :     * is also used to fill the delay slot in the target block!
262 :     *)
263 :     and strategy2() =
264 :     case (nOn,findTarget(id,succ)) of
265 :     (D.D_TAKEN,SOME(delaySlot,label)) =>
266 :     if not(D.delaySlotCandidate{jmp=jmp,
267 :     delaySlot=delaySlot}) orelse
268 :     D.conflict{src=delaySlot,dst=jmp}
269 :     then strategy3()
270 :     else scan(body,[],0,
271 :     [mkCandidate2(eliminateNop jmp,delaySlot,label)])
272 :     | _ => strategy3()
273 : monnier 247
274 : george 909 (*
275 :     * If nop is on and if the delay slot is only active on
276 :     * the fallsthru branch, then turn nullify on and eliminate
277 :     * the delay slot
278 :     *)
279 :     and strategy3() = scan(eliminateNop(jmp)::body,[],0,[])
280 : monnier 411
281 : george 909 and eliminateNop(jmp) =
282 :     case (nop,nOn) of
283 :     (true,(D.D_FALLTHRU | D.D_NONE)) =>
284 :     D.enableDelaySlot{n=true,nop=false,instr=jmp}
285 :     | _ => jmp
286 : monnier 247
287 : george 909 in strategy1()
288 :     end
289 :    
290 : george 1009 and process(instrs, others) = let
291 :     fun alignIt(chunks) =
292 :     (case !align of NONE => chunks | SOME p => PSEUDO(p)::chunks)
293 :     val code =
294 :     (case instrs
295 :     of [] => []
296 :     | jmp::body =>
297 :     (case Props.instrKind jmp
298 :     of Props.IK_JUMP => fitDelaySlot(jmp, body)
299 :     | _ => scan(instrs, [], 0, [])
300 :     (*esac*))
301 :     (*esac*))
302 :     in
303 :     alignIt
304 :     (map LABEL (!labels) @
305 :     CODE (A.sub(labelMap, id), code) :: others)
306 :    
307 :     end
308 : monnier 247 in
309 : george 909 process(!insns,compress rest)
310 :     end (* compress *)
311 : monnier 247
312 : george 984 val CFG.INFO{data, ...} = #graph_info graph
313 : george 909 in
314 :     blockOrder(blocks);
315 :     enterLabels(blocks);
316 : george 984 clusterList := CLUSTER{comp=compress blocks} :: !clusterList;
317 :     dataList := !data @ !dataList
318 : george 909 end (* bbsched *)
319 :    
320 :    
321 :    
322 :    
323 : blume 986 fun finish () = let
324 : george 1000 fun labels(PSEUDO pOp::rest, loc) =
325 :     (P.adjustLabels(pOp, loc); labels(rest, loc+P.sizeOf(pOp, loc)))
326 :     | labels(LABEL lab::rest, loc) =
327 :     (Label.setAddr(lab, loc); labels(rest, loc))
328 :     | labels(CODE(lab,code)::rest, loc) = let
329 : monnier 247 fun size(FIXED{size, ...}) = size
330 :     | size(SDI{size, ...}) = !size
331 :     | size(BRANCH{insn,...}) = sizeList(insn,0)
332 :     | size(DELAYSLOT{insn,...}) = sizeList(insn,0)
333 :     | size(CANDIDATE{oldInsns,newInsns,fillSlot,...}) =
334 :     sizeList(if !fillSlot then newInsns else oldInsns,0)
335 :     and sizeList([],n) = n
336 :     | sizeList(code::rest,n) = sizeList(rest,size code + n)
337 : george 1000 in Label.setAddr(lab,loc+4);
338 :     labels(rest, sizeList(code,loc))
339 : monnier 247 end
340 : george 1000 | labels([], loc) = loc
341 :    
342 :     fun initLabels clusters =
343 :     List.foldl
344 :     (fn (CLUSTER{comp}, loc) => labels(comp, loc)) 0 clusters
345 : monnier 247
346 : george 1000
347 : monnier 247 val delaySlotSize = D.delaySlotSize
348 : george 1000 (*
349 :     Suppose we have:
350 : monnier 247
351 : george 1000 u
352 :     jmp L1
353 :     nop
354 :     ...
355 :     L1: i
356 :     j
357 :     k
358 :    
359 :     I insert a fake label L2:
360 :    
361 :     L1: i
362 :     L2: j
363 :     k
364 :    
365 :     L2 is the label in CODE(label,code).
366 :    
367 :     If instruction u cannot be put into the delay slot of jmp L1 I try
368 :     to put i into the delay slot of L1. This creates code like this:
369 :    
370 :     u
371 :     jmp L2
372 :     i
373 :     ...
374 :     L1: i
375 :     L2: j
376 :     k
377 :     -- Allen
378 :     *)
379 :     fun adjust(CLUSTER{comp, ...}, pos, changed) = let
380 :     fun scan(PSEUDO pOp::rest, pos, changed) = let
381 :     val chgd = P.adjustLabels(pOp, pos)
382 :     in scan(rest, pos+P.sizeOf(pOp,pos), changed orelse chgd)
383 :     end
384 :     | scan(LABEL lab::rest, pos, changed) =
385 :     if Label.addrOf(lab) = pos then scan(rest, pos, changed)
386 :     else (Label.setAddr(lab, pos); scan(rest, pos, true))
387 :     | scan(CODE(lab,code)::rest, pos, changed) = let
388 :     val (newPos,changed) = doCode(code,pos,changed)
389 :     in
390 :     if Label.addrOf(lab) = pos+4 then
391 :     scan(rest, newPos, changed)
392 :     else (Label.setAddr(lab, pos+4); scan(rest, newPos, true))
393 :     end
394 :     | scan([], pos, changed) = (pos, changed)
395 :    
396 :     and doCode([],pos,changed) = (pos,changed)
397 :     | doCode(code::rest,pos,changed) =
398 :     case code of
399 :     FIXED{size,...} => doCode(rest,pos+size,changed)
400 :     | SDI{size, insn} =>
401 :     let val newSize = J.sdiSize(insn, Label.addrOf, pos)
402 :     in if newSize <= !size then
403 :     doCode(rest,!size + pos,changed)
404 :     else (size:=newSize; doCode(rest, newSize+pos, true))
405 :     end
406 :     | DELAYSLOT{insn,fillSlot,...} =>
407 :     let val (newPos,changed) = doCode(insn,pos,changed)
408 :     in doCode(rest, newPos,
409 :     if newPos - pos <> delaySlotSize then
410 :     (fillSlot := false; true) else changed)
411 :     end
412 :     | BRANCH{insn,branchSize,fillSlot,...} =>
413 :     let val (newPos,changed) = doCode(insn,pos,changed)
414 :     in doCode(rest, newPos,
415 :     if newPos - pos <> branchSize then
416 :     (fillSlot := false; true) else changed)
417 :     end
418 :     | CANDIDATE{oldInsns,newInsns,fillSlot,...} =>
419 :     doCode((if !fillSlot then newInsns else oldInsns) @ rest,
420 :     pos,changed)
421 : monnier 247 in scan(comp, pos, changed)
422 :     end
423 :    
424 : george 1000 fun adjustLabels clusters = let
425 :     fun f (cl, (pos, chgd)) = adjust(cl, pos, chgd)
426 :     in List.foldl f (0, false) clusters
427 : monnier 247 end
428 :    
429 : george 1000 fun fixpoint zl i = let
430 :     val (size, changed) = adjustLabels zl
431 :     in if changed then fixpoint zl (i+1) else size
432 :     end
433 :    
434 : blume 986 val E.S.STREAM{defineLabel,pseudoOp,emit,beginCluster,...} =
435 :     E.makeStream []
436 : george 1009
437 :     val debug = MLRiscControl.getFlag "dump-cfg-after-spandep"
438 :    
439 :     fun emitCluster (CLUSTER{comp},loc) = let
440 : george 1000 val emitInstrs = app emit
441 :     fun nops 0 = ()
442 :     | nops n = if n < 0 then error "nops" else (emit(Props.nop()); nops(n-4))
443 : monnier 247
444 : george 1000 fun process(PSEUDO pOp,loc) = (pseudoOp pOp; loc+P.sizeOf(pOp,loc))
445 :     | process(LABEL lab,loc) = let
446 :     val addr = Label.addrOf lab
447 :     in
448 :     if addr = loc then (defineLabel lab; loc)
449 :     else if addr > loc then (nops(addr-loc); defineLabel lab; addr)
450 :     else error "label"
451 :     end
452 :     | process(CODE(lab,code),loc) = let
453 :     fun e(FIXED{insns, size, ...},loc) = (emitInstrs insns; loc+size)
454 :     | e(SDI{size, insn},loc) =
455 :     (emitInstrs(J.expand(insn, !size, loc)); !size + loc)
456 :     | e(BRANCH{insn,...},loc) = foldl e loc insn
457 :     | e(DELAYSLOT{insn,...},loc) = foldl e loc insn
458 :     | e(CANDIDATE{newInsns,oldInsns,fillSlot,...},loc) =
459 :     foldl e loc (if !fillSlot then newInsns else oldInsns)
460 :     in
461 : george 1009 foldl e loc code
462 : george 1000 end
463 :     in foldl process loc comp
464 :     end
465 :    
466 :     (* The dataList is in reverse order and the clusters are in reverse *)
467 :     fun dataCluster([], acc) = CLUSTER{comp=acc}
468 :     | dataCluster(d::dl, acc) = dataCluster(dl, PSEUDO d::acc)
469 :     val compressed =
470 :     rev (dataCluster(!dataList, []) :: !clusterList) before cleanUp()
471 : george 909 in
472 : george 1000 initLabels(compressed);
473 :     beginCluster(fixpoint compressed 0);
474 : george 984 foldl emitCluster 0 compressed;
475 : monnier 411 ()
476 : monnier 247 end (*finish*)
477 :     end (* spanDep.sml *)
478 :    

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