Algorithms for Compiler Design: THE MACHINE MODEL

Being a machine-dependent phase, we will need to describe some of the features of a typical computer in order to discuss the various issues involved in code generation. For this purpose, we describe a hypothetical machine model, as follows.

We assume that the machine is byte-addressable with two bytes per word, having 2¹⁶ bytes, and eight general-purpose registers, R0 to R7, that are capable of holding a 16-bit quantity. The format of the instruction is an op source destination with four-bit opcode, and the source and destination are each six-bit fields. Since a six-bit field is not capable of holding a memory address (a memory address is a 16-bit), when sources and destinations are memory addresses, then these six-bit fields hold certain bit patterns that specify that the words following an instruction contain memory addresses used as source and destination operands, respectively. The following addressing modes are assumed to be supported by the machine model:

1. r (register addressing)

2. *r (indirect register)

3. X (absolute address)

4. #data (immediate)

5. X(r) (indexed address)

6. *X(r) (indirect indexed address)

We assume that opcodes like the one listed below are available:

• MOV (for moving source to destination),

• ADD (for adding source to destination), and

• SUB (for subtracting source from destination), and so on.

The cost of the instruction is considered to be its length, because generating a shorter instruction not only reduces the storage requirement of the object code, but it also reduces the time taken to perform the operation. This is because most machines spend more time fetching words from memory than they spend in executing the instruction. Hence, by minimizing the instruction length, we minimize the time taken to perform the instruction, as well.

For example, length of the instruction MOV R0, R1 is one memory word, because, three-bit code is enough for uniquely identifying each of the registers. Therefore, the six-bit fields, each for source and destination operand, can easily hold the three-bit codes for the registers shown in Table 1.

Table 1: Six-Bit Registers for the Instruction MOV R0, R1

MOV

R0

R1

Similarly, the length of the instruction MOV R0, M is two memory words, because since the destination operand is a memory address, it will occupy the word following an instruction, as shown in Table 2.

Table 2: Six-Bit Registers for the Instruction MOV R0, R2

MOV	R0	bit pattern
M

Similarly, the length of the instruction MOV M1, M2 is three memory words, because the source and the destination operands, being memory addresses, will occupy the words following the instruction, as shown in Table 3.

Table 3: Six-Bit Registers for the Instruction MOV M1, M2

MOV	bit pattern	bit pattern
M1
M2

For example, consider a three-address statement, a = b + c. We can generate the following different instruction sequences for this statement, depending upon where the values of operand b and c can be found.

If the values of b and c can be found in the memory locations of the same name, then the following instruction sequences can be generated:

1. MOV b, R0
   ADD c, R0
   MOV R0, a���� length = six words

2. MOV b, a
   ADD c, a������� length = six words

   If the addresses of a, b, and c are assumed to be in registers R0, R1, and R2, respectively then the following instruction sequence can be generated:

3. MOV *R1, *R0
   ADD *R2, *R0������ length = two words

   If the values of b and c are assumed to be in registers R0 and R1, respectively, then the following instruction sequence can be generated:

4. ADD R2, R1
   MOV R1, a ������ length = three words

Therefore, we conclude that for generating good code, we must utilize the addressing capabilities of the machine efficiently. And this will be possible if we keep the one-value or the r-value of the name in the register if it is going to be used in the future.