1 (* Minor tweaks by Stephen
Weeks (sweeks@sweeks
.com
) on
2001-07-17 to turn into a
9 * e
-mail
: Matthew_Fluet@hmc
.edu
11 * A DLX Simulator
in Standard ML
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
:
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
.
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
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
.
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.
93 * Patterson
, David A
. and John L
. Hennessy
. _Computer Architecture
: A
94 * Quantitative Approach
: Second Edition_
. San Francisco
: Morgan
95 * Kaufmann Publishers
, Inc
., 1996.
99 (* ************************************************************************* *)
101 (* sweeks added rand
*)
104 val seed
: word ref
= ref
0w13
106 (* From page
284 of Numerical Recipes
in C
. *)
109 val res
= 0w1664525
* !seed
+ 0w1013904223
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
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
.
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
.
149 val immarray
: (int * 'a
) -> 'a immarray
;
150 val fromList
: 'a list
-> 'a immarray
;
151 val toList
: 'a immarray
-> 'a list
;
153 val tabulate
: int * (int -> 'a
) -> 'a immarray
;
154 val length
: 'a immarray
-> int;
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
;
160 val copy
: {src
: 'a immarray
, si
: int, len
: int option
,
161 dst
: 'a immarray
, di
: int} -> 'a immarray
;
163 val appi
: (int * 'a
-> unit
) -> ('a immarray
* int * int option
)
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
)
174 val map
: ('a
-> 'b
) -> 'a immarray
-> 'b immarray
;
175 val modifyi
: ((int * 'a
) -> 'a
) -> ('a immarray
* int * int option
)
177 val modify
: ('a
-> 'a
) -> 'a immarray
-> 'a immarray
;
181 structure ImmArray
: IMMARRAY
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
.
189 datatype 'a immarray
= IA
of 'a list
;
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
198 val maxLen
= Array
.maxLen
;
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
.
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
;
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
.
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))));
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
.
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
));
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
238 fun copy
{src
, si
, len
, dst
=IA ia
, di
}
240 val IA sia
= extract (src
, si
, len
);
241 val pre
= List.take (ia
, di
);
243 of NONE
=> List.drop (ia
, di
+(List.length sia
))
244 | SOME n
=> List.drop (ia
, di
+n
);
246 IA (pre @ sia @ post
)
249 (* val appi
: ('a
* int -> unit
) -> ('a immarray
* int * int option
)
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
.
258 fun appi_aux f i
[] = ()
259 | appi_aux f
i (h
::t
) = (f(i
,h
); appi_aux
f (i
+ 1) t
);
261 fun appi
f (IA ia
, i
, len
) = let
262 val IA sia
= extract (IA ia
, i
, len
);
267 fun app f immarr
= appi (f
o #
2) (immarr
, 0, NONE
);
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
.
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
);
286 fun foldli f
b (IA ia
, i
, len
)
288 val IA ia2
= extract (IA ia
, i
, len
);
292 fun foldri f
b (IA ia
, i
, len
)
294 val IA ia2
= extract (IA ia
, i
, len
);
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
);
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
.
315 fun mapi_aux f i
[] = []
316 | mapi_aux f
i (h
::t
) = (f (i
,h
))::(mapi_aux
f (i
+ 1) t
);
318 fun mapi
f (IA ia
, i
, len
) = let
319 val IA ia2
= extract (IA ia
, i
, len
);
321 IA (mapi_aux f i ia2
)
324 fun map
f (IA ia
)= mapi (f
o #
2) (IA ia
, 0, NONE
);
326 (* val modifyi
: (int * 'a
-> 'a
) -> ('a immarray
* int * int option
)
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
.
336 fun modifyi_aux f i
[] = []
337 | modifyi_aux f
i (h
::t
) = (f (i
,h
))::(modifyi_aux
f (i
+ 1) t
);
339 fun modifyi
f (IA ia
, i
, len
)
341 val pre
= List.take (ia
, i
);
342 val IA ia2
= extract (IA ia
, i
, len
);
345 | SOME n
=> List.drop (ia
, i
+n
);
347 IA (pre @
(modifyi_aux f i ia2
) @ post
)
350 fun modify
f (IA ia
) = modifyi (f
o #
2) (IA ia
, 0, NONE
);
354 (* ************************************************************************* *)
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.
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
.
381 datatype traversal
= RowMajor | ColMajor
383 val immarray2
: int * int * 'a
-> 'a immarray2
;
384 val tabulate
: traversal
-> int * int * ((int * int) -> 'a
)
386 val fromList
: 'a list list
-> 'a immarray2
;
387 val dimensions
: 'a immarray2
-> int * int;
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
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
;
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
;
403 val appi
: traversal
-> (int * int * 'a
-> unit
)
404 -> ('a immarray2
* int * int * int option
* int option
)
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
)
410 val foldri
: traversal
-> ((int * int * 'a
* 'b
) -> 'b
) -> 'b
411 -> ('a immarray2
* int * int * int option
* int option
)
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
)
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
)
422 val modify
: traversal
-> ('a
-> 'a
) -> 'a immarray2
-> 'a immarray2
;
425 structure ImmArray2
: IMMARRAY2
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
.
433 datatype 'a immarray2
= IA2
of 'a ImmArray
.immarray ImmArray
.immarray
;
434 datatype traversal
= RowMajor | ColMajor
436 (* val tabulate
: traversal
-> int * int * (int * int -> 'a
)
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
.
452 fun tabulate
RowMajor (r
, c
, initfn
)
454 fun initrow r
= ImmArray
.tabulate (c
, fn ic
=> initfn (r
,ic
));
456 IA2 (ImmArray
.tabulate (r
, fn ir
=> initrow ir
))
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
)
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)))
467 (* turn
: 'a immarray2
-> 'a immarray2
468 * This function reverses the rows
and columns
of an immarray2
469 * to allow handling
of ColMajor traversals
.
472 val (r
,c
) = dimensions ia2
;
474 tabulate
RowMajor (c
,r
,fn (cc
,rr
) => sub (ia2
,rr
,cc
))
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
.
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
),
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
.
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
)));
497 (* val nRows
: 'a immarray2
-> int
498 * val nCols
: 'a immarray2
-> int
499 * These functions return specific dimensions
of an immarray2
.
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
.
509 fun row (ia2
, r
) = let
510 val (c
, _
) = dimensions ia2
;
512 ImmArray
.tabulate (c
, fn i
=> sub (ia2
, r
, i
))
514 fun column (ia2
, c
) = let
515 val (_
, r
) = dimensions ia2
;
517 ImmArray
.tabulate (r
, fn i
=> sub (ia2
, i
, c
))
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
.
526 fun copy
{src
, si
, sj
, ilen
, jlen
, dst
=IA2 ia2
, di
, dj
}
528 val nilen
= case ilen
529 of NONE
=> SOME ((nRows src
) - si
)
532 IA2 (ImmArray
.modifyi (fn (r
, ia
)
533 => ImmArray
.copy
{src
=row (src
, si
+r
-di
),
539 (* val appi
: traversal
-> ('a
* int * int -> unit
) -> 'a immarray2
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
.
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
))
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
);
555 (* val foldli
: traversal
-> ((int * int * 'a
* 'b
) -> 'b
) -> 'b
556 * -> ('a immarray2
* int * int * int option
* int option
)
558 * val foldri
: traversal
-> ((int * int * 'a
* 'b
) -> 'b
) -> 'b
559 * -> ('a immarray2
* int * int * int option
* int option
)
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
.
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
))
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
))
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
);
593 (* val mapi
: traversal
-> ('a
* int * int -> 'b
) -> 'a 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
.
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
))
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
);
616 (* val modifyi
: traversal
-> (int * int* 'a
-> 'a
)
617 -> ('a immarray2
* int * int * int option
* int option
)
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
.
626 fun modifyi RowMajor
f (IA2 ia2
, i
, j
, rlen
, clen
)
627 = IA2 (ImmArray
.modifyi (fn (r
,ia
) => ImmArray
.modifyi (fn (c
,x
)
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
);
639 (* ************************************************************************* *)
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
.
656 signature REGISTERFILE
661 val InitRegisterFile
: unit
-> registerfile
;
663 val LoadRegister
: registerfile
* int -> Word32
.word;
665 val StoreRegister
: registerfile
* int * Word32
.word -> registerfile
;
669 (*****************************************************************************)
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
.
685 * The underlying
structure of registerfile is an immutable array
of
689 structure RegisterFile
: REGISTERFILE
692 type registerfile
= Word32
.word ImmArray
.immarray
;
694 fun InitRegisterFile ()
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
;
705 fun LoadRegister (rf
, reg
) = ImmArray
.sub(rf
, reg
);
707 fun StoreRegister (rf
, reg
, data
) = ImmArray
.update(rf
, reg
, data
);
712 (*****************************************************************************)
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.
727 datatype ALUOp
= SLL | SRL | SRA |
735 val PerformAL
: (ALUOp
* Word32
.word * Word32
.word) -> Word32
.word;
739 (*****************************************************************************)
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.
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
.
765 datatype ALUOp
= SLL | SRL | SRA |
773 fun PerformAL (opcode
, s1
, s2
) =
776 Word32
.<< (s1
, Word.fromLarge (Word32
.toLarge s2
))
778 Word32
.>> (s1
, Word.fromLarge (Word32
.toLarge s2
))
780 Word32
.~
>> (s1
, Word.fromLarge (Word32
.toLarge s2
))
782 Word32
.fromInt (Int.+ (Word32
.toIntX s1
,
787 Word32
.fromInt (Int.- (Word32
.toIntX s1
,
799 then 0wx00000001
: Word32
.word
800 else 0wx00000000
: Word32
.word
803 then 0wx00000001
: Word32
.word
804 else 0wx00000000
: Word32
.word
806 if Int.< (Word32
.toIntX s1
, Word32
.toIntX s2
)
807 then 0wx00000001
: Word32
.word
808 else 0wx00000000
: Word32
.word
810 if Int.> (Word32
.toIntX s1
, Word32
.toIntX s2
)
811 then 0wx00000001
: Word32
.word
812 else 0wx00000000
: Word32
.word
814 if Int.<= (Word32
.toIntX s1
, Word32
.toIntX s2
)
815 then 0wx00000001
: Word32
.word
816 else 0wx00000000
: Word32
.word
818 if Int.>= (Word32
.toIntX s1
, Word32
.toIntX s2
)
819 then 0wx00000001
: Word32
.word
820 else 0wx00000000
: Word32
.word)
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.
827 (print
"Error : ALU returning 0\n";
828 0wx00000000
: Word32
.word);
832 (*****************************************************************************)
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.
860 val InitMemory
: unit
-> memory
;
862 val LoadWord
: memory
* Word32
.word -> memory
* Word32
.word;
863 val StoreWord
: memory
* Word32
.word * Word32
.word -> memory
;
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
;
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
;
873 val GetStatistics
: memory
-> string;
881 (*****************************************************************************)
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.
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
.
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
.
914 structure Memory
: MEMORY
917 type memory
= Word32
.word ImmArray
.immarray
* (int * int);
920 (ImmArray
.immarray(Word32
.toInt(0wx10000
: Word32
.word),
921 0wx00000000
: Word32
.word),
924 fun AlignWAddress address
925 = Word32
.<< (Word32
.>> (address
, 0wx0002
), 0wx0002
);
927 fun AlignHWAddress address
928 = Word32
.<< (Word32
.>> (address
, 0wx0001
), 0wx0001
);
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
.
943 fun Load ((mem
, (reads
, writes
)), address
)
945 val aligned_address
= AlignWAddress address
;
946 val use_address
= Word32
.>> (aligned_address
, 0wx0002
);
948 ((mem
, (reads
+ 1, writes
)),
949 ImmArray
.sub(mem
, Word32
.toInt(use_address
)))
952 fun Store ((mem
, (reads
, writes
)), address
, data
)
954 val aligned_address
= AlignWAddress address
;
955 val use_address
= Word32
.>> (aligned_address
, 0wx0002
);
957 (ImmArray
.update(mem
, Word32
.toInt(use_address
), data
),
962 fun LoadWord (mem
, address
)
965 = if address
= AlignWAddress address
967 else (print
"Error LW: Memory using aligned address\n";
968 AlignWAddress address
);
970 Load(mem
, aligned_address
)
973 fun StoreWord (mem
, address
, data
)
976 = if address
= AlignWAddress address
978 else (print
"Error SW: Memory using aligned address\n";
979 AlignWAddress address
);
981 Store(mem
, aligned_address
, data
)
984 fun LoadHWord (mem
, address
)
987 = if address
= AlignHWAddress address
989 else (print
"Error LH: Memory using aligned address\n";
990 AlignHWAddress address
);
991 val (nmem
,l_word
) = Load(mem
, aligned_address
);
995 of 0wx00000000
: Word32
.word
996 => Word32
.~
>>(Word32
.<<(l_word
, 0wx0010
),
998 |
0wx00000010
: Word32
.word
999 => Word32
.~
>>(Word32
.<<(l_word
, 0wx0000
),
1001 | _
=> (print
"Error LH: Memory returning 0\n";
1002 0wx00000000
: Word32
.word))
1005 fun LoadHWordU (mem
, address
)
1008 = if address
= AlignHWAddress address
1010 else (print
"Error LHU: Memory using aligned address\n";
1011 AlignHWAddress address
);
1012 val (nmem
, l_word
) = Load(mem
, aligned_address
);
1015 case aligned_address
1016 of 0wx00000000
: Word32
.word
1017 => Word32
.>>(Word32
.<<(l_word
, 0wx0010
),
1019 |
0wx00000010
: Word32
.word
1020 => Word32
.>>(Word32
.<<(l_word
, 0wx0000
),
1022 | _
=> (print
"Error LHU: Memory returning 0\n";
1023 0wx00000000
: Word32
.word))
1026 fun StoreHWord (mem
, address
, data
)
1029 = if address
= AlignHWAddress address
1031 else (print
"Error SH: Memory using aligned address\n";
1032 AlignWAddress address
);
1033 val (_
, s_word
) = Load(mem
, aligned_address
);
1035 case aligned_address
1036 of 0wx00000000
: Word32
.word
1037 => Store(mem
, aligned_address
,
1038 Word32
.orb(Word32
.andb(0wxFFFF0000
: Word32
.word,
1040 Word32
.<<(Word32
.andb(0wx0000FFFF
:
1044 |
0wx00000010
: Word32
.word
1045 => Store(mem
, aligned_address
,
1046 Word32
.orb(Word32
.andb(0wx0000FFFF
: Word32
.word,
1048 Word32
.<<(Word32
.andb(0wx0000FFFF
:
1052 | _
=> (print
"Error SH: Memory unchanged\n";
1056 fun LoadByte (mem
, address
)
1058 val aligned_address
= address
;
1059 val (nmem
, l_word
) = Load(mem
, aligned_address
);
1062 case aligned_address
1063 of 0wx00000000
: Word32
.word
1064 => Word32
.~
>>(Word32
.<<(l_word
,
1067 |
0wx00000008
: Word32
.word
1068 => Word32
.~
>>(Word32
.<<(l_word
,
1071 |
0wx00000010
: Word32
.word
1072 => Word32
.~
>>(Word32
.<<(l_word
,
1075 |
0wx00000018
: Word32
.word
1076 => Word32
.~
>>(Word32
.<<(l_word
,
1079 | _
=> (print
"Error LB: Memory returning 0\n";
1080 0wx00000000
: Word32
.word))
1083 fun LoadByteU (mem
, address
)
1085 val aligned_address
= address
;
1086 val (nmem
, l_word
) = Load(mem
, aligned_address
);
1089 case aligned_address
1090 of 0wx00000000
: Word32
.word
1091 => Word32
.>>(Word32
.<<(l_word
,
1094 |
0wx00000008
: Word32
.word
1095 => Word32
.>>(Word32
.<<(l_word
,
1098 |
0wx00000010
: Word32
.word
1099 => Word32
.>>(Word32
.<<(l_word
,
1102 |
0wx00000018
: Word32
.word
1103 => Word32
.>>(Word32
.<<(l_word
,
1106 | _
=> (print
"Error LBU: Memory returning 0\n";
1107 0wx00000000
: Word32
.word))
1110 fun StoreByte (mem
, address
, data
)
1112 val aligned_address
= address
;
1113 val (_
, s_word
) = Load(mem
, aligned_address
);
1115 case aligned_address
1116 of 0wx00000000
: Word32
.word
1117 => Store(mem
, aligned_address
,
1118 Word32
.orb(Word32
.andb(0wxFFFFFF00
: Word32
.word,
1120 Word32
.<<(Word32
.andb(0wx000000FF
:
1124 |
0wx00000008
: Word32
.word
1125 => Store(mem
, aligned_address
,
1126 Word32
.orb(Word32
.andb(0wxFFFF00FF
: Word32
.word,
1128 Word32
.<<(Word32
.andb(0wx000000FF
:
1132 |
0wx00000010
: Word32
.word
1133 => Store(mem
, aligned_address
,
1134 Word32
.orb(Word32
.andb(0wxFF00FFFF
: Word32
.word,
1136 Word32
.<<(Word32
.andb(0wx000000FF
:
1140 |
0wx00000018
: Word32
.word
1141 => Store(mem
, aligned_address
,
1142 Word32
.orb(Word32
.andb(0wx00FFFFFF
: Word32
.word,
1144 Word32
.<<(Word32
.andb(0wx000000FF
:
1148 | _
=> (print
"Error SB: Memory unchanged\n";
1152 fun GetStatistics (mem
, (reads
, writes
))
1154 "Memory Reads : " ^
(Int.toString reads
) ^
"\n" ^
1155 "Memory Writes : " ^
(Int.toString writes
) ^
"\n";
1159 (*****************************************************************************)
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
1179 datatype WriteHitOption
= Write_Through
1182 datatype WriteMissOption
= Write_Allocate
1183 | Write_No_Allocate
;
1185 val CacheName
: string;
1186 val CacheSize
: int;
1187 val BlockSize
: int;
1188 val Associativity
: int;
1189 val WriteHit
: WriteHitOption
;
1190 val WriteMiss
: WriteMissOption
;
1194 (*****************************************************************************)
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.
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
.
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
.
1232 functor CachedMemory (structure CS
: CACHESPEC
;
1233 structure MEM
: MEMORY
;) : MEMORY
1237 = bool * bool * Word32
.word * Word32
.word ImmArray
.immarray
;
1240 = cacheline ImmArray
.immarray
;
1243 = cacheset ImmArray
.immarray
;
1245 type memory
= (cache
* (int * int * int * int)) * MEM
.memory
;
1248 (* Performs log
[base2
] on an integer
. *)
1250 | exp2 n
= 2 * (exp2 (n
-1))
1252 fun log2_aux n
= if exp2 n
> x
1262 * The following values
of index size
and field bits are
1263 * calculated from the values
in the cache specification
1266 val IndexSize
= CacheSize
div (BlockSize
* Associativity
);
1267 val BlockOffsetBits
= log2 (BlockSize
* 4);
1268 val IndexBits
= log2 IndexSize
;
1269 val TagBits
= 32 - BlockOffsetBits
- IndexBits
;
1273 * RandEntry returns a random number between
1274 * [0, Associativity
- 1]. It is used to determine
1275 * replacement
of data
in the cache
.
1278 val modulus
= Word.fromInt(Associativity
- 1)
1280 fn () => Word.toInt(Word.mod(rand (),
1285 * The InitCache function initializes the cache to
1286 * not
-valid
, not
-dirty
, 0wx00000000 tag
, blocks initialized
1291 val cacheline
= (false, false, 0wx00000000
: Word32
.word,
1292 ImmArray
.immarray (BlockSize
,
1293 0wx00000000
: Word32
.word));
1294 val cacheset
= ImmArray
.immarray (Associativity
, cacheline
);
1296 (ImmArray
.immarray (IndexSize
, cacheset
),
1302 * The InitMemory function initializes the cache
1303 * and the memory being cached
.
1305 fun InitMemory () = (InitCache (), MEM
.InitMemory ()) : memory
;
1309 * GetTag returns the Word32
.word corresponding to the tag field
of
1313 = Word32
.>> (address
,
1314 Word.fromInt (IndexBits
+ BlockOffsetBits
));
1318 * GetIndex returns the Word32
.word corresponding to the index
1321 fun GetIndex address
1326 (Word32
.>> (0wxFFFFFFFF
: Word32
.word,
1327 Word.fromInt (IndexBits
+ BlockOffsetBits
)),
1328 Word.fromInt (IndexBits
+ BlockOffsetBits
)));
1330 Word32
.>> (Word32
.andb (address
, mask
),
1331 Word.fromInt (BlockOffsetBits
))
1336 * GetBlockOffset returns the Word32
.word corresponding to the
1337 * block offset field
of address
.
1339 fun GetBlockOffset address
1344 (Word32
.>> (0wxFFFFFFFF
: Word32
.word,
1345 Word.fromInt BlockOffsetBits
),
1346 Word.fromInt BlockOffsetBits
));
1348 Word32
.andb (address
, mask
)
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
).
1357 fun InCache_aux_entry ((valid
, dirty
, tag
, block
), address
)
1358 = tag
= (GetTag address
) andalso valid
;
1360 fun InCache_aux_set (set
, address
)
1361 = ImmArray
.foldr (fn (entry
, result
) =>
1362 (InCache_aux_entry (entry
, address
)) orelse
1367 fun InCache (cac
, address
)
1368 = InCache_aux_set (ImmArray
.sub (cac
,
1369 Word32
.toInt (GetIndex address
)),
1373 * The ReadCache
* family
of functions returns the Word32
.word
1374 * stored at address
in the cache
.
1376 fun ReadCache_aux_entry ((valid
, dirty
, tag
, block
), address
)
1377 = ImmArray
.sub (block
,
1378 Word32
.toInt (Word32
.>> (GetBlockOffset address
,
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
)
1386 (0wx00000000
: Word32
.word)
1389 fun ReadCache (cac
, address
)
1390 = ReadCache_aux_set (ImmArray
.sub (cac
,
1391 Word32
.toInt(GetIndex address
)),
1396 * The WriteCache
* family
of functions returns the updated
1397 * cache
with data stored at address
.
1399 fun WriteCache_aux_entry ((valid
, dirty
, tag
, block
), address
, data
)
1401 val ndirty
= case WriteHit
1402 of Write_Through
=> false
1403 | Write_Back
=> true;
1406 ImmArray
.update (block
,
1407 Word32
.toInt (Word32
.>>
1408 (GetBlockOffset address
,
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
,
1421 fun WriteCache (cac
, address
, data
)
1423 val index
= Word32
.toInt (GetIndex address
);
1424 val nset
= WriteCache_aux_set (ImmArray
.sub (cac
, index
),
1427 ImmArray
.update (cac
, index
, nset
)
1432 * The LoadBlock function returns the updated
1433 * memory
and the block containing address loaded from memory
.
1435 fun LoadBlock (mem
, address
)
1436 = ImmArray
.foldr (fn (offset
, (block
, mem
)) =>
1439 = Word32
.+ (Word32
.<<
1446 Word32
.<< (Word32
.fromInt
1449 val (nmem
, nword
) = MEM
.LoadWord (mem
,
1452 (ImmArray
.update (block
, offset
, nword
), nmem
)
1454 (ImmArray
.immarray (BlockSize
,
1455 0wx00000000
: Word32
.word), mem
)
1456 (ImmArray
.tabulate (BlockSize
, fn i
=> i
));
1460 * The StoreBlock functionsreturns the updated
1461 * memory
with block stored into the block containing address
.
1463 fun StoreBlock (block
, mem
, address
)
1464 = ImmArray
.foldr (fn (offset
, mem
) =>
1467 = Word32
.+ (Word32
.<<
1474 Word32
.<< (Word32
.fromInt
1478 MEM
.StoreWord (mem
, saddress
,
1479 ImmArray
.sub (block
, offset
))
1482 (ImmArray
.tabulate (BlockSize
, fn i
=> i
));
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
.
1491 fun LoadCache_aux_entry ((valid
, dirty
, tag
, block
), mem
, address
)
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
)
1501 val (nblock
, nnmem
) = LoadBlock (nmem
, address
);
1503 ((true, false, GetTag address
, nblock
), nnmem
)
1506 fun LoadCache_aux_set (set
, mem
, address
)
1508 val entry
= RandEntry ();
1509 val (nentry
, nmem
) = LoadCache_aux_entry (ImmArray
.sub (set
,
1513 (ImmArray
.update (set
, entry
, nentry
), nmem
)
1516 fun LoadCache (cac
, mem
, address
)
1518 val index
= Word32
.toInt (GetIndex address
);
1520 = LoadCache_aux_set (ImmArray
.sub (cac
, index
),
1523 (ImmArray
.update (cac
, index
, nset
), nmem
)
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
1534 fun AlignWAddress address
1535 = Word32
.<< (Word32
.>> (address
, 0wx0002
), 0wx0002
);
1537 fun AlignHWAddress address
1538 = Word32
.<< (Word32
.>> (address
, 0wx0001
), 0wx0001
);
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
.
1553 fun Load (((cac
, (rh
, rm
, wh
, wm
)), mem
), address
)
1555 val aligned_address
= AlignWAddress address
;
1557 if InCache (cac
, aligned_address
)
1558 then (((cac
, (rh
+ 1, rm
, wh
, wm
)), mem
),
1559 ReadCache (cac
, aligned_address
))
1562 = LoadCache (cac
, mem
, aligned_address
);
1564 (((ncac
, (rh
, rm
+ 1, wh
, wm
)), nmem
),
1565 ReadCache (ncac
, aligned_address
))
1570 fun Store (((cac
, (rh
, rm
, wh
, wm
)), mem
), address
, data
)
1572 val aligned_address
= AlignWAddress address
;
1574 if InCache (cac
, aligned_address
)
1576 val ncac
= WriteCache (cac
, aligned_address
, data
);
1580 ((ncac
, (rh
, rm
, wh
+ 1, wm
)),
1581 MEM
.StoreWord (mem
, aligned_address
, data
))
1583 ((ncac
, (rh
, rm
, wh
+ 1, wm
)), mem
)
1586 of Write_Allocate
=>
1589 = LoadCache (cac
, mem
, aligned_address
);
1591 = WriteCache (ncac
, aligned_address
, data
);
1595 ((nncac
, (rh
, rm
, wh
, wm
+ 1)),
1596 MEM
.StoreWord (nmem
, aligned_address
,
1599 ((nncac
, (rh
, rm
, wh
, wm
+ 1)),
1602 | Write_No_Allocate
=>
1603 ((cac
, (rh
, rm
, wh
, wm
+ 1)),
1604 MEM
.StoreWord (mem
, aligned_address
, data
))
1607 fun LoadWord (mem
, address
)
1610 = if address
= AlignWAddress address
1612 else (print
"Error LW: Memory using aligned address\n";
1613 AlignWAddress address
);
1615 Load(mem
, aligned_address
)
1618 fun StoreWord (mem
, address
, data
)
1621 = if address
= AlignWAddress address
1623 else (print
"Error SW: Memory using aligned address\n";
1624 AlignWAddress address
);
1626 Store(mem
, aligned_address
, data
)
1629 fun LoadHWord (mem
, address
)
1632 = if address
= AlignHWAddress address
1634 else (print
"Error LH: Memory using aligned address\n";
1635 AlignHWAddress address
);
1636 val (nmem
,l_word
) = Load(mem
, aligned_address
);
1639 case aligned_address
1640 of 0wx00000000
: Word32
.word
1641 => Word32
.~
>>(Word32
.<<(l_word
, 0wx0010
),
1643 |
0wx00000010
: Word32
.word
1644 => Word32
.~
>>(Word32
.<<(l_word
, 0wx0000
),
1646 | _
=> (print
"Error LH: Memory returning 0\n";
1647 0wx00000000
: Word32
.word))
1650 fun LoadHWordU (mem
, address
)
1653 = if address
= AlignHWAddress address
1655 else (print
"Error LHU: Memory using aligned address\n";
1656 AlignHWAddress address
);
1657 val (nmem
, l_word
) = Load(mem
, aligned_address
);
1660 case aligned_address
1661 of 0wx00000000
: Word32
.word
1662 => Word32
.>>(Word32
.<<(l_word
, 0wx0010
),
1664 |
0wx00000010
: Word32
.word
1665 => Word32
.>>(Word32
.<<(l_word
, 0wx0000
),
1667 | _
=> (print
"Error LHU: Memory returning 0\n";
1668 0wx00000000
: Word32
.word))
1671 fun StoreHWord (mem
, address
, data
)
1674 = if address
= AlignHWAddress address
1676 else (print
"Error SH: Memory using aligned address\n";
1677 AlignWAddress address
);
1678 val (_
, s_word
) = Load(mem
, aligned_address
);
1680 case aligned_address
1681 of 0wx00000000
: Word32
.word
1682 => Store(mem
, aligned_address
,
1683 Word32
.orb(Word32
.andb(0wxFFFF0000
: Word32
.word,
1685 Word32
.<<(Word32
.andb(0wx0000FFFF
:
1689 |
0wx00000010
: Word32
.word
1690 => Store(mem
, aligned_address
,
1691 Word32
.orb(Word32
.andb(0wx0000FFFF
: Word32
.word,
1693 Word32
.<<(Word32
.andb(0wx0000FFFF
:
1697 | _
=> (print
"Error SH: Memory unchanged\n";
1701 fun LoadByte (mem
, address
)
1703 val aligned_address
= address
;
1704 val (nmem
, l_word
) = Load(mem
, aligned_address
);
1707 case aligned_address
1708 of 0wx00000000
: Word32
.word
1709 => Word32
.~
>>(Word32
.<<(l_word
,
1712 |
0wx00000008
: Word32
.word
1713 => Word32
.~
>>(Word32
.<<(l_word
,
1716 |
0wx00000010
: Word32
.word
1717 => Word32
.~
>>(Word32
.<<(l_word
,
1720 |
0wx00000018
: Word32
.word
1721 => Word32
.~
>>(Word32
.<<(l_word
,
1724 | _
=> (print
"Error LB: Memory returning 0\n";
1725 0wx00000000
: Word32
.word))
1728 fun LoadByteU (mem
, address
)
1730 val aligned_address
= address
;
1731 val (nmem
, l_word
) = Load(mem
, aligned_address
);
1734 case aligned_address
1735 of 0wx00000000
: Word32
.word
1736 => Word32
.>>(Word32
.<<(l_word
,
1739 |
0wx00000008
: Word32
.word
1740 => Word32
.>>(Word32
.<<(l_word
,
1743 |
0wx00000010
: Word32
.word
1744 => Word32
.>>(Word32
.<<(l_word
,
1747 |
0wx00000018
: Word32
.word
1748 => Word32
.>>(Word32
.<<(l_word
,
1751 | _
=> (print
"Error LBU: Memory returning 0\n";
1752 0wx00000000
: Word32
.word))
1755 fun StoreByte (mem
, address
, data
)
1757 val aligned_address
= address
;
1758 val (_
, s_word
) = Load(mem
, aligned_address
);
1760 case aligned_address
1761 of 0wx00000000
: Word32
.word
1762 => Store(mem
, aligned_address
,
1763 Word32
.orb(Word32
.andb(0wxFFFFFF00
: Word32
.word,
1765 Word32
.<<(Word32
.andb(0wx000000FF
:
1769 |
0wx00000008
: Word32
.word
1770 => Store(mem
, aligned_address
,
1771 Word32
.orb(Word32
.andb(0wxFFFF00FF
: Word32
.word,
1773 Word32
.<<(Word32
.andb(0wx000000FF
:
1777 |
0wx00000010
: Word32
.word
1778 => Store(mem
, aligned_address
,
1779 Word32
.orb(Word32
.andb(0wxFF00FFFF
: Word32
.word,
1781 Word32
.<<(Word32
.andb(0wx000000FF
:
1785 |
0wx00000018
: Word32
.word
1786 => Store(mem
, aligned_address
,
1787 Word32
.orb(Word32
.andb(0wx00FFFFFF
: Word32
.word,
1789 Word32
.<<(Word32
.andb(0wx000000FF
:
1793 | _
=> (print
"Error SB: Memory unchanged\n";
1797 fun GetStatistics ((cac
, (rh
, rm
, wh
, wm
)), mem
)
1804 val who
= case WriteHit
1805 of Write_Through
=> "Write Through"
1806 | Write_Back
=> "Write Back";
1808 val wmo
= case WriteMiss
1809 of Write_Allocate
=> "Write Allocate"
1810 | Write_No_Allocate
=> "Write No Allocate";
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
)
1830 (*****************************************************************************)
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
.
1841 signature DLXSIMULATOR
1844 val run_file
: string -> unit
;
1845 val run_prog
: string list
-> unit
;
1849 (*****************************************************************************)
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
.
1862 functor DLXSimulatorFun (structure RF
: REGISTERFILE
;
1863 structure ALU
: ALU
;
1864 structure MEM
: MEMORY
; ) : DLXSIMULATOR
1868 * The
datatype Opcode provides a means
of differentiating
*
1869 * among the main opcodes
.
1872 (* for R
-type opcodes
*)
1874 (* I
-type opcodes
*)
1876 ADDI | ADDUI | SUBI | SUBUI |
1879 SLLI | SRLI | SRAI |
1880 SEQI | SNEI | SLTI | SGTI | SLEI | SGEI |
1884 (* J
-type opcodes
*)
1885 J | JAL | TRAP | JR | JALR |
1886 (* Unrecognized opcode
*)
1890 * The
datatype RRFuncCode provides a means
of
1891 * differentiating among
1892 * the register
-register function codes
.
1894 datatype RRFunctCode
= NOP | SLL | SRL | SRA |
1895 ADD | ADDU | SUB | SUBU |
1897 SEQ | SNE | SLT | SGT | SLE | SGE |
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.
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
1916 * The value HALT is set to the DLX instruction TRAP #
0,
1917 * and is used to check for the halt
of the program
.
1919 val HALT
= JTYPE (TRAP
, 0wx00000000
);
1922 * The function DecodeIType decodes a Word32
.word into an
1923 * I
-type instruction
.
1925 fun DecodeIType instr
1927 val opc
= Word32
.andb (Word32
.>> (instr
,
1929 0wx0000003F
: Word32
.word);
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";
1962 val rs1
= Word32
.toInt(Word32
.andb (Word32
.>> (instr
, 0wx0015
),
1963 0wx0000001F
: Word32
.word));
1965 val rd
= Word32
.toInt(Word32
.andb (Word32
.>> (instr
, 0wx0010
),
1966 0wx0000001F
: Word32
.word));
1968 val immediate
= Word32
.~
>> (Word32
.<< (instr
, 0wx0010
),
1974 else ITYPE (opcode
, rs1
, rd
, immediate
)
1978 * The function DecodeRType decodes a Word32
.word into an
1979 * R
-type instruction
.
1981 fun DecodeRType instr
1984 val rs1
= Word32
.toInt (Word32
.andb (Word32
.>> (instr
, 0wx0015
),
1985 0wx0000001F
: Word32
.word));
1987 val rs2
= Word32
.toInt (Word32
.andb (Word32
.>> (instr
, 0wx0010
),
1988 0wx0000001F
: Word32
.word));
1990 val rd
= Word32
.toInt (Word32
.andb (Word32
.>> (instr
, 0wx000B
),
1991 0wx0000001F
: Word32
.word));
1994 = Word32
.toInt (Word32
.andb (Word32
.>> (instr
, 0wx0006
),
1995 0wx0000001F
: Word32
.word));
1997 val funct
= Word32
.andb (instr
, 0wx0000003F
: Word32
.word);
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";
2021 if functcode
= NON_FUNCT
2023 else RTYPE (SPECIAL
, rs1
, rs2
, rd
, shamt
, functcode
)
2027 * The function DecodeJType decodes a Word32
.word into an
2028 * J
-type instruction
.
2030 fun DecodeJType instr
2033 val opc
= Word32
.andb (Word32
.>> (instr
, 0wx1A
),
2034 0wx0000003F
: Word32
.word);
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";
2045 val offset
= Word32
.~
>> (Word32
.<< (instr
, 0wx0006
),
2051 else JTYPE (opcode
, offset
)
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
.
2060 fun DecodeInstr instr
2063 val opcode
= Word32
.andb (Word32
.>> (instr
, 0wx1A
),
2064 0wx0000003F
: Word32
.word);
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";
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
.
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
,
2114 (Word32
.<< (immediate
,
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
,
2123 (Word32
.<< (immediate
,
2128 |
PerformIType ((ADDI
, rs1
, rd
, immediate
), (PC
, rf
, mem
))
2130 RF
.StoreRegister(rf
, rd
,
2131 ALU
.PerformAL(ALU
.ADD
,
2132 RF
.LoadRegister(rf
, rs1
),
2136 |
PerformIType ((ADDUI
, rs1
, rd
, immediate
), (PC
, rf
, mem
))
2138 RF
.StoreRegister(rf
, rd
,
2139 ALU
.PerformAL(ALU
.ADDU
,
2140 RF
.LoadRegister(rf
, rs1
),
2144 |
PerformIType ((SUBI
, rs1
, rd
, immediate
), (PC
, rf
, mem
))
2146 RF
.StoreRegister(rf
, rd
,
2147 ALU
.PerformAL(ALU
.SUB
,
2148 RF
.LoadRegister(rf
, rs1
),
2152 |
PerformIType ((SUBUI
, rs1
, rd
, immediate
), (PC
, rf
, mem
))
2154 RF
.StoreRegister(rf
, rd
,
2155 ALU
.PerformAL(ALU
.SUBU
,
2156 RF
.LoadRegister(rf
, rs1
),
2160 |
PerformIType ((ANDI
, rs1
, rd
, immediate
), (PC
, rf
, mem
))
2162 RF
.StoreRegister(rf
, rd
,
2163 ALU
.PerformAL(ALU
.AND
,
2164 RF
.LoadRegister(rf
, rs1
),
2168 |
PerformIType ((ORI
, rs1
, rd
, immediate
), (PC
, rf
, mem
))
2170 RF
.StoreRegister(rf
, rd
,
2171 ALU
.PerformAL(ALU
.OR
,
2172 RF
.LoadRegister(rf
, rs1
),
2176 |
PerformIType ((XORI
, rs1
, rd
, immediate
), (PC
, rf
, mem
))
2178 RF
.StoreRegister(rf
, rd
,
2179 ALU
.PerformAL(ALU
.XOR
,
2180 RF
.LoadRegister(rf
, rs1
),
2184 |
PerformIType ((LHI
, rs1
, rd
, immediate
), (PC
, rf
, mem
))
2185 = (PC
, RF
.StoreRegister(rf
, rd
, Word32
.<< (immediate
, 0wx0010
)), mem
)
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
))),
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
))),
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
))),
2205 |
PerformIType ((SEQI
, rs1
, rd
, immediate
), (PC
, rf
, mem
))
2207 RF
.StoreRegister(rf
, rd
,
2208 ALU
.PerformAL(ALU
.SEQ
,
2209 RF
.LoadRegister(rf
, rs1
),
2213 |
PerformIType ((SNEI
, rs1
, rd
, immediate
), (PC
, rf
, mem
))
2215 RF
.StoreRegister(rf
, rd
,
2216 ALU
.PerformAL(ALU
.SNE
,
2217 RF
.LoadRegister(rf
, rs1
),
2221 |
PerformIType ((SLTI
, rs1
, rd
, immediate
), (PC
, rf
, mem
))
2223 RF
.StoreRegister(rf
, rd
,
2224 ALU
.PerformAL(ALU
.SLT
,
2225 RF
.LoadRegister(rf
, rs1
),
2229 |
PerformIType ((SGTI
, rs1
, rd
, immediate
), (PC
, rf
, mem
))
2231 RF
.StoreRegister(rf
, rd
,
2232 ALU
.PerformAL(ALU
.SGT
,
2233 RF
.LoadRegister(rf
, rs1
),
2237 |
PerformIType ((SLEI
, rs1
, rd
, immediate
), (PC
, rf
, mem
))
2239 RF
.StoreRegister(rf
, rd
,
2240 ALU
.PerformAL(ALU
.SLE
,
2241 RF
.LoadRegister(rf
, rs1
),
2245 |
PerformIType ((SGEI
, rs1
, rd
, immediate
), (PC
, rf
, mem
))
2247 RF
.StoreRegister(rf
, rd
,
2248 ALU
.PerformAL(ALU
.SGE
,
2249 RF
.LoadRegister(rf
, rs1
),
2253 |
PerformIType ((LB
, rs1
, rd
, immediate
), (PC
, rf
, mem
))
2256 = MEM
.LoadByte(mem
, Word32
.+ (RF
.LoadRegister(rf
, rs1
),
2260 RF
.StoreRegister(rf
, rd
, l_byte
),
2264 |
PerformIType ((LBU
, rs1
, rd
, immediate
), (PC
, rf
, mem
))
2267 = MEM
.LoadByteU(mem
, Word32
.+ (RF
.LoadRegister(rf
, rs1
),
2271 RF
.StoreRegister(rf
, rd
, l_byte
),
2275 |
PerformIType ((SB
, rs1
, rd
, immediate
), (PC
, rf
, mem
))
2279 Word32
.+ (RF
.LoadRegister(rf
, rs1
), immediate
),
2280 Word32
.andb(0wx000000FF
, RF
.LoadRegister(rf
, rd
))))
2282 |
PerformIType ((LH
, rs1
, rd
, immediate
), (PC
, rf
, mem
))
2285 = MEM
.LoadHWord(mem
, Word32
.+ (RF
.LoadRegister(rf
, rs1
),
2289 RF
.StoreRegister(rf
, rd
, l_hword
),
2293 |
PerformIType ((LHU
, rs1
, rd
, immediate
), (PC
, rf
, mem
))
2296 = MEM
.LoadHWordU(mem
, Word32
.+ (RF
.LoadRegister(rf
, rs1
),
2300 RF
.StoreRegister(rf
, rd
, l_hword
),
2304 |
PerformIType ((SH
, rs1
, rd
, immediate
), (PC
, rf
, mem
))
2308 Word32
.+ (RF
.LoadRegister(rf
, rs1
), immediate
),
2309 Word32
.andb(0wx0000FFFF
, RF
.LoadRegister(rf
, rd
))))
2312 |
PerformIType ((LW
, rs1
, rd
, immediate
), (PC
, rf
, mem
))
2315 = MEM
.LoadWord(mem
, Word32
.+ (RF
.LoadRegister(rf
, rs1
),
2319 RF
.StoreRegister(rf
, rd
, l_word
),
2323 |
PerformIType ((SW
, rs1
, rd
, immediate
), (PC
, rf
, mem
))
2327 Word32
.+ (RF
.LoadRegister(rf
, rs1
), immediate
),
2328 RF
.LoadRegister(rf
, rd
)))
2330 |
PerformIType ((_
, rs1
, rd
, immediate
), (PC
, rf
, mem
))
2331 = (print
"Error : Non I-Type opcode, performing NOP\n";
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
.
2340 fun PerformRType ((SPECIA
, rs1
, rs2
, rd
, shamt
, NOP
), (PC
, rf
, mem
))
2343 |
PerformRType ((SPECIAL
, rs1
, rs2
, rd
, shamt
, SLL
), (PC
, rf
, mem
))
2345 RF
.StoreRegister(rf
, rd
,
2346 ALU
.PerformAL(ALU
.SLL
,
2347 RF
.LoadRegister(rf
, rs1
),
2348 RF
.LoadRegister(rf
, rs2
))),
2351 |
PerformRType ((SPECIAL
, rs1
, rs2
, rd
, shamt
, SRL
), (PC
, rf
, mem
))
2353 RF
.StoreRegister(rf
, rd
,
2354 ALU
.PerformAL(ALU
.SRL
,
2355 RF
.LoadRegister(rf
, rs1
),
2356 RF
.LoadRegister(rf
, rs2
))),
2359 |
PerformRType ((SPECIAL
, rs1
, rs2
, rd
, shamt
, SRA
), (PC
, rf
, mem
))
2361 RF
.StoreRegister(rf
, rd
,
2362 ALU
.PerformAL(ALU
.SRA
,
2363 RF
.LoadRegister(rf
, rs1
),
2364 RF
.LoadRegister(rf
, rs2
))),
2367 |
PerformRType ((SPECIAL
, rs1
, rs2
, rd
, shamt
, ADD
), (PC
, rf
, mem
))
2369 RF
.StoreRegister(rf
, rd
,
2370 ALU
.PerformAL(ALU
.ADD
,
2371 RF
.LoadRegister(rf
, rs1
),
2372 RF
.LoadRegister(rf
, rs2
))),
2375 |
PerformRType ((SPECIAL
, rs1
, rs2
, rd
, shamt
, ADDU
), (PC
, rf
, mem
))
2377 RF
.StoreRegister(rf
, rd
,
2378 ALU
.PerformAL(ALU
.ADDU
,
2379 RF
.LoadRegister(rf
, rs1
),
2380 RF
.LoadRegister(rf
, rs2
))),
2383 |
PerformRType ((SPECIAL
, rs1
, rs2
, rd
, shamt
, SUB
), (PC
, rf
, mem
))
2385 RF
.StoreRegister(rf
, rd
,
2386 ALU
.PerformAL(ALU
.SUB
,
2387 RF
.LoadRegister(rf
, rs1
),
2388 RF
.LoadRegister(rf
, rs2
))),
2391 |
PerformRType ((SPECIAL
, rs1
, rs2
, rd
, shamt
, SUBU
), (PC
, rf
, mem
))
2393 RF
.StoreRegister(rf
, rd
,
2394 ALU
.PerformAL(ALU
.SUBU
,
2395 RF
.LoadRegister(rf
, rs1
),
2396 RF
.LoadRegister(rf
, rs2
))),
2399 |
PerformRType ((SPECIAL
, rs1
, rs2
, rd
, shamt
, AND
), (PC
, rf
, mem
))
2401 RF
.StoreRegister(rf
, rd
,
2402 ALU
.PerformAL(ALU
.AND
,
2403 RF
.LoadRegister(rf
, rs1
),
2404 RF
.LoadRegister(rf
, rs2
))),
2407 |
PerformRType ((SPECIAL
, rs1
, rs2
, rd
, shamt
, OR
), (PC
, rf
, mem
))
2409 RF
.StoreRegister(rf
, rd
,
2410 ALU
.PerformAL(ALU
.OR
,
2411 RF
.LoadRegister(rf
, rs1
),
2412 RF
.LoadRegister(rf
, rs2
))),
2415 |
PerformRType ((SPECIAL
, rs1
, rs2
, rd
, shamt
, XOR
), (PC
, rf
, mem
))
2417 RF
.StoreRegister(rf
, rd
,
2418 ALU
.PerformAL(ALU
.XOR
,
2419 RF
.LoadRegister(rf
, rs1
),
2420 RF
.LoadRegister(rf
, rs2
))),
2423 |
PerformRType ((SPECIAL
, rs1
, rs2
, rd
, shamt
, SEQ
), (PC
, rf
, mem
))
2425 RF
.StoreRegister(rf
, rd
,
2426 ALU
.PerformAL(ALU
.SEQ
,
2427 RF
.LoadRegister(rf
, rs1
),
2428 RF
.LoadRegister(rf
, rs2
))),
2431 |
PerformRType ((SPECIAL
, rs1
, rs2
, rd
, shamt
, SNE
), (PC
, rf
, mem
))
2433 RF
.StoreRegister(rf
, rd
,
2434 ALU
.PerformAL(ALU
.SNE
,
2435 RF
.LoadRegister(rf
, rs1
),
2436 RF
.LoadRegister(rf
, rs2
))),
2439 |
PerformRType ((SPECIAL
, rs1
, rs2
, rd
, shamt
, SLT
), (PC
, rf
, mem
))
2441 RF
.StoreRegister(rf
, rd
,
2442 ALU
.PerformAL(ALU
.SLT
,
2443 RF
.LoadRegister(rf
, rs1
),
2444 RF
.LoadRegister(rf
, rs2
))),
2447 |
PerformRType ((SPECIAL
, rs1
, rs2
, rd
, shamt
, SGT
), (PC
, rf
, mem
))
2449 RF
.StoreRegister(rf
, rd
,
2450 ALU
.PerformAL(ALU
.SGT
,
2451 RF
.LoadRegister(rf
, rs1
),
2452 RF
.LoadRegister(rf
, rs2
))),
2455 |
PerformRType ((SPECIAL
, rs1
, rs2
, rd
, shamt
, SLE
), (PC
, rf
, mem
))
2457 RF
.StoreRegister(rf
, rd
,
2458 ALU
.PerformAL(ALU
.SLE
,
2459 RF
.LoadRegister(rf
, rs1
),
2460 RF
.LoadRegister(rf
, rs2
))),
2463 |
PerformRType ((SPECIAL
, rs1
, rs2
, rd
, shamt
, SGE
), (PC
, rf
, mem
))
2465 RF
.StoreRegister(rf
, rd
,
2466 ALU
.PerformAL(ALU
.SGE
,
2467 RF
.LoadRegister(rf
, rs1
),
2468 RF
.LoadRegister(rf
, rs2
))),
2471 |
PerformRType ((_
, rs1
, rs2
, rd
, shamt
, _
), (PC
, rf
, mem
))
2472 = (print
"Error : Non R-Type opcode, performing NOP\n";
2477 * The function PerformJType performs one
of the J
-Type
2480 fun PerformJType ((J
, offset
), (PC
, rf
, mem
))
2481 = (Word32
.fromInt (Int.+ (Word32
.toIntX PC
,
2483 (Word32
.<< (offset
, 0wx0002
)))),
2486 |
PerformJType ((JR
, offset
), (PC
, rf
, mem
))
2487 = (RF
.LoadRegister(rf
,
2488 Word32
.toInt(Word32
.andb (Word32
.>> (offset
,
2494 |
PerformJType ((JAL
, offset
), (PC
, rf
, mem
))
2495 = (Word32
.fromInt (Int.+ (Word32
.toIntX PC
,
2497 (Word32
.<< (offset
, 0wx0002
)))),
2498 RF
.StoreRegister(rf
, 31, PC
),
2501 |
PerformJType ((JALR
, offset
), (PC
, rf
, mem
))
2502 = (RF
.LoadRegister(rf
,
2503 Word32
.toInt (Word32
.andb (Word32
.>> (offset
,
2507 RF
.StoreRegister(rf
, 31, PC
),
2510 |
PerformJType ((TRAP
, 0wx00000003
: Word32
.word), (PC
, rf
, mem
))
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
2517 else (TextIO.print
"Error : Returning 0\n";
2521 RF
.StoreRegister(rf
, 14, Word32
.fromInt input
),
2525 |
PerformJType ((TRAP
, 0wx00000004
: Word32
.word), (PC
, rf
, mem
))
2527 val output
= Int.toString (Word32
.toIntX
2528 (RF
.LoadRegister(rf
, 14)));
2531 (TextIO.print ("Output: " ^ output ^
"\n");
2535 |
PerformJType ((_
, offset
), (PC
, rf
, mem
))
2536 = (print
"Error : Non J-Type opcode, performing NOP\n";
2541 * The function PerformInstr performs an instruction by
2542 * passing the instruction to the appropriate auxiliary function
.
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
))
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
2564 fun CycleLoop (PC
, rf
, mem
)
2566 val (nmem
, instr_word
) = MEM
.LoadWord (mem
, PC
);
2567 val instr
= DecodeInstr instr_word
;
2568 val nPC
= Word32
.+ (PC
, 0wx00000004
: Word32
.word);
2570 if instr
= HALT
orelse instr
= ILLEGAL
2571 then (print
"Program halted.\n";
2572 print (MEM
.GetStatistics (nmem
));
2574 else CycleLoop (PerformInstr (instr
, (nPC
, rf
, nmem
)))
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
.
2584 fun LoadProgAux ([], mem
, address
)
2586 |
LoadProgAux (instrs
::instr_list
, mem
, address
)
2588 val instro
= Word32
.fromString instrs
;
2589 val instr
= if isSome instro
2591 else (print ("Error : Invalid " ^
2592 "instruction format, " ^
2594 0wx00000000
: Word32
.word);
2596 LoadProgAux (instr_list
,
2597 MEM
.StoreWord (mem
, address
, instr
),
2598 Word32
.+ (address
, 0wx00000004
: Word32
.word))
2602 * The function LoadProg takes a list
of instructions
and memory
, and
2603 * loads the file into memory
, beginning at
0x10000.
2605 fun LoadProg (instr_list
, mem
)
2606 = LoadProgAux (instr_list
, mem
, 0wx00010000
: Word32
.word);
2610 * The function ReadFileToInstr reads the sequence
of
2611 * instructions
in a file into a list
.
2613 fun ReadFileToInstr file
2614 = (case TextIO.inputLine file
of
2616 | SOME l
=> l
:: (ReadFileToInstr file
));
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
.
2626 fun run_prog instructions
2627 = CycleLoop (0wx00010000
: Word32
.word,
2628 RF
.InitRegisterFile (),
2629 LoadProg (instructions
, MEM
.InitMemory ()));
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
.
2638 fun run_file filename
2639 = (run_prog
o ReadFileToInstr
) (TextIO.openIn filename
);
2646 (* ************************************************************************* *)
2651 * This file describes a small simple level
1 cache
.
2654 structure L1CacheSpec1
: CACHESPEC
2657 datatype WriteHitOption
= Write_Through
2660 datatype WriteMissOption
= Write_Allocate
2661 | Write_No_Allocate
;
2663 val CacheName
= "Level 1 Cache";
2664 val CacheSize
= 256;
2666 val Associativity
= 2;
2667 val WriteHit
= Write_Through
;
2668 val WriteMiss
= Write_No_Allocate
;
2673 structure L1Cache1
: MEMORY
2674 = CachedMemory (structure CS
= L1CacheSpec1
;
2675 structure MEM
= Memory
; );
2678 structure DLXSimulatorC1
: DLXSIMULATOR
2679 = DLXSimulatorFun (structure RF
= RegisterFile
;
2680 structure ALU
= ALU
;
2681 structure MEM
= L1Cache1
; );
2683 (* Example programs
*)
2685 val Simple
= ["200E002F",
2689 val Twos
= ["44000003",
2701 val Abs
= ["44000003",
2712 val Fact
= ["0C000002",
2763 val GCD
= ["0C000002",
2822 val _
= DLXSimulatorC1
.run_prog GCD
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