Skia: Exposing Shadow Branches

Chrysanthos Pepi, Bhargav Reddy Godala, Krishnam Tibrewala, Gino A. Chacon, Paul V. Gratz, Daniel A. Jiménez and 2 others

A modern processor runs ahead of itself, predicting branches to prefetch the code it will soon need — but that prediction relies on a table of known branches that is too small for today's sprawling data-center programs, so it constantly forgets branches and stalls; this paper (Princeton, Texas A&M, Intel) notices that most of these forgotten branches are actually already sitting in the instruction cache, in the parts of each fetched line the decoder skips over, and builds Skia, which decodes those skipped bytes to recover the hidden branches into a small side table, speeding programs up about 5.7 percent for the cost of 12 kilobytes.

The argument in one glance

Problem

The processor predicts branches to run ahead, but keeps forgetting where the branches are

To keep its execution units fed, a modern processor decouples its front-end: the branch prediction unit runs ahead of instruction fetch, predicting the path the program will take, and a prefetcher pulls the upcoming code into the instruction cache before it is needed, so fetch never stalls waiting on memory. This whole scheme rests on the processor knowing where the branches are — because a branch is where the path can turn — and it tracks that in a branch target buffer, a table recording each known branch's location and target. The trouble is that data-center applications have enormous code footprints, far more branches than the buffer can hold. So branches are constantly evicted: a branch the processor once decoded and recorded gets pushed out to make room, and the next time execution reaches it, the buffer misses. On that miss the predictor does not even recognize the current instruction as a branch, so it either fails to prefetch the right code or, worse, runs down the wrong path and pollutes the instruction cache with code that will not be used.
What people did

Make the branch target buffer bigger

The obvious remedy is a larger branch target buffer: add more entries so it can remember more branches and miss less often. Data-center processors already devote substantial area to this structure, and the natural response to more branches is simply more capacity.
Why it fell short

A bigger buffer is expensive and still misses the cold branches

Growing the branch target buffer costs precious on-chip area and power, and it scales poorly against ever-growing code footprints — you can never quite hold everything. Worse, the branches that miss most are the infrequently-executed "cold" branches, which are exactly the ones a capacity-limited buffer evicts before they are seen again, so pouring area into the buffer chases diminishing returns on the branches that hurt least while still missing the long tail that hurts most. The processor keeps rediscovering the same cold branches the slow way, at decode, after it has already stalled or mis-speculated. There is a large, recurring cost here that simply adding capacity does not efficiently address.
This paper's idea

Decode the branches already hiding in the cache lines you fetched

Skia starts from a striking observation: the vast majority — 75 percent — of these missing, unrecognized branches are already sitting in instruction-cache lines the prefetcher has already fetched. They are just never decoded, because the processor decodes a cache line only from where it entered it (the target of the last taken branch) to where it leaves it (the next taken branch), ignoring the bytes before and after. The branches hiding in those ignored bytes are "shadow branches." Skia decodes those unused bytes — the code is already in hand — extracts the shadow branches, and stores them in a small Shadow Branch Buffer accessed in parallel with the main table. Now a branch-target-buffer miss can still be resolved from the shadow buffer, so the front-end keeps running. It costs about 12 kilobytes and speeds programs up around 5.7 percent.

Why this problem is worth solving

The whole front-end is built to run ahead of execution, and it can only do that if it knows where the branches are.

A modern high-performance processor separates predicting the instruction stream from fetching it, a design called a decoupled front-end. The branch prediction unit runs far ahead, following the predicted control flow and producing a queue of the cache lines the program will soon execute; fetch-directed instruction prefetching then pulls those lines into the first-level instruction cache ahead of time, so when the fetch engine gets there the code is waiting rather than being fetched from a distant cache or memory. This is what lets a wide processor stay fed instead of stalling on instruction-cache misses. But the branch predictor can only run ahead if it can identify branches and predict their targets, because a branch is the only place the instruction stream can diverge. It does this with tracking structures, chiefly the branch target buffer. When those structures know the branch, prefetching flows smoothly; when they do not, the predictor is blind at exactly the point where the path could turn, and the entire run-ahead machinery falls apart. So the accuracy and coverage of branch tracking is the linchpin of front-end performance.

The specific structure that fails is a cache of known branches, and code growth is overrunning it.

The branch target buffer is a hardware table that records, for branches the processor has seen, where each one is and where it jumps to, so the predictor can recognize a branch and predict its target without having decoded the instruction yet. Like any cache it is finite, and modern data-center applications have code footprints with far more branches than it can hold, so branches are evicted and later missed. A branch target buffer miss is costly because the predictor does not know a branch is there: it may prefetch the wrong code or none, and the branch is only recognized much later, at decode, forcing a resteer — the front-end throws away the work it did on the wrong path and restarts fetching from the correct target. Resteers are a major source of front-end stalls in these workloads. The branches that miss most are the “cold” ones, executed infrequently and thus evicted before their next use, yet collectively they cause a lot of resteers. Recovering those missing branches without the cost of a much larger buffer is what Skia sets out to do.

What people did before, and where it broke

Enlarge the branch target buffer. Add entries so more branches are remembered and fewer miss. Where it broke. It costs significant area and power, scales poorly against growing code footprints, and spends that area disproportionately on the frequently-executed branches while still missing the cold long tail that causes many resteers.
Rely on fetch-directed prefetching alone. Use the run-ahead prefetcher to hide instruction-cache misses. Where it broke. Prefetching depends on the branch target buffer to know where to go, so on a buffer miss it is blind — it cannot prefetch correctly and may speculate down the wrong path, actively polluting the instruction cache.
Prefill the buffer from instruction-cache misses. Try to populate the branch target buffer based on instruction-cache miss activity so branches are learned earlier. Where it broke. Such schemes require extra machinery, and, as the paper notes, add complexity like virtualized structures, without directly capturing the branches that are already present but undecoded in fetched lines.
Predecode instructions to find branches. Scan fetched bytes to identify branches ahead of full decode. Where it broke. Predecoders assume the perfect instruction alignment of the true path and decode only the executed portion of a line; they do not decode the ignored bytes before the entry point or after the exit point, so the branches hiding there stay invisible.
The gap. No approach recovered the large fraction of missing branches that are already sitting, undecoded, in the ignored parts of cache lines the prefetcher already fetched. Decoding those unused bytes to expose the shadow branches, cheaply and in parallel, is what Skia contributes.

How Skia works

Turning ignored cache-line bytes into recovered branch predictions

↓ →
new
↓ →
new
↓ →
new
↓ →
new
↓ →
new

The idea

The missing branches are not missing from the chip — only from the table. The key reframing is that a branch-target-buffer miss does not mean the branch’s bytes are absent; the paper measures that three-quarters of the time those bytes are already in the instruction cache, brought in by the very prefetcher that then fails to recognize the branch. The information the front-end lacks is already physically present; it was simply never decoded into the tracking structure. Skia’s foundation is to close that gap by decoding what is already in hand rather than fetching or storing anything new. Recovering predictive information the machine already has access to but is not using, by processing data that has already flowed through the pipeline, is the same make-use-of-what-you-observe instinct the runtime prefetch-generation work covered elsewhere on this site is built on, deriving the guidance the hardware needs from behavior it is already exposed to instead of paying to acquire it afresh.

Decode the bytes the normal path deliberately skips. The reason these branches stay hidden is a structural quirk of how lines are decoded: a cache line is processed only from its entry point, the target of the previous taken branch, to its exit point, the next taken branch that leaves the line, so any branch sitting before the entry or after the exit is never looked at. Those are the shadow branches. Because the prefetcher forwards the entire line, including those ignored regions, Skia can decode the skipped bytes in parallel with the true-path decode and harvest the shadow branches essentially for free, adding a compact Shadow Branch Buffer that is queried alongside the main table. A small, targeted auxiliary structure that captures exactly the cases the primary mechanism cannot, at a fraction of its cost, is the same lean-augmentation strategy the critical-slice-prefetching work covered elsewhere on this site relies on, bolting a focused helper onto the normal path to eliminate the stalls it would otherwise suffer rather than scaling the whole structure up.

Target the cold long tail that a bigger buffer never catches. The branches Skia recovers are disproportionately cold — infrequently executed, and therefore evicted from the branch target buffer before they recur, precisely the branches that resist a capacity solution. Because the shadow buffer is populated from what the prefetcher happens to fetch, it captures branches largely distinct from those the main buffer holds, so the two are complementary rather than redundant, and Skia keeps helping across buffer sizes until saturation. This directly attacks the front-end bottleneck that large-code-footprint data-center workloads suffer, where the sheer volume of branches overruns the tracking structures. Attacking the instruction-side front-end pressure that sprawling warehouse-scale applications create, rather than accepting it as fixed, is the same target the profile-guided code-layout work covered elsewhere on this site pursues, going after the front-end stalls that dominate these workloads instead of only their data-side behavior.

Following a cold branch through Skia

Recovering a branch that the buffer forgot

A trace, from the paper, of how Skia resolves a branch-target-buffer miss on a cold branch that the prefetcher had already fetched into the cache.

Step 1 of 5

The prefetcher fetches a line containing a cold branch

Running ahead, the prefetcher pulls a cache line into the instruction cache. The line holds the true-path code between its entry and exit points, but also, in the bytes before the entry or after the exit, a cold branch that the program will later reach.

The prefetcher forwards the whole line, so those extra bytes are already in the front-end.

Why it works

The needed branches are already in the cache, so recovering them is nearly free. A buffer miss looks like the branch is unknown, but 75 percent of the time its bytes are already fetched → but decoding those already-present bytes needs no new fetch or storage of code → so Skia recovers most missing branches at little cost by processing what the prefetcher already delivered.
Decoding the skipped regions exposes branches the normal path never sees. The processor decodes a line only between its entry and exit points, so branches outside that window stay invisible → but decoding the ignored bytes in parallel finds exactly those shadow branches → so the front-end learns branches it otherwise would only rediscover at decode.
A small parallel buffer captures the complementary, cold branches. Growing the main buffer chases frequent branches and still misses the cold tail → but a shadow buffer populated from fetched lines holds branches largely distinct from the main buffer → so a mere twelve kilobytes adds coverage that scaling the main buffer would not, beating an equal-size buffer expansion by about 2 percent.
Resolving misses early prevents wrong-path pollution and resteers. On a buffer miss the predictor is blind and may prefetch the wrong path, polluting the instruction cache and forcing a resteer → but the shadow buffer supplies the branch and its target in parallel → so the front-end stays on the correct path and avoids the stall.
It attacks the front-end bottleneck of large-footprint workloads directly. Data-center code footprints overrun the branch tracking structures, which capacity alone cannot fix → but exposing shadow branches targets the cold branches driving resteers → so across sixteen front-end-bound applications Skia yields about a 5.7 percent geomean speedup.

What it costs (trade-offs and scope)

It targets front-end-bound, large-footprint workloads. Skia’s gains come from workloads where branch-target-buffer misses and resteers are a real bottleneck, namely data-center applications with large code footprints; programs that fit comfortably in the branch target buffer, or that are not front-end-bound, have little for it to recover and will see little benefit.
Recovering shadow branches depends on them being co-fetched. The technique works because the branches are already in fetched lines, so its coverage is bounded by which lines the prefetcher brings in and how many shadow branches ride along; branches never co-resident with fetched true-path code, or reached without their line being prefetched, are not captured.
It adds decode and buffer machinery. Skia decodes the unused bytes of fetched lines and maintains a Shadow Branch Buffer queried in parallel with the branch target buffer; while the storage is small (about twelve kilobytes) and the decode is parallel, this is added front-end complexity and hardware, not a free change, and it must handle the practical details of decoding non-true-path bytes.
The gains are meaningful but bounded. A roughly 5.7 percent geomean speedup, and about 2 percent over an equal-size buffer expansion, is a solid architectural improvement for the area, but it is an incremental front-end optimization rather than a transformational one, and the benefit saturates as structures grow.
Evaluation is on a specific set and configuration. The results are for sixteen front-end-bound applications against a nominally-sized eight-thousand-entry branch target buffer; the magnitude of benefit will depend on the baseline buffer size, the instruction set and its encoding, the prefetcher, and the workload mix, so the numbers characterize this setting rather than every processor.

The evaluation

Reducing branch-target-buffer misses in a large-footprint front-end

Property	Baseline branch target buffer	Bigger branch target buffer	Skia (Shadow Branch Buffer)
How missing branches are recovered
Coverage of cold branches
Storage cost
Complementary to the main buffer	n/a
Reported speedup	Baseline

From the paper's evaluation across sixteen front-end-bound applications. Skia adds a roughly 12.25-kilobyte Shadow Branch Buffer, decoded from bytes already fetched, that captures branches largely distinct from the branch target buffer, delivering about a 5.7 percent geomean speedup over a 78-kilobyte 8K-entry buffer and about 2 percent over giving that buffer an equal amount of extra state, with gains that persist across sizes until saturation.Underlined values explain themselves when clicked.

Where this stops working

What to keep in mind

The contribution is a clean, cheap insight into a real front-end bottleneck: as data-center code footprints grow, the branch target buffer misses constantly, blinding the run-ahead prefetcher and causing resteers, and simply enlarging the buffer is expensive and misses the cold tail. Skia observes that most of these missing branches are already sitting, undecoded, in the ignored portions of cache lines the prefetcher already fetched — the shadow branches — and recovers them by decoding those unused bytes in parallel into a small Shadow Branch Buffer queried alongside the main table. Because the recovered branches are largely distinct and disproportionately cold, about twelve kilobytes buys roughly a 5.7 percent geomean speedup, beating an equal-size buffer expansion. Read that within its scope. The benefit is specific to front-end-bound, large-footprint workloads and bounded by which shadow branches ride along in fetched lines; it adds decode and buffer hardware, modest but real; the speedup is meaningful but incremental and saturates with size; and the numbers reflect a particular baseline buffer, instruction set, and application set. Within those bounds it is an elegant example of finding performance not by adding resources but by using information the machine already had in hand.

Background

Why the instruction front-end is a data-center bottleneck

It helps to see why chasing a few percent in the front-end is worth a paper. For a long time, processor performance work focused on the data side — caches, memory latency, out-of-order execution to hide it. But for the server workloads that run at data-center scale, a different bottleneck came to dominate: the instruction front-end. These applications, with their deep software stacks, many libraries, and sprawling codebases, have instruction footprints far larger than any first-level cache or branch-tracking structure can hold, so the processor spends a great deal of time stalled not on data but on getting the next instructions and figuring out where the code goes next. Because these workloads run on enormous fleets, even a small per-core improvement in how efficiently the front-end keeps the pipeline fed translates into large aggregate savings in machines and energy, which is why branch prediction, instruction prefetching, and code layout have become intensely studied for exactly this class of program. And the branch predictor sits at the very center of this: it is the structure that decides, cycle by cycle, where the processor goes next, so central that its internal state is powerful enough to be probed and exploited — the same conditional-branch-predictor machinery the control-flow-attack work covered elsewhere on this site turns into a side channel. Skia works the performance side of that same structure, extracting the branch information the front-end needs from cache lines it already holds.

If you remember only three things

1. Modern processors use a decoupled front-end where the branch predictor runs ahead and a prefetcher pulls in upcoming code, but this depends on a branch target buffer that records where branches are, and data-center code footprints have grown so large that the buffer constantly misses — a branch it once knew has been evicted — so the predictor no longer recognizes the current instruction as a branch, fails to prefetch or speculates wrongly, and pays a resteer; simply enlarging the buffer is costly and still misses the infrequently-executed cold branches that cause many resteers.
2. Skia is built on the observation that 75 percent of these missing, unrecognized branches are already present in instruction-cache lines the prefetcher has already fetched, just never decoded — because a line is only decoded from its entry point (the last taken branch's target) to its exit point (the next taken branch), so branches in the ignored bytes before or after are invisible; these are "shadow branches," and Skia decodes those unused bytes in parallel with the true-path decode and stores the recovered branches in a small Shadow Branch Buffer queried alongside the branch target buffer, so a buffer miss can still be resolved and the front-end keeps running.
3. Because shadow branches are largely distinct from and complementary to the branches in the main buffer, and disproportionately cold, a Shadow Branch Buffer of only about 12.25 kilobytes delivers a roughly 5.7 percent geomean speedup over a 78-kilobyte 8K-entry branch target buffer across sixteen front-end-bound applications, and about 2 percent over adding the same amount of state to the buffer, with gains persisting across sizes until saturation; the approach targets front-end-bound large-footprint workloads, is bounded by which shadow branches ride along in fetched lines, and adds modest decode and buffer hardware.

Check yourself

Check your understanding

1. Why does the branch predictor keep failing on data-center applications?
2. What is a shadow branch?
3. How does Skia recover shadow branches, and why is it cheap?
4. What did Skia achieve, and what are its limits?

Sources

The paper is “Skia: Exposing Shadow Branches” by Chrysanthos Pepi, Bhargav Reddy Godala, Krishnam Tibrewala, Gino A. Chacon, Paul V. Gratz, Daniel A. Jimenez, Gilles A. Pokam, and David I. August (Princeton University, Texas A&M University, and Intel), published at ASPLOS 2025 (Volume 2), DOI 10.1145/3676641.3716273.

This explainer is written from the full text of the authors’ arXiv version (arXiv:2408.12592). Everything above comes from the paper’s own sections: the introduction on the decoupled front-end and fetch-directed instruction prefetching driven by the branch prediction unit and its branch target buffer, and the problem that growing data-center code footprints cause many branch target buffer misses (branches previously decoded and inserted but since evicted), where on a miss the predictor may not identify the current instruction as a branch, preventing prefetching or causing wrong-path speculation that pollutes the instruction cache; the key observation that 75 percent of these branch-target-buffer-missing, unidentified branches are already present in instruction-cache lines the prefetcher has fetched but are undecoded because a line is decoded only from its entry point (the target of the previous taken branch) to its exit point (a taken branch), leaving branches in the ignored bytes as “shadow branches” (often cold branches that are evicted before reuse yet contribute significantly to resteers); the Skia technique of decoding the unused bytes of already-fetched cache lines in parallel with the true-path decode and inserting the recovered branches into a Shadow Branch Buffer accessed in parallel with the branch target buffer so that a buffer miss can still be resolved; the discussion that predecoders relying on true-path alignment do not decode these bytes and that the shadow branches are largely distinct from those in a similarly-sized buffer; and the evaluation reporting that a 12.25-kilobyte Shadow Branch Buffer delivers about a 5.7 percent geomean speedup over an 8,000-entry (78-kilobyte) branch target buffer and about 2 percent over adding an equal amount of state to the buffer, across sixteen front-end-bound applications, with consistent gains across sizes until saturation.