What You Trace is What You Get: Dynamic Stack-Layout Recovery for Binary Recompilation

A binary recompiler lifts a program you have no source for into a compiler's intermediate form so modern optimizations can be applied, but every lifter so far treats the function stack as one opaque byte array, which blinds the compiler to local variables and cripples optimization — WYTIWYG runs the lifted program on real inputs, watches how every stack pointer is derived, dereferenced and spilled, and from those traces splits each frame into individually sized variables, so that recompiled binaries run within 6 to 10 percent of the originals, old GCC 4.4 binaries speed up 1.22 times, and unoptimized ones 2.1 times, with 94.4 percent precision on the recovered layout.

The argument in one glance

Problem

Legacy binaries are stuck in time, and lifting them loses the variables

Software whose source is gone or whose vendor has left cannot be recompiled, so it never benefits from newer optimizers, sanitizers or bug fixes. Binary recompilers lift machine code to a compiler IR such as LLVM and lower it back, but the lifted code emulates the original stack as an opaque byte array. The compiler then cannot tell one local variable from another, so it cannot prove that a store through one pointer does not clobber a value spilled elsewhere, and most optimizations stall.
What people did

Static stack analysis with heuristics or conservative merging

SecondWrite, McSema with IDA Pro, RetDec and mctoll try to split the frame statically, using ABI conventions to guess which registers are saved and which stack slots are distinct, and falling back to one symbol per frame when they cannot prove separation.
Why it fell short

Conservative means useless; heuristic means broken

Variable recovery from binaries is undecidable, so static tools must choose. Conservative analysis labels every stack access of any non-trivial function with a single symbol, so the IR gains nothing. Heuristic splitting alters semantics unpredictably when its assumptions fail, and compilers routinely violate ABI conventions inside a translation unit, emit end pointers past the end of arrays, and merge tail calls. RetDec and mctoll recompile none of SPECint 2006; McSema needs a skilled operator; SecondWrite could not even disassemble binaries from current compilers.
This paper's idea

Observe how pointers are actually used, then carve the frame to match

WYTIWYG instruments the lifted program and runs it on user-provided inputs, refining the IR in iterations. One refinement finds every direct stack reference by symbolically tagging registers at function entry and watching whether they are merely saved or used as arguments. The next assigns each reference a tracked object, records the minimum and maximum offsets of every pointer derived from it when dereferenced, merges overlapping ranges, and replaces the emulated stack with real per-variable allocations. Built on BinRec, it recompiles all supported SPECint 2006 programs from GCC 12.2, Clang 16 and GCC 4.4 with no manual work: 1.10 and 1.06 times the original runtime for the modern -O3 binaries, 1.22 times faster than the originals for GCC 4.4, 2.10 times faster for -O0, 1.18 times better than SecondWrite, and 94.4 percent precision with 87.6 percent recall against the compiler's true layout.

Why this problem is worth solving

Consider the small function in the paper’s Figure 2. It declares a struct a, an array b of three structs, and a pointer ptr; it calls f2 with the addresses of a and b, stores a into b at an index returned by f3, then writes through ptr. Compiled with GCC, all of that becomes offsets from the frame pointer: a.x at ebp−20, ptr at ebp−12, b starting at ebp−44, and the indexed store at ebp−44 plus 8 times the return value of f3. The source compiler knew the index store could not touch ptr, because an out-of-bounds write is undefined behaviour. The binary does not say so. A recompiler that wants to keep the value of ptr in a register across line 5 must prove that ebp−44+f3(24)·8 never equals ebp−12, and in general it cannot. So it reloads, and every analysis downstream assumes the worst.

This is not a corner case. The paper identifies the opaque emulated stack as the primary cause limiting program analysis and transformation in every binary recompiler it examined, and cites an independent study by Liu and colleagues reaching the same conclusion. Without

stack symbolization

Labelling every direct stack reference in a function with a symbol naming the distinct local variable it belongs to, so the IR carries separate allocations rather than one byte array.

, AddressSanitizer cannot guard locals, alias analysis cannot separate them, and value-range analyses do not scale. The goal is to recover locals precisely enough that LLVM treats the lifted program like one its own front end produced.

What people did before, and where it broke

Rewriters such as Egalito. Modify control flow and instruction sequences directly. Where it broke. They offer no way to manipulate variables or memory layout at all.
Recompilers without symbolization: McSema, Rev.ng, BinRec. Lift to LLVM IR with the stack as a byte array. Where it broke. Correct, but the IR is oblivious to locals, arguments, saved registers and spills, so optimizations that depend on memory layout or precise use-def chains are crippled.
SecondWrite. The most complete static stack analysis among recompilers. Where it broke. Conservative by design: functions beyond a certain complexity get a single symbol for all locals. In this paper’s evaluation it could not disassemble binaries from GCC 12.2 or Clang 16 because of unhandled SIMD instructions, could not link xalancbmk, crashed gcc on every input, and mishandled PIC relocations and jump tables.
Heuristic ABI-based register classification. Assume callee-saved registers per the platform ABI. Where it broke. Compilers define their own conventions for non-exported functions, and merged tail calls save registers zero or several times, so heuristics misclassify.
Decompilation-oriented variable recovery: TIE, Howard, OSPREY. Recover types and variables for reverse engineering. Where it broke. Probabilistic answers are fine for a human reader but not for recompilation, where a mispredicted layout silently breaks the program.
The gap. No recompiler recovered individual local variables in fully optimized, current-compiler binaries while guaranteeing the recompiled program behaves like the original.

Where WYTIWYG sits

Refinement lifting on top of BinRec

BinRec tracing

S2E records all control transfers on user inputs; CFGs are merged and RevGen lifts to LLVM IR with an emulated stack and virtual CPU state.
↓ →
Function recovery new

Nucleus-style entry detection from the traced call graph, tail-call identification, and splitting so every function has one entry.
↓ →
Refinement 1: stack references new

Instrument, run, and classify each register as saved or argument; fold all constant displacements into sp0-relative base pointers.
↓ →
Refinement 2: object bounds new

Instrument pointer derivations, loads and stores; record per-object offset ranges and links; merge overlaps into a layout.
↓ →
Rewrite new

Replace base pointers with native allocations of the deduced size and alignment, add stack-passed arguments to signatures, delete the emulated stack.
↓ →
LLVM optimize and lower

Standard LLVM passes now see real locals; emit the recovered binary.

Each refinement instruments the current IR, executes it on the same inputs, and transforms the IR for the next. The paper calls the iterative process refinement lifting.

The idea

Two stacks, and why one of them hides everything. A lifted program keeps a native stack for its own calls and an

emulated stack

A pre-allocated byte array in the lifted program that stands in for the original program's call stack, addressed through a virtual stack pointer.

that mirrors the original program’s. Every push, prologue, spill and local access becomes arithmetic on a virtual stack pointer and a load or store into the array. That is faithful, and it is also opaque: two accesses at different constant offsets are just two addresses into one object, and an indexed access could be anywhere. The paper’s plan is to carve that array into the variables the source program had, so that LLVM can see them.

Refinement lifting. Rather than lift everything in one step, WYTIWYG runs a sequence of dynamic analyses on the lifted IR, each implemented as instrumentation plus a small runtime library in the style of a sanitizer, and after each run transforms the IR so the next analysis starts from a cleaner program. The two refinements below are the core; an earlier one resolves the exact signatures of variadic library calls such as printf by inspecting format strings at runtime, and function recovery precedes them all.

Refinement 1: find every direct stack reference. A

direct stack reference

A pointer computed as the initial stack pointer at function entry, sp0, plus a constant displacement; the only way a function's own frame is addressed directly.

is sp0 plus a constant. Folding is easy for the current function, but frame pointers and other stack references get saved and restored across calls, and from the recompiler’s view a restored register holds an opaque value loaded from memory. Static ABI rules are unreliable, so WYTIWYG tags every register with a symbolic value at function entry and watches. A register is saved if its symbol is only ever loaded from and stored to the current frame and is back in the register at return; anything else makes it an argument. Registers forwarded unused to callees are resolved after tracing by constraints such as “if edx is an argument in f2, it is an argument in f1.” Saved registers are then preserved explicitly around every call site in the IR, which turns an indirect dependency through memory into a direct one and lets all displacements fold into sp0.

Refinement 2: recover object bounds. Each direct reference becomes a candidate base pointer with its own

StackVar

A runtime record for a candidate stack object holding the lowest and highest offsets ever dereferenced through pointers derived from its base pointer, plus an alignment factor.

. Every pointer-sized value carries a PointerInfo naming its StackVar and offset. Instrumented operations do the work: derive for add, sub and and with a constant, derive2 when both operands might be pointers, link when a subtraction of two pointers or a comparison shows they belong to one object, and load and store, which update the address map and widen the object’s bounds by the access size. Because x86 does not distinguish pointers from integers, sub-register writes can leave stale upper bytes that look like pointers, so bounds are updated only when a value is actually dereferenced, never merely derived. That also handles compiler-generated end pointers that sit past the end of an array. If a base pointer itself is out of bounds, bounds start undefined and are initialized at the first dereference. Arguments pushed by the caller are recorded per call site, and call-site signatures are merged into a super signature per function, filling gaps such as an untraced second argument between a traced first and third.

Rewrite. Overlapping and linked ranges are coalesced; each coalesced set becomes a native allocation of the deduced size and alignment; stack-passed arguments join function signatures; base pointers are replaced; the emulated stack is deleted. What was one array is now a set of typed, separately allocated locals, and LLVM’s alias analysis, scalar replacement and register allocation apply as they would to source-compiled code.

Tracing the running example

Recovering a, b and ptr in Figure 2

32-bit x86, frame pointer ebp = sp0 - 4. Locals: ptr at ebp-12, a (8 bytes) at ebp-20, b (3 structs, 24 bytes) at ebp-44. Trace input: f2 returns its first argument (&a), f3 returns 2.

Step 1 of 6

Lift with an emulated stack

BinRec lifts push %ebp into: subtract 4 from the virtual esp, store the operand at that address. Every local access is a load or store into the emulated byte array at ebp-offset. Nothing distinguishes ptr from a from b.

vcpu.esp = vcpu.esp - 4; *vcpu.esp = vcpu.ebp - 20 | one byte array, many offsets

Why it works

Execution answers questions static analysis cannot. Whether a register is saved, whether two references share an object, and how far a pointer reaches are all decided by what the program does on real inputs, so no ABI assumption or conservative merge is needed.
Every refinement makes the next one easier. Explicitly saving registers around calls removes the memory indirection that hid frame pointers; folded sp0 references give the bounds analysis a clean set of base pointers; recovered signatures let the emulated stack be deleted. The paper argues this staging is what lets later analyses stay simple.
Bounds from dereferences are conservative in the right direction. An object is at least as large as anything ever accessed through it, so accesses observed in tracing cannot overflow the recovered allocation. Deferring updates past mere derivation avoids being fooled by stale sub-register bytes or end pointers.
Separate allocations restore what the compiler needs. Once locals are distinct IR objects, alias analysis can prove non-interference, scalar replacement can put them in registers, and the two-stack overhead disappears. Performance is the paper’s proxy for IR quality, and the gap to native code shrinks from 24 to 10 percent for GCC 12.2 -O3 and from 31 to 6 percent for Clang 16.
Function recovery removes chokepoints. Turning BinRec’s single giant function into real functions, with returns as returns rather than switch statements over return addresses, improved even the unsymbolized -O0 baseline from 0.98 to 0.76 of original runtime.

What it costs

Correctness is relative to the traced inputs. An input that exercises an access no trace saw can overflow an undersized or split object. Variable-length arrays and alloca become fixed-size allocations. The paper counts undersized and missed objects as potential incorrect recompilations and reports 87.6 percent recall.
Tracing effort. Programs must be run on representative inputs under S2E-based instrumentation; gcc and xalancbmk needed BinRec’s incremental lifting and larger stack limits to reach adequate coverage.
Not every binary qualifies. Functions need a single entry, call and ret for transfers (tail calls excepted), and a conventional stack pointer. Pointer arithmetic must reduce to addition and subtraction, so obfuscated code with mixed boolean-arithmetic transforms is out of scope.
32-bit x86 only, single-threaded only. The prototype inherits BinRec’s 32-bit support; setjmp/longjmp, exceptions and x87 floating point are unsupported, which excludes omnetpp, perlbench and all of SPECfp. Multithreading would need a multi-stack runtime and, harder, a way to guarantee functionality under non-deterministic interleavings.
Some regressions. hmmer compiled with GCC 12.2 -O3 runs 3.04 times slower after symbolization, and libquantum also regresses, because LLVM’s heuristics and the software-emulated SIMD lifting produce worse code for these lifted programs.
Globals and heap objects are not recovered. That is why -O0 binaries, whose global accesses are unoptimized, stay slightly behind the GCC 12.2 native baseline.

The evaluation

SPECint 2006 without omnetpp and perlbench, each built with GCC 12.2 at -O3 and -O0, Clang 16 at -O3, and GCC 4.4.3 at -O3 on Ubuntu 10.04 so that SecondWrite could process something. Tracing and validation used the ref inputs. Runtime measurements on an AMD Ryzen 9 3900X at a fixed 3.8 GHz with boost, scaling and SMT disabled, LLVM targeting pentium4 to exclude newer ISA features.

Geometric-mean runtime relative to the input binary (Table 1)

Property	GCC 12.2 -O3	GCC 12.2 -O0	Clang 16 -O3	GCC 4.4 -O3	SecondWrite on GCC 4.4
Recompiled, no symbolization (BinRec baseline)	1.24		1.31	1.05
Recompiled with WYTIWYG symbolization			1.06
Largest per-benchmark gains	gobmk 1.25 to 0.99; sjeng 1.06 to 0.85	xalancbmk 0.55 to 0.10	gobmk 1.20 to 0.97; sjeng 1.13 to 0.87	hmmer 0.72 to 0.60; xalancbmk 1.17 to 0.77	—
Regressions		—	—	—	—
Layout accuracy versus LLVM 16 ground truth		—	—	—	—

Runtime ratios below 1.0 mean the recompiled binary is faster than its input. Every WYTIWYG configuration recompiled every benchmark with no manual intervention. Figure 6 additionally shows that all -O3 recompilations approach a GCC 12.2 native baseline, with -O0 slightly behind because globals are not yet symbolized.Underlined values explain themselves when clicked.

In an actual implementation

Two subtleties the tracing runtime must get right

Stale sub-register bytes: writing an 8- or 16-bit x86 sub-register leaves the upper bits untouched, so after arbitrary code the register may look like a pointer it no longer is. Updating an object’s bounds on derive would let such phantoms inflate variables; WYTIWYG updates bounds only on load or store, when the value is proven to be a pointer by being dereferenced. Out-of-bounds base pointers: optimizers turn index loops into pointer loops whose end pointer sits past the array, and occasionally the base pointer a function starts from is itself outside the object. Bounds therefore begin undefined, are initialized by the first dereference, and two objects are linked only when both have defined bounds. Recursion adds a third: one StackVar can stand for the same variable in many frames, so PointerInfo lives on the native stack per activation rather than inside the StackVar.

Where this stops working

The title is the guarantee and the limit: what you trace is what you get. Objects sized from traces can be too small for untraced inputs, especially variable-length arrays turned into fixed allocations, and the 12.4 percent of ground-truth objects that were undersized or missed are exactly the risk. The prototype is 32-bit, single-threaded, and excludes exceptions, setjmp and x87 code, which removed two SPECint benchmarks and all of SPECfp. Obfuscated pointer arithmetic defeats tracking. A few benchmarks regress after symbolization because LLVM’s heuristics and the lifting of SIMD instructions are not tuned for lifted code. And the comparison to prior work is limited to SecondWrite on old-compiler binaries, because no other symbolizing recompiler could process the modern ones at all.

If you remember only three things

1. Binary recompilers lift machine code to LLVM IR but keep the original stack as one opaque byte array, so the compiler cannot separate local variables, cannot prove non-aliasing, and cannot optimize; recovering locals statically is undecidable, and existing tools either merge every local into one symbol or split heuristically and risk breaking the program.
2. WYTIWYG symbolizes locals with dynamic analysis in iterative refinement steps on top of BinRec: tag registers at entry and observe whether they are saved or arguments, fold every direct stack reference to sp0 plus a constant, then track pointer derivations, dereferences and spills at runtime to bound each stack object, merge overlapping ranges, replace the emulated stack with native per-variable allocations, and recover stack-passed argument signatures. Bounds move only on dereference, which defuses stale sub-register bytes and past-the-end pointers.
3. On SPECint 2006 the recompiled binaries run at 1.10 and 1.06 times the runtime of GCC 12.2 and Clang 16 -O3 originals, 1.22 times faster than GCC 4.4 originals, 2.10 times faster than -O0 originals, and 1.18 times faster than SecondWrite's output, with 94.4 percent precision and 87.6 percent recall on the recovered layout. Correctness holds for traced inputs; untraced accesses, variable-length arrays, obfuscation, threads and 64-bit code are outside the prototype.

Check yourself

Check your understanding

1. Why does lifting a binary with an emulated stack cripple LLVM's optimizations even though the lifted program is correct?
2. How does WYTIWYG decide whether a register such as ebp is saved or an argument, and why not use the ABI?
3. Predict what happens if, on every traced input, f3 returns 0 so only b[0] is ever accessed.
4. Why are object bounds updated only when a pointer is dereferenced, not when it is derived?
5. Which result most directly supports the claim that fine-grained stack symbolization, not just recompilation, is what enables reoptimization?

Sources

The paper is “What You Trace is What You Get: Dynamic Stack-Layout Recovery for Binary Recompilation” by Fabian Parzefall, Chinmay Deshpande, Felicitas Hetzelt and Michael Franz, University of California, Irvine, published at ASPLOS 2024, Volume 2, pages 1250 to 1263, DOI 10.1145/3620665.3640371, under a Creative Commons Attribution licence. This explainer was written from the full text of the open-access repository copy on eScholarship (California Digital Library, item 8d3363v4). Numbers are taken from Table 1 and Figures 6 and 7.