4.0 SIM4 - A GENERAL REGISTER MACHINE 4.1 INTRODUCTION When Intel Corporation invented the microprocessor (a processor on a chip) in the early 1970's, the largest chips that could be manufactured contained only several thousand transistors. As a result, early microprocessors only contained a small number of special purpose registers such as acc and ip in the SIM processors. As it became possible to manufacture chips with millions of transistors, microprocessors evolved to contain a larger number of general purpose registers. For example, in 32-bit mode, modern Intel microprocessors allow the programmer to access eight somewhat specialized 32-bit registers. In 64-bit mode, these same processors allow access to sixteen 64-bit general registers. The SIM4 design adds eight general registers to the two registers (acc and ip) of the previous design. The ten processor registers appear as follows: +---PROCESSOR---+ | reg content | | +------+ | | 0 | dddd | | %r0 is %acc | +------+ | | 1 | dddd | | | +------+ | | ... | | +------+ | | 7 | 0ddd | | %r7 is sp, the stack pointer | +------+ | | 8 | 0ddd | | %r8 is lr, the link register | +------+ | | 9 | 0ddd | | %r9 is %ip, the instruction pointer. | +------+ | +---------------+ /\ /||\ || \||/ \/ MEMORY As shown in the figure, %r0 is the new name for the accumulator (acc) and %r9 is the new name for the instruction pointer (ip). Because registers %r7, %r8, and %r9 are designed to manipulate 3-digit addresses, the first digit is forced to be a zero, so that the contents are always a valid address (0000 to 0999). 4.2 SIM4 INSTRUCTIONS In the SIM4 processor, The HALT, JUMP, and memory instructions (LOAD, STORE, ADD, and SUBTRACT) are unchanged. The memory instructions (operation codes 1aaa through 5aaa) always use %r0 because there are no "spare digits" that could be used to specify a general register. The SKIP family can now test the value in any of the ten processor registers. The table below compares the old family of SKIP instructions with the SIM4 family. The instruction format is changed from 6n00 (where n specifies the particular instruction) to 6n0r where r specifies one of the ten processor registers (%r0 through %r9). The assembly language statements are also modified. The assembly statement skeq which skips if acc is equal to zero, becomes skeq %r0. The table below illustrates the changes. OLD (SIM2, SIM3) SKIP INSTRUCTION FAMILY machine assembly name format format effect JUMP 6aaa jmp symb %ip = aaa SKIP 7000 skip %ip = %ip + 1 SKEQ 7100 skeq if (%acc==0) %ip=%ip+1 SKNE 7200 skne if (%acc!=0) %ip=%ip+1 SKGT 7300 skgt if (%acc> 0) %ip=%ip+1 SKGE 7400 skge if (%acc>=0) %ip=%ip+1 SKLT 7500 sklt if (%acc< 0) %ip=%ip+1 SKLE 7600 skle if (%acc<=0) %ip=%ip+1 NEW (SIM4) SKIP INSTRUCTION FAMILY (r is 0 to 9 and %rn is %r0 to %r9) machine assembly name format format effect SKIP 7000 skip R[9] = R[9]+1 SKEQ 710r skeq %rn if (R[r]==0) R[9]=R[9]+1 SKNE 720r skne %rn if (R[r]!=0) R[9]=R[9]+1 SKGT 730r skgt %rn if (R[r]> 0) R[9]=R[9]+1 SKGE 740r skge %rn if (R[r]>=0) R[9]=R[9]+1 SKLT 750r sklt %rn if (R[r]< 0) R[9]=R[9]+1 SKLE 760r skle %rn if (R[r]<=0) R[9]=R[9]+1 In a similar way, the accumulator family of instructions becomes the single register family of instructions. SINGLE REGISTER INSTRUCTION FAMILY (r is 0 to 9 and %rn is %r0 to %r9) machine assembly name format format effect IN 800r in %rn R[r] = input device OUT 810r out %rn output device = R[r] CLR 820r clr %rn R[r] = 0000 INC 830r inc %rn R[r] = R[r] + 1 DEC 840r dec %rn R[r] = R[r] - 1 NEG 850r neg %rn R[r] = 0.0 - R[r] SHFTL 860r shl %rn R[r] = R[r] * 10 SHFTR 870r shr %rn R[r] = R[r] / 10 Finally, the 9xxx operation code (unused in SIM1, SIM2, and SIM3) is used to implement a new two-register family of instructions. These instructions can move words between registers, add and subtract registers, and use addresses in registers to access memory. Since two registers need to be specified, the letter s is used to specify a general register used as a source of a word and d is used when the register is the destination of a word. TWO REGISTER INSTRUCTION FAMILY (s and d are 0 to 9, %rs and %rd are %r0 to %r9) machine assembly name format format effect ------> <------- MVRR 90sd mvrr %rs,%rd R[d]=R[s] MVMR 91sd mvmr (%rs),%rd R[d]=M[R[s]] MVRM 92sd mvrm %rs,(%rd) M[R[d]]=R[s] EXCH 93sd exch %rs,%rd R[d]<=>R[s] ADDR 94sd addr %rs,%rd R[d]= R[d]+R[s] SUBR 95sd subr %rs,%rd R[d]= R[d]-R[s] MVRR, MVMR, and MVRM are acronyms for MoVe Register to Register, MoVe Memory to Register, and MoVe Register to Memory. EXCH exchanges the words in a pair of registers, and ADDRR (ADD Register to Register) and SUBRR perform addition and subtraction on words in a pair of registers. The order in which the two register appear can be confusing. For example, in the following instruction: machine assembly name format format effect ------> <------- MVRR 9035 mvrr %r3,%r5 R[5]=R[3] the machine and assembly language versions should be read as "move the word in register 3 to register 5" (i.e., the information moves from left to right). However, when the effect of the instruction is described "R[5]=R[3]", the information flow is right to left. We adopt left-to-right for assembly language because the GNU assembler in our textbook moves information left-to-right. In contrast, most documentation uses the right-to-left convention of high-level languages like C and Java so the right-to-left convention is used when describing the effect of an instruction. 4.3 SAMPLE PROGRAMS The file sum1to10.sim4 contains a program to sum the integers from 1 to 10 and leave the result in memory address sum. A down-counting loop is used with the index stored in %r2 and the sum stored temporarily in %r1 before being moved to sum. #sum1to10.sim4 - Sum the integers from 1 to 10 000 8201 start: clr %r1 %r1 = 0; 001 5010 lda 10 for (%r2=10;%r2!=0;%r2--) 002 9002 mvrr %r0,%r2 { 003 7202 loop: skne %r2 004 6008 jmp done 005 9421 add %r2,%r1 %r1=%r1+%r2; 006 8402 dec %r2 007 6003 jmp loop } 008 9010 done: mvrr %r1,%r0 sum = %r1; 009 2011 st sum 010 0000 halt return; 011 0000 sum: .word int sum; 000 .end start As the instructions in addresses 001 and 002 illustrate, it requires two instructions to load the constant 10 into register 2 - one to load the constant into %r0 and one to copy %r0 to %r2. 001 5010 lda 10 for (%r2=10;%r2!=0;%r2--) 002 9002 mvrr %r0,%r2 { An assembly statement such as mvrr 10,%r2 would be illegal because the mvrr instruction requires both operands to specify processor registers. Similarly, it requires two instructions to move the sum from %r2 into memory cell sum. 008 9010 done: mvrr %r1,%r0 sum = %r1; 009 2011 st sum The same result could have been achieved by loading the address of sum into %r0 and then using a mvrm instruction. 008 5011 done: lda sum,%r0 sum = %r1; 009 9210 mvrm %r1,(%r0) Instead of loading the word at address sum (e.g. 0055) into %r0, the instruction lda sum,%r0 loads the address sum (011) into %r0. In the mvrm instruction, The second operand is (%r0) rather than %r0. Instead of moving the value in %r1 into %r0, the mvrm instruction moves the value in %r1 to the memory cell whose address is contained in %r0. There are three different move machine language operation codes - MVRR (90sd), MVMR (91sd), and MVRM (92sd) and three different assembly language symbolic opcodes (mvrr, mvmr, and mvrm). The assembler could be rewritten to use only a single symbolic operation code (mov) because the operands that follow the mov can be used to distinguish between the three different operation codes (90sd, 91sd, or 93sd). The designers of processors (.e.g. Intel or AMD) select the names for the machine language operations (MVRR) and the designers of assemblers (e.g. GNU or Microsoft) select the symbolic operation codes (mvrr or mov). There are several different assemblers (e.g. Microsoft MASM and GNU) for our Intel processors. We can manipulate arrays of memory cells by placing addresses into registers and then manipulating the addresses. As an example of using arrays, the following program reads up to 100 numbers and then prints them out in reverse order. If this program is given the input "3 10 20 30", the output will be "0030, 0020, 0010". #reverse.sim4 - Input n integers and output them in reverse order 000 8001 start: in %r1 n = read(); 001 5020 lda array %r2 points to array 002 9002 mvrr %r0,%r2 003 9013 mvrr %r1,%r3 for (i=n; i!=0; --i) 004 7203 inlp: skne %r3 { 005 6011 jmp outlp 006 8403 dec %r3 007 8004 in %r4 array[%r2] = read(); 008 9242 mvrm %r4,(%r2) 009 8302 inc %r2 %r2++ 010 6004 jmp inlp } 011 9013 mvrr %r1,%r3 for (i=n; i!=0; --i) 012 7203 outlp: skne %r3 { 013 6019 jmp done 014 8403 dec %r3 015 8402 dec %r2 %r2--; 016 9124 mvmr (%r2),%r4 write() = array[%r2]; 017 8104 out %r4 018 6012 jmp outlp } 019 0000 done: halt return; 020 0000 array: .=.+100 int array[100]; 000 .end start 3 10 20 30 Recall that the assembly language symbol "." is called the location counter which specifies the address where the next word of code is to be placed. When the assembly statement: 020 0000 array: .=.+100 int array[100]; is encountered, the location counter is equal to 020. The assembly directive .=.+100 adds 100 to the location counter producing a value of 120. As a result, addresses 020 through 119 (100 memory words) are reserved for array. As the reverse.sim4 program illustrates, long machine language programs can be difficult to write, debug, and understand. Rather than trying to write machine language code directly, it is easier to create code by writing a SIM4 assembly language program and then translating it "by hand" into SIM4 machine language (or you could write a program to do the translation for you as you will soon be asked to do). 4.4 CALLING AND RETURNING FROM FUNCTIONS Up to this point, there has been no reasonable way to implement function calls. The problem is not in calling a function - the jmp instruction would accomplish that. The problem is in returning to the calling function when the called function completes. This requires some method for saving the value in the instruction pointer (ip or %r9) when the function is called. SIM4 relies on the fact that register 9 (%r9) is the instruction pointer. To call a function called mult(), we can load the address "mult" into a general register (say register 8) and then exchange the values in registers 8 and 9. In assembly language: lda mult ; address "mult" in %r0 mvrr %r0,%r8 ; address "mult" in %r8 exch %r8,%r9 ; call mult() - addr "back" in %r8, addr "mult" in %r9, back: ... halt mult: ... mvrr %r8,%r9 ; return to caller at address back After the exch %r8,%r9 instruction is fetched from memory, the SIM4 processor increments the instruction pointer (%r9 = %r9 + 1) so that %r9 contains the address of the next instruction (back:). This is the address stored in %r8 when the exch %r8,%r9 instruction is executed. A register that holds the return address to a calling program is called a link register and we will refer to %r8 as the link register or lr. The following program inputs two integers into %r1 and %r2, calls the function %r0=mult(%r1,%r2) to compute the product by successive addition, and then prints the product that the function mult() leaves in %r0. #mult.sim4 - Read 2 integers and print their product 000 8001 start: in %r1 r1 = read(); 001 8002 in %r2 r2 = read(); 002 5007 lda mult r0 = mult(r1,r2); 003 9008 mvrr %r0,%r8 004 9389 exch %r8,%r9 005 8100 out %r0 out() = r0; 006 0000 halt return; 007 8200 mult: clr %r0 r0 = 0; 008 7201 loop: skne %r1 if (r1==0) 009 9089 mvrr %r8,%r9 return; 010 9420 addr %r2,%r0 r0 = r0 + r2; 011 8401 dec %r1 r1--; 012 6008 jmp loop goto loop; 000 .end start 3 4 4.5 QUESTIONS AND PROBLEMS 1. The programs readv2.sim3 and addn.sim4 both add n numbers and print the sum. However, addn.sim4 is more efficient than readv2.sim3 because it uses the general registers rather than memory to store the data words. a. If n is equal to 3, how many instructions does readv2.sim3 execute by the time it halts. (Just execute the program). b. If n is equal to 3, how many instructions does addn.sim4 require. c. Find general formulas for the number of instructions executed by readv2.sim3 and addn.sim4 for an arbitrary value of n. 2. Write a machine language program to input n numbers and output them in reverse order. (If the input data is "3, 10, 20, 30", the output should be "30, 20, 10".) Use a processor register to point to the array, and access the array by modifying the register. 3. Write a loader program that reads an array into memory beginning at address 100 and then jumps to address 100. (If the data to your program is as follows, your program should use a loop to place 8002 into address 100, 8302 into address 0101, 8102 into address 0102, and 0000 into address 0103. After jumping to address 100, your program should output 1000.) 0004 8002 8302 8102 0000 0999 4. Write a program that inputs n numbers (up to 100) and outputs the numbers in ascending sequence. Write your program in four stages: a. Write your program using the high-level language we have been using. b. Translate the high-level language program into a SIM4 assembly language program. c. Translate the assembly language program into machine language. d. Test and debug the machine language program. 4.6 SIM2 PRACTICE QUIZ What number will each of the following SIM4 programs print? 1. printed value = ________ 000 8109 start: out %r9 001 0000 halt 000 .end start 2. printed value = ________ 000 9092 start: mvrr %r9,%r2 001 9092 mvrr %r9,%r2 002 8102 out %r2 003 0000 halt 000 .end start 3. printed value = ________ 000 1004 start: ld a 001 9002 mvrr %r0,%r2 002 8102 out %r2 003 0000 halt 004 0000 a: .word 0 000 .end start 3. printed value = ________ 000 5004 start: lda a 001 9002 mvrr %r0,%r2 002 8102 out %r2 003 0000 halt 004 0000 a: .word 0 000 .end start 4. printed value = ________ 000 5004 start: lda a 001 9102 mvmr (%r0),%r2 002 8102 out %r2 003 0000 halt 004 0000 a: .word 0 000 .end start 5. printed value = ________ 000 1004 start: ld a 001 9102 mvmr (%r0),%r2 002 8102 out %r2 003 0000 halt 004 0000 a: .word 0 000 .end start