In the previous HW you pipelined nop, halt, irmovq, rrmovq, OPq and cmovXX. In lab you pipelined rmmovq and mrmovq (if you didn’t finish, we have posted an example solution). To finish your pipelined simulator, you need to combine those two and then add jXX, pushq, popq, call, and ret.

1 Approach

You may approach this however you wish, but I suggest the following flow:

1. Combine your pipehw1.hcl and pipelab2.hcl and test the combination.
2. Add jXX with speculative execution and branch misprediction recovery. Predict that all branches are taken. Test.
3. Add pushq and test.
4. Add call and test.
5. Add popq and test.
6. Add ret with handling for the return hazard, and test.

1.1 Combine and Test

All of the tests that either source file passed ought to still pass the combination.

1.2 jXX

This one is messy because we have branch prediction, speculative execution, and recovery from misprediction through stage bubbling. Let’s look at through a set of questions

What are we predicting?

That all jXX are taken (i.e., that the new PC is valC for all jXX).

How do we store that prediction?

In a predPC register inside the xF register bank (or pP or whatever else you called it).

How do we speculatively execute based on that prediction?

By setting the pc to the predicted PC (pc = F_predPC).

When would our prediction be wrong?

If the condition codes evaluate to false.

When would we learn that our prediction was wrong?

At the end of the jXX’s execute stage (which is when we check the condition codes).

We need to know at the beginning of Fetch…

End of execute = beginning of memory, so we can look in the M_... register bank outputs.

How should we react to misprediction?

We need to fetch the correct address (jXX’s valP) and bubble any stages that we should not have run.

Which stages get bubbled?

Since jXX is in memory, we keep that one (and writeback, which is a pre-jXX instruction); since we are fixing fetch we keep that one too; so we bubble just the decode and execute stages.

How do we fetch the correct address?

By using a mux to pick pc

What is the mux conditions?

mispredicted: oldValP and 1: F_predPC

1. Add a predicted PC to the xF register bank
2. Predict all branches as taken: valP for a non-jump, valC for a jump.
3. Set the pc to
   • the predicted PC unless we discover that there was a jump that we predicted incorrectly.
   • we predicted a jump wrong if (1) there is a jXX in Memory and (2) the result of checking the condition codes stored in the eM register bank is 0.
   • if we mispredicted, we’ll need to fetch the old valP
   • we’ll also need to bubble the mispredicted stages

1.3 pushq and popq

Like an rmmovq or mrmovq except you use REG_RSP not rB and ±8 not valC. Also has a writeback component for REG_RSP.

Note that popq updates two registers, so it will need both reg_dstE and reg_dstM.

Note that popq reads from the old %rsp while pushq writes to the new %rsp.

1.3.1 call and ret

call 0x1234 is push valP; jXX 0x1234. Combining the logic of push and unconditional jump should be sufficient.

ret is jump-to-the-read-value-when-popping. It always encounters the ret-hazard:

You’ll have to stall the fetch stage as long as a ret is in decode, execute, or memory and forward the value from W_valM to the pc.

2 Testing your code

2.1 Same Semantics

Your code should have the same semantics as tools/yis: set the same registers and memory

2.2 More cycles

As a general rule, your pipelined processor will need

• 1 cycle per instruction executed

• 4 extra cycles because we have a five-stage pipeline; even halt takes 5 cycles now.

• +1 more cycle for each load-use hazard (i.e., read from memory in one cycle, use as src next cycle)

• +2 more cycles for each conditional jump the code should not take (the misprediction penalty)

• +3 more cycles for each ret executed

2.3 Examples

2.3.1 jXX

y86/jxx.yo

    irmovq $3, %rax
    irmovq $-1, %rbx
a:
    jmp b
c:
    jge a
    halt
b:
    addq %rbx, %rax
    jmp c

takes 25 cycles and leaves

| RAX: ffffffffffffffff   RCX:                0   RDX:                0 |
| RBX: ffffffffffffffff   RSP:                0   RBP:                0 |

A full trace is available as pipe-jxx.txt

2.3.2 pushq

y86/push.yo

irmovq $3, %rax
irmovq $256, %rsp
pushq %rax

takes 8 cycles and leaves

| RAX:                3   RCX:                0   RDX:                0 |
| RBX:                0   RSP:               f8   RBP:                0 |

| used memory:   _0 _1 _2 _3  _4 _5 _6 _7   _8 _9 _a _b  _c _d _e _f    |
|  0x000000f_:                              03 00 00 00  00 00 00 00    |

A full trace is available as pipe-push.txt

2.3.3 popq

y86/pop.yo

irmovq $4, %rsp
popq %rax

takes 7 cycles and leaves

| RAX:  fb0000000000000   RCX:                0   RDX:                0 |
| RBX:                0   RSP:                c   RBP:                0 |

A full trace is available as pipe-pop.txt

2.3.4 call

y86/call.yo

    irmovq $256, %rsp
    call a
    addq %rsp, %rsp
a:
    halt

takes 7 cycles and leaves

| RBX:                0   RSP:               f8   RBP:                0 |

| used memory:   _0 _1 _2 _3  _4 _5 _6 _7   _8 _9 _a _b  _c _d _e _f    |
|  0x000000f_:                              13 00 00 00  00 00 00 00    |

A full trace is available as pipe-call.txt

2.3.5 ret

y86/ret.yo

    irmovq $256, %rsp
    irmovq a, %rbx
    rmmovq %rbx, (%rsp)
    ret
    halt
a:
    irmovq $258, %rax
    halt

takes 13 cycles and leaves

| RAX:              102   RCX:                0   RDX:                0 |
| RBX:               20   RSP:              108   RBP:                0 |

| used memory:   _0 _1 _2 _3  _4 _5 _6 _7   _8 _9 _a _b  _c _d _e _f    |
|  0x0000010_:   20 00 00 00  00 00 00 00                               |

A full trace is available as pipe-ret.txt.

(It is okay to diagree with this trace about what instruction is fetched and ignored while waiting for the ret, but you should take the same number of cycles and produce the same final results.)

2.4 Other tests

The same tests that should have worked on your single-cycle processor in seqhw should produce the correct results on your pipelined processor.

3 Debugging

As an experiment this semester, one of our TAs prepared a video tutorial on debugging pipelined procesors which is available here.

Our general advice for debugging this assignment:

• Use the -d output;
• Write out what instruction is in each stage of the pipeline;
• Try to simplify the test cases so it’s easier to spot your problems;

4 Submit

Submit pipehw2.hcl on the submission page.