[GH-ISSUE #3716] [RFC/Epic] Common Bytecode and VM Framework: unified instruction decoding, CFG synthesis, SSA analysis and source decompilation #1428

New issue

Open

opened 2026-10-16 21:05:21 +00:00 by bsakaguchi · 0 comments

bsakaguchi commented

2026-10-16 21:05:21 +00:00

Owner

Originally created by @matbrgz on GitHub (Oct 14, 2026).
Original GitHub issue: https://github.com/morluto/rea/issues/3716

Problem Statement & Architectural Context

Bytecode virtual machines (VMs) are pervasive across modern software: JVM (#1558), .NET CIL (#3607), Lua/LuaJIT (#3699), Luau (#3692), Python bytecode (#3678), ActionScript (#3614), Papyrus (#3706), GameMaker GML (#3632), QuickJS, Hermes (#3608), and Ethereum EVM.

Currently, reverse engineering tools—including REA—often implement decompilers as bespoke, siloed monoliths for each specific VM. This leads to duplicate implementations of textbook compiler algorithms (control-flow graph construction, loop restructuring, SSA form conversion, liveness analysis, dead-code elimination, and type propagation).

REA should introduce a Common Bytecode & VM Framework that separates VM-specific frontend decoders from shared, high-performance compiler analysis and source decompilation backends.

Proposed Architecture

flowchart TD
    subgraph VM Frontends
        A1["Lua / LuaJIT Bytecode Decoder"]
        A2["Python Bytecode Decoder"]
        A3["Luau Bytecode Decoder"]
        A4["Custom / Domain VM Decoders"]
    end

    A1 & A2 & A3 & A4 --> B["Intermediate Bytecode Representation (Bytecode IR)"]
    
    subgraph Shared Analysis Engine
        B --> C["Control Flow Graph (CFG) Constructor"]
        C --> D["Dominator Tree & Natural Loop Analyzer"]
        D --> E["Static Single Assignment (SSA) & Data-Flow Engine"]
        E --> F["Structural De-Sugaring (if/else, while, for, match)"]
    end
    
    subgraph Decompiler Backends
        F --> G1["Structured AST (Abstract Syntax Tree)"]
        G1 --> H1["Target Language Emitter (Lua, Python, TypeScript, Pseudocode)"]
        G1 --> H2["Mermaid Flowchart / CFG Graph Visualizer"]
    end

Technical Capabilities & Modules

Generic Instruction & Virtual Register Abstraction:
- Universal instruction schema accommodating both stack-based VMs (e.g. JVM, Python, EVM) and register-based VMs (e.g. Lua, Luau, Dalvik).
- Generalized operand types: register index, immediate value, string table index, upvalue/closure reference, branch target.
CFG & Dominator Tree Synthesis:
- Universal basic block partitioning based on branch targets and fallthrough edges.
- Lengauer-Tarjan dominator tree computation and dominance frontier identification.
- Loop detection: identify loop headers, back edges, loop pre-headers, and classify into pre-tested (while), post-tested (do-while), and iterator-based (for-in) loops.
SSA Form & Data-Flow Transformation:
- Place $\phi$-nodes (phi functions) and rename virtual registers into SSA form.
- Sparse Conditional Constant Propagation (SCCP) to eliminate unreachable dead blocks and evaluate constant expressions.
- Live-range analysis to consolidate compiler-generated temporary variables into clean source-level variable names.
Expression Tree Reconstruction & Short-Circuiting:
- Reconstruct complex composite expressions from sequence of binary/unary operations.
- De-sugar boolean short-circuit evaluation chains (A and B or C) into logical expression trees.
Extensible Frontend Adapter API:
- Minimalist adapter interface requiring new VM modules to implement only:
  - Header/constant pool deserializer.
  - Opcode-to-GenericInstruction mapping table.
  - Calling convention / argument passing rules.
- Enables adding support for obscure or custom proprietary VMs in hundreds of lines of code rather than thousands.

Acceptance Criteria

Unified IR and CFG engine shared across multiple registered VM frontends.
Accurate structural recovery of nested loops, break/continue statements, and conditional branches.
Automatic elimination of temporary stack/register variables via SSA data-flow reduction.
Emission of readable, syntactically clean pseudocode and ASTs.
Demonstrated integration with at least two distinct VM families (e.g. Lua/LuaJIT and Python).

Complements #3699 (Lua and LuaJIT bytecode reverse engineering)
Complements #3692 (Roblox/Luau reverse engineering)
Complements #3678 (Python packaged application reverse engineering)
Complements #3608 (React Semantic Reconstruction & Hermes unbundling)

Originally created by @matbrgz on GitHub (Oct 14, 2026). Original GitHub issue: https://github.com/morluto/rea/issues/3716 [![Type: Architecture / RFC](https://img.shields.io/badge/type-architecture_%2F_RFC-darkred.svg?style=flat-square)](https://github.com/morluto/rea) [![Status: Proposed](https://img.shields.io/badge/status-proposed-blue.svg?style=flat-square)](https://github.com/morluto/rea) [![Ecosystem: REA](https://img.shields.io/badge/ecosystem-morluto%2Frea-8A2BE2.svg?style=flat-square)](https://github.com/morluto/rea) ### Problem Statement & Architectural Context Bytecode virtual machines (VMs) are pervasive across modern software: JVM (#1558), .NET CIL (#3607), Lua/LuaJIT (#3699), Luau (#3692), Python bytecode (#3678), ActionScript (#3614), Papyrus (#3706), GameMaker GML (#3632), QuickJS, Hermes (#3608), and Ethereum EVM. Currently, reverse engineering tools—including REA—often implement decompilers as bespoke, siloed monoliths for each specific VM. This leads to duplicate implementations of textbook compiler algorithms (control-flow graph construction, loop restructuring, SSA form conversion, liveness analysis, dead-code elimination, and type propagation). REA should introduce a **Common Bytecode & VM Framework** that separates VM-specific frontend decoders from shared, high-performance compiler analysis and source decompilation backends. ### Proposed Architecture ```mermaid flowchart TD subgraph VM Frontends A1["Lua / LuaJIT Bytecode Decoder"] A2["Python Bytecode Decoder"] A3["Luau Bytecode Decoder"] A4["Custom / Domain VM Decoders"] end A1 & A2 & A3 & A4 --> B["Intermediate Bytecode Representation (Bytecode IR)"] subgraph Shared Analysis Engine B --> C["Control Flow Graph (CFG) Constructor"] C --> D["Dominator Tree & Natural Loop Analyzer"] D --> E["Static Single Assignment (SSA) & Data-Flow Engine"] E --> F["Structural De-Sugaring (if/else, while, for, match)"] end subgraph Decompiler Backends F --> G1["Structured AST (Abstract Syntax Tree)"] G1 --> H1["Target Language Emitter (Lua, Python, TypeScript, Pseudocode)"] G1 --> H2["Mermaid Flowchart / CFG Graph Visualizer"] end ``` ### Technical Capabilities & Modules 1. **Generic Instruction & Virtual Register Abstraction:** - Universal instruction schema accommodating both stack-based VMs (e.g. JVM, Python, EVM) and register-based VMs (e.g. Lua, Luau, Dalvik). - Generalized operand types: register index, immediate value, string table index, upvalue/closure reference, branch target. 2. **CFG & Dominator Tree Synthesis:** - Universal basic block partitioning based on branch targets and fallthrough edges. - Lengauer-Tarjan dominator tree computation and dominance frontier identification. - Loop detection: identify loop headers, back edges, loop pre-headers, and classify into pre-tested (`while`), post-tested (`do-while`), and iterator-based (`for-in`) loops. 3. **SSA Form & Data-Flow Transformation:** - Place $\phi$-nodes (phi functions) and rename virtual registers into SSA form. - Sparse Conditional Constant Propagation (SCCP) to eliminate unreachable dead blocks and evaluate constant expressions. - Live-range analysis to consolidate compiler-generated temporary variables into clean source-level variable names. 4. **Expression Tree Reconstruction & Short-Circuiting:** - Reconstruct complex composite expressions from sequence of binary/unary operations. - De-sugar boolean short-circuit evaluation chains (`A and B or C`) into logical expression trees. 5. **Extensible Frontend Adapter API:** - Minimalist adapter interface requiring new VM modules to implement only: - Header/constant pool deserializer. - Opcode-to-GenericInstruction mapping table. - Calling convention / argument passing rules. - Enables adding support for obscure or custom proprietary VMs in hundreds of lines of code rather than thousands. ### Acceptance Criteria - [ ] Unified IR and CFG engine shared across multiple registered VM frontends. - [ ] Accurate structural recovery of nested loops, break/continue statements, and conditional branches. - [ ] Automatic elimination of temporary stack/register variables via SSA data-flow reduction. - [ ] Emission of readable, syntactically clean pseudocode and ASTs. - [ ] Demonstrated integration with at least two distinct VM families (e.g. Lua/LuaJIT and Python). ### Related Issues & Dependencies - Complements #3699 (Lua and LuaJIT bytecode reverse engineering) - Complements #3692 (Roblox/Luau reverse engineering) - Complements #3678 (Python packaged application reverse engineering) - Complements #3608 (React Semantic Reconstruction & Hermes unbundling)

bsakaguchi referenced this issue

2026-10-17 21:11:25 +00:00

[PR #1437] [MERGED] fix(javascript): preserve effects through yielded array references #2886

No milestone

No project

No assignees

1 participant

Notifications

Due date

The due date is invalid or out of range. Please use the format "yyyy-mm-dd".

No due date set.

Dependencies

No dependencies set.

Reference

morluto/rea#1428

No description provided.

Rows
Columns