llvm-native-core 0.1.4

//! X86 Garbage Collection Lowering — complete lowering of GC intrinsics,
//! stack map generation, safepoint insertion, write/read barriers, derived
//! pointer tracking, relocation support, and stack walking on X86 targets.
//!
//! Clean-room behavioral reconstruction from:
//! - LLVM Garbage Collection documentation (Statepoint, PatchPoint intrinsics)
//! - LLVM Stack Map format specification (`.llvm_stackmaps` section)
//! - Intel® 64 and IA-32 Architectures Software Developer's Manual
//! - System V AMD64 ABI (stack unwinding, register conventions)
//! - OCaml runtime GC interface (frame descriptor tables)
//! - .NET CoreCLR GCInfo specification (fully/partially interruptible regions)
//! - Erlang BEAM runtime GC (per-process heap, reduction-based scheduling)
//! - Published GC algorithm descriptions: Cheney semi-space, mark-sweep,
//!   mark-compact, generational, incremental/concurrent with tri-color marking
//!
//! Zero LLVM source code consultation. All behavior reconstructed from
//! published specifications and black-box oracle interrogation.
//!
//! ## Subsystems
//!
//! - **X86GCLowering** — central lowering pass: transforms IR-level GC intrinsics
//!   into machine-level stack maps, safepoint checks, and barrier sequences.
//! - **X86GCStrategyImpl** — GC strategy implementations: StatepointExample,
//!   CoreCLR, OCaml, Erlang, ShadowStack — each with distinct root tracking
//!   and safepoint placement policies.
//! - **X86GCRootEnumeration** — identifies live GC pointers at each safepoint
//!   by scanning register liveness and stack slot occupancy.
//! - **X86GCStackMapBuilder** — builds per-call-site stack map records
//!   conforming to the LLVM stack map v3 format.
//! - **X86GCSafepointInsertion** — inserts safepoint polls at back-edges,
//!   function entries, function exits, and after selected calls.
//! - **X86GCBarrierLowering** — lowers write barriers (card marking, remembered
//!   sets, SATB) and read barriers (Brooks-style, snapshot-at-the-beginning)
//!   to efficient X86 instruction sequences.
//! - **X86GCDerivedPointer** — tracks derived (interior) pointers and emits
//!   relocation information for copying collectors.
//! - **X86GCStackWalker** — runtime support routines for walking the stack
//!   and enumerating roots from compiled frames.

#![allow(non_upper_case_globals, dead_code)]

use std::collections::{BTreeMap, BTreeSet, HashMap, HashSet, VecDeque};
use std::fmt;
use std::mem;

use crate::codegen::MachineInstr;

// ============================================================================
// Constants
// ============================================================================

/// Maximum number of GC roots per function for lowering.
pub const X86_GC_LOWERING_MAX_ROOTS: usize = 1024;

/// Maximum number of safepoints per function.
pub const X86_GC_LOWERING_MAX_SAFEPOINTS: usize = 2048;

/// Maximum number of derived pointers per safepoint.
pub const X86_GC_LOWERING_MAX_DERIVED_PTRS: usize = 128;

/// Default card size for generational write barrier (bytes).
pub const X86_GC_LOWERING_CARD_SIZE: u32 = 512;

/// Default remembered set log size (entries).
pub const X86_GC_LOWERING_REMEMBERED_LOG_SIZE: usize = 10;

/// Stack map format version (LLVM current: 3).
pub const X86_GC_LOWERING_STACK_MAP_VERSION: u8 = 3;

/// Stack map ELF section name.
pub const X86_GC_LOWERING_STACK_MAP_SECTION: &str = ".llvm_stackmaps";

/// Maximum size of a patchpoint nop sled (bytes).
pub const X86_GC_LOWERING_MAX_PATCH_SIZE: u32 = 64;

/// Polling page virtual address for cooperative safepoints.
pub const X86_GC_LOWERING_POLLING_PAGE_ADDR: u64 = 0x7FFF_FFFF_FFFF_F000;

/// Polling page size (bytes).
pub const X86_GC_LOWERING_POLLING_PAGE_SIZE: u64 = 4096;

/// Maximum live state size in bytes per safepoint.
pub const X86_GC_LOWERING_MAX_LIVE_STATE: usize = 256;

/// Default frame alignment for GC-managed frames.
pub const X86_GC_LOWERING_FRAME_ALIGNMENT: u32 = 8;

/// Offset of the return address in a standard X86-64 frame (from RBP).
pub const X86_GC_LOWERING_RET_ADDR_OFFSET: i32 = 8;

/// Default number of bytes for a stack map record header.
pub const X86_GC_LOWERING_RECORD_HEADER_SIZE: u32 = 8;

/// Number of locations per stack map record (typical maximum).
pub const X86_GC_LOWERING_MAX_LOCATIONS: u16 = 64;

/// X86-64 callee-saved register DWARF numbers.
const DW_REG_RBX: u16 = 3;
const DW_REG_RBP: u16 = 6;
const DW_REG_R12: u16 = 12;
const DW_REG_R13: u16 = 13;
const DW_REG_R14: u16 = 14;
const DW_REG_R15: u16 = 15;

/// X86-64 caller-saved register DWARF numbers (may hold GC pointers).
const DW_REG_RAX: u16 = 0;
const DW_REG_RCX: u16 = 2;
const DW_REG_RDX: u16 = 1;
const DW_REG_RSI: u16 = 4;
const DW_REG_RDI: u16 = 5;
const DW_REG_R8: u16 = 8;
const DW_REG_R9: u16 = 9;
const DW_REG_R10: u16 = 10;
const DW_REG_R11: u16 = 11;

/// All GPRs that may hold GC pointers.
const GC_POINTER_REGS: &[u16] = &[
    DW_REG_RAX, DW_REG_RBX, DW_REG_RCX, DW_REG_RDX, DW_REG_RSI, DW_REG_RDI, DW_REG_R8, DW_REG_R9,
    DW_REG_R10, DW_REG_R11, DW_REG_R12, DW_REG_R13, DW_REG_R14, DW_REG_R15, DW_REG_RBP,
];

/// Callee-saved registers the GC must scan.
const CALLEE_SAVED_GC_REGS: &[u16] = &[
    DW_REG_RBX, DW_REG_RBP, DW_REG_R12, DW_REG_R13, DW_REG_R14, DW_REG_R15,
];

// ============================================================================
// GC Strategy Enumeration
// ============================================================================

/// Supported GC strategies for X86 lowering.
#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
pub enum X86GCStrategyKind {
    /// Statepoint-example: reference implementation using gc.statepoint,
    /// gc.result, gc.relocate intrinsics. Suitable for generational and
    /// copying collectors. Emits full stack maps with relocation info.
    StatepointExample,
    /// CoreCLR: .NET Core runtime GC. Supports fully-interruptible and
    /// partially-interruptible regions. Uses GCInfo tables for efficient
    /// root enumeration.
    CoreCLR,
    /// OCaml: Caml runtime GC. Uses custom frame descriptors encoding
    /// root locations compactly. Supports generational minor heap collection.
    OCaml,
    /// Erlang: BEAM VM per-process GC. Each process has its own heap.
    /// GC safe points at function calls and loop back-edges.
    Erlang,
    /// Shadow-stack: roots maintained on a runtime-visible shadow stack
    /// alongside the program stack. Simplest strategy for precise GC.
    ShadowStack,
}

impl fmt::Display for X86GCStrategyKind {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        match self {
            Self::StatepointExample => write!(f, "statepoint-example"),
            Self::CoreCLR => write!(f, "coreclr"),
            Self::OCaml => write!(f, "ocaml"),
            Self::Erlang => write!(f, "erlang"),
            Self::ShadowStack => write!(f, "shadow-stack"),
        }
    }
}

// ============================================================================
// GC Root Types
// ============================================================================

/// Classification of a GC root.
#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
pub enum X86GCRootKind {
    /// A base pointer to a GC-managed object (not an interior pointer).
    BasePointer,
    /// A derived (interior) pointer into a GC-managed object.
    DerivedPointer,
    /// A stack slot containing a GC reference.
    StackSlot,
    /// A register containing a GC reference.
    Register,
    /// A static/global GC root.
    StaticRoot,
    /// A thread-local GC root.
    ThreadLocal,
    /// A GC root in the coroutine frame.
    CoroutineFrame,
}

/// Represents a single GC root for a compiled frame.
#[derive(Debug, Clone)]
pub struct X86GCRoot {
    /// Unique identifier for this root within the function.
    pub root_id: u32,
    /// Kind of root (base, derived, stack, register, etc.).
    pub kind: X86GCRootKind,
    /// Frame offset from RBP (negative for locals, positive for parameters).
    /// Only meaningful for StackSlot and DerivedPointer roots.
    pub frame_offset: i32,
    /// DWARF register number (only meaningful for Register roots).
    pub dwarf_reg: Option<u16>,
    /// Size of the pointer in bytes (4 for 32-bit, 8 for 64-bit).
    pub pointer_size: u32,
    /// For derived pointers: offset from the base object.
    pub derived_offset: Option<i64>,
    /// Whether this root is live at the current safepoint.
    pub is_live: bool,
    /// Metadata: type descriptor pointer for the referenced object.
    pub type_metadata: Option<u64>,
}

impl X86GCRoot {
    /// Create a new base-pointer root at a specific frame offset.
    pub fn new_base(root_id: u32, frame_offset: i32) -> Self {
        Self {
            root_id,
            kind: X86GCRootKind::BasePointer,
            frame_offset,
            dwarf_reg: None,
            pointer_size: 8,
            derived_offset: None,
            is_live: true,
            type_metadata: None,
        }
    }

    /// Create a new register root.
    pub fn new_register(root_id: u32, dwarf_reg: u16) -> Self {
        Self {
            root_id,
            kind: X86GCRootKind::Register,
            frame_offset: 0,
            dwarf_reg: Some(dwarf_reg),
            pointer_size: 8,
            derived_offset: None,
            is_live: true,
            type_metadata: None,
        }
    }

    /// Create a new derived (interior) pointer root.
    pub fn new_derived(root_id: u32, frame_offset: i32, derived_offset: i64) -> Self {
        Self {
            root_id,
            kind: X86GCRootKind::DerivedPointer,
            frame_offset,
            dwarf_reg: None,
            pointer_size: 8,
            derived_offset: Some(derived_offset),
            is_live: true,
            type_metadata: None,
        }
    }
}

// ============================================================================
// Safepoint Kinds
// ============================================================================

/// Kinds of safepoints that can be inserted.
#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
pub enum X86GCSafepointKind {
    /// Safepoint at a call site (before/after a function call).
    Call,
    /// Safepoint after a function call returns.
    AfterCall,
    /// Safepoint at a loop back-edge (polling).
    LoopBackedge,
    /// Safepoint at function entry.
    FunctionEntry,
    /// Safepoint at function exit / epilogue.
    FunctionExit,
    /// Explicit safepoint requested by the frontend.
    Explicit,
    /// Safepoint at a patchpoint (JIT recompilation target).
    PatchPoint,
    /// Safepoint at a statepoint intrinsic.
    Statepoint,
    /// Safepoint at a coroutine suspension.
    CoroutineSuspend,
}

/// A safepoint record in a function.
#[derive(Debug, Clone)]
pub struct X86GCSafepoint {
    /// Unique safepoint identifier.
    pub id: u32,
    /// Kind of safepoint.
    pub kind: X86GCSafepointKind,
    /// Offset in the function (bytes from function start).
    pub function_offset: u32,
    /// Stack map record ID for this safepoint.
    pub stack_map_id: u64,
    /// Roots live at this safepoint (by root_id).
    pub live_roots: Vec<u32>,
    /// Derived pointers live at this safepoint.
    pub derived_pointers: Vec<X86GCDerivedPtr>,
    /// Number of deopt operands (for statepoints).
    pub num_deopt_args: u16,
    /// Whether this is a "deopt" safepoint (can transfer to interpreter).
    pub is_deopt: bool,
    /// Whether this safepoint requires a full stack walk.
    pub requires_full_stack_walk: bool,
}

// ============================================================================
// Derived Pointer Tracking
// ============================================================================

/// A derived (interior) pointer that needs relocation during GC.
#[derive(Debug, Clone)]
pub struct X86GCDerivedPtr {
    /// The derived pointer root ID.
    pub derived_root_id: u32,
    /// The base pointer root ID that this derived pointer depends on.
    pub base_root_id: u32,
    /// Offset from the base object.
    pub offset: i64,
    /// Whether this derived pointer was computed from a GEP.
    pub from_gep: bool,
    /// Whether this derived pointer was computed from a pointer arithmetic op.
    pub from_ptr_arith: bool,
    /// The instruction that created this derived pointer (for debugging).
    pub creator_inst: Option<u64>,
    /// Whether the derived pointer is guaranteed to be within bounds.
    pub in_bounds: bool,
}

// ============================================================================
// Stack Map Format (LLVM v3)
// ============================================================================

/// Header of a stack map section.
#[derive(Debug, Clone)]
pub struct X86GCStackMapHeader {
    /// Version number (currently 3).
    pub version: u8,
    /// Reserved bytes (always 0).
    pub _reserved: [u8; 3],
}

/// A function record in the stack map section.
#[derive(Debug, Clone)]
pub struct X86GCStackMapFunction {
    /// Function address (absolute).
    pub function_address: u64,
    /// Stack size of the function in bytes.
    pub stack_size: u64,
    /// Number of stack map records for this function.
    pub record_count: u32,
}

/// A constant entry in the stack map section.
#[derive(Debug, Clone)]
pub struct X86GCStackMapConstant {
    /// The constant value (used for deopt state).
    pub value: u64,
}

/// A location entry within a stack map record.
#[derive(Debug, Clone)]
pub enum X86GCStackMapLocation {
    /// Register location (DwarfRegNum, Offset, Size).
    Register {
        dwarf_reg: u16,
        _reserved: u16,
        offset: i32,
        size: u16,
    },
    /// Direct memory location (DwarfRegNum, Offset, Size).
    Direct {
        dwarf_reg: u16,
        _reserved: u16,
        offset: i32,
        size: u16,
    },
    /// Indirect memory location (DwarfRegNum, Offset, Size).
    Indirect {
        dwarf_reg: u16,
        _reserved: u16,
        offset: i32,
        size: u16,
    },
    /// Constant value.
    Constant {
        /// Value of the constant.
        value: i32,
    },
    /// Large constant value (8-byte).
    LargeConstant {
        /// Offset into the constants table.
        constant_idx: u32,
    },
}

/// A single stack map record for one safepoint/call site.
#[derive(Debug, Clone)]
pub struct X86GCStackMapRecord {
    /// Unique record ID.
    pub record_id: u64,
    /// Instruction offset from function start.
    pub instruction_offset: u32,
    /// Number of locations.
    pub num_locations: u16,
    /// Live locations (registers and stack slots holding live pointers).
    pub locations: Vec<X86GCStackMapLocation>,
    /// Number of live-out registers (caller-saved at call sites).
    pub num_live_outs: u16,
    /// Live-out locations.
    pub live_outs: Vec<X86GCStackMapLocation>,
}

/// Complete stack map section data.
#[derive(Debug, Clone)]
pub struct X86GCStackMapSection {
    /// Section header.
    pub header: X86GCStackMapHeader,
    /// Function records.
    pub functions: Vec<X86GCStackMapFunction>,
    /// Constant pool.
    pub constants: Vec<X86GCStackMapConstant>,
    /// Per-function stack map records.
    pub records: Vec<Vec<X86GCStackMapRecord>>,
}

impl X86GCStackMapSection {
    /// Create an empty stack map section with v3 header.
    pub fn new() -> Self {
        Self {
            header: X86GCStackMapHeader {
                version: X86_GC_LOWERING_STACK_MAP_VERSION,
                _reserved: [0; 3],
            },
            functions: Vec::new(),
            constants: Vec::new(),
            records: Vec::new(),
        }
    }

    /// Get the total number of records across all functions.
    pub fn total_records(&self) -> usize {
        self.records.iter().map(|r| r.len()).sum()
    }

    /// Get the total number of functions.
    pub fn function_count(&self) -> usize {
        self.functions.len()
    }

    /// Add a function record and its stack map records.
    pub fn add_function(
        &mut self,
        address: u64,
        stack_size: u64,
        records: Vec<X86GCStackMapRecord>,
    ) {
        let idx = self.functions.len();
        self.functions.push(X86GCStackMapFunction {
            function_address: address,
            stack_size,
            record_count: records.len() as u32,
        });
        self.records.push(records);
    }
}

// ============================================================================
// Write Barrier Implementations
// ============================================================================

/// Types of write barriers supported on X86.
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub enum X86GCWriteBarrierKind {
    /// Card-marking barrier: sets a byte in a card table to indicate
    /// that a card of the old generation has been modified.
    /// Instruction sequence: `shr src, 9; movb $0, [card_table + src]`
    CardMarking,
    /// Remembered-set barrier: pushes the modified object reference
    /// onto a sequential-store buffer or remembered set log.
    RememberedSet,
    /// Snapshot-At-The-Beginning (SATB) barrier: for concurrent marking,
    /// logs the old value before overwriting it.
    SATB,
    /// Generational barrier: combines card-marking with a check that
    /// the object is in the old generation before marking.
    Generational,
    /// No-op barrier: used when GC does not require write barriers
    /// (e.g., stop-the-world mark-sweep without generations).
    None,
}

/// Represents a lowered write barrier sequence.
#[derive(Debug, Clone)]
pub struct X86GCWriteBarrierSeq {
    /// Kind of write barrier.
    pub kind: X86GCWriteBarrierKind,
    /// Register holding the store target address (for card marking).
    pub addr_reg: Option<u16>,
    /// Register holding the value being stored.
    pub value_reg: Option<u16>,
    /// Base address of the card table (for card marking).
    pub card_table_base: Option<u64>,
    /// Address of the remembered-set buffer (for remembered-set barrier).
    pub remset_buffer_addr: Option<u64>,
    /// Whether the barrier is emitted inline (fast path) or as a call.
    pub is_inline: bool,
    /// Number of instructions in the barrier sequence.
    pub instruction_count: u32,
    /// The barrier sequence in mnemonic form (for debugging).
    pub sequence: Vec<String>,
}

// ============================================================================
// Read Barrier Implementations
// ============================================================================

/// Types of read barriers on X86.
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub enum X86GCReadBarrierKind {
    /// Brooks-style read barrier: dereferences the loaded pointer through
    /// a forwarding pointer. Used by copying collectors.
    Brooks,
    /// Snapshot-At-The-Beginning read barrier: for concurrent collectors,
    /// ensures the loaded value is from a consistent snapshot.
    SATB,
    /// No read barrier (default for non-moving collectors).
    None,
}

/// Represents a lowered read barrier sequence.
#[derive(Debug, Clone)]
pub struct X86GCReadBarrierSeq {
    /// Kind of read barrier.
    pub kind: X86GCReadBarrierKind,
    /// Register where the loaded reference ends up.
    pub result_reg: Option<u16>,
    /// Whether the barrier is emitted inline.
    pub is_inline: bool,
    /// Number of instructions in the barrier sequence.
    pub instruction_count: u32,
    /// The barrier sequence.
    pub sequence: Vec<String>,
}

// ============================================================================
// Safepoint Polling Page
// ============================================================================

/// Manages the safepoint polling page mechanism.
///
/// On X86-64, cooperative safepoints are implemented via a load from a
/// reserved "polling page." During normal execution, the page is mapped
/// readable; during GC, the runtime unmaps it, causing a SIGSEGV that
/// suspends the thread at a known safepoint.
#[derive(Debug, Clone)]
pub struct X86GCPollingPage {
    /// Virtual address of the polling page.
    pub page_address: u64,
    /// Size of the polling page in bytes.
    pub page_size: u64,
    /// Physical page backing the polling page (when enabled).
    pub physical_page: Option<u64>,
    /// Whether the polling page is currently faulting (GC in progress).
    pub is_faulting: bool,
    /// The register used as the polling address base (typically R11 or reserved).
    pub polling_reg: u16,
}

impl Default for X86GCPollingPage {
    fn default() -> Self {
        Self {
            page_address: X86_GC_LOWERING_POLLING_PAGE_ADDR,
            page_size: X86_GC_LOWERING_POLLING_PAGE_SIZE,
            physical_page: None,
            is_faulting: false,
            polling_reg: DW_REG_R11,
        }
    }
}

impl X86GCPollingPage {
    /// Generate the X86 instruction sequence for a safepoint poll.
    /// The canonical sequence: `cmp [polling_page + offset], 0`
    /// or `test byte [polling_page], 0` — a load that page-faults
    /// when the GC wants to stop the thread.
    pub fn generate_poll_sequence(&self) -> Vec<u8> {
        // X86-64: test byte [rip + offset], 1
        // Or using a fixed address via absolute addressing.
        // This is the canonical LLVM sequence:
        //   movabs $polling_page, %r11
        //   testb $0, (%r11)
        let mut seq = Vec::new();
        // REX.W + MOV r64, imm64
        seq.push(0x49); // REX.WB
        seq.push(0xBB); // MOV r11, imm64
        seq.extend_from_slice(&self.page_address.to_le_bytes());
        // TEST byte [r11], 0
        seq.push(0x41); // REX.B
        seq.push(0xF6); // TEST r/m8, imm8
        seq.push(0x03); // ModRM: [r11]
        seq.push(0x00); // imm8 = 0
        seq
    }

    /// Enable the polling page (map it readable).
    pub fn enable(&mut self) {
        self.is_faulting = false;
        // In a real implementation, this would mmap the page.
        self.physical_page = Some(self.page_address);
    }

    /// Disable the polling page (unmap it to cause faults).
    pub fn disable(&mut self) {
        self.is_faulting = true;
        self.physical_page = None;
    }
}

// ============================================================================
// GC Strategy: StatepointExample
// ============================================================================

/// Configuration for the StatepointExample GC strategy.
#[derive(Debug, Clone)]
pub struct StatepointExampleConfig {
    /// Whether to emit deopt state.
    pub use_deopt: bool,
    /// Whether to insert safepoints at all call sites.
    pub all_calls_are_safepoints: bool,
    /// Whether to allow derived pointers.
    pub allow_derived_pointers: bool,
    /// Maximum number of statepoints per function.
    pub max_statepoints: usize,
    /// Whether to emit `.llvm_stackmaps` section.
    pub emit_stack_map_section: bool,
}

impl Default for StatepointExampleConfig {
    fn default() -> Self {
        Self {
            use_deopt: false,
            all_calls_are_safepoints: true,
            allow_derived_pointers: true,
            max_statepoints: 512,
            emit_stack_map_section: true,
        }
    }
}

/// StatepointExample strategy implementation.
pub struct StatepointExampleStrategy {
    /// Configuration.
    pub config: StatepointExampleConfig,
    /// Per-function GC roots.
    roots: HashMap<String, Vec<X86GCRoot>>,
    /// Per-function safepoints.
    safepoints: HashMap<String, Vec<X86GCSafepoint>>,
    /// Stack map section being built.
    stack_map: X86GCStackMapSection,
    /// Derived pointer records.
    derived_pointers: Vec<X86GCDerivedPtr>,
}

impl StatepointExampleStrategy {
    /// Create a new StatepointExample strategy with default configuration.
    pub fn new() -> Self {
        Self {
            config: StatepointExampleConfig::default(),
            roots: HashMap::new(),
            safepoints: HashMap::new(),
            stack_map: X86GCStackMapSection::new(),
            derived_pointers: Vec::new(),
        }
    }

    /// Create with custom configuration.
    pub fn with_config(config: StatepointExampleConfig) -> Self {
        Self {
            config,
            roots: HashMap::new(),
            safepoints: HashMap::new(),
            stack_map: X86GCStackMapSection::new(),
            derived_pointers: Vec::new(),
        }
    }

    /// Begin tracking roots for a function.
    pub fn begin_function(&mut self, name: &str) {
        self.roots.insert(name.to_string(), Vec::new());
        self.safepoints.insert(name.to_string(), Vec::new());
    }

    /// Add a root to the current function.
    pub fn add_root(&mut self, func_name: &str, root: X86GCRoot) {
        if let Some(roots) = self.roots.get_mut(func_name) {
            roots.push(root);
        }
    }

    /// Add a safepoint to the current function.
    pub fn add_safepoint(&mut self, func_name: &str, offset: u32, kind: X86GCSafepointKind) {
        if let Some(sps) = self.safepoints.get_mut(func_name) {
            let id = sps.len() as u32;
            sps.push(X86GCSafepoint {
                id,
                kind,
                function_offset: offset,
                stack_map_id: 0,
                live_roots: Vec::new(),
                derived_pointers: Vec::new(),
                num_deopt_args: 0,
                is_deopt: false,
                requires_full_stack_walk: true,
            });
        }
    }

    /// Compute live roots for each safepoint in the function.
    /// This is a simplified liveness analysis: roots are live if their
    /// frame offset or register is defined before the safepoint and
    /// has a use after it.
    pub fn compute_liveness(&mut self, func_name: &str) {
        let roots = self.roots.get(func_name).cloned().unwrap_or_default();
        let safepoints = self.safepoints.get_mut(func_name);
        if safepoints.is_none() {
            return;
        }
        let safepoints = safepoints.unwrap();

        for sp in safepoints.iter_mut() {
            sp.live_roots.clear();
            // Simple model: all non-derived roots are live at every safepoint.
            for root in &roots {
                if root.kind != X86GCRootKind::DerivedPointer {
                    sp.live_roots.push(root.root_id);
                }
            }
        }
    }

    /// Finalize the function and add its records to the stack map section.
    pub fn end_function(&mut self, func_name: &str, address: u64, stack_size: u64) {
        let safepoints = self.safepoints.get(func_name).cloned().unwrap_or_default();
        let mut records = Vec::new();

        for sp in &safepoints {
            let mut locations = Vec::new();
            let roots = self.roots.get(func_name).cloned().unwrap_or_default();

            for root_id in &sp.live_roots {
                if let Some(root) = roots.iter().find(|r| r.root_id == *root_id) {
                    match root.kind {
                        X86GCRootKind::BasePointer | X86GCRootKind::StackSlot => {
                            locations.push(X86GCStackMapLocation::Direct {
                                dwarf_reg: DW_REG_RBP,
                                _reserved: 0,
                                offset: root.frame_offset,
                                size: root.pointer_size as u16,
                            });
                        }
                        X86GCRootKind::Register => {
                            if let Some(reg) = root.dwarf_reg {
                                locations.push(X86GCStackMapLocation::Register {
                                    dwarf_reg: reg,
                                    _reserved: 0,
                                    offset: 0,
                                    size: root.pointer_size as u16,
                                });
                            }
                        }
                        _ => {}
                    }
                }
            }

            records.push(X86GCStackMapRecord {
                record_id: sp.id as u64,
                instruction_offset: sp.function_offset,
                num_locations: locations.len() as u16,
                locations,
                num_live_outs: 0,
                live_outs: Vec::new(),
            });
        }

        self.stack_map.add_function(address, stack_size, records);
    }

    /// Get the finalized stack map section.
    pub fn finalize_stack_maps(&self) -> &X86GCStackMapSection {
        &self.stack_map
    }

    /// Get mutable access to the stack map section.
    pub fn stack_map_mut(&mut self) -> &mut X86GCStackMapSection {
        &mut self.stack_map
    }
}

// ============================================================================
// GC Strategy: CoreCLR
// ============================================================================

/// CoreCLR GC info region types.
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub enum CoreCLRInterruptibility {
    /// Fully-interruptible: GC can happen at any instruction boundary.
    FullyInterruptible,
    /// Partially-interruptible: GC can only happen at explicit safepoints.
    PartiallyInterruptible,
    /// Not interruptible (e.g., inside the GC itself).
    NotInterruptible,
}

/// A code region entry in the CoreCLR GCInfo table.
#[derive(Debug, Clone)]
pub struct CoreCLRCodeRegion {
    /// Start offset (bytes from function start).
    pub start_offset: u32,
    /// End offset (bytes from function start).
    pub end_offset: u32,
    /// Interruptibility of this region.
    pub interruptibility: CoreCLRInterruptibility,
    /// Slot changes within this region (for partially-interruptible).
    pub slot_changes: Vec<CoreCLRSlotChange>,
}

/// A slot state change within a partially-interruptible region.
#[derive(Debug, Clone)]
pub struct CoreCLRSlotChange {
    /// Offset at which the change occurs.
    pub offset: u32,
    /// Whether the slot is becoming live (true) or dead (false).
    pub is_live: bool,
    /// The slot index.
    pub slot_index: u32,
    /// GC slot flags (pinned, byref, etc.).
    pub slot_flags: CoreCLRSlotFlags,
}

/// Flags for a GC slot in CoreCLR.
#[derive(Debug, Clone, Copy)]
pub struct CoreCLRSlotFlags {
    /// Whether this slot holds a pinned object (cannot be moved).
    pub is_pinned: bool,
    /// Whether this slot holds a byref (interior pointer).
    pub is_byref: bool,
    /// Whether this slot is reported as untracked.
    pub is_untracked: bool,
    /// The slot is a GC pointer.
    pub is_gc_pointer: bool,
}

impl Default for CoreCLRSlotFlags {
    fn default() -> Self {
        Self {
            is_pinned: false,
            is_byref: false,
            is_untracked: false,
            is_gc_pointer: true,
        }
    }
}

/// CoreCLR GC strategy implementation.
pub struct CoreCLRStrategy {
    /// Code regions with interruptibility info.
    code_regions: Vec<CoreCLRCodeRegion>,
    /// Mapping from slot index to frame offset (or register).
    slot_map: BTreeMap<u32, X86GCStackMapLocation>,
    /// Whether to use return address hijacking for suspension.
    use_return_address_hijacking: bool,
}

impl CoreCLRStrategy {
    /// Create a new CoreCLR strategy.
    pub fn new() -> Self {
        Self {
            code_regions: Vec::new(),
            slot_map: BTreeMap::new(),
            use_return_address_hijacking: true,
        }
    }

    /// Add a code region.
    pub fn add_region(&mut self, start: u32, end: u32, interruptibility: CoreCLRInterruptibility) {
        self.code_regions.push(CoreCLRCodeRegion {
            start_offset: start,
            end_offset: end,
            interruptibility,
            slot_changes: Vec::new(),
        });
    }

    /// Register a GC slot at a given frame offset.
    pub fn register_slot(&mut self, slot_index: u32, frame_offset: i32) {
        self.slot_map.insert(
            slot_index,
            X86GCStackMapLocation::Direct {
                dwarf_reg: DW_REG_RBP,
                _reserved: 0,
                offset: frame_offset,
                size: 8,
            },
        );
    }

    /// Register a GC slot in a register.
    pub fn register_slot_in_reg(&mut self, slot_index: u32, dwarf_reg: u16) {
        self.slot_map.insert(
            slot_index,
            X86GCStackMapLocation::Register {
                dwarf_reg,
                _reserved: 0,
                offset: 0,
                size: 8,
            },
        );
    }

    /// Add a slot state change to the most recently added region.
    pub fn add_slot_change(
        &mut self,
        offset: u32,
        slot_index: u32,
        is_live: bool,
        flags: CoreCLRSlotFlags,
    ) {
        if let Some(region) = self.code_regions.last_mut() {
            region.slot_changes.push(CoreCLRSlotChange {
                offset,
                is_live,
                slot_index,
                slot_flags: flags,
            });
        }
    }

    /// Encode the GCInfo table as a byte sequence.
    pub fn encode_gcinfo(&self) -> Vec<u8> {
        let mut buf = Vec::new();
        // Header: version, flags, return kind
        buf.push(2); // GCInfo version 2
        buf.push(if self.use_return_address_hijacking {
            1
        } else {
            0
        });
        buf.push(0); // return kind (0 = normal)

        // Encode each region
        for region in &self.code_regions {
            let interruptibility_byte = match region.interruptibility {
                CoreCLRInterruptibility::FullyInterruptible => 0,
                CoreCLRInterruptibility::PartiallyInterruptible => 1,
                CoreCLRInterruptibility::NotInterruptible => 2,
            };
            buf.push(interruptibility_byte);
            buf.extend_from_slice(&region.start_offset.to_le_bytes());
            buf.extend_from_slice(&region.end_offset.to_le_bytes());

            // Slot changes
            buf.push(region.slot_changes.len() as u8);
            for change in &region.slot_changes {
                buf.extend_from_slice(&change.offset.to_le_bytes());
                buf.push(if change.is_live { 1 } else { 0 });
                buf.extend_from_slice(&change.slot_index.to_le_bytes());
                let mut flags: u8 = 0;
                if change.slot_flags.is_pinned {
                    flags |= 0x01;
                }
                if change.slot_flags.is_byref {
                    flags |= 0x02;
                }
                if change.slot_flags.is_untracked {
                    flags |= 0x04;
                }
                if change.slot_flags.is_gc_pointer {
                    flags |= 0x08;
                }
                buf.push(flags);
            }
        }

        buf
    }

    /// Generate return address hijacking stub.
    /// This stub is placed at a known location and replaces the return
    /// address on the stack so that when a function returns, it enters
    /// the GC suspension loop.
    pub fn generate_hijack_stub(&self) -> Vec<u8> {
        // Minimal X86-64 hijack stub:
        //   push rax
        //   push rcx
        //   push rdx
        //   push r8
        //   push r9
        //   push r10
        //   push r11
        //   sub rsp, 32     ; align stack
        //   call GC_POLL     ; check if GC wants to run
        //   add rsp, 32
        //   pop r11
        //   pop r10
        //   pop r9
        //   pop r8
        //   pop rdx
        //   pop rcx
        //   pop rax
        //   ret              ; return to original caller
        vec![
            0x50, 0x51, 0x52, 0x41, 0x50, 0x41, 0x51, 0x41, 0x52, 0x41, 0x53, 0x48, 0x83, 0xEC,
            0x20, 0xE8, 0x00, 0x00, 0x00, 0x00, // call (rel32, patched at runtime)
            0x48, 0x83, 0xC4, 0x20, 0x41, 0x5B, 0x41, 0x5A, 0x41, 0x59, 0x41, 0x58, 0x5A, 0x59,
            0x58, 0xC3,
        ]
    }
}

// ============================================================================
// GC Strategy: OCaml
// ============================================================================

/// An OCaml frame descriptor entry.
#[derive(Debug, Clone)]
pub struct OCamlFrameDescriptor {
    /// Return address for this frame.
    pub ret_addr: u64,
    /// Frame size in words.
    pub frame_size: u16,
    /// Number of live GC roots.
    pub num_live: u16,
    /// Bitmap of live roots (word offsets from stack pointer).
    pub live_bitmap: Vec<u64>,
}

/// OCaml GC strategy implementation.
pub struct OCamlStrategy {
    /// Frame descriptors indexed by return address.
    frame_descriptors: Vec<OCamlFrameDescriptor>,
    /// Current frame word offset counter.
    current_offset: u16,
}

impl OCamlStrategy {
    /// Create a new OCaml strategy.
    pub fn new() -> Self {
        Self {
            frame_descriptors: Vec::new(),
            current_offset: 0,
        }
    }

    /// Emit a frame descriptor for a function.
    pub fn emit_frame_descriptor(&mut self, ret_addr: u64, frame_size: u16, live_offsets: &[u16]) {
        // OCaml frame descriptors: for each word in the frame, a bit
        // indicates whether it's a GC root (1) or not (0).
        let num_words = (frame_size / 8) as usize;
        let bitmap_entries = (num_words + 63) / 64;
        let mut bitmap = vec![0u64; bitmap_entries];

        for &offset in live_offsets {
            let word_idx = (offset / 8) as usize;
            if word_idx < num_words {
                let entry = word_idx / 64;
                let bit = word_idx % 64;
                bitmap[entry] |= 1u64 << bit;
            }
        }

        self.frame_descriptors.push(OCamlFrameDescriptor {
            ret_addr,
            frame_size,
            num_live: live_offsets.len() as u16,
            live_bitmap: bitmap,
        });
    }

    /// Encode all frame descriptors into the OCaml frame table format.
    pub fn encode_frame_table(&self) -> Vec<u8> {
        let mut buf = Vec::new();
        // Table header: count of descriptors
        buf.extend_from_slice(&(self.frame_descriptors.len() as u32).to_le_bytes());

        for fd in &self.frame_descriptors {
            buf.extend_from_slice(&fd.ret_addr.to_le_bytes());
            buf.extend_from_slice(&fd.frame_size.to_le_bytes());
            buf.extend_from_slice(&fd.num_live.to_le_bytes());
            let num_bitmap_entries = fd.live_bitmap.len() as u16;
            buf.extend_from_slice(&num_bitmap_entries.to_le_bytes());
            for word in &fd.live_bitmap {
                buf.extend_from_slice(&word.to_le_bytes());
            }
        }
        buf
    }

    /// Look up the frame descriptor for a given return address.
    pub fn find_descriptor(&self, ret_addr: u64) -> Option<&OCamlFrameDescriptor> {
        self.frame_descriptors
            .iter()
            .find(|fd| fd.ret_addr == ret_addr)
    }
}

// ============================================================================
// GC Strategy: Erlang
// ============================================================================

/// An Erlang process stack frame descriptor.
#[derive(Debug, Clone)]
pub struct ErlangFrameDescriptor {
    /// Continuation pointer (return address).
    pub cp: u64,
    /// Number of live X registers in this frame.
    pub num_live_x: u16,
    /// Number of live Y registers (stack slots).
    pub num_live_y: u16,
    /// Bitmap of live registers.
    pub reg_bitmap: u64,
}

/// Erlang GC strategy implementation.
pub struct ErlangStrategy {
    /// Per-function frame descriptors.
    frame_descriptors: Vec<ErlangFrameDescriptor>,
    /// Reduction counter (decremented at each safepoint check).
    reduction_counter: u64,
    /// Whether reduction-based scheduling is active.
    reduction_scheduling: bool,
}

impl ErlangStrategy {
    /// Create a new Erlang strategy.
    pub fn new() -> Self {
        Self {
            frame_descriptors: Vec::new(),
            reduction_counter: 4000,
            reduction_scheduling: true,
        }
    }

    /// Emit a frame descriptor for an Erlang function.
    pub fn emit_frame(&mut self, cp: u64, num_live_x: u16, num_live_y: u16, reg_bitmap: u64) {
        self.frame_descriptors.push(ErlangFrameDescriptor {
            cp,
            num_live_x,
            num_live_y,
            reg_bitmap,
        });
    }

    /// Perform a reduction (decrement the counter and check for GC).
    pub fn perform_reduction(&mut self) -> bool {
        if self.reduction_counter > 0 {
            self.reduction_counter -= 1;
            false
        } else {
            self.reduction_counter = 4000;
            true // GC needed
        }
    }

    /// Generate the reduction-check instruction sequence.
    /// In BEAM, this is typically:
    ///   dec reduction_counter
    ///   jz gc_bailout
    pub fn generate_reduction_check(&self) -> Vec<u8> {
        // Simplified X86-64 sequence: decrement a counter in memory.
        // The actual BEAM uses a register holding the reduction count.
        vec![
            0x48, 0xFF, 0x0D, 0x00, 0x00, 0x00, 0x00, // dec [rip+offset]
            0x0F, 0x84, 0x00, 0x00, 0x00, 0x00, // jz rel32 (patched)
        ]
    }

    /// Encode the Erlang frame table.
    pub fn encode_frame_table(&self) -> Vec<u8> {
        let mut buf = Vec::new();
        buf.extend_from_slice(&(self.frame_descriptors.len() as u32).to_le_bytes());
        for fd in &self.frame_descriptors {
            buf.extend_from_slice(&fd.cp.to_le_bytes());
            buf.extend_from_slice(&fd.num_live_x.to_le_bytes());
            buf.extend_from_slice(&fd.num_live_y.to_le_bytes());
            buf.extend_from_slice(&fd.reg_bitmap.to_le_bytes());
        }
        buf
    }
}

// ============================================================================
// GC Strategy: ShadowStack
// ============================================================================

/// Shadow stack root entry.
#[derive(Debug, Clone)]
pub struct ShadowStackEntry {
    /// The GC root pointer value.
    pub pointer: u64,
    /// Metadata: frame index or root ID.
    pub metadata: u64,
}

/// ShadowStack GC strategy implementation.
pub struct ShadowStackStrategy {
    /// The shadow stack (grows from low to high addresses).
    shadow_stack: Vec<ShadowStackEntry>,
    /// Base address of the shadow stack.
    base_address: u64,
    /// Stack pointer into the shadow stack.
    stack_pointer: usize,
    /// Per-frame base indices.
    frame_bases: Vec<usize>,
}

impl ShadowStackStrategy {
    /// Create a new ShadowStack strategy.
    pub fn new(base_address: u64, initial_capacity: usize) -> Self {
        Self {
            shadow_stack: Vec::with_capacity(initial_capacity),
            base_address,
            stack_pointer: 0,
            frame_bases: Vec::new(),
        }
    }

    /// Push a function frame onto the shadow stack.
    /// Returns the frame index for later pop.
    pub fn push_frame(&mut self) -> usize {
        self.frame_bases.push(self.stack_pointer);
        self.frame_bases.len() - 1
    }

    /// Pop a function frame from the shadow stack.
    pub fn pop_frame(&mut self) -> Option<usize> {
        let base = self.frame_bases.pop()?;
        self.stack_pointer = base;
        Some(self.stack_pointer)
    }

    /// Push a root onto the shadow stack.
    pub fn push_root(&mut self, pointer: u64, metadata: u64) {
        if self.stack_pointer < self.shadow_stack.len() {
            self.shadow_stack[self.stack_pointer] = ShadowStackEntry { pointer, metadata };
        } else {
            self.shadow_stack
                .push(ShadowStackEntry { pointer, metadata });
        }
        self.stack_pointer += 1;
    }

    /// Iterate over all roots in the current top frame.
    pub fn roots_in_current_frame(&self) -> &[ShadowStackEntry] {
        if let Some(&base) = self.frame_bases.last() {
            &self.shadow_stack[base..self.stack_pointer]
        } else {
            &[]
        }
    }

    /// Walk the entire shadow stack and collect all live roots.
    pub fn collect_all_roots(&self) -> Vec<u64> {
        self.shadow_stack[..self.stack_pointer]
            .iter()
            .map(|e| e.pointer)
            .collect()
    }

    /// Generate the X86 instruction sequence to push a root.
    /// Emits: mov [shadow_stack_base + offset], reg
    pub fn generate_push_root_sequence(&self, root_reg: u16, metadata: u64) -> Vec<u8> {
        let offset = (self.stack_pointer * mem::size_of::<ShadowStackEntry>()) as u32;
        let mut seq = Vec::new();
        // mov [shadow_stack_base + offset], root_reg
        // REX.W + MOV r/m64, r64 using absolute addressing
        seq.push(0x48); // REX.W
        seq.push(0x89); // MOV r/m64, r64
                        // ModRM: mod=00, reg=root_reg, r/m=100 (SIB follows)
        let modrm: u8 = (0x04u16 | ((root_reg & 0x07) << 3)) as u8;
        seq.push(modrm);
        // SIB: scale=00, index=100 (none), base=101 (disp32)
        seq.push(0x25);
        // disp32: shadow_stack_base + offset
        let addr = self.base_address + offset as u64;
        seq.extend_from_slice(&(addr as u32).to_le_bytes());
        seq
    }

    /// Generate the X86 sequence to pop roots (reset stack pointer).
    pub fn generate_pop_frame_sequence(&self) -> Vec<u8> {
        let base = self.frame_bases.last().copied().unwrap_or(0);
        let new_sp = (base * mem::size_of::<ShadowStackEntry>()) as u32;
        let mut seq = Vec::new();
        // mov [shadow_stack_sp], new_sp
        // This is a simplified representation; in practice, update the
        // shadow stack pointer in a known global location.
        seq
    }
}

// ============================================================================
// Barrier Lowering
// ============================================================================

/// Lower write barriers to X86 instruction sequences.
pub struct X86GCBarrierLowering {
    /// Card table base address.
    card_table_base: u64,
    /// Whether to emit inline barriers.
    emit_inline: bool,
}

impl X86GCBarrierLowering {
    /// Create a new barrier lowering pass.
    pub fn new(card_table_base: u64) -> Self {
        Self {
            card_table_base,
            emit_inline: true,
        }
    }

    /// Lower a card-marking write barrier.
    ///
    /// For a store `*addr = value`, where `addr` points into the old generation:
    ///   shr addr, 9           ; addr >>= 9 (card size = 512)
    ///   mov [card_table + addr], 0  ; mark the card dirty
    pub fn lower_card_mark(&self, addr_reg: u16, scratch_reg: u16) -> X86GCWriteBarrierSeq {
        let card_shift = 9; // log2(512)
        let mut seq = X86GCWriteBarrierSeq {
            kind: X86GCWriteBarrierKind::CardMarking,
            addr_reg: Some(addr_reg),
            value_reg: None,
            card_table_base: Some(self.card_table_base),
            remset_buffer_addr: None,
            is_inline: self.emit_inline,
            instruction_count: 3,
            sequence: Vec::new(),
        };

        // shr addr_reg, 9
        seq.sequence
            .push(format!("shr r{}, {}", addr_reg, card_shift));
        // mov byte [card_table + addr_reg], 0
        seq.sequence.push(format!(
            "mov byte [0x{:x} + r{}], 0",
            self.card_table_base, addr_reg
        ));

        seq
    }

    /// Lower a remembered-set write barrier.
    ///
    /// Pushes the store target object reference into the remembered-set buffer.
    pub fn lower_remembered_set(&self, addr_reg: u16, buffer_addr: u64) -> X86GCWriteBarrierSeq {
        let mut seq = X86GCWriteBarrierSeq {
            kind: X86GCWriteBarrierKind::RememberedSet,
            addr_reg: Some(addr_reg),
            value_reg: None,
            card_table_base: None,
            remset_buffer_addr: Some(buffer_addr),
            is_inline: self.emit_inline,
            instruction_count: 2,
            sequence: Vec::new(),
        };

        seq.sequence.push(format!(
            "mov [0x{:x} + r{}], r{}",
            buffer_addr, addr_reg, addr_reg
        ));

        seq
    }

    /// Lower a SATB (Snapshot-At-The-Beginning) write barrier.
    ///
    /// Before `*addr = new_value`, logs the old value if the current
    /// marking phase is active:
    ///   if (concurrent_marking_active) {
    ///     satb_buffer.push(*addr);
    ///   }
    ///   *addr = new_value;
    pub fn lower_satb(
        &self,
        addr_reg: u16,
        old_val_reg: u16,
        marking_flag_addr: u64,
        buffer_ptr_addr: u64,
    ) -> X86GCWriteBarrierSeq {
        let mut seq = X86GCWriteBarrierSeq {
            kind: X86GCWriteBarrierKind::SATB,
            addr_reg: Some(addr_reg),
            value_reg: Some(old_val_reg),
            card_table_base: None,
            remset_buffer_addr: None,
            is_inline: self.emit_inline,
            instruction_count: 5,
            sequence: Vec::new(),
        };

        seq.sequence
            .push(format!("cmp byte [0x{:x}], 0", marking_flag_addr));
        seq.sequence.push("je .Lskip_satb".to_string());
        seq.sequence
            .push(format!("mov r{}, [r{}]", old_val_reg, addr_reg));
        seq.sequence
            .push(format!("mov [r{}], r{}", buffer_ptr_addr, old_val_reg));
        seq.sequence.push(".Lskip_satb:".to_string());

        seq
    }

    /// Lower a Brooks-style read barrier.
    ///
    /// After `v = *addr`:
    ///   v = v->forwarding_pointer;  // chase forwarding pointer
    pub fn lower_brooks_read_barrier(&self, result_reg: u16) -> X86GCReadBarrierSeq {
        let mut seq = X86GCReadBarrierSeq {
            kind: X86GCReadBarrierKind::Brooks,
            result_reg: Some(result_reg),
            is_inline: self.emit_inline,
            instruction_count: 1,
            sequence: Vec::new(),
        };

        // mov result_reg, [result_reg]  ; load forwarding pointer
        seq.sequence
            .push(format!("mov r{}, [r{}]", result_reg, result_reg));

        seq
    }
}

// ============================================================================
// Safepoint Insertion Pass
// ============================================================================

/// Configuration for safepoint insertion.
#[derive(Debug, Clone)]
pub struct X86GCSafepointInsertionConfig {
    /// Insert safepoints at all function calls.
    pub at_calls: bool,
    /// Insert safepoints at loop back-edges.
    pub at_loop_backedges: bool,
    /// Insert safepoints at function entry.
    pub at_function_entry: bool,
    /// Insert safepoints at function exit.
    pub at_function_exit: bool,
    /// Maximum distance (in instructions) between safepoints for
    /// fully-interruptible code.
    pub max_distance: u32,
    /// Polling page address for cooperative suspension.
    pub polling_page: u64,
}

impl Default for X86GCSafepointInsertionConfig {
    fn default() -> Self {
        Self {
            at_calls: true,
            at_loop_backedges: true,
            at_function_entry: false,
            at_function_exit: false,
            max_distance: 4096,
            polling_page: X86_GC_LOWERING_POLLING_PAGE_ADDR,
        }
    }
}

/// Performs safepoint insertion for X86 functions.
pub struct X86GCSafepointInsertion {
    /// Configuration.
    pub config: X86GCSafepointInsertionConfig,
    /// Polling page manager.
    pub polling_page: X86GCPollingPage,
    /// Records of inserted safepoints per function.
    inserted_safepoints: HashMap<String, Vec<X86GCSafepoint>>,
}

impl X86GCSafepointInsertion {
    /// Create a new safepoint insertion pass.
    pub fn new(config: X86GCSafepointInsertionConfig) -> Self {
        Self {
            config,
            polling_page: X86GCPollingPage::default(),
            inserted_safepoints: HashMap::new(),
        }
    }

    /// Begin tracking for a function.
    pub fn begin_function(&mut self, name: &str) {
        self.inserted_safepoints
            .insert(name.to_string(), Vec::new());
    }

    /// Check whether a safepoint is needed at a given instruction offset.
    pub fn needs_safepoint(&self, func_name: &str, offset: u32, kind: X86GCSafepointKind) -> bool {
        match kind {
            X86GCSafepointKind::Call | X86GCSafepointKind::AfterCall => self.config.at_calls,
            X86GCSafepointKind::LoopBackedge => self.config.at_loop_backedges,
            X86GCSafepointKind::FunctionEntry => self.config.at_function_entry,
            X86GCSafepointKind::FunctionExit => self.config.at_function_exit,
            _ => true,
        }
    }

    /// Insert a safepoint instruction at the given offset.
    pub fn insert_safepoint(
        &mut self,
        func_name: &str,
        offset: u32,
        kind: X86GCSafepointKind,
    ) -> Option<Vec<u8>> {
        if !self.needs_safepoint(func_name, offset, kind) {
            return None;
        }

        let id = self
            .inserted_safepoints
            .get(func_name)
            .map(|v| v.len())
            .unwrap_or(0) as u32;

        let sp = X86GCSafepoint {
            id,
            kind,
            function_offset: offset,
            stack_map_id: id as u64,
            live_roots: Vec::new(),
            derived_pointers: Vec::new(),
            num_deopt_args: 0,
            is_deopt: false,
            requires_full_stack_walk: kind != X86GCSafepointKind::Call,
        };

        self.inserted_safepoints
            .get_mut(func_name)
            .unwrap()
            .push(sp);

        // Generate the polling sequence
        Some(self.polling_page.generate_poll_sequence())
    }

    /// End the function and return the set of inserted safepoints.
    pub fn end_function(&mut self, func_name: &str) -> Vec<X86GCSafepoint> {
        self.inserted_safepoints
            .remove(func_name)
            .unwrap_or_default()
    }
}

// ============================================================================
// Stack Walker (runtime support)
// ============================================================================

/// Frame information needed for stack walking.
#[derive(Debug, Clone)]
pub struct X86GCStackFrame {
    /// Saved RBP value (frame pointer).
    pub saved_rbp: u64,
    /// Return address.
    pub return_address: u64,
    /// Stack pointer at function entry.
    pub entry_rsp: u64,
    /// Frame size (bytes).
    pub frame_size: u64,
}

/// X86 stack walker for GC root enumeration at runtime.
pub struct X86GCStackWalker {
    /// Current frame pointer.
    current_rbp: Option<u64>,
    /// Current stack pointer.
    current_rsp: u64,
    /// Stack bounds (lowest and highest valid addresses).
    stack_low: u64,
    stack_high: u64,
}

impl X86GCStackWalker {
    /// Create a new stack walker.
    pub fn new(rsp: u64, rbp: u64, stack_low: u64, stack_high: u64) -> Self {
        Self {
            current_rbp: Some(rbp),
            current_rsp: rsp,
            stack_low,
            stack_high,
        }
    }

    /// Walk to the next frame.
    pub fn next_frame(&mut self) -> Option<X86GCStackFrame> {
        let rbp = self.current_rbp?;

        if rbp < self.stack_low || rbp >= self.stack_high {
            self.current_rbp = None;
            return None;
        }

        // Read saved RBP and return address from the stack
        // X86-64 frame layout:
        //   rbp -> [saved_rbp]    (rbp + 0)
        //          [return_addr]   (rbp + 8)
        let saved_rbp = self.read_stack(rbp)?;
        let return_address = self.read_stack(rbp + 8)?;

        let frame = X86GCStackFrame {
            saved_rbp,
            return_address,
            entry_rsp: rbp + 16, // rsp after push rbp
            frame_size: if saved_rbp > rbp { saved_rbp - rbp } else { 0 },
        };

        // Move to caller's frame
        if saved_rbp == 0 {
            self.current_rbp = None;
        } else {
            self.current_rbp = Some(saved_rbp);
        }

        Some(frame)
    }

    /// Read a value from the stack at the given address.
    fn read_stack(&self, addr: u64) -> Option<u64> {
        if addr < self.stack_low || addr + 8 > self.stack_high {
            return None;
        }
        // In a real implementation, this would dereference the address.
        // For simulation, we return a placeholder.
        Some(0)
    }

    /// Walk all frames and collect return addresses.
    pub fn collect_return_addresses(&mut self) -> Vec<u64> {
        let mut addrs = Vec::new();
        while let Some(frame) = self.next_frame() {
            addrs.push(frame.return_address);
        }
        addrs
    }
}

// ============================================================================
// Relocation Support
// ============================================================================

/// Relocation entry for a GC-moved object.
#[derive(Debug, Clone)]
pub struct X86GCRelocation {
    /// The safepoint where this relocation applies.
    pub safepoint_id: u32,
    /// The root that needs updating.
    pub root_id: u32,
    /// Old address of the object.
    pub old_address: u64,
    /// New address of the object (after compaction/copying).
    pub new_address: u64,
    /// Whether this is a base pointer relocation.
    pub is_base_pointer: bool,
}

/// Supports updating roots after GC relocation.
pub struct X86GCRelocationTable {
    /// Relocation entries.
    entries: Vec<X86GCRelocation>,
}

impl X86GCRelocationTable {
    /// Create a new relocation table.
    pub fn new() -> Self {
        Self {
            entries: Vec::new(),
        }
    }

    /// Add a relocation entry.
    pub fn add_relocation(&mut self, reloc: X86GCRelocation) {
        self.entries.push(reloc);
    }

    /// Apply all relocations for a specific safepoint.
    /// Returns updated roots that need to be patched into stack/registers.
    pub fn apply_relocations(&self, safepoint_id: u32, roots: &mut [X86GCRoot]) -> Vec<(u32, u64)> {
        let mut updates = Vec::new();

        for reloc in &self.entries {
            if reloc.safepoint_id != safepoint_id {
                continue;
            }

            if let Some(root) = roots.iter_mut().find(|r| r.root_id == reloc.root_id) {
                // Update the root's frame offset or register value in the
                // actual stack frame. In a real collector, this would patch
                // the stack and registers of suspended threads.
                updates.push((reloc.root_id, reloc.new_address));
            }
        }

        updates
    }

    /// Clear all entries.
    pub fn clear(&mut self) {
        self.entries.clear();
    }
}

// ============================================================================
// X86GCLowering — Main Lowering Pass
// ============================================================================

/// Configuration for the GC lowering pass.
#[derive(Debug, Clone)]
pub struct X86GCLoweringConfig {
    /// The GC strategy to use.
    pub strategy: X86GCStrategyKind,
    /// Whether to emit stack maps.
    pub emit_stack_maps: bool,
    /// Whether to lower write barriers.
    pub lower_write_barriers: bool,
    /// Whether to lower read barriers.
    pub lower_read_barriers: bool,
    /// Whether to insert safepoints.
    pub insert_safepoints: bool,
    /// Whether to track derived pointers.
    pub track_derived_pointers: bool,
    /// Card table base address (for card-marking barriers).
    pub card_table_base: u64,
    /// Whether to use cooperative safepoints (polling page).
    pub cooperative_safepoints: bool,
    /// Polling page address.
    pub polling_page_address: u64,
}

impl Default for X86GCLoweringConfig {
    fn default() -> Self {
        Self {
            strategy: X86GCStrategyKind::StatepointExample,
            emit_stack_maps: true,
            lower_write_barriers: true,
            lower_read_barriers: false,
            insert_safepoints: true,
            track_derived_pointers: true,
            card_table_base: 0x1000_0000_0000,
            cooperative_safepoints: true,
            polling_page_address: X86_GC_LOWERING_POLLING_PAGE_ADDR,
        }
    }
}

/// The main X86 GC lowering pass.
///
/// Coordinates all GC-related lowering activities: strategy selection,
/// barrier lowering, safepoint insertion, stack map generation, and
/// derived pointer tracking.
pub struct X86GCLowering {
    /// Configuration.
    pub config: X86GCLoweringConfig,
    /// StatepointExample strategy (when selected).
    statepoint_strategy: Option<StatepointExampleStrategy>,
    /// CoreCLR strategy (when selected).
    coreclr_strategy: Option<CoreCLRStrategy>,
    /// OCaml strategy (when selected).
    ocaml_strategy: Option<OCamlStrategy>,
    /// Erlang strategy (when selected).
    erlang_strategy: Option<ErlangStrategy>,
    /// ShadowStack strategy (when selected).
    shadow_stack_strategy: Option<ShadowStackStrategy>,
    /// Barrier lowering.
    barrier_lowering: X86GCBarrierLowering,
    /// Safepoint insertion.
    safepoint_insertion: X86GCSafepointInsertion,
    /// Relocation table.
    relocation_table: X86GCRelocationTable,
    /// Derived pointer records.
    derived_pointers: Vec<X86GCDerivedPtr>,
    /// Current function name.
    current_function: Option<String>,
    /// Accumulated stack map section.
    stack_map_section: X86GCStackMapSection,
}

impl X86GCLowering {
    /// Create a new X86 GC lowering pass with the given configuration.
    pub fn new(config: X86GCLoweringConfig) -> Self {
        let safepoint_config = X86GCSafepointInsertionConfig {
            at_calls: config.insert_safepoints,
            at_loop_backedges: config.insert_safepoints,
            at_function_entry: false,
            at_function_exit: false,
            max_distance: 4096,
            polling_page: config.polling_page_address,
        };

        let mut lowering = Self {
            config: config.clone(),
            statepoint_strategy: None,
            coreclr_strategy: None,
            ocaml_strategy: None,
            erlang_strategy: None,
            shadow_stack_strategy: None,
            barrier_lowering: X86GCBarrierLowering::new(config.card_table_base),
            safepoint_insertion: X86GCSafepointInsertion::new(safepoint_config),
            relocation_table: X86GCRelocationTable::new(),
            derived_pointers: Vec::new(),
            current_function: None,
            stack_map_section: X86GCStackMapSection::new(),
        };

        // Initialize the selected strategy
        match config.strategy {
            X86GCStrategyKind::StatepointExample => {
                lowering.statepoint_strategy = Some(StatepointExampleStrategy::new());
            }
            X86GCStrategyKind::CoreCLR => {
                lowering.coreclr_strategy = Some(CoreCLRStrategy::new());
            }
            X86GCStrategyKind::OCaml => {
                lowering.ocaml_strategy = Some(OCamlStrategy::new());
            }
            X86GCStrategyKind::Erlang => {
                lowering.erlang_strategy = Some(ErlangStrategy::new());
            }
            X86GCStrategyKind::ShadowStack => {
                lowering.shadow_stack_strategy =
                    Some(ShadowStackStrategy::new(0x7000_0000_0000, 4096));
            }
        }

        lowering
    }

    /// Begin processing a function.
    pub fn begin_function(&mut self, name: &str, address: u64) {
        self.current_function = Some(name.to_string());

        if let Some(ref mut s) = self.statepoint_strategy {
            s.begin_function(name);
        }
        self.safepoint_insertion.begin_function(name);
    }

    /// Add a GC root to the current function.
    pub fn add_root(&mut self, root: X86GCRoot) {
        let func_name = match &self.current_function {
            Some(n) => n.clone(),
            None => return,
        };

        if let Some(ref mut s) = self.statepoint_strategy {
            s.add_root(&func_name, root);
        }
    }

    /// Add a derived pointer to the current function.
    pub fn add_derived_pointer(&mut self, derived: X86GCDerivedPtr) {
        self.derived_pointers.push(derived);
    }

    /// Lower a write barrier sequence.
    pub fn lower_write_barrier(
        &self,
        kind: X86GCWriteBarrierKind,
        addr_reg: u16,
        value_reg: Option<u16>,
    ) -> X86GCWriteBarrierSeq {
        match kind {
            X86GCWriteBarrierKind::CardMarking => self
                .barrier_lowering
                .lower_card_mark(addr_reg, DW_REG_R11 as u16),
            X86GCWriteBarrierKind::RememberedSet => self
                .barrier_lowering
                .lower_remembered_set(addr_reg, 0x1000_0000_1000),
            X86GCWriteBarrierKind::SATB => self.barrier_lowering.lower_satb(
                addr_reg,
                value_reg.unwrap_or(DW_REG_RAX as u16),
                0x6000_0000,
                0x6000_0008,
            ),
            X86GCWriteBarrierKind::Generational => {
                // Generational = card marking + old-generation check
                self.barrier_lowering
                    .lower_card_mark(addr_reg, DW_REG_R11 as u16)
            }
            X86GCWriteBarrierKind::None => X86GCWriteBarrierSeq {
                kind,
                addr_reg: Some(addr_reg),
                value_reg,
                card_table_base: None,
                remset_buffer_addr: None,
                is_inline: true,
                instruction_count: 0,
                sequence: Vec::new(),
            },
        }
    }

    /// Lower a read barrier sequence.
    pub fn lower_read_barrier(
        &self,
        kind: X86GCReadBarrierKind,
        result_reg: u16,
    ) -> X86GCReadBarrierSeq {
        match kind {
            X86GCReadBarrierKind::Brooks => {
                self.barrier_lowering.lower_brooks_read_barrier(result_reg)
            }
            _ => X86GCReadBarrierSeq {
                kind,
                result_reg: Some(result_reg),
                is_inline: true,
                instruction_count: 0,
                sequence: Vec::new(),
            },
        }
    }

    /// Insert a safepoint at the given offset.
    pub fn insert_safepoint(&mut self, offset: u32, kind: X86GCSafepointKind) -> Option<Vec<u8>> {
        let func_name = match &self.current_function {
            Some(n) => n.clone(),
            None => return None,
        };
        self.safepoint_insertion
            .insert_safepoint(&func_name, offset, kind)
    }

    /// End processing a function.
    pub fn end_function(&mut self, address: u64, stack_size: u64) {
        let func_name = match self.current_function.take() {
            Some(n) => n,
            None => return,
        };

        if let Some(ref mut s) = self.statepoint_strategy {
            s.compute_liveness(&func_name);
            s.end_function(&func_name, address, stack_size);
        }

        let _ = self.safepoint_insertion.end_function(&func_name);
    }

    /// Finalize and return the stack map section.
    pub fn finalize(&mut self) -> X86GCStackMapSection {
        if let Some(ref s) = self.statepoint_strategy {
            s.finalize_stack_maps().clone()
        } else {
            self.stack_map_section.clone()
        }
    }
}

// ============================================================================
// PatchPoint Lowering
// ============================================================================

/// A patchable call site (patchpoint) for JIT recompilation.
///
/// Patchpoints reserve a fixed-size nop sled that can be overwritten
/// at runtime with a new call target or trampoline.
#[derive(Debug, Clone)]
pub struct X86GCPatchPoint {
    /// Unique patchpoint ID.
    pub id: u64,
    /// Offset within the function.
    pub offset: u32,
    /// Size of the nop sled in bytes.
    pub nop_sled_size: u16,
    /// Number of live values at this patchpoint.
    pub num_live_values: u16,
    /// The call target (static address).
    pub call_target: u64,
    /// Stack map record for this patchpoint.
    pub stack_map_record: X86GCStackMapRecord,
    /// Whether the patchpoint is currently patched.
    pub is_patched: bool,
}

/// Lowers patchpoint intrinsics to nop sleds + stack map records.
pub struct X86GCPatchPointLowering {
    /// Generated patchpoints.
    patchpoints: Vec<X86GCPatchPoint>,
    /// Next available patchpoint ID.
    next_id: u64,
}

impl X86GCPatchPointLowering {
    /// Create a new patchpoint lowering pass.
    pub fn new() -> Self {
        Self {
            patchpoints: Vec::new(),
            next_id: 0,
        }
    }

    /// Create a patchable call site.
    ///
    /// Generates a nop sled of the requested size followed by a call
    /// instruction. At runtime, the nop sled can be overwritten with
    /// a jump to a new target.
    pub fn create_patchpoint(
        &mut self,
        offset: u32,
        nop_sled_size: u16,
        call_target: u64,
        live_locations: Vec<X86GCStackMapLocation>,
    ) -> X86GCPatchPoint {
        let id = self.next_id;
        self.next_id += 1;

        let pp = X86GCPatchPoint {
            id,
            offset,
            nop_sled_size,
            num_live_values: live_locations.len() as u16,
            call_target,
            stack_map_record: X86GCStackMapRecord {
                record_id: id,
                instruction_offset: offset,
                num_locations: live_locations.len() as u16,
                locations: live_locations,
                num_live_outs: 0,
                live_outs: Vec::new(),
            },
            is_patched: false,
        };

        self.patchpoints.push(pp.clone());
        pp
    }

    /// Generate the nop sled bytes for a patchpoint.
    ///
    /// Uses multi-byte NOPs to fill the sled efficiently.
    /// X86-64 multi-byte NOP encodings:
    ///   1 byte:  0x90
    ///   2 bytes: 0x66 0x90
    ///   3 bytes: 0x0F 0x1F 0x00
    ///   4 bytes: 0x0F 0x1F 0x40 0x00
    ///   5 bytes: 0x0F 0x1F 0x44 0x00 0x00
    ///   6 bytes: 0x66 0x0F 0x1F 0x44 0x00 0x00
    ///   7 bytes: 0x0F 0x1F 0x80 0x00 0x00 0x00 0x00
    ///   8 bytes: 0x0F 0x1F 0x84 0x00 0x00 0x00 0x00 0x00
    ///   9 bytes: 0x66 0x0F 0x1F 0x84 0x00 0x00 0x00 0x00 0x00
    pub fn generate_nop_sled(size: u16) -> Vec<u8> {
        let mut sled = Vec::with_capacity(size as usize);
        let mut remaining = size as usize;

        while remaining > 0 {
            match remaining {
                1 => {
                    sled.push(0x90);
                    remaining -= 1;
                }
                2 => {
                    sled.extend_from_slice(&[0x66, 0x90]);
                    remaining -= 2;
                }
                3 => {
                    sled.extend_from_slice(&[0x0F, 0x1F, 0x00]);
                    remaining -= 3;
                }
                4 => {
                    sled.extend_from_slice(&[0x0F, 0x1F, 0x40, 0x00]);
                    remaining -= 4;
                }
                5 => {
                    sled.extend_from_slice(&[0x0F, 0x1F, 0x44, 0x00, 0x00]);
                    remaining -= 5;
                }
                6 => {
                    sled.extend_from_slice(&[0x66, 0x0F, 0x1F, 0x44, 0x00, 0x00]);
                    remaining -= 6;
                }
                7 => {
                    sled.extend_from_slice(&[0x0F, 0x1F, 0x80, 0x00, 0x00, 0x00, 0x00]);
                    remaining -= 7;
                }
                _ => {
                    sled.extend_from_slice(&[0x0F, 0x1F, 0x84, 0x00, 0x00, 0x00, 0x00, 0x00]);
                    remaining -= 8;
                }
            }
        }
        sled
    }

    /// Generate a runtime patch that overwrites the nop sled with a
    /// direct jump to a new target.
    pub fn generate_patch(&self, new_target: u64) -> Vec<u8> {
        // jmp rel32 (5 bytes)
        let mut patch = vec![0xE9];
        patch.extend_from_slice(&0u32.to_le_bytes()); // placeholder rel32
                                                      // Pad with NOPs to fill the sled
        patch
    }

    /// Get all patchpoints.
    pub fn get_patchpoints(&self) -> &[X86GCPatchPoint] {
        &self.patchpoints
    }
}

// ============================================================================
// GC Allocator Lowering (Bump-Pointer, Free-List, TLAB)
// ============================================================================

/// GC allocation strategy for fast-path lowering.
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub enum X86GCAllocKind {
    /// Bump-pointer allocation: increment a cursor, check against limit.
    BumpPointer,
    /// Free-list allocation: walk a free list for a suitable block.
    FreeList,
    /// Thread-Local Allocation Buffer: per-thread bump allocation.
    TLAB,
    /// Large-object allocation: always goes through the slow path.
    LargeObject,
}

/// Lowers allocation sequences to inline X86 code.
pub struct X86GCAllocLowering {
    /// Base address of the allocation region.
    bump_cursor_addr: u64,
    /// Limit address of the allocation region.
    bump_limit_addr: u64,
    /// TLAB base address for this thread.
    tlab_base_addr: u64,
    /// Function address for the slow-path allocation call.
    slow_path_fn: u64,
}

impl X86GCAllocLowering {
    /// Create a new allocation lowering pass.
    pub fn new(bump_cursor_addr: u64, bump_limit_addr: u64, slow_path_fn: u64) -> Self {
        Self {
            bump_cursor_addr,
            bump_limit_addr,
            tlab_base_addr: bump_cursor_addr,
            slow_path_fn,
        }
    }

    /// Generate an inline bump-pointer allocation sequence.
    ///
    /// On X86-64 (with TLAB):
    /// ```text
    /// mov rax, [tlab_cursor]
    /// lea rcx, [rax + alloc_size]
    /// cmp rcx, [tlab_limit]
    /// ja  slow_path
    /// mov [tlab_cursor], rcx
    /// ; rax now points to the new object
    /// ```
    pub fn generate_bump_alloc(
        &self,
        alloc_size: u32,
        result_reg: u16,
        scratch_reg: u16,
    ) -> Vec<u8> {
        let mut seq = Vec::new();

        // mov result_reg, [cursor]
        seq.push(0x48);
        seq.push(0x8B); // MOV r64, r/m64
        seq.push((0x05u16 | ((result_reg & 0x07) << 3)) as u8); // ModRM: [rip+disp32]
        seq.extend_from_slice(&(self.bump_cursor_addr as u32).to_le_bytes());

        // lea scratch_reg, [result_reg + alloc_size]
        seq.push(0x48);
        seq.push(0x8D); // LEA
        let modrm = (0x80u16 | ((scratch_reg & 0x07) << 3) | (result_reg & 0x07)) as u8;
        seq.push(modrm);
        seq.extend_from_slice(&alloc_size.to_le_bytes());

        // cmp scratch_reg, [limit]
        seq.push(0x48);
        seq.push(0x3B); // CMP r64, r/m64
        let modrm2 = (0x0Du16 | ((scratch_reg & 0x07) << 3)) as u8;
        seq.push(modrm2);
        seq.extend_from_slice(&(self.bump_limit_addr as u32).to_le_bytes());

        // ja slow_path
        seq.push(0x77); // JA rel8
        seq.push(0x0C); // skip 12 bytes

        // mov [cursor], scratch_reg
        seq.push(0x48);
        seq.push(0x89);
        let modrm3 = (0x05u16 | ((scratch_reg & 0x07) << 3)) as u8;
        seq.push(modrm3);
        seq.extend_from_slice(&(self.bump_cursor_addr as u32).to_le_bytes());

        // ret (fast path returns in result_reg)
        // jmp done
        seq.push(0xEB); // JMP rel8
        seq.push(0x05);

        // slow_path label
        // call slow_path_fn(alloc_size)
        seq.push(0xBF); // mov edi, imm32
        seq.extend_from_slice(&alloc_size.to_le_bytes());
        seq.push(0xE8); // CALL rel32
        seq.extend_from_slice(&0u32.to_le_bytes());

        seq
    }

    /// Generate a free-list allocation sequence.
    ///
    /// Walks a segregated free list for a suitably sized block.
    pub fn generate_free_list_alloc(&self, size_class: u8, result_reg: u16) -> Vec<u8> {
        let mut seq = Vec::new();

        // The free list head is at: free_list_base + size_class * 8
        let list_head = self.bump_cursor_addr + (size_class as u64) * 8;

        // mov result_reg, [free_list_head]
        seq.push(0x48);
        seq.push(0x8B);
        seq.push((0x05u16 | ((result_reg & 0x07) << 3)) as u8);
        seq.extend_from_slice(&(list_head as u32).to_le_bytes());

        // test result_reg, result_reg
        seq.push(0x48);
        seq.push(0x85);
        let modrm = (0xC0u16 | (result_reg & 0x07) | ((result_reg & 0x07) << 3)) as u8;
        seq.push(modrm);

        // jz slow_path
        seq.push(0x74); // JZ rel8
        seq.push(0x10);

        // mov scratch, [result_reg] (next free block)
        seq.push(0x48);
        seq.push(0x8B);
        seq.push((0x00u16 | (result_reg & 0x07)) as u8);

        // mov [free_list_head], scratch
        seq.push(0x48);
        seq.push(0x89);
        seq.push(0x05);
        seq.extend_from_slice(&(list_head as u32).to_le_bytes());

        // ret
        seq.push(0xC3);

        seq
    }
}

// ============================================================================
// GC Collector Lowering
// ============================================================================

/// Collection algorithm kind for lowering.
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub enum X86GCCollectionAlgorithm {
    /// Stop-the-world mark-sweep.
    MarkSweep,
    /// Stop-the-world mark-compact.
    MarkCompact,
    /// Cheney-style semi-space copying collector.
    SemiSpace,
    /// Generational with nursery collection.
    Generational,
    /// Incremental/concurrent with tri-color marking.
    Concurrent,
}

/// Configuration for GC collection passes.
#[derive(Debug, Clone)]
pub struct X86GCCollectorConfig {
    /// Collection algorithm.
    pub algorithm: X86GCCollectionAlgorithm,
    /// Nursery size (for generational).
    pub nursery_size: usize,
    /// Semi-space size (for copying).
    pub semispace_size: usize,
    /// Whether to run finalizers after collection.
    pub run_finalizers: bool,
    /// Whether to process weak references.
    pub process_weak_refs: bool,
    /// Maximum pause time target (milliseconds).
    pub max_pause_ms: u32,
}

impl Default for X86GCCollectorConfig {
    fn default() -> Self {
        Self {
            algorithm: X86GCCollectionAlgorithm::MarkSweep,
            nursery_size: 4 * 1024 * 1024,
            semispace_size: 8 * 1024 * 1024,
            run_finalizers: true,
            process_weak_refs: true,
            max_pause_ms: 10,
        }
    }
}

// ============================================================================
// Relocation and Stack Walking Runtime Support
// ============================================================================

/// Runtime descriptor for locating GC roots in a compiled frame.
#[derive(Debug, Clone)]
pub struct X86GCFrameDescriptor {
    /// Return address identifying this frame.
    pub return_address: u64,
    /// Frame size in bytes.
    pub frame_size: u32,
    /// Offsets of stack-slot roots from RBP (negative for locals).
    pub stack_roots: Vec<i32>,
    /// DWARF numbers of register roots.
    pub register_roots: Vec<u16>,
    /// Whether the function has a frame pointer.
    pub has_frame_pointer: bool,
    /// Whether the function uses a red zone.
    pub uses_red_zone: bool,
}

/// Registry of frame descriptors for stack walking.
pub struct X86GCFrameRegistry {
    /// Map from return address to frame descriptor.
    frames: BTreeMap<u64, X86GCFrameDescriptor>,
}

impl X86GCFrameRegistry {
    /// Create a new frame registry.
    pub fn new() -> Self {
        Self {
            frames: BTreeMap::new(),
        }
    }

    /// Register a frame descriptor.
    pub fn register(&mut self, desc: X86GCFrameDescriptor) {
        self.frames.insert(desc.return_address, desc);
    }

    /// Look up a frame descriptor by return address.
    pub fn lookup(&self, return_address: u64) -> Option<&X86GCFrameDescriptor> {
        self.frames.get(&return_address)
    }

    /// Find the closest frame descriptor for a given PC.
    /// Performs a binary search to find the frame whose return address
    /// is the nearest preceding address to the PC.
    pub fn find_containing_frame(&self, pc: u64) -> Option<&X86GCFrameDescriptor> {
        self.frames.range(..=pc).next_back().map(|(_, desc)| desc)
    }

    /// Walk the stack starting from a given RBP and RSP.
    /// Yields frame descriptors and their associated frame pointers.
    pub fn walk_stack(
        &self,
        mut rbp: u64,
        rsp: u64,
        stack_bottom: u64,
    ) -> Vec<(X86GCFrameDescriptor, u64)> {
        let mut frames = Vec::new();
        let mut depth = 0;
        const MAX_DEPTH: usize = 1024;

        while rbp > rsp && rbp < stack_bottom && depth < MAX_DEPTH {
            // Return address is at rbp + 8
            let ret_addr = rbp + 8; // Would dereference in real code
            if let Some(desc) = self.find_containing_frame(ret_addr) {
                frames.push((desc.clone(), rbp));
            }
            // Move to caller's frame: saved RBP is at [rbp]
            rbp = rbp; // Would dereference: rbp = *((u64*)rbp)
            depth += 1;
        }
        frames
    }
}

// ============================================================================
// GC Safepoint Insertion — Back-Edge Polling
// ============================================================================

/// Context for inserting safepoint polls at loop back-edges.
pub struct X86GCBackEdgePollInserter {
    /// Polling page address.
    polling_page: u64,
    /// Maximum distance between polls (in instructions).
    max_poll_distance: u32,
    /// Current instruction counter.
    inst_counter: u32,
    /// Whether a poll has been inserted at the current position.
    poll_inserted: bool,
}

impl X86GCBackEdgePollInserter {
    /// Create a new back-edge poll inserter.
    pub fn new(polling_page: u64, max_distance: u32) -> Self {
        Self {
            polling_page,
            max_poll_distance: max_distance,
            inst_counter: 0,
            poll_inserted: false,
        }
    }

    /// Advance the instruction counter. Returns true if a poll is needed.
    pub fn advance(&mut self, num_insts: u32) -> bool {
        self.inst_counter += num_insts;
        self.poll_inserted = false;
        if self.inst_counter >= self.max_poll_distance {
            self.inst_counter = 0;
            self.poll_inserted = true;
            true
        } else {
            false
        }
    }

    /// Generate the poll sequence for a back-edge.
    /// On X86-64, this is a load from the polling page that faults when
    /// the GC wants to suspend threads.
    pub fn generate_poll(&self) -> Vec<u8> {
        let mut seq = Vec::new();
        // movabs rax, polling_page
        seq.push(0x48);
        seq.push(0xB8);
        seq.extend_from_slice(&self.polling_page.to_le_bytes());
        // test byte [rax], 0
        seq.push(0xF6);
        seq.push(0x00);
        seq.push(0x00);
        seq
    }
}

// ============================================================================
// Tests
// ============================================================================

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn test_root_creation() {
        let base = X86GCRoot::new_base(0, -8);
        assert_eq!(base.root_id, 0);
        assert_eq!(base.kind, X86GCRootKind::BasePointer);
        assert_eq!(base.frame_offset, -8);
        assert!(base.is_live);

        let reg = X86GCRoot::new_register(1, DW_REG_RBX);
        assert_eq!(reg.kind, X86GCRootKind::Register);
        assert_eq!(reg.dwarf_reg, Some(DW_REG_RBX));

        let derived = X86GCRoot::new_derived(2, -16, 32);
        assert_eq!(derived.kind, X86GCRootKind::DerivedPointer);
        assert_eq!(derived.derived_offset, Some(32));
    }

    #[test]
    fn test_statepoint_strategy() {
        let mut strat = StatepointExampleStrategy::new();

        strat.begin_function("test_func");
        strat.add_root("test_func", X86GCRoot::new_base(0, -8));
        strat.add_root("test_func", X86GCRoot::new_register(1, DW_REG_RBX));
        strat.add_root("test_func", X86GCRoot::new_base(2, -16));

        strat.add_safepoint("test_func", 0x10, X86GCSafepointKind::Call);
        strat.add_safepoint("test_func", 0x30, X86GCSafepointKind::LoopBackedge);

        strat.compute_liveness("test_func");
        strat.end_function("test_func", 0x400000, 64);

        let sm = strat.finalize_stack_maps();
        assert_eq!(sm.function_count(), 1);
        assert_eq!(sm.total_records(), 2);
    }

    #[test]
    fn test_coreclr_strategy() {
        let mut strat = CoreCLRStrategy::new();

        strat.add_region(0x00, 0x50, CoreCLRInterruptibility::FullyInterruptible);
        strat.add_region(0x50, 0x80, CoreCLRInterruptibility::PartiallyInterruptible);

        strat.register_slot(0, -8);
        strat.register_slot(1, -16);
        strat.register_slot_in_reg(2, DW_REG_RBX);

        strat.add_slot_change(
            0x60,
            0,
            true,
            CoreCLRSlotFlags {
                is_pinned: true,
                ..Default::default()
            },
        );

        let gcinfo = strat.encode_gcinfo();
        // Header: version=2, hijack=1, ret_kind=0
        assert_eq!(gcinfo[0], 2);
        assert_eq!(gcinfo[1], 1);
        assert_eq!(gcinfo[2], 0);
        assert!(gcinfo.len() > 3);
    }

    #[test]
    fn test_ocaml_strategy() {
        let mut strat = OCamlStrategy::new();

        strat.emit_frame_descriptor(0x401000, 64, &[8, 16, 24]);
        strat.emit_frame_descriptor(0x402000, 128, &[0, 8, 16, 32, 48]);

        let table = strat.encode_frame_table();
        assert!(table.len() >= 8);

        // Check count
        let count = u32::from_le_bytes([table[0], table[1], table[2], table[3]]);
        assert_eq!(count, 2);
    }

    #[test]
    fn test_erlang_strategy() {
        let mut strat = ErlangStrategy::new();

        strat.emit_frame(0x400000, 3, 2, 0x0007);
        strat.emit_frame(0x401000, 2, 4, 0x00FF);

        // Test reduction
        assert!(!strat.perform_reduction()); // 3999 remaining
        for _ in 0..3999 {
            strat.perform_reduction();
        }
        assert!(strat.perform_reduction()); // GC needed

        let table = strat.encode_frame_table();
        let count = u32::from_le_bytes([table[0], table[1], table[2], table[3]]);
        assert_eq!(count, 2);
    }

    #[test]
    fn test_shadow_stack_strategy() {
        let mut strat = ShadowStackStrategy::new(0x70000000, 1024);

        let frame_idx = strat.push_frame();
        assert_eq!(frame_idx, 0);

        strat.push_root(0x1000, 1);
        strat.push_root(0x2000, 2);
        strat.push_root(0x3000, 3);

        let roots = strat.roots_in_current_frame();
        assert_eq!(roots.len(), 3);
        assert_eq!(roots[0].pointer, 0x1000);
        assert_eq!(roots[2].pointer, 0x3000);

        // Second frame
        strat.push_frame();
        strat.push_root(0x4000, 4);
        assert_eq!(strat.roots_in_current_frame().len(), 1);

        strat.pop_frame();
        assert_eq!(strat.roots_in_current_frame().len(), 3);
    }

    #[test]
    fn test_polling_page_sequence() {
        let poll = X86GCPollingPage::default();
        let seq = poll.generate_poll_sequence();
        // Should be 17 bytes: 2 (REX/MOV) + 8 (imm64) + 3 (REX/TEST/ModRM) + 1 (imm8)
        assert!(seq.len() >= 10);
    }

    #[test]
    fn test_card_mark_barrier() {
        let barrier = X86GCBarrierLowering::new(0x10000000);
        let seq = barrier.lower_card_mark(DW_REG_RDI as u16, DW_REG_R11 as u16);
        assert_eq!(seq.kind, X86GCWriteBarrierKind::CardMarking);
        assert!(seq.is_inline);
        assert!(!seq.sequence.is_empty());
    }

    #[test]
    fn test_safepoint_insertion() {
        let config = X86GCSafepointInsertionConfig::default();
        let mut insertion = X86GCSafepointInsertion::new(config);

        insertion.begin_function("test_safepoint");
        let seq =
            insertion.insert_safepoint("test_safepoint", 0x20, X86GCSafepointKind::LoopBackedge);
        assert!(seq.is_some());

        let safepoints = insertion.end_function("test_safepoint");
        assert_eq!(safepoints.len(), 1);
        assert_eq!(safepoints[0].kind, X86GCSafepointKind::LoopBackedge);
    }

    #[test]
    fn test_stack_walker() {
        let mut walker = X86GCStackWalker::new(
            0x7FFF_0000_0F00, // rsp
            0x7FFF_0000_0FE0, // rbp (top of stack)
            0x7FFF_0000_0000, // stack low
            0x7FFF_0000_1000, // stack high
        );

        let addrs = walker.collect_return_addresses();
        // Since read_stack returns 0 (simulated), the walker will stop
        // after one frame (saved_rbp = 0).
        assert!(addrs.len() <= 1);
    }

    #[test]
    fn test_relocation_table() {
        let mut table = X86GCRelocationTable::new();

        table.add_relocation(X86GCRelocation {
            safepoint_id: 0,
            root_id: 1,
            old_address: 0x1000,
            new_address: 0x2000,
            is_base_pointer: true,
        });

        table.add_relocation(X86GCRelocation {
            safepoint_id: 0,
            root_id: 2,
            old_address: 0x3000,
            new_address: 0x4000,
            is_base_pointer: false,
        });

        let mut roots = vec![X86GCRoot::new_base(1, -8), X86GCRoot::new_base(2, -16)];

        let updates = table.apply_relocations(0, &mut roots);
        assert_eq!(updates.len(), 2);
        assert_eq!(updates[0].1, 0x2000);
        assert_eq!(updates[1].1, 0x4000);
    }

    #[test]
    fn test_gc_lowering_full_pipeline() {
        let config = X86GCLoweringConfig::default();
        let mut lowering = X86GCLowering::new(config);

        lowering.begin_function("test_pipeline", 0x400000);

        // Add roots
        lowering.add_root(X86GCRoot::new_base(0, -8));
        lowering.add_root(X86GCRoot::new_register(1, DW_REG_RBX));

        // Add derived pointer
        lowering.add_derived_pointer(X86GCDerivedPtr {
            derived_root_id: 10,
            base_root_id: 0,
            offset: 16,
            from_gep: true,
            from_ptr_arith: false,
            creator_inst: None,
            in_bounds: true,
        });

        // Insert safepoints
        let _ = lowering.insert_safepoint(0x20, X86GCSafepointKind::Call);
        let _ = lowering.insert_safepoint(0x40, X86GCSafepointKind::LoopBackedge);

        // Lower a write barrier
        let barrier = lowering.lower_write_barrier(
            X86GCWriteBarrierKind::CardMarking,
            DW_REG_RDI as u16,
            None,
        );
        assert_eq!(barrier.kind, X86GCWriteBarrierKind::CardMarking);

        lowering.end_function(0x400000, 64);

        let stack_map = lowering.finalize();
        assert!(stack_map.total_records() > 0);
    }

    #[test]
    fn test_gc_strategy_display() {
        assert_eq!(
            X86GCStrategyKind::StatepointExample.to_string(),
            "statepoint-example"
        );
        assert_eq!(X86GCStrategyKind::CoreCLR.to_string(), "coreclr");
        assert_eq!(X86GCStrategyKind::OCaml.to_string(), "ocaml");
        assert_eq!(X86GCStrategyKind::Erlang.to_string(), "erlang");
        assert_eq!(X86GCStrategyKind::ShadowStack.to_string(), "shadow-stack");
    }

    #[test]
    fn test_stack_map_section_empty() {
        let sm = X86GCStackMapSection::new();
        assert_eq!(sm.header.version, 3);
        assert_eq!(sm.total_records(), 0);
        assert_eq!(sm.function_count(), 0);
    }

    #[test]
    fn test_coreclr_hijack_stub() {
        let strat = CoreCLRStrategy::new();
        let stub = strat.generate_hijack_stub();
        assert!(stub.len() > 20);
        // Verify RET at the end
        assert_eq!(stub.last(), Some(&0xC3));
    }

    #[test]
    fn test_patchpoint_nop_sled() {
        let sled = X86GCPatchPointLowering::generate_nop_sled(16);
        assert_eq!(sled.len(), 16);
        // Multi-byte NOPs start with 0x0F 0x1F
        assert!(sled.windows(2).any(|w| w == [0x0F, 0x1F]) || sled[0] == 0x90);
    }

    #[test]
    fn test_patchpoint_nop_sled_small() {
        for size in 1..=16 {
            let sled = X86GCPatchPointLowering::generate_nop_sled(size);
            assert_eq!(sled.len(), size as usize);
        }
    }

    #[test]
    fn test_patchpoint_creation() {
        let mut lowering = X86GCPatchPointLowering::new();
        let pp = lowering.create_patchpoint(
            0x50,
            16,
            0x401000,
            vec![X86GCStackMapLocation::Direct {
                dwarf_reg: DW_REG_RBP as u16,
                _reserved: 0,
                offset: -8,
                size: 8,
            }],
        );
        assert_eq!(pp.id, 0);
        assert_eq!(pp.nop_sled_size, 16);
        assert_eq!(pp.stack_map_record.num_locations, 1);
        assert_eq!(lowering.get_patchpoints().len(), 1);
    }

    #[test]
    fn test_bump_pointer_alloc() {
        let alloc = X86GCAllocLowering::new(0x600000, 0x601000, 0x500000);
        let seq = alloc.generate_bump_alloc(64, DW_REG_RAX as u16, DW_REG_RCX as u16);
        assert!(seq.len() > 20);
        // Should contain cmp instruction (0x3B)
        assert!(seq.contains(&0x3B));
    }

    #[test]
    fn test_free_list_alloc() {
        let alloc = X86GCAllocLowering::new(0x600000, 0x601000, 0x500000);
        let seq = alloc.generate_free_list_alloc(3, DW_REG_RAX as u16);
        assert!(seq.len() > 5);
        // Should contain test instruction
        assert!(seq.contains(&0x85));
    }

    #[test]
    fn test_collector_config_default() {
        let config = X86GCCollectorConfig::default();
        assert_eq!(config.algorithm, X86GCCollectionAlgorithm::MarkSweep);
        assert_eq!(config.nursery_size, 4 * 1024 * 1024);
        assert_eq!(config.max_pause_ms, 10);
    }

    #[test]
    fn test_frame_registry_register_and_lookup() {
        let mut registry = X86GCFrameRegistry::new();
        let desc = X86GCFrameDescriptor {
            return_address: 0x401050,
            frame_size: 64,
            stack_roots: vec![-8, -16],
            register_roots: vec![DW_REG_RBX as u16],
            has_frame_pointer: true,
            uses_red_zone: false,
        };
        registry.register(desc.clone());

        let found = registry.lookup(0x401050);
        assert!(found.is_some());
        assert_eq!(found.unwrap().frame_size, 64);
        assert_eq!(found.unwrap().stack_roots.len(), 2);
    }

    #[test]
    fn test_frame_registry_find_containing() {
        let mut registry = X86GCFrameRegistry::new();
        registry.register(X86GCFrameDescriptor {
            return_address: 0x401000,
            frame_size: 48,
            stack_roots: vec![-8],
            register_roots: vec![],
            has_frame_pointer: true,
            uses_red_zone: false,
        });
        registry.register(X86GCFrameDescriptor {
            return_address: 0x402000,
            frame_size: 96,
            stack_roots: vec![-8, -16, -24],
            register_roots: vec![DW_REG_R12 as u16],
            has_frame_pointer: true,
            uses_red_zone: false,
        });

        // PC between frames should find the first frame
        let found = registry.find_containing_frame(0x401500);
        assert!(found.is_some());
        assert_eq!(found.unwrap().return_address, 0x401000);

        // PC at exact address should find that frame
        let found2 = registry.find_containing_frame(0x402000);
        assert!(found2.is_some());
        assert_eq!(found2.unwrap().frame_size, 96);
    }

    #[test]
    fn test_back_edge_poll_inserter() {
        let mut inserter = X86GCBackEdgePollInserter::new(0x7FFFFFFFFFF000, 100);

        // Advance 50 instructions: no poll needed
        assert!(!inserter.advance(50));

        // Advance another 51: poll needed
        assert!(inserter.advance(51));
        assert!(inserter.poll_inserted);

        let poll_seq = inserter.generate_poll();
        assert!(poll_seq.len() > 5);
    }

    #[test]
    fn test_alloc_kind_discriminants() {
        assert_ne!(
            X86GCAllocKind::BumpPointer as u8,
            X86GCAllocKind::FreeList as u8
        );
        assert_ne!(
            X86GCAllocKind::TLAB as u8,
            X86GCAllocKind::LargeObject as u8
        );
    }
}