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/blume-private-devel/src/MLRISC/instructions/cells-basis.sml
ViewVC logotype

Annotation of /sml/branches/blume-private-devel/src/MLRISC/instructions/cells-basis.sml

Parent Directory Parent Directory | Revision Log Revision Log


Revision 1408 - (view) (download)

1 : leunga 744 (*
2 :     * Description of cell and other updatable cells.
3 :     *
4 :     * -- Allen.
5 :     *)
6 :    
7 : george 889
8 : leunga 744 (*
9 : george 889 * Basic utilities on cells
10 : leunga 744 *)
11 : george 889 structure CellsBasis : CELLS_BASIS =
12 : leunga 744 struct
13 :    
14 :     datatype cellkindInfo = INFO of {name:string, nickname:string}
15 :    
16 :     type sz = int (* width in bits *)
17 :     type cell_id = int (* unique cell identifier *)
18 :     type register_id = int (* encoding of phsyical registers *)
19 :     type register_num = int
20 :    
21 :     (* Cellkind denote the types of storage cells.
22 :     * This definition is further augumented by architecture specific
23 :     * cells descriptions. Type cellkind is an equality type.
24 :     *)
25 :     datatype cellkind =
26 :     GP (* general purpose register *)
27 :     | FP (* floating point register *)
28 :     | CC (* condition code register *)
29 :    
30 :     | MEM (* memory *)
31 :     | CTRL (* control dependence *)
32 :    
33 :     | MISC_KIND of cellkindInfo ref (* client defined *)
34 :    
35 :     (* This data structure is automatically generated by MDGen to
36 :     * describe a cellkind.
37 :     *)
38 :     datatype cellkindDesc =
39 :     DESC of
40 :     {kind : cellkind,
41 :     counter : int ref,
42 : george 823 dedicated : int ref,
43 :     (* It is sometimes desirable to allocate dedicated
44 :     * pseudo registers that will get rewritten to something else,
45 :     * e.g., the virtual frame pointer.
46 :     * Since these registers are never assigned a register by
47 :     * the register allocator, a limited number of these kinds
48 :     * of registers may be generated.
49 :     *)
50 : leunga 744 low : int,
51 :     high : int,
52 :     toString : register_id -> string,
53 :     toStringWithSize : register_id * sz -> string,
54 :     defaultValues : (register_id * int) list,
55 :     physicalRegs : cell Array.array ref,
56 :     zeroReg : register_id option
57 :     }
58 :    
59 :     and cell =
60 :     CELL of {id : cell_id,
61 :     col : cellColor ref,
62 :     desc : cellkindDesc,
63 :     an : Annotations.annotations ref
64 :     }
65 :    
66 :     and cellColor =
67 :     MACHINE of register_id
68 :     | PSEUDO
69 :     | ALIASED of cell
70 :     | SPILLED
71 :    
72 :     val array0 = Array.tabulate(0, fn _ => raise Match) : cell Array.array
73 :    
74 :     fun error msg = MLRiscErrorMsg.error ("CellBasis", msg)
75 :    
76 :     val i2s = Int.toString
77 :    
78 :     fun cellkindToString GP = "GP"
79 :     | cellkindToString FP = "FP"
80 :     | cellkindToString CC = "CC"
81 :     | cellkindToString MEM = "MEM"
82 :     | cellkindToString CTRL = "CTRL"
83 : george 889 | cellkindToString (MISC_KIND(ref(INFO{name, ...}))) = name
84 : leunga 744
85 :     fun cellkindToNickname GP = "r"
86 :     | cellkindToNickname FP = "f"
87 :     | cellkindToNickname CC = "cc"
88 :     | cellkindToNickname MEM = "m"
89 :     | cellkindToNickname CTRL = "ctrl"
90 : george 889 | cellkindToNickname (MISC_KIND(ref(INFO{nickname, ...}))) = nickname
91 : leunga 744
92 :     fun newCellKind{name="GP", ...} = GP
93 :     | newCellKind{name="FP", ...} = FP
94 :     | newCellKind{name="CC", ...} = CC
95 :     | newCellKind{name="MEM", ...} = MEM
96 :     | newCellKind{name="CTRL", ...} = CTRL
97 :     | newCellKind{name, nickname} =
98 :     MISC_KIND(ref(INFO{name=name, nickname=nickname}))
99 :    
100 :     fun chase(CELL{col=ref(ALIASED c), ...}) = chase(c)
101 :     | chase c = c
102 :    
103 :     fun registerId(CELL{col=ref(ALIASED c), ...}) = registerId(c)
104 :     | registerId(CELL{col=ref(MACHINE r), ...}) = r
105 :     | registerId(CELL{col=ref(SPILLED), ...}) = ~1
106 :     | registerId(CELL{col=ref(PSEUDO), id, ...}) = id
107 :    
108 :     fun registerNum(CELL{col=ref(ALIASED c), ...}) = registerNum(c)
109 :     | registerNum(CELL{col=ref(MACHINE r), desc=DESC{low,...}, ...}) = r-low
110 :     | registerNum(CELL{col=ref SPILLED, id, ...}) = ~1
111 :     | registerNum(CELL{col=ref PSEUDO, id, ...}) = id
112 :    
113 :     fun physicalRegisterNum(CELL{col=ref(ALIASED c), ...}) =
114 :     physicalRegisterNum(c)
115 :     | physicalRegisterNum(CELL{col=ref(MACHINE r),
116 :     desc=DESC{low,...}, ...}) = r-low
117 :     | physicalRegisterNum(CELL{col=ref SPILLED, id, ...}) =
118 :     error("physicalRegisterNum: SPILLED: "^i2s id)
119 :     | physicalRegisterNum(CELL{col=ref PSEUDO, id, ...}) =
120 :     error("physicalRegisterNum: PSEUDO: "^i2s id)
121 :    
122 :    
123 :     fun cellId(CELL{id, ...}) = id
124 :    
125 :     fun hashCell(CELL{id, ...}) = Word.fromInt id
126 : leunga 775 fun hashColor c = Word.fromInt(registerId c)
127 : leunga 744 fun desc(CELL{desc, ...}) = desc
128 :     fun sameCell(c1, c2) = cellId(c1) = cellId(c2)
129 :     fun sameDesc(DESC{counter=x, ...}, DESC{counter=y, ...}) = x=y
130 :     fun sameKind(c1, c2) = sameDesc(desc c1,desc c2)
131 :     fun sameAliasedCell(c1, c2) = sameCell(chase c1, chase c2)
132 :     fun sameColor(c1, c2) = registerId c1 = registerId c2
133 : leunga 775 fun compareColor(c1, c2) = Int.compare(registerId c1, registerId c2)
134 : leunga 744 fun cellkind(CELL{desc=DESC{kind, ...}, ...}) = kind
135 :     fun annotations(CELL{an, ...}) = an
136 :    
137 :     fun setAlias{from, to} =
138 : leunga 775 let val CELL{id, col, desc=DESC{kind, ...}, ...} = chase from
139 : leunga 744 val to as CELL{col=colTo, ...} = chase to
140 :     in if col = colTo then () (* prevent self-loops *)
141 : leunga 775 else if id < 0 then error "setAlias: constant"
142 :     else case (!col, kind)
143 :     of (PSEUDO, _) => col := ALIASED to
144 :     | _ => error "setAlias: non-pseudo"
145 : leunga 744 end
146 :    
147 : leunga 775 fun isConst(CELL{id, ...}) = id < 0
148 :    
149 : leunga 744 (* Pretty printing of cells *)
150 : mblume 1408 fun toString(CELL{col=ref(ALIASED c), ...}) = toString(c)
151 :     | toString(c as CELL{desc=DESC{toString, ...}, ...}) =
152 : leunga 744 toString(registerNum c)
153 :    
154 :     fun toStringWithSize(c as CELL{desc=DESC{toStringWithSize,...},...},sz) =
155 :     toStringWithSize(registerNum c,sz)
156 :    
157 : leunga 775 fun cnv(r, low, high) = if low <= r andalso r <= high then r - low else r
158 :     fun show(DESC{toString, low, high, ...}) r = toString(cnv(r,low,high))
159 :     fun showWithSize(DESC{toStringWithSize, low, high, ...}) (r, sz) =
160 :     toStringWithSize(cnv(r,low,high),sz)
161 :    
162 : leunga 744 structure SortedCells = struct
163 :     type sorted_cells = cell list
164 :    
165 :     val empty = []
166 :    
167 :     val size = List.length
168 :    
169 :     fun enter(cell, l) = let
170 :     val c = registerId cell
171 :     fun f [] = [cell]
172 :     | f (l as (h::t)) =
173 :     let val ch = registerId h
174 :     in if c < ch then cell::l else if c > ch then h::f t else l
175 :     end
176 :     in f l
177 :     end
178 :    
179 : leunga 796 fun member(x, l) =
180 :     let val x = registerId x
181 :     in List.exists (fn y => registerId y = x) l
182 :     end
183 :    
184 : leunga 744 fun rmv(cell, l) = let
185 :     val c = registerId cell
186 :     fun f [] = []
187 :     | f (l as (h::t)) =
188 :     let val ch = registerId h
189 :     in if c = ch then t
190 :     else if c < ch then l
191 :     else h::f l
192 :     end
193 :     in f l
194 :     end
195 :    
196 :     fun uniq (cells) = List.foldl enter [] (map chase cells)
197 :    
198 :     fun difference([], _) = []
199 :     | difference(l, []) = l
200 :     | difference(l1 as x::xs, l2 as y::ys) =
201 :     let val cx = registerId x and cy = registerId y
202 :     in if cx = cy then difference(xs,ys)
203 :     else if cx < cy then x::difference(xs,l2)
204 :     else difference(l1,ys)
205 :     end
206 :    
207 :     fun union(a, []) = a
208 :     | union([], a) = a
209 :     | union(l1 as x::xs, l2 as y::ys) =
210 :     let val cx = registerId x and cy = registerId y
211 :     in if cx = cy then x::union(xs,ys)
212 :     else if cx < cy then x::union(xs,l2)
213 :     else y::union(l1,ys)
214 :     end
215 :    
216 :     fun intersect(a, []) = []
217 :     | intersect([], a) = []
218 :     | intersect(l1 as x::xs, l2 as y::ys) =
219 :     let val cx = registerId x and cy = registerId y
220 :     in if cx = cy then x::intersect(xs,ys)
221 :     else if cx < cy then intersect(xs,l2)
222 :     else intersect(l1,ys)
223 :     end
224 :    
225 :     fun notEq([], []) = false
226 :     | notEq([], l) = true
227 :     | notEq(_, []) = true
228 :     | notEq(x::l1, y::l2) = registerId x <> registerId y orelse notEq(l1,l2)
229 :    
230 :     fun eq([], []) = true
231 :     | eq(x::l1, y::l2) = registerId x = registerId y orelse eq(l1,l2)
232 :     | eq(_, _) = false
233 :    
234 :     fun return cs = cs
235 :    
236 :     fun isEmpty [] = true
237 :     | isEmpty _ = false
238 :    
239 :     fun emptyIntersection(_, []) = true
240 :     | emptyIntersection([], _) = true
241 :     | emptyIntersection(l1 as x::xs, l2 as y::ys) =
242 :     let val cx = registerId x and cy = registerId y
243 :     in if cx = cy then false
244 :     else if cx < cy then emptyIntersection(xs,l2)
245 :     else emptyIntersection(l1,ys)
246 :     end
247 :    
248 :     fun nonEmptyIntersection(_, []) = false
249 :     | nonEmptyIntersection([], _) = false
250 :     | nonEmptyIntersection(l1 as x::xs, l2 as y::ys) =
251 :     let val cx = registerId x and cy = registerId y
252 :     in if cx = cy then true
253 :     else if cx < cy then nonEmptyIntersection(xs,l2)
254 :     else nonEmptyIntersection(l1,ys)
255 :     end
256 :     end
257 :    
258 :     structure HashTable =
259 :     HashTableFn(type hash_key = cell
260 :     val hashVal = hashCell
261 :     val sameKey = sameCell)
262 :    
263 : leunga 775 structure ColorTable =
264 :     HashTableFn(type hash_key = cell
265 :     val hashVal = hashColor
266 :     val sameKey = sameColor)
267 :    
268 : jhr 900 structure CellSet =
269 :     struct
270 :     type cellset = (cellkindDesc * cell list) list
271 :     val empty = []
272 :    
273 :     fun same(DESC{counter=c1,...}, DESC{counter=c2,...}) = c1=c2
274 :    
275 :     fun descOf (CELL{desc, ...}) = desc
276 :    
277 :     fun add (r, cellset:cellset) =
278 :     let val k = descOf r
279 :     fun loop [] = [(k,[r])]
280 :     | loop((x as (k',s))::cellset) =
281 :     if same(k,k') then (k',r::s)::cellset
282 :     else x::loop cellset
283 :     in loop cellset end
284 :    
285 :     fun rmv (r, cellset:cellset) =
286 :     let val k = descOf r
287 :     val c = registerId r
288 :     fun filter [] = []
289 :     | filter(r::rs) = if registerId r = c then filter rs
290 :     else r::filter rs
291 :     fun loop [] = []
292 :     | loop((x as (k',s))::cellset) =
293 :     if same(k,k') then (k',filter s)::cellset else x::loop cellset
294 :     in loop cellset end
295 :    
296 :     fun get (k : cellkindDesc) = let
297 :     fun loop ([] : cellset) = []
298 :     | loop ((x as (k',s))::cellset) =
299 :     if same(k, k') then s else loop cellset
300 :     in
301 :     loop
302 :     end
303 :    
304 :     fun update (k : cellkindDesc) (cellset:cellset, s) = let
305 :     fun loop [] = [(k,s)]
306 :     | loop((x as (k',_))::cellset) =
307 :     if same(k,k') then (k',s)::cellset else x::loop cellset
308 :     in
309 :     loop cellset
310 :     end
311 :    
312 :     fun map {from,to} (cellset:cellset) =
313 :     let val CELL{desc=k,...} = from
314 :     val cf = registerId from
315 :     fun trans r = if registerId r = cf then to else r
316 :     fun loop [] = []
317 :     | loop((x as (k',s))::cellset) =
318 :     if same(k, k') then (k',List.map trans s)::cellset
319 :     else x::loop cellset
320 :     in loop cellset end
321 :    
322 :     val toCellList : cellset -> cell list =
323 :     List.foldr (fn ((_,S),S') => S @ S') []
324 :    
325 :     (* Pretty print cellset *)
326 :     fun printSet(f,set,S) =
327 :     let fun loop([], S) = "}"::S
328 :     | loop([x], S) = f(chase x)::"}"::S
329 :     | loop(x::xs, S) = f(chase x)::" "::loop(xs, S)
330 :     in "{"::loop(set, S) end
331 :    
332 :     fun toString' cellset =
333 :     let fun pr cellset =
334 : leunga 1025 let fun loop((DESC{kind, ...},s)::rest, S)=
335 : jhr 900 (case s of
336 :     [] => loop(rest, S)
337 :     | _ => cellkindToString kind::"="::
338 : leunga 1025 printSet(toString,s," "::loop(rest,S))
339 : jhr 900 )
340 :     | loop([],S) = S
341 :     in String.concat(loop(cellset, []))
342 :     end
343 :     in pr cellset end
344 :    
345 :     val toString = toString'
346 :     end (* CellSet *)
347 :    
348 : leunga 744 (*
349 :     * These annotations specifies definitions and uses
350 :     * for a pseudo instruction.
351 :     *)
352 :     exception DEF_USE of {cellkind:cellkind, defs:cell list, uses:cell list}
353 :     val DEFUSE = Annotations.new'
354 :     {create=DEF_USE,
355 :     get=fn DEF_USE x => x | e => raise e,
356 :     toString=fn{cellkind,defs,uses} =>
357 :     "DEFUSE"^cellkindToString cellkind
358 :     }
359 :     (*
360 :     * Hack for generating memory aliasing cells
361 :     *)
362 :     val memDesc =
363 :     DESC
364 :     {kind = MEM,
365 :     counter = ref 0,
366 : george 823 dedicated = ref 0,
367 : leunga 744 low = 0,
368 :     high = ~1,
369 :     toString = fn m => "m"^i2s m,
370 :     toStringWithSize = fn (m, _) => "m"^i2s m,
371 :     defaultValues = [],
372 : george 889 physicalRegs = ref array0,
373 : leunga 744 zeroReg = NONE
374 :     }
375 :    
376 :     fun mem id = CELL{id=id, an=ref [], desc=memDesc, col=ref(MACHINE id)}
377 :    
378 : george 889 val array0 = Array.tabulate(0, fn _ => raise Match) : cell Array.array
379 : leunga 744 end
380 :    

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