Algorithms for Compiler Design: THE MACHINE MODEL

7/24/2010 8:04:52 PM
11.3 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 216 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




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



bit pattern


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


bit pattern

bit pattern



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.

Most View
Windows Vista : Build Your Network (part 7) - Troubleshoot Network Connections, Test an IP Address
Android Application Development : Rolling Your Own Widgets (part 3) - Canvas Drawing - Drawing text, Matrix transformations
Compact Liquid Cooling System Roundup – Front Runners (Part 2)
Smart, But Not Pricey : LG Optimus L7, Nokia Lumia 610, Sony Xperia U, Micromax A90S, BlackBerry Curve 9320, Nokia Lumia 710
AMD A10-6800 - AMD Accelerated Processors for Desktop PCs
Microsoft Lync Server 2010 : Microsoft Communicator Client for Macintosh - Audio/Video Calls and Conferencing
The Best Deals On Cool-Running Components And Passive Cooling Solutions
Are Your Passwords Safe? (Part 1)
Take Encoding Up A Level (Part 1)
Toshiba Satellite Pro L830 10J – An Affordable 13.3in Laptop
Top 10
Olympus Stylus 1 - The Pied Piper (Part 3)
Olympus Stylus 1 - The Pied Piper (Part 2)
Olympus Stylus 1 - The Pied Piper (Part 1)
Olympus Pen E-PL5 - April 2014
Nikon 1 J3 – April 2014
New Camera For You – Nikon 1 AW1
Phase One IQ250, Hasselblad H5D-50c - Medium-format Media Systems: Bigger Gets Better
Kaveri APU - AMD A10-7700K
Fujifilm X-M1 – Review April 2014
Fujifilm X-T1 : Good To Go