← Back
Home › Systems › Compilers and language tooling

decompiler

binary decompiler and analysis

Ghidra, IDA

SystemTechniques · 13Primitives · 24 decompiler Alias analysiscompilers · medium: Decide whether two pointers may refer to the same memory (Andersen, Steensgaard, type-based) to enable optimizationsBinary lifting to ircompilers · medium: Translate machine instructions into a semantic IR (p-code, LLVM IR) with explicit flags and memory effectsCfg recoverycompilers · medium: Recover functions and control-flow graphs from binaries: recursive descent, jump tables, tail callsDataflow analysiscompilers · medium: Compute a fact per program point (live variables, reaching definitions, available expressions) by iterating transfer functions over the CFG to a fixed point.›Function fingerprintingcompilers · medium: Identify library functions in binaries via byte signatures and hashes with wildcards (FLIRT-style)Sparse conditional constant propaga…compilers · medium: SCCP: constant propagation plus unreachable-code detection on SSAStructured control flowcompilers · medium: Turn a jump graph into nested block, loop and if constructs with numbered breaks; reducible graphs need no duplication.›SSA formcompilers · low: Give every variable exactly one definition, merging at joins with phi functions; def-use becomes explicit and optimizations turn sparse and cheap.›Disassemblycompilers · low: Instruction decoding for x86 (prefixes, ModRM, variable length) and ARM; linear sweep vs recursive traversalDominator treecompilers · low: Dominators via Lengauer-Tarjan or Cooper-Harvey-Kennedy; dominance frontiers for SSAExecutable formats elf pecompilers · low: ELF, PE and Mach-O: sections, segments, symbol tables, relocations, dynamic loadingUnificationcompilers · low: First-order unification with union-find and occurs check; basis of type inference and logic programmingCalling conventions abicompilers · low: System V, Windows x64 and AAPCS64 ABIs: argument registers, stack frames, struct passing, FFIUnion-findgraphs · low: Disjoint-set forest with union by size and path compression; merges sets and answers same-set queries in effectively constant time.›Control-flow graphcompilers · low: Split a linear instruction list into basic blocks and connect them by jumps; the graph every optimizer, SSA builder and dataflow pass walks.›Topological sortgraphs · low: Order the vertices of a DAG so every edge points forward; the core of build systems, schedulers and dependency resolution, with cycle detection for free.›Fast hash functionsdata-structures · low: Non-cryptographic hashes built from 64×64→128-bit multiplies and xor-shifts; pick by key size, trust level and whether the hash is persisted.›Radix triedata-structures · low: Compressed prefix tree for path routing, domain matching and prefix lookupsStrongly connected componentsgraphs · low: Tarjan/Kosaraju SCCs for cycle detection in dependency graphsSimplex methodoptimization · low: Solves linear programs by walking along the edges of the feasible polytope from vertex to vertex, one basis swap (pivot) at a time; the workhorse behind MIP solvers.›Hash consingdata-structures · low: Intern structurally equal immutable terms so equality is pointer comparison and sharing is maximalArithmetic circuitshardware-os · low: Adder and multiplier circuits: carry-lookahead, prefix adders, Booth encoding, Wallace and Dadda treesTseitin transformationoptimization · low: Linear-size CNF encoding of formulas with auxiliary variables+ 6 more techniques+ 8 more primitives

Similar systems

Share the most building blocks with this one.

compiler 20 %shader-compiler 20 %