In Part 1 we built the pipeline; in Part 2 we recovered control flow, so the pseudo-C had real if/else, while, and switch instead of a wall of gotos. But every value was still typed int64_t, and every memory access read like *(int32_t*)(t5). This post is about getting types back: figuring out that a value is a pointer, that a pointer indexes an array, and that a pointer is a struct base accessed at constant offsets. Type inference is the hardest part of decompilation and the results are always approximate but getting the obvious cases right is the difference between machine code with extra steps and something you can actually read.
What int64_t everywhere costs you
Here's a real function from vkQuake after Part 2, this is structurally correct, but type-blind:
int64_t sub_14000ada0() {
rax_0 = rsp;
*(int64_t*)(rax_0 + 0x8) = rbx;
*(int64_t*)(rax_0 + 0x18) = r14;
t6 = *(int32_t*)(rdx_1 + rax_3 * 4);
return rax_0;
}Every line is correct. But you have to do the type reasoning in your head: rax_0 + 0x8 and rax_0 + 0x18 are two fields of the same object, rdx_1 + rax_3*4 is an array index, and the function returns a pointer. The decompiler knows none of that at this point it's just emitting casts mechanically.
Compare to what we want:
void* sub_14000ada0() {
rax_0->field_0x8 = rbx;
rax_0->field_0x18 = r14;
t6 = rdx_1[rax_3];
return rax_0;
}Same code. But now the shape of the data is visible. That's the entire goal of Part 3.
The one thing that had to happen first: fix the lifter
Before any of this could work, I hit a wall in the IR lifter. The old mem_addr function that turns a memory operand into an IR address expression computed the address like this:
// OLD — drops index*scale entirely
match &m.base {
Some(r) => {
let base = IrValue::Var(Var::reg(r.name(64), 64));
if m.displacement == 0 && m.index.is_none() {
base
} else {
let t = self.fresh_temp(64);
block.push(/* t = base + disp */); // disp only — index ignored!
IrValue::Var(t)
}
}
None => IrValue::Const(m.displacement, 64),
}The comment in that function literally said "real implementation would compute base + index*scale + disp" and then didn't. So mov eax, [rcx + rdx*4] which is a textbook array load lifted to load(rcx). The index register and the scale just vanished.
You can't detect base + i * element_size array indexing if the IR never records the index or the scale. So step zero was rewriting mem_addr to emit the full effective address, one term at a time, each as its own visible temp:
// index*scale term — the array-access signature
if let Some(idx_reg) = &m.index {
let idx = IrValue::Var(Var::reg(idx_reg.name(64), 64));
let scaled = if m.scale > 1 {
let t = self.fresh_temp(64);
block.push(/* t = idx * scale */);
IrValue::Var(t)
} else { idx };
acc = Some(/* base + scaled */);
}
// displacement term — the struct-field signature
if m.displacement != 0 {
acc = Some(/* acc + disp */);
}Keeping each term as a separate temp is deliberate here, thats because the array detector matches the index * scale multiply (where scale is the element size); the struct detector matches the base + disp add (where disp is the field offset). If we folded these into one constant the way an optimizing compiler would, the information we need to recover types would be gone.
The type lattice
The vocabulary of types is small. The existing InferredType enum gained one variant, the Struct variant and otherwise stayed as it was:
pub enum InferredType {
Unknown,
Int(u8), UInt(u8), // width in bits
Bool,
Pointer(Box<InferredType>),
Array(Box<InferredType>, Option<u64>), // element type, count if known
Struct(Vec<(i64, InferredType)>), // (field offset, field type)
Void,
}The important rule less about the enum, but rather how types combine. Inference is noisy: the same value might trigger a weak "it's loaded from memory, so probably an int" rule and a strong "it's used as a struct base" rule. When that happens, the more specific type has to win, and we must never downgrade.
This is encoded as a rank function. When set() is asked to record a type for a variable that already has one, it only overwrites if the new type ranks higher:
fn type_rank(t: &InferredType) -> u8 {
match t {
InferredType::Unknown => 0,
InferredType::Bool => 1,
InferredType::Int(_) | InferredType::UInt(_) | InferredType::Void => 2,
InferredType::Pointer(_) => 3,
InferredType::Array(..) => 4,
InferredType::Struct(_) => 5,
}
}So a value first seen as Int(32) can be upgraded to Array(int32) or Struct later, but a struct base never gets clobbered back down to a plain int by a weaker rule firing afterward.
Reading types off the address shape
The richest source of type information is how a memory address is computed. Every load(addr) and store(addr) tells us addr is a pointer but the shape of addr tells us what kind.
The engine looks at the op that produced the address temp and classifies it:
match def.get(&key) {
// base + disp - > struct field access at `disp` on `base`
Some(IrOp::BinOp(BinOp::Add, IrValue::Var(base), IrValue::Const(disp, _)))
| Some(IrOp::BinOp(BinOp::Add, IrValue::Const(disp, _), IrValue::Var(base))) => {
if is_frame_or_ip_reg(base) { return; } // rsp/rbp/rip aren't heap pointers
let base_key = self.canon_of(&var_key(base));
self.set(&base_key, InferredType::Pointer(Box::new(InferredType::Unknown)), 0.85,
&format!("used as base of a memory access at offset {:#x}", disp));
self.struct_fields.entry(base_key).or_default().push((*disp, access_bits));
}
// base + index*scale - > array; element size = scale
Some(IrOp::BinOp(BinOp::Add, IrValue::Var(a), IrValue::Var(b))) => {
// Add is commutative, so probe BOTH operands to find the index*scale multiply
let (base, elem_bytes) = match (scale_of_mul(def.get(&var_key(a))),
scale_of_mul(def.get(&var_key(b)))) {
(Some(s), _) => (b, Some(s)),
(_, Some(s)) => (a, Some(s)),
(None, None) => (a, None),
};
// ... set base to Array(elem) ...
}
// bare register deref - > plain pointer
_ => { /* Pointer(int<access_bits>) */ }
}A couple of things worth calling out:
rsp, rbp, and rip are excluded. rsp + 0x10 is a stack access (the stack frame analysis from earlier owns that), and rip + disp is a RIP relative global reference. Neither is a heap object pointer, and typing them as structs produced pure noise (more on that in the bugs section).
Struct vs pointer is a counting decision. A single offset on a base just makes it a pointer. It takes two or more distinct offsets before we promote it to a struct. One field is a pointer to a scalar.
Every one of these calls carries a confidence and an evidence string, because Acheron's whole reason for existing is explainable decompilation. The analysis panel shows why:
- rcx_2: struct { 3 fields } [85%] accessed at 3 distinct field offsets
- rdx_1: int32[] [80%] indexed as array with 4-byte elements (base + index*4)The engine: three phases
The whole thing runs as three passes over the SSA-form IR, plus a canonicalization step up front.
Seed walks the IR once and applies direct evidence rules: a comparison result is a bool, a value loaded from memory is a weak int, an address operand is classified by its shape as above.
Propagate flows types along copy edges (a = b) to a fixpoint. If either end of a copy has a known type and the other doesn't, the type flows across. Functions are small enough that a naive iterate-until-stable loop with a generous cap is plenty.
Finish consolidates the struct-field observations: any base with 2+ distinct offsets becomes a Struct, fields sorted and deduped. It also computes the return type (more below).
That left one phase I haven't mentioned is the one that turned out to matter most.
The phase that actually made it work: SSA canonicalization
Here's where the demo quality version fell apart on real code.
Real compilers spill registers to the stack constantly. A pointer gets computed, used, spilled to a stack slot because the register is needed for something else, then reloaded later under a fresh SSA name. So the same logical object shows up as rcx_0 in one place and rcx_2 in another:
Without doing anything about this, the two field accesses land on two different SSA names. rcx_0 sees offset 0x10, rcx_2 sees offset 0x18, each has exactly one offset, neither reaches the two-offset threshold, and no struct is ever detected. Struct recovery passed every hand-written unit test and silently failed on most real functions, because most real functions spill.
The fix is a small union-find that collapses SSA names which provably hold the same value:
pub struct Canonicalizer {
parent: HashMap<String, String>,
}It unions two kinds of relationships:
- Direct copies —
a = bwherebis a variable. Same value, different name. - Spill/reload —
a = load(slot)where an earlierstore(slot, b)wrote that slot. We track the last variable stored to each stack slot in program order, so a reload picks up whatever was spilled there.
The slot bookkeeping needs to recognize that two different address temps both point at, say, rbp - 8. A small helper resolves a load/store address back to a stable slot key like rbp#-8:
fn stack_slot_key(addr: &IrValue, def: &HashMap<String, IrOp>) -> Option<String> {
let IrValue::Var(v) = addr else { return None };
match def.get(&var_key(v)) {
Some(IrOp::BinOp(BinOp::Add, IrValue::Var(base), IrValue::Const(disp, _)))
| Some(IrOp::BinOp(BinOp::Add, IrValue::Const(disp, _), IrValue::Var(base))) => {
if is_frame_or_ip_reg(base) { Some(format!("{}#{}", base.name, disp)) }
else { None }
}
_ if is_frame_or_ip_reg(v) => Some(format!("{}#0", v.name)),
_ => None,
}
}Struct and array facts are then keyed by the canonical name instead of the raw SSA name, so every access to the same object accumulates into one group. The union-find keeps the lexicographically smaller name as the representative (rcx_0 beats rcx_2), which also makes the pseudo-C deterministic, so every access to the object renders with the same base name.
This single change is what moved struct detection from "works in a demo" to "works." I'll show the numbers shortly.
Return types and globals
Two smaller wins fell out once the engine existed.
Return types. Every function was still declared int64_t. But we already infer the type of rax, and the value returned in rax is the return type. Collect the returned variables, resolve them through the canonical map (the returned rax is often a copy), and pick the most specific type by the same rank function:
void* sub_14000ada0() { ... } // instead of int64_t
int32* sub_140009630(...) { ... }Globals. When a load/store address is a bare constant (an absolute or resolved global address) the old output was *(int32_t*)0x140abc. Now it renders as g_0x140abc, which reads like a variable instead of a raw cast.
Wiring it into the pseudo-C
The pseudo-C generator gained an EmitCtx, built once per function, that precomputes a pretty access string for each address temp:
- a struct base + disp ->
rcx_2->field_0x14 - an array base + index ->
rdx_1[rax_3]
Loads and stores render through this context, falling back to a plain dereference only when there's no typed access. The redundant address-arithmetic lines (t5 = rcx_2 + 0x14;) get suppressed when they've been folded into a typed access, so the output isn't cluttered with pointer math that's now implicit in the ->.
One subtlety: because struct/array facts are keyed by canonical name, the emitter has to canonicalize its lookups too, and render the canonical base name — otherwise rcx_0->field_0x10 and rcx_2->field_0x18 would print with different bases despite being the same object. The canonical map is exported on TypeRecovery precisely so the emitter can do this.
Does it actually work? The survey
Unit tests are necessary but they prove nothing about real code, I write them with the intention for them to pass. The honest test is to run the whole pipeline over hundreds of real functions and count how often types come out.
So I wrote a survey that harvests every E8 rel32 call target from .text, runs the full chain. The order of operations is Decode -> CFG -> lift -> SSA -> type recovery on each, and counts how many produce struct or array types:
harvested 720 call targets
examined 720 functions: 352 with structs, 167 with arrays49% of functions get an inferred struct. 23% get an array. That's the line between a party trick and a feature. It also surfaced concrete examples worth looking at:
candidate 0x140001c80 [struct] (max 5 fields)
candidate 0x140006f40 [struct] (returns a pointer)
candidate 0x140009630 [struct] (returns int32*)
candidate 0x14000ada0 [struct+array] (max 29 fields, returns a struct)That last one (a 29-field struct) is some big object's constructor or initializer. Dumping its pseudo-C confirms the whole chain end to end:
void* sub_14000ada0() {
...
rax->field_0x8 = rbx;
rax->field_0x18 = r14;
...
}void* return type, rax->field_0xNN stores. Exactly the readability win the post opened with.
What went wrong
rsp, rbp, and rip typed as struct pointers. The very first run of the survey lit up rsp as "a pointer accessed at offset 0x10" and rip as "a pointer at offset 0x2b897." Both are wrong rsp+disp is stack access, rip+disp is a global reference. They flooded the findings with garbage. The fix was a small is_frame_or_ip_reg guard that skips those registers (and their 32-bit names) as struct/array/pointer bases. Dropped the entry-function findings from 73 noisy to 70 clean.
The unreachable match arm. My first stab at array detection looked like this:
Some(BinOp(Add, Var(base), Var(scaled)))
| Some(BinOp(Add, Var(scaled), Var(base))) => { ... }At first glance its not horrible, but I thought I was writing "match base+scaled in either order." But that's not what | patterns with the same constructor do. Rust binds by position, so the first arm already matches every two-variable Add, the second arm is unreachable, and both base and scaled just get bound to whatever's in position. The compiler caught it. Addition is commutative and the multiply can be on either side, so the real fix was to bind both operands generically and call a scale_of_mul helper on each to discover which side is the index * scale term. The same bug existed in the pseudo-C emitter, fixed the same way. The lesson here is a | pattern that's "the same shape twice in different orders" isn't an OR over shapes it's in fact the same shape, twice.
A borrow checker standoff in the canonical export. Exporting the canonical map with .map(|k| (k, self.canon.find(k))) doesn't compile: find takes &mut self because path-halving mutates the union-find, while the iterator holds a shared borrow of the same map. Collect the key names into a Vec first, then resolve each in a plain loop. It's not elegant, but the alternative (a non-mutating find) gives up the path compression that keeps it fast.
Where Part 3 stands — and what's deliberately deferred
By the end of this post, Acheron reliably recovers the three things Part 1 promised: it knows a value is a pointer, that a pointer indexes an array, and that a pointer is a struct base. It survives register spills, types function returns and arguments, names globals, and shows its reasoning for every inference... across roughly half the functions in a real binary.
It is still rough in honest ways, and we should talk about what's intentionally left for later because it is still far from finished.
- Field names are offsets.
ptr->field_0x14, notplayer->health. Semantic names need cross-references and usage context. - No cross-function struct unification. Each function infers its own anonymous struct; the same object passed to two functions gets two unrelated layouts.
- Field types are width-only. A pointer-typed field still shows as
int64. - The canonicalizer is linear, not path-sensitive. It can over-union if two unrelated values reuse the same stack slot on different paths.
- No float/SSE types — This one especially at the moment the decoder doesn't lift SSE yet, so XMM values are invisible (you can see the
???movaps/movss noise in the dumps).
Here's the thing though most of the list can't be done well yet. Semantic field names and cross-function unification both depend on having the whole call graph knowing every function, who calls whom, and how the same pointer flows between them. And that's exactly the next milestone.
So rather than a "Part 3b" cleanup post, these items will get folded into the posts where they're actually motivated. Cross-function type work will when we have cross-function data to work with.
What's next
Part 4 — Function Discovery. Right now Acheron starts from the entry point and exports and harvests call targets, which finds maybe a few hundred of the ~1400 functions in vkQuake. Real coverage needs CALL-target harvesting done properly, function-prologue pattern matching, and gap analysis, finding code that no known function reaches. Once we can see all the functions and how they call each other, the deferred type work above suddenly becomes possible because a struct passed from one function to another can be unified, and a field's purpose can be inferred from how callers use it.
That feedback loop allows for function discovery enabling better type recovery enabling better function signatures and this is where a decompiler starts to feel less like a disassembler with structure and more like it's genuinely reading the program.
Code not yet published — it'll land alongside a later post once it's cleaned up. vkQuake remains the running target throughout.