# Chapter 1: The Foundations: Logic and Proofs Lecture 18 Last Lecture Instruction formats Little versus big endian Internal storage in the CPU: stacks vs. registers Number of operands and instruction length Expanding opcodes

Todays Topic Instruction types Addressing modes 1 Byte Ordering Little endian machines store the most significant byte at the least significant byte. Big endian machines store the most significant byte fir st (at the lower address). As an example, suppose we have the hexadecimal nu mber 0x12345678.

2 Little vs. big endian Exercise 1 Assume a computer that has 32-bit integers. Show how each of the foll owing values would be stored sequentially in memory, starting at addre ss 0x100, assuming each address holds one byte. Be sure to extend e ach value to the appropriate number of bits. You will need to add more rows (addresses) to store all five values. 3 Stack Arithmetic Expression

Infix notation, such as: Z = X + Y. Stack arithmetic uses postfix notation: Z = XY+. This is also called reverse Polish notation, in honor of its Polish inventor, Jan Lukasiewicz (1878 - 1956). The principal advantage of postfix notation is that paren theses are not used. For example, the infix expression, Z = (X Y) + (W U), becomes:

Z = X Y W U + in postfix notation. 4 Infix & Postfix Expressions Exercise 1 Convert the following expressions from infix to rev erse Polish (postfix) notation. a) X * Y + W * Z + V * U XY*WZ*VU*++ b) W * X + W * (U * V + Z) WX*WUV*Z+*+

c) (W * (X + Y * (U * V)))/(U * (X + Y)) WXYUV**+*UXY+*/ 5 Stack Arithmetic Operation - Exercise a) Write the following expression in postfix (Reverse Polish) notation. Remember the rules of precedenc e for arithmetic operators! AB-CDE*F-*+GHK*+/ b) Write a program to evaluate the above arithmetic s tatement using a stack organized computer with ze ro-address instructions (so only pop and push can

access memory). 6 Expanding Opcodes Exercise 1 A computer has 32-bit instructions and 12-bit addresses. Supp ose there are 250 2-address instructions. How many 1-addres s instructions can be formulated? Explain your answer. 7 Expanding Opcodes Exercise 2 In a computer instruction format, the instruction length is 11 bi

ts and the size of an address field is 4 bits. Is it possible to ha ve: 5 2-address instructions 45 1-address instructions 32 0-address instructions using the specified format? Justify your answer. 8 Expanding Opcodes Exercise 2 Solution 9

Instruction Types Data movement Move data from memory to registers, from registers to registers, fro m registers to memory. Examples: Move, load, store, push, pop, exchange. Input/Output: Input: transfers data from a device or port to either memory or a reg ister. Output: transfers data from a register or memory to a specific port o r a device. Arithmetic Operations

Add, subtract, multiply, divide, increment, decrement, negate. Control transfer Alter the normal sequence of program execution. Branches, skips, procedure calls, returns, and program termination. 10 Instruction Types (Cont) Boolean logic Perform boolean operations. AND, NOT, OR, TEST, and COMPARE Bit manipulation

Setting or extracting individual bits within a given data word. Arithmetic and logic shift and rotate (a circle shift). Arithmetic shift, commonly used to multiply or divide by 2, treat data as signed twos complement numbers. Logical shift instructions shift bits to either the left or to the right by a specific number of bits, shifting in zeros on the opposite end. Rotate instructions are simply shift instructions that shift in the bits that are shift out. Special purpose String processing, high-level language support, protection, flag cont rol, word/byte conversion, cache management, register access, ad dress calculation, no-ops. 11

Instruction Set Orthogonality Each instruction should perform unique function without du plicating any other instructions. Means no redundant instru ctions. Instruction set must be consistent: the operand/opcode rela tionship cannot be restricted (there are no special registers for particular instructions.) 12 Addressing Modes Addressing modes specify where an operand is located.

They can specify a constant, a register, or a memory location. Addressing modes: Immediate addressing is where the data is part of the instruction. Example: addi \$t0, \$t1, 64 Direct addressing is where the address of the data is given in the instr uction. Example: Load 3 Indirect addressing gives the address of the address of the data in the instruction. Example: loadi 3 13

Addressing Modes Addressing modes specify where an operand is located. They can specify a constant, a register, or a memory location. Addressing modes: Register addressing is where the data is located in a register. Example: add \$t0,\$s1,\$s2 Register indirect addressing uses a register to store the address of the address of the data. (Effective PC address = contents of register 'reg' ) Example: add AX,[BX]

14 Addressing Modes Addressing modes (cont) Indexed addressing: use an index register to store an offset, which is added to the address in the operand to determine th e effective address of the data. Index + signed displacement Useful to access elements of an array Displacement ==> points to the beginning of the array Index register ==> selects an element of the array (array index)

15 Addressing Modes Addressing modes (cont) Based addressing is similar except that a base address regist er is used instead of an index register. base + signed displacement Useful to access fields of a structure or record Base register ==> points to the base address of the structure Displacement ==> relative offset within the structure The difference between these two is that an index register holds an offset relative to the address given

in the instruction, a base register holds a base address where the address field represents an offset from this base. 16 Addressing Modes Addressing modes (cont) Stack addressing: the operand is assumed to be on top of the s tack. Variations to these addressing modes: Indirect indexed: use both indirect and indexed addressing. Base/offset: offset + a base register + the specified instruction.

Self-relative: the address of the operand is an offset from the c urrent instruction. Auto increment decrement: automatically increment or decre ment the register used. 17 Addressing Mode Exercise 1 For the instruction shown, what value is loaded into the accumulator for each addressing mode? 18

Addressing Mode Exercise 1 Solution For the instruction shown, what value is loaded into the accumulator for each addressing mode? 19