HCoop / hcoop / debian / mlton.git / blame
? search:
summary | shortlog | log | commit | commitdiff | tree
blob | blame (incremental) | history | HEAD
Import Upstream version 20180207
[hcoop/debian/mlton.git] / benchmark / tests / DLXSimulator.sml
CommitLineData
7f918cf1
CE		 1(* Minor tweaks by Stephen Weeks (sweeks@sweeks.com) on 2001-07-17 to turn into a
2 * benchmark.
3 * Added rand function.
4 *)
5(*
6 * Matthew Thomas Fluet
7 * Harvey Mudd College
8 * Claremont, CA 91711
9 * e-mail: Matthew_Fluet@hmc.edu
10 *
11 * A DLX Simulator in Standard ML
12 *
13 * Description:
14 * The DLX Simulator is a partial implementation of the RISC instruction
15 * set described in Patterson's and Hennessy's _Computer Architecture_.
16 * Currently, the DLX Simulator implements the following instructions:
17 * ADD ADDI
18 * ADDU ADDUI
19 * SUB SUBI
20 * SUBU SUBUI
21 * AND ANDI
22 * OR ORI
23 * XOR XORI
24 *
25 * LHI
26 *
27 * SLL SLLI
28 * SRL SRLI
29 * SRA SRAI
30 *
31 * SEQ SEQI
32 * SNE SNEI
33 * SLT SLTI
34 * SGT SGTI
35 * SLE SLEI
36 * SGE SGEI
37 *
38 * LB LBU SB
39 * LH LHU SH
40 * LW SW
41 *
42 * BEQZ BNEZ
43 * J JR
44 * JAL JALR
45 *
46 * TRAP
47 *
48 * NOP
49 *
50 * Currently, the DLX Simulator uses 32 bit words for addressing and
51 * the register file and a 65535 word memory. To augment the memory
52 * a cache can be installed in the simulator, with a number of different
53 * caching options that can be made. Caches can also cache other caches,
54 * so realistic dual level caches can be simulated. Input and output
55 * is limited to requesting and outputing signed integers.
56 *
57 * Usage:
58 * DLXSimulatorCX.run_file : string -> unit
59 * DLXSimulatorCX.run_prog : string list -> unit;
60 * The DLXSimualatorCX family of structures represent different caches
61 * used on the simulator. The following table describes the different
62 * caches used:
63 * C1: a small level 1 cache
64 * DLXSimulatorCX.run_file attempts to open and execute the instructions
65 * in a file. DLXSimulatorCX.run_prog runs a set of instructions as
66 * a list of strings. Four programs are included here.
67 * Simple : simply outputs the number 42.
68 * Twos: performs the twos complement on an inputed number.
69 * Abs: performs the absolute value on an imputed number.
70 * Fact: performs the factorial on an inputed number.
71 * GCD: performs the greatest common divisor on two imputed numbers.
72 * After running, the DLX Simulator outputs a set of statistics
73 * concerning memory reads and writes, and cache hits and misses.
74 *
75 * Future Work:
76 * With the implementation of the PACK_REAL structures
77 * as documented in the SML'97 Basis Library, the remainder
78 * of the DLX instruction set should be implemented.
79 * Currently, without an efficient and correct means of
80 * converting a 32 bit word into a 32 bit float, it is
81 * difficult to incorporate these instructions.
82 * In order to finish following the current development
83 * model, a FPALU structure should be implemented as the
84 * floating point arithmetic-logic unit.
85 * Another possibility for future work would be to
86 * model a pipelined processor. Currently, the DLX Simulator
87 * uses a simple one cycle per instruction model.
88 * It should be possible to break this model and implement
89 * a pipeline, but it would mean a major reworking of the
90 * DLXSimulatorFun functor.
91 *
92 * References:
93 * Patterson, David A. and John L. Hennessy. _Computer Architecture: A
94 * Quantitative Approach: Second Edition_. San Francisco: Morgan
95 * Kaufmann Publishers, Inc., 1996.
96 *
97 *)
98
99(* ************************************************************************* *)
100
101(* sweeks added rand *)
102local
103 open Word
104 val seed: word ref = ref 0w13
105in
106 (* From page 284 of Numerical Recipes in C. *)
107 fun rand (): word =
108 let
109 val res = 0w1664525 * !seed + 0w1013904223
110 val _ = seed := res
111 in
112 res
113 end
114end
115
116(*
117 * ImmArray.sml
118 *
119 * The ImmArray structure defines an immutable array implementation.
120 * An immarray is stored internally as a list.
121 * This results in O(n) sub and update functions, as opposed
122 * to O(1) sub and update functions found in Array. However,
123 * immutable arrays are truly immutable, and can be integrated
124 * with a functionally programming style easier than mutable
125 * arrays.
126 *
127 * The ImmArray structure mimics the Array structure as much as possible.
128 * The most obvious deviation is that unit return types in Array are replaced
129 * by 'a immarray return types in ImmArray. Unlike an 'a array, an 'a immarray
130 * is an equality type if and only if 'a is an equality type. Further immarray
131 * equality is structural, rather than the "creation" equality used by Array.
132 * Additionally, no vector type is supported, and consequently no copyVec
133 * function is supported. Finally, the functions mapi and map provide
134 * similar functionality as modifyi and modify, but relax the constraint that
135 * the argument function need be of type 'a -> 'a.
136 *
137 * Future Work : There are random-access list implementations
138 * that support O(log n) sub and update functions,
139 * which may provide a faster implementation, although
140 * possibly at the expense of space and the ease of
141 * implementing app, foldl, foldr, modify, and map functions.
142 *)
143
144signature IMMARRAY
145 = sig
146 type 'a immarray;
147
148 val maxLen : int;
149 val immarray : (int * 'a) -> 'a immarray;
150 val fromList : 'a list -> 'a immarray;
151 val toList : 'a immarray -> 'a list;
152
153 val tabulate : int * (int -> 'a) -> 'a immarray;
154 val length : 'a immarray -> int;
155
156 val sub : 'a immarray * int -> 'a;
157 val update : 'a immarray * int * 'a -> 'a immarray;
158 val extract : 'a immarray * int * int option -> 'a immarray;
159
160 val copy : {src : 'a immarray, si : int, len : int option,
161 dst : 'a immarray, di : int} -> 'a immarray;
162
163 val appi : (int * 'a -> unit) -> ('a immarray * int * int option)
164 -> unit;
165 val app : ('a -> unit) -> 'a immarray -> unit;
166 val foldli : ((int * 'a * 'b) -> 'b) -> 'b
167 -> ('a immarray * int * int option) -> 'b;
168 val foldri : ((int * 'a * 'b) -> 'b) -> 'b
169 -> ('a immarray * int * int option) -> 'b;
170 val foldl : (('a * 'b) -> 'b) -> 'b -> 'a immarray -> 'b;
171 val foldr : (('a * 'b) -> 'b) -> 'b -> 'a immarray -> 'b;
172 val mapi : ((int * 'a) -> 'b) -> ('a immarray * int * int option)
173 -> 'b immarray;
174 val map : ('a -> 'b) -> 'a immarray -> 'b immarray;
175 val modifyi : ((int * 'a) -> 'a) -> ('a immarray * int * int option)
176 -> 'a immarray;
177 val modify : ('a -> 'a) -> 'a immarray -> 'a immarray;
178 end;
179
180
181structure ImmArray : IMMARRAY
182 = struct
183
184 (* datatype 'a immarray
185 * An immarray is stored internally as a list.
186 * The use of a constructor prevents list functions from
187 * treating immarray type as a list.
188 *)
189 datatype 'a immarray = IA of 'a list;
190
191 (* val maxLen : int
192 * The maximum length of immarrays supported.
193 * Technically, under this implementation, the maximum length
194 * of immarrays is the same as the maximum length of a list,
195 * but for convience and compatibility, use the Array structure's
196 * maximum length.
197 *)
198 val maxLen = Array.maxLen;
199
200 (* val tabulate : int * (int -> 'a) -> 'a immarray
201 * val immarray : int * 'a -> 'a immarray
202 * val fromList : 'a list -> 'a immarray
203 * val toList : 'a immarray -> 'a list
204 * val length : 'a immarray -> int
205 * These functions perform basic immarray functions.
206 * The tabulate, immarray, and fromList functions create an immarray.
207 * The toList function converts an immarray to a list.
208 * The length function returns the length of an immarray.
209 *)
210 fun tabulate (n, initfn) = IA (List.tabulate (n, initfn));
211 fun immarray (n, init) = tabulate (n, fn _ => init);
212 fun fromList l = IA l;
213 fun toList (IA ia) = ia;
214 fun length (IA ia) = List.length ia;
215
216 (* val sub : 'a immarray * int -> 'a
217 * val update : 'a immarray * int * 'a -> 'a immarray
218 * These functions sub and update an immarray by index.
219 *)
220 fun sub (IA ia, i) = List.nth (ia, i);
221 fun update (IA ia, i, x) = IA ((List.take (ia, i)) @
222 (x::(List.drop (ia, i + 1))));
223
224 (* val extract : 'a immarray * int * int option -> 'a immarray
225 * This function extracts an immarray slice from an immarray from
226 * one index either through the rest of the immarray (NONE)
227 * or for n elements (SOME n), as described in the
228 * Standard ML Basis Library.
229 *)
230 fun extract (IA ia, i, NONE) = IA (List.drop (ia, i))
231 | extract (IA ia, i, SOME n) = IA (List.take (List.drop (ia, i), n));
232
233 (* val copy : {src : 'a immarray, si : int, len : int option,
234 dst : 'a immarray, di : int} -> 'a immarray
235 * This function copies an immarray slice from src into dst starting
236 * at the di element.
237 *)
238 fun copy {src, si, len, dst=IA ia, di}
239 = let
240 val IA sia = extract (src, si, len);
241 val pre = List.take (ia, di);
242 val post = case len
243 of NONE => List.drop (ia, di+(List.length sia))
244 | SOME n => List.drop (ia, di+n);
245 in
246 IA (pre @ sia @ post)
247 end;
248
249 (* val appi : ('a * int -> unit) -> ('a immarray * int * int option)
250 * -> unit
251 * val app : ('a -> unit) -> 'a immarray -> unit
252 * These functions apply a function to every element
253 * of an immarray. The appi function also provides the
254 * index of the element as an argument to the applied function
255 * and uses an immarray slice argument.
256 *)
257 local
258 fun appi_aux f i [] = ()
259 | appi_aux f i (h::t) = (f(i,h); appi_aux f (i + 1) t);
260 in
261 fun appi f (IA ia, i, len) = let
262 val IA sia = extract (IA ia, i, len);
263 in
264 appi_aux f i sia
265 end;
266 end;
267 fun app f immarr = appi (f o #2) (immarr, 0, NONE);
268
269 (* val foldli : (int * 'a * 'b -> 'b) -> 'b
270 * -> ('a immarray * int * int option) -> 'b;
271 * val foldri : (int * 'a * 'b -> 'b) -> 'b
272 * -> ('a immarray * int * int option) -> 'b;
273 * val foldl : ('a * 'b -> 'b) -> 'b -> 'a immarray -> 'b
274 * val foldr : ('a * 'b -> 'b) -> 'b -> 'a immarray -> 'b
275 * These functions fold a function over every element
276 * of an immarray. The foldri and foldli functions also provide
277 * the index of the element as an argument to the folded function
278 * and uses an immarray slice argument.
279 *)
280 local
281 fun foldli_aux f b i [] = b
282 | foldli_aux f b i (h::t) = foldli_aux f (f(i,h,b)) (i+1) t;
283 fun foldri_aux f b i [] = b
284 | foldri_aux f b i (h::t) = f(i,h,foldri_aux f b (i+1) t);
285 in
286 fun foldli f b (IA ia, i, len)
287 = let
288 val IA ia2 = extract (IA ia, i, len);
289 in
290 foldli_aux f b i ia2
291 end;
292 fun foldri f b (IA ia, i, len)
293 = let
294 val IA ia2 = extract (IA ia, i, len);
295 in
296 foldri_aux f b i ia2
297 end;
298 end;
299 fun foldl f b (IA ia) = foldli (fn (_,i,x) => f(i,x)) b (IA ia, 0, NONE);
300 fun foldr f b (IA ia) = foldri (fn (_,i,x) => f(i,x)) b (IA ia, 0, NONE);
301
302 (* val mapi : ('a * int -> 'b) -> 'a immarray -> 'b immarray
303 * val map : ('a -> 'b) -> 'a immarray -> 'b immarray
304 * These functions map a function over every element
305 * of an immarray. The mapi function also provides the
306 * index of the element as an argument to the mapped function
307 * and uses an immarray slice argument. Although there are
308 * similarities between mapi and modifyi, note that when mapi is
309 * used with an immarray slice, the resulting immarray is the
310 * same size as the slice. This is necessary to preserve the
311 * type of the resulting immarray. Thus, mapi with the identity
312 * function reduces to the extract function.
313 *)
314 local
315 fun mapi_aux f i [] = []
316 | mapi_aux f i (h::t) = (f (i,h))::(mapi_aux f (i + 1) t);
317 in
318 fun mapi f (IA ia, i, len) = let
319 val IA ia2 = extract (IA ia, i, len);
320 in
321 IA (mapi_aux f i ia2)
322 end;
323 end;
324 fun map f (IA ia)= mapi (f o #2) (IA ia, 0, NONE);
325
326 (* val modifyi : (int * 'a -> 'a) -> ('a immarray * int * int option)
327 * -> 'a immarray
328 * val modify : ('a -> 'a) -> 'a immarray -> 'a immarray
329 * These functions apply a function to every element of an immarray
330 * in left to right order and returns a new immarray where corresponding
331 * elements are replaced by their modified values. The modifyi
332 * function also provides the index of the element as an argument
333 * to the mapped function and uses an immarray slice argument.
334 *)
335 local
336 fun modifyi_aux f i [] = []
337 | modifyi_aux f i (h::t) = (f (i,h))::(modifyi_aux f (i + 1) t);
338 in
339 fun modifyi f (IA ia, i, len)
340 = let
341 val pre = List.take (ia, i);
342 val IA ia2 = extract (IA ia, i, len);
343 val post = case len
344 of NONE => []
345 | SOME n => List.drop (ia, i+n);
346 in
347 IA (pre @ (modifyi_aux f i ia2) @ post)
348 end;
349 end;
350 fun modify f (IA ia) = modifyi (f o #2) (IA ia, 0, NONE);
351
352 end;
353
354(* ************************************************************************* *)
355
356(*
357 * ImmArray2.sml
358 *
359 * The ImmArray2 structure defines a two dimensional immutable array
360 * implementation. An immarray2 is stored internally as an immutable
361 * array of immutable arrays. As such, the ImmArray2 makes heavy use
362 * of the ImmArray structure.
363 *
364 * The ImmArray2 structure mimics the Array2 structure as much as possible.
365 * The most obvious deviation is that unit return types in Array2 are replaced
366 * by 'a immarray2 return types in ImmArray2. Unlike an 'a array,
367 * an 'a immarray2 is an equality type if and only if 'a is an equality type.
368 * Further immarray2 equality is structural, rather than the "creation"
369 * equality used by Array2. Also, the 'a region type is not included in
370 * ImmArray2, but all functions in Array2 that require 'a regions are present
371 * with arguments taken in the natural order. Finally, the functions mapi
372 * and map provide similar functionality as modifyi and modify, but relax
373 * the constraint that the argument function need be of type 'a -> 'a.
374 *)
375
376signature IMMARRAY2
377 = sig
378
379 type 'a immarray2;
380
381 datatype traversal = RowMajor | ColMajor
382
383 val immarray2 : int * int * 'a -> 'a immarray2;
384 val tabulate : traversal -> int * int * ((int * int) -> 'a)
385 -> 'a immarray2;
386 val fromList : 'a list list -> 'a immarray2;
387 val dimensions : 'a immarray2 -> int * int;
388
389 val sub : 'a immarray2 * int * int -> 'a;
390 val update : 'a immarray2 * int * int * 'a -> 'a immarray2;
391 val extract : 'a immarray2 * int * int * int option * int option
392 -> 'a immarray2;
393
394 val copy : {src : 'a immarray2, si : int, sj : int,
395 ilen : int option, jlen : int option,
396 dst : 'a immarray2, di : int, dj : int} -> 'a immarray2;
397
398 val nRows : 'a immarray2 -> int;
399 val nCols : 'a immarray2 -> int;
400 val row : 'a immarray2 * int -> 'a ImmArray.immarray;
401 val column : 'a immarray2 * int -> 'a ImmArray.immarray;
402
403 val appi : traversal -> (int * int * 'a -> unit)
404 -> ('a immarray2 * int * int * int option * int option)
405 -> unit;
406 val app : traversal -> ('a -> unit) -> 'a immarray2 -> unit;
407 val foldli : traversal -> ((int * int * 'a * 'b) -> 'b) -> 'b
408 -> ('a immarray2 * int * int * int option * int option)
409 -> 'b
410 val foldri : traversal -> ((int * int * 'a * 'b) -> 'b) -> 'b
411 -> ('a immarray2 * int * int * int option * int option)
412 -> 'b
413 val foldl : traversal -> (('a * 'b) -> 'b) -> 'b -> 'a immarray2 -> 'b
414 val foldr : traversal -> (('a * 'b) -> 'b) -> 'b -> 'a immarray2 -> 'b
415 val mapi : traversal -> (int * int * 'a -> 'b)
416 -> ('a immarray2 * int * int * int option * int option)
417 -> 'b immarray2;
418 val map : traversal -> ('a -> 'b) -> 'a immarray2 -> 'b immarray2;
419 val modifyi : traversal -> ((int * int * 'a) -> 'a)
420 -> ('a immarray2 * int * int * int option * int option)
421 -> 'a immarray2;
422 val modify : traversal -> ('a -> 'a) -> 'a immarray2 -> 'a immarray2;
423 end;
424
425structure ImmArray2 : IMMARRAY2
426 = struct
427
428 (* datatype 'a immarray2
429 * An immarray2 is stored internally as an immutable array
430 * of immutable arrays. The use of a contructor prevents ImmArray
431 * functions from treating the immarray2 type as an immarray.
432 *)
433 datatype 'a immarray2 = IA2 of 'a ImmArray.immarray ImmArray.immarray;
434 datatype traversal = RowMajor | ColMajor
435
436 (* val tabulate : traversal -> int * int * (int * int -> 'a)
437 * -> 'a immarray2
438 * val immarray2 : int * int * 'a -> 'a immarray2
439 * val fromList : 'a list list -> 'a immarray2
440 * val dmensions : 'a immarray2 -> int * int
441 * These functions perform basic immarray2 functions.
442 * The tabulate and immarray2 functions create an immarray2.
443 * The fromList function converts a list of lists into an immarray2.
444 * Unlike Array2.fromList, fromList will accept lists of different
445 * lengths, allowing one to create an immarray2 in which the
446 * rows have different numbers of columns, although it is likely that
447 * exceptions will be raised when other ImmArray2 functions are applied
448 * to such an immarray2. Note that dimensions will return the
449 * number of columns in row 0.
450 * The dimensions function returns the dimensions of an immarray2.
451 *)
452 fun tabulate RowMajor (r, c, initfn)
453 = let
454 fun initrow r = ImmArray.tabulate (c, fn ic => initfn (r,ic));
455 in
456 IA2 (ImmArray.tabulate (r, fn ir => initrow ir))
457 end
458 | tabulate ColMajor (r, c, initfn)
459 = turn (tabulate RowMajor (c,r, fn (c,r) => initfn(r,c)))
460 and immarray2 (r, c, init) = tabulate RowMajor (r, c, fn (_, _) => init)
461 and fromList l
462 = IA2 (ImmArray.tabulate (length l,
463 fn ir => ImmArray.fromList (List.nth(l,ir))))
464 and dimensions (IA2 ia2) = (ImmArray.length ia2,
465 ImmArray.length (ImmArray.sub (ia2, 0)))
466
467 (* turn : 'a immarray2 -> 'a immarray2
468 * This function reverses the rows and columns of an immarray2
469 * to allow handling of ColMajor traversals.
470 *)
471 and turn ia2 = let
472 val (r,c) = dimensions ia2;
473 in
474 tabulate RowMajor (c,r,fn (cc,rr) => sub (ia2,rr,cc))
475 end
476
477 (* val sub : 'a immarray2 * int * int -> 'a
478 * val update : 'a immarray2 * int * int * 'a -> 'a immarray2
479 * These functions sub and update an immarray2 by indices.
480 *)
481 and sub (IA2 ia2, r, c) = ImmArray.sub(ImmArray.sub (ia2, r), c);
482 fun update (IA2 ia2, r, c, x)
483 = IA2 (ImmArray.update (ia2, r,
484 ImmArray.update (ImmArray.sub (ia2, r),
485 c, x)));
486
487 (* val extract : 'a immarray2 * int * int *
488 * int option * int option -> 'a immarray2
489 * This function extracts a subarray from an immarray2 from
490 * one pair of indices either through the rest of the
491 * immarray2 (NONE, NONE) or for the specfied number of elements.
492 *)
493 fun extract (IA2 ia2, i, j, rlen, clen)
494 = IA2 (ImmArray.map (fn ia => ImmArray.extract (ia, j, clen))
495 (ImmArray.extract (ia2, i, rlen)));
496
497 (* val nRows : 'a immarray2 -> int
498 * val nCols : 'a immarray2 -> int
499 * These functions return specific dimensions of an immarray2.
500 *)
501 fun nRows (IA2 ia2) = (#1 o dimensions) (IA2 ia2);
502 fun nCols (IA2 ia2) = (#2 o dimensions) (IA2 ia2);
503 (* val row : immarray2 * int -> ImmArray.immarray
504 * val column : immarray2 * int -> ImmArray.immarray
505 * These functions extract an entire row or column from
506 * an immarray2 by index, returning the row or column as
507 * an ImmArray.immarray.
508 *)
509 fun row (ia2, r) = let
510 val (c, _) = dimensions ia2;
511 in
512 ImmArray.tabulate (c, fn i => sub (ia2, r, i))
513 end;
514 fun column (ia2, c) = let
515 val (_, r) = dimensions ia2;
516 in
517 ImmArray.tabulate (r, fn i => sub (ia2, i, c))
518 end;
519
520 (* val copy : {src : 'a immarray2, si : int, sj : int,
521 * ilen : int option, jlen : int option,
522 * dst : 'a immarray2, di : int, dj : int};
523 * This function copies an immarray2 slice from src int dst starting
524 * at the di,dj element.
525 *)
526 fun copy {src, si, sj, ilen, jlen, dst=IA2 ia2, di, dj}
527 = let
528 val nilen = case ilen
529 of NONE => SOME ((nRows src) - si)
530 | SOME n => SOME n;
531 in
532 IA2 (ImmArray.modifyi (fn (r, ia)
533 => ImmArray.copy {src=row (src, si+r-di),
534 si=sj, len=jlen,
535 dst=ia, di=dj})
536 (ia2, di, nilen))
537 end;
538
539 (* val appi : traversal -> ('a * int * int -> unit) -> 'a immarray2
540 * -> unit
541 * val app : traversal -> ('a -> unit) -> 'a immarray2 -> unit
542 * These functions apply a function to every element
543 * of an immarray2. The appi function also provides the
544 * indices of the element as an argument to the applied function
545 * and uses an immarray2 slice argument.
546 *)
547 fun appi RowMajor f (IA2 ia2, i, j, rlen, clen)
548 = ImmArray.appi (fn (r,ia) => ImmArray.appi (fn (c,x) => f(r,c,x))
549 (ia, j, clen))
550 (ia2, i, rlen)
551 | appi ColMajor f (ia2, i, j, rlen, clen)
552 = appi RowMajor (fn (c,r,x) => f(r,c,x)) (turn ia2, j, i, clen, rlen);
553 fun app tr f (IA2 ia2) = appi tr (f o #3) (IA2 ia2, 0, 0, NONE, NONE);
554
555 (* val foldli : traversal -> ((int * int * 'a * 'b) -> 'b) -> 'b
556 * -> ('a immarray2 * int * int * int option * int option)
557 * -> 'b
558 * val foldri : traversal -> ((int * int * 'a * 'b) -> 'b) -> 'b
559 * -> ('a immarray2 * int * int * int option * int option)
560 * -> 'b
561 * val foldl : traversal -> ('a * 'b -> 'b) -> 'b -> 'a immarray2 -> 'b
562 * val foldr : traversal -> ('a * 'b -> 'b) -> 'b -> 'a immarray2 -> 'b
563 * These functions fold a function over every element
564 * of an immarray2. The foldri and foldli functions also provide
565 * the index of the element as an argument to the folded function
566 * and uses an immarray2 slice argument.
567 *)
568 fun foldli RowMajor f b (IA2 ia2, i, j, rlen, clen)
569 = ImmArray.foldli (fn (r,ia,b)
570 => ImmArray.foldli (fn (c,x,b) => f(r,c,x,b))
571 b
572 (ia, j, clen))
573 b
574 (ia2, i, rlen)
575 | foldli ColMajor f b (ia2, i, j, rlen, clen)
576 = foldli RowMajor (fn (c,r,x,b) => f(r,c,x,b)) b
577 (turn ia2, j, i, clen, rlen);
578 fun foldri RowMajor f b (IA2 ia2, i, j, rlen, clen)
579 = ImmArray.foldri (fn (r,ia,b)
580 => ImmArray.foldri (fn (c,x,b) => f(r,c,x,b))
581 b
582 (ia, j, clen))
583 b
584 (ia2, i, rlen)
585 | foldri ColMajor f b (ia2, i, j, rlen, clen)
586 = foldri RowMajor (fn (c,r,x,b) => f(r,c,x,b)) b
587 (turn ia2, j, i, clen, rlen);
588 fun foldl tr f b (IA2 ia2)
589 = foldli tr (fn (_,_,x,b) => f(x,b)) b (IA2 ia2, 0, 0, NONE, NONE);
590 fun foldr tr f b (IA2 ia2)
591 = foldri tr (fn (_,_,x,b) => f(x,b)) b (IA2 ia2, 0, 0, NONE, NONE);
592
593 (* val mapi : traversal -> ('a * int * int -> 'b) -> 'a immarray2
594 * -> 'b immarray2
595 * val map : traversal -> ('a -> 'b) -> 'a immarray2 -> 'b immarray2
596 * These functions map a function over every element
597 * of an immarray2. The mapi function also provides the
598 * indices of the element as an argument to the mapped function
599 * and uses an immarray2 slice argument. Although there are
600 * similarities between mapi and modifyi, note that when mapi is
601 * used with an immarray2 slice, the resulting immarray2 is the
602 * same size as the slice. This is necessary to preserve the
603 * type of the resulting immarray2. Thus, mapi with the identity
604 * function reduces to the extract function.
605 *)
606 fun mapi RowMajor f (IA2 ia2, i, j, rlen, clen)
607 = IA2 (ImmArray.mapi (fn (r,ia) => ImmArray.mapi (fn (c,x) => f(r,c,x))
608 (ia, j, clen))
609 (ia2, i, rlen))
610 | mapi ColMajor f (ia2, i, j, rlen, clen)
611 = turn (mapi RowMajor (fn (c,r,x) => f(r,c,x))
612 (turn ia2, j, i, clen, rlen))
613 fun map tr f (IA2 ia2)
614 = mapi tr (f o #3) (IA2 ia2, 0, 0, NONE, NONE);
615
616 (* val modifyi : traversal -> (int * int* 'a -> 'a)
617 -> ('a immarray2 * int * int * int option * int option)
618 * -> 'a immarray2
619 * val modify : traversal -> ('a -> 'a) -> 'a immarray2 -> 'a immarray2
620 * These functions apply a function to every element of an immarray2
621 * in row by column order and returns a new immarray2 where corresponding
622 * elements are replaced by their modified values. The modifyi
623 * function also provides the index of the element as an argument
624 * to the mapped function and uses an immarray2 slice argument.
625 *)
626 fun modifyi RowMajor f (IA2 ia2, i, j, rlen, clen)
627 = IA2 (ImmArray.modifyi (fn (r,ia) => ImmArray.modifyi (fn (c,x)
628 => f(r,c,x))
629 (ia, j, clen))
630 (ia2, i, rlen))
631 | modifyi ColMajor f (ia2, i, j, rlen, clen)
632 = turn (modifyi RowMajor (fn (c,r,x) => f(r,c,x))
633 (turn ia2, j, i, clen, rlen));
634 fun modify tr f (IA2 ia2)
635 = modifyi tr (f o #3) (IA2 ia2, 0, 0, NONE, NONE);
636
637 end;
638
639(* ************************************************************************* *)
640
641(*
642 * RegisterFile.sig
643 *
644 * This defines the exported datatype and functions provided by the
645 * register file. The datatype registerfile provides the encapsulation
646 * of the register file, InitRegisterFile initializes the registerfile,
647 * setting all registers to zero and setting r0, gp, sp, and fp to
648 * their appropriate values, LoadRegister takes a registerfile and
649 * an integer corresponding to the register, and returns the
650 * Word32.word value at that register, and StoreRegister takes a
651 * registerfile, an integer corresponding to the register, and a
652 * Word32.word and returns the registerfile updated with the word
653 * stored in the appropriate register.
654 *)
655
656signature REGISTERFILE
657 = sig
658
659 type registerfile;
660
661 val InitRegisterFile : unit -> registerfile;
662
663 val LoadRegister : registerfile * int -> Word32.word;
664
665 val StoreRegister : registerfile * int * Word32.word -> registerfile;
666
667 end;
668
669(*****************************************************************************)
670
671(*
672 * RegisterFile.sml
673 *
674 * This defines the RegisterFile structure, which provides the
675 * functionality of the register file. The datatype registerfile
676 * provides the encapsulation of the register file, InitRegisterFile
677 * initializes the registerfile, setting all registers to zero and
678 * setting r0, gp, sp, and fp to their appropriate values,
679 * LoadRegister takes a registerfile and an integer corresponding to
680 * the register, and returns the Word32.word value at that register,
681 * and StoreRegister takes a registerfile, an integer corresponding to
682 * the register, and a Word32.word and returns the registerfile
683 * updated with the word stored in the appropriate register.
684 *
685 * The underlying structure of registerfile is an immutable array of
686 * Word32.word.
687 *)
688
689structure RegisterFile : REGISTERFILE
690 = struct
691
692 type registerfile = Word32.word ImmArray.immarray;
693
694 fun InitRegisterFile ()
695 = ImmArray.update
696 (ImmArray.update
697 (ImmArray.update
698 (ImmArray.update
699 (ImmArray.immarray(32, 0wx00000000 : Word32.word),
700 00, 0wx00000000 : Word32.word),
701 28, 0wx00000000 : Word32.word),
702 29, 0wx00040000 : Word32.word),
703 30, 0wx00040000 : Word32.word) : registerfile;
704
705 fun LoadRegister (rf, reg) = ImmArray.sub(rf, reg);
706
707 fun StoreRegister (rf, reg, data) = ImmArray.update(rf, reg, data);
708
709 end;
710
711
712(*****************************************************************************)
713
714(*
715 * ALU.sig
716 *
717 * This defines the exported datatype and function provided by the
718 * ALU. The datatype ALUOp provides a means to specify which
719 * operation is to be performed by the ALU, and PerformAL performs
720 * one of the operations on two thirty-two bit words, returning the
721 * result as a thirty-two bit word.
722 *)
723
724signature ALU
725 = sig
726
727 datatype ALUOp = SLL | SRL | SRA |
728 ADD | ADDU |
729 SUB | SUBU |
730 AND | OR | XOR |
731 SEQ | SNE |
732 SLT | SGT |
733 SLE | SGE;
734
735 val PerformAL : (ALUOp * Word32.word * Word32.word) -> Word32.word;
736
737 end;
738
739(*****************************************************************************)
740
741(*
742 * ALU.sml
743 *
744 * This defines the ALU structure, which provides the functionality of
745 * an Arithmetic/Logic Unit. The datatype ALUOp provides a means to
746 * specify which operation is to be performed by the ALU, and
747 * PerformAL performs one of the operations on two thirty-two bit
748 * words, returning the result as a thirty-two bit word.
749 *
750 * A note about SML'97 Basis Library implementation of thirty-two bit
751 * numbers: the Word32.word is an unsigned thirty-two bit integer,
752 * while Int.int (equivalent to Int.int) is a signed thirty-two
753 * bit integer. In order to perform the signed operations, it is
754 * necessary to convert the words to signed form, using the
755 * Word32.toIntX function, which performs sign extension,
756 * and to convert the result back into unsigned form using the
757 * Word32.fromInt function. In addition, to perform a shift,
758 * the second Word32.word needs to be "downsized" to a normal
759 * Word.word using the Word.fromWord function.
760 *)
761
762structure ALU : ALU
763 = struct
764
765 datatype ALUOp = SLL | SRL | SRA |
766 ADD | ADDU |
767 SUB | SUBU |
768 AND | OR | XOR |
769 SEQ | SNE |
770 SLT | SGT |
771 SLE | SGE;
772
773 fun PerformAL (opcode, s1, s2) =
774 (case opcode
775 of SLL =>
776 Word32.<< (s1, Word.fromLarge (Word32.toLarge s2))
777 | SRL =>
778 Word32.>> (s1, Word.fromLarge (Word32.toLarge s2))
779 | SRA =>
780 Word32.~>> (s1, Word.fromLarge (Word32.toLarge s2))
781 | ADD =>
782 Word32.fromInt (Int.+ (Word32.toIntX s1,
783 Word32.toIntX s2))
784 | ADDU =>
785 Word32.+ (s1, s2)
786 | SUB =>
787 Word32.fromInt (Int.- (Word32.toIntX s1,
788 Word32.toIntX s2))
789 | SUBU =>
790 Word32.- (s1, s2)
791 | AND =>
792 Word32.andb (s1, s2)
793 | OR =>
794 Word32.orb (s1, s2)
795 | XOR =>
796 Word32.xorb (s1, s2)
797 | SEQ =>
798 if (s1 = s2)
799 then 0wx00000001 : Word32.word
800 else 0wx00000000 : Word32.word
801 | SNE =>
802 if not (s1 = s2)
803 then 0wx00000001 : Word32.word
804 else 0wx00000000 : Word32.word
805 | SLT =>
806 if Int.< (Word32.toIntX s1, Word32.toIntX s2)
807 then 0wx00000001 : Word32.word
808 else 0wx00000000 : Word32.word
809 | SGT =>
810 if Int.> (Word32.toIntX s1, Word32.toIntX s2)
811 then 0wx00000001 : Word32.word
812 else 0wx00000000 : Word32.word
813 | SLE =>
814 if Int.<= (Word32.toIntX s1, Word32.toIntX s2)
815 then 0wx00000001 : Word32.word
816 else 0wx00000000 : Word32.word
817 | SGE =>
818 if Int.>= (Word32.toIntX s1, Word32.toIntX s2)
819 then 0wx00000001 : Word32.word
820 else 0wx00000000 : Word32.word)
821 (*
822 * This handle will handle all ALU errors, most
823 * notably overflow and division by zero, and will
824 * print an error message and return 0.
825 *)
826 handle _ =>
827 (print "Error : ALU returning 0\n";
828 0wx00000000 : Word32.word);
829
830 end;
831
832(*****************************************************************************)
833
834(*
835 * Memory.sig
836 *
837 * This defines the exported datatype and functions provided by
838 * memory. The datatype memory provides the encapsulation
839 * of memory, InitMemory initializes memory, setting all
840 * addresses to zero, LoadWord takes memory and
841 * a Word32.word corresponding to the address, and returns the
842 * Word32.word value at that address, StoreWord takes memory,
843 * a Word32.word corresponding to the address, and a
844 * Word32.word and returns memory updated with the word
845 * stored at the appropriate address. LoadHWord, LoadHWordU,
846 * LoadByte, and LoadByteU load halfwords, unsigned halfwords,
847 * bytes, and unsigned bytes respectively from memory into the
848 * lower portion of the returned Word32.word. StoreHWord and
849 * StoreByte store halfwords and bytes taken from the lower portion
850 * of the Word32.word into memory.
851 * GetStatistics takes memory and returns the read and write
852 * statistics as a string.
853 *)
854
855signature MEMORY
856 = sig
857
858 type memory;
859
860 val InitMemory : unit -> memory;
861
862 val LoadWord : memory * Word32.word -> memory * Word32.word;
863 val StoreWord : memory * Word32.word * Word32.word -> memory;
864
865 val LoadHWord : memory * Word32.word -> memory * Word32.word;
866 val LoadHWordU : memory * Word32.word -> memory * Word32.word;
867 val StoreHWord : memory * Word32.word * Word32.word -> memory;
868
869 val LoadByte : memory * Word32.word -> memory * Word32.word;
870 val LoadByteU : memory * Word32.word -> memory * Word32.word;
871 val StoreByte : memory * Word32.word * Word32.word -> memory;
872
873 val GetStatistics : memory -> string;
874
875 end;
876
877
878
879
880
881(*****************************************************************************)
882
883(*
884 * Memory.sml
885 *
886 * This defines the Memory structure, which provides the functionality
887 * of memory. The datatype memory provides the encapsulation of
888 * memory, InitMemory initializes memory, setting all
889 * addresses to zero, LoadWord takes memory and
890 * a Word32.word corresponding to the address, and returns the
891 * Word32.word value at that address and the updated memory,
892 * StoreWord takes memory, a Word32.word corresponding to the
893 * address, and a Word32.word and returns memory updated with the word
894 * stored at the appropriate address. LoadHWord, LoadHWordU,
895 * LoadByte, and LoadByteU load halfwords, unsigned halfwords,
896 * bytes, and unsigned bytes respectively from memory into the
897 * lower portion of the returned Word32.word. StoreHWord and
898 * StoreByte store halfwords and bytes taken from the lower portion
899 * of the Word32.word into memory.
900 * GetStatistics takes memory and returns the read and write
901 * statistics as a string.
902 *
903 * The underlying structure of memory is an immutable array of Word32.word.
904 * The array has a length of 0x10000, since every element of the array
905 * corresponds to a thirty-two bit integer.
906 *
907 * Also, the functions AlignWAddress and AlignHWAddress aligns a memory
908 * address to a word and halfword address, respectively. If LoadWord,
909 * StoreWord, LoadHWord, LoadHWordU, or StoreHWord is asked to access an
910 * unaligned address, it writes an error message, and uses the address
911 * rounded down to the aligned address.
912 *)
913
914structure Memory : MEMORY
915 = struct
916
917 type memory = Word32.word ImmArray.immarray * (int * int);
918
919 fun InitMemory () =
920 (ImmArray.immarray(Word32.toInt(0wx10000 : Word32.word),
921 0wx00000000 : Word32.word),
922 (0, 0)) : memory;
923
924 fun AlignWAddress address
925 = Word32.<< (Word32.>> (address, 0wx0002), 0wx0002);
926
927 fun AlignHWAddress address
928 = Word32.<< (Word32.>> (address, 0wx0001), 0wx0001);
929
930 (* Load and Store provide errorless access to memory.
931 * They provide a common interface to memory, while
932 * the LoadX and StoreX specifically access words,
933 * halfwords and bytes, requiring address to be aligned.
934 * In Load and Store, two intermediate values are
935 * generated. The value aligned_address is the aligned
936 * version of the given address, and is used to compare with
937 * the original address to determine if it was aligned. The
938 * value use_address is equivalent to aligned_address divided
939 * by four, and it corresponds to the index of the memory
940 * array where the corresponding aligned address can be found.
941 *)
942
943 fun Load ((mem, (reads, writes)), address)
944 = let
945 val aligned_address = AlignWAddress address;
946 val use_address = Word32.>> (aligned_address, 0wx0002);
947 in
948 ((mem, (reads + 1, writes)),
949 ImmArray.sub(mem, Word32.toInt(use_address)))
950 end;
951
952 fun Store ((mem, (reads, writes)), address, data)
953 = let
954 val aligned_address = AlignWAddress address;
955 val use_address = Word32.>> (aligned_address, 0wx0002);
956 in
957 (ImmArray.update(mem, Word32.toInt(use_address), data),
958 (reads, writes + 1))
959 end;
960
961
962 fun LoadWord (mem, address)
963 = let
964 val aligned_address
965 = if address = AlignWAddress address
966 then address
967 else (print "Error LW: Memory using aligned address\n";
968 AlignWAddress address);
969 in
970 Load(mem, aligned_address)
971 end;
972
973 fun StoreWord (mem, address, data)
974 = let
975 val aligned_address
976 = if address = AlignWAddress address
977 then address
978 else (print "Error SW: Memory using aligned address\n";
979 AlignWAddress address);
980 in
981 Store(mem, aligned_address, data)
982 end;
983
984 fun LoadHWord (mem, address)
985 = let
986 val aligned_address
987 = if address = AlignHWAddress address
988 then address
989 else (print "Error LH: Memory using aligned address\n";
990 AlignHWAddress address);
991 val (nmem,l_word) = Load(mem, aligned_address);
992 in
993 (nmem,
994 case aligned_address
995 of 0wx00000000 : Word32.word
996 => Word32.~>>(Word32.<<(l_word, 0wx0010),
997 0wx0010)
998 | 0wx00000010 : Word32.word
999 => Word32.~>>(Word32.<<(l_word, 0wx0000),
1000 0wx0010)
1001 | _ => (print "Error LH: Memory returning 0\n";
1002 0wx00000000 : Word32.word))
1003 end;
1004
1005 fun LoadHWordU (mem, address)
1006 = let
1007 val aligned_address
1008 = if address = AlignHWAddress address
1009 then address
1010 else (print "Error LHU: Memory using aligned address\n";
1011 AlignHWAddress address);
1012 val (nmem, l_word) = Load(mem, aligned_address);
1013 in
1014 (nmem,
1015 case aligned_address
1016 of 0wx00000000 : Word32.word
1017 => Word32.>>(Word32.<<(l_word, 0wx0010),
1018 0wx0010)
1019 | 0wx00000010 : Word32.word
1020 => Word32.>>(Word32.<<(l_word, 0wx0000),
1021 0wx0010)
1022 | _ => (print "Error LHU: Memory returning 0\n";
1023 0wx00000000 : Word32.word))
1024 end;
1025
1026 fun StoreHWord (mem, address, data)
1027 = let
1028 val aligned_address
1029 = if address = AlignHWAddress address
1030 then address
1031 else (print "Error SH: Memory using aligned address\n";
1032 AlignWAddress address);
1033 val (_, s_word) = Load(mem, aligned_address);
1034 in
1035 case aligned_address
1036 of 0wx00000000 : Word32.word
1037 => Store(mem, aligned_address,
1038 Word32.orb(Word32.andb(0wxFFFF0000 : Word32.word,
1039 s_word),
1040 Word32.<<(Word32.andb(0wx0000FFFF :
1041 Word32.word,
1042 data),
1043 0wx0000)))
1044 | 0wx00000010 : Word32.word
1045 => Store(mem, aligned_address,
1046 Word32.orb(Word32.andb(0wx0000FFFF : Word32.word,
1047 s_word),
1048 Word32.<<(Word32.andb(0wx0000FFFF :
1049 Word32.word,
1050 data),
1051 0wx0010)))
1052 | _ => (print "Error SH: Memory unchanged\n";
1053 mem)
1054 end;
1055
1056 fun LoadByte (mem, address)
1057 = let
1058 val aligned_address = address;
1059 val (nmem, l_word) = Load(mem, aligned_address);
1060 in
1061 (nmem,
1062 case aligned_address
1063 of 0wx00000000 : Word32.word
1064 => Word32.~>>(Word32.<<(l_word,
1065 0wx0018),
1066 0wx0018)
1067 | 0wx00000008 : Word32.word
1068 => Word32.~>>(Word32.<<(l_word,
1069 0wx0010),
1070 0wx0018)
1071 | 0wx00000010 : Word32.word
1072 => Word32.~>>(Word32.<<(l_word,
1073 0wx0008),
1074 0wx0018)
1075 | 0wx00000018 : Word32.word
1076 => Word32.~>>(Word32.<<(l_word,
1077 0wx0000),
1078 0wx0018)
1079 | _ => (print "Error LB: Memory returning 0\n";
1080 0wx00000000 : Word32.word))
1081 end;
1082
1083 fun LoadByteU (mem, address)
1084 = let
1085 val aligned_address = address;
1086 val (nmem, l_word) = Load(mem, aligned_address);
1087 in
1088 (nmem,
1089 case aligned_address
1090 of 0wx00000000 : Word32.word
1091 => Word32.>>(Word32.<<(l_word,
1092 0wx0018),
1093 0wx0018)
1094 | 0wx00000008 : Word32.word
1095 => Word32.>>(Word32.<<(l_word,
1096 0wx0010),
1097 0wx0018)
1098 | 0wx00000010 : Word32.word
1099 => Word32.>>(Word32.<<(l_word,
1100 0wx0008),
1101 0wx0018)
1102 | 0wx00000018 : Word32.word
1103 => Word32.>>(Word32.<<(l_word,
1104 0wx0000),
1105 0wx0018)
1106 | _ => (print "Error LBU: Memory returning 0\n";
1107 0wx00000000 : Word32.word))
1108 end;
1109
1110 fun StoreByte (mem, address, data)
1111 = let
1112 val aligned_address = address;
1113 val (_, s_word) = Load(mem, aligned_address);
1114 in
1115 case aligned_address
1116 of 0wx00000000 : Word32.word
1117 => Store(mem, aligned_address,
1118 Word32.orb(Word32.andb(0wxFFFFFF00 : Word32.word,
1119 s_word),
1120 Word32.<<(Word32.andb(0wx000000FF :
1121 Word32.word,
1122 data),
1123 0wx0000)))
1124 | 0wx00000008 : Word32.word
1125 => Store(mem, aligned_address,
1126 Word32.orb(Word32.andb(0wxFFFF00FF : Word32.word,
1127 s_word),
1128 Word32.<<(Word32.andb(0wx000000FF :
1129 Word32.word,
1130 data),
1131 0wx0008)))
1132 | 0wx00000010 : Word32.word
1133 => Store(mem, aligned_address,
1134 Word32.orb(Word32.andb(0wxFF00FFFF : Word32.word,
1135 s_word),
1136 Word32.<<(Word32.andb(0wx000000FF :
1137 Word32.word,
1138 data),
1139 0wx0010)))
1140 | 0wx00000018 : Word32.word
1141 => Store(mem, aligned_address,
1142 Word32.orb(Word32.andb(0wx00FFFFFF : Word32.word,
1143 s_word),
1144 Word32.<<(Word32.andb(0wx000000FF :
1145 Word32.word,
1146 data),
1147 0wx0018)))
1148 | _ => (print "Error SB: Memory unchanged\n";
1149 mem)
1150 end;
1151
1152 fun GetStatistics (mem, (reads, writes))
1153 = "Memory :\n" ^
1154 "Memory Reads : " ^ (Int.toString reads) ^ "\n" ^
1155 "Memory Writes : " ^ (Int.toString writes) ^ "\n";
1156
1157 end;
1158
1159(*****************************************************************************)
1160
1161(*
1162 * CacheSpec.sig
1163 *
1164 * This defines the signature that outlines the specifications to
1165 * describe a cache. The two datatypes are given to provide clear
1166 * means of differentiating between the write hit and write miss
1167 * options. CacheName can be any string describing the cache.
1168 * CacheSize is an integer that represents the total number of words
1169 * in the cache. BlockSize is an integer that represents the total
1170 * number of words in a block. Associativity is an integer that
1171 * represents the associativity of the cache. WriteHit and WriteMiss
1172 * represent the write hit and write miss options to be implemented by
1173 * this cache.
1174 *)
1175
1176signature CACHESPEC
1177 = sig
1178
1179 datatype WriteHitOption = Write_Through
1180 | Write_Back;
1181
1182 datatype WriteMissOption = Write_Allocate
1183 | Write_No_Allocate;
1184
1185 val CacheName : string;
1186 val CacheSize : int;
1187 val BlockSize : int;
1188 val Associativity : int;
1189 val WriteHit : WriteHitOption;
1190 val WriteMiss : WriteMissOption;
1191
1192 end;
1193
1194(*****************************************************************************)
1195
1196(*
1197 * CachedMemory.sml
1198 *
1199 * This defines the CachedMemory functor, which provides the
1200 * functionality of a cached memory and which takes two structures,
1201 * corresponding to the cache specification and the the level of
1202 * memory which the cache will be caching. The datatype memory
1203 * provides the encapsulation of the cache along with the memory
1204 * system that is being cached, InitMemory initializes the cache and
1205 * the memory system that is being cached, LoadWord takes memory and a
1206 * Word32.word corresponding to the address, and returns the
1207 * Word32.word at that address and the updated cache and memory,
1208 * StoreWord takes memory, a Word32.word corresponding to the address,
1209 * and a Word32.word and returns the cache and memory updated with the
1210 * stored at the appropriate address. LoadHWord, LoadHWordU,
1211 * LoadByte, and LoadByteU load halfwords, unsigned halfwords,
1212 * bytes, and unsigned bytes respectively from memory into the
1213 * lower portion of the returned Word32.word. StoreHWord and
1214 * StoreByte store halfwords and bytes taken from the lower portion
1215 * of the Word32.word into memory.
1216 * GetStatistics takes memory and returns the read and write
1217 * statistics as a string.
1218 *
1219 * The underlying structure of cache is a two dimensional array of
1220 * cache lines, where a cache line consists of a valid bit, dirty bit,
1221 * a tag and a block of words, as a Word32.word array.
1222 * The size of the cache, the associativity, and the block size are
1223 * specified by the cache specification.
1224 *
1225 * Also, the functions AlignWAddress and AlignHWAddress aligns a memory
1226 * address to a word and halfword address, respectively. If LoadWord,
1227 * StoreWord, LoadHWord, LoadHWordU, or StoreHWord is asked to access an
1228 * unaligned address, it writes an error message, and uses the address
1229 * rounded down to the aligned address.
1230 *)
1231
1232functor CachedMemory (structure CS : CACHESPEC;
1233 structure MEM : MEMORY;) : MEMORY
1234 = struct
1235
1236 type cacheline
1237 = bool * bool * Word32.word * Word32.word ImmArray.immarray;
1238
1239 type cacheset
1240 = cacheline ImmArray.immarray;
1241
1242 type cache
1243 = cacheset ImmArray.immarray;
1244
1245 type memory = (cache * (int * int * int * int)) * MEM.memory;
1246
1247
1248 (* Performs log[base2] on an integer. *)
1249 fun exp2 0 = 1
1250 | exp2 n = 2 * (exp2 (n-1))
1251 fun log2 x = let
1252 fun log2_aux n = if exp2 n > x
1253 then (n-1)
1254 else log2_aux (n+1)
1255 in
1256 log2_aux 0
1257 end
1258
1259 open CS;
1260
1261 (*
1262 * The following values of index size and field bits are
1263 * calculated from the values in the cache specification
1264 * structure.
1265 *)
1266 val IndexSize = CacheSize div (BlockSize * Associativity);
1267 val BlockOffsetBits = log2 (BlockSize * 4);
1268 val IndexBits = log2 IndexSize;
1269 val TagBits = 32 - BlockOffsetBits - IndexBits;
1270
1271
1272 (*
1273 * RandEntry returns a random number between
1274 * [0, Associativity - 1]. It is used to determine
1275 * replacement of data in the cache.
1276 *)
1277 val RandEntry = let
1278 val modulus = Word.fromInt(Associativity - 1)
1279 in
1280 fn () => Word.toInt(Word.mod(rand (),
1281 modulus))
1282 end
1283
1284 (*
1285 * The InitCache function initializes the cache to
1286 * not-valid, not-dirty, 0wx00000000 tag, blocks initialized
1287 * to 0wx00000000.
1288 *)
1289 fun InitCache ()
1290 = let
1291 val cacheline = (false, false, 0wx00000000 : Word32.word,
1292 ImmArray.immarray (BlockSize,
1293 0wx00000000 : Word32.word));
1294 val cacheset = ImmArray.immarray (Associativity, cacheline);
1295 in
1296 (ImmArray.immarray (IndexSize, cacheset),
1297 (0, 0, 0, 0))
1298 end;
1299
1300
1301 (*
1302 * The InitMemory function initializes the cache
1303 * and the memory being cached.
1304 *)
1305 fun InitMemory () = (InitCache (), MEM.InitMemory ()) : memory;
1306
1307
1308 (*
1309 * GetTag returns the Word32.word corresponding to the tag field of
1310 * address
1311 *)
1312 fun GetTag address
1313 = Word32.>> (address,
1314 Word.fromInt (IndexBits + BlockOffsetBits));
1315
1316
1317 (*
1318 * GetIndex returns the Word32.word corresponding to the index
1319 * field of address.
1320 *)
1321 fun GetIndex address
1322 = let
1323 val mask
1324 = Word32.notb
1325 (Word32.<<
1326 (Word32.>> (0wxFFFFFFFF : Word32.word,
1327 Word.fromInt (IndexBits + BlockOffsetBits)),
1328 Word.fromInt (IndexBits + BlockOffsetBits)));
1329 in
1330 Word32.>> (Word32.andb (address, mask),
1331 Word.fromInt (BlockOffsetBits))
1332 end;
1333
1334
1335 (*
1336 * GetBlockOffset returns the Word32.word corresponding to the
1337 * block offset field of address.
1338 *)
1339 fun GetBlockOffset address
1340 = let
1341 val mask
1342 = Word32.notb
1343 (Word32.<<
1344 (Word32.>> (0wxFFFFFFFF : Word32.word,
1345 Word.fromInt BlockOffsetBits),
1346 Word.fromInt BlockOffsetBits));
1347 in
1348 Word32.andb (address, mask)
1349 end;
1350
1351
1352 (*
1353 * The InCache* family of functions returns a boolean value
1354 * that determines if the word specified by address is in the
1355 * cache at the current time (and that the data is valid).
1356 *)
1357 fun InCache_aux_entry ((valid, dirty, tag, block), address)
1358 = tag = (GetTag address) andalso valid;
1359
1360 fun InCache_aux_set (set, address)
1361 = ImmArray.foldr (fn (entry, result) =>
1362 (InCache_aux_entry (entry, address)) orelse
1363 result)
1364 false
1365 set;
1366
1367 fun InCache (cac, address)
1368 = InCache_aux_set (ImmArray.sub (cac,
1369 Word32.toInt (GetIndex address)),
1370 address);
1371
1372 (*
1373 * The ReadCache* family of functions returns the Word32.word
1374 * stored at address in the cache.
1375 *)
1376 fun ReadCache_aux_entry ((valid, dirty, tag, block), address)
1377 = ImmArray.sub (block,
1378 Word32.toInt (Word32.>> (GetBlockOffset address,
1379 0wx0002)));
1380
1381 fun ReadCache_aux_set (set, address)
1382 = ImmArray.foldr (fn (entry, result) =>
1383 if InCache_aux_entry (entry, address)
1384 then ReadCache_aux_entry (entry, address)
1385 else result)
1386 (0wx00000000 : Word32.word)
1387 set;
1388
1389 fun ReadCache (cac, address)
1390 = ReadCache_aux_set (ImmArray.sub (cac,
1391 Word32.toInt(GetIndex address)),
1392 address);
1393
1394
1395 (*
1396 * The WriteCache* family of functions returns the updated
1397 * cache with data stored at address.
1398 *)
1399 fun WriteCache_aux_entry ((valid, dirty, tag, block), address, data)
1400 = let
1401 val ndirty = case WriteHit
1402 of Write_Through => false
1403 | Write_Back => true;
1404 in
1405 (true, ndirty, tag,
1406 ImmArray.update (block,
1407 Word32.toInt (Word32.>>
1408 (GetBlockOffset address,
1409 0wx0002)),
1410 data))
1411 end;
1412
1413 fun WriteCache_aux_set (set, address, data)
1414 = ImmArray.map (fn entry =>
1415 if InCache_aux_entry (entry, address)
1416 then WriteCache_aux_entry (entry, address,
1417 data)
1418 else entry)
1419 set;
1420
1421 fun WriteCache (cac, address, data)
1422 = let
1423 val index = Word32.toInt (GetIndex address);
1424 val nset = WriteCache_aux_set (ImmArray.sub (cac, index),
1425 address, data);
1426 in
1427 ImmArray.update (cac, index, nset)
1428 end;
1429
1430
1431 (*
1432 * The LoadBlock function returns the updated
1433 * memory and the block containing address loaded from memory.
1434 *)
1435 fun LoadBlock (mem, address)
1436 = ImmArray.foldr (fn (offset, (block, mem)) =>
1437 let
1438 val laddress
1439 = Word32.+ (Word32.<<
1440 (Word32.>>
1441 (address,
1442 Word.fromInt
1443 BlockOffsetBits),
1444 Word.fromInt
1445 BlockOffsetBits),
1446 Word32.<< (Word32.fromInt
1447 offset,
1448 0wx0002));
1449 val (nmem, nword) = MEM.LoadWord (mem,
1450 laddress);
1451 in
1452 (ImmArray.update (block, offset, nword), nmem)
1453 end)
1454 (ImmArray.immarray (BlockSize,
1455 0wx00000000 : Word32.word), mem)
1456 (ImmArray.tabulate (BlockSize, fn i => i));
1457
1458
1459 (*
1460 * The StoreBlock functionsreturns the updated
1461 * memory with block stored into the block containing address.
1462 *)
1463 fun StoreBlock (block, mem, address)
1464 = ImmArray.foldr (fn (offset, mem) =>
1465 let
1466 val saddress
1467 = Word32.+ (Word32.<<
1468 (Word32.>>
1469 (address,
1470 Word.fromInt
1471 BlockOffsetBits),
1472 Word.fromInt
1473 BlockOffsetBits),
1474 Word32.<< (Word32.fromInt
1475 offset,
1476 0wx0002));
1477 in
1478 MEM.StoreWord (mem, saddress,
1479 ImmArray.sub (block, offset))
1480 end)
1481 mem
1482 (ImmArray.tabulate (BlockSize, fn i => i));
1483
1484
1485 (*
1486 * The LoadCache* family of functions returns the updated
1487 * cache and memory, with the block containing address loaded
1488 * into the cache at the appropriate cache line, and dirty
1489 * data written back to memory as needed.
1490 *)
1491 fun LoadCache_aux_entry ((valid, dirty, tag, block), mem, address)
1492 = let
1493 val saddress
1494 = Word32.orb (Word32.<< (tag,
1495 Word.fromInt TagBits),
1496 Word32.<< (GetIndex address,
1497 Word.fromInt IndexBits));
1498 val nmem = if valid andalso dirty
1499 then StoreBlock (block, mem, saddress)
1500 else mem;
1501 val (nblock, nnmem) = LoadBlock (nmem, address);
1502 in
1503 ((true, false, GetTag address, nblock), nnmem)
1504 end;
1505
1506 fun LoadCache_aux_set (set, mem, address)
1507 = let
1508 val entry = RandEntry ();
1509 val (nentry, nmem) = LoadCache_aux_entry (ImmArray.sub (set,
1510 entry),
1511 mem, address);
1512 in
1513 (ImmArray.update (set, entry, nentry), nmem)
1514 end;
1515
1516 fun LoadCache (cac, mem, address)
1517 = let
1518 val index = Word32.toInt (GetIndex address);
1519 val (nset, nmem)
1520 = LoadCache_aux_set (ImmArray.sub (cac, index),
1521 mem, address);
1522 in
1523 (ImmArray.update (cac, index, nset), nmem)
1524 end;
1525
1526
1527 (*
1528 * The remainder of the function defined here satisfy the MEMORY
1529 * signature. This allows a CachedMemory to act exactly like
1530 * a normal Memory, and thus caches can be nested to an arbitrary
1531 * depth.
1532 *)
1533
1534 fun AlignWAddress address
1535 = Word32.<< (Word32.>> (address, 0wx0002), 0wx0002);
1536
1537 fun AlignHWAddress address
1538 = Word32.<< (Word32.>> (address, 0wx0001), 0wx0001);
1539
1540 (* Load and Store provide errorless access to memory.
1541 * They provide a common interface to memory, while
1542 * the LoadX and StoreX specifically access words,
1543 * halfwords and bytes, requiring address to be aligned.
1544 * In Load and Store, two intermediate values are
1545 * generated. The value aligned_address is the aligned
1546 * version of the given address, and is used to compare with
1547 * the original address to determine if it was aligned. The
1548 * value use_address is equivalent to aligned_address divided
1549 * by four, and it corresponds to the index of the memory
1550 * array where the corresponding aligned address can be found.
1551 *)
1552
1553 fun Load (((cac, (rh, rm, wh, wm)), mem), address)
1554 = let
1555 val aligned_address = AlignWAddress address;
1556 in
1557 if InCache (cac, aligned_address)
1558 then (((cac, (rh + 1, rm, wh, wm)), mem),
1559 ReadCache (cac, aligned_address))
1560 else let
1561 val (ncac, nmem)
1562 = LoadCache (cac, mem, aligned_address);
1563 in
1564 (((ncac, (rh, rm + 1, wh, wm)), nmem),
1565 ReadCache (ncac, aligned_address))
1566 end
1567 end;
1568
1569
1570 fun Store (((cac, (rh, rm, wh, wm)), mem), address, data)
1571 = let
1572 val aligned_address = AlignWAddress address;
1573 in
1574 if InCache (cac, aligned_address)
1575 then let
1576 val ncac = WriteCache (cac, aligned_address, data);
1577 in
1578 case WriteHit
1579 of Write_Through =>
1580 ((ncac, (rh, rm, wh + 1, wm)),
1581 MEM.StoreWord (mem, aligned_address, data))
1582 | Write_Back =>
1583 ((ncac, (rh, rm, wh + 1, wm)), mem)
1584 end
1585 else case WriteMiss
1586 of Write_Allocate =>
1587 let
1588 val (ncac, nmem)
1589 = LoadCache (cac, mem, aligned_address);
1590 val nncac
1591 = WriteCache (ncac, aligned_address, data);
1592 in
1593 case WriteHit
1594 of Write_Through =>
1595 ((nncac, (rh, rm, wh, wm + 1)),
1596 MEM.StoreWord (nmem, aligned_address,
1597 data))
1598 | Write_Back =>
1599 ((nncac, (rh, rm, wh, wm + 1)),
1600 nmem)
1601 end
1602 | Write_No_Allocate =>
1603 ((cac, (rh, rm, wh, wm + 1)),
1604 MEM.StoreWord (mem, aligned_address, data))
1605 end;
1606
1607 fun LoadWord (mem, address)
1608 = let
1609 val aligned_address
1610 = if address = AlignWAddress address
1611 then address
1612 else (print "Error LW: Memory using aligned address\n";
1613 AlignWAddress address);
1614 in
1615 Load(mem, aligned_address)
1616 end;
1617
1618 fun StoreWord (mem, address, data)
1619 = let
1620 val aligned_address
1621 = if address = AlignWAddress address
1622 then address
1623 else (print "Error SW: Memory using aligned address\n";
1624 AlignWAddress address);
1625 in
1626 Store(mem, aligned_address, data)
1627 end;
1628
1629 fun LoadHWord (mem, address)
1630 = let
1631 val aligned_address
1632 = if address = AlignHWAddress address
1633 then address
1634 else (print "Error LH: Memory using aligned address\n";
1635 AlignHWAddress address);
1636 val (nmem,l_word) = Load(mem, aligned_address);
1637 in
1638 (nmem,
1639 case aligned_address
1640 of 0wx00000000 : Word32.word
1641 => Word32.~>>(Word32.<<(l_word, 0wx0010),
1642 0wx0010)
1643 | 0wx00000010 : Word32.word
1644 => Word32.~>>(Word32.<<(l_word, 0wx0000),
1645 0wx0010)
1646 | _ => (print "Error LH: Memory returning 0\n";
1647 0wx00000000 : Word32.word))
1648 end;
1649
1650 fun LoadHWordU (mem, address)
1651 = let
1652 val aligned_address
1653 = if address = AlignHWAddress address
1654 then address
1655 else (print "Error LHU: Memory using aligned address\n";
1656 AlignHWAddress address);
1657 val (nmem, l_word) = Load(mem, aligned_address);
1658 in
1659 (nmem,
1660 case aligned_address
1661 of 0wx00000000 : Word32.word
1662 => Word32.>>(Word32.<<(l_word, 0wx0010),
1663 0wx0010)
1664 | 0wx00000010 : Word32.word
1665 => Word32.>>(Word32.<<(l_word, 0wx0000),
1666 0wx0010)
1667 | _ => (print "Error LHU: Memory returning 0\n";
1668 0wx00000000 : Word32.word))
1669 end;
1670
1671 fun StoreHWord (mem, address, data)
1672 = let
1673 val aligned_address
1674 = if address = AlignHWAddress address
1675 then address
1676 else (print "Error SH: Memory using aligned address\n";
1677 AlignWAddress address);
1678 val (_, s_word) = Load(mem, aligned_address);
1679 in
1680 case aligned_address
1681 of 0wx00000000 : Word32.word
1682 => Store(mem, aligned_address,
1683 Word32.orb(Word32.andb(0wxFFFF0000 : Word32.word,
1684 s_word),
1685 Word32.<<(Word32.andb(0wx0000FFFF :
1686 Word32.word,
1687 data),
1688 0wx0000)))
1689 | 0wx00000010 : Word32.word
1690 => Store(mem, aligned_address,
1691 Word32.orb(Word32.andb(0wx0000FFFF : Word32.word,
1692 s_word),
1693 Word32.<<(Word32.andb(0wx0000FFFF :
1694 Word32.word,
1695 data),
1696 0wx0010)))
1697 | _ => (print "Error SH: Memory unchanged\n";
1698 mem)
1699 end;
1700
1701 fun LoadByte (mem, address)
1702 = let
1703 val aligned_address = address;
1704 val (nmem, l_word) = Load(mem, aligned_address);
1705 in
1706 (nmem,
1707 case aligned_address
1708 of 0wx00000000 : Word32.word
1709 => Word32.~>>(Word32.<<(l_word,
1710 0wx0018),
1711 0wx0018)
1712 | 0wx00000008 : Word32.word
1713 => Word32.~>>(Word32.<<(l_word,
1714 0wx0010),
1715 0wx0018)
1716 | 0wx00000010 : Word32.word
1717 => Word32.~>>(Word32.<<(l_word,
1718 0wx0008),
1719 0wx0018)
1720 | 0wx00000018 : Word32.word
1721 => Word32.~>>(Word32.<<(l_word,
1722 0wx0000),
1723 0wx0018)
1724 | _ => (print "Error LB: Memory returning 0\n";
1725 0wx00000000 : Word32.word))
1726 end;
1727
1728 fun LoadByteU (mem, address)
1729 = let
1730 val aligned_address = address;
1731 val (nmem, l_word) = Load(mem, aligned_address);
1732 in
1733 (nmem,
1734 case aligned_address
1735 of 0wx00000000 : Word32.word
1736 => Word32.>>(Word32.<<(l_word,
1737 0wx0018),
1738 0wx0018)
1739 | 0wx00000008 : Word32.word
1740 => Word32.>>(Word32.<<(l_word,
1741 0wx0010),
1742 0wx0018)
1743 | 0wx00000010 : Word32.word
1744 => Word32.>>(Word32.<<(l_word,
1745 0wx0008),
1746 0wx0018)
1747 | 0wx00000018 : Word32.word
1748 => Word32.>>(Word32.<<(l_word,
1749 0wx0000),
1750 0wx0018)
1751 | _ => (print "Error LBU: Memory returning 0\n";
1752 0wx00000000 : Word32.word))
1753 end;
1754
1755 fun StoreByte (mem, address, data)
1756 = let
1757 val aligned_address = address;
1758 val (_, s_word) = Load(mem, aligned_address);
1759 in
1760 case aligned_address
1761 of 0wx00000000 : Word32.word
1762 => Store(mem, aligned_address,
1763 Word32.orb(Word32.andb(0wxFFFFFF00 : Word32.word,
1764 s_word),
1765 Word32.<<(Word32.andb(0wx000000FF :
1766 Word32.word,
1767 data),
1768 0wx0000)))
1769 | 0wx00000008 : Word32.word
1770 => Store(mem, aligned_address,
1771 Word32.orb(Word32.andb(0wxFFFF00FF : Word32.word,
1772 s_word),
1773 Word32.<<(Word32.andb(0wx000000FF :
1774 Word32.word,
1775 data),
1776 0wx0008)))
1777 | 0wx00000010 : Word32.word
1778 => Store(mem, aligned_address,
1779 Word32.orb(Word32.andb(0wxFF00FFFF : Word32.word,
1780 s_word),
1781 Word32.<<(Word32.andb(0wx000000FF :
1782 Word32.word,
1783 data),
1784 0wx0010)))
1785 | 0wx00000018 : Word32.word
1786 => Store(mem, aligned_address,
1787 Word32.orb(Word32.andb(0wx00FFFFFF : Word32.word,
1788 s_word),
1789 Word32.<<(Word32.andb(0wx000000FF :
1790 Word32.word,
1791 data),
1792 0wx0018)))
1793 | _ => (print "Error SB: Memory unchanged\n";
1794 mem)
1795 end;
1796
1797 fun GetStatistics ((cac, (rh, rm, wh, wm)), mem)
1798 = let
1799
1800 val th = rh + wh;
1801
1802 val tm = rm + wm;
1803
1804 val who = case WriteHit
1805 of Write_Through => "Write Through"
1806 | Write_Back => "Write Back";
1807
1808 val wmo = case WriteMiss
1809 of Write_Allocate => "Write Allocate"
1810 | Write_No_Allocate => "Write No Allocate";
1811
1812 in
1813 CacheName ^ " :\n" ^
1814 "CacheSize : " ^ (Int.toString CacheSize) ^ "\n" ^
1815 "BlockSize : " ^ (Int.toString BlockSize) ^ "\n" ^
1816 "Associativity : " ^ (Int.toString Associativity) ^ "\n" ^
1817 "Write Hit : " ^ who ^ "\n" ^
1818 "Write Miss : " ^ wmo ^ "\n" ^
1819 "Read hits : " ^ (Int.toString rh) ^ "\n" ^
1820 "Read misses : " ^ (Int.toString rm) ^ "\n" ^
1821 "Write hits : " ^ (Int.toString wh) ^ "\n" ^
1822 "Write misses : " ^ (Int.toString wm) ^ "\n" ^
1823 "Total hits : " ^ (Int.toString th) ^ "\n" ^
1824 "Total misses : " ^ (Int.toString tm) ^ "\n" ^
1825 (MEM.GetStatistics mem)
1826 end;
1827
1828 end;
1829
1830(*****************************************************************************)
1831
1832(*
1833 * DLXSimulator.sig
1834 *
1835 * This defines the exported function provided by the DLXSimulator.
1836 * The function run_file takes a string corresponding to the name of the
1837 * file to be run, and executes it. The function run_prog takes a
1838 * list of instructions and executes them.
1839 *)
1840
1841signature DLXSIMULATOR
1842 = sig
1843
1844 val run_file : string -> unit;
1845 val run_prog : string list -> unit;
1846
1847 end;
1848
1849(*****************************************************************************)
1850
1851(*
1852 * DLXSimulator.sml
1853 *
1854 * This defines the DLXSimulatorFun functor, which takes three
1855 * structures, corresponding to the register file, the ALU, and memory,
1856 * and provides the functionality of a DLX processor, able to execute
1857 * DLX programs. The function run_file takes a string corresponding to the
1858 * name of the file to be executed, and executes it. The function
1859 * run_prog takes a list of instructions and executes them.
1860 *)
1861
1862functor DLXSimulatorFun (structure RF : REGISTERFILE;
1863 structure ALU : ALU;
1864 structure MEM : MEMORY; ) : DLXSIMULATOR
1865 = struct
1866
1867 (*
1868 * The datatype Opcode provides a means of differentiating *
1869 * among the main opcodes.
1870 *)
1871 datatype Opcode =
1872 (* for R-type opcodes *)
1873 SPECIAL |
1874 (* I-type opcodes *)
1875 BEQZ | BNEZ |
1876 ADDI | ADDUI | SUBI | SUBUI |
1877 ANDI | ORI | XORI |
1878 LHI |
1879 SLLI | SRLI | SRAI |
1880 SEQI | SNEI | SLTI | SGTI | SLEI | SGEI |
1881 LB | LBU | SB |
1882 LH | LHU | SH |
1883 LW | SW |
1884 (* J-type opcodes *)
1885 J | JAL | TRAP | JR | JALR |
1886 (* Unrecognized opcode *)
1887 NON_OP;
1888
1889 (*
1890 * The datatype RRFuncCode provides a means of
1891 * differentiating among
1892 * the register-register function codes.
1893 *)
1894 datatype RRFunctCode = NOP | SLL | SRL | SRA |
1895 ADD | ADDU | SUB | SUBU |
1896 AND | OR | XOR |
1897 SEQ | SNE | SLT | SGT | SLE | SGE |
1898 NON_FUNCT;
1899
1900 (*
1901 * The datatype Instruction provides a means of
1902 * differentiating among the three different types of
1903 * instructions, I-type, R-type, and J-type.
1904 * An I-type is interpreted as (opcode, rs1, rd, immediate).
1905 * An R-type is interpreted as (opcode, rs1, rs2, rd, shamt, funct).
1906 * An J-type is interpreted as (opcode, offset).
1907 * An ILLEGAL causes the simulator to end.
1908 *)
1909 datatype Instruction
1910 = ITYPE of Opcode * int * int * Word32.word
1911 | RTYPE of Opcode * int * int * int * int * RRFunctCode
1912 | JTYPE of Opcode * Word32.word
1913 | ILLEGAL;
1914
1915 (*
1916 * The value HALT is set to the DLX instruction TRAP #0,
1917 * and is used to check for the halt of the program.
1918 *)
1919 val HALT = JTYPE (TRAP, 0wx00000000);
1920
1921 (*
1922 * The function DecodeIType decodes a Word32.word into an
1923 * I-type instruction.
1924 *)
1925 fun DecodeIType instr
1926 = let
1927 val opc = Word32.andb (Word32.>> (instr,
1928 0wx001A),
1929 0wx0000003F : Word32.word);
1930
1931 val opcode = case opc
1932 of 0wx00000004 : Word32.word => BEQZ
1933 | 0wx00000005 : Word32.word => BNEZ
1934 | 0wx00000008 : Word32.word => ADDI
1935 | 0wx00000009 : Word32.word => ADDUI
1936 | 0wx0000000A : Word32.word => SUBI
1937 | 0wx0000000B : Word32.word => SUBUI
1938 | 0wx0000000C : Word32.word => ANDI
1939 | 0wx0000000D : Word32.word => ORI
1940 | 0wx0000000E : Word32.word => XORI
1941 | 0wx0000000F : Word32.word => LHI
1942 | 0wx00000014 : Word32.word => SLLI
1943 | 0wx00000016 : Word32.word => SRLI
1944 | 0wx00000017 : Word32.word => SRAI
1945 | 0wx00000018 : Word32.word => SEQI
1946 | 0wx00000019 : Word32.word => SNEI
1947 | 0wx0000001A : Word32.word => SLTI
1948 | 0wx0000001B : Word32.word => SGTI
1949 | 0wx0000001C : Word32.word => SLEI
1950 | 0wx0000001D : Word32.word => SGEI
1951 | 0wx00000020 : Word32.word => LB
1952 | 0wx00000024 : Word32.word => LBU
1953 | 0wx00000028 : Word32.word => SB
1954 | 0wx00000021 : Word32.word => LH
1955 | 0wx00000025 : Word32.word => LHU
1956 | 0wx00000029 : Word32.word => SH
1957 | 0wx00000023 : Word32.word => LW
1958 | 0wx0000002B : Word32.word => SW
1959 | _ => (print "Error : Non I-Type opcode\n";
1960 NON_OP);
1961
1962 val rs1 = Word32.toInt(Word32.andb (Word32.>> (instr, 0wx0015),
1963 0wx0000001F : Word32.word));
1964
1965 val rd = Word32.toInt(Word32.andb (Word32.>> (instr, 0wx0010),
1966 0wx0000001F : Word32.word));
1967
1968 val immediate = Word32.~>> (Word32.<< (instr, 0wx0010),
1969 0wx0010);
1970
1971 in
1972 if opcode = NON_OP
1973 then ILLEGAL
1974 else ITYPE (opcode, rs1, rd, immediate)
1975 end;
1976
1977 (*
1978 * The function DecodeRType decodes a Word32.word into an
1979 * R-type instruction.
1980 *)
1981 fun DecodeRType instr
1982 = let
1983
1984 val rs1 = Word32.toInt (Word32.andb (Word32.>> (instr, 0wx0015),
1985 0wx0000001F : Word32.word));
1986
1987 val rs2 = Word32.toInt (Word32.andb (Word32.>> (instr, 0wx0010),
1988 0wx0000001F : Word32.word));
1989
1990 val rd = Word32.toInt (Word32.andb (Word32.>> (instr, 0wx000B),
1991 0wx0000001F : Word32.word));
1992
1993 val shamt
1994 = Word32.toInt (Word32.andb (Word32.>> (instr, 0wx0006),
1995 0wx0000001F : Word32.word));
1996
1997 val funct = Word32.andb (instr, 0wx0000003F : Word32.word);
1998
1999 val functcode = case funct
2000 of 0wx00000000 : Word32.word => NOP
2001 | 0wx00000004 : Word32.word => SLL
2002 | 0wx00000006 : Word32.word => SRL
2003 | 0wx00000007 : Word32.word => SRA
2004 | 0wx00000020 : Word32.word => ADD
2005 | 0wx00000021 : Word32.word => ADDU
2006 | 0wx00000022 : Word32.word => SUB
2007 | 0wx00000023 : Word32.word => SUBU
2008 | 0wx00000024 : Word32.word => AND
2009 | 0wx00000025 : Word32.word => OR
2010 | 0wx00000026 : Word32.word => XOR
2011 | 0wx00000028 : Word32.word => SEQ
2012 | 0wx00000029 : Word32.word => SNE
2013 | 0wx0000002A : Word32.word => SLT
2014 | 0wx0000002B : Word32.word => SGT
2015 | 0wx0000002C : Word32.word => SLE
2016 | 0wx0000002D : Word32.word => SGE
2017 | _ => (print "Error : Non R-type funct\n";
2018 NON_FUNCT);
2019
2020 in
2021 if functcode = NON_FUNCT
2022 then ILLEGAL
2023 else RTYPE (SPECIAL, rs1, rs2, rd, shamt, functcode)
2024 end;
2025
2026 (*
2027 * The function DecodeJType decodes a Word32.word into an
2028 * J-type instruction.
2029 *)
2030 fun DecodeJType instr
2031 = let
2032
2033 val opc = Word32.andb (Word32.>> (instr, 0wx1A),
2034 0wx0000003F : Word32.word);
2035
2036 val opcode = case opc
2037 of 0wx00000002 : Word32.word => J
2038 | 0wx00000003 : Word32.word => JAL
2039 | 0wx00000011 : Word32.word => TRAP
2040 | 0wx00000012 : Word32.word => JR
2041 | 0wx00000013 : Word32.word => JALR
2042 | _ => (print "Error : Non J-type opcode\n";
2043 NON_OP);
2044
2045 val offset = Word32.~>> (Word32.<< (instr, 0wx0006),
2046 0wx0006);
2047
2048 in
2049 if opcode = NON_OP
2050 then ILLEGAL
2051 else JTYPE (opcode, offset)
2052 end;
2053
2054 (*
2055 * The function DecodeInstr decodes a Word32.word into an
2056 * instruction. It first checks the opcode, and then calls
2057 * one of DecodeIType, DecodeJType, and DecodeRType to
2058 * complete the decoding process.
2059 *)
2060 fun DecodeInstr instr
2061 = let
2062
2063 val opcode = Word32.andb (Word32.>> (instr, 0wx1A),
2064 0wx0000003F : Word32.word);
2065
2066 in
2067 case opcode
2068 of 0wx00000000 : Word32.word => DecodeRType instr
2069 | 0wx00000002 : Word32.word => DecodeJType instr
2070 | 0wx00000003 : Word32.word => DecodeJType instr
2071 | 0wx00000004 : Word32.word => DecodeIType instr
2072 | 0wx00000005 : Word32.word => DecodeIType instr
2073 | 0wx00000008 : Word32.word => DecodeIType instr
2074 | 0wx00000009 : Word32.word => DecodeIType instr
2075 | 0wx0000000A : Word32.word => DecodeIType instr
2076 | 0wx0000000B : Word32.word => DecodeIType instr
2077 | 0wx0000000C : Word32.word => DecodeIType instr
2078 | 0wx0000000D : Word32.word => DecodeIType instr
2079 | 0wx0000000E : Word32.word => DecodeIType instr
2080 | 0wx0000000F : Word32.word => DecodeIType instr
2081 | 0wx00000011 : Word32.word => DecodeJType instr
2082 | 0wx00000012 : Word32.word => DecodeJType instr
2083 | 0wx00000013 : Word32.word => DecodeJType instr
2084 | 0wx00000016 : Word32.word => DecodeIType instr
2085 | 0wx00000017 : Word32.word => DecodeIType instr
2086 | 0wx00000018 : Word32.word => DecodeIType instr
2087 | 0wx00000019 : Word32.word => DecodeIType instr
2088 | 0wx0000001A : Word32.word => DecodeIType instr
2089 | 0wx0000001B : Word32.word => DecodeIType instr
2090 | 0wx0000001C : Word32.word => DecodeIType instr
2091 | 0wx0000001D : Word32.word => DecodeIType instr
2092 | 0wx00000020 : Word32.word => DecodeIType instr
2093 | 0wx00000024 : Word32.word => DecodeIType instr
2094 | 0wx00000028 : Word32.word => DecodeIType instr
2095 | 0wx00000021 : Word32.word => DecodeIType instr
2096 | 0wx00000025 : Word32.word => DecodeIType instr
2097 | 0wx00000029 : Word32.word => DecodeIType instr
2098 | 0wx00000023 : Word32.word => DecodeIType instr
2099 | 0wx0000002B : Word32.word => DecodeIType instr
2100 | _ => (print "Error : Unrecognized opcode\n";
2101 ILLEGAL)
2102 end;
2103
2104
2105 (*
2106 * The function PerformIType performs one of the I-Type
2107 * instructions. A number of the instructions make use of the
2108 * ALU, and as such, call ALU.PerformAL.
2109 *)
2110 fun PerformIType ((BEQZ, rs1, rd, immediate), (PC, rf, mem))
2111 = if (RF.LoadRegister(rf, rs1) = (0wx00000000 : Word32.word))
2112 then (Word32.fromInt (Int.+ (Word32.toIntX PC,
2113 Word32.toIntX
2114 (Word32.<< (immediate,
2115 0wx0002)))),
2116 rf, mem)
2117 else (PC, rf, mem)
2118
2119 | PerformIType ((BNEZ, rs1, rd, immediate), (PC, rf, mem))
2120 = if not (RF.LoadRegister(rf, rs1) = (0wx00000000 : Word32.word))
2121 then (Word32.fromInt (Int.+ (Word32.toIntX PC,
2122 Word32.toIntX
2123 (Word32.<< (immediate,
2124 0wx0002)))),
2125 rf, mem)
2126 else (PC, rf, mem)
2127
2128 | PerformIType ((ADDI, rs1, rd, immediate), (PC, rf, mem))
2129 = (PC,
2130 RF.StoreRegister(rf, rd,
2131 ALU.PerformAL(ALU.ADD,
2132 RF.LoadRegister(rf, rs1),
2133 immediate)),
2134 mem)
2135
2136 | PerformIType ((ADDUI, rs1, rd, immediate), (PC, rf, mem))
2137 = (PC,
2138 RF.StoreRegister(rf, rd,
2139 ALU.PerformAL(ALU.ADDU,
2140 RF.LoadRegister(rf, rs1),
2141 immediate)),
2142 mem)
2143
2144 | PerformIType ((SUBI, rs1, rd, immediate), (PC, rf, mem))
2145 = (PC,
2146 RF.StoreRegister(rf, rd,
2147 ALU.PerformAL(ALU.SUB,
2148 RF.LoadRegister(rf, rs1),
2149 immediate)),
2150 mem)
2151
2152 | PerformIType ((SUBUI, rs1, rd, immediate), (PC, rf, mem))
2153 = (PC,
2154 RF.StoreRegister(rf, rd,
2155 ALU.PerformAL(ALU.SUBU,
2156 RF.LoadRegister(rf, rs1),
2157 immediate)),
2158 mem)
2159
2160 | PerformIType ((ANDI, rs1, rd, immediate), (PC, rf, mem))
2161 = (PC,
2162 RF.StoreRegister(rf, rd,
2163 ALU.PerformAL(ALU.AND,
2164 RF.LoadRegister(rf, rs1),
2165 immediate)),
2166 mem)
2167
2168 | PerformIType ((ORI, rs1, rd, immediate), (PC, rf, mem))
2169 = (PC,
2170 RF.StoreRegister(rf, rd,
2171 ALU.PerformAL(ALU.OR,
2172 RF.LoadRegister(rf, rs1),
2173 immediate)),
2174 mem)
2175
2176 | PerformIType ((XORI, rs1, rd, immediate), (PC, rf, mem))
2177 = (PC,
2178 RF.StoreRegister(rf, rd,
2179 ALU.PerformAL(ALU.XOR,
2180 RF.LoadRegister(rf, rs1),
2181 immediate)),
2182 mem)
2183
2184 | PerformIType ((LHI, rs1, rd, immediate), (PC, rf, mem))
2185 = (PC, RF.StoreRegister(rf, rd, Word32.<< (immediate, 0wx0010)), mem)
2186
2187 | PerformIType ((SLLI, rs1, rd, immediate), (PC, rf, mem))
2188 = (PC, RF.StoreRegister(rf, rd,
2189 Word32.<< (RF.LoadRegister(rf, rs1),
2190 Word.fromLarge (Word32.toLarge immediate))),
2191 mem)
2192
2193 | PerformIType ((SRLI, rs1, rd, immediate), (PC, rf, mem))
2194 = (PC, RF.StoreRegister(rf, rd,
2195 Word32.>> (RF.LoadRegister(rf, rs1),
2196 Word.fromLarge (Word32.toLarge immediate))),
2197 mem)
2198
2199 | PerformIType ((SRAI, rs1, rd, immediate), (PC, rf, mem))
2200 = (PC, RF.StoreRegister(rf, rd,
2201 Word32.~>> (RF.LoadRegister(rf, rs1),
2202 Word.fromLarge (Word32.toLarge immediate))),
2203 mem)
2204
2205 | PerformIType ((SEQI, rs1, rd, immediate), (PC, rf, mem))
2206 = (PC,
2207 RF.StoreRegister(rf, rd,
2208 ALU.PerformAL(ALU.SEQ,
2209 RF.LoadRegister(rf, rs1),
2210 immediate)),
2211 mem)
2212
2213 | PerformIType ((SNEI, rs1, rd, immediate), (PC, rf, mem))
2214 = (PC,
2215 RF.StoreRegister(rf, rd,
2216 ALU.PerformAL(ALU.SNE,
2217 RF.LoadRegister(rf, rs1),
2218 immediate)),
2219 mem)
2220
2221 | PerformIType ((SLTI, rs1, rd, immediate), (PC, rf, mem))
2222 = (PC,
2223 RF.StoreRegister(rf, rd,
2224 ALU.PerformAL(ALU.SLT,
2225 RF.LoadRegister(rf, rs1),
2226 immediate)),
2227 mem)
2228
2229 | PerformIType ((SGTI, rs1, rd, immediate), (PC, rf, mem))
2230 = (PC,
2231 RF.StoreRegister(rf, rd,
2232 ALU.PerformAL(ALU.SGT,
2233 RF.LoadRegister(rf, rs1),
2234 immediate)),
2235 mem)
2236
2237 | PerformIType ((SLEI, rs1, rd, immediate), (PC, rf, mem))
2238 = (PC,
2239 RF.StoreRegister(rf, rd,
2240 ALU.PerformAL(ALU.SLE,
2241 RF.LoadRegister(rf, rs1),
2242 immediate)),
2243 mem)
2244
2245 | PerformIType ((SGEI, rs1, rd, immediate), (PC, rf, mem))
2246 = (PC,
2247 RF.StoreRegister(rf, rd,
2248 ALU.PerformAL(ALU.SGE,
2249 RF.LoadRegister(rf, rs1),
2250 immediate)),
2251 mem)
2252
2253 | PerformIType ((LB, rs1, rd, immediate), (PC, rf, mem))
2254 = let
2255 val (nmem, l_byte)
2256 = MEM.LoadByte(mem, Word32.+ (RF.LoadRegister(rf, rs1),
2257 immediate));
2258 in
2259 (PC,
2260 RF.StoreRegister(rf, rd, l_byte),
2261 nmem)
2262 end
2263
2264 | PerformIType ((LBU, rs1, rd, immediate), (PC, rf, mem))
2265 = let
2266 val (nmem, l_byte)
2267 = MEM.LoadByteU(mem, Word32.+ (RF.LoadRegister(rf, rs1),
2268 immediate));
2269 in
2270 (PC,
2271 RF.StoreRegister(rf, rd, l_byte),
2272 nmem)
2273 end
2274
2275 | PerformIType ((SB, rs1, rd, immediate), (PC, rf, mem))
2276 = (PC,
2277 rf,
2278 MEM.StoreByte(mem,
2279 Word32.+ (RF.LoadRegister(rf, rs1), immediate),
2280 Word32.andb(0wx000000FF, RF.LoadRegister(rf, rd))))
2281
2282 | PerformIType ((LH, rs1, rd, immediate), (PC, rf, mem))
2283 = let
2284 val (nmem, l_hword)
2285 = MEM.LoadHWord(mem, Word32.+ (RF.LoadRegister(rf, rs1),
2286 immediate));
2287 in
2288 (PC,
2289 RF.StoreRegister(rf, rd, l_hword),
2290 nmem)
2291 end
2292
2293 | PerformIType ((LHU, rs1, rd, immediate), (PC, rf, mem))
2294 = let
2295 val (nmem, l_hword)
2296 = MEM.LoadHWordU(mem, Word32.+ (RF.LoadRegister(rf, rs1),
2297 immediate));
2298 in
2299 (PC,
2300 RF.StoreRegister(rf, rd, l_hword),
2301 nmem)
2302 end
2303
2304 | PerformIType ((SH, rs1, rd, immediate), (PC, rf, mem))
2305 = (PC,
2306 rf,
2307 MEM.StoreByte(mem,
2308 Word32.+ (RF.LoadRegister(rf, rs1), immediate),
2309 Word32.andb(0wx0000FFFF, RF.LoadRegister(rf, rd))))
2310
2311
2312 | PerformIType ((LW, rs1, rd, immediate), (PC, rf, mem))
2313 = let
2314 val (nmem, l_word)
2315 = MEM.LoadWord(mem, Word32.+ (RF.LoadRegister(rf, rs1),
2316 immediate));
2317 in
2318 (PC,
2319 RF.StoreRegister(rf, rd, l_word),
2320 nmem)
2321 end
2322
2323 | PerformIType ((SW, rs1, rd, immediate), (PC, rf, mem))
2324 = (PC,
2325 rf,
2326 MEM.StoreWord(mem,
2327 Word32.+ (RF.LoadRegister(rf, rs1), immediate),
2328 RF.LoadRegister(rf, rd)))
2329
2330 | PerformIType ((_, rs1, rd, immediate), (PC, rf, mem))
2331 = (print "Error : Non I-Type opcode, performing NOP\n";
2332 (PC, rf, mem));
2333
2334
2335 (*
2336 * The function PerformRType performs one of the R-Type
2337 * instructions. All of the instructions make use of the
2338 * ALU, and as such, call ALU.PerformAL.
2339 *)
2340 fun PerformRType ((SPECIA, rs1, rs2, rd, shamt, NOP), (PC, rf, mem))
2341 = (PC, rf, mem)
2342
2343 | PerformRType ((SPECIAL, rs1, rs2, rd, shamt, SLL), (PC, rf, mem))
2344 = (PC,
2345 RF.StoreRegister(rf, rd,
2346 ALU.PerformAL(ALU.SLL,
2347 RF.LoadRegister(rf, rs1),
2348 RF.LoadRegister(rf, rs2))),
2349 mem)
2350
2351 | PerformRType ((SPECIAL, rs1, rs2, rd, shamt, SRL), (PC, rf, mem))
2352 = (PC,
2353 RF.StoreRegister(rf, rd,
2354 ALU.PerformAL(ALU.SRL,
2355 RF.LoadRegister(rf, rs1),
2356 RF.LoadRegister(rf, rs2))),
2357 mem)
2358
2359 | PerformRType ((SPECIAL, rs1, rs2, rd, shamt, SRA), (PC, rf, mem))
2360 = (PC,
2361 RF.StoreRegister(rf, rd,
2362 ALU.PerformAL(ALU.SRA,
2363 RF.LoadRegister(rf, rs1),
2364 RF.LoadRegister(rf, rs2))),
2365 mem)
2366
2367 | PerformRType ((SPECIAL, rs1, rs2, rd, shamt, ADD), (PC, rf, mem))
2368 = (PC,
2369 RF.StoreRegister(rf, rd,
2370 ALU.PerformAL(ALU.ADD,
2371 RF.LoadRegister(rf, rs1),
2372 RF.LoadRegister(rf, rs2))),
2373 mem)
2374
2375 | PerformRType ((SPECIAL, rs1, rs2, rd, shamt, ADDU), (PC, rf, mem))
2376 = (PC,
2377 RF.StoreRegister(rf, rd,
2378 ALU.PerformAL(ALU.ADDU,
2379 RF.LoadRegister(rf, rs1),
2380 RF.LoadRegister(rf, rs2))),
2381 mem)
2382
2383 | PerformRType ((SPECIAL, rs1, rs2, rd, shamt, SUB), (PC, rf, mem))
2384 = (PC,
2385 RF.StoreRegister(rf, rd,
2386 ALU.PerformAL(ALU.SUB,
2387 RF.LoadRegister(rf, rs1),
2388 RF.LoadRegister(rf, rs2))),
2389 mem)
2390
2391 | PerformRType ((SPECIAL, rs1, rs2, rd, shamt, SUBU), (PC, rf, mem))
2392 = (PC,
2393 RF.StoreRegister(rf, rd,
2394 ALU.PerformAL(ALU.SUBU,
2395 RF.LoadRegister(rf, rs1),
2396 RF.LoadRegister(rf, rs2))),
2397 mem)
2398
2399 | PerformRType ((SPECIAL, rs1, rs2, rd, shamt, AND), (PC, rf, mem))
2400 = (PC,
2401 RF.StoreRegister(rf, rd,
2402 ALU.PerformAL(ALU.AND,
2403 RF.LoadRegister(rf, rs1),
2404 RF.LoadRegister(rf, rs2))),
2405 mem)
2406
2407 | PerformRType ((SPECIAL, rs1, rs2, rd, shamt, OR), (PC, rf, mem))
2408 = (PC,
2409 RF.StoreRegister(rf, rd,
2410 ALU.PerformAL(ALU.OR,
2411 RF.LoadRegister(rf, rs1),
2412 RF.LoadRegister(rf, rs2))),
2413 mem)
2414
2415 | PerformRType ((SPECIAL, rs1, rs2, rd, shamt, XOR), (PC, rf, mem))
2416 = (PC,
2417 RF.StoreRegister(rf, rd,
2418 ALU.PerformAL(ALU.XOR,
2419 RF.LoadRegister(rf, rs1),
2420 RF.LoadRegister(rf, rs2))),
2421 mem)
2422
2423 | PerformRType ((SPECIAL, rs1, rs2, rd, shamt, SEQ), (PC, rf, mem))
2424 = (PC,
2425 RF.StoreRegister(rf, rd,
2426 ALU.PerformAL(ALU.SEQ,
2427 RF.LoadRegister(rf, rs1),
2428 RF.LoadRegister(rf, rs2))),
2429 mem)
2430
2431 | PerformRType ((SPECIAL, rs1, rs2, rd, shamt, SNE), (PC, rf, mem))
2432 = (PC,
2433 RF.StoreRegister(rf, rd,
2434 ALU.PerformAL(ALU.SNE,
2435 RF.LoadRegister(rf, rs1),
2436 RF.LoadRegister(rf, rs2))),
2437 mem)
2438
2439 | PerformRType ((SPECIAL, rs1, rs2, rd, shamt, SLT), (PC, rf, mem))
2440 = (PC,
2441 RF.StoreRegister(rf, rd,
2442 ALU.PerformAL(ALU.SLT,
2443 RF.LoadRegister(rf, rs1),
2444 RF.LoadRegister(rf, rs2))),
2445 mem)
2446
2447 | PerformRType ((SPECIAL, rs1, rs2, rd, shamt, SGT), (PC, rf, mem))
2448 = (PC,
2449 RF.StoreRegister(rf, rd,
2450 ALU.PerformAL(ALU.SGT,
2451 RF.LoadRegister(rf, rs1),
2452 RF.LoadRegister(rf, rs2))),
2453 mem)
2454
2455 | PerformRType ((SPECIAL, rs1, rs2, rd, shamt, SLE), (PC, rf, mem))
2456 = (PC,
2457 RF.StoreRegister(rf, rd,
2458 ALU.PerformAL(ALU.SLE,
2459 RF.LoadRegister(rf, rs1),
2460 RF.LoadRegister(rf, rs2))),
2461 mem)
2462
2463 | PerformRType ((SPECIAL, rs1, rs2, rd, shamt, SGE), (PC, rf, mem))
2464 = (PC,
2465 RF.StoreRegister(rf, rd,
2466 ALU.PerformAL(ALU.SGE,
2467 RF.LoadRegister(rf, rs1),
2468 RF.LoadRegister(rf, rs2))),
2469 mem)
2470
2471 | PerformRType ((_, rs1, rs2, rd, shamt, _), (PC, rf, mem))
2472 = (print "Error : Non R-Type opcode, performing NOP\n";
2473 (PC, rf, mem));
2474
2475
2476 (*
2477 * The function PerformJType performs one of the J-Type
2478 * instructions.
2479 *)
2480 fun PerformJType ((J, offset), (PC, rf, mem))
2481 = (Word32.fromInt (Int.+ (Word32.toIntX PC,
2482 Word32.toIntX
2483 (Word32.<< (offset, 0wx0002)))),
2484 rf, mem)
2485
2486 | PerformJType ((JR, offset), (PC, rf, mem))
2487 = (RF.LoadRegister(rf,
2488 Word32.toInt(Word32.andb (Word32.>> (offset,
2489 0wx0015),
2490 0wx0000001F :
2491 Word32.word))),
2492 rf, mem)
2493
2494 | PerformJType ((JAL, offset), (PC, rf, mem))
2495 = (Word32.fromInt (Int.+ (Word32.toIntX PC,
2496 Word32.toIntX
2497 (Word32.<< (offset, 0wx0002)))),
2498 RF.StoreRegister(rf, 31, PC),
2499 mem)
2500
2501 | PerformJType ((JALR, offset), (PC, rf, mem))
2502 = (RF.LoadRegister(rf,
2503 Word32.toInt (Word32.andb (Word32.>> (offset,
2504 0wx0015),
2505 0wx0000001F :
2506 Word32.word))),
2507 RF.StoreRegister(rf, 31, PC),
2508 mem)
2509
2510 | PerformJType ((TRAP, 0wx00000003 : Word32.word), (PC, rf, mem))
2511 = let
2512 val x = TextIO.print "Value? ";
2513 val s = "10" (* TextIO.inputLine TextIO.stdIn; *)
2514 val i = Int.fromString s;
2515 val input = if isSome i
2516 then valOf i
2517 else (TextIO.print "Error : Returning 0\n";
2518 Int.fromInt 0);
2519 in
2520 (PC,
2521 RF.StoreRegister(rf, 14, Word32.fromInt input),
2522 mem)
2523 end
2524
2525 | PerformJType ((TRAP, 0wx00000004 : Word32.word), (PC, rf, mem))
2526 = let
2527 val output = Int.toString (Word32.toIntX
2528 (RF.LoadRegister(rf, 14)));
2529
2530 in
2531 (TextIO.print ("Output: " ^ output ^ "\n");
2532 (PC, rf, mem))
2533 end
2534
2535 | PerformJType ((_, offset), (PC, rf, mem))
2536 = (print "Error : Non J-Type opcode, performing NOP\n";
2537 (PC, rf, mem));
2538
2539
2540 (*
2541 * The function PerformInstr performs an instruction by
2542 * passing the instruction to the appropriate auxiliary function.
2543 *)
2544 fun PerformInstr (ITYPE instr, (PC, rf, mem))
2545 = PerformIType (instr, (PC, rf, mem))
2546 | PerformInstr (RTYPE instr, (PC, rf, mem))
2547 = PerformRType (instr, (PC, rf, mem))
2548 | PerformInstr (JTYPE instr, (PC, rf, mem))
2549 = PerformJType (instr, (PC, rf, mem))
2550 | PerformInstr (ILLEGAL, (PC, rf, mem))
2551 = (PC, rf, mem);
2552
2553
2554 (*
2555 * The function CycleLoop represents the basic clock cylce of
2556 * the DLX processor. It takes as input the current program
2557 * counter, the current register file, and the current memory.
2558 * It loads, decodes, and executes an instruction and increments
2559 * the program counter. If the instruction that was loaded is
2560 * the HALT instruction, the program terminates, otherwise,
2561 * CycleLoop is recursively called with the result of performing
2562 * the instruction.
2563 *)
2564 fun CycleLoop (PC, rf, mem)
2565 = let
2566 val (nmem, instr_word) = MEM.LoadWord (mem, PC);
2567 val instr = DecodeInstr instr_word;
2568 val nPC = Word32.+ (PC, 0wx00000004 : Word32.word);
2569 in
2570 if instr = HALT orelse instr = ILLEGAL
2571 then (print "Program halted.\n";
2572 print (MEM.GetStatistics (nmem));
2573 ())
2574 else CycleLoop (PerformInstr (instr, (nPC, rf, nmem)))
2575 end
2576
2577
2578 (*
2579 * The function LoadProgAux is an auxilary function that
2580 * assists in loading a program into memory. It recursively
2581 * calls itself, each time loading an instruction and incrementing
2582 * the address to which the next instruction is to be loaded.
2583 *)
2584 fun LoadProgAux ([], mem, address)
2585 = mem
2586 | LoadProgAux (instrs::instr_list, mem, address)
2587 = let
2588 val instro = Word32.fromString instrs;
2589 val instr = if isSome instro
2590 then valOf instro
2591 else (print ("Error : Invalid " ^
2592 "instruction format, " ^
2593 "returning NOP\n");
2594 0wx00000000 : Word32.word);
2595 in
2596 LoadProgAux (instr_list,
2597 MEM.StoreWord (mem, address, instr),
2598 Word32.+ (address, 0wx00000004 : Word32.word))
2599 end;
2600
2601 (*
2602 * The function LoadProg takes a list of instructions and memory, and
2603 * loads the file into memory, beginning at 0x10000.
2604 *)
2605 fun LoadProg (instr_list, mem)
2606 = LoadProgAux (instr_list, mem, 0wx00010000 : Word32.word);
2607
2608
2609 (*
2610 * The function ReadFileToInstr reads the sequence of
2611 * instructions in a file into a list.
2612 *)
2613 fun ReadFileToInstr file
2614 = (case TextIO.inputLine file of
2615 NONE => []
2616 | SOME l => l :: (ReadFileToInstr file));
2617
2618
2619 (*
2620 * The function run_prog is exported by DLXSimulator.
2621 * It takes a list of instructions, then begins
2622 * execution of the instructions loaded at 0x10000, with an
2623 * initialized register file, and the loaded program in an
2624 * initialised memory.
2625 *)
2626 fun run_prog instructions
2627 = CycleLoop (0wx00010000 : Word32.word,
2628 RF.InitRegisterFile (),
2629 LoadProg (instructions, MEM.InitMemory ()));
2630
2631 (*
2632 * The function run_file is exported by DLXSimulator.
2633 * It takes the name of a file to be run, then begins
2634 * execution of the loaded program at 0x10000, with an
2635 * initialized register file, and the loaded program in an
2636 * initialized memory.
2637 *)
2638 fun run_file filename
2639 = (run_prog o ReadFileToInstr) (TextIO.openIn filename);
2640
2641 end;
2642
2643
2644
2645
2646(* ************************************************************************* *)
2647
2648(*
2649 * Cache1.sml
2650 *
2651 * This file describes a small simple level 1 cache.
2652 *)
2653
2654structure L1CacheSpec1 : CACHESPEC
2655 = struct
2656
2657 datatype WriteHitOption = Write_Through
2658 | Write_Back;
2659
2660 datatype WriteMissOption = Write_Allocate
2661 | Write_No_Allocate;
2662
2663 val CacheName = "Level 1 Cache";
2664 val CacheSize = 256;
2665 val BlockSize = 4;
2666 val Associativity = 2;
2667 val WriteHit = Write_Through;
2668 val WriteMiss = Write_No_Allocate;
2669
2670 end;
2671
2672
2673structure L1Cache1 : MEMORY
2674 = CachedMemory (structure CS = L1CacheSpec1;
2675 structure MEM = Memory; );
2676
2677
2678structure DLXSimulatorC1 : DLXSIMULATOR
2679 = DLXSimulatorFun (structure RF = RegisterFile;
2680 structure ALU = ALU;
2681 structure MEM = L1Cache1; );
2682
2683(* Example programs *)
2684
2685val Simple = ["200E002F",
2686 "44000004",
2687 "44000000"];
2688
2689val Twos = ["44000003",
2690 "00000000",
2691 "3D00FFFF",
2692 "3508FFFF",
2693 "010E7026",
2694 "25CE0001",
2695 "44000004",
2696 "00000000",
2697 "44000000",
2698 "00000000"];
2699
2700
2701val Abs = ["44000003",
2702 "00000000",
2703 "01C0402A",
2704 "11000002",
2705 "00000000",
2706 "000E7022",
2707 "44000004",
2708 "00000000",
2709 "44000000",
2710 "00000000"]
2711
2712val Fact = ["0C000002",
2713 "00000000",
2714 "44000000",
2715 "44000003",
2716 "000E2020",
2717 "2FBD0020",
2718 "AFBF0014",
2719 "AFBE0010",
2720 "27BE0020",
2721 "0C000009",
2722 "00000000",
2723 "8FBE0010",
2724 "8FBF0014",
2725 "27BD0020",
2726 "00027020",
2727 "44000004",
2728 "00001020",
2729 "4BE00000",
2730 "00000000",
2731 "20080001",
2732 "0088402C",
2733 "11000004",
2734 "00000000",
2735 "20020001",
2736 "08000016",
2737 "00000000",
2738 "2FBD0004",
2739 "AFA40000",
2740 "28840001",
2741 "2FBD0020",
2742 "AFBF0014",
2743 "AFBE0010",
2744 "27BE0020",
2745 "0FFFFFF1",
2746 "00000000",
2747 "8FBE0010",
2748 "8FBF0014",
2749 "27BD0020",
2750 "8FA40000",
2751 "27BD0004",
2752 "00004020",
2753 "10800005",
2754 "00000000",
2755 "01024020",
2756 "28840001",
2757 "0BFFFFFB",
2758 "00000000",
2759 "01001020",
2760 "4BE00000",
2761 "00000000"];
2762
2763val GCD = ["0C000002",
2764 "00000000",
2765 "44000000",
2766 "44000003",
2767 "00000000",
2768 "000E2020",
2769 "0080402A",
2770 "11000002",
2771 "00000000",
2772 "00042022",
2773 "44000003",
2774 "00000000",
2775 "000E2820",
2776 "00A0402A",
2777 "11000002",
2778 "00000000",
2779 "00052822",
2780 "2FBD0020",
2781 "AFBF0014",
2782 "AFBE0010",
2783 "27BE0020",
2784 "0C00000A",
2785 "00000000",
2786 "8FBE0010",
2787 "8FBF0014",
2788 "27BD0020",
2789 "00027020",
2790 "44000004",
2791 "00000000",
2792 "00001020",
2793 "4BE00000",
2794 "00000000",
2795 "14A00004",
2796 "00000000",
2797 "00801020",
2798 "08000013",
2799 "00000000",
2800 "0085402C",
2801 "15000006",
2802 "00000000",
2803 "00804020",
2804 "00A02020",
2805 "01002820",
2806 "08000002",
2807 "00000000",
2808 "00A42822",
2809 "2FBD0020",
2810 "AFBF0014",
2811 "AFBE0010",
2812 "27BE0020",
2813 "0FFFFFED",
2814 "00000000",
2815 "8FBE0010",
2816 "8FBF0014",
2817 "27BD0020",
2818 "4BE00000",
2819 "00000000"];
2820
2821(*
2822val _ = DLXSimulatorC1.run_prog GCD
2823*)
2824
2825structure Main =
2826 struct
2827 fun doit () =
2828 (DLXSimulatorC1.run_prog Simple
2829 ; DLXSimulatorC1.run_prog Twos
2830 ; DLXSimulatorC1.run_prog Abs
2831 ; DLXSimulatorC1.run_prog Fact
2832 ; DLXSimulatorC1.run_prog GCD
2833 )
2834
2835 val doit =
2836 fn size =>
2837 let
2838 fun loop n =
2839 if n = 0
2840 then ()
2841 else (doit();
2842 loop(n-1))
2843 in loop size
2844 end
2845 end
mlton packaging