254 — CHAPTEREIGHT Central Processing Unit stack operations The procedure consists of first converting the arithmetic expression into its equivalent reverse Polish notation. The operands are pushed into the stack in the order in which they appear. The initiation of an operation depends on whether we have a calculator or a computer. Ina calculator, the operators are entered through the keyboard. In a computer, they must be initiated by instructions that contain an operation field (no address field is required). The following microoperations are executed with the stack when an operation is entered in a calculator or issued by the control in a computer: (1) the two topmost operands in the stack are used for the operation, and (2) the stack is popped and the result of the operation replaces the lower operand. By pushing, the operands into the stack continuously and performing the operations as defined above, the expression is evaluated in the proper order and the final result remains on top of the stack. The following numerical example may clarify this procedure. Consider the arithmetic expression (+4) + 6x6) In reverse Polish notation, it is expressed as 344 56% + Now consider the stack operations shown in Fig. 8-5. Each box represents one stack operation and the arrow always points to the top of the stack. Scanning the expression from left to right, we encounter two operands. First the number 3 is pushed into the stack, then the number 4. The next symbol is the multi- plication operator *. This causes a multiplication of the two topmost items in the stack. The stack is then popped and the product is placed on top of the stack, replacing the two original operands. Next we encounter the two operands 5 and 6, so they are pushed into the stack. The stack operation that results from the next * replaces these two numbers by their product. The last operation causes an arithmetic addition of the two topmost numbers in the stack to produce the final result of 42. Scientific calculators that employ an internal stack require that the user convert the arithmetic expressions into reverse Polish notation. Computers that use a stack-organized CPU provide a system program to perform the Figure 8-5 Stack operations to evaluate 3+ 4 +5 +6, Aaae ~4] ~ ls s | +30 ] +L 3) >L2 12] 12 12) >L4a 3 4 . 5 6 * +register address SECTION 8-4 Instruction Formats 255 conversion for the user. Most compilers, irrespective of their CPU organiza- tion, convert all arithmetic expressions into Polish notation anyway because this is the most efficient method for translating arithmetic expressions into machine language instructions. So in essence, a stack-organized CPU may be more efficient in some applications than a CPU without a stack. 8-4 Instruction Formats The physical and logical structure of computers is normally described in refer- ence manuals provided with the system. Such manuals explain the internal construction of the CPU, including the processor registers available and their logical capabilities. They list all hardware-implemented instructions, specify their binary code format, and provide a precise definition of each instruction. A computer will usually have a variety of instruction code formats. It is the function of the control unit within the CPU to interpret each instruction code and provide the necessary control functions needed to process the instruction. The format of an instruction is usually depicted in a rectangular box symbolizing the bits of the instruction as they appear in memory words or in a control register. The bits of the instruction are divided into groups called fields. The most common fields found in instruction formats are: 1. An operation code field that specifies the operation to be performed 2. An address field that designates a memory address or a processor register. 3. Amode field that specifies the way the operand or the effective address is determined. Other special fields are sometimes employed under certain circumstances, as for example a field that gives the number of shifts in a shift-type instruction. The operation code field of an instruction is a group of bits that define various processor operations, such as add, subtract, complement, and shift. The most common operations available in computer instructions are enumer- ated and discussed in Sec. 8-6. The bits that define the mode field of an instruction code specify a variety of alternatives for choosing the operands from the given address. The various addressing modes that have been formu- lated for digital computers are presented in Sec. 8-5. In this section we are concerned with the address field of an instruction format and consider the effect of including multiple address fields in an instruction. Operations specified by computer instructions are executed on some data stored in memory or processor registers. Operands residing in memory are specified by their memory address. Operands residing in processor registers are specified with a register address. A register address is a binary number of kbits that defines one of 2 registers in the CPU. Thus a CPU with 16 processor256 CHAPTER EIGHT Central Processing Unit registers RO through R15 will have a register address field of four bits. The binary number 0101, for example, will designate register R5. Computers may have instructions of several different lengths containing varying number of addresses. The number of address fields in the instruction format of a computer depends on the internal organization of ts registers. Most computers fall into one of three types of CPU organizations: 1. Single accumulator organization. 2. General register organization. 3. Stack organization. An example of an accumulator-type organization is the basic computer presented in Chap. 5. All operations are performed with an implied accumu- lator register. The instruction format in this type of computer uses one address field. For example, the instruction that specifies an arithmetic addition is defined by an assembly language instruction as ADD X where X is the address of the operand. The ADD instruction in this case results in the operation AC —AC + M[X]. AC is the accumulator register and M[X] symbolizes the memory word located at address X. An example of a general register type of organization was presented in Fig. 7-1. The instruction format in this type of computer needs three register address fields. Thus the instruction for an arithmetic addition may be written in an assembly language as ADD Rl, Re, RI to denote the operation R1<-R2 + R3. The number of address fields in the instruction can be reduced from three to two if the destination register is the same as one of the source registers. Thus the instruction ADD R1, Re would denote the operation Rl <—R1 + R2. Only register addresses for R1 and R2 need be specified in this instruction. Computers with multiple processor registers use the move instruction with a mnemonic MOV to symbolize a transfer instruction. Thus the instruc tion MOV RL, R2 denotes the transfer R1<—R2 (or R2<-R1, depending on the particular com- puter). Thus transfer-type instructions need two address fields to specify the source and the destination. General register-type computers employ two or three address fields inSECTION 8-4 Instruction Formats 257 their instruction format. Each address field may specify a processor register or a memory word. An instruction symbolized by ADD R4,X would specify the operation R1<-R1 + M[X]. It has two address fields, one for register R1 and the other for the memory address X. The stack-organized CPU was presented in Fig. 8-4. Computers with stack organization would have PUSH and POP instructions which require an address field. Thus the instruction PUSH x will push the word at address X to the top of the stack. The stack pointer is updated automatically. Operation-type instructions do not need an address field in stack-organized computers. This is because the operation is performed ‘on the two items that are on top of the stack. The instruction ADD ina stack computer consists of an operation code only with no address field. This operation has the effect of popping the two top numbers from the stack, adding the numbers, and pushing the sum into the stack. There is no need to. specify operands with an address field since all operands are implied to be in the stack. Most computers fall into one of the three types of organizations that have just been described. Some computers combine features from more than one organizational structure. For example, the Intel 8080 microprocessor has seven CPU registers, one of which is an accumulator register. As a consequence, the processor has some of the characteristics of a general register type and some of the characteristics of an accumulator type. All arithmetic and logic instruc- tions, as well as the load and store instructions, use the accumulator register, so these instructions have only one address field. On the other hand, instruc- tions that transfer data among the seven processor registers have a format that contains two register address fields. Moreover, the Intel 8080 processor has a stack pointer and instructions to push and pop from a memory stack. The processor, however, does not have the zero-address-type instructions which are characteristic of a stack-organized CPU. To illustrate the influence of the number of addresses on computer pro- grams, we will evaluate the arithmetic statement X =(A+B)*(C +D) using zero, one, two, or three address instructions. We will use the symbols ADD, SUB, MUL, and DIV for the four arithmetic operations; MOV for the transfer-type operation; and LOAD and STORE for transfers to and