From Machine Code to Intermediate Representation
How Decompilers Work · Reverse Engineering track
6 min read
In this module
Reversing the Compilation Process
Compilers turn source code into machine code. Decompilers attempt the reverse. The catch: compilation is lossy. Variable names, comments, type information, high-level structure — all gone. Decompilation can't perfectly reconstruct the original source, but it can produce useful pseudo-code that captures what the program actually does.
Knowing how decompilers work makes you a sharper reverse engineer. You'll know what the tool can and can't recover, where to trust its output, and where to cross-check against the assembly yourself.
Every decompiler in this module follows roughly the same pipeline. This lesson covers the first three boxes; the rest of the module takes the others in turn:
Step 1: Disassembly
The first stage converts raw bytes into assembly instructions. This sounds simple but is surprisingly difficult, especially for variable-length instruction sets like x86 where instructions range from 1 to 15 bytes.
Linear sweep starts at the top of a code section and processes bytes sequentially. The problem: when it hits data embedded in code — a common practice — it misinterprets those bytes as instructions, produces garbage, and gets out of sync. Off by one byte, and every subsequent instruction is wrong. The error cascades.
Recursive descent starts at known entry points (the program's main function, exported symbols, interrupt handlers) and follows control flow. When it encounters a conditional branch, it queues both targets for disassembly. This avoids data-in-code problems but may miss code that is only reachable through computed jumps or function pointers.
Modern disassemblers use a hybrid approach, combining recursive descent with heuristics to identify additional code regions. They look for function prologues (common instruction patterns like push ebp; mov ebp, esp), search for references in data sections that point to code, and use other signatures to find code regions that recursive descent alone would miss.
Disassembly converts raw bytes to assembly instructions. This is the foundation of all reverse engineering. Variable-length instruction sets (like x86) make this challenging because a single wrong byte offset can cause all subsequent instructions to be decoded incorrectly. This is why obfuscation techniques that embed data in code or use overlapping instructions can confuse disassemblers.
Step 2: Lifting to IR
Assembly is architecture-specific: x86, ARM, and MIPS all have different registers, instruction formats, and calling conventions. To analyse programs uniformly, decompilers lift assembly into an intermediate representation (IR) - a platform-independent language that captures the semantics of each instruction.
For example, Ghidra lifts the x86 instruction ADD EAX, EBX to P-Code along these lines:
CF = INT_CARRY EAX, EBX ; unsigned carry outOF = INT_SCARRY EAX, EBX ; signed overflowEAX = INT_ADD EAX, EBXSF = INT_SLESS EAX, 0ZF = INT_EQUAL EAX, 0PF = ... ; parity of the low byte, a few more opsThe carry and overflow flags are computed first, while the inputs are still intact. Notice that the IR makes explicit all the side effects (flag updates) that the x86 instruction performs implicitly. ADD writes six status flags (CF, PF, AF, ZF, SF and OF) on top of the sum; the listing shows the five that matter in practice, since AF is only read by the old BCD-adjust instructions. This completeness is essential for accurate analysis - if the decompiler misses a side effect, it might incorrectly eliminate code that depends on that effect.
Common IRs
Ghidra P-Code: Ghidra's IR uses a RISC-like instruction set with operations like COPY, INT_ADD, LOAD, STORE, BRANCH, and CALL. Each machine instruction maps to one or more P-Code operations. P-Code is designed to be simple enough that analysis passes can be written once and work across all supported architectures.
IDA Hex-Rays microcode: IDA's decompiler uses a proprietary microcode IR with multiple optimisation levels. Raw microcode closely mirrors the machine instructions; optimised microcode is closer to the final decompiled output. The progression through optimisation levels is what transforms low-level register shuffling into recognisable high-level expressions.
LLVM IR: While primarily a compiler IR, LLVM IR is also used in some binary analysis tools (like McSema/Remill) for binary lifting. The advantage is access to LLVM's extensive optimisation and analysis infrastructure.
VEX IR: Used by the Valgrind tool suite and the angr binary analysis framework. VEX lifts x86, ARM, MIPS, and other architectures into a uniform IR whose temporaries are in SSA form. SSA (static single assignment) means each variable is assigned exactly once, which simplifies many analysis algorithms; VEX's guest registers, though, are read and written like ordinary state, so a full SSA view needs another pass.
The Lifting Challenge
Lifting must handle every quirk of the target architecture:
- Flag computations: x86 has condition flags (carry, parity, auxiliary carry, zero, sign, overflow) that are implicitly set by most arithmetic instructions and read by conditional branches. The lifter must model all of them accurately.
- Implicit operands: Some instructions have hidden inputs or outputs (like x86
DIVusing EDX:EAX as the dividend and producing both quotient and remainder). - Addressing modes: Complex memory addressing (base + index * scale + displacement) must be broken into simpler operations that the IR can represent.
- SIMD instructions: Vector operations that process multiple values simultaneously need special handling to represent parallel operations.
- Processor-specific behaviours: Differences between processor generations, undocumented instructions, and platform-specific extensions all create edge cases that the lifter must handle or at least recognise.
Miss one side effect or lift an instruction incorrectly, and the decompiler's output is wrong in ways that are hard to spot. Lifting is quietly one of the most error-prone stages of the whole pipeline.
From IR to Analysis
Once the program is in IR form, the decompiler can apply architecture-independent analysis passes:
- Dead code elimination: Remove flag computations that are never read. Most flag updates from arithmetic instructions are never used by subsequent branches, so eliminating them dramatically simplifies the IR.
- Constant propagation: Replace computations with known results. If a register is loaded with a constant value and never modified before use, the constant can be substituted directly.
- Expression folding: Combine multiple IR operations back into single expressions. Three IR operations that load a base address, compute an offset, and dereference the result fold back into a single array access.
- Stack analysis: Track the stack pointer to identify local variables. By following pushes, pops, and stack-relative accesses, the decompiler can reconstruct the function's local variable layout.
These transformations gradually simplify the IR from a verbose, instruction-level representation to something approaching high-level pseudo-code. The next lessons cover the key challenges: recovering control flow structures and inferring data types.