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 889 - (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 :     fun toString(c as CELL{desc=DESC{toString, ...},...}) =
151 :     toString(registerNum c)
152 :    
153 :     fun toStringWithSize(c as CELL{desc=DESC{toStringWithSize,...},...},sz) =
154 :     toStringWithSize(registerNum c,sz)
155 :    
156 : leunga 775 fun cnv(r, low, high) = if low <= r andalso r <= high then r - low else r
157 :     fun show(DESC{toString, low, high, ...}) r = toString(cnv(r,low,high))
158 :     fun showWithSize(DESC{toStringWithSize, low, high, ...}) (r, sz) =
159 :     toStringWithSize(cnv(r,low,high),sz)
160 :    
161 : leunga 744 structure SortedCells = struct
162 :     type sorted_cells = cell list
163 :    
164 :     val empty = []
165 :    
166 :     val size = List.length
167 :    
168 :     fun enter(cell, l) = let
169 :     val c = registerId cell
170 :     fun f [] = [cell]
171 :     | f (l as (h::t)) =
172 :     let val ch = registerId h
173 :     in if c < ch then cell::l else if c > ch then h::f t else l
174 :     end
175 :     in f l
176 :     end
177 :    
178 : leunga 796 fun member(x, l) =
179 :     let val x = registerId x
180 :     in List.exists (fn y => registerId y = x) l
181 :     end
182 :    
183 : leunga 744 fun rmv(cell, l) = let
184 :     val c = registerId cell
185 :     fun f [] = []
186 :     | f (l as (h::t)) =
187 :     let val ch = registerId h
188 :     in if c = ch then t
189 :     else if c < ch then l
190 :     else h::f l
191 :     end
192 :     in f l
193 :     end
194 :    
195 :     fun uniq (cells) = List.foldl enter [] (map chase cells)
196 :    
197 :     fun difference([], _) = []
198 :     | difference(l, []) = l
199 :     | difference(l1 as x::xs, l2 as y::ys) =
200 :     let val cx = registerId x and cy = registerId y
201 :     in if cx = cy then difference(xs,ys)
202 :     else if cx < cy then x::difference(xs,l2)
203 :     else difference(l1,ys)
204 :     end
205 :    
206 :     fun union(a, []) = a
207 :     | union([], a) = a
208 :     | union(l1 as x::xs, l2 as y::ys) =
209 :     let val cx = registerId x and cy = registerId y
210 :     in if cx = cy then x::union(xs,ys)
211 :     else if cx < cy then x::union(xs,l2)
212 :     else y::union(l1,ys)
213 :     end
214 :    
215 :     fun intersect(a, []) = []
216 :     | intersect([], a) = []
217 :     | intersect(l1 as x::xs, l2 as y::ys) =
218 :     let val cx = registerId x and cy = registerId y
219 :     in if cx = cy then x::intersect(xs,ys)
220 :     else if cx < cy then intersect(xs,l2)
221 :     else intersect(l1,ys)
222 :     end
223 :    
224 :     fun notEq([], []) = false
225 :     | notEq([], l) = true
226 :     | notEq(_, []) = true
227 :     | notEq(x::l1, y::l2) = registerId x <> registerId y orelse notEq(l1,l2)
228 :    
229 :     fun eq([], []) = true
230 :     | eq(x::l1, y::l2) = registerId x = registerId y orelse eq(l1,l2)
231 :     | eq(_, _) = false
232 :    
233 :     fun return cs = cs
234 :    
235 :     fun isEmpty [] = true
236 :     | isEmpty _ = false
237 :    
238 :     fun emptyIntersection(_, []) = true
239 :     | emptyIntersection([], _) = true
240 :     | emptyIntersection(l1 as x::xs, l2 as y::ys) =
241 :     let val cx = registerId x and cy = registerId y
242 :     in if cx = cy then false
243 :     else if cx < cy then emptyIntersection(xs,l2)
244 :     else emptyIntersection(l1,ys)
245 :     end
246 :    
247 :     fun nonEmptyIntersection(_, []) = false
248 :     | nonEmptyIntersection([], _) = false
249 :     | nonEmptyIntersection(l1 as x::xs, l2 as y::ys) =
250 :     let val cx = registerId x and cy = registerId y
251 :     in if cx = cy then true
252 :     else if cx < cy then nonEmptyIntersection(xs,l2)
253 :     else nonEmptyIntersection(l1,ys)
254 :     end
255 :     end
256 :    
257 :     structure HashTable =
258 :     HashTableFn(type hash_key = cell
259 :     val hashVal = hashCell
260 :     val sameKey = sameCell)
261 :    
262 : leunga 775 structure ColorTable =
263 :     HashTableFn(type hash_key = cell
264 :     val hashVal = hashColor
265 :     val sameKey = sameColor)
266 :    
267 : leunga 744 (*
268 :     * These annotations specifies definitions and uses
269 :     * for a pseudo instruction.
270 :     *)
271 :     exception DEF_USE of {cellkind:cellkind, defs:cell list, uses:cell list}
272 :     val DEFUSE = Annotations.new'
273 :     {create=DEF_USE,
274 :     get=fn DEF_USE x => x | e => raise e,
275 :     toString=fn{cellkind,defs,uses} =>
276 :     "DEFUSE"^cellkindToString cellkind
277 :     }
278 :     (*
279 :     * Hack for generating memory aliasing cells
280 :     *)
281 :     val memDesc =
282 :     DESC
283 :     {kind = MEM,
284 :     counter = ref 0,
285 : george 823 dedicated = ref 0,
286 : leunga 744 low = 0,
287 :     high = ~1,
288 :     toString = fn m => "m"^i2s m,
289 :     toStringWithSize = fn (m, _) => "m"^i2s m,
290 :     defaultValues = [],
291 : george 889 physicalRegs = ref array0,
292 : leunga 744 zeroReg = NONE
293 :     }
294 :    
295 :     fun mem id = CELL{id=id, an=ref [], desc=memDesc, col=ref(MACHINE id)}
296 :    
297 : george 889 val array0 = Array.tabulate(0, fn _ => raise Match) : cell Array.array
298 : leunga 744 end
299 :    

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