Arithmetic and Logic

With operands in place, the machine computes. x86-64's integer arithmetic and logic instructions are a compact set: a few binary operations, a few unary ones, the shifts, and the bitwise logicals. Two facts make them more than a table to memorize. First, lea from the previous lesson doubles as an arithmetic instruction. Second, almost every arithmetic instruction quietly sets the condition-code flags as a side effect, and those flags are what the conditional jumps of the next lesson read.

Binary and unary operations

The binary operations take two operands and write the result to the destination, following the AT&T source-then-destination order. The destination accumulates: D becomes D op S, not S op D. This matters for the non-commutative sub.

The operand order is worth stating plainly: subq %rax, %rbx computes $\mathtt{rbx}\leftarrow \mathtt{rbx}-\mathtt{rax}$, subtracting the source from the destination. Reading it as rax minus rbx inverts the sign of every program you analyze.

The unary operations take a single operand that is both source and destination.

# long arith(long x, long y): x in %rdi, y in %rsi
addq    %rsi, %rdi        # rdi = x + y
imulq   $3, %rdi          # rdi = 3*(x+y)
negq    %rdi              # rdi = -(3*(x+y))
movq    %rdi, %rax        # result to the return register
ret

By convention a procedure's result comes back in %rax, hence the final movq; the rule is made precise in the lesson on procedures.

lea as a fast arithmetic trick

The lea instruction from data movement computes Imm + Rb + Ri·S and stores it. Used on plain integers rather than addresses, it is a three-input adder with a built-in small multiplier, and it does not disturb the condition codes — a property compilers exploit to compute intermediate values without clobbering flags a later branch depends on.

So leaq (%rdi,%rdi,2), %rax triples a number ($x+2x$), leaq (,%rdi,8), %rax multiplies by 8, and leaq 1(%rdi,%rsi), %rax computes $x+y+1$ — each in one flag-preserving instruction.

A compiler chains these to avoid a general multiply entirely. The function long f(long x) { return 7 * x; } has a constant multiplier, and $7x=8x-x$, so gcc computes it without imul:

# long f(long x): return 7 * x;  x in %rdi
leaq    0(,%rdi,8), %rax   # rax = 8*x   (scale-8, no base)
subq    %rdi, %rax         # rax = 8*x - x = 7*x
ret

Trace it with x = 5. The leaq computes $8\cdot 5=40$ into %rax; the subq then does $40-5=35=7\cdot 5$, the answer. Two cheap instructions replaced a multiply, and the lea never touched the flags in between. The compiler picks this strength reduction whenever the constant factors into small shifts and adds; a factor like $10=8+2$ becomes leaq (%rdi,%rdi,4), %rax (that is $5x$) followed by addq %rax, %rax (doubling to $10x$). Reading such a pair backward — scale by 8, subtract one $x$ — is how you recover the constant the source multiplied by.

Shifts

The shift instructions move the bits of the destination left or right by a count given either as an immediate or in the single-byte register %cl. Left and right each come in the flavors the two's-complement representation demands.

• sal k, D / shl k, D — shift left by k, filling with zeros. The two mnemonics are identical; left shift by k multiplies by $2^k$.
• shr k, D — logical shift right, filling the vacated high bits with zeros. This is the right shift for unsigned values.
• sar k, D — arithmetic shift right, filling the high bits with copies of the sign bit. This is the right shift for signed values, preserving the sign.

A variable count has a fixed home: the shift instructions read it only from the single-byte register %cl, never from an arbitrary register. So a shift by a computed amount first moves that amount into %cl, as in movb %r8b, %cl then shlq %cl, %rax. The immediate form shlq $3, %rax is the other option, used when the count is a constant.

The hardware then consults only the low bits of the count, masking it to the operand width: a 32-bit shift uses %cl mod 32 (its low 5 bits), a 64-bit shift uses %cl mod 64 (its low 6 bits). A count of 33 on a 32-bit value therefore shifts by 1, not 33, and never clears the whole register the way a naive reading would suggest. This masking is why a shift amount is always in range.

A quick trace shows the masking in action. Suppose %cl holds 33 and the instruction is shll %cl, %eax, a 32-bit shift. The hardware keeps only the low 5 bits of the count, and $33=0b100001$, whose low five bits are 00001 — a count of 1. So %eax shifts left by one, doubling, not by 33 (which would clear it to zero). The same %cl = 33 fed to a 64-bit shlq %cl, %rax keeps the low 6 bits, 100001, again a count of 1. The width of the operand decides how many count bits survive: 5 bits for 32-bit shifts, 6 for 64-bit, so a shift amount is always in range and can never blank a register the way a naive shift by 33 would.

The signed/unsigned split is what makes C's >> compile to sar for int and shr for unsigned.

Left shift is simpler: every bit slides toward the high end and zeros flow in at the bottom, which multiplies the value by $2^k$. This is why a compiler turns x * 8 into sal $3, x — a shift is far cheaper than a multiply.

Condition codes

Beyond their named registers, the processor keeps a few single-bit condition-code flags that record properties of the most recent arithmetic or logical result. The four that matter here are set as a side effect of nearly every ALU instruction.¹

A worked case shows all four flags at once and why signed and unsigned overflow are different events. Work in a single byte (8 bits) to keep the numbers small, and add 0x50 + 0x50 (decimal $80+80$).

Read the result three ways. The bit pattern is 0xA0 = 1010 0000. There was no carry out of the top bit, so CF = 0: as an unsigned sum, $80+80=160$ fits in a byte and is correct. But the top bit is now 1, so SF = 1, and two positive signed operands produced a negative-looking result — the definition of signed overflow — so OF = 1: as a signed sum, $80+80$ should be $160$, which does not fit in the signed byte range $[-128,127]$, and the value reads as $-96$. The same addition on the same bits produces two different overflow verdicts, which is why the conditional jumps split into signed and unsigned families in the next lesson. The processor sets every flag on every add and lets the branch pick which ones matter.

Two design points keep the flags useful. First, lea does not set flags (noted above), nor do plain mov instructions. Second, the instructions that do set them are not uniform about it: add, sub, the logicals, neg, and the shifts all update the flags, not sets none at all, and inc/dec set every flag except CF, which they leave untouched — a classic x86 quirk that lets a loop counter step without destroying a carry. So a compiler can compute an address with lea, then test a value, and trust the flags it cares about to survive.

cmp and test

Two instructions exist purely to set flags without keeping a result — exactly what a conditional branch needs, since the question is how two values compare, not what their difference is.

• cmpq S2, S1 computes $S_1-S_2$, sets the flags accordingly, and discards the difference. Note the operand order: the flags describe $S_1-S_2$, so cmpq %rsi, %rdi sets ZF when $\mathtt{rdi}=\mathtt{rsi}$ and SF/OF as if you had subtracted %rsi from %rdi.
• testq S2, S1 computes $S_1\&S_2$, sets the flags, and discards the AND. The common idiom testq %rax, %rax sets ZF exactly when %rax is zero and SF when it is negative — a register sign/zero check costing no scratch register.

# branch on whether x < y, x in %rdi, y in %rsi (signed)
cmpq    %rsi, %rdi        # flags describe rdi - rsi
jl      .Lless            # jump if x < y  (reads SF, OF)

The flags cmp and test deposit are read by the conditional jumps and set instructions, which translate the flags say %rdi < %rsi into a taken branch. That translation is the whole of the next lesson on control flow.

The operations one register cannot hold

The two-operand imulq S, D above keeps only the low 64 bits of a 64-by-64-bit product, which is all a C long multiply needs. But the true product of two 64-bit numbers is up to 128 bits, and CS:APP notes in passing that x86-64 has one-operand forms — mulq S (unsigned) and imulq S (signed) — that produce the full double-width result, splitting it across %rdx:%rax (high half in %rdx, low in %rax). Division is the mirror image: idivq S takes a 128-bit dividend in %rdx:%rax and leaves the quotient in %rax and the remainder in %rdx, which is why signed division is always preceded by cqto, an instruction whose only job is to sign-extend %rax into %rdx so the dividend is a proper 128-bit value. These fixed-register operands are a rare place where x86-64 pins specific registers, a direct inheritance from the 8086's accumulator model.²

The modern chapter the textbook predates is the BMI (Bit Manipulation Instruction) extensions Intel and AMD added around 2013. They turn common bit idioms that once took several instructions into one: andn computes ~x & y without a separate not; blsr clears the lowest set bit; tzcnt and lzcnt count trailing and leading zeros directly, which compilers emit for C's __builtin_ctz and __builtin_clz; and pdep/pext scatter and gather bits under a mask. A compiler targeting a recent -march will replace a hand-rolled bit-twiddle loop with one of these, so a shift-and-mask sequence you expect may appear as a single unfamiliar mnemonic. They obey the same operand grammar as the classic ALU instructions, only with more specialized semantics.³