How instruction skipping is avoided during procedure calls in pipelined architectures?

Question

I have a question regarding a PC register (IP in x86 lingo). In most architectures it is updated during an execution stage and thus stores an address of a next instruction to be fetched. It seemed clear to me until I started to reason about a pipelined architecture. For example, imagine the following classic RISC pipeline with 5 stages (Fetch, Decode, Execute, Memory access, Write back) which is filled with the following instructions (designated as "a", "b", "c", "d"):

F D E M W
c b a - -

0x12 call [0x100] ; a
0x14 mov ax, 10   ; b
0x16 add ax, 2    ; c
0x18 nop          ; d <- IP

By the time an instruction "a" reaches the E (Execute) stage in the pipeline, it is already full with subsequent instructions and IP points to an instruction at address 0x18 (the next one to fetch). When "call [0x100]" executes, it saves the contents of the IP (a return address) on the stack. But it's obviously not the address of the instruction following "call [0x100]"! So, as we return from the CALL, we effectively jump over 2 instructions since pipeline is flushed during the CALL execution!

Which means that:

• There is another hidden register storing the address of the instructions being executed and it's stored on the stack instead of IP
• It doesn't work this way
• I am missing something :)

Answer 1

Reading through the reference manual on the X86 assembly... https://courses.cs.washington.edu/courses/cse548/05wi/files/x86-reference-long.pdf

you will find this... "The call instruction calls near procedures using a full pointer. call causes the procedure named in the operand to be executed. When the called procedure completes, execution flow resumes at the instruction following the call instruction (see the return instruction)"

This tells you that the call has to return first. This means that when run, noop instructions will be placed after it until it returns.

Immediately after this is called, the Control block will determine it is a call, which is a command requiring action by the hazard detection unit. This unit fires off what is essentially a call interrupt. So immediately upon seeing this instruction this interrupt occurs to call noops and will not allow PC to increment.

Answer 2

Yes, on a pipelined CPU, a CALL instruction goes through the same pipeline stages as any other instruction. By the time the return address is stored somewhere, the PC has already been incremented several times and several other instructions have already been loaded into the pipeline.

I know of 3 ways of dealing with this, but I suspect only the 3rd way can really be used if you're trying to maintain x86 compatibility:

1. Store the current IP as the return address, several instructions past the CALL instruction. (This leads to, as user16324 pointed out, the delay slot(s) used in several DSP and RISC CPUs including MIPS; see "What is the point of delay slots?"; "Why do you think the delay slot is bad?" ). This leads to the simplest hardware, because the pipeline never needs to be flushed.
2. Store the current IP minus some fixed constant, or subtract some fixed constant from the saved return address during RETURN, or both, hopefully ending up RETURNing to the instruction immediately after the CALL instruction. (I've heard that the ARM processor does this). (This seems to require that all instructions are fixed-length, unlike x86 instructions)(This also seems to require that other kinds of branches don't mess up the IP if it's needed for the CALL).
3. In the same way that we pass the instruction down a series of pipeline registers, so each stage of the pipeline can handle a different instruction, also pass the incremented PC (the address of the instruction just after the CALL instruction) down a series of pipeline registers, so each stage of executing the CALL instruction that needs that incremented PC has it available.

"In IF, in addition to fetching the instruction and computing the new PC, we store the incremented PC both into the PC and into a pipeline register (NPC) for later use in computing the branch-target address"

-- CS4617 Computer Architecture: Pipelining

The best explanation of pipelining I've seen so far is in the book "Computer Architecture: A Quantitative Approach" by John L. Hennessy and David Patterson.

As you suspected, the pipeline registers carrying the NPC are hidden from the programmer (like all of the pipeline registers).

This "pipelining the NPC value" approach:

• supports variable-length instructions.
• allows the stage that decides to flush the pipeline on a CALL instruction (turn all the instructions in the "prior" pipeline registers into the NOP instructions) to be a different stage than the stage that decides to flush the pipeline on a conditional BRANCH.
• supports branch prediction, even if it has already modified the PC currently fetching the next instruction.