Y86-64 Programming

A Y86-64 program is plain text in a .ys file, and the assembler's job is to turn that text into the byte image from the previous lesson laid out at the right addresses in memory. Writing one end to end exercises all of it at once: directives place code and data, labels become addresses, the stack has to be set up by hand because there is no operating system underneath, and call/ret move the program counter through the stack. This lesson writes a complete array-sum program, follows it all the way down to the bytes, and closes with the branch-free conditional idiom that cmovXX exists for.

Directives: placing code and data

Most lines of a .ys file are instructions, but a few are assembler directives — commands to the assembler that emit no opcode of their own, only control where things land.

• .pos a sets the location counter to address a: the next byte the assembler emits goes there. A program begins with .pos 0, and we use another .pos to park the stack far from the code.
• .align k advances the location counter to the next multiple of k, padding with zero bytes. Used before data so multi-byte values sit at aligned addresses, exactly the alignment the hardware prefers.
• .quad v emits the 8-byte value v, little-endian. It is how we lay down initial data — here, the array elements.

A label is just a name for the current location counter value. When the assembler reaches sum: it records the address of the next byte under the name sum, and every call sum or jmp test elsewhere is resolved to that address.

The calling convention

Y86-64 the ISA says nothing about how procedures pass arguments; call and ret only move the PC. Everything else is convention, and Y86-64 programs adopt x86-64's System V convention wholesale (minus %r15, which Y86-64 does not have) so that compiled C maps straight over:

%rsp always aims at the top of the stack; call pushes the return address there and ret pops it. None of this is enforced by hardware. It is a contract between caller and callee in exactly the sense the first lesson gave the word: agree on it, and procedures compiled by different people compose. Because Y86-64 has no operating system underneath, one more job falls on the program itself: the very first instruction must establish the stack pointer, by loading the address of a region reserved with .pos.

A complete program: summing an array

Here is a full Y86-64 program that sums a four-element array and leaves the total in %rax. The structure is the C loop for (i = n; i != 0; i--) sum += *p++; written out in Y86-64, with a sum procedure called from a small driver. The array base and count arrive in %rdi and %rsi, per the convention.

.pos 0
irmovq stack, %rsp      # set up stack pointer
irmovq array, %rdi      # %rdi = &array[0]
irmovq $4, %rsi         # %rsi = element count
call sum                # sum(array, 4) -> %rax
halt                    # stop the machine

# long sum(long *p, long count)
sum:
irmovq $8, %r8          # %r8 = 8, the pointer stride
irmovq $1, %r9          # %r9 = 1, the loop decrement
xorq %rax, %rax         # %rax = 0, the running total
jmp test                # enter loop at the test
loop:
mrmovq (%rdi), %r10     # %r10 = *p
addq %r10, %rax         # sum += %r10
addq %r8, %rdi          # p++  (advance 8 bytes)
subq %r9, %rsi          # count--
test:
andq %rsi, %rsi         # set condition codes from count
jne loop                # if count != 0, loop again
ret                     # return, total in %rax

.align 8
array:
.quad 10                # array[0]
.quad 20                # array[1]
.quad 30                # array[2]
.quad 40                # array[3]

.pos 0x200
stack:                  # %rsp starts here, stack grows down

Three patterns are worth naming. The loop is entered at its test (jmp test), not the body — the standard guard for a count that might be zero: the body runs only once the test confirms work remains. The test is andq %rsi, %rsi, the Y86-64 idiom for set condition codes from a register without changing it (since $x\&x=x$); on the path arriving via jmp test, no arithmetic has touched the count, so the codes must be established before jne reads them. Inside the loop the pointer walks by 8 with addq %r8, %rdi rather than recomputing base + 8*i each pass — the strength-reduction answer to Y86-64's missing scaled-index mode, with the stride and decrement parked in %r8 and %r9 because addq and subq take only register operands.

To see the loop actually compute, trace the registers across the four iterations on the array [10, 20, 30, 40]. Entry has %rdi pointing at array (call it A), %rsi = 4, and %rax = 0. Each pass loads *%rdi, adds it to the total, advances the pointer by 8, and decrements the count; the loop exits when the count hits zero.

The pointer %rdi walks A, A+8, A+16, A+24 — one stride per pass, never recomputed from a base and index — and %rsi counts 4, 3, 2, 1, 0. On the pass that drives %rsi to 0, the andq sets ZF = 1, jne falls through, and %rax holds 10 + 20 + 30 + 40 = 100. The loop body has no multiply and no scaled index, just a load and three adds.

From assembly to bytes

The assembler walks the listing, tracking the location counter, and emits each instruction's bytes exactly as the encoding rules dictate. Resolving the labels gives sum = 0x028, loop = 0x047, test = 0x057, array = 0x068, and stack = 0x200, and every reference is filled in little-endian. The result is the program's memory image: a map from address to bytes.

Read the image against the reference and every byte checks out: call sum is 80 followed by 0x28 little-endian; irmovq array,%rdi is 30 f7 (no source, dest %rdi = 7) then 0x68 little-endian; addq %r10,%rax is 60 then a0 (%r10 = A, %rax = 0); mrmovq (%rdi),%r10 is 50 then a7 (dest %r10 = A, base %rdi = 7) with a zero displacement. The jumps jmp test (70 57...) and jne loop (74 47...) carry their resolved targets directly — absolute 8-byte addresses, since Y86-64 has no PC-relative branches. The four .quads lay 0a 14 1e 28 — ten, twenty, thirty, forty — at 0x068 onward, eight bytes apiece.

The stack during the call

The program's one subroutine call exercises the stack. call sum executes two updates atomically, then ret reverses them:

The return address ${\text{PC}}_{\text{ret}}$ is the instruction after the call, here 0x027. The stack grows downward from stack = 0x200, so the pushed address lands at $0x200-8=0x1f8$.

This hand-built stack is the same machinery the procedures lesson treats in x86-64, stripped to its essentials: call and ret are nothing more than a push and a pop of the program counter.

A second pattern: branch-free max

The array sum exercises loops; the second pattern is the branch-free conditional, the reason cmovXX is in the instruction set. Here is long max(long a, long b) with a in %rdi and b in %rsi, returning in %rax:

# long max(long a, long b)
max:
rrmovq %rdi, %rax       # result = a, provisionally
rrmovq %rsi, %r10       # copy b: subq would destroy it
subq %rdi, %r10         # %r10 = b - a, sets CC
cmovg %rsi, %rax        # if b > a, result = b
ret

Two Y86-64 habits show up in four instructions. First, the comparison costs a spare register: Y86-64 has no cmpq, so testing $b-a$ means running subq, and subq %rdi, %r10 overwrites %r10 — hence the copy, keeping %rsi intact for the cmovg. Second, the conditional is straight-line: every execution runs all instructions, and the condition governs only whether the move commits,

The branching version (jle around an rrmovq) computes the same answer, but its jump is unpredictable when the data is, and the pipelined processor pays for every misprediction. cmovg reads the codes subq set — g holds exactly when $b-a>0$ with the overflow correction folded in — and the PC never leaves the straight path.

With complete programs assembled into bytes, a working stack, and both loop and conditional idioms in hand, every piece the next module needs is in place: the sequential processor fetches and decodes byte images in exactly this format, programs just like this one, one instruction at a time.

The convention in the real world

The calling convention this lesson borrows wholesale from x86-64 is the System V AMD64 ABI, the same document every C compiler, linker, and debugger on Linux and macOS agrees to. A few of its real-world corners are worth knowing, because they are exactly the parts Y86-64's tiny programs never grow large enough to need.

Stack frames and the frame pointer. The sum procedure above uses no stack space of its own — it keeps everything in registers, so its frame is just the return address call pushed. Real procedures with locals or many live values allocate a stack frame: they subtract from %rsp on entry to reserve space, keep locals at fixed displacements from the frame base, and add it back on exit.¹ CS:APP's procedures lesson develops this in x86-64; the Y86-64 mechanics are identical, because call, ret, pushq, and popq are the same, only the programs here stay small enough to dodge the frame.

The red zone. The System V ABI reserves 128 bytes below %rsp — the red zone — that a leaf function (one that calls nothing) may scribble in without adjusting %rsp at all, because no call will overwrite it. This is a pure performance convention: it saves the sub/add pair around %rsp in the common case of a small helper, exactly the kind of function sum is. Nothing in the hardware knows about the red zone; it is a promise the compiler and the ABI make to each other, in precisely the sense the first lesson gave the word convention.

Why andq x, x and not a compare. The loop-entry idiom of this lesson — andq %rsi, %rsi to set the flags from a register without changing it — is a Y86-64 necessity, but the same shape appears in real x86-64: testq %rsi, %rsi is the standard compiler emission for is this register zero or negative?, chosen over cmpq $0, %rsi because it is one byte shorter and needs no immediate. The idiom this module frames as a workaround for Y86-64's missing compare turns out to be what production compilers emit anyway, for the density reason.