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/branches/SMLNJ/src/MLRISC/backpatch/spanDep.sml
ViewVC logotype

Annotation of /sml/branches/SMLNJ/src/MLRISC/backpatch/spanDep.sml

Parent Directory Parent Directory | Revision Log Revision Log


Revision 247 - (view) (download)

1 : monnier 247 (*
2 :     * This version of the span dependency resolution also fill delay slots
3 :     * using a few simple strategies.
4 :     *
5 :     * Allen
6 :     *)
7 :    
8 :     functor SpanDependencyResolution
9 :     (structure Flowgraph : FLOWGRAPH
10 :     structure Jumps : SDI_JUMPS
11 :     structure Emitter : EMITTER_NEW
12 :     structure DelaySlot : DELAY_SLOT_PROPERTIES
13 :     structure Props : INSN_PROPERTIES
14 :     sharing Emitter.P = Flowgraph.P
15 :     sharing Flowgraph.I = Jumps.I = Emitter.I = DelaySlot.I = Props.I)
16 :     : BBSCHED =
17 :     struct
18 :    
19 :     structure F = Flowgraph
20 :     structure I = F.I
21 :     structure C = I.C
22 :     structure E = Emitter
23 :     structure J = Jumps
24 :     structure P = Flowgraph.P
25 :     structure D = DelaySlot
26 :     structure A = Array
27 :    
28 :     fun error msg = MLRiscErrorMsg.impossible ("SpanDependencyResolution."^msg)
29 :    
30 :     datatype code =
31 :     SDI of {size : int ref, (* variable sized *)
32 :     insn : I.instruction}
33 :     | FIXED of {size: int, (* size of fixed instructions *)
34 :     insns: I.instruction list}
35 :     | BRANCH of {insn : code list, (* instruction with delay slot*)
36 :     branchSize : int,
37 :     fillSlot : bool ref}
38 :     | DELAYSLOT of {insn : code list, (* instruction in delay slot *)
39 :     fillSlot : bool ref}
40 :     | CANDIDATE of (* two alternatives *)
41 :     { oldInsns : code list, (* without delay slot filling *)
42 :     newInsns : code list, (* when delay slot is filled *)
43 :     fillSlot : bool ref (* should we fill the delay slot? *)
44 :     }
45 :    
46 :     datatype compressed =
47 :     PSEUDO of P.pseudo_op
48 :     | LABEL of Label.label
49 :     | CODE of Label.label * code list
50 :     | CLUSTER of {comp : compressed list, regmap : int Intmap.intmap}
51 :    
52 :     val clusterList : compressed list ref = ref []
53 :     fun cleanUp() = clusterList := []
54 :    
55 :     fun bbsched(cluster as F.CLUSTER{blocks, regmap, blkCounter, ...}) =
56 :     let fun lookup r = Intmap.map regmap r handle _ => r
57 :    
58 :     fun blknumOf(F.BBLOCK{blknum,...}) = blknum
59 :     | blknumOf(F.EXIT{blknum,...}) = blknum
60 :     | blknumOf _ = error "blknumOf"
61 :    
62 :     fun noPseudo [] = true
63 :     | noPseudo (F.BBLOCK _::_) = true
64 :     | noPseudo (F.LABEL _::rest) = noPseudo rest
65 :     | noPseudo (F.ORDERED l::rest) = noPseudo(l@rest)
66 :     | noPseudo (F.PSEUDO _::_) = false
67 :    
68 :     (* Maps blknum -> label at the position of the second instruction *)
69 :     val dummy = Label.newLabel ""
70 :     val labelMap = A.array(!blkCounter,dummy)
71 :    
72 :     (* enter labels into the labelMap *)
73 :     fun enterLabels([]) = ()
74 :     | enterLabels(F.PSEUDO _::rest) = enterLabels rest
75 :     | enterLabels(F.LABEL _::rest) = enterLabels rest
76 :     | enterLabels(F.ORDERED blks::rest) = enterLabels(blks@rest)
77 :     | enterLabels(F.BBLOCK{blknum,...}::rest) =
78 :     (A.update(labelMap,blknum,Label.newLabel ""); enterLabels rest)
79 :     | enterLabels _ = error "enterLabels"
80 :    
81 :     (*
82 :     * Find the branch target of block blknum, return the first instruction
83 :     * in the target block and its associated label.
84 :     *)
85 :     fun findTarget(blknum,[F.BBLOCK{blknum=x,insns=insns1,...},
86 :     F.BBLOCK{blknum=y,insns=insns2,...}]) =
87 :     let fun extract(blknum,[]) = NONE
88 :     | extract(blknum,[_]) = NONE
89 :     | extract(blknum,[_,_]) = NONE
90 :     | extract(blknum,insns) =
91 :     SOME(List.last insns,A.sub(labelMap,blknum))
92 :     in if x = blknum + 1 then extract(y,!insns2)
93 :     else if y = blknum + 1 then extract(x,!insns1)
94 :     else NONE
95 :     end
96 :     | findTarget _ = NONE
97 :    
98 :    
99 :     (* Convert a cluster into compressed form *)
100 :     fun compress(F.PSEUDO pOp::rest) = PSEUDO pOp::compress rest
101 :     | compress(F.LABEL lab::rest) = LABEL lab:: compress rest
102 :     | compress(F.ORDERED blks::rest) = compress(blks@rest)
103 :     | compress(F.BBLOCK{blknum,insns,succ,...}::rest) =
104 :     let
105 :     val backward = List.exists (fn b => blknumOf b <= blknum) (!succ)
106 :    
107 :     (* build the code list *)
108 :     fun scan([],nonSdiInstrs,nonSdiSize,code) =
109 :     group(nonSdiSize,nonSdiInstrs,code)
110 :     | scan(instr::instrs,nonSdiInstrs,nonSdiSize,code) =
111 :     let val {n,nOn,nOff,nop} = D.delaySlot{instr=instr,backward=backward}
112 :     in case (nOff,instrs) of
113 :     (D.D_ALWAYS,delaySlot::rest) =>
114 :     if D.delaySlotCandidate{jmp=instr,
115 :     delaySlot=delaySlot} andalso
116 :     not(D.conflict{regmap=lookup,src=delaySlot,dst=instr})
117 :     then scan(rest,[],0,
118 :     mkCandidate1(instr,delaySlot)::
119 :     group(nonSdiSize,nonSdiInstrs,code))
120 :     else scanSdi(instr,instrs,nonSdiInstrs,nonSdiSize,code)
121 :     | _ => scanSdi(instr,instrs,nonSdiInstrs,nonSdiSize,code)
122 :     end
123 :     and scanSdi(instr,instrs,nonSdiInstrs,nonSdiSize,code) =
124 :     let val s = J.minSize instr
125 :     in if J.isSdi instr then
126 :     scan(instrs,[],0,SDI{size=ref s,insn=instr}::
127 :     group(nonSdiSize,nonSdiInstrs,code))
128 :     else scan(instrs,instr::nonSdiInstrs,nonSdiSize+s,code)
129 :     end
130 :     and group(0,[],code) = code
131 :     | group(size,insns,code) = FIXED{size=size,insns=insns}::code
132 :    
133 :     and buildList instrs = scan'(instrs,[],0,[])
134 :    
135 :     and scan'([],nonSdiInstrs,nonSdiSize,code) =
136 :     group(nonSdiSize,nonSdiInstrs,code)
137 :     | scan'(instr::instrs,nonSdiInstrs,nonSdiSize,code) =
138 :     let val s = J.minSize instr
139 :     in if J.isSdi instr then
140 :     scan'(instrs,[],0,SDI{size=ref s,insn=instr}::
141 :     group(nonSdiSize,nonSdiInstrs,code))
142 :     else scan'(instrs,instr::nonSdiInstrs,nonSdiSize+s,code)
143 :     end
144 :    
145 :     (*
146 :     * Create a branch delay slot candidate sequence.
147 :     * jmp is the normal jump instruction; jmp' is the
148 :     * jump instruction when the delay slot is active.
149 :     *)
150 :     and mkCandidate1(jmp,delaySlot) =
151 :     let val fillSlot = ref true
152 :     val jmp' = D.enableDelaySlot{n=false,nop=false,instr=jmp}
153 :     in CANDIDATE{newInsns=
154 :     [BRANCH{branchSize=J.minSize jmp',
155 :     insn=buildList [jmp'],
156 :     fillSlot=fillSlot},
157 :     DELAYSLOT{insn=buildList [delaySlot],
158 :     fillSlot=fillSlot}],
159 :     oldInsns=buildList [jmp,delaySlot],
160 :     fillSlot=fillSlot}
161 :     end
162 :    
163 :     (*
164 :     * Create a branch delay slot candidate sequence.
165 :     * jmp is the normal jump instruction; jmp' is the
166 :     * jump instruction when the delay slot is active.
167 :     *)
168 :     and mkCandidate2(jmp,delaySlot,label) =
169 :     let val fillSlot = ref true
170 :     val jmp' = D.setTarget(
171 :     D.enableDelaySlot{n=true,nop=false,instr=jmp},
172 :     label)
173 :     in CANDIDATE{newInsns=
174 :     [BRANCH{branchSize=J.minSize jmp',
175 :     insn=buildList [jmp'],
176 :     fillSlot=fillSlot},
177 :     DELAYSLOT{insn=buildList [delaySlot],
178 :     fillSlot=fillSlot}],
179 :     oldInsns=buildList [jmp],
180 :     fillSlot=fillSlot}
181 :     end
182 :    
183 :     (*
184 :     * Try different strategies for delay slot filling
185 :     *)
186 :     and fitDelaySlot(jmp,body,instrs) =
187 :     let val {n,nOn,nOff,nop} = D.delaySlot{instr=jmp,backward=backward}
188 :     (*
189 :     * Use the previous instruction to fill the delay slot
190 :     *)
191 :     fun strategy1() =
192 :     case (nOff,body) of
193 :     (D.D_ALWAYS,delaySlot::body) =>
194 :     if not(D.delaySlotCandidate{jmp=jmp,
195 :     delaySlot=delaySlot}) orelse
196 :     D.conflict{regmap=lookup,src=delaySlot,dst=jmp}
197 :     then strategy2()
198 :     else scan(body,[],0,[mkCandidate1(jmp,delaySlot)])
199 :     | _ => strategy2()
200 :     (*
201 :     * Use the first instruction in the target block to fill
202 :     * the delay slot
203 :     *)
204 :     and strategy2() =
205 :     case (nOn,findTarget(blknum,!succ)) of
206 :     (D.D_TAKEN,SOME(delaySlot,label)) =>
207 :     if not(D.delaySlotCandidate{jmp=jmp,
208 :     delaySlot=delaySlot}) orelse
209 :     D.conflict{regmap=lookup,src=delaySlot,dst=jmp}
210 :     then strategy3()
211 :     else scan(body,[],0,[mkCandidate2(jmp,delaySlot,label)])
212 :     | _ => strategy3()
213 :     (*
214 :     * No delay slot filling
215 :     *)
216 :     and strategy3() = scan(instrs,[],0,[])
217 :     in strategy1()
218 :     end
219 :    
220 :     (*
221 :     * Try to remove the branch if it is unnecessary
222 :     *)
223 :     and processBranch(jmp,body,instrs) =
224 :     case (!succ, noPseudo rest) of
225 :     ([F.BBLOCK{blknum=id,...}],true) =>
226 :     if id = blknum + 1 then scan(body,[],0,[])
227 :     else fitDelaySlot(jmp,body,instrs)
228 :     | _ => fitDelaySlot(jmp,body,instrs)
229 :    
230 :     and process([],others) = others
231 :     | process(instrs as jmp::body,others) =
232 :     CODE(A.sub(labelMap,blknum),
233 :     case Props.instrKind jmp of
234 :     Props.IK_JUMP => processBranch(jmp,body,instrs)
235 :     | _ => scan(instrs,[],0,[])
236 :     )::others
237 :     in
238 :     process(!insns,compress rest)
239 :     end
240 :     | compress [] = []
241 :     in enterLabels blocks;
242 :     clusterList:=CLUSTER{comp = compress blocks, regmap=regmap}::
243 :     (!clusterList)
244 :     end
245 :    
246 :     fun finish() = let
247 :     fun labels(PSEUDO pOp::rest, pos) =
248 :     (P.adjustLabels(pOp, pos); labels(rest, pos+P.sizeOf(pOp,pos)))
249 :     | labels(LABEL lab::rest, pos) =
250 :     (Label.setAddr(lab,pos); labels(rest, pos))
251 :     | labels(CODE(lab,code)::rest, pos) = let
252 :     fun size(FIXED{size, ...}) = size
253 :     | size(SDI{size, ...}) = !size
254 :     | size(BRANCH{insn,...}) = sizeList(insn,0)
255 :     | size(DELAYSLOT{insn,...}) = sizeList(insn,0)
256 :     | size(CANDIDATE{oldInsns,newInsns,fillSlot,...}) =
257 :     sizeList(if !fillSlot then newInsns else oldInsns,0)
258 :     and sizeList([],n) = n
259 :     | sizeList(code::rest,n) = sizeList(rest,size code + n)
260 :     in Label.setAddr(lab,pos+4);
261 :     labels(rest, sizeList(code,pos))
262 :     end
263 :     | labels(CLUSTER{comp, ...}::rest, pos) = labels(rest, labels(comp,pos))
264 :     | labels([], pos) = pos
265 :    
266 :     val delaySlotSize = D.delaySlotSize
267 :    
268 :     fun adjust(CLUSTER{comp, regmap}::cluster, pos, changed) =
269 :     let fun scan(PSEUDO pOp::rest, pos, changed) =
270 :     scan(rest, pos+P.sizeOf(pOp,pos), changed)
271 :     | scan(LABEL _::rest, pos, changed) = scan(rest, pos, changed)
272 :     | scan(CODE(_,code)::rest, pos, changed) =
273 :     let val (pos,changed) = doCode(code,pos,changed)
274 :     in scan(rest,pos,changed) end
275 :     | scan([], pos, changed) = adjust(cluster, pos, changed)
276 :     and doCode([],pos,changed) = (pos,changed)
277 :     | doCode(code::rest,pos,changed) =
278 :     case code of
279 :     FIXED{size,...} => doCode(rest,pos+size,changed)
280 :     | SDI{size, insn} =>
281 :     let val newSize = J.sdiSize(insn, regmap, Label.addrOf, pos)
282 :     in if newSize <= !size then
283 :     doCode(rest,!size + pos,changed)
284 :     else (size:=newSize; doCode(rest, newSize+pos, true))
285 :     end
286 :     | DELAYSLOT{insn,fillSlot,...} =>
287 :     let val (newPos,changed) = doCode(insn,pos,changed)
288 :     in doCode(rest, newPos,
289 :     if newPos - pos <> delaySlotSize then
290 :     (fillSlot := false; true) else changed)
291 :     end
292 :     | BRANCH{insn,branchSize,fillSlot,...} =>
293 :     let val (newPos,changed) = doCode(insn,pos,changed)
294 :     in doCode(rest, newPos,
295 :     if newPos - pos <> branchSize then
296 :     (fillSlot := false; true) else changed)
297 :     end
298 :     | CANDIDATE{oldInsns,newInsns,fillSlot,...} =>
299 :     doCode((if !fillSlot then newInsns else oldInsns) @ rest,
300 :     pos,changed)
301 :     in scan(comp, pos, changed)
302 :     end
303 :     | adjust(_::_, _, _) = error "adjust"
304 :     | adjust([], _, changed) = changed
305 :    
306 :     fun fixpoint zl = let
307 :     val size = labels(zl, 0)
308 :     in if adjust(zl, 0, false) then fixpoint zl else size
309 :     end
310 :    
311 :     fun emitCluster(CLUSTER{comp, regmap}, loc) = let
312 :     fun emit(PSEUDO pOp, loc) = (E.pseudoOp pOp; loc+P.sizeOf(pOp, loc))
313 :     | emit(LABEL lab, loc) = (E.defineLabel lab; loc)
314 :     | emit(CODE(_,code), loc) = let
315 :     val emitInstrs = app (fn i => E.emitInstr(i, regmap))
316 :     fun e(FIXED{insns, size, ...}, loc) = (emitInstrs insns; loc+size)
317 :     | e(SDI{size, insn}, loc) =
318 :     (emitInstrs(J.expand(insn, !size, loc)); !size+loc)
319 :     | e(BRANCH{insn,...}, loc) = List.foldl e loc insn
320 :     | e(DELAYSLOT{insn,...}, loc) = List.foldl e loc insn
321 :     | e(CANDIDATE{newInsns,oldInsns,fillSlot,...}, loc) =
322 :     List.foldl e loc (if !fillSlot then newInsns else oldInsns)
323 :     in List.foldl e loc code
324 :     end
325 :     in List.foldl emit loc comp
326 :     end
327 :    
328 :     val compressed = (rev (!clusterList)) before cleanUp()
329 :     in
330 :     E.init(fixpoint compressed);
331 :     List.foldl emitCluster 0 compressed handle e => raise e;
332 :     ()
333 :     end (*finish*)
334 :    
335 :     end (* spanDep.sml *)
336 :    
337 :     (*
338 :     * $Log: spanDep.sml,v $
339 :     * Revision 1.1.1.1 1998/11/16 21:47:14 george
340 :     * Version 110.10
341 :     *
342 :     * Revision 1.3 1998/10/06 14:07:49 george
343 :     * Flowgraph has been removed from modules that do not need it.
344 :     * Changes to compiler/CodeGen/*/*{MLTree,CG}.sml necessary.
345 :     * [leunga]
346 :     *
347 :     * Revision 1.2 1998/08/12 13:36:09 leunga
348 :     * Fixed the 2.0 + 2.0 == nan bug by treating FCMP as instrs with delay slots
349 :     *
350 :     * Revision 1.1 1998/08/05 19:47:21 george
351 :     * Changes to support the SPARC back end
352 :     *
353 :     *)

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