Out-of-order execution on x86-64 cores

An out-of-order core does not run instructions in program order. It splits them into micro-ops, keeps a window of them, and starts each one once its inputs are ready and a unit is free, so that later independent work fills the cycles in which an earlier instruction waits, for a load from memory for instance. A dependency chain is what it cannot overlap: when every instruction waits for the result of the one before, the chain runs at the pace of its latencies however wide the core is. [Agner Fog, Chapter 2 and Section 2.1, page 11; Intel 248966, Section 3.5, page 3-20]

Every instruction that writes a register is given a fresh physical register for its result. A later write to the same name therefore does not wait for the readers of the earlier value, and code may reuse a few register names for unrelated work at no cost. The general registers, the flags and the vector registers are renamed on every core here; state a core does not rename, as many older cores did not rename the x87 control word, makes the code that writes it slow. [Agner Fog, Section 2.2, pages 12 and 13; Agner Fog, Section 11.8, page 154]

The size of the window bounds how far past a waiting instruction a core can look. The reorder buffer holds 224 micro-ops on Skylake and 512 on Golden Cove, the latter by LLVM’s model since Intel gives no size, and the retire queue 256 macro-ops on Zen 3, 320 on Zen 4 and 448 on Zen 5, where each of two threads sharing the core gets half. [Agner Fog, Section 11.1, page 152; LLVM 23.1.2, X86SchedAlderlakeP.td, line 17; AMD 56665, Section 2.10.3, pages 40 and 41; AMD 57647, Section 2.10.3, page 33; AMD 58455, Section 2.10.3, page 42]

Other resources can run out first. Allocation also stalls when a scheduler, the load or store buffer or a register file has no free entry. Zen 5 has 240 integer physical registers, up to 40 of them per thread holding architectural state, and 192 more for flag results; Agner Fog puts its vector register file at 384 registers of 512 bits. [Intel 248966, Section 22.4.1.1, page 22-19; AMD 58455, Section 2.10.3, page 42; Agner Fog, Section 25.7, page 256]

Instructions retire in order, so a load that misses the caches holds the head of the window while the core runs whatever does not depend on it, until the window fills; Intel reads a reorder buffer that is often full as a sign of such misses. Agner Fog notes that Zen 5 has registers enough to run several iterations of a loop at once, but only when no value passes from one iteration to the next and the loop ends on a simple counter with a limit known in advance. [AMD 58455, Section 2.10.3, page 42; Intel 248966, Section 22.8.3.1, page 22-71; Agner Fog, Section 25.21, page 260]

The narrowest stage sets the peak rate: 4 micro-ops a cycle through Skylake, 6 allocated and 8 retired a cycle on Golden Cove, 6 macro-ops dispatched on Zen 3 and Zen 4 and 8 on Zen 5. Agner Fog expects about 6 instructions a cycle on Zen 5 in practice, and only from code spread over its units without long dependency chains. [Agner Fog, Sections 11.1 and 11.2, page 152; Intel 248966, Sections 2.4 and 2.4.1, pages 2-10 and 2-11; AMD 56665, Section 2.9.6, page 37; AMD 57647, Section 2.9.8, page 30; AMD 58455, Section 2.9.7, page 39; Agner Fog, Section 25.21, page 260]

PUSH, POP, CALL and RET each change RSP, which would chain every stack operation to the one before it. A stack engine at the renaming stage tracks those changes on Intel’s and AMD’s cores, so they need no execution unit and no wait. An instruction that uses RSP explicitly between them, such as add rsp, 8 on Skylake, costs a micro-op that brings the engine’s value back in step, and on AMD’s cores every use of RSP the engine does not handle costs an extra op and restarts the tracking (Zen 5). [Agner Fog, Section 2.1, pages 11 and 12; Agner Fog, Section 11.7, page 154; AMD 57647, Section 2.9.7, pages 29 and 30; AMD 58455, Section 2.9.6, page 38]

xor eax, eax and sub eax, eax give zero whatever EAX held, and every core here recognizes them as it renames: the result needs no execution unit and does not wait for the old value, so the idiom also ends any chain through the register. This holds for 32-bit and 64-bit registers but not for 8-bit and 16-bit ones, whose other bits are kept. Intel prefers the idioms to moving a zero into the register. [Intel 248966, Section 3.5.1.7, page 3-25; Agner Fog, Section 11.8, pages 154 and 155; AMD 58455, Section 2.9.2, page 35; Agner Fog, Section 25.14, page 258]

The vector registers have idioms of their own: pxor, xorps, xorpd, pandn, andnps, the integer subtractions psub and the comparisons pcmpgt of a register with itself, with their VEX and EVEX forms, which Intel counts for 512-bit registers only unmasked. Skylake and AMD’s cores clear the register without an execution unit. [Intel 248966, Section 3.5.1.7, page 3-25; Agner Fog, Section 11.8, pages 154 and 155; AMD 57647, Section 2.9.2, page 27; AMD 58455, Section 2.9.2, page 35]

A floating-point subtraction of a register from itself is not a safe way to zero it, since a NaN input gives NaN. Agner Fog found that Zen 3, Zen 4 and Zen 5 never treat subps of a register from itself, or such a floating-point comparison, as free of the register’s old value, and neither his list for Skylake nor LLVM’s Skylake model includes them. [Agner Fog, Sections 23.14 and 24.14, pages 245 and 251; Agner Fog, Section 25.14, page 258; Agner Fog, Section 11.8, page 154; LLVM 23.1.2, X86SchedSkylakeClient.td, line 1729]

The idioms write the flags, as any xor or sub does. Where the flags must survive, as between a comparison and the branch that reads it, mov eax, 0 sets the register instead, at the price of a longer instruction and, on Intel’s cores, an execution unit. [Intel 248966, Section 3.5.1.7, Rule 32, page 3-25; AMD 58455, Section 2.9.2, page 35]

pcmpeqd xmm0, xmm0 and the other equality comparisons of a register with itself set every bit without waiting for the old value. AMD’s Zen 3 to Zen 5 list them as ones idioms; Agner Fog found that Skylake does not wait for the register either but still spends an execution unit on them. [AMD 56665, Section 2.9.2, pages 34 and 35; AMD 58455, Section 2.9.2, page 35; Agner Fog, Section 11.8, page 155]

AMD’s cores recognize two more: cmp eax, eax, which takes no cycle, and sbb eax, eax, which turns the carry flag into 0 or all ones in one cycle without waiting for EAX. Agner Fog found that Skylake treats neither specially. LLVM 23.1.2 follows this: tuned for AMD’s cores it makes such a mask with the bare sbb, and for others it zeroes the register first. [AMD 58455, Section 2.9.2, page 35; Agner Fog, Section 11.8, page 155; LLVM 23.1.2, X86.td, line 646; LLVM 23.1.2, X86.td, line 1703; LLVM 23.1.2, X86ISelDAGToDAG.cpp, line 6538]

Some instructions that overwrite their whole destination still wait for its old value, a flaw of particular cores: LLVM’s tunings mark popcnt from Sandy Bridge to the Skylake family and lzcnt and tzcnt on Haswell, AMD names tzcnt and three BMI1 instructions on some versions of Zen 5, and Intel several AVX-512 permutations and multiplications on Golden Cove (Skylake, Zen 5, Golden Cove). A zeroing idiom on the destination first removes the wait, and LLVM inserts one when tuning for those cores. [LLVM 23.1.2, X86.td, line 1044; LLVM 23.1.2, X86.td, line 1077; LLVM 23.1.2, X86.td, line 1108; LLVM 23.1.2, X86InstrInfo.cpp, line 6819; AMD 58455, Section 2.9.9, page 39; Intel 248966, Section 2.4.1.2, pages 2-15 and 2-16]

A register-to-register copy can be made at renaming, by pointing the destination at the physical register of the source; the move then has no latency and uses no execution unit. Intel’s cores from Ivy Bridge on and AMD’s Zen 3 to Zen 5 do this for mov between 32-bit or 64-bit registers and for whole-register vector moves such as movaps and movdqa and their VEX and EVEX forms, and AMD’s also for xchg of two such registers. [Intel 248966, Section 3.5.1.12, page 3-29; Agner Fog, Section 9.8, page 131; AMD 56665, Section 2.9.4, page 36; AMD 58455, Section 2.9.5, page 37; Agner Fog, Section 25.13, page 257]

Elimination has limits. Moves into 8-bit or 16-bit registers and MMX registers are not eliminated, and on Intel’s cores neither is a register moved onto itself, such as mov eax, eax to clear the upper half of RAX, so a move into another register is cheaper. Intel’s cores can also run short of the resources it needs: Agner Fog found it working in more than 80% of cases, and Intel shows a loop that runs about 8% faster when the registers involved are overwritten soon after each move. [Agner Fog, Section 11.8, page 155; Agner Fog, Section 25.13, page 257; Intel 248966, Section 3.5.1.12, Example 3-23, page 3-30]

Intel’s list of moves eliminated from Ivy Bridge on includes movzx from an 8-bit register other than AH, BH, CH and DH into a 32-bit or 64-bit one, which Agner Fog confirmed on Ivy Bridge, and LLVM’s Alder Lake model gives that movzx a latency of zero. AMD’s lists of zero-cycle moves for Zen 3 to Zen 5 do not include it. [Intel 248966, Section 3.5.1.12, Example 3-21, page 3-29; Agner Fog, Section 9.8, page 131; LLVM 23.1.2, X86SchedAlderlakeP.td, line 1432; AMD 56665, Section 2.9.4, page 36; AMD 58455, Section 2.9.5, page 37]

Golden Cove goes further: Agner Fog found that adding a small constant to a register sometimes takes no time, and LLVM’s model gives add and sub of an 8-bit immediate to a 64-bit register no micro-op at all (Golden Cove). [Agner Fog, Chapter 13, page 173; LLVM 23.1.2, X86SchedAlderlakeP.td, line 572]

A write to AL, AH or AX, such as mov al, [rsi], keeps the rest of RAX, so its result must be merged with the old value. AMD’s Zen 3 to Zen 5 keep each integer register whole: a write to any part of it waits for the last write to the register, a false dependency when only the low byte matters. A 32-bit write is different on every core: it clears the upper half of the 64-bit register and depends on nothing. [Agner Fog, Sections 23.13 and 24.13, pages 245 and 251; Agner Fog, Section 25.13, page 257]

Intel’s cores since Skylake merge a write of AL or AX into the full register without a stall or an extra micro-op. The high bytes still cost: reading EAX after a write of AH takes a merging micro-op and a cycle more, and operations on AH, BH, CH and DH run on fewer ports, with a latency of three cycles on Golden Cove (Skylake, Golden Cove). [Intel 248966, Section 3.5.2.3, page 3-32; Agner Fog, Section 11.11, page 159]

Writing whole registers avoids the question on every core: Intel advises working on 32-bit registers rather than 8-bit or 16-bit ones, loading bytes and words with movzx, and choosing zero extension over sign extension where the value allows. LLVM 23.1.2 does this late in compilation, turning byte and word loads and copies whose upper bits nothing reads into 32-bit forms or movzx. [Intel 248966, Section 3.5.1.7, Rules 33 and 34, page 3-26; LLVM 23.1.2, X86FixupBWInsts.cpp, line 15]

setcc writes a single byte, so making a 32-bit 0 or 1 of a condition takes either a movzx after it or a zeroing idiom before. LLVM 23.1.2 takes the second, placing xor eax, eax ahead of the instruction that sets the flags and setcc al after it: the idiom cuts the dependency on the old EAX and the code is shorter. [LLVM 23.1.2, X86FixupSetCC.cpp, line 14; LLVM 23.1.2, X86FixupSetCC.cpp, line 130]

Some instructions write only part of the flags: inc and dec leave the carry flag as it was, and bt leaves the zero flag. An instruction that then reads flags from two writers needs them merged, which Intel’s cores since Sandy Bridge do with an extra micro-op rather than a stall; Agner Fog saw Skylake add one for a cmovbe after bt, though none after inc, dec or a shift. AMD’s Zen 3 to Zen 5 track parts of the flags apart, so writing the carry flag alone does not wait for the zero flag. A test, which writes all the flags, between the two avoids the merge. [Intel 248966, Section 3.5.2.5, pages 3-33 and 3-34; Agner Fog, Section 11.11, pages 159 and 160; Agner Fog, Section 25.13, page 257; Intel 248966, Section 3.5.1.8, page 3-27]

A shift or rotate by CL leaves the flags alone when the count is zero, which is known only when it runs, so it depends on the old flags too. Sandy Bridge and Ivy Bridge split it into three micro-ops, and using its flags, or following a dec, which keeps the old carry, makes it take the slow path; a sub in place of the dec avoids that. LLVM’s models give a shift by CL three micro-ops on Skylake and two on Golden Cove, against one on Zen 3 and Zen 4. [Intel 248966, Section 3.5.1.5, page 3-24; Intel 248966, Section 3.5.2.5, page 3-33; LLVM 23.1.2, X86SchedSkylakeClient.td, line 196; LLVM 23.1.2, X86SchedAlderlakeP.td, line 413; LLVM 23.1.2, X86ScheduleZnver3.td, line 741; LLVM 23.1.2, X86ScheduleZnver4.td, line 753]

Scalar SSE instructions that write only the low element of an XMM register keep the rest of it, and so wait for its last writer: movss and movsd between registers, movlpd and movhpd from memory, and conversions and square roots such as cvtsi2sd and sqrtss. Intel advises copying registers whole with movaps or movapd, loading 64 bits with movsd or movq, which clear the rest, and avoiding the partial loads. [Intel 248966, Section 3.5.2.4, pages 3-32 and 3-33; Intel 248966, Section 3.5.2.6, Rule 39, pages 3-34 and 3-35; AMD 58455, Section 2.11.5, page 48]

AMD’s Zen 3 to Zen 5 soften this. They remember which XMM registers have upper parts known to be zero, through any later instructions that keep them so, and let a list of scalar instructions, sqrtss, cvtsi2sd and movss between registers among them, skip the wait on such a register. AMD therefore advises clearing a vector register with a zeroing idiom when done with it, which also frees its physical register. [AMD 56665, Section 2.11.5, pages 44 and 45; AMD 58455, Section 2.11.5, page 48; AMD 58455, Section 2.11.2, page 46]

Compilers break these dependencies themselves. LLVM 23.1.2 puts an xorps (vxorps with AVX, vpxord for XMM16 to XMM31) before cvtsi2sd, sqrtss and the other partial writers when the register was written within the last 64 instructions, a distance its hidden option -partial-reg-update-clearance changes. [LLVM 23.1.2, X86InstrInfo.cpp, line 74; LLVM 23.1.2, X86InstrInfo.cpp, line 6466; LLVM 23.1.2, X86InstrInfo.cpp, line 7247]

Each micro-op runs on a port, or pipe, whose unit can do its operation, so the throughput of a kind of operation depends on how many units have it: two independent multiplications cannot start together on a core with one multiplier. Intel’s cores feed their ports from schedulers shared by integer and vector work (Skylake, Golden Cove); AMD’s split the core into an integer side and a floating-point and vector side, each with its own renamer, registers and schedulers (Zen 5). [Agner Fog, Chapter 2, page 11; Agner Fog, Section 11.9, page 155; AMD 58455, Section 2.11, page 43; Agner Fog, Section 25.7, page 256]

Code that leans on one kind of operation is held up by its units even when nothing waits for a result. Operations that only one port runs, such as integer multiplication and bit counting on Skylake’s port 1 or arithmetic on AH on Golden Cove’s, queue behind one another (Skylake). Intel’s general rules prefer instructions of one micro-op and short latency, and instructions from the microcode sequencer least. [Intel 248966, Section 3.5.1, Rule 25, page 3-20; Intel 248966, Section 2.7.2, Table 2-14, page 2-35; Intel 248966, Section 3.5.2.3, page 3-32]

AMD’s cores dispatch macro-ops in groups that must suit the units behind them. On Zen 3 and Zen 4 any six in a row keep full speed only within limits per kind, such as one integer division and two multiplications (Zen 4), and an integer scheduler takes at most two a cycle; on Zen 5 a group of eight may hold at most two taken branches and eight immediates or displacements, and its eighth op may be neither a load nor a store. [AMD 56665, Section 2.10.1, page 40; AMD 57647, Sections 2.9.8 and 2.10.1, pages 30 and 33; AMD 58455, Section 2.9.7, page 39]

On AMD’s floating-point side the scheduler holds 2 times 32 macro-ops on Zen 3 and Zen 4 and 3 times 38 on Zen 5. When it is full, or on Zen 5 when more than six floating-point macro-ops come in one cycle, the rest wait in a queue before it, of 64 entries on Zen 3 and Zen 4 and 96 on Zen 5, which lets their loads and stores go ahead. [AMD 56665, Section 2.11, page 41; AMD 57647, Section 2.11, page 34; AMD 58455, Section 2.11, page 43]

Vector units are split into an integer domain and a floating-point domain, and a result that crosses between them, such as a product of mulps that pand uses, can arrive a cycle late. Intel’s general rules and AMD’s guides advise keeping to one type: xorps and andps for floating-point data, pxor and pand for integers (Zen 3, Golden Cove). [Intel 248966, Section 3.5.2.2, page 3-31; Intel 248966, Section 3.5.1.10, page 3-28; AMD 56665, Sections 2.11.1 and 2.11.2, page 43; AMD 58455, Section 2.11.2, page 46]

Latency counts the cycles from the start of an instruction until one that needs its result can start; throughput is how many such instructions complete per cycle when none waits for another. Units are pipelined, so a floating-point addition of four cycles can start a new one every cycle and have four in flight, if the code offers four that do not depend on each other. [AMD 58455, Appendix A.1, page 61; Agner Fog, Chapter 2, page 11]

Which of the two limits a loop depends on its longest chain of dependent operations carried from one iteration to the next, such as a running sum or a pointer being followed: each iteration takes at least the sum of the latencies along it, however many units are idle. Agner Fog expects latency to be the usual limit on Zen 5, whose units are rarely the bottleneck, and Intel advises code bound by latency to run more independent work or break the chains. [Agner Fog, Section 25.21, page 260; Intel 248966, Section 3.5.2.2, page 3-31]

A reduction such as the sum of an array is one chain through its accumulator. Splitting it into several accumulators, each taking every n-th element and added together after the loop, lets as many operations run at once as there are accumulators, and Intel advises at least the latency times the number of units that run the operation. By AMD’s figures vaddps on Zen 5 takes two cycles on either of two pipes, so four accumulators keep both busy, where an FMA chain on Skylake needs eight (Skylake); a chain through the addend of an FMA is better split the same way (Zen 5). [Intel 248966, Section 15.15.1, Rule 31, page 15-54; AMD 58455, latency spreadsheet, row 3 (VADDPS); AMD 58455, Section 2.11.7, page 49]

Adding floating-point numbers in another order rounds them differently, so compilers split such chains only when allowed. The x86 back end of LLVM 23.1.2 reorders chains of integer additions and logic to shorten them, but floating-point additions and multiplications only when the code permits reassociation and ignoring the sign of zero, as fast-math options do. [LLVM 23.1.2, X86InstrInfo.cpp, line 9979; LLVM 23.1.2, X86InstrInfo.cpp, line 10297]

Unrolling with many accumulators needs registers, and a value spilled to memory puts a store and a load into whatever chain it is on. Intel advises keeping values carried from one iteration to the next in registers and leaving loop invariants in memory instead, since a load of an invariant never waits for a store. [Intel 248966, Section 3.5.1.11, Rule 38, pages 3-28 and 3-29]

On the critical path the choice of instruction counts. An lea with a base, an index and a displacement takes three cycles on Sandy Bridge and runs on port 1 only on Skylake, and is two macro-ops on Zen 4 and Zen 5 (Skylake, Zen 5). Two simpler lea instructions or an add are faster there, and Intel suggests additions in place of a scaled index as well. [Intel 248966, Section 3.5.1.2, pages 3-21 and 3-22; Intel 248966, Section 3.5.1.2, Rule 30, page 3-23; AMD 57647, Section 2.10.2, page 33; AMD 58455, Section 2.10.2, page 41]