Writing S2 extended instructions with
microprogram
To allow students to do exercise in writing microprogram, three
extended instructions are predefined:
xl
r1 ads L-format
xd r1 r2 #im D-format
xx r1 r2 r3 X-format
The assembler will accept these extended instructions and outputs the
correct object codes for them.
The meaning of these instructions depends on how their microprogram are
written. The existing microprogram of S2 has these three
instruction in-place but do nothing.
.m
...
:xl
jmp /fetch ;
:xd
jmp /fetch ;
:xx
jmp /fetch ;
.e
Let's do an example of adding a new instruction by
microprogramming. We will use the program "list.txt" as our
intended new instruction.
;;
search the linked list
;; linked-list
;; list
;; data
;; next
;; search for d in list x
;; return 1 found, 0 not found
;; search(x,d)
;; int flag
;; flag = 0
;; while x != nil
;; if
x.data == d
;;
flag = 1
;;
break
;; else
;;
x = x.next
;; return flag
We will do the instruction:
search
r x d
where x is in R[r2] and d is in R[r3] , R[r1] is used as a temp and
return value. It will be in X-format.
The RTL for this instruction is:
:loop
test R[r2]-0
jump if Z=0
skip
R[r1] =
0 .. not found
jump fetch
.. return
:skip MAR = R[r2]
R[r1] =
M[MAR] .. read x.data, R[r1] as
temp
test
R[r1]-R[r3] .. x.data == d ?
jump if Z=0
next
R[r1] =
1 .. yes
jump fetch
.. return
:next T = R[r2] + 1
MAR = T
R[r2] =
M[MAR] .. x = x.next
jump loop
To write this program in the microprogram, additional control signals
are required. The first is to specify the register to multiplexor
x, y, d
x_r1, x_r2, x_r3
y_r1, y_r2, y_r3
d_r1, d_r2, d_r3
The new branches on flags are required.
jz, jnz -- branch on Z=1, Z=0
Some constants are necessary, we provide 0, 1, 2, 4 at the mux z.
z_0, z_1, z_2, z_4
With these additional control signals, the "search r x d" instruction
can be written:
:loop
x_r2 z_0 alu_sub ;
jnz /skip ;
z_0 alu_pass2
lt ;
r_tbus d_r1 lr
jmp /fetch ;
:skip x_r2 alu_pass1 lt ;
a_tbus lmar ;
mr r_mbus d_r1
lr ;
x_r1 y_r3 z_ry
alu_sub ;
jnz /next ;
z_1 alu_pass2
lt ;
r_tbus d_r1 lr
jmp /fetch ;
:next x_r2 z_1 alu_add lt ;
a_tbus lmar ;
mr r_mbus d_r2
lr jmp /loop ;
The assembly program using this new instruction is:
Program 1
;;
linked-list
;; list
;; data
;; next
;; search for d in list x
;; return 1 found, 0 not found
;; test list (7,8,9)
;;
1000:7, 1001:1002, 1002:8, 1003:1004,
;;
1004:9, 1005:0
;; main
;; print
search(list,8)
;; let x=r1, d=r2, tmp=r3
;; let retval=r4
;; let list
.s
list
1000 ;; to 1005
.a 0
.c
ld r31 #2000
ld r1 #7
st 1000 r1
ld r1 #1002
st 1001 r1
ld r1 #8
st 1002 r1
ld r1 #1004
st 1003 r1
ld r1 #9
st 1004 r1
ld r1 #0
st 1005
r1 ;; list (7,8,9)
:main ld r1 #1000
ld r2 #8
xx r4 r1
r2 ;; searh rv x d
trap print r4
trap stop r0
.e
Compare this program to the one written without the new instruction.
Program 2
;;
let x=r1, d=r2, flag=r3, t=r4, x.data=r5
;; let retval=r29, link=r30,
sp=r31
;; let search_x, search_d, list
.s
search_x 1010
search_d 1011
list
1000 ;; to 1005
.a 0
.c
ld r31 #2000
ld r1 #7
st 1000 r1
ld r1 #1002
st 1001 r1
ld r1 #8
st 1002 r1
ld r1 #1004
st 1003 r1
ld r1 #9
st 1004 r1
ld r1 #0
st 1005
r1 ;; list (7,8,9)
:main ld r1 #1000
st search_x r1
ld r1 #8
st search_d r1
jal r30 search
trap print r29
trap stop r0
:search st @1 r31 r1
st @2 r31 r2
st @3 r31 r3
st @4 r31 r4
st @5 r31 r5
add r31 r31
#5 ;; push r1..r5
ld r1 search_x
ld r2
search_d ;; pass x d
ld r3
#0 ;; flag=0
:loop sub r4 r1
r0 ;; x != nil
jmp eq
ret
ld r5 @0
r1 ;; x.data
sub r4 r5
r2 ;; x.data == d
jmp neq else
ld r3
#1 ;; flag=1
jmp always ret
:else ld r1 @1 r1
;; x=x.next
jmp always loop
:ret or r29 r3
r0 ;; return flag
ld r5 @0 r31
ld r4 @-1 r31
ld r3 @-2 r31
ld r2 @-3 r31
ld r1 @-4 r31
sub r31 r31
#5 ;; pop r5..r1
jr r30
.e
Comparing the number of cycle between Program 1 and Program 2,
program 1: 17 instruction, 78 clocks
program 2: 50 instruction, 199 clocks
last update 15 Feb 2005
P. Chongstitvatana