Updating the PC

Introduction

There are six steps to executing an instruction. So far, we've looked at the hardware for the first five steps. We're almost done.

• Fetch instruction
• Decode instruction/Fetch Operands The operands can come from the register file, or from the instruction (e.g., immediate values and offset) or both.
• Perform ALU operations Mostly this involves introducing MUXes so that we can select which data to send to the X and Y input of the ALU.
• Access memory for load/store operations
• Store ALU (or other) results to register file The results written to the register file are usually due to an R-type instruction or due to a load. We designed hardware to handle both data locations.

We're now at the last step which is Update PC. This means to update the program counter.

At any step, the PC is either holding the address of the current instruction, or it's being updated to hold the address of the next instruction to be executed.

There are three ways the PC can be updated.

• Set PC <- PC + 4. This increments the program counter by 4. Recall each MIPS instruction is exactly 4 bytes, so uses up 4 consecutive memory locations. To get to the address of the next instruction in memory, add 4. This is used for straight-line code (i.e., no branches, etc).

• Set PC < PC + offset. This is for a branch instructions like beq and bne. The offset is computed by taking bits IR_15..0, which is the immediate part of an I-type instruction, sign-extending it, and shifting it left 2 bits, so that the low two bits are 00.

  The reason we shift left is because all word addresses are word-aligned. Since instructions are words, they must be stored (in MIPS) at word-aligned addresses. However, it doesn't make sense to have IR_1..0 set to 00 (i.e., the low two bits of the instruction set to 00). That wastes two bits that we could use. So we use it, and then shift left to get the 00.

  Input 2 of the Y MUX is the one that sign-extends and shifts left, and feeds it to the Y input of the ALU.

• Set PC to PC_31..26::IR_25..0. This is for jump instructions like j and jal.

  You take the upper 6 bits of the PC and concatenate it with the lower 26 bits of the IR.

Branching

Of the three, computing the branch address takes the most work. You need to use the ALU for two purposes. You need to compute the address of the branch. This is done by feeding in PC to the X input (via the X MUX) of the ALU, and the sign-extended, left-shifted immediate value to the Y input.

However, you also need to do a comparison. For example, consider:

  beq $r1, $r2, LABEL

The CPU needs to compare $r1 and $r2, as well as compute the address for the branch, and then determine whether to take the branch address or not.

How can you do both operations with a single ALU? There are two solutions. Either use a second, more limited ALU, used primarily for comparisons, or store the result of one operation in a register placed at the output of the ALU, and then do the other operation.

We're going to choose the second option. We'll place a register at the output of the ALU and call it ALUresult.

The next question is which order to perform the operation. Should we compute the branch address first, or should we do the comparison first?

We want to use the 1-bit ALU output called Branch to decide whether we should update the PC with PC + 4 or with the branch address. Thus, we should compute the address first, store it in ALUresult, then do the comparison.

We don't encounter this problem of using the ALU for two purposes with jumps, for two reasons. First, jumps are unconditional, so there's no need to use the ALU to do comparisons. Second, we just need to concatenate bits from the PC to bits from the IR. This doesn't require the ALU either.

Precomputing PC + 4

It turns out that we can compute PC + 4 very early in the instruction execution process.

Once we've fetched the instruction, we can go ahead and update PC right away.

We do this by selecting PC for input X of the ALU (see the diagram in the ALU notes) and + 4 for input Y. This is then fed back to the a MUX for the PC.

Here's a diagram illustrating how this works.

Again, the diagram is incomplete, just showing enough to illustrate the point.

• Pay attention to the output of the ALU being fed back to input 0 of a 3-1 MUX to the PC. This is immediately loaded by the PC.
• If the instruction turns out to be a successful branch or a jump, the PC is updated a second time. Input 1 is for (successful) branch instructions, while input 2 is for jump.
• We need logic for the PC to indicate whether to load for a conditional branch or to hold. An unsuccessful conditional branch keeps PC at the same value. Thus, we would need to hold. Otherwise, jumps and successful conditional branches cause the PC to load a second time.

Loading PC with PC + 4 right away causes some problems. In particular, when we compute branches or jumps, it must be relative to the PC + 4, the address of the next instruction in memory rather than the address of the current instruction. However, the assembler or compiler is written to handle this behavior of the CPU.

A Closer Look at the PC MUX

The PC can be updated one of three ways.

• Option 0 Load PC + 4 into the PC. This is the next instruction in memory (i.e., if the current instruction is at address 1000, then the next instruction in memory is at address 1004---note the next instruction in memory is not always the next instruction to be executed).

• Option 1 Load a branch address into the PC. This should only be done if the branch condition is true.

• Option 2 Load a jump address into the PC.

These options will match the three inputs of a 3-1 MUX which is fed into the PC.

Option 0 is used when we want to execute the next instruction in memory. Actually, we always use Option 0 to update to PC + 4, and later on, we determine whether we should update the PC a second time to a branch address or a jump address.

While this may seem silly, we have an opportunity to update the PC early on when the ALU is not really being used, so we do so.

At any point in time, only one of the three inputs to the MUX is valid. Clearly, if we have a branch address computed, we can't have a jump address ready. We simply don't have the bits ready.

Also, because we increment PC early on to PC + 4, we must wait for that to load before computing branch or jump addresses (should that be necessary, that is) because these are computed relative to the next address in memory.

Here's a diagram of the input to the MUX.

In red, you can see PC + 4 being output from the ALU to input 0 of the PC Mux. In green, we have the branch address, which is in the ALUout register, sent to input 1 of the MUX. In blue, we have the jump address, which is computed by taking PC_31..26 (the high 6 bits of PC) and concatenating it with IR_25..0 (the low 26 bits of IR). There's not really any logic gates in the box labelled LOGIC. It's only there to show that bits of PC and bits of IR are used together.

Summary

There are three kinds of updates to the PC.

• Load PC to PC + 4. This is updating the PC with the next instruction in memory. We'll always perform this step, mostly because we can.

• Load PC with the branch address, but only if the branch condition is true. If it's false, we want to make sure PC doesn't load. The branch address is computed by adding the PC to the sign-extended 16 bit offset, shifted left 2 bits. This requires the ALU.

• Load PC with the jump address. The address is computed using bits from PC and IR. This does not require the ALU.

All three inputs to the PC MUX always have some inputs. However, only one is valid, and that's the one we select.

In the next section, we discuss the details of how to set the control signals correctly so the PC update is performed.

Web Accessibility