Philippe Darche "Microprocessor 4"

NOTE.– The choice has been made to write the names of registers in upper case in the text and figures but in lower case in assembly language, since the norm (IEEE 1985) does not specify which case to use. The name of the instructions is in lower case in the text and programs (MIPS (Microprocessor without Interlocked Pipeline Stages) style), sometimes also in upper case (Motorola or Arm

style). Moreover, the examples given refer to current and older microprocessors and computer processors for the purposes of instruction. This chapter is not intended to be exhaustive. It mainly presents the functions of the first MPUs. It will be completed by the following two books. The instructions cited will be complemented by MPU documentation or in a specialist work.

1

Coding and Addressing Modes

This chapter focuses on two important characteristics of Instruction Set Architecture (ISA) (cf. В§ V1-3.5), which are instruction encoding and addressing modes.

1.1. Encoding and formatting an instruction

The instruction

is represented in a computer using a binary word in the format i bits, a multiple of the format n of the data and, in general, a multiple of the byte. We use the expression machine code to mean all those binary words representing the instruction to be executed. Instruction encoding depends on the architecture of the target processor. It is formed at least of an instruction code and, potentially, of one or more operands as Figure 1.1 illustrates.

Figure 1.1.Breakdown of an instruction

This instruction can be broken down into fields

. The instruction code, also called operation code (abridged to opcode), in format c, has one or more fields. The essential one is the function code. It defines the operation to be executed. Its format of f bits defines the maximum number of instructions F (= 2

) in the instruction set

. Other fields can be added to this such as, for example, one that specifies the addressing mode (the addressing mode field) of the operands to the format as Figure 1.2 illustrates (VAX

approach from the Digital Equipment Corporation (DEC)). The processor therefore has 2

addressing modes. Besides simplifying the encoding, one benefit is to separate the encoding of the function from that of the address, which makes it possible to make the instruction set symmetrical (cf. В§ 3.1.3). This instruction code generally takes the format of the data n of the processor to optimize access to primary memory. Since in our example n is fixed, the architect of the microprocessor or MPU (MicroProcessor Unit) must therefore compromise between the number of instructions and the number of addressing modes if the field exists. One field may be favored to the detriment of the other.

Figure 1.2.An example of the structure of an operation code

If the instruction requires, the operation code is followed by one or more operand fields (Figure 1.3), and their number is dependent on the operation (unary or binary) and the architecture. This operand field in the format o bits makes it possible to specify, depending on the addressing mode chosen, the value of the reference of the location of the operand needed for calculation or, potentially, the result. An operand's storage location, which is imposed by the programmer, compiler or linker or architecture, is a register or memory location. An instruction to one operand is called a “monadic”, and one with two operands, “dyadic”. When there are two operands, we speak of source and destination operands or sink operands or sometimes simply left and right operands. We cite the VAX mini-computer with a variable format as an example of encoding. The operation code included one to two bytes. It was eventually followed by no more than six operand specifiers, mainly address specifiers, making it possible to design the operand. The MPU MC6800 instruction format included one to three bytes, the first being an operation code indicating the addressing mode.

Figure 1.3.Format of an instruction with two operands

Table 1.1 shows the different address combinations for IA-32 instruction set (IA for Intel Architecture, also called i386). Combinations not indicated are not possible either due to the architecture or to their incoherence. We cite impossible memory (to) memory combinations in most architectures, as it is necessary to pass through a register and an immediate-register or immediate-memory, which cannot be done because of the impossibility of allocating a value to a constant.

Table 1.1.Possible address combinations in family IA-32

The identification field (ID) of the operand(s) specifies the format and addressing mode (register or memory reference) as well as the direction of transfer (Figure 1.4). In a RISC microprocessor (Reduced Instruction Set Computer, this will be covered in a future book by the author on microprocessors), this field is included in the instruction's code through simplification and in view of the reduced number of instructions and addressing modes.

Figure 1.4.An instruction with several operands

By construction, the format of the instruction is fixed (fixed length), short or long, or variable (variable length). The value of a fixed format is a multiple of the byte in general. Its value will have a direct consequence for the incrementation value of the Program Counter (PC, cf. § V3-3.1.3). The benefit is that it will be possible to align the instructions (cf. § 3.1.2), thus accelerating memory reading or writing by reducing the number of memory accesses. The division of the instruction into subfields, for example, one for the instruction class (cf. Chapter 2 (#ud6d44f92-6a6a-555e-9f28-1b50c4c9828d)), the second for the function, the third for the type of operands and the last for the operands and a unique format allowing simplification of the hardware, the counterpart being a larger format. A variable format, a multiple of the MPU data format, complicates the Control Unit (CU), and it has an impact on the number of machine cycles (cf. § V3-2.4.1) needed for decoding. During this phase, the decoder should determine the size of the instruction as quickly as possible. This information is needed, for example, for debugging, to determine the instruction boundaries or limits in the machine code (interruptible “at instruction boundaries”). On the other hand, it has the advantage of obtaining programs that take up less memory. In fact, a simple instruction such as nop (no operation, cf. § 2.8.5) will classically take up one byte compared to a word with several bytes with a fixed format. The format's variability makes it difficult to use a pipeline or a superscalar execution (this will be covered in a future book by the author on microprocessors). As an example of a fixed format, we cite the format n = 32 bits for MIPS Technologies microprocessors. Even if the format is fixed, the number of fields may vary as well as the format. Encoding uses three types, which are Register (R-type), Immediate (I-type) and Jump (J-type) format (Figure 1.5). The operation code, completed possibly by the function field, specifies the instruction. For the first type, the second field is a specifier of the source register (rs). The following specifies the target or destination register (rt or rd), which receives the result or branching condition. The last field is an immediate value, a jump or address displacement. For the J type, the operand is the jump address in a 26-bit format. For the last type, the third field is a destination register specifier (rd). The penultimate field indicates the value of a possible shift (0 = no shift). Note the conventions rt = rs + immediate and rd = rs + rt. This simple encoding should be compared with that of the Arm

family, which can show as many as 21 types (Arm 2000).

Figure 1.5.Three fixed formats for MIPS instructions

None of these different fields have been standardized and are dependent on the manufacturer and the MPU family. For example, for Bayliss et al. (1981), an instruction is formed of four fields, which are the function fields (opcode), reference fields, and format and class fields. The class specifies the number of operands and their types. The necessary format field if there is at least one operand indicates their location (memory, register or pile, for example). The reference field gives their location explicitly. Their operation code field specifies the operation to be executed.

Figure 1.6 shows the typical variable instruction of an existing microprocessor. The instruction code has a format of 6 bits. The direction bit D indicates the direction of transfer (0 = source specified by the field reg, 1 = destination specified by the field). The bit W specifies the transfer format (0 = byte, 1 = word of 16 bits). The 2

byte is called a “post-byte”. The mode field indicates whether the transfer involves only the registers or if the memory is involved, the two displacement fields therefore indicate the length of the latter. We recognize the Little Endian byte order (LE (Cohen 1981), cf. § 2.6.2 from Darche (2012)) typical of Intel architecture since the Least Significant Byte (LSB) is first stored in the memory, in the order of the increasing addresses. To finish, the R/M (Register/Memory) field, poorly named, specifies the addressing mode, that is, the method of calculating the effective address (cf. § 1.2). Another format exists where the instruction is coded on a single byte. Thus, the format of these instructions can vary from 1 to 6 bytes. It is possible to add to these three types of prefix to modify the behavior of the instruction.

Figure 1.6.Typical instruction format from 8086/88

The architecture can also add a field, before or after the operation code to code the instruction class (called an extension of the operation code) or to specify a variable format. One example is the central IBM System/370 computer with its first 2 bits. The encoding of one instruction of the i486 by Intel is a typical example of the CISC approach (Complex Instruction Set Computer, this will be covered in a future book by the author on microprocessors). This type of instruction has a size ranging from 1 to 13 bytes. The word-code is therefore formed of one or two bytes for the operational code, a modify Register or Memory (mod R/M) byte, a ScaleIndex-Base (SIB) byte, the bytes for displacement and the bytes for the immediate values. The reg/operation code field specifies a register or makes it possible to add information for the operation code. The R/M field specifies a register (2

at most) or, if it is combined with the mode field, makes it possible to specify a mode of address (24 maximum). The SIB byte makes it possible to specify the scale factor (0, 2, 4 or 8), an index register number and the base register number. In addition, one or more prefix bytes (in any order except for REX, see below) can change how the following instruction is interpreted. Figure 1.7 shows the instruction format for Intel IA-32 and Intel 64 architectures, which has changed with the evolution of MPUs. For example, the operation code for Pentium had a maximum size of two bytes. Today, the maximum length of an instruction is 15 bytes. The format for the instructions has not ceased growing.

Another example is Arm

architecture, which, to the left of the operation code, adds a condition field (Figure 2.23). Today, there are sets of instructions in multiple formats, a sort of compromise between fixed and variable formats with only two formats, for example, 32 bits and another value such as 16 bits with 19 different forms of encoding for Thumb

(Arm

) technology linked to the compression of these instruction codes (cf. В§ 1.1.1).

Figure 1.7.Variable instruction format Intel IA-32 and Intel 64 (Intel 2016) architectures

Several technical solutions exist for retaining ascending binary compatibility (cf. В§ 3.3.3). Intel has chosen the instruction prefix. It affects how the instruction is interpreted. For example, a REX (Register Extension) prefix in 64-bit mode that indicates that the instruction uses extended registers is a valid instruction (inc or dec) in IA-32 mode. This solution had already been used by Z80 with four non-assigned machine codes (hexadecimal values CB, DD, ED and FD as prefix) to expand its compatible instruction set with 8080. Another solution was to add a post-byte to distinguish between the sets of instructions. One recent example is the VEX prefix for Vector Extensions, which makes it possible to encode the AVX (Advanced Vector eXtensions, cf. В§ 2.7.1) extension from Intel.

The number of instructions, type of architecture (stack-based, register-based, etc.), the number of addressable registers, the number of internal busses and the type, format and location of the operands will have an influence on the format i of an instruction. For access to primary memory, the memory organization, in particular the exchange format (byte or word), byte order (remember the Endian story! cf. В§ V1-2.2.1) and the alignment (cf. В§ 2.6.1 from Darche (2012)), will have some influence. The ISA can be evaluated by the number of instructions F, their complexity, their format i and the memory space they occupy. The designer's choice will depend on the function of the desired performances (execution time, memory requirement, etc.), of the usage domains and the manufacturing cost. Complexity, if it is not material, could affect the software, in particular the compiler as in the RISC approach and in the programmer. The appendix shows the instruction encoding table for MPU 6809E from Motorola. For information, the aspect of decoding an instruction has been discussed in the previous volume.

1.1.1. Code compression

In order to limit the programs' memory footprint for reasons of cost, memory size, performance or, in particular, power saving, one solution is to compress the machine code at compilation and its decompression at execution, for example, when it is loaded in the MPU cache memory (Wolfe and Chanin 1992). One benefit lies in the fact that the compiler has not been modified. For implementation, the Huffman (1952) (de)compression algorithm can be used, for example. Because of its objectives, it is intended especially for embedded systems with an MPU/MCU

RISC. Two industrial examples are Thumb

and Thumb-2 for which the 16-bit instruction word is a compression of the classic version of ArmВ® processors, which have a 32-bit format. RISC-V (Waterman 2016) has a compressed version of its code suggested by (Waterman 2011). A comparison between MPUs can be made using a measurement of the code density.

The principle can quite clearly be applied to data and to buses (cf. V2) for the same aims.

1.2. Addressing modes

We recall that the address is a whole number that makes it possible to identify (we also say locate or spot) a place in the memory (cf. § V1-2.1). This, generated by an MPU, is termed “physical” (PA for Physical Address) since it is this that will be carried by the address bus. This physical address can be positive (i.e. natural integer) or also negative (i.e. relative integer) in the case of an address in Assembly Language (AL) or machine language, for example, for a displacement relative to the current value of the PC (Program Counter). Addressing is the mechanism for accessing information (data and instructions) stored in MPU registers or in other levels of the memory hierarchy (cf. § V1-2.3). The addressing or referencing mode specifies how to reach the instruction (code addressing mode) and its operands (operand addressing mode) during its execution. This distinction between the addressing code and its operands, which may moreover be an instruction classification (cf. § 2.1), may not exist (which is the most common scenario). One of the difficulties of using the concept is that its designation and its semantics vary depending on the architecture and on the designer of the CU (Control Unit). Thus, it involves sometimes only the memory address (memory address calculation mode) or it also covers the registers (operand addressing mode). The definition is taken in its widest sense. It does not therefore only involve access to the primary memory. The different addressing modes add to the wealth of a processor, and their number still varies depending on the architectures and designers. Addressing modes are one of the ISA specification points (cf. § V1-3.5). For example, the IBM System/360 mainframe computer only has three (immediate, register and memory), but the Pentium microprocessor has nine. The more possibilities there are, the less the assembly language programmer will have to write the lines of code to carry out the desired operation. The argument refers today to the compiler designer, as assembly language is used less and less, except for teaching purposes or to meet a specific need in the use domain (cf. § V2-1.3). The other side of the coin is a more complex control unit and a longer execution for the instruction using it. We will see what the consequences of this will be covered in a future book by the author on microprocessors, which studies, among others, the RISC approach. If necessary, it specifies the means used to calculate the effective address (EA), also called the target address. This address is the result of the evaluation of an address according to its addressing mode. It will be applied on the address bus to reference the memory location if there is no virtual address mechanism at work (a mechanism that will be covered in a future book by the author on microprocessors). A synonym for EA (Effective Address) is “physical address”. In the contrary scenario, the effective address is a logical address that should then be translated into a physical address in the case of the Virtual Memory (VM) mechanism. Depending on the manufacturers, the name may also be different or there may be other nuances. To finish, some microprocessors distinguish access to instructions and to their operands from access to Input–Output (I/O) registers with specialized instructions (I/O addressing mode), thus making it possible to address different Address Space (AS) (cf. § V3-2.1.1.1). One example is shown in § 2.8.2.

We define four modes of basic (i.e. simple) addressing, which are immediate addressing, implicit and explicit addressing and memory addressing. Memory addressing is broken down into direct, relative, indirect, indexed and based addressing. These modes indicate the way to fetch or store the operand. The storage of one value can only be done in a register or memory location. There can then exist combinations of these basic addressings, called complex addressings that can be replaced using a sequence of instructions with simple addressing. The other modes involve primary memory, the stack, the bit, the registers and those specific to a particular MPU family. To illustrate these, we have chosen some instructions that are representative of various MPUs. In these examples, all digital data will be expressed on base 10 (implicit base) with the exception of indications in the form of a character prefixing or post-fixing the value or of a number in subscript. To define the operand, the rules of syntax inspired by those of the MC6809 microprocessor will be the following:

#: immediate value

$: hexadecimal base

%: binary base

The registers will be the following:

PC: Program Counter

A: accumulator

The conventions for the pseudo-code will be the following:

← or =: assignment of the right-hand value (similar to an rvalue) in the left identifier (similar to an lvalue). The symbol used means “receives” or “takes the value”. This left–right positional information avoids using parentheses, but it makes use of them for the right-hand value; they mean “contained in”.

(): address access, of which the value is framed.

@: (calculation of) the two-point symbol address: concatenation

1.2.1. Immediate addressing

Immediate addressing mode, also called immediate data addressing mode, makes it possible to initialize a register or a memory location with a constant value d, which is specified after the instruction mnemonic (cf. § 2.1) (Figure 1.8), hence its other name “literal addressing mode”. There is no effective address here since the memory is not addressed, but (DEC 1983) called it “PC immediate mode with autoincrement” as the PC (Program Counter) is used to address the value memorized immediately after the instruction code. One example is LDA #%10101010 from MC6802 from Motorola, which means that the accumulator A receives the immediate binary value 10101010b (b for binary) in byte format.