1 Y86 4: PIPE part 2 (pipehw1)

Continuing with the same subset of instructions from the lab, add in the other pipeline stages to nop, halt, irmovq, rrmovq; in addition, implement OPq, and cmovXX.

Even though these instructions do not use memory and some do not use execute, add in all five stages.

Implement forwarding to resolve hazards.

2 Approach

Get to know and love figure 4.41 (page 424 of the 3rd edition, page 403 of the 2nd). To match the textbook’s text, the name of these registers would be fF, fD, dE, eM, and mW. However, we can’t have two register banks with the lowercase f so pick something else for the name of fF (maybe xF or pP or the like) and remember that the book’s f_predPC is named differently in your HCL.

I suggest you do not add all the registers to each register bank in advance, instead adding them as needed for the instructions you implement, but that is just a suggestion.

2.1 Stalls and Bubbles

You will only need one pipeline stall for this homework: if the Stat computed during Fetch is not STAT_AOK you should stall the register feeding the fetch stage (but not bubble the register after it; we want the non-AOK instruction to reach the end of the pipeline). Note that you’ll need to pass that non-OK Stat down through all the pipeline registers before putting it into the Stat output.

When you extend this processor to handle memory instructions, this stall will help you ensure that a program like:

irmovq $10, %rax
halt
rmmovq %rax, 10(%rax)

does not write a value to memory, and otherwise prevent changing the state of your processor because of logically unexecuted instructions.

2.2 Forwarding

For these instructions, rrmovq and OPq read a register but either irmovq or rrmovq or OPq could be writing it. To implement forwarding, the easiest approach is probably to add a mux to the inputs to the dE register that check for things like

reg_srcA == m_dstE : m_valE;

and so on for all the other possible overlaps of srcs and dsts that are later in the pipeline.

2.3 OPq and condition codes

Put the condition codes in their own register bank; you don’t want to bubble them if you bubble another register bank as part of stalling a stage.

Also check the condition codes in execute (based on the ifun there) and store the result of that comparison in the eM register bank.

2.4 cmovXX and condition codes

To implement cmovXX, all you need to do is change reg_dstE to be either the value you’d normally predict for it or REG_NONE, depending on the truth of the condition codes. The easiest way to do that is probably by adding a mux in the execute stage, something like

e_dstE = [
    /* this is a cmovXX and the condition codes are not satisfied */ : REG_NONE;
    1 : E_dstE;
];

3 Organizing your code

You may either put all your registers at the beginning of the file, or you may put them between the phases in question. The hclrs executable makes multiple passes through your file, so defining them after you use them is permitted and can lead to a more flow-oriented layout, but some people find that distracting and prefer to define before use. Whichever you prefer.

4 Testing your code

You can run the command make test-pipehw1 to run all the tests listed in testdata/pipehw1-tests.txt, comparing the output to reference outputs supplied in testdata/pipe-reference. When you are done with this homework, that command should report that all tests passed.

For all test cases, we have supplied traces in testdata/pipe-traces which were produced by our reference solution.

5 Specific test cases

Here, we hilight test cases for specific functionality. A common strategy is to get these test cases working in order, then proceed to more complete testing of the processor.

5.1 nop and halt and illegal instructions

The following program (y86/halt.yo)

halt
 

should take 5 cycles to complete and do nothing (fetching address 0x0 four times and updating no registers or memory)

The following program (y86/nophalt.yo)

nop
nop
nop
halt
nop
 

should take 8 cycles to complete and do nothing (fetching address 0x0, 0x1, 0x2, and then 0x3 five times (never fetch address 0x4) and update no registers or memory)

The following program (y86/ins.yo)

nop
iaddq $1, %r8
halt
 

should take 6 cycles to complete, do nothing, and end with an invalid instruction error (error code 4, STAT_INS)

5.2 irmovq and rrmovq

The following program (y86/irrr7.yo)

irmovq $1, %rax
rrmovq %rax, %rbx
 

should take 7 cycles to complete and leave 1 in both %rax and %rbx.

The following program (y86/rrmovq.yo)

irmovq $5678, %rax
irmovq $34, %rcx
rrmovq %rax, %rdx
rrmovq %rcx, %rax
 

should take 9 cycles to complete and change the following registers:

| RAX:               22   RCX:               22   RDX:             162e |

The following program (y86/irrr7b.yo)

irmovq $0x1, %rax
irmovq $0x2, %rbx
irmovq $0x3, %rcx
rrmovq %rax, %rdx
rrmovq %rcx, %rbx
rrmovq %rbx, %rsi
rrmovq %rbx, %rdi

should take 12 cycles and change the following registers:

| RAX:                1   RCX:                3   RDX:                1 |
| RBX:                3   RSP:                0   RBP:                0 |
| RSI:                3   RDI:                3   R8:                 0 |

5.3 OPq

The following program (y86/opq.yo)

irmovq $7, %rdx
irmovq $3, %rcx
addq %rcx, %rbx
subq %rdx, %rcx
andq %rdx, %rbx
xorq %rcx, %rdx
andq %rdx, %rsi

should take 12 cycles and leave

| RAX:                0   RCX: fffffffffffffffc   RDX: fffffffffffffffb |
| RBX:                3   RSP:                0   RBP:                0 |

A full trace is in testdata/pipe-traces/opq.txt.

The programs y86/forward1a.yo through y86/forward4a.yo and y86/forward1b.yo through y86/forward4b.yo systematically test forwarding cases involving irmovq and OPq.

5.4 cmovXX

The following program (y86/cmovXX.yo)

irmovq $2766, %rbx
irmovq    $1, %rax
andq    %rax, %rax
cmovg   %rbx, %rcx
cmovne  %rbx, %rdx
irmovq   $-1, %rax
andq    %rax, %rax
cmovl   %rbx, %rsp
cmovle  %rbx, %rbp
xorq    %rax, %rax
cmove   %rbx, %rsi
cmovge  %rbx, %rdi
irmovq $2989, %rbx
irmovq    $1, %rax
andq    %rax, %rax
cmovl   %rbx, %rcx
cmove   %rbx, %rdx
irmovq   $-1, %rax
andq    %rax, %rax
cmovge  %rbx, %rsp
cmovg   %rbx, %rbp
xorq    %rax, %rax
cmovl   %rbx, %rsi
cmovne  %rbx, %rdi
irmovq    $0, %rbx

should take 30 cycles and leave 0xace in %rcx, %rdx, %rsp, %rbp, %rsi, and %rdi.

A full trace is available in testdata/pipe-traces/cmovXX.txt.

5.5 Other tests

make test-pipehw1 also runs the following tests, which overlap substantially with the above tests:

• prog1.yo through prog4.yo and prog8.yo
• cmov-noforward.yo
• irmovq-norcxrax.yo

6 Debugging

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;

7 Submit

Submit pipehw1.hcl on the submission page.