Skip to content

codegen.md

Latest commit

 

History

History
266 lines (212 loc) · 11.1 KB

codegen.md

File metadata and controls

266 lines (212 loc) · 11.1 KB
Raw

C17 to WasmVM Lowering Pipeline Documentation

This document provides comprehensive documentation for the C17 to WasmVM lowering pipeline implementation, detailing each component and their integration.

Overview

The wvmcc compiler now includes a complete C17 to WasmVM lowering pipeline that transforms C17 source code into valid WebAssembly modules. This implementation follows the phased approach outlined in the lowering plan, with each phase building upon the previous ones to provide full C17 language support.

Code Generation Components

1. TypeMap

The TypeMap component is responsible for converting C types to their WebAssembly equivalents and providing type information for memory operations.

Key Features:

  • Converts C types to Wasm ValueType (e.g., int → i32, long/pointers → i64)
  • Calculates byte size and alignment for all C types
  • Determines if a type is memory resident (structs, unions, arrays)
  • Generates appropriate load/store instructions with memory indices

Implementation Details:

WasmVM::ValueType toWasmType(const wvmcc::parser::TypeNodePtr& type) const;
size_t byteSize(const wvmcc::parser::TypeNodePtr& type) const;
size_t byteAlignment(const wvmcc::parser::TypeNodePtr& type) const;
bool isMemoryResident(const wvmcc::parser::TypeNodePtr& type) const;
WasmVM::WasmInstr makeLoad(const wvmcc::parser::TypeNodePtr& type, uint8_t memidx) const;
WasmVM::WasmInstr makeStore(const wvmcc::parser::TypeNodePtr& type, uint8_t memidx) const;

2. SymbolTable

The SymbolTable manages symbol information with proper scoping and variable tracking.

Key Features:

  • Scope-stacked symbol management
  • Tracks different symbol types (ScalarLocal, MemoryLocal, GlobalScalar, GlobalMem, FuncSymbol)
  • Supports nested scopes with proper lookup and definition
  • Handles symbol visibility and lifetime

Implementation Details:

void pushScope();
void popScope();
bool define(const std::string& name, const VarInfoStruct& info);
std::optional<VarInfoStruct> lookup(const std::string& name) const;

3. TypeIndexCache

The TypeIndexCache deduplicates function types to avoid redundant entries in the Wasm module.

Key Features:

  • Interns FuncType objects to prevent duplication
  • Maintains a mapping from function types to indices in the module's type section
  • Provides efficient lookup for existing function types

Implementation Details:

WasmVM::index_t intern(const WasmVM::FuncType& funcType);
std::optional<WasmVM::index_t> getIndex(const WasmVM::FuncType& funcType) const;

4. GlobalDataAllocator

The GlobalDataAllocator manages static data allocation and string literal handling.

Key Features:

  • Allocates space for static data with proper alignment
  • Interns string literals and tracks their addresses
  • Generates Wasm data segments for static content

Implementation Details:

size_t allocate(size_t size, size_t align);
size_t internString(const std::string& str);
std::vector<WasmVM::WasmData> getDataSegments() const;

5. FunctionCodegen

The FunctionCodegen component generates WebAssembly code for individual functions.

Key Features:

  • Per-function code generation with instruction buffering
  • Local variable allocation and tracking
  • Control flow stack management for break/continue handling
  • Expression and statement emission with proper Wasm instruction generation

Implementation Details:

WasmVM::WasmFunc generate(const wvmcc::parser::FunctionDefPtr& funcDef, 
                          const wvmcc::parser::Semantic& semantic);
void emitExpr(const wvmcc::parser::ExprPtr& expr, bool needLValue = false);
void emitStmt(const wvmcc::parser::StmtPtr& stmt);

6. ModuleCodegen

The ModuleCodegen component orchestrates the entire module generation process.

Key Features:

  • First pass: symbol registration and function import/definition
  • Second pass: actual function body generation
  • Memory setup with proper Wasm64 memory configuration
  • Global variable and string literal handling

Implementation Details:

WasmVM::WasmModule generate(const wvmcc::parser::TranslationUnitPtr& tu);
void setupMemory();
void setupGlobals();
void firstPass(const wvmcc::parser::TranslationUnitPtr& tu);
void secondPass(const wvmcc::parser::TranslationUnitPtr& tu);

Memory Model

The implementation follows the Wasm64 memory model with a 4-bit namespace:

memidx  Purpose
─────   ─────────────────────────────────────────────────────
  0     Heap + Static data (Wasm64 i64 addresses)
        [0..7]          reserved (null pointer sentinel)
        [8..static_end) static data: aggregates, string literals (BSS/rodata)
        [static_end..)  future heap (malloc)
  1     Shadow stack (Wasm64 i64 addresses, grows downward)
        [top..bottom]   call frames (address-taken locals, aggregate locals)
 2–14   Explicit per-object placement via
        __attribute__((wvmcc_memidx(N))) on a file-scope/static object
        (both freestanding and linkable/multi-TU; see below).
   15   Reserved — the function-pointer tag (`kFuncPtrTag`); never a data memory,
        so NULL (0) is never a valid function pointer.

Explicit placement: __attribute__((wvmcc_memidx(N)))

A file-scope or static object can be placed in linear memory N (2..14) instead of the default mem[0]:

__attribute__((wvmcc_memidx(2))) int counter = 5;   // lives in mem[2]

ModuleCodegen::registerGlobalVar reads the attribute, stamps GlobalMem.memidx, bumps maxDataMemidx_ (ensureMemory), and emits the initializer data segment into (memory N). A named access compiles to a direct (memory N) load/store; &counter decays to a pointer tagged with nibble N, so an opaque deref dispatches to mem[N] via the tagged path below.

How memory N comes to exist depends on the compile mode:

  • Freestanding (-ffreestanding): ensureMemory defines mem[N] locally, filling any gap so memory indices stay contiguous.

  • Linkable (the default, multi-TU): the TU imports env.__memory_N (materializeMemoryImports, run after firstPass), so the object declares the memory it references. The linker's crt0 (Crt0Synth) drops every env memory import (__linear_memory, __stack_memory, __memory_N) and recreates that many local memories at the same indices. Per-TU static data — across all memories — is rebased by the merger's single per-TU delta (ModuleMerge); because each TU allocates offsets from one counter, the uniform shift keeps objects disjoint within every memory simultaneously, so no per-memory merge logic is needed. __heap_base is computed from mem[0] segments only.

    A cross-TU extern reference to a placed global works when the extern declaration carries the same wvmcc_memidx(N) attribute (the shared-header idiom) — readPlacementMemidx honors it on both the defining and referencing paths, so the imported address-global is dereferenced against the right memory. An unannotated extern of a placed global still resolves its address but reads mem[0] (the default) — a silent mismatch, the same hazard as declaring extern with the wrong type; keep the attribute in a shared header.

Tagged pointers (cross-memory dereference)

A C pointer value must work no matter which memory its target lives in, yet the deref site (*p, p->m, p[i]) cannot statically know whether a given pointer points at the heap (mem[0]) or the shadow stack (mem[1]). To bridge the two memories without merging them, a pointer value carries its target memidx in the high nibble of the i64 (bit 60, kMemidxShift); the low 60 bits hold the byte offset (kPtrOffMask).

  • Taking an address (&local, array/aggregate decay) ORs in the object's tag (emitApplyTag); mem[0] needs no tag (nibble 0), so only shadow-stack (mem[1]) and explicitly-placed (mem[N], N≥2) addresses set a nibble.
  • A named lvalue resolves to a statically known memory (addressKind carries the concrete memidx) and uses a direct load/store with that memidx.
  • An opaque pointer-rooted lvalue (addressKind → Dynamic: deref, ->, pointer indexing, call results, casts, pointer arithmetic) is dispatched at runtime by emitTaggedLoad/emitTaggedStore: branch on the nibble (an N-way chain sized by the highest live memidx), mask it off, then load/store from the selected memory.

This is what makes the &local-passed-to-a-helper idiom work (issue #78) — it is pervasive in real C and in the M2 runtime libc (vfprintf builds a local output context and calls do_format(&o, …), etc.), so the conformance run-suite under tests/standard/ exercises it implicitly. (Caveat: a pointer laundered through an integer typedef such as <stdint.h>'s uintptr_t can still mis-size to i32 and truncate the tag — that is the separate typedef-resolution gap, not a flaw in this scheme.)

Integration with Main Pipeline

The code generation is integrated into the main compilation pipeline in src/exec/main.cpp:

// Replace empty module construction with:
wvmcc::codegen::ModuleCodegen codegen(sem);
auto module = codegen.generate(tu);

Testing

Comprehensive unit tests are provided in tests/unit/codegen/ that verify:

  • Component instantiation and basic functionality
  • Type mapping correctness
  • Symbol table scoping behavior
  • Memory allocation and string interning
  • Function type deduplication

Phase Implementation Status

All five lowering phases are complete; codegen produces validated WasmModules for the full C17 subset described in docs/lowering-plan.md.

Phase 1 - Scalar Foundation (Complete)

  • Basic type mapping and memory model
  • Symbol table with scope management
  • Function code generation skeleton
  • Module generation with proper memory setup

Phase 2 - Memory and Aggregates (Complete)

  • Address-taken analysis
  • Shadow stack management
  • Struct/union layout support
  • Pointer and address expression handling (tagged-pointer cross-memory deref)

Phase 3 - Control Flow Completeness (Complete)

  • Break/continue support
  • Switch statement handling (dense br_table and sparse if/else)
  • Short-circuit evaluation
  • Ternary operator support

Phase 4 - Advanced Features (Complete)

  • Function pointers via tagged-i64 funcref-table slots + call_indirect
  • Static local variables
  • Arbitrary goto lowered through a dispatch loop (forward, backward, and non-local jumps), superseding the original forward-only restriction

Phase 5 - Robustness (Complete)

  • Comprehensive diagnostics on unimplemented paths
  • BSS zero-initialization
  • Integration testing suite

Usage Example

To compile a C file to WebAssembly:

./wvmcc input.c -o output.wasm

The resulting WebAssembly module will contain properly generated code with:

  • Correct function signatures and types
  • Proper memory layout and access patterns
  • Valid Wasm64 instructions for all C constructs

Validation

All generated modules are validated using WasmVM::module_validate() to ensure they meet WebAssembly specification requirements. The pipeline passes all existing parser and semantic unit tests while adding full code generation capabilities.