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
