Tracing a Program

We have a complete datapath and we have proven it correct on two instructions in isolation. The last thing to do is the thing the whole module was for: run a real program and watch state evolve. Correct stages in isolation are not enough: a processor must, started at an address, drive itself through a program by the loop we built, cycle after cycle, with no external help. This lesson takes a short Y86-64 program, sets it on SEQ, and traces every cycle until it halts. If the registers hold the right answer at the end, the assembled datapath and control logic are a working CPU. They do.

The program

We compute $1 + 2 + 3 = 6$ with a countdown loop: start a counter at 3, add it to a running sum, decrement, and repeat until the counter hits zero.

sum.ysassembly

        irmovq $3, %rdi      # rdi = n = 3   (loop counter)
        irmovq $0, %rax      # rax = sum = 0
        irmovq $1, %r8       # r8  = 1       (decrement constant)
loop:
        addq   %rdi, %rax    # sum += n
        subq   %r8,  %rdi    # n   -= 1
        jne    loop          # if n != 0, repeat (tests ZF)
        halt

The assembler lays this out from address 0x00. Each irmovq is 10 bytes, each OPq is 2, the jne is 9, and halt is 1, giving the byte addresses below, which is what the PC steps through.

The byte layout of sum.ys from address 0. The three irmovq each take 10 bytes, so the loop body starts at 0x1e; addq and subq are 2 bytes each, jne is 9, and halt is 1. The jne destination is the loop label, 0x1e.

How to read one cycle

SEQ executes one instruction per clock cycle: in a single tick it fetches, decodes, executes, touches memory, writes back, and updates the PC, then the new register and PC values clock in at the rising edge, ready for the next cycle. So one row of the trace is one cycle is one instruction. For each we record the PC, the instruction fetched there, the salient stage computations, and the resulting state.

The three irmovq cycles are the warm-up. Each fetches at its address, passes the immediate through the ALU (valE = 0 + valC), and writes valE to its register; none touches memory or the condition codes, and newPC = valP.

Cycles 1-3: the three irmovq instructions load the initial registers. Each computes valE = 0 + valC and writes it to dstE = rB; PC advances by 10 each time (valP). No memory, no condition codes. After cycle 3 the loop begins.

After cycle 3 the state is $%rdi = 3$ , $%rax = 0$ , $%r8 = 1$ , condition codes unset, and $PC = 0x1e$ — the loop entry. Now the interesting part.

The loop, cycle by cycle

Each iteration is three cycles: addq, subq, jne. The addq updates the sum and sets the condition codes; the subq decrements the counter and sets them again; the jne reads ZF to decide whether newPC is the loop target valC = 0x1e (taken) or the fall-through valP = 0x2b (not taken). Watch %rax climb and %rdi fall.

Cycles 4-12: three loop iterations. Each addq adds %rdi into %rax; each subq drops %rdi by 1 and sets ZF; each jne takes the branch (newPC=0x1e) while ZF=0, and falls through (newPC=0x2b) when the last subq makes %rdi 0, setting ZF=1. The sum reaches 6.

Three iterations and the loop is done. The first addq adds 3, the second 2, the third 1, so %rax walks $0 \to 3 \to 5 \to 6$ . Each subq drops %rdi by one, $3 \to 2 \to 1 \to 0$ ; the moment it reaches 0, that subq sets ZF = 1, and the following jne reads ZF = 1, so its branch condition Cnd is false and newPC falls through to 0x2b instead of looping. Cycle 13 fetches halt at 0x2b, which sets Stat = HLT, and the machine stops with $%rax = 6$ — the sum $1 + 2 + 3$ , exactly as the program intends.

Laying out the register state across the twelve loop cycles as one table makes the convergence visible.

Register and flag state after each loop cycle (cycles 4-12), plus the halt. %rax accumulates 3, 5, 6 while %rdi counts down 2, 1, 0; the subq that zeroes %rdi sets ZF=1, so the next jne falls through and halt stops with %rax = 6. %r8 stays 1 throughout.

Read down the %rax column and the program's whole purpose is visible: 3, 3, 3, 5, 5, 5, 6, 6, 6, 6 — the sum settling as each iteration folds in one more term. Read down ZF and the loop's exit condition is visible: it is 0 until cycle 11's subq zeroes %rdi, and the cycle-12 jne that reads it is the one that finally falls through.

Cycle 4 under the microscope

The trace above records outcomes. To connect it back to the control logic, freeze one cycle and write down every named signal: the full contents of the stage tables and HCL, evaluated with real numbers. Take cycle 4, the first addq %rdi, %rax, fetched at 0x1e with %rdi = 3 and %rax = 0.

Every signal of cycle 4, the first addq %rdi,%rax. Fetch splits the two bytes 60 70 into icode 6, ifun 0, rA 7, rB 0; the control logic selects srcA=rA, srcB=rB, dstE=rB; the ALU adds 0x0 and 0x3; nothing touches memory; the E port commits 0x3 to %rax and the PC advances to 0x20.

Every entry is forced. The bytes 60 70 are forced by the assembler; the selects srcA = rA, srcB = rB, dstE = rB are the OPq lines of the HCL; the values 0x3 and 0x0 are what cycles 1 and 2 left in the registers; ZF = 0 because 0x3 is nonzero. Each signal traces back to the matching case expression in lesson 3; this table is that logic, evaluated once.

A snapshot mid-flight

The same cycle, drawn on the datapath. The figure shows the live values on the key wires as the instruction climbs the bands.

SEQ frozen during cycle 4, the addq %rdi,%rax of the first iteration. Fetch at PC 0x1e yields icode 6:0; Decode reads valA=3 (%rdi), valB=0 (%rax); the ALU adds to valE=3 and sets ZF=0; Write-back stores 3 into %rax; newPC=0x20.

Every value on that snapshot was derived, not asserted: valA = 3 because Decode read %rdi, which cycle 1's irmovq set; valE = 3 because the ALU added valB = 0 and valA = 3; ZF = 0 because the result is nonzero; newPC = 0x20 = 0x1e + 2 because addq is two bytes and is not a branch. The control logic of lesson 3 chose every mux input; the stage tables of lesson 2 defined every computation; the datapath carried the bits. Nothing outside the machine intervened.

A second program: call and ret through the stack

sum.ys never touches memory. To watch the stack machinery — the %rsp bookkeeping, the memory write of a return address, the valM-into-PC wire — run a second program, five instructions long.

callret.ysassembly

        irmovq $0x100, %rsp  # 0x000: set up the stack
        call sum3            # 0x00a: push 0x013, jump to sum3
        halt                 # 0x013: after the return
sum3:
        irmovq $6, %rax      # 0x014: the function body
        ret                  # 0x01e: pop 0x013 into the PC

The layout: irmovq (10 bytes) at 0x000, call (9 bytes) at 0x00a, halt at 0x013, then sum3 at 0x014 with its irmovq and the ret at 0x01e. Five cycles run: the two irmovqs bracket the call (cycles 1–3), then ret (cycle 4) and halt (cycle 5). The two cycles worth tracing in full are the call and the ret.

Cycle 2 (call sum3, left) and cycle 4 (ret, right), every stage in hex. call computes valE = 0x100 - 8 = 0xf8, stores the return address 0x013 there, commits %rsp = 0xf8, and jumps to valC = 0x014. ret reads valA = 0xf8, loads valM = 0x013 from it, commits %rsp = 0x100, and jumps to valM.

The two tables are mirror images through the stack. call writes 0x013, an address it computed as valP (the byte after its own 9-byte body), into memory at the decremented %rsp, and that number sits inert at 0xf8 for two cycles while sum3 runs. Then ret, knowing nothing about who called, reads whatever the top of the stack holds, and the machine lands back at halt. The trace confirms what the procedures lesson claimed: a return address is just a word in memory, trusted absolutely.

Check the arithmetic that has to line up for this to work, because a single wrong constant would break it. The call sits at 0x00a and is 9 bytes long, so its valP is $0x00a + 9 = 0x013$ — the address of the halt, the point where control should resume. Execute decrements the stack pointer by 8, so $0x100 - 8 = 0xf8$ , and Memory stores 0x013 there. When ret runs, its Execute adds 8 back ( $0xf8 + 8 = 0x100$ , restoring %rsp), but its address is valA = 0xf8, the pre-increment top, so it reads the word 0x013 that call left — not the word above it. The off-by-eight bug flagged in lesson 3's memory control amounts to using valE = 0x100 as the read address instead of valA = 0xf8; the trace shows the correct choice landing back on 0x013 and the halt, and any other choice would return into garbage.

The stack during callret.ys. call decrements %rsp from 0x100 to 0xf8 and stores the return address 0x013 at the new top; ret reads it back and restores %rsp to 0x100. The word at 0xf8 still holds 0x013 afterward — ret reads, it does not erase.

Counting cycles and the CPI that motivates pipelining

The trace also lets us measure SEQ, and the measurement motivates the next module. sum.ys executed 13 instructions in 13 cycles: three irmovq, three loop iterations of three instructions each, and one halt. SEQ runs exactly one instruction per cycle, so its cycles per instruction (CPI) is exactly 1 — you cannot do better than one instruction every clock tick if the whole machine is one big combinational settle per instruction.

CPI is only half of what determines speed. The usual accounting (Bryant & O'Hallaron, CS:APP §4.3 and §5.7) writes a program's running time as

time = instructions \times CPI \times clock period,

and SEQ wins the middle factor (CPI = 1) only by paying dearly on the third. The clock period had to cover the entire critical path — instruction fetch, register read, ALU, data memory, and the New-PC mux in series — so on the illustrative delays of the previous lesson that period was near 390 ps. Every one of sum.ys's 13 cycles was that long, even the addq cycles that needed no memory at all.

Pipelining attacks the third factor without giving up much of the first. If the six stages each get their own clock band and several instructions occupy different stages at once, the clock period drops toward the delay of the single slowest stage (roughly the 120 ps of a memory access) rather than the sum of all of them. The ideal is CPI still near 1 but a clock several times faster — which, on a straight-line program like sum.ys, is a several-fold speedup for free. The catch is the loop: sum.ys's jne does not know its target until it has been executed, and a pipeline that has already begun fetching past the branch may have guessed wrong. Resolving those hazards — data dependencies between overlapping instructions, and control dependencies at branches — is the entire subject of the pipelining module, and this trace is the baseline it improves on: correct, simple, and one instruction slow at a time.

What we have built

The traces close the loop the module opened. Twelve cycles of pure combinational choices, clocked one instruction at a time, took three registers from an initial state to the correct answer and stopped at the right place; five more cycles pushed a return address, ran a function, and came back through it, and at no point did anything direct the machine but its own PC and the bytes it pointed at. That is the entire claim of the stored-program computer, realized in logic we specified gate by gate.

The course has now gone from bits and bytes, through an instruction set, through gates and memory, to a circuit that runs programs. From here the questions become how fast — the same six stages, overlapped in a pipeline so several instructions are in flight at once — and how to keep the data close, with the memory hierarchy and caches.