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

Parent Directory | Revision Log

---

Revision 171 - (view) (download)

1 :	monnier	171	(*
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}) = let
312 :			fun emit(PSEUDO pOp) = E.pseudoOp pOp
313 :			| emit(LABEL lab) = E.defineLabel lab
314 :			| emit(CODE(_,code)) = let
315 :			fun emitInstrs insns = app (fn i => E.emitInstr(i, regmap)) insns
316 :			fun e(FIXED{insns, ...}) = emitInstrs insns
317 :			| e(SDI{size, insn}) = emitInstrs(J.expand(insn, !size))
318 :			| e(BRANCH{insn,...}) = app e insn
319 :			| e(DELAYSLOT{insn,...}) = app e insn
320 :			| e(CANDIDATE{newInsns,oldInsns,fillSlot,...}) =
321 :			app e (if !fillSlot then newInsns else oldInsns)
322 :			in app e code
323 :			end
324 :			in app emit comp
325 :			end
326 :
327 :			val compressed = (rev (!clusterList)) before cleanUp()
328 :			in
329 :			E.init(fixpoint compressed);
330 :			app emitCluster compressed
331 :			end (*finish*)
332 :
333 :			end (* spanDep.sml *)
334 :
335 :			(*
336 :			* $Log: spanDep.sml,v $
337 :			* Revision 1.2 1998/08/12 13:36:09 leunga
338 :			* Fixed the 2.0 + 2.0 == nan bug by treating FCMP as instrs with delay slots
339 :			*
340 :			* Revision 1.1 1998/08/05 19:47:21 george
341 :			* Changes to support the SPARC back end
342 :			*
343 :			*)

---

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