-
Notifications
You must be signed in to change notification settings - Fork 0
/
emu.lisp
444 lines (370 loc) · 14.7 KB
/
emu.lisp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
(in-package #:regmach4wasm)
(declaim (optimize (debug 3)))
(defstruct emu
(microcode-vm (make-mcvm))
(assembler-env nil))
(defun emu-load (program)
;; need to get the env back from the assembler which contains
;; .directives that the emulator will care about.
;;
(let* ((emu (make-emu))
(result (assemble-with-beta program))
(byte-list (assembly-byte-list result))
(env (assembly-env result)))
(mcvm-load-list (emu-microcode-vm emu) byte-list)
(setf (emu-assembler-env emu) env)
emu))
(defun emu-execute-opc (emu byte-list instruction)
"execute one OPC instruction given an emulator, a list with four
bytes in indexed from low to high, and an instruction object."
(let ((env (make-environment))
(rc-segment (select-bits byte-list 25 21))
(ra-segment (select-bits byte-list 20 16))
(lit-segment (select-bits byte-list 15 0)))
(env-append env `((ra ,ra-segment)
(rc ,rc-segment)
(literal ,lit-segment)))
(eval-mc-prog (emu-microcode-vm emu)
(bind-vars env (instruction-microcode instruction)))))
(defun emu-execute-op (emu byte-list instruction)
(let ((env (make-environment))
(rc-segment (select-bits byte-list 25 21))
(ra-segment (select-bits byte-list 20 16))
(rb-segment (select-bits byte-list 15 11)))
(env-append env `((ra ,ra-segment)
(rb ,rb-segment)
(rc ,rc-segment)))
(eval-mc-prog (emu-microcode-vm emu)
(bind-vars env (instruction-microcode instruction)))))
(defun emu-execute-one-instruction (emu byte-list)
(when (equal '(0 0 0 0) byte-list) (break "HALT instruction encountered"))
(let* ((opcode (select-bits byte-list 31 26))
(instruction (get-instruction opcode)))
(case (instruction-layout instruction)
(OP (emu-execute-op emu byte-list instruction))
(OPC (emu-execute-opc emu byte-list instruction))
(OP-JMP (emu-execute-opc emu byte-list instruction))
(otherwise (error "unknown opcode layout encountered")))))
(defun emu-step (emu)
;; fetch instruction
;; (break)
(let* ((vm (emu-microcode-vm emu))
(next-inst (mcvm-fetch-inst vm)))
;; execute next instruction
(emu-execute-one-instruction emu next-inst)))
(defun emu-reg (emu reg)
;; (check-type reg integer)
;; (assert (>= reg 0))
;; (assert (<= reg 31))
(if (eq reg 31) 0
(mcvm-get-reg (emu-microcode-vm emu) reg)))
(defun emu-mem (emu)
(mcvm-memory (emu-microcode-vm emu)))
(defun emu-pc (emu)
(mcvm-pc (emu-microcode-vm emu)))
;; -----------------------------------------------------------------------------
(defun emu-test-reg (program n-steps register exp)
(let ((emu (emu-load program)))
(loop repeat n-steps do
(emu-step emu))
(let ((result (emu-reg emu register)))
(unless (eq result exp)
(expected exp result)))
emu))
(defun emu-fmt-mem (emu)
"format the array of memory bytes to look like a hexdump with 32 bit
words in little endian, as bsim does."
(ram-fmt (emu-mem emu)))
(progn
(emu-test-reg '((cmove 3 r0)
(add r0 r0 r0))
2 0 6)
(emu-test-reg '((cmove 1024 r0)
(add r0 r0 r0))
2 0 2048)
(emu-test-reg '((addc r31 2048 r0)
(add r0 r0 r0))
2 0 4096)
(emu-test-reg '((cmove 3 r0)
(add r0 r0 r0)
(add r0 r0 r0))
3 0 12)
(emu-test-reg '((cmove 0 r0)
(cmove 1234 r1)
(or r0 r1 r0))
3 0 1234)
(emu-test-reg '((cmove 0 r0)
(cmove 1234 r1)
(and r0 r1 r0))
3 0 0)
(emu-test-reg '((cmove 11 r0)
(cmove 11 r1)
(and r0 r1 r0))
3 0 11)
;;(emu-test-reg '() 0 31 0)
;; when is
)
(let ((em (emu-load '(:start
(add r0 r0 r0)
(add r0 r0 r0)
(add r0 r0 r0)
(beq r0 start r0)
(add r0 r0 r0)))))
(emu-step em)
(expected 4 (emu-pc em))
(emu-step em)
(expected 8 (emu-pc em))
(emu-step em)
(expected 12 (emu-pc em))
(emu-step em)
(expected 0 (emu-pc em))
)
(let ((em (emu-load '(:start
(add r0 r0 r0)
(add r0 r0 r0)
(add r0 r0 r0)
(add r0 r0 r0)
(beq r0 start r0)
(add r0 r0 r0)))))
(emu-step em)
(expected 4 (emu-pc em))
(emu-step em)
(expected 8 (emu-pc em))
(emu-step em)
(expected 12 (emu-pc em))
(emu-step em)
(expected 16 (emu-pc em))
(emu-step em)
(expected 0 (emu-pc em))
)
(emu-test-reg '((cmove 1 r0)
(or r0 r0 r0)
(or r0 r0 r0))
3 0 1)
(emu-test-reg '((cmove 0 r0)
(cmove 1234 r1)
(or r0 r1 r0))
3 0 1234)
(emu-test-reg '((cmove 0 r0)
(cmove 1234 r1)
(and r0 r1 r0))
3 0 0)
(emu-test-reg
;; count down from 10 in R0, count up to 10 in R2
'((cmove 10 r0)
(cmove 0 r2)
:loop
(addc r0 -1 r0)
(addc r2 1 r2)
(bt r0 :loop) ; if r0 > 0 goto loop.
:done
;; after 32 cycles register 2 should contain 10
)
32 2 10)
(emu-test-reg
'((cmove 42 r0) ; put 42 into r0
(st r0 4 r31) ; mem[4] = reg[r0]
(ld r31 4 r0) ; r0 <- 42;
)
3 0 42)
(emu-test-reg
'((br :A)
(cmove 7 r0)
(cmove 7 r0)
:A
(cmove 0 r0)
(cmove 0 r0)
(cmove :A r0)
)
4 0 12)
(emu-test-reg
'((br :A)
(OR r0 r0 r0)
(OR r0 r0 r0)
:A
(ADDC r31 1 r0)
(ADD r0 r0 r0)
(ADD r0 r0 r0)
(ADD r0 r0 r0)
)
5 0 8)
(emu-test-reg
;; this assembles correctly.
'((br :a)
(cmove 7 r0)
:a
(ADD r31 r31 r0)
)
2 0 0)
(emu-test-reg
'((push r0)
(ADD r0 r0 r0))
1 0 0)
(defparameter bubble-sort-prog
'((BR STEP1) ;; start execution with Step 1
;; the array to be sorted
:A
(LONG 10) (LONG 56) (LONG 27) (LONG 69) (LONG 73) (LONG 99)
(LONG 44) (LONG 36) (LONG 10) (LONG 72) (LONG 71) (LONG 1)
(set ALEN (/ (- $ A) 4)) ;; determine number of elements in A
;; Please enter your code for each of the steps below...
(set swapped r1)
(set i r2)
(set cur r3)
(set prev r4)
(set tmp r5)
(set idx r6)
:STEP1
(CMOVE 0 swapped)
:STEP2
(CMOVE 0 i)
:STEP3
(ADDC i 1 i) ; increment array index
(CMPLTC i 12 tmp) ;
(BF tmp STEP5)
:STEP4
(MULC i 4 idx)
(LD idx (- A 4) prev)
(LD idx A cur)
(CMPLE prev cur tmp) ;; if A[i-1] <= A[i] then tmp=1 else tmp=0
(BT tmp STEP3) ;; if tmp == 1 then goto STEP3
(ST prev A idx) ;; swap A[i-1] and A[i]
(ST cur (- A 4) idx)
(CMOVE 1 swapped) ;; set swapped to 1
(BR STEP3)
:STEP5
(BT swapped STEP1)
:done
(HALT)))
(emu-test-reg bubble-sort-prog 0 0 0)
(emu-test-reg bubble-sort-prog 0 0 0)
(emu-test-reg bubble-sort-prog 2 2 0)
(emu-test-reg bubble-sort-prog 3 2 0)
(emu-test-reg bubble-sort-prog 4 2 1)
(emu-test-reg bubble-sort-prog 4 5 0)
(emu-test-reg bubble-sort-prog 5 5 1)
(emu-test-reg bubble-sort-prog 7 6 4)
(emu-test-reg bubble-sort-prog 8 4 10)
(defun test-bubble-sort-at-cycle (n regmap &optional emu)
(if (null regmap) (list 'pass emu)
(let* ((reg (caar regmap))
(val (cadar regmap))
(emu (emu-test-reg bubble-sort-prog n reg val)))
(test-bubble-sort-at-cycle n (cdr regmap) emu))))
(defun test-pc-at-cycle (program n-steps exp)
(let ((emu (emu-load program)))
(loop repeat n-steps do
(emu-step emu))
(let ((result (emu-pc emu)))
(unless (eq result exp)
(expected exp result)))))
(defun hexsymbol-to-int (s)
(parse-integer (format nil "~a" s) :radix 16))
(defun test-pc-at-cycles (program pc-list &optional cycle)
"pc-list is a list of expected program counter values which signify
what the PC should be as encountered, as the program runs one cycle as
a time."
(cond
((null pc-list) 'pass)
((null cycle) (test-pc-at-cycles program pc-list 1))
(t (progn (test-pc-at-cycle program cycle (car pc-list))
(test-pc-at-cycles program (cdr pc-list) (+ 1 cycle))))))
(test-pc-at-cycles bubble-sort-prog
(mapcar 'hexsymbol-to-int
'(34 38
3c 40 44 48 4c 50 54 58
3c 40 44 48 4c 50 54 58 5c 60 64 68
3c 40 44 48 4c 50 54 58
3c 40 44 48 4c 50 54 58
3c 40 44 48 4c 50 54 58
3c 40 44 48 4c 50 54 58 5c 60 64 68
3c 40 44 48 4c 50 54 58 5c 60 64 68
3c 40 44 48 4c 50 54 58 5c 60 64 68
3c 40 44 48 4c 50 54 58 5c 60 64 68
3c 40 44 48 4c 50 54 58 5c 60 64 68
3c 40 44 48 4c 50 54 58 5c 60 64 68
3c 40 44 6c
)
))
(test-bubble-sort-at-cycle 86 '((0 0) (1 1) (2 9) (3 #xa) (4 #x63) (5 1) (6 #x20) (7 0)))
(test-bubble-sort-at-cycle 87 '((0 0) (1 1) (2 9) (3 #xa) (4 #x63) (5 1) (6 #x24) (7 0)))
(test-bubble-sort-at-cycle 88 '((0 0) (1 1) (2 9) (3 #xa) (4 #x63) (5 1) (6 #x24) (7 0)))
(test-bubble-sort-at-cycle 89 '((0 0) (1 1) (2 9) (3 #x48) (4 #x63) (5 1) (6 #x24) (7 0)))
(test-bubble-sort-at-cycle 90 '((0 0) (1 1) (2 9) (3 #x48) (4 #x63) (5 0) (6 #x24) (7 0)))
(test-bubble-sort-at-cycle 91 '((0 0) (1 1) (2 9) (3 #x48) (4 #x63) (5 0) (6 #x24) (7 0)))
(test-bubble-sort-at-cycle 92 '((0 0) (1 1) (2 9) (3 #x48) (4 #x63) (5 0) (6 #x24) (7 0)))
(test-bubble-sort-at-cycle 93 '((0 0) (1 1) (2 9) (3 #x48) (4 #x63) (5 0) (6 #x24) (7 0)))
(test-bubble-sort-at-cycle 94 '((0 0) (1 1) (2 9) (3 #x48) (4 #x63) (5 0) (6 #x24) (7 0)))
(test-bubble-sort-at-cycle 95 '((0 0) (1 1) (2 9) (3 #x48) (4 #x63) (5 0) (6 #x24) (7 0)))
(test-bubble-sort-at-cycle 96 '((0 0) (1 1) (2 #xa) (3 #x48) (4 #x63) (5 0) (6 #x24) (7 0)))
(test-bubble-sort-at-cycle 97 '((0 0) (1 1) (2 #xa) (3 #x48) (4 #x63) (5 1) (6 #x24) (7 0)))
(test-bubble-sort-at-cycle 98 '((0 0) (1 1) (2 #xa) (3 #x48) (4 #x63) (5 1) (6 #x24) (7 0)))
(test-bubble-sort-at-cycle 99 '((0 0) (1 1) (2 #xa) (3 #x48) (4 #x63) (5 1) (6 #x28) (7 0)))
(test-bubble-sort-at-cycle 100 '((0 0) (1 1) (2 #xa) (3 #x48) (4 #x63) (5 1) (6 #x28) (7 0)))
(test-bubble-sort-at-cycle 101 '((0 0) (1 1) (2 #xa) (3 #x47) (4 #x63) (5 1) (6 #x28) (7 0)))
(test-bubble-sort-at-cycle 102 '((0 0) (1 1) (2 #xa) (3 #x47) (4 #x63) (5 0) (6 #x28) (7 0)))
(test-bubble-sort-at-cycle 103 '((0 0) (1 1) (2 #xa) (3 #x47) (4 #x63) (5 0) (6 #x28) (7 0)))
(test-bubble-sort-at-cycle 104 '((0 0) (1 1) (2 #xa) (3 #x47) (4 #x63) (5 0) (6 #x28) (7 0)))
(test-bubble-sort-at-cycle 105 '((0 0) (1 1) (2 #xa) (3 #x47) (4 #x63) (5 0) (6 #x28) (7 0)))
(test-bubble-sort-at-cycle 106 '((0 0) (1 1) (2 #xa) (3 #x47) (4 #x63) (5 0) (6 #x28) (7 0)))
(test-bubble-sort-at-cycle 107 '((0 0) (1 1) (2 #xa) (3 #x47) (4 #x63) (5 0) (6 #x28) (7 0)))
(test-bubble-sort-at-cycle 108 '((0 0) (1 1) (2 #xb) (3 #x47) (4 #x63) (5 0) (6 #x28) (7 0)))
(test-bubble-sort-at-cycle 109 '((0 0) (1 1) (2 #xb) (3 #x47) (4 #x63) (5 1) (6 #x28) (7 0)))
(test-bubble-sort-at-cycle 110 '((0 0) (1 1) (2 #xb) (3 #x47) (4 #x63) (5 1) (6 #x28) (7 0)))
(test-bubble-sort-at-cycle 111 '((0 0) (1 1) (2 #xb) (3 #x47) (4 #x63) (5 1) (6 #x2c) (7 0)))
(test-bubble-sort-at-cycle 112 '((0 0) (1 1) (2 #xb) (3 #x47) (4 #x63) (5 1) (6 #x2c) (7 0)))
(test-bubble-sort-at-cycle 113 '((0 0) (1 1) (2 #xb) (3 #x1) (4 #x63) (5 1) (6 #x2c) (7 0)))
(test-bubble-sort-at-cycle 114 '((0 0) (1 1) (2 #xb) (3 #x1) (4 #x63) (5 0) (6 #x2c) (7 0)))
(test-bubble-sort-at-cycle 115 '((0 0) (1 1) (2 #xb) (3 #x1) (4 #x63) (5 0) (6 #x2c) (7 0)))
(test-bubble-sort-at-cycle 116 '((0 0) (1 1) (2 #xb) (3 #x1) (4 #x63) (5 0) (6 #x2c) (7 0)))
(test-bubble-sort-at-cycle 117 '((0 0) (1 1) (2 #xb) (3 #x1) (4 #x63) (5 0) (6 #x2c) (7 0)))
(test-bubble-sort-at-cycle 118 '((0 0) (1 1) (2 #xb) (3 #x1) (4 #x63) (5 0) (6 #x2c) (7 0)))
(test-bubble-sort-at-cycle 119 '((0 0) (1 1) (2 #xb) (3 #x1) (4 #x63) (5 0) (6 #x2c) (7 0)))
(test-bubble-sort-at-cycle 120 '((0 0) (1 1) (2 #xc) (3 #x1) (4 #x63) (5 0) (6 #x2c) (7 0)))
(test-bubble-sort-at-cycle 121 '((0 0) (1 1) (2 #xc) (3 #x1) (4 #x63) (5 0) (6 #x2c) (7 0)))
(defun memcheck-at-cycle (prog n exp) '())
;; multiplication
(emu-test-reg '(;(option clk)
(cmove 2 r0)
(mul r0 r0 r0))
2 0 4)
;; factorial works!
(emu-test-reg
'((cmove stack sp)
(br start)
;; ------------------------------------------------------------------
:fact ; factorial
;; prologue
(push lp) ; save linkage
(push bp) ; save base
(move sp bp) ; update
(push r1) ; remember caller's r1
(ld bp -12 r1) ; r1 <- n
;; body
(cmplec r1 0 r0) ; r0 <- n <= 0 ?
(bt r0 else) ; if n<=0 goto else
(subc r1 1 r1) ; otherwise, r -= 1
(push r1) ; prepare arg to fact
(br fact lp) ; fact(n-1)
;; this is where the recursion starts unwinding
(deallocate 1) ; remove r1
(ld bp -12 r1) ; r1 <- fact(n-1)
(mul r1 r0 r0) ; r0 <- n * fact(n-1)
(br rtn) ; goto rtn
:else ; base case
(cmove 1 r0) ; return 1
:rtn ; epilogue
(pop r1) ; restore caller's r1
(move bp sp) ; restore caller's stack
(pop bp) ; restore caller's base pointer
(pop lp) ;
(jmp lp)
;; ------------------------------------------------------------------
:start
(cmove 4 r0) ; prepare fact(4)
(push r0) ; push 4 onto arg stack
(call fact) ; go!
(halt)
:stack
(reserve 100)) ;
129 0 24)