The Fetch&execute

The Fetch-Execute Cycle RegistersThis is the sequence of steps that happens when the CPU (Central Processing Unit) fetches an instruction from the memory. It involves several registers inside the CPU - specifically, the Program Counter. Here are a summary of the registers needed: •

•

•

•

The program counter is the register that holds the memory address of the current instruction being executed. When the next instruction is to be fetched, this register is incremented by the appropriate number of bytes. Some CPUs contain a memory address register, which holds the address of the byte being loaded. This doesn't necessarily mean the instruction byte, as several instructions have one or more bytes as operands (i.e. that follow the instruction). Other CPUs don't have this register. They simply increase the program counter and use it to fetch the next byte(s) into memory. CPUs contain general registers. In the example below, I shall use the 6502's registers. The 6502 processor (used in the BBC micro computer) contains three general registers - the Accumulator (A) and two index registers (X and Y). In the CPU, there is a status register (also called the condition codes register) which indicates various things about the last calculation carried out. For instance, there is a zero flag (which is set to true if the last calculation produced a zero), a carry flag (true if the last calculation produced a carry out i.e. an overflow) etc.

Communication between CPU and memory There are various wires that connect the CPU to the memory. Whenever the CPU needs to read (or write) a byte of data to/from the memory, it specifies the address of the byte on a set of wires called the address bus. The data itself is placed on a set of wires called the data bus. The address bus is unidrectional - meaning that the CPU specifies addresses, but the memory doesn't. The data bus is bidirectional - both the CPU and the memory can place information on it. As well as these buses, there is another set of wires called the control bus. These specify whether the memory is being read or written to and send signals from the CPU to the memory (or vice-versa) that the data is ready on the various buses. One wire in the control bus is referred to as Read/Write or (R/W). This is set to

binary "1" (the voltage representing "true" - typically 5 volts) to indicate that the memory is to be read, and to binary "0" (the voltage representing "false" - typically 0 volts) to indicate that the memory is to be written to. The line is sometimes written with a line over the W to show that it is the 0 value that means write, not the 1 value. Similarly, there is an address bus ready line (often called address bus enable), which is set to 1 by the processor whenever there is a valid address on the address bus (it is the signal that says to the memory "Address is ready - come and get it!"), and a similar signal, data bus ready (or

data

bus

enable),

which

either

the

memory

or

the

CPU

can

set.

An example of a one-byte instruction - INX The 6502 instruction set contains the INX instruction, which means "increment (add one) to the contents of the X register". This instruction is called a "one byte" instruction as it is not followed by any other bytes as operands. It is therefore the simplest example of the fetch execute cycle. The steps are as follows: 1. The CPU examines the program counter register. This gives the address of the instruction to be brought in from memory (the INX in this case - although the processor doesn't know that, yet!) If the CPU has a memory address register, then the value in the program counter is copied into it. The memory address register is the one which holds the addresses to be placed on the address bus. This is what happens. 2. The processor then sets the Read/Write line to 1 to indicate that the memory value is to be read into the CPU. After it has done that, it. sets the Address Bus Enable line to indicate that the address bus holds a valid address. These operations must be done in this order, as the Address Bus Enable line is the signal for the memory to act. If it were set before the Read/Write line, then the memory might well look at the Read/Write line before it was ready, possibly writing data into memory instead of reading from it. It's a question of making sure everything is correct before sending the "go" signal. 3. The memory fetches the byte from the specified address and places it on the data bus. 4. The memory then sets the Data Bus Enable line to indicate to the processor that the data bus contains a valid byte. 5. The CPU reads the byte in from the data bus. This is the "Fetch" part of the cycle. The processor then executes the instruction, which, in this case, means two more steps: 6. The processor increases the value of the X register by 1. If the X register held its largest possible value (255) before the increase, it then "overflows" back to zero. 7. The processor examines the contents of the X register and sets the status flags accordingly. If the X register now contains 0, then the carry flag is set (to indicate that there was an overflow) and the zero flag is set (to indicate that the result of the calculation was 0). Otherwise, both these flags are cleared. After the instruction has been executed, the CPU increases its Program Counter by 1 so that it will point to the instruction after the INX instruction.

An example of a two-byte instruction - LDA #7

The instruction LDA #7 in the 6502 assembly language means "Load the accumulator with the value 7." It requires two bytes of memory - one to hold the instruction ("Load the accumulator with the byte that follows me in memory") and one to hold the byte itself:

The sequence of instructions is now as follows: 1. The CPU fetches the instruction "LDA with the following value" from memory using the fetch cycle (steps 1 to 5 described above). 2. The CPU is programmed so that when it received this instruction, it fetches the next byte from memory. This is done by increasing the memory address register by 1 (the next byte on from the instruction) - or using the program counter if the CPU doesn't have a memory address register - and fetching the next byte as per normal. 3. The value read in (7 in this case) is placed into the accumulator (A), thus replacing any value that was already in there. The status flags are changed accordingly. Because the value was not 0, the zero flag is cleared. Had the instruction been LDA #0, then the zero flag would have been set. When the instruction has been carried out, the CPU will increase the value in the Program Counter so that it points to the instruction after the LDA instruction. If the CPU has a memory address register, then it will need to increase the Program Counter by 2, in order to bypass the LDA instruction itself and the number 7 in memory. If the CPU used the Program Counter itself as the memory address register, then it will already be pointing to the 7 in memory, and will only need to be increased by 1 in order to point to the next instruction. A two-byte instruction involving a memory write - STA 100 The instruction STA 100 means "Store the value currently in the accumulator in memory address 100". I have included it as it involves two memory reads (getting the instruction, and getting the address in which to store the number) and a memory write (actually storing the number itself). I am assuming for simplicity's sake that the number 100, the address itself, is a one byte number, so that the

instruction will look like this: The 6502 processor does have a version of the STA instruction which stores numbers in using one byte addresses, so this is a reasonable assumption. That version of the STA instruction can only store numbers in the first 256 bytes of memory (called the Zero Page), as one byte numbers can't specify addresses above 255. Another version of the

instruction exists (with a slightly different op-code) which is followed by 2 bytes, specifying the low and high bytes of a 2-byte memory address:

The memory address in this case would be 14 + 73 x 256 = 18702. However, this adds complexity to the process, so I won't be explaining this. 1. The CPU fetches the instruction using the fetch cycle. This instruction is the op-code for STA, which the CPU interprets as meaning "The next number in memory is a one-byte address. Store the value currently in the accumulator in that address in memory." 2. The CPU will either increase the value in the memory address register (if it has one) or increase the value in the Program Counter. Then it uses the fetch cycle to fetch the address into memory. This will probably be stored in a memory buffer register in the CPU (used to hold memory addresses while they are being dealt with). 3. The CPU then carries out the write cycle which copies the accumulator contents into memory. This is similar to the read cycle but with the data direction reversed. The write-cycle goes as follows: 1. 2. 3. 4. 5.

The CPU sets the Read/Write line to 0, indicating that it wants to write a value to memory. It then places the value in the accumulator onto the data bus. This is the value to write to slot 100. It then sets the Data Bus Enable line to 1 (i.e. true) to indicate that the value on the data bus is valid. It then places the address 100 (suitably padded to two bytes) onto the address bus. Finally, the CPU sets the Address Bus Enable line to 1 (true) to indicate that the address on the address bus is valid. This is the cue to make the memory write the value into the memory slot.

The last thing the CPU does is to increase the Program Counter, either by 1 if it has been using the Program Counter instead of a memory address register, or by 2 if it really does have a memory address register. An instruction involving the ALU - ADC #40 The ALU is the Arithmetic Logic Unit, which is used to perform arithmetic (adding and subtracting) and logic (AND or OR). The instruction ADC #40 means "Add the value currently in the accumulator to the number 40, putting the answer back into the accumulator. Change the status flags accordingly". 1. The first step is the same as for all the examples up to now. In fact, all computer instructions start this way the CPU has to fetch the instruction from memory. It now knows that it has to fetch one more byte from memory, in this case, the number to add. 2. Next the computer fetches the number to add and puts it temporarily in the memory buffer register.

You can see that the output from the ALU only goes back to the accumulator. No instruction can access the contents of the ALU directly. It has to look inside the CPU instead. 3. Now the computer adds the number 40 in the memory buffer register with the number in the accumulator. The instruction ADC actually stands for "Add with Carry", which means that the value currently in the carry flag is also included. The reason for this will be explained below. 4. If the result overflows over 255, then the carry flag in the register is set to 1. It is cleared to 0 otherwise. Similarly, if the accumulator ends up holding zero (i.e. it overflows exactly to zero, for instance, 250 + 6) then the zero flag in the status register is set. Otherwise it is cleared. 5. Finally, the Program Counter is increased appropriately. This will follow the same format as for the STA 100 instruction. Why do we need to Add With Carry? - Multi-byte addition The instruction ADC is only capable of adding one single byte, but by using the carry flag, it can be extended to multi-byte addition. Let me explain the problem:

This diagram shows a three-byte number being added to another three-byte number to produce a three-byte answer. There is a carry bit from the first byte to the second (which happens to be 1 in this case) and another carry from the second to the third (which is 0 in this case). Let's suppose we had to implement this in 6502 assembly code. The two numbers to be added are in addresses 70, 71 and 72 for the first number and 80, 81 and 82 for the second number, and the answer has to be put in addresses 90, 91 and 92. Addresses 70 and 80 hold the least-significant bytes of the numbers and address 90 is to hold the least significant byte of the answer. ("Least signficant" means the byte on the right side). The code for this addition is: CLC

Clear the carry flag before the addition

LDA 70

Load byte from address 70 into accumulator

ADC 80

Add the byte in address 80, setting the carry flag if there is a carry to the next byte.

STA 90

Store the answer in address 90.

LDA 71

Repeat calculation for bytes 71 and 81

ADC 81 STA 91 LDA 72

Repeat calculation for bytes 72 and 82

ADC 82 STA 92 The first addition is carried out in lines 2 to 4. If there is a carry between this byte and the next, then the carry flag is set automatically by the ADC instruction. This is why there is no CLC instruction before the next byte addition (lines 5 to 7). Similarly, there may be a carry between the second byte and the third byte. The third byte addition happens in the last three lines. In this way, the carry flag is saved between each byte of the addition. The example above shows the code for a three-byte addition. However, if we used similar code to add twenty-byte numbers, it would be a very long program. We can use the X register to keep a counter, so we can put the code in a loop. Here is a rewritten program which adds the twenty bytes in addresses 10 to 39 to the twenty bytes in addresses 50 to 69 and stores the answer in the twenty bytes from addresses 80 to 99.

.loop

CLC LDX #0 LDA 10,X ADC 50,X STA 80,X INX CPX 20 BNE loop

Clear the carry flag before the addition Load the counter with 0 Load the relevant byte of the first number into A Add the relevant byte from the second number Store in relevant byte of answer Add 1 to the counter Has it reached 20? Jump if it hasn't back to the loop.

This program uses an unusual addressing mode. The instruction LDA 10,X means "Load the accumulator with the number in address (10 + the contents of the X register)". This means that when X holds the number 0, the instruction is equivalent to LDA 10, when X holds the number 1, the instruction is equivalent to LDA 11, when it holds 2, it is equivalent to LDA 12 etc. The instructions ADC 50,X and STA 80,X work in a similar manner. The code works like a loop. The first time round the loop, the byte in 10 is added to the byte in 50 and the answer placed in the address 80. The second time round the loop, the byte in 11 is added to the byte in 51 and the answer placed in 81 etc. All the time the carry flag keeps track of any carries from one byte to the next. The loop only stops when the value of X reaches 20. As long as it hasn't, it jumps back. The instruction "BNE loop" means "Branch if it is Not Equal to the point marked 'loop'".