S21 A Hypothetical 32-bit Processor


This is a typical simple 32-bit CPU.  It has a three-address instruction architecture, with 32 registers and load/store instructions. This document presents only S21 assembly language view. It does not give details about microarchitecture (such as pipeline).

S21 has three-address instruction set.  A general format of an instruction (register to register operations) is:

op r1 r2 r3     means  R[r1] = R[r2] op R[r3]

To pass values between memory and registers, load/store instructions are used.   Load means transfer memory to register. Store means transfer register to memory. There are two addressing mode: absolute and index.
 
ld r1 ads          R[r1] = M[ads]          absolute
ld r1 +r2 r3       R[r1] = M[R[r2]+R[r3]]  index
st ads r1          M[ads] = R[r1]          absolute
st +r2 r3 r1       M[R[r2]+R[r3]] = R[r1]  index

In assembly language, these addressing modes are written using the convention op dest <- source.

Instruction type

arithmetic:             add sub mul div
logic:                  and or xor eq ne lt le gt ge shl shr
control:                jmp jt jf jal ret
data:                   ld st push pop

Instruction meaning

false == 0
true  != 0
R[0] always zero

op r1 r2 r3     is    R[r1] = R[r2] op R[r3]
op r1 r2 #n     is    R[r1] = R[r2] op n

Data

ld r1 ads       is    R[r1] = M[ads]          absolute
ld r1 +r2 r3    is    R[r1] = M[R[r2]+R[r3]]  index
st ads r1       is    M[ads] = R[r1]          absolute
st +r2 r3 r1    is    M[R[r2]+R[r3]] = R[r1]  index

Control

jmp ads         is    pc = ads
jt r1 ads       is    if R[r1] != 0  pc = ads
jf r1 ads       is    if R[r1] == 0  pc = ads
jal r1 ads      is    R[r1] = PC; PC = ads    ;  jump and link
ret r1          is    PC = R[r1]              ;  return

Arithmetic

two-complement integer arithmetic

add r1 r2 r3     R[r1] = R[r2] + R[r3]
add r1 r2 #n     R[r1] = R[r2] + sign extended n (n is 17 bits)
sub r1 r2 ...    R[r1] = R[r2] - R[r3]
mul r1 r2 ...    R[r1] = R[r2] * R[r3]
div r1 r2 ...    R[r1] = R[r2] / R[r3]  integer division

Logic (bitwise)

and r1 r2 r3     R[r1] = R[r2] bit-and R[r3]
and r1 r2 #n     R[r1] = R[r2] bit-and n (sign extended)
or r1 r2 r3      R[r1] = R[r2] bit-or  R[r3]
or r1 r2 #n      R[r1] = R[r2] bit-or  n (sign extended)
xor r1 r2 r3     R[r1] = R[r2] bit-xor R[r3]
xor r1 r2 #n     R[r1] = R[r2] bit-xor n (sign extended)
eq r1 r2 r3      R[r1] = R[r2] == R[r3]
eq r1 r2 #n      R[r1] = R[r2] == n (sign extended)
ne ...
lt ...
le ...
gt ...
ge ...
 shl r1 r2 r3     R[r1] = R[r2] << R[r3]
shl r1 r2 #n     R[r1] = R[r2] << #n
shr r1 r2 r3     R[r1] = R[r2] >> R[r3]
shr r1 r2 #n     R[r1] = R[r2] >> #n

Stack operation

To facilitate passing the parameters to a subroutine and also to save state (link register) for recursive call, two stack operations are defined: push, pop.

push r1 r2      is    R[r1]++; M[R[r1]] = R[r2]  // push r2, r1 as stack pointer  
pop  r1 r2      is    R[r2] = M[R[r1]]; R[r1]--  // pop to r2, r1 as stack pointer

Pseudo

Pseudo instructions are unlike other instructions, they are used mainly to control the simulator and to perform input/output.  Some pseudo instructions are just like short-hand mnemonics, they are synthesized from other real instructions.

trap n           special instruction, n is in r1-field.

trap 0                   stop simulation
trap 1                   print integer in R[30]
trap 2                   print character in R[30]

R0 is always zero, many instructions can be synthesized using r0.

mv r1 r2     is    or r1 r2 r0    
mv r1 #n     is    add r1 r0 #n  (n is 17-bit)

Indirect address can be synthesized from index with r0.

ld r5 +r2 r0  is   load r5 with indirect r2       R[5] = M[R[2]]

 To complement a register, xor with 0xFFFFFFFF (-1) can be used.

not r1 r2     is    xor r1 r2 #-1       R[r1] = complement R[r2]

Instruction format

L-format    op:5 rd1:5 ads:22
D-format    op:5 rd1:5 rs2:5 disp:17
X-format    op:5 rd1:5 rs2:5 rs3:5 xop:12

(rd dest, rs source, ads 22-bit,  disp 17-bit sign extended)

Instructions are fixed length at 32 bits.  There are 32 registers, with R[0] always returns zero. The address space is 32-bit.  Access to memory is always on word boundary (no byte-access). Direct (absolute address) is 22-bit or the first 4M words.  Index and indirect access can reach the whole 32-bit address space.  Immediate value (d) is 17-bit.  It is sign extended.  The  jump instructions (jmp, jt, jf) have 22-bit address.

ISA and opcode encoding

opcode   format

0  -    nop
1  L    ld r1 ads     (ads is absolute 22-bit)
3  L    st ads r1 
6  L    jmp ads  
7  L    jal r1 ads      
8  L    jt r1 ads
9  L    jf r1 ads 
10 D    add r1 r2 #n  (n 17-bit is sign extended)
11 D    sub r1 r2 #n  ...
12 D    mul r1 r2 #n
13 D    div r1 r2 #n
14 D    and r1 r2 #n
15 D    or r1 r2 #n
16 D    xor r1 r2 #n
17 D    eq r1 r2 #n
18 D    ne r1 r2 #n
19 D    lt r1 r2 #n
20 D    le r1 r2 #n
21 D    gt r1 r2 #n
22 D    ge r1 r2 #n
23 D    shl r1 r2 #n
24 D    shr r1 r2 #n
25..30 undefined
31 xop    -     X

xop
0  X   add r1 r2 r3
1  X   sub r1 r2 r3
2  X   mul r1 r2 r3
3  X   div r1 r2 r3
4  X   and r1 r2 r3
5  X   or r1 r2 r3
6  X   xor r1 r2 r3
7  X   eq r1 r2 r3
8  X   ne r1 r2 r3
9  X   lt r1 r2 r3
10 X   le r1 r2 r3
11 X   gt r1 r2 r3
12 X   ge r1 r2 r3
13 X   shl r1 r2 r3
14 X   shr r1 r2 r3
16 X   ld r1 +r2 r3
17 X   st +r2 r3 r1
18 X   ret r1
19 X   trap #n       use #n at r1 n = 0..31
20 X   push r1 r2    use r1 as stack pointer
21 X   pop r1 r2     use r1 as stack pointer
23..4095 undefined

Historical fact

S21 is an extension of S2 from 2007. This design is a result of my collective experience in teaching assembly language to novice programmers for many years.  S2 has been used for teaching since 2001.  S2 itself is an "extended" version of S1 (a 16-bit processor) which is used for teaching since 1997.

To improve understandability of S2 assembly language, flags are not used.  Instead, new logical instructions that have 3-address are introduced.  They are similar to existing arithmetic instructions.  The result (true/false) is stored in a register.  Two conditional jumps are introduced "jt", "jf". They make use of the result from logical instructions.  To avoid the confusion between absolute addressing and moving between registers, a "pseudo" instruction "mv" is introduced and to make ld/st symmetry, "ld r1 #n" is eliminated. Indirect addressing caused difficulty to many students (similar to pointers in C language).  However, array index is simple to understand (may be aided by students' experience in high level language programming). So, the use of index instead of indirect is enforced here.

The opcode format and assembly language format for S2 follow the tradition "dest = source1 op source2" from classic machines such as PDP-11, VAX and IBM S360.

Example programs

1.  Add 1 to 10
s = 0
i = 0
while i <= 10
  s = s + i
  i = i + 1
use r1 as s, r2 as i, r3 as flag
.code 0
  or r1 r0 r0    ;; s = 0
  or r2 r0 r0    ;; i = 0
:while
  le r3 r2 #10   ;; i <= 10
  jf r3 exit
  add r1 r1 r2   ;; s = s + i
  add r2 r2 #1   ;; i = i + 1
  jmp while
:exit
  trap 0         ;; stop
.end
2.  Sum all elements in an array.  Assume the array is at 100, size of array is n.
s = 0
i = 0
while i < n
  s = s + ax[i]
  i = i + 1
use r1 as s, r2 as i, r3 as base, r4 as ax[i], r5 as flag
.code 0
  or r1 r0 r0     ;; s = 0
  or r2 r0 r0     ;; i = 0
  add r3 r0 #100  ;; set base address
:while
  lt r5 r2 #5     ;; i < n
  jf r5 exit
  ld r4 +r3 r2    ;; ax[i]
  add r1 r1 r4    ;; s = s + ax[i]
  add r2 r2 #1    ;; i = i + 1
  jmp while
:exit
  trap 0          ;; stop

.data 100
  11 22 33 44 55  ;; ax[.] at 100
.end
3.  Write "pointer chasing" program in assembly language.

Goal, to test if a number is in a list.

Data structure  (singly linked list)

A list is made out of an array of nodes.  A node has two fields: the first one contains the number, the second one contains an index to the next node. The last node has 0 in the next field, signified the end of the list. For example, this is a list of number <11,22,33>.  The list start at index 100.

address: 100  101   102   103   104   105   106
data:    11   102   22    104   33    0     ...

Pseudo code

Let L be a list, x is a number.
member(x, L)
  if head(L) == x return yes
  while tail(L) != 0
    if head(L) == x return yes
    L = tail(L)
  return no
We can improve this program a bit.
member2(x, L)
  while L != 0
    if head(L) == x return yes
    L = tail(L)
  return no
It can also be written in a recursive form.
memberrec(x, L)
  if head(L) == x return yes
  if tail(L) == 0 return no
  return memberrec(x, tail(L))
We write the second version of program in s21 assembly language. The program runs  "member2(22,L)"   where L = 100.  That is, it checks whether 22 is in the list L.

How to access head(L) and tail(L)?  We use index addressing,  assume base address of L is in r2, then

  ld r4 +r0 r2  

will load M[0+r2] to r4 which is exactly head(L).  For tail(L) we need offset 1.  Let assume r1 is 1, then

  ld r4 +r1 r2

will load M[1+r2] to r4, tail(L).  Use r1 for c1, r2 base, r3 x, r4 value, r5 flag.
;; member of list

.code 0
:member2
  mv r1 #1            ;; constant 1
  mv r2 #100          ;; base address L
  mv r3 #22           ;; x = 22
:loop
  jf r2 no            ;;  while L != 0
  ld r4 +r0 r2        ;;  head(L)
  eq r5 r4 r3         ;;  head(L) == x ?
  jt r5 yes
  ld r2 +r1 r2        ;;  L = tail(L)
  jmp loop
:yes
  mv r5 #1
  jmp exit
:no
  mv r5 #0
:exit
  trap 0

.data 100
  11 102 22 104 33 0   ;; list L at 100
.end 
Put this code into a text file "mem2.txt".  Assemble it using:
c:> as21 mem2.txt
The assembler produces a listing file and an object file.  The simulator s21.exe  takes an object file and run it.
c:> s21 mem2.obj
Using the command "t"  (single step), you will see:

D:\prabhas\bag\s21\test>s21 mem2.obj
load program, last address 106
>t
PC   0 mv r1 #1          r1:1 r2:0 r3:0 r4:0 r5:0 r28:0 r29:0 r31:0
>t
PC   1 mv r2 #100        r1:1 r2:100 r3:0 r4:0 r5:0 r28:0 r29:0 r31:0
>t
PC   2 mv r3 #22         r1:1 r2:100 r3:22 r4:0 r5:0 r28:0 r29:0 r31:0
>t
PC   3 jf r2 11          r1:1 r2:100 r3:22 r4:0 r5:0 r28:0 r29:0 r31:0
>t
PC   4 ld r4 +r0 r2      r1:1 r2:100 r3:22 r4:11 r5:0 r28:0 r29:0 r31:0
>t
PC   5 eq r5 r4 r3       r1:1 r2:100 r3:22 r4:11 r5:0 r28:0 r29:0 r31:0
>t
PC   6 jt r5 9           r1:1 r2:100 r3:22 r4:11 r5:0 r28:0 r29:0 r31:0
>t
PC   7 ld r2 +r1 r2      r1:1 r2:102 r3:22 r4:11 r5:0 r28:0 r29:0 r31:0
>t
PC   8 jmp 3             r1:1 r2:102 r3:22 r4:11 r5:0 r28:0 r29:0 r31:0
>t
PC   3 jf r2 11          r1:1 r2:102 r3:22 r4:11 r5:0 r28:0 r29:0 r31:0
>t
PC   4 ld r4 +r0 r2      r1:1 r2:102 r3:22 r4:22 r5:0 r28:0 r29:0 r31:0
>t
PC   5 eq r5 r4 r3       r1:1 r2:102 r3:22 r4:22 r5:1 r28:0 r29:0 r31:0
>t
PC   6 jt r5 9           r1:1 r2:102 r3:22 r4:22 r5:1 r28:0 r29:0 r31:0
>t
PC   9 mv r5 #1          r1:1 r2:102 r3:22 r4:22 r5:1 r28:0 r29:0 r31:0
>t
PC  10 jmp 12            r1:1 r2:102 r3:22 r4:22 r5:1 r28:0 r29:0 r31:0
>t
stop, execute 16 instructions
PC  12 trap 0            r1:1 r2:102 r3:22 r4:22 r5:1 r28:0 r29:0 r31:0
>

if you change x to 44.  Reassemble mem2.txt, and run mem2.obj again.

D:\prabhas\bag\s21\test>s21 mem2.obj
load program, last address 106
>g
stop, execute 24 instructions
>r

r0 :0    r1 :1    r2 :0    r3 :44   r4 :33   r5 :0    r6 :0    r7 :0
r8 :0    r9 :0    r10:0    r11:0    r12:0    r13:0    r14:0    r15:0
r16:0    r17:0    r18:0    r19:0    r20:0    r21:0    r22:0    r23:0
r24:0    r25:0    r26:0    r27:0    r28:0    r29:0    r30:0    r31:0
>

This time we let it run through using the command "g".  The simulator stops and we list registers by "r", to see the result in r5 = 0 (No).


last update 17 Dec 2012