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/mlrisc/bbsched.sml
ViewVC logotype

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

Parent Directory Parent Directory | Revision Log Revision Log


Revision 16 - (view) (download)

1 : monnier 16 (* bbsched.sml
2 :     *
3 :     * COPYRIGHT (c) 1996 Bell Laboratories.
4 :     *
5 :     *)
6 :    
7 :     (** bbsched.sml - invoke scheduling after span dependent resolution **)
8 :    
9 :     (* Note: This module can be made to go a faster by changing vsub
10 :     * to System.Unsafe.subscriptv.
11 :     *)
12 :    
13 :     signature BBSCHED = sig
14 :     structure F : FLOWGRAPH
15 :     structure P : INSN_PROPERTIES
16 :    
17 :     val bbsched : F.cluster -> unit
18 :     val finish : unit -> unit
19 :     val cleanUp : unit -> unit
20 :     end
21 :    
22 :    
23 :     functor BBSched
24 :     (structure Flowgraph : FLOWGRAPH
25 :     structure InsnProps : INSN_PROPERTIES
26 :     structure Emitter : EMITTER_NEW
27 :     structure Scheduler : SCHEDULER
28 :     val icount : int -> InsnProps.I.instruction
29 :    
30 :     sharing Flowgraph.I = InsnProps.I = Emitter.I = Scheduler.I) : BBSCHED =
31 :     struct
32 :    
33 :     structure F = Flowgraph
34 :     structure I = F.I
35 :     structure P = InsnProps
36 :     structure C = InsnProps.C
37 :     structure E = Emitter
38 :    
39 :     fun error msg = MLRiscErrorMsg.impossible ("BBSched."^msg)
40 :    
41 :     val vsub = Vector.sub
42 :    
43 :     (* collect clusters as they arrive *)
44 :     val clusterList : F.cluster list ref = ref []
45 :    
46 :     fun align n = Word.toIntX (Word.andb (Word.fromInt(n+7), Word.notb 0w7))
47 :    
48 :     fun cleanUp () = clusterList := []
49 :    
50 :     (* Note: blocks within cluster are in correct order, whereas
51 :     * the clusters themselves are in reverse order
52 :     *)
53 :     fun bbsched(F.CLUSTER{blocks=blks, regmaps, ...}) = let
54 :     fun f(F.BBLOCK{insns,...}) = F.CODE(ref(Vector.fromList(!insns)))
55 :     | f x = x
56 :     val compressed = map f blks
57 :     in
58 :     clusterList:=
59 :     F.CLUSTER{blocks=compressed,
60 :     regmaps=regmaps,
61 :     rematerial=[]} :: (!clusterList)
62 :     end
63 :    
64 :     (* ---------------------- *)
65 :    
66 :     (* more compact representation for label resolution *)
67 :     (* components of sdi are: 1. position of sdi in instruction vector,
68 :     * 2. size of sdi under optimistic assumptions, and 3. size under
69 :     * pessimistic assumptions.
70 :     * Note: the last instruction in the block is at offset 0.
71 :     * Invariant: the sdi list is maintained in decreasing order over
72 :     * the first component. This is crucial to fixLabels.fix.sumSdiSize.
73 :     *)
74 :     datatype compressedBlk
75 :     = DATA of int
76 :     | ALIGN
77 :     | LABEL of Label.label
78 :     | CODE of
79 :     {code: I.instruction Vector.vector ref,
80 :     sdi: (int*int*int) list ref,
81 :     minSize: int,
82 :     maxSize: int,
83 :     regmaps : int Array.array ref list}
84 :    
85 :     datatype labelExtremety = LO | HI
86 :    
87 :     (* mkCompressedList - simplify the codeList to include just data,
88 :     * labels and code.
89 :     *)
90 :     fun mkCompressedList(F.CLUSTER{blocks,regmaps,...}::rest) = let
91 :     fun f(F.MARK::blks,n) = f(blks,n+4)
92 :     | f(F.REALconst(lab,_)::blks,n) =
93 :     if n=0 then ALIGN::DATA 8::LABEL lab::f(blks,8)
94 :     else DATA n::ALIGN::DATA 8::LABEL lab::f(blks,8)
95 :     | f(F.STRINGconst(lab,_,s)::blks,n) = let val sSize = String.size s
96 :     in if n=0 then DATA 8::LABEL lab::f(blks,sSize)
97 :     else DATA(n+8)::LABEL lab::f(blks,sSize)
98 :     end
99 :     | f(F.JMPtable(lab,labs)::blks,n) = let val tSize = 4 * length labs
100 :     in if n=0 then LABEL lab::f(blks,tSize)
101 :     else DATA n::LABEL lab::f(blks,tSize)
102 :     end
103 :     | f(F.LABEL lab::blks,n) =
104 :     if n=0 then LABEL lab::f(blks,0)
105 :     else DATA n::LABEL lab::f(blks,0)
106 :     | f(F.CODE instrs::blks,n) = let
107 :     val v = !instrs
108 :     fun findSdis(~1,min,max,sdis) = (sdis,min,max)
109 :     | findSdis(n,min,max,sdis) = let
110 :     val insn = vsub(v,n)
111 :     val minSize = P.minSize insn
112 :     val maxSize = P.maxSize insn
113 :     in
114 :     if P.isSdi insn then
115 :     findSdis(n-1,min,max,(n,minSize,minSize)::sdis)
116 :     else
117 :     findSdis(n-1,min+minSize,max+maxSize,sdis)
118 :     end
119 :     val (sdis,min,max) = findSdis(Vector.length v-1,0,0,[])
120 :     val icount =
121 :     if Word.andb(Word.fromInt(!Control.CG.misc4), 0w4096) <> 0w0
122 :     then 4
123 :     else 0
124 :     val cn = CODE{code=instrs,
125 :     sdi=ref sdis,
126 :     minSize=min + icount,
127 :     maxSize=max + icount,
128 :     regmaps=regmaps}
129 :     in
130 :     if n=0 then cn::f(blks,0) else DATA n::cn::f(blks,0)
131 :     end
132 :     | f(F.BBLOCK _::_,_) = error "mkCompressedList.f: BBLOCK"
133 :     | f([],n) =
134 :     if n=0 then mkCompressedList rest else DATA n::mkCompressedList rest
135 :     in
136 :     f(blocks,0)
137 :     end
138 :     | mkCompressedList [] = []
139 :    
140 :     local
141 :     (* modifies the entries for SDIs and labmap
142 :     * according to extremety
143 :     *)
144 :     fun fixLabels(compressed,labMap,extremety) = let
145 :     val lookup = Intmap.map labMap
146 :     val enter = Intmap.add labMap
147 :     val lookupLabel = lookup o Label.id
148 :    
149 :     fun fix([],_,changed) = changed
150 :     | fix(ALIGN::blks,loc,changed) = fix(blks,loc+4,changed)
151 :     | fix(DATA n::blks,loc,changed) = fix(blks,loc+n,changed)
152 :     | fix(LABEL lab::blks,loc,changed) = let
153 :     val id = Label.id lab
154 :     in
155 :     if changed then (enter(id,loc); fix(blks,loc,changed))
156 :     else if lookup id = loc then fix(blks,loc,changed)
157 :     else (enter(id,loc); fix(blks,loc,true))
158 :     end
159 :     | fix(CODE{sdi=ref [],minSize,maxSize,...}::blks,loc,changed) =
160 :     (case extremety
161 :     of LO => fix(blks,minSize+loc,changed)
162 :     | HI => fix(blks,maxSize+loc,changed))
163 :     | fix(CODE{code,sdi=rsdi,minSize,maxSize,...}::blks,loc,changed) = let
164 :     val instrs = !code
165 :     val codeLen = Vector.length instrs - 1
166 :     val sdi = !rsdi
167 :     val codeSize = case extremety of LO =>minSize | HI =>maxSize
168 :    
169 :     (* sumSdiSize(SDIs,size,delta,acc)
170 :     * delta - is the increase in size of SDIs needed
171 :     * to calculate the correct value of loc.
172 :     *)
173 :     fun sumSdiSize([],size,_,sdi') = (size,rev sdi')
174 :     | sumSdiSize((sdi as (n,lo,hi))::rest,size,delta,sdi') = let
175 :     val sdiLoc = (codeLen-n)*4+loc+delta
176 :     val s = P.sdiSize(vsub(instrs,n),lookupLabel,sdiLoc)
177 :     in
178 :     case extremety
179 :     of LO =>
180 :     if s <= lo then
181 :     sumSdiSize(rest,size+lo,delta+lo-4,sdi::sdi')
182 :     else
183 :     sumSdiSize(rest,size+s,delta+s-4,(n,s,hi)::sdi')
184 :     | HI =>
185 :     if s <= hi then
186 :     sumSdiSize(rest,size+hi,delta+hi-4,sdi::sdi')
187 :     else
188 :     sumSdiSize(rest,size+s,delta+s-4,(n,lo,s)::sdi')
189 :     end (* sumSdiSize *)
190 :     val (sdiSize,sdi') = sumSdiSize(sdi,0,0,[])
191 :     in
192 :     rsdi:=sdi';
193 :     fix(blks,loc+codeSize+sdiSize,changed)
194 :     end (* fix *)
195 :     fun fixpoint () = if fix(compressed,0,false) then fixpoint() else ()
196 :     in
197 :     fixpoint()
198 :     end (* fixLabels *)
199 :     in
200 :     fun fixLoLabels(compressed,labMap) = fixLabels(compressed,labMap,LO)
201 :     fun fixHiLabels(compressed,labMap) = fixLabels(compressed,labMap,HI)
202 :     end
203 :    
204 :     (* note: The result of initLabMaps can be used to short circuit
205 :     * all this, if we know that max < {some machine specifc constant}
206 :     * that guarantees that all sdis will be their minimum size. Should
207 :     * add a flag minSdiGuarantee to machine description.
208 :     *)
209 :     fun process compressed = let
210 :     exception BBSchedLabMap
211 :     val lowLabMap : int Intmap.intmap = Intmap.new(16,BBSchedLabMap)
212 :     val hiLabMap : int Intmap.intmap = Intmap.new(16,BBSchedLabMap)
213 :     val lookupHi = Intmap.map hiLabMap
214 :    
215 :     (* initialize label maps based on extremety *)
216 :     fun initLabMaps () = let
217 :     val enterLow = Intmap.add lowLabMap
218 :     val enterHi = Intmap.add hiLabMap
219 :     fun iter([],_,hi) = hi
220 :     | iter(ALIGN::blks,low,hi) = iter(blks,low+4,hi+4)
221 :     | iter(DATA n::blks,low,hi) = iter(blks,low+n,hi+n)
222 :     | iter(LABEL lab::blks,low,hi) = let val id = Label.id lab
223 :     in
224 :     enterLow(id,low); enterHi(id,hi); iter(blks,low,hi)
225 :     end
226 :     | iter(CODE{minSize,maxSize,sdi,code,...}::blks,low,hi) = let
227 :     fun doSdi((n,_,_)::rest,size,acc) = let
228 :     val sdiSize=P.minSize(vsub(!code,n))
229 :     in
230 :     doSdi(rest,size+sdiSize,(n,sdiSize,sdiSize)::acc)
231 :     end
232 :     | doSdi([],size,acc) = (size,rev acc)
233 :    
234 :     val (sdiBaseSize,sdi') = doSdi(!sdi,0,[])
235 :     in
236 :     sdi:=sdi';
237 :     iter(blks,low+minSize+sdiBaseSize,hi+maxSize+sdiBaseSize)
238 :     end
239 :     in
240 :     iter(compressed,0,0)
241 :     end (* initLabMaps *)
242 :    
243 :     (* invokeSchedule: - expands sdis to native instructions before
244 :     * invoking the scheduler.
245 :     *)
246 :     fun invokeSchedule(codeRef,sdis,regmaps) = let
247 :     fun expand(instrs,sdis) = let
248 :     val ilen = Vector.length instrs
249 :     val vec = Array.array(ilen,0)
250 :     fun markSdi[] = ()
251 :     | markSdi((n,_,hi)::rest) =
252 :     (Array.update(vec,n,hi); markSdi rest)
253 :    
254 :     fun f(~1,[],acc) = acc
255 :     | f(~1,curr,acc) = rev(Vector.fromList curr::acc)
256 :     | f(n,curr,acc) = let
257 :     val insn = vsub(instrs,n)
258 :     fun add([],curr,acc) = (curr,acc)
259 :     | add(instr::rest,curr,acc) =
260 :     (case P.instrKind instr
261 :     of P.IK_JUMP =>
262 :     add(rest,[], Vector.fromList(instr::curr)::acc)
263 :     | _ => add(rest,instr::curr,acc)
264 :     (* esac *))
265 :     val size = Array.sub(vec,n)
266 :     in
267 :     if (size = 0) then f(n-1,insn::curr,acc)
268 :     else let
269 :     val sdiCode = P.expand(insn,size,lookupHi)
270 :     val (curr',acc') = add(sdiCode,curr,acc)
271 :     in
272 :     f(n-1,curr',acc')
273 :     end
274 :     end
275 :     in
276 :     markSdi sdis;
277 :     f(ilen -1,[],[])
278 :     end (* expand *)
279 :    
280 :     fun doit(iv::instrV,acc) =
281 :     doit(instrV,Scheduler.schedule(iv,regmaps) :: acc)
282 :     | doit([],acc) = let
283 :     fun vecToList(v, i, len) =
284 :     if i = len then [] else Vector.sub(v, i)::vecToList(v, i+1, len)
285 :     fun merge([], acc) = acc
286 :     | merge(v::vs, acc) =
287 :     merge(vs, vecToList(v,0,Vector.length v) @ acc)
288 :     in
289 :     Vector.fromList (merge(acc, []))
290 :     end
291 :     val newCode = doit(expand(!codeRef,sdis),[])
292 :     in
293 :     codeRef:=newCode; DATA(Vector.length newCode * 4)
294 :     end (* invokeSchedule *)
295 :    
296 :     fun procStableBBs([],cl,stable,unStable) = (rev cl,stable,unStable)
297 :     | procStableBBs(CODE{code,sdi=ref [],regmaps,...}::blks,cl,s,u) = let
298 :     val sched'd = Scheduler.schedule(!code, regmaps)
299 :     val nd = DATA(Vector.length sched'd * 4)
300 :     in
301 :     code:=sched'd; procStableBBs(blks,nd::cl,s+1,u)
302 :     end
303 :     | procStableBBs((c as CODE{code,sdi,regmaps,...})::blks,cl,s,u) = let
304 :     val instrs = !code
305 :     val sdi' = !sdi
306 :    
307 :     fun isStable [] = true
308 :     | isStable((_,lo:int,hi)::rest) = lo=hi andalso isStable rest
309 :    
310 :     fun initSdi [] = []
311 :     | initSdi((n,_,_)::rest) = let
312 :     val min = P.minSize(vsub(instrs,n))
313 :     in
314 :     (n,min,min)::initSdi rest
315 :     end
316 :    
317 :     in
318 :     if isStable(sdi')
319 :     then let val nd = invokeSchedule(code,sdi',regmaps)
320 :     in
321 :     procStableBBs(blks,nd::cl,s+1,u)
322 :     end
323 :     else
324 :     (sdi := initSdi sdi';
325 :     procStableBBs(blks,c::cl,s,u+1))
326 :     end
327 :     | procStableBBs(blk::blks,cl,s,u) = procStableBBs(blks,blk::cl,s,u)
328 :    
329 :     fun procUnStableBBs([],cl) = rev cl
330 :     | procUnStableBBs(CODE{code,sdi,regmaps,...}::blks,cl) = let
331 :     val nd = invokeSchedule(code,!sdi,regmaps)
332 :     in
333 :     procUnStableBBs(blks,nd::cl)
334 :     end
335 :     | procUnStableBBs(blk::blks,cl) = procUnStableBBs(blks,blk::cl)
336 :    
337 :     val max = initLabMaps()
338 :     val _ = (fixLoLabels(compressed,lowLabMap);
339 :     fixHiLabels(compressed,hiLabMap))
340 :    
341 :     val (cl,nStable,nUnStable) = procStableBBs(compressed,[],0,0)
342 :     in
343 :     if nUnStable = 0 then cl
344 :     else if nStable <> 0 then process cl
345 :     else
346 :     (print "processing unstable...\n";
347 :     initLabMaps();
348 :     fixHiLabels(cl,hiLabMap);
349 :     procUnStableBBs(cl,[]))
350 :     end (* process *)
351 :    
352 :     fun finish () = let
353 :     fun initLabels([],loc) = loc
354 :     | initLabels(ALIGN::blks,loc) = initLabels(blks,align loc)
355 :     | initLabels(LABEL lab::blks,loc) =
356 :     (Label.setAddr(lab,loc); initLabels(blks,loc))
357 :     | initLabels(DATA n::blks,loc) = initLabels(blks,loc+n)
358 :     | initLabels(CODE _::_,_) = error "finish.initLabels"
359 :    
360 :     val clusters = rev (!clusterList) before clusterList := []
361 :     val codeList = process(mkCompressedList clusters)
362 :     val size = initLabels(codeList,0)
363 :    
364 :     fun emitInstrs(n,instrs,regmaps) =
365 :     (E.emitInstr(vsub(instrs,n),regmaps);
366 :     emitInstrs(n+1,instrs,regmaps))
367 :     handle _ => ()
368 :    
369 :     fun emit(F.CLUSTER{blocks,regmaps,...}) = let
370 :     fun emitBlock F.MARK = E.mark ()
371 :     | emitBlock(F.LABEL lab) = E.defineLabel lab
372 :     | emitBlock(F.REALconst arg) = E.emitReal arg
373 :     | emitBlock(F.STRINGconst arg) = E.emitString arg
374 :     | emitBlock(F.JMPtable(lab,labs)) = E.emitJmpTable(lab,labs)
375 :     | emitBlock(F.BBLOCK{insns,...}) = error "finish:F.BBLOCK"
376 :     | emitBlock(F.CODE(instrs)) = emitInstrs(0,!instrs,regmaps)
377 :     in app emitBlock blocks
378 :     end
379 :     in
380 :     E.init size;
381 :     app emit (clusters)
382 :     end (* finish *)
383 :    
384 :     val finish = Stats.doPhase (Stats.makePhase "Compiler 130 Schedule") finish
385 :    
386 :     end (* BBSched *)
387 :    
388 :     (*
389 :     * $Log: bbsched.sml,v $
390 :     * Revision 1.1.1.1 1997/04/19 18:14:20 george
391 :     * Version 109.27
392 :     *
393 :     *)

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