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/instructions/cells-basis.sml
ViewVC logotype

Annotation of /sml/trunk/src/MLRISC/instructions/cells-basis.sml

Parent Directory Parent Directory | Revision Log Revision Log


Revision 796 - (view) (download)

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

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