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
rv x d
where x is in R[1] and d is in R[2] , R[3] is used as a temp. The
return value is in R[rv]. It will be in X-format.
The RTL for this instruction is:
R[rv] = 0
:loop test R[1]-0
jump if Z=1
fetch .. return
MAR = R[1]
R[3] =
M[MAR] .. read x.data
test R[3]-R[2]
jump if Z=0
next
R[rv] =
1 ..
x.data == d
jump fetch
.. return
:next T = R[1] + 1
MAR = T
R[1] =
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 number
directly (instead of using the field from IR). Four registers are
available for the multiplexors: x, y, d.
x_1, x_2, x_3, x_4
y_1, y_2, y_3, y_4
d_1, d_2, d_3, d_4
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 rv x d" instruction
can be written:
:xx
z_0 alu_pass2
lt ;
d_r1 r_tbus lr
;
:loop x_1 z_0 alu_sub ;
jz /fetch ;
x_1 alu_pass1
lt ;
a_tbus lmar ;
mr d_3 r_mbus
lr ;
x_3 y_2 z_ry
alu_sub ;
jnz /next ;
z_1 alu_pass2
lt ;
d_r1 r_tbus lr
jmp /fetch ;
:next x_1 z_1 alu_add lt ;
a_tbus lmar ;
mr d_1 r_mbus
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, 80 clocks
program 2: 50 instruction, 199 clocks
last update 15 Feb 2005
P. Chongstitvatana