Instruction decoding long has been a bottleneck for the x86 architecture, which was designed in the mid-1970s and has been held to a high standard of backward compatibility throughout its history. x86 instructions can range from one to fifteen bytes long, with optional prefixes that change the meaning of the bytes that follow them, so a decoder presented with a 16-byte block of instruction bytes cannot know where the second instruction starts until it has at least partially decoded the first. For decades, x86 designers have worked to make that serial problem look parallel (predecoding instruction lengths, marking instruction boundaries in the instruction cache, decoding several instructions per cycle once the boundaries are known), and all of those techniques cost power on every fetch, since the same bytes in a hot loop are decoded again on every iteration.

Sandy Bridge (2011) added a cache of the decoder’s output: about 1,500 µops, indexed by the virtual address of the instructions that produced them. When the front end finds a fetch address in the µop cache, it bypasses the legacy decoders entirely and streams µops into the back end at higher bandwidth, and lower power, than decoding would have permitted. AMD’s Zen cores have had an equivalent op cache since 2017.

The idea had been tried before, more ambitiously, when the Pentium 4 replaced its first-level instruction cache with a trace cache of about 12,000 µops, which stored instructions not in address order but in the order the program was predicted to execute them, so a single trace could run through several taken branches. The trace cache therefore was a hybrid of the two structures that this series keeps separate: a memo of the decoder’s output, which must be correct, arranged according to a branch prediction, which need not be. When the trace cache missed, the Pentium 4 fell back to a decoder that handled only one x86 instruction per cycle (a regression from the Pentium Pro’s decoder that could handle up to 3 instructions/clock), and performance accordingly fell off a cliff. The Core microarchitecture abandoned the trace cache, and when the µop cache returned with Sandy Bridge, it was indexed by address rather than by trace, and backed by a full-width decoder.

Like the TLB, the µop cache holds derived state that must be correct, and if the inputs change, that state must be discarded. Further complicating the picture: to support x86 backward compatibility, stores to instruction bytes (by self-modifying code, or more commonly, by a JIT compiler) must be made visible to subsequent instruction fetches without any action by software. Self-modifying code was once a legitimate optimization, but as instruction caches have become more sophisticated, it has started to incur performance penalties that more than offset the benefits. Intel’s manual observes that a write to an instruction already “decoded and resident in the trace cache invalidates the entire trace cache,” so that “programs that self-modify code can cause severe degradation of performance.”1 Intel does not document what a modern core does to its µop cache; the only public signal is MACHINE_CLEARS.SMC, which counts the machine clears and says nothing about what was discarded.

Hardware support for self-modifying code is an x86 anachronism. Most RISC architectures require extensive software intervention when the program has written opcodes into memory and intends to start executing them. On Arm, a JIT compiler must clean the data cache, invalidate the instruction cache, and issue barriers before transferring control to the newly written code2. Arm’s arrangement is more modern, and more economical, because it reduces the costs of hardware implementation by placing a reasonable burden on the software. In contrast, x86 hardware must monitor every store instruction and discard decoded copies whenever one lands on cached instruction bytes.

Derived state that must be correct has one practical advantage: the slow path is always present, and always correct, so if the structure that memoizes it turns out to be broken, it can be switched off. Intel has done that twice on the same microarchitecture, beginning with the loop stream detector, which captures the µops of a small loop and replays them without involving the fetch and decode stages. Intel disabled the feature on Skylake and Kaby Lake with a 2017 microcode update, after an erratum designated SKL150 revealed that short loops using the legacy high-byte registers (AH, BH, CH, and DH) could misbehave when both hyperthreads were active. (Users of the OCaml compiler had spent months chasing intermittent crashes before one of them spotted the erratum in a Linux distribution’s microcode changelog and matched the two3.) Two years later, the so-called JCC erratum prompted a microcode update that forbade the µop cache from holding any jump instruction that crossed or ended on a 32-byte boundary, at a cost Intel put at 0 to 4 percent on many industry-standard benchmarks. In both cases, the fix made the machine slower, not wrong; and in the second case the toolchains responded, with the GNU assembler adding an option (-mbranches-within-32B-boundaries) that pads code so jumps avoid the forbidden alignments.

Time will tell whether compilers continue to target the µop cache by emitting code accommodating its alignment requirements, CPU vendors continue to increase hardware capabilities to enable more use cases, or both.

How to Detect It

Names are Intel’s for Skylake and Ice Lake, and AMD’s for Zen 4.

• µops delivered by the legacy decoders instead of the µop cache.

  • Intel: IDQ.DSB_UOPS against IDQ.MITE_UOPS, with DSB2MITE_SWITCHES.PENALTY_CYCLES and FRONTEND_RETIRED.DSB_MISS

  • AMD: de_src_op_disp.op_cache against de_src_op_disp.decoder, with op_cache_hit_miss.op_cache_miss

• Machine clears for self-modifying code.

  • Intel: MACHINE_CLEARS.SMC

  • AMD: resyncs_or_nc_redirects, which combines every cause of a resync

A self-modifying-code machine clear is the µop cache discarding stale decodes, and AMD reports it only through a counter that combines every cause of a pipeline resync.

Working Around It

Keep writes away from running code. A store to a cache line holding instructions that are in the pipeline triggers a self-modifying-code machine clear, so a JIT compiler should keep the data it writes off the lines, and preferably the pages, holding code that is running.

Lay out code for the front end. Large programs often are limited less by any single misbehaving branch than by the sheer volume of code they execute, which overflows the instruction cache, instruction TLB, µop cache, and BTB at once. Profile-guided optimization, and post-link optimizers such as BOLT and Propeller, address all four together, by gathering hot code into a contiguous region and moving cold code out of the way, enabling the hardware to more effectively support the code that actually runs4. Where a microcode update has imposed alignment rules on the µop cache, as the JCC erratum did, the assembler option it prompted (passed through the compiler as -Wa,-mbranches-within-32B-boundaries) can recover much of the loss. Finally, unrolling that helps a small loop on paper can hurt it in practice, if it pushes the loop out of the µop cache.

Further Reading

• Xavier Leroy, How I found a bug in Intel Skylake processors — Months of intermittent OCaml crashes, traced to an erratum by way of a Debian microcode changelog.

• Panchenko and coauthors, BOLT: A Practical Binary Optimizer — What laying out code for the front end looks like when it is done to a whole datacenter binary.