Appendix A: CVM Opcode Reference

This appendix provides a comprehensive reference for the Cognica Virtual Machine (CVM) instruction set architecture, including all opcodes, their encodings, operand formats, and execution semantics.

A.1 Instruction Format Overview

The CVM uses a fixed-width 32-bit instruction encoding optimized for cache efficiency and decode simplicity. Extended instructions requiring 64-bit immediates use an additional 8-byte word.

A.1.1 Format Types

The CVM defines seven instruction formats:

A.1.2 Register Allocation

The CVM provides a virtualized register file with the following conventions:

Insight

• The CVM uses a computed-goto dispatch mechanism for efficient opcode execution, achieving 2-5ns per instruction on modern processors.
• Register allocation is performed at compile time by the RegisterAllocationPass, using a linear-scan algorithm for hot paths.
• The 4-bit register fields support 16 logical registers; spill slots extend this to 256 virtual registers.

A.2 Opcode Space Layout

The 256-entry opcode space is organized into functional categories:

A.3 Data Movement Operations (0x00-0x0F)

Data movement operations transfer values between registers, memory, and the constant pool.

A.3.1 Basic Movement

Example: Loading a string constant

LOAD_CONST  R3, 42    ; R3 = pool[42] (string "hello")

A.4 Integer Arithmetic Operations (0x10-0x1F)

Integer arithmetic operates on 64-bit signed integers stored in general-purpose registers.

Overflow Semantics: Integer overflow wraps according to two's complement arithmetic. Division by zero raises an error.

A.5 Floating-Point Arithmetic (0x20-0x2F)

Floating-point operations follow IEEE 754 double precision semantics.

A.6 Bitwise Operations (0x30-0x3F)

Bitwise operations manipulate 64-bit integers at the bit level.

A.7 Comparison Operations (0x40-0x5F)

Comparison operations produce boolean results. The CVM supports type-specialized comparisons for optimal performance.

A.7.1 Integer Comparisons (0x40-0x4F)

A.7.2 Float Comparisons (0x50-0x57)

A.7.3 String Comparisons (0x58-0x5F)

A.8 Logical and Debug Operations (0x60-0x6F)

A.8.1 Logical Operations (0x60-0x65)

A.8.2 Debug Operations (0x66-0x6B)

A.9 Control Flow Operations (0x70-0x7F)

Control flow operations manage the program counter and function calls.

Branch Offset Encoding: The 16-bit signed offset is relative to the instruction following the branch, measured in 4-byte instruction units.

A.10 Type Operations (0x80-0x8F)

Type operations handle runtime type checking, casting, and NULL handling.

A.11 Field Access Operations (0x90-0x9F)

Field access operations extract and modify document fields.

A.12 Array Operations (0xA0-0xAF)

Array operations manipulate ordered collections of values.

A.13 String Operations (0xB0-0xBF)

String operations handle UTF-8 encoded text.

A.14 Aggregation Operations (0xC0-0xCF)

Aggregation operations support SQL aggregate functions and GROUP BY processing.

A.14.1 Single Aggregation (0xC0-0xC7)

A.14.2 Aggregation Tables (0xC8-0xCF)

Aggregation Function Types:

A.15 Query Buffer Operations (0xD0-0xDF)

Query buffer operations support window functions, hash joins, sorting, and set operations.

A.15.1 Window Buffer (0xD0-0xD3)

A.15.2 Hash Table (0xD4-0xD7)

A.15.3 Sort Buffer (0xD8-0xDB)

A.15.4 Set Operations (0xDC-0xDF)

Set Operation Types (encoded in imm16):

• 0: UNION
• 1: INTERSECT
• 2: EXCEPT

A.16 Working Table Operations (0xE0-0xE7)

Working table operations support recursive Common Table Expressions (CTEs).

A.17 Function Call Operations (0xE8-0xEF)

Function call operations invoke built-in, user-defined, and external functions.

A.18 Cursor Operations (0xF0-0xF7)

Cursor operations manage iteration over tables and CTEs.

Cursor Open Flags (imm16 encoding):

• Bit 15: is_cte flag (1=CTE, 0=collection)
• Bits 0-14: constant pool index for name

A.19 Subquery and External Operations (0xF8-0xFC)

External Function IDs:

The kFTSMatch external function implements the @@ (text search match) operator in WHERE clauses. When the planner encounters a column @@ to_tsquery('...') predicate, it lowers the expression to a CALL_EXTERNAL instruction with function ID 0x0100. The function accepts alternating field/query pairs on the argument stack and returns a boolean indicating whether the document matches the full-text search query. This enables CVM-compiled queries to evaluate FTS predicates inline without falling back to the Volcano executor.

A.20 Error and Extension (0xFD-0xFF)

A.21 Extended Opcodes (0xFE prefix)

Extended opcodes provide 256 additional instructions accessed via the 0xFE prefix.

A.21.1 Iteration Operations (0x01-0x0A)

A.21.2 Document Construction (0x0B-0x12)

A.21.3 Composite Row Operations (0x13-0x1C)

Composite row operations enable zero-copy JOIN processing.

A.21.3a Outer Context Operations (0x85)

Outer context operations support correlated subquery execution within the CVM. When a subquery references columns from an outer query, these opcodes resolve the outer column values without falling back to the Volcano executor.

GET_OUTER_FIELD reads a field from the outer query's current row. During plan lowering, column references whose table alias is not in the local alias set are emitted as GET_OUTER_FIELD instead of GET_FIELD. The interpreter resolves the field from the outer row context, which may be either a plain Document or a CompositeRow (for outer queries involving joins).

Example: Correlated subquery

SELECT d.name,
       (SELECT COUNT(*) FROM employees e WHERE e.dept_id = d.id)
FROM departments d

The inner subquery's reference to d.id compiles to:

GET_OUTER_FIELD  R3, pool["d.id"]   ; R3 = outer_row.d.id
GET_FIELD        R4, pool["dept_id"] ; R4 = current_row.dept_id
CMP_EQ_POLY      R5, R4, R3         ; R5 = (dept_id == d.id)

A.21.4 Vectorized/Batch Operations (0x20-0x67)

Batch operations enable SIMD-accelerated columnar processing.

Batch Scan (0x20-0x27):

Batch Arithmetic (0x28-0x37):

Batch Comparison (0x38-0x47):

Batch Logical (0x48-0x4F):

Parallel Operations (0x5C-0x67):

A.21.5 SPI Cursor Operations (0x68-0x6F)

SPI operations support PL/pgSQL FOR-query loops.

A.21.6 Exception Handling (0x70-0x76)

A.22 Runtime Type System

The CVM uses a dynamic type system with the following type enumeration:

A.22.1 VMValue Structure

The VMValue structure is a 24-byte discriminated union:

struct VMValue {
  CVMType type;     // 1 byte
  uint8_t flags;    // 1 byte (kFlagOwned=0x01, kFlagConst=0x02)
  uint16_t reserved;
  uint32_t padding;
  union {           // 16 bytes
    bool bool_val;
    int64_t int64_val;
    double double_val;
    StringRef string_val;
    ArrayRef array_val;
    Document* doc_val;
    CompositeRow* composite_row_val;
    TimestampVal timestamp_val;
    // ... other types
  };
};

A.23 Builtin Function Reference

The CVM provides an extensive library of built-in functions organized by category.

A.23.1 Mathematical Functions (0x0000-0x00FF)

A.23.2 String Functions (0x0100-0x01FF)

A.23.3 JSON/Document Functions (0x0500-0x05FF)

A.23.4 Date/Time Functions (0x0600-0x06FF)

A.24 Table Function Reference

Table functions return multiple rows and are used in FROM clauses.

A.25 Execution Examples

A.25.1 Simple Arithmetic Query

SELECT a + b * 2 FROM t

Compiled Bytecode:

00: CURSOR_OPEN     R0, 0, 42     ; Open cursor for table t
04: JMP_NULL        R0, 28        ; Jump to end if exhausted
08: GET_FIELD       R1, 43        ; R1 = doc.a
0C: GET_FIELD       R2, 44        ; R2 = doc.b
10: MOVE_IMM        R3, 2         ; R3 = 2
14: MUL_I64         R4, R2, R3    ; R4 = b * 2
18: ADD_I64         R5, R1, R4    ; R5 = a + (b * 2)
1C: EMIT_ROW        R5            ; Output result
20: CURSOR_NEXT     R0, 0         ; Advance cursor
24: JMP             -20           ; Loop back
28: CURSOR_CLOSE    0             ; Close cursor
2C: HALT                          ; Done

A.25.2 Aggregation Query

SELECT SUM(amount) FROM orders GROUP BY customer_id

Compiled Bytecode:

00: AGG_TBL_NEW     R0, 1         ; Create agg table (SUM)
04: CURSOR_OPEN     R1, 0, 50     ; Open orders cursor
08: JMP_NULL        R1, 40        ; Jump if exhausted
0C: GET_FIELD       R2, 51        ; R2 = customer_id
10: GET_FIELD       R3, 52        ; R3 = amount
14: AGG_GET_CREATE  R4, R0, R2    ; Get/create group for key
18: AGG_STATE_AT    R5, R4, 0     ; Get SUM state
1C: AGG_ACCUM       R5, R3        ; Accumulate amount
20: CURSOR_NEXT     R1, 0         ; Advance
24: JMP             -28           ; Loop
28: AGG_ITER_INIT   R0            ; Init group iterator
2C: AGG_ITER_NEXT   R6, R0        ; Get next group
30: JMP_NULL        R6, 48        ; Done if null
34: AGG_FINAL       R7, R6        ; Finalize SUM
38: EMIT_ROW        R7            ; Output
3C: JMP             -16           ; Next group
40: CURSOR_CLOSE    0
44: HALT

A.26 Performance Characteristics

A.26.1 Instruction Timing

A.26.2 Opcode Frequency Analysis

Typical query workloads show the following opcode distribution:

Insight

• The CVM achieves 2-5 million instructions per second for typical OLTP workloads through computed-goto dispatch and careful cache optimization.
• Vectorized batch operations (0x20-0x5F extended) can process 1000+ rows per opcode execution, achieving 10-50x throughput for analytical queries.
• Copy-and-patch JIT compilation elevates hot bytecode sequences to native code with 2-5x additional speedup at ~100us compilation latency.

A.27 Summary

The CVM instruction set provides a comprehensive foundation for executing SQL queries:

1. 256 core opcodes organized into functional categories
2. 256 extended opcodes via the 0xFE prefix for advanced operations
3. Fixed 32-bit encoding for cache efficiency and fast decode
4. Type-specialized operations for integer, float, and string processing
5. Query-specific operations for cursors, aggregation, joins, and window functions
6. Vectorized batch operations for SIMD-accelerated analytical processing
7. PL/pgSQL support via SPI and exception handling opcodes
8. Correlated subquery support via GET_OUTER_FIELD for outer row field access
9. Full-text search integration via CALL_EXTERNAL with kFTSMatch/kFTSScore for inline @@ operator evaluation

The instruction set balances:

• Decode efficiency through fixed-width encoding
• Expressiveness through comprehensive operation coverage
• Performance through type specialization and batch operations
• Extensibility through the extended opcode mechanism