llvm-native-core-ext 0.1.0

//! LLVM Garbage Collection Infrastructure — Extended Strategies
//!
//! This module provides advanced GC algorithms and infrastructure beyond
//! the basic GC strategies defined in codegen_gc.rs.
//!
//! ## Coverage
//!
//! - **Immix GC**: opportunistic defragmentation, line/block marking
//! - **Mark-Sweep**: full mark phase with worklist, sweep phase with free list
//! - **Copying GC**: Cheney semispace, breadth-first copying
//! - **Generational GC**: nursery, minor/major collections, remembered sets
//! - **Reference Counting**: strong/weak references, cycle detection
//! - **ZGC-style**: colored pointers, load barriers, concurrent marking
//! - **Shenandoah-style**: Brooks pointers, concurrent evacuation
//! - **GC Barriers**: ReadBarrier, WriteBarrier, CASBarrier, AtomicRMWBarrier
//! - **Allocation Fast Paths**: bump pointer, free list, thread-local allocation
//!   buffer (TLAB)
//! - **GC Safepoint Placement**: loop backedge, function entry, call sites
//!
//! Clean-room behavioural reconstruction from published GC research papers,
//! the LLVM GC documentation, and the OpenJDK/Go/V8 GC implementation
//! descriptions. No LLVM C++ source code is consulted.

use std::collections::{HashMap, HashSet, VecDeque};

// ============================================================================
// Immix GC
// ============================================================================

/// Immix is a mark-region garbage collector that combines the benefits of
/// mark-sweep (no copying overhead) and copying collectors (defragmentation).
/// Memory is organized into blocks (e.g., 32 KB) subdivided into lines
/// (e.g., 128 bytes). Objects are allocated into contiguous lines within a
/// block. During collection, live objects are opportunistically moved to
/// defragment, but only when a block is sufficiently fragmented.

/// Immix block size in bytes (32 KB).
pub const IMMIX_BLOCK_SIZE: usize = 32768;

/// Immix line size in bytes (128 bytes).
pub const IMMIX_LINE_SIZE: usize = 128;

/// Number of lines per block.
pub const IMMIX_LINES_PER_BLOCK: usize = IMMIX_BLOCK_SIZE / IMMIX_LINE_SIZE;

/// An Immix block with line marking and allocation state.
#[derive(Debug, Clone)]
pub struct ImmixBlock {
    /// Block ID.
    pub id: u64,
    /// Base address of the block.
    pub base: usize,
    /// Mark bits per line (one bit per line).
    pub line_mark_bits: u128,
    /// Allocation cursor within the block.
    pub cursor: usize,
    /// Limit of the block.
    pub limit: usize,
    /// Defragmentation state: holes per line.
    pub hole_count: u8,
    /// Whether this block is completely free.
    pub is_free: bool,
    /// Recycled lines (lines that were evacuated).
    pub recycled_lines: HashSet<u8>,
}

impl ImmixBlock {
    pub fn new(id: u64, base: usize) -> Self {
        ImmixBlock {
            id,
            base,
            line_mark_bits: 0,
            cursor: base,
            limit: base + IMMIX_BLOCK_SIZE,
            hole_count: 0,
            is_free: true,
            recycled_lines: HashSet::new(),
        }
    }

    /// Try to allocate `size` bytes in this block at bump-pointer speed.
    pub fn bump_allocate(&mut self, size: usize, alignment: usize) -> Option<usize> {
        let aligned = (self.cursor + alignment - 1) & !(alignment - 1);
        if aligned + size <= self.limit {
            let addr = aligned;
            self.cursor = aligned + size;
            self.is_free = false;
            let line_start = (addr - self.base) / IMMIX_LINE_SIZE;
            let line_end = (aligned + size - self.base - 1) / IMMIX_LINE_SIZE;
            for line in line_start..=line_end {
                self.mark_line(line as u8);
            }
            Some(addr)
        } else {
            None
        }
    }

    /// Mark a line as in-use.
    pub fn mark_line(&mut self, line: u8) {
        if line < 64 {
            self.line_mark_bits |= 1u128 << line;
        }
    }

    /// Check if a line is marked.
    pub fn is_line_marked(&self, line: u8) -> bool {
        line < 64 && (self.line_mark_bits & (1u128 << line)) != 0
    }

    /// Count number of live lines.
    pub fn live_lines(&self) -> u32 {
        self.line_mark_bits.count_ones()
    }

    /// Determine if this block should be defragmented.
    pub fn should_defrag(&self, fragmentation_threshold: f64) -> bool {
        let live = self.live_lines() as f64;
        let total = IMMIX_LINES_PER_BLOCK as f64;
        if total == 0.0 {
            return false;
        }
        (live / total) > fragmentation_threshold && self.hole_count > 0
    }
}

/// Immix GC state.
#[derive(Debug)]
pub struct ImmixGC {
    /// All blocks managed by this collector.
    pub blocks: Vec<ImmixBlock>,
    /// Free block indices (recycled empty blocks).
    pub free_blocks: Vec<usize>,
    /// Current allocation block index.
    pub alloc_block: usize,
    /// Fragmentation threshold for triggering defragmentation.
    pub fragmentation_threshold: f64,
    /// Statistics.
    pub bytes_allocated: u64,
    pub bytes_copied: u64,
    pub collections: u64,
}

impl ImmixGC {
    pub fn new(initial_heap: usize) -> Self {
        let num_blocks = (initial_heap + IMMIX_BLOCK_SIZE - 1) / IMMIX_BLOCK_SIZE;
        let mut blocks = Vec::with_capacity(num_blocks);
        for i in 0..num_blocks {
            blocks.push(ImmixBlock::new(i as u64, i * IMMIX_BLOCK_SIZE));
        }
        ImmixGC {
            blocks,
            free_blocks: Vec::new(),
            alloc_block: 0,
            fragmentation_threshold: 0.75,
            bytes_allocated: 0,
            bytes_copied: 0,
            collections: 0,
        }
    }

    /// Fast-path bump pointer allocation.
    pub fn allocate(&mut self, size: usize, alignment: usize) -> Option<usize> {
        // Try current allocation block
        if let Some(addr) = self.blocks[self.alloc_block].bump_allocate(size, alignment) {
            self.bytes_allocated += size as u64;
            return Some(addr);
        }
        // Try recycled blocks
        for &idx in &self.free_blocks {
            if let Some(addr) = self.blocks[idx].bump_allocate(size, alignment) {
                self.alloc_block = idx;
                self.bytes_allocated += size as u64;
                return Some(addr);
            }
        }
        None
    }

    /// Trigger a collection cycle.
    pub fn collect(&mut self, _mark_queue: &mut HashSet<usize>) {
        self.collections += 1;
        // Mark phase: all live objects in mark_queue
        for block in &mut self.blocks {
            block.line_mark_bits = 0;
            block.hole_count = 0;
        }
        // Sweep/defrag phase
        for i in 0..self.blocks.len() {
            let block = &mut self.blocks[i];
            if block.live_lines() == 0 {
                block.is_free = true;
                block.cursor = block.base;
                self.free_blocks.push(i);
            } else if block.should_defrag(self.fragmentation_threshold) {
                self.defrag_block(i);
            }
        }
    }

    /// Opportunistically defragment a single block.
    fn defrag_block(&mut self, block_idx: usize) {
        let block = &mut self.blocks[block_idx];
        // Copy live lines to the start of the block
        let mut target = block.base;
        for line in 0..IMMIX_LINES_PER_BLOCK {
            if block.is_line_marked(line as u8) {
                let src = block.base + line * IMMIX_LINE_SIZE;
                let size = IMMIX_LINE_SIZE;
                // In a real implementation, we'd memmove here
                self.bytes_copied += size as u64;
                // Update target
                target += size;
            }
        }
        // Reset allocation cursor to after the compacted region
        block.cursor = target;
        block.hole_count = 0;
    }
}

// ============================================================================
// Mark-Sweep GC
// ============================================================================

/// A mark-sweep garbage collector maintains a free list and uses a mark
/// bit per object. The mark phase traverses all reachable objects from
/// roots using a worklist. The sweep phase reclaims unmarked objects
/// and adds them to the free list.

/// A free list entry.
#[derive(Debug, Clone, Copy)]
pub struct FreeListEntry {
    pub addr: usize,
    pub size: usize,
}

/// Mark-sweep GC state.
#[derive(Debug)]
pub struct MarkSweepGC {
    /// Heap base address.
    pub heap_base: usize,
    /// Heap size in bytes.
    pub heap_size: usize,
    /// Free list entries sorted by address.
    pub free_list: Vec<FreeListEntry>,
    /// Mark bits (bitmap).
    pub mark_bits: Vec<u8>,
    /// Number of heap objects (approximate).
    pub object_count: u64,
    /// Statistics.
    pub bytes_allocated: u64,
    pub bytes_freed: u64,
    pub collections: u64,
}

impl MarkSweepGC {
    pub fn new(heap_base: usize, heap_size: usize) -> Self {
        let mark_bytes = (heap_size + 7) / 8;
        MarkSweepGC {
            heap_base,
            heap_size,
            free_list: vec![FreeListEntry {
                addr: heap_base,
                size: heap_size,
            }],
            mark_bits: vec![0; mark_bytes],
            object_count: 0,
            bytes_allocated: 0,
            bytes_freed: 0,
            collections: 0,
        }
    }

    /// Allocate from the free list (first-fit).
    pub fn allocate(&mut self, size: usize) -> Option<usize> {
        for i in 0..self.free_list.len() {
            if self.free_list[i].size >= size {
                let entry = self.free_list[i];
                let addr = entry.addr;
                if entry.size > size {
                    self.free_list[i] = FreeListEntry {
                        addr: entry.addr + size,
                        size: entry.size - size,
                    };
                } else {
                    self.free_list.remove(i);
                }
                self.set_mark(addr, true);
                self.object_count += 1;
                self.bytes_allocated += size as u64;
                return Some(addr);
            }
        }
        None
    }

    /// Set the mark bit for a given address.
    pub fn set_mark(&mut self, addr: usize, marked: bool) {
        if addr >= self.heap_base && addr < self.heap_base + self.heap_size {
            let offset = addr - self.heap_base;
            let byte_idx = offset / 8;
            let bit_idx = offset % 8;
            if marked {
                self.mark_bits[byte_idx] |= 1 << bit_idx;
            } else {
                self.mark_bits[byte_idx] &= !(1 << bit_idx);
            }
        }
    }

    /// Check if an address is marked.
    pub fn is_marked(&self, addr: usize) -> bool {
        if addr >= self.heap_base && addr < self.heap_base + self.heap_size {
            let offset = addr - self.heap_base;
            let byte_idx = offset / 8;
            let bit_idx = offset % 8;
            (self.mark_bits[byte_idx] & (1 << bit_idx)) != 0
        } else {
            false
        }
    }

    /// Full mark phase using a worklist.
    pub fn mark_phase(&mut self, roots: &[usize], edges: &dyn Fn(usize) -> Vec<usize>) {
        // Clear all mark bits
        for b in &mut self.mark_bits {
            *b = 0;
        }
        let mut worklist: VecDeque<usize> = VecDeque::new();
        for &root in roots {
            self.set_mark(root, true);
            worklist.push_back(root);
        }
        // Iterative mark using worklist
        while let Some(obj) = worklist.pop_front() {
            for child in edges(obj) {
                if !self.is_marked(child) {
                    self.set_mark(child, true);
                    worklist.push_back(child);
                }
            }
        }
    }

    /// Sweep phase: add unmarked objects to free list.
    pub fn sweep_phase(&mut self) {
        self.free_list.clear();
        let mut current = self.heap_base;
        let end = self.heap_base + self.heap_size;
        let mut free_start = current;
        let mut in_free = false;
        while current < end {
            if self.is_marked(current) {
                if in_free {
                    let size = current - free_start;
                    if size > 0 {
                        self.free_list.push(FreeListEntry {
                            addr: free_start,
                            size,
                        });
                        self.bytes_freed += size as u64;
                    }
                    in_free = false;
                }
            } else {
                if !in_free {
                    free_start = current;
                    in_free = true;
                }
            }
            current += 8; // step by minimum object size
        }
        if in_free {
            let size = current - free_start;
            if size > 0 {
                self.free_list.push(FreeListEntry {
                    addr: free_start,
                    size,
                });
            }
        }
        self.collections += 1;
    }

    /// Full collection cycle.
    pub fn collect(&mut self, roots: &[usize], edges: &dyn Fn(usize) -> Vec<usize>) {
        self.mark_phase(roots, edges);
        self.sweep_phase();
    }
}

// ============================================================================
// Copying GC — Cheney Semispace
// ============================================================================

/// A Cheney semispace copying collector divides the heap into two equal
/// semispaces: fromspace and tospace. During collection, live objects are
/// copied from fromspace to tospace using a breadth-first algorithm (scan
/// pointer and free pointer). After copying, the semispaces are swapped.

#[derive(Debug)]
pub struct CheneyGC {
    /// Size of each semispace in bytes.
    pub semispace_size: usize,
    /// Base of fromspace.
    pub fromspace: usize,
    /// Base of tospace.
    pub tospace: usize,
    /// Current allocation pointer in tospace (free pointer).
    pub free: usize,
    /// Scan pointer for breadth-first copying.
    pub scan: usize,
    /// Whether we are in the middle of a collection.
    pub collecting: bool,
    /// Statistics.
    pub bytes_allocated: u64,
    pub bytes_copied: u64,
    pub collections: u64,
}

impl CheneyGC {
    pub fn new(fromspace: usize, semispace_size: usize) -> Self {
        let tospace = fromspace + semispace_size;
        CheneyGC {
            semispace_size,
            fromspace,
            tospace,
            free: tospace,
            scan: tospace,
            collecting: false,
            bytes_allocated: 0,
            bytes_copied: 0,
            collections: 0,
        }
    }

    /// Fast-path bump-pointer allocation in tospace.
    pub fn allocate(&mut self, size: usize) -> Option<usize> {
        let addr = self.free;
        if addr + size <= self.tospace + self.semispace_size {
            self.free += size;
            self.bytes_allocated += size as u64;
            Some(addr)
        } else {
            None
        }
    }

    /// Forward a pointer during copying collection.
    pub fn forward(&mut self, ptr: usize, edges: &dyn Fn(usize) -> Vec<usize>) -> usize {
        if ptr >= self.fromspace && ptr < self.fromspace + self.semispace_size {
            // Object in fromspace — copy it
            let obj_size = 64; // simplified: assume fixed size
            let new_addr = self.free;
            // Copy data
            self.free += obj_size;
            self.bytes_copied += obj_size as u64;
            // Write forwarding pointer at old location
            // (in real impl, we'd store new_addr at ptr)
            new_addr
        } else {
            ptr // already in tospace or not a heap pointer
        }
    }

    /// Breadth-first copying collection (Cheney algorithm).
    pub fn collect(&mut self, roots: &mut [usize], edges: &dyn Fn(usize) -> Vec<usize>) {
        self.collecting = true;
        self.free = self.tospace;
        self.scan = self.tospace;

        // Forward all roots
        for root in roots.iter_mut() {
            *root = self.forward(*root, edges);
        }

        // Breadth-first scan: process objects from scan to free
        while self.scan < self.free {
            let obj = self.scan;
            self.scan += 64; // simplified: advance past object header
            for child in edges(obj) {
                let fwd = self.forward(child, edges);
                // Update reference in object
            }
        }

        // Swap semispaces
        std::mem::swap(&mut self.fromspace, &mut self.tospace);
        self.tospace = self.fromspace + self.semispace_size;
        self.free = self.tospace;
        self.scan = self.tospace;
        self.collecting = false;
        self.collections += 1;
    }
}

// ============================================================================
// Generational GC
// ============================================================================

/// A generational garbage collector divides the heap into young (nursery)
/// and old generations. Minor collections only scan the nursery, using a
/// remembered set to track old→young pointers. Major collections scan the
/// entire heap.

#[derive(Debug)]
pub struct GenerationalGC {
    /// Nursery (young generation) size.
    pub nursery_size: usize,
    /// Nursery base address.
    pub nursery_base: usize,
    /// Nursery allocation pointer (bump pointer).
    pub nursery_free: usize,
    /// Remembered set: addresses of old objects that reference young objects.
    pub remembered_set: HashSet<usize>,
    /// Old generation — managed by a mark-sweep collector.
    pub old_gc: MarkSweepGC,
    /// Minor collection count.
    pub minor_collections: u64,
    /// Major collection count.
    pub major_collections: u64,
    /// Promote threshold: objects surviving N minor collections get promoted.
    pub promote_threshold: u8,
    /// Age of objects in nursery.
    pub object_ages: HashMap<usize, u8>,
}

impl GenerationalGC {
    pub fn new(nursery_base: usize, nursery_size: usize, old_base: usize, old_size: usize) -> Self {
        GenerationalGC {
            nursery_size,
            nursery_base,
            nursery_free: nursery_base,
            remembered_set: HashSet::new(),
            old_gc: MarkSweepGC::new(old_base, old_size),
            minor_collections: 0,
            major_collections: 0,
            promote_threshold: 3,
            object_ages: HashMap::new(),
        }
    }

    /// Fast-path nursery allocation.
    pub fn nursery_allocate(&mut self, size: usize) -> Option<usize> {
        let addr = self.nursery_free;
        if addr + size <= self.nursery_base + self.nursery_size {
            self.nursery_free += size;
            self.object_ages.insert(addr, 0);
            Some(addr)
        } else {
            None
        }
    }

    /// Minor collection: evacuate live nursery objects.
    pub fn minor_collect(&mut self, roots: &[usize], edges: &dyn Fn(usize) -> Vec<usize>) {
        self.minor_collections += 1;
        // Scan nursery roots and remembered set
        let mut survivors: Vec<usize> = Vec::new();
        for &root in roots {
            if root >= self.nursery_base && root < self.nursery_base + self.nursery_size {
                survivors.push(root);
            }
        }
        for &rs_entry in &self.remembered_set {
            // Any young objects reachable from rs_entry are live
            for child in edges(rs_entry) {
                if child >= self.nursery_base && child < self.nursery_base + self.nursery_size {
                    survivors.push(child);
                }
            }
        }
        // Promote survivors that exceed the age threshold
        for obj in &survivors {
            let age = self.object_ages.entry(*obj).or_insert(0);
            *age += 1;
            if *age >= self.promote_threshold {
                // Promote to old generation
                let promoted = self.old_gc.allocate(64);
                self.object_ages.remove(obj);
            }
        }
        // Reset nursery
        self.nursery_free = self.nursery_base;
        self.object_ages.clear();
    }

    /// Major collection: full heap collection.
    pub fn major_collect(&mut self, roots: &[usize], edges: &dyn Fn(usize) -> Vec<usize>) {
        self.major_collections += 1;
        self.old_gc.collect(roots, edges);
        self.remembered_set.clear();
    }

    /// Record an old→young reference.
    pub fn record_write(&mut self, old_obj: usize) {
        self.remembered_set.insert(old_obj);
    }
}

// ============================================================================
// Reference Counting GC
// ============================================================================

/// Reference counting garbage collection maintains a count of incoming
/// references for each object. When the count drops to zero, the object
/// is deallocated. Supports strong and weak references with optional
/// cycle detection.

#[derive(Debug, Clone)]
pub struct RefCountedObject {
    pub addr: usize,
    pub size: usize,
    pub strong_count: u64,
    pub weak_count: u64,
    pub is_collected: bool,
    pub color: RCColor,
}

#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub enum RCColor {
    Black,  // definitely live
    Gray,   // possibly in a cycle
    White,  // possibly garbage
    Purple, // possible root of a cycle
}

#[derive(Debug)]
pub struct ReferenceCountingGC {
    pub objects: HashMap<usize, RefCountedObject>,
    pub cycle_buffer: Vec<usize>,
    pub stats_cycles_detected: u64,
    pub stats_objects_collected: u64,
    pub stats_bytes_freed: u64,
}

impl ReferenceCountingGC {
    pub fn new() -> Self {
        ReferenceCountingGC {
            objects: HashMap::new(),
            cycle_buffer: Vec::new(),
            stats_cycles_detected: 0,
            stats_objects_collected: 0,
            stats_bytes_freed: 0,
        }
    }

    /// Increment reference count.
    pub fn inc_ref(&mut self, addr: usize) {
        if let Some(obj) = self.objects.get_mut(&addr) {
            obj.strong_count += 1;
            obj.color = RCColor::Black;
        }
    }

    /// Decrement reference count; if zero, schedule for deallocation.
    pub fn dec_ref(&mut self, addr: usize) -> bool {
        if let Some(obj) = self.objects.get_mut(&addr) {
            if obj.strong_count > 0 {
                obj.strong_count -= 1;
            }
            if obj.strong_count == 0 {
                obj.is_collected = true;
                self.stats_objects_collected += 1;
                self.stats_bytes_freed += obj.size as u64;
                // In a real impl, decrement refcounts of all children
                return true;
            } else if obj.color != RCColor::Purple {
                obj.color = RCColor::Purple;
                self.cycle_buffer.push(addr);
            }
        }
        false
    }

    /// Cycle detection: scan the cycle buffer for garbage cycles.
    pub fn detect_cycles(&mut self, edges: &dyn Fn(usize) -> Vec<usize>) {
        let buffer: Vec<usize> = self.cycle_buffer.drain(..).collect();
        for obj_addr in &buffer {
            let is_purple = self
                .objects
                .get(obj_addr)
                .map(|obj| obj.color == RCColor::Purple)
                .unwrap_or(false);
            if is_purple {
                // Mark gray: all reachable nodes
                self.mark_gray(*obj_addr, edges);
                // Scan: decrement refcounts from internal references
                self.scan(*obj_addr, edges);
                // Collect white: nodes with refcount 0 after scan
                self.collect_white(*obj_addr, edges);
            }
        }
        self.stats_cycles_detected += 1;
    }

    fn mark_gray(&mut self, obj_addr: usize, edges: &dyn Fn(usize) -> Vec<usize>) {
        if let Some(obj) = self.objects.get_mut(&obj_addr) {
            if obj.color != RCColor::Gray {
                obj.color = RCColor::Gray;
                for child in edges(obj_addr) {
                    if let Some(child_obj) = self.objects.get_mut(&child) {
                        child_obj.strong_count = child_obj.strong_count.saturating_sub(1);
                    }
                    self.mark_gray(child, edges);
                }
            }
        }
    }

    fn scan(&mut self, obj_addr: usize, edges: &dyn Fn(usize) -> Vec<usize>) {
        if let Some(obj) = self.objects.get(&obj_addr) {
            if obj.color == RCColor::Gray {
                if obj.strong_count > 0 {
                    self.scan_black(obj_addr, edges);
                } else {
                    if let Some(obj_mut) = self.objects.get_mut(&obj_addr) {
                        obj_mut.color = RCColor::White;
                    }
                    for child in edges(obj_addr) {
                        self.scan(child, edges);
                    }
                }
            }
        }
    }

    fn scan_black(&mut self, obj_addr: usize, edges: &dyn Fn(usize) -> Vec<usize>) {
        if let Some(obj) = self.objects.get_mut(&obj_addr) {
            obj.color = RCColor::Black;
            for child in edges(obj_addr) {
                if let Some(child_obj) = self.objects.get_mut(&child) {
                    child_obj.strong_count += 1;
                }
                if let Some(child_obj) = self.objects.get(&child) {
                    if child_obj.color != RCColor::Black {
                        self.scan_black(child, edges);
                    }
                }
            }
        }
    }

    fn collect_white(&mut self, obj_addr: usize, _edges: &dyn Fn(usize) -> Vec<usize>) {
        if let Some(obj) = self.objects.get_mut(&obj_addr) {
            if obj.color == RCColor::White {
                obj.color = RCColor::Black;
                obj.is_collected = true;
                self.stats_objects_collected += 1;
                self.stats_bytes_freed += obj.size as u64;
                // In a real impl, decrement children's refcounts
            }
        }
    }
}

// ============================================================================
// ZGC-Style Colored Pointers
// ============================================================================

/// ZGC (Z Garbage Collector) uses colored pointers to encode GC state
/// directly in object references. On 64-bit platforms, unused virtual
/// address bits are repurposed as metadata:
///   - Finalizable (bit 44)
///   - Remapped (bit 45)
///   - Marked0 / Marked1 (bits 46-47, toggling between collections)

/// Color bits for ZGC-style colored pointers.
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub struct ZGCColor {
    pub finalizable: bool,
    pub remapped: bool,
    pub marked0: bool,
    pub marked1: bool,
}

impl ZGCColor {
    pub fn to_bits(&self) -> u64 {
        let mut bits: u64 = 0;
        if self.finalizable {
            bits |= 1 << 44;
        }
        if self.remapped {
            bits |= 1 << 45;
        }
        if self.marked0 {
            bits |= 1 << 46;
        }
        if self.marked1 {
            bits |= 1 << 47;
        }
        bits
    }

    pub fn from_pointer(ptr: u64) -> Self {
        ZGCColor {
            finalizable: (ptr & (1u64 << 44)) != 0,
            remapped: (ptr & (1u64 << 45)) != 0,
            marked0: (ptr & (1u64 << 46)) != 0,
            marked1: (ptr & (1u64 << 47)) != 0,
        }
    }

    /// Strip color bits to get the real address.
    pub fn strip(ptr: u64) -> u64 {
        ptr & 0x0000_0FFF_FFFF_FFFF // 44-bit address
    }
}

/// ZGC load barrier: when loading a reference, check if the color
/// indicates the object needs relocation/remapping.
#[derive(Debug)]
pub struct ZGCLoadBarrier {
    pub good_color: u64,
    pub enable_relocation: bool,
    pub barrier_count: u64,
}

impl ZGCLoadBarrier {
    pub fn new(good_color: u64) -> Self {
        ZGCLoadBarrier {
            good_color,
            enable_relocation: true,
            barrier_count: 0,
        }
    }

    /// Apply the load barrier: fix up the pointer if colored incorrectly.
    pub fn barrier(&mut self, ptr: u64) -> u64 {
        self.barrier_count += 1;
        let color_bits = ptr >> 44;
        if color_bits == self.good_color >> 44 {
            ZGCColor::strip(ptr) // Fast path: color is good
        } else {
            // Slow path: fix up the color
            let addr = ZGCColor::strip(ptr);
            if self.enable_relocation {
                // Relocate object and return forwarding pointer
                addr
            } else {
                // Remap: install forwarding pointer
                addr
            }
        }
    }
}

/// ZGC concurrent marking state.
#[derive(Debug)]
pub struct ZGCConcurrentMarker {
    pub is_marking: bool,
    pub marked_objects: HashSet<usize>,
    pub pending_objects: VecDeque<usize>,
    pub mark_stack: Vec<usize>,
}

impl ZGCConcurrentMarker {
    pub fn new() -> Self {
        ZGCConcurrentMarker {
            is_marking: false,
            marked_objects: HashSet::new(),
            pending_objects: VecDeque::new(),
            mark_stack: Vec::new(),
        }
    }

    /// Start a concurrent mark cycle.
    pub fn start_mark(&mut self, roots: &[usize]) {
        self.is_marking = true;
        self.marked_objects.clear();
        for &root in roots {
            self.pending_objects.push_back(root);
        }
    }

    /// Process a batch of pending objects (concurrent marking increment).
    pub fn mark_batch(&mut self, batch_size: usize, edges: &dyn Fn(usize) -> Vec<usize>) -> bool {
        let mut processed = 0;
        while processed < batch_size && !self.pending_objects.is_empty() {
            if let Some(obj) = self.pending_objects.pop_front() {
                if self.marked_objects.insert(obj) {
                    for child in edges(obj) {
                        if !self.marked_objects.contains(&child) {
                            self.pending_objects.push_back(child);
                        }
                    }
                }
                processed += 1;
            }
        }
        self.is_marking = !self.pending_objects.is_empty();
        !self.is_marking
    }
}

// ============================================================================
// Shenandoah-Style Brooks Pointers
// ============================================================================

/// Shenandoah GC uses Brooks-style forwarding pointers: each object has
/// a forwarding pointer at a known offset. During concurrent evacuation,
/// the object is copied to a new location and the forwarding pointer is
/// updated. All accesses go through the forwarding pointer.

/// A Shenandoah object header with Brooks forwarding pointer.
#[derive(Debug, Clone)]
pub struct ShenandoahObject {
    /// Forwarding pointer (points to itself when not forwarded).
    pub forwarding_ptr: usize,
    /// Object size.
    pub size: usize,
    /// Mark word.
    pub mark_word: u64,
    /// Whether this object is in the collection set (to be evacuated).
    pub in_cset: bool,
}

/// Shenandoah GC state.
#[derive(Debug)]
pub struct ShenandoahGC {
    /// All managed objects.
    pub objects: HashMap<usize, ShenandoahObject>,
    /// Collection set (regions to evacuate).
    pub collection_set: HashSet<usize>,
    /// Concurrent evacuation thread state.
    pub evacuating: bool,
    /// Statistics.
    pub bytes_evacuated: u64,
    pub collections: u64,
}

impl ShenandoahGC {
    pub fn new() -> Self {
        ShenandoahGC {
            objects: HashMap::new(),
            collection_set: HashSet::new(),
            evacuating: false,
            bytes_evacuated: 0,
            collections: 0,
        }
    }

    /// Brooks pointer load: always read through the forwarding pointer.
    pub fn load_reference(&self, ptr: usize) -> Option<usize> {
        self.objects.get(&ptr).map(|obj| {
            if obj.forwarding_ptr == ptr {
                ptr // self-forwarding: not evacuated
            } else {
                obj.forwarding_ptr // forwarded
            }
        })
    }

    /// Update a reference to point to the forwarding address.
    pub fn update_reference(&self, ptr: usize) -> usize {
        if let Some(obj) = self.objects.get(&ptr) {
            obj.forwarding_ptr
        } else {
            ptr
        }
    }

    /// Begin concurrent evacuation of the collection set.
    pub fn start_evacuation(&mut self, regions: Vec<usize>) {
        self.collection_set.clear();
        for r in regions {
            self.collection_set.insert(r);
        }
        self.evacuating = true;
        self.collections += 1;
    }

    /// Evacuate a single object to a new location.
    pub fn evacuate_object(&mut self, old_addr: usize, new_addr: usize, size: usize) {
        if self.collection_set.contains(&old_addr) {
            self.objects.insert(
                new_addr,
                ShenandoahObject {
                    forwarding_ptr: new_addr,
                    size,
                    mark_word: 0,
                    in_cset: false,
                },
            );
            if let Some(obj) = self.objects.get_mut(&old_addr) {
                obj.forwarding_ptr = new_addr;
                obj.in_cset = false;
            }
            self.bytes_evacuated += size as u64;
        }
    }
}

// ============================================================================
// GC Barriers
// ============================================================================

/// Read barrier: intercepts every heap reference read to check/update
/// the object state (used by ZGC, Shenandoah).
#[derive(Debug, Clone)]
pub struct ReadBarrier {
    pub barrier_type: ReadBarrierType,
    pub calls: u64,
}

#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub enum ReadBarrierType {
    ZGCLoadBarrier,
    ShenandoahLoadRefBarrier,
    NullCheck,
}

impl ReadBarrier {
    pub fn new(ty: ReadBarrierType) -> Self {
        ReadBarrier {
            barrier_type: ty,
            calls: 0,
        }
    }

    /// Apply the read barrier.
    pub fn apply(&mut self, ptr: usize, gc_state: &ShenandoahGC) -> usize {
        self.calls += 1;
        match self.barrier_type {
            ReadBarrierType::ShenandoahLoadRefBarrier => gc_state.update_reference(ptr),
            ReadBarrierType::ZGCLoadBarrier => {
                // ZGC: check color bits and potentially fix up
                ptr
            }
            ReadBarrierType::NullCheck => {
                if ptr == 0 {
                    0
                } else {
                    ptr
                }
            }
        }
    }
}

/// Write barrier: intercepts every heap reference write to maintain
/// GC invariants (card marking, remembered sets, SATB).
#[derive(Debug, Clone)]
pub struct WriteBarrier {
    pub barrier_type: WriteBarrierType,
    pub calls: u64,
}

#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub enum WriteBarrierType {
    CardMarking,
    SATB,          // Snapshot-At-The-Beginning (G1)
    RememberedSet, // Generational remembered set
    Yuasa,         // Yuasa deletion barrier
    Dijkstra,      // Dijkstra insertion barrier
    Steele,        // Steele insertion barrier
}

impl WriteBarrier {
    pub fn new(ty: WriteBarrierType) -> Self {
        WriteBarrier {
            barrier_type: ty,
            calls: 0,
        }
    }

    /// Apply the write barrier.
    pub fn apply(
        &mut self,
        field_addr: usize,
        new_value: usize,
        card_table: &mut [u8],
        card_size: u32,
    ) {
        self.calls += 1;
        match self.barrier_type {
            WriteBarrierType::CardMarking => {
                let card_idx = field_addr / card_size as usize;
                if card_idx < card_table.len() {
                    card_table[card_idx] = 1;
                }
            }
            WriteBarrierType::SATB => {
                // Snapshot-At-The-Beginning: log the old value before overwriting
                let _old_value = 0; // would be read before store
            }
            WriteBarrierType::RememberedSet => {
                // Record that an old object now points to a young object
            }
            _ => {}
        }
    }
}

/// CAS (Compare-And-Swap) barrier: for atomic updates in GC'd heaps.
#[derive(Debug, Clone)]
pub struct CASBarrier {
    pub calls: u64,
    pub successes: u64,
}

impl CASBarrier {
    pub fn new() -> Self {
        CASBarrier {
            calls: 0,
            successes: 0,
        }
    }

    /// CAS with GC barrier. The barrier ensures that if the CAS
    /// succeeds, the write barrier is applied to the new value.
    pub fn cas_with_barrier(&mut self, ptr: *mut usize, expected: usize, new_val: usize) -> bool {
        self.calls += 1;
        // In a real implementation, this would be an atomic CAS
        unsafe {
            if *ptr == expected {
                *ptr = new_val;
                self.successes += 1;
                true
            } else {
                false
            }
        }
    }
}

/// AtomicRMW (Read-Modify-Write) barrier.
#[derive(Debug, Clone)]
pub struct AtomicRMWBarrier {
    pub calls: u64,
}

impl AtomicRMWBarrier {
    pub fn new() -> Self {
        AtomicRMWBarrier { calls: 0 }
    }

    pub fn apply(&mut self, ptr: *mut usize, op: fn(usize) -> usize) -> usize {
        self.calls += 1;
        unsafe {
            let old = *ptr;
            *ptr = op(old);
            old
        }
    }
}

// ============================================================================
// Allocation Fast Paths
// ============================================================================

/// Bump pointer allocator: the simplest and fastest allocation path.
/// A single pointer is bumped forward. No free list needed. Requires
/// a copying or compacting GC to reclaim space.
#[derive(Debug)]
pub struct BumpPointerAllocator {
    pub base: usize,
    pub cursor: usize,
    pub limit: usize,
    pub bytes_allocated: u64,
}

impl BumpPointerAllocator {
    pub fn new(base: usize, size: usize) -> Self {
        BumpPointerAllocator {
            base,
            cursor: base,
            limit: base + size,
            bytes_allocated: 0,
        }
    }

    /// Try to bump-allocate. Returns Some(addr) on success, None on overflow.
    pub fn allocate(&mut self, size: usize, alignment: usize) -> Option<usize> {
        let aligned = (self.cursor + alignment - 1) & !(alignment - 1);
        if aligned + size <= self.limit {
            let addr = aligned;
            self.cursor = aligned + size;
            self.bytes_allocated += size as u64;
            Some(addr)
        } else {
            None
        }
    }

    /// Reset the allocator (e.g., after a collection).
    pub fn reset(&mut self) {
        self.cursor = self.base;
    }
}

/// Free list allocator: maintains explicit lists of free blocks.
/// Supports coalescing of adjacent free blocks.
#[derive(Debug)]
pub struct FreeListAllocator {
    pub free_lists: HashMap<usize, Vec<usize>>, // size_class -> list of addresses
    pub coalesce: bool,
    pub bytes_allocated: u64,
}

impl FreeListAllocator {
    pub fn new() -> Self {
        FreeListAllocator {
            free_lists: HashMap::new(),
            coalesce: true,
            bytes_allocated: 0,
        }
    }

    /// Add a free block.
    pub fn add_free(&mut self, addr: usize, size: usize) {
        let size_class = self.size_class(size);
        self.free_lists
            .entry(size_class)
            .or_insert_with(Vec::new)
            .push(addr);
    }

    /// Allocate from the appropriate size class.
    pub fn allocate(&mut self, size: usize) -> Option<usize> {
        let size_class = self.size_class(size);
        if let Some(list) = self.free_lists.get_mut(&size_class) {
            if let Some(addr) = list.pop() {
                self.bytes_allocated += size as u64;
                return Some(addr);
            }
        }
        // Try larger size classes
        let classes: Vec<usize> = self.free_lists.keys().cloned().collect();
        for sc in classes {
            if sc >= size_class {
                if let Some(list) = self.free_lists.get_mut(&sc) {
                    if let Some(addr) = list.pop() {
                        let remaining = sc - size;
                        if remaining > 0 && self.coalesce {
                            self.add_free(addr + size, remaining);
                        }
                        self.bytes_allocated += size as u64;
                        return Some(addr);
                    }
                }
            }
        }
        None
    }

    fn size_class(&self, size: usize) -> usize {
        // Round up to the nearest power of 2, minimum 16
        if size <= 16 {
            16
        } else if size <= 32 {
            32
        } else if size <= 64 {
            64
        } else if size <= 128 {
            128
        } else if size <= 256 {
            256
        } else if size <= 512 {
            512
        } else if size <= 1024 {
            1024
        } else {
            (size + 1023) / 1024 * 1024
        }
    }
}

/// Thread-Local Allocation Buffer (TLAB): each thread gets a private
/// allocation buffer to avoid synchronization on the global allocator.
#[derive(Debug)]
pub struct TLAB {
    pub thread_id: u64,
    pub base: usize,
    pub cursor: usize,
    pub limit: usize,
    pub refill_count: u64,
}

impl TLAB {
    pub fn new(thread_id: u64) -> Self {
        TLAB {
            thread_id,
            base: 0,
            cursor: 0,
            limit: 0,
            refill_count: 0,
        }
    }

    /// Try to allocate from local buffer.
    pub fn allocate(&mut self, size: usize) -> Option<usize> {
        if self.cursor + size <= self.limit {
            let addr = self.cursor;
            self.cursor += size;
            Some(addr)
        } else {
            None
        }
    }

    /// Refill the TLAB from the global allocator.
    pub fn refill(&mut self, global: &mut BumpPointerAllocator, tlab_size: usize) -> bool {
        if let Some(base) = global.allocate(tlab_size, 8) {
            self.base = base;
            self.cursor = base;
            self.limit = base + tlab_size;
            self.refill_count += 1;
            true
        } else {
            false
        }
    }

    /// Return remaining space to global allocator (optional).
    pub fn retire(&self) -> usize {
        self.limit.saturating_sub(self.cursor)
    }
}

// ============================================================================
// GC Safepoint Placement
// ============================================================================

/// GC safepoint placement strategies determine where in the generated
/// code safepoint checks are inserted. A safepoint is a point where
/// the thread can be safely paused for garbage collection.

/// Safepoint placement strategy.
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub enum SafepointStrategy {
    /// Place safepoints at every loop backedge.
    LoopBackedge,
    /// Place safepoints at every function entry.
    FunctionEntry,
    /// Place safepoints at every call site.
    CallSite,
    /// Place safepoints at every return instruction.
    FunctionReturn,
    /// All of the above.
    All,
    /// No safepoints (unsafe; for testing).
    None,
}

/// Safepoint placement engine.
#[derive(Debug)]
pub struct SafepointPlacer {
    pub strategy: SafepointStrategy,
    pub placed_safepoints: Vec<SafepointLocation>,
}

/// A placed safepoint.
#[derive(Debug, Clone)]
pub struct SafepointLocation {
    pub kind: SafepointKind,
    pub function_name: String,
    pub basic_block_name: String,
    pub instruction_index: u32,
    pub is_polling: bool,
}

#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub enum SafepointKind {
    LoopBackedge,
    FunctionEntry,
    CallSite,
    FunctionReturn,
}

impl SafepointPlacer {
    pub fn new(strategy: SafepointStrategy) -> Self {
        SafepointPlacer {
            strategy,
            placed_safepoints: Vec::new(),
        }
    }

    /// Determine if a safepoint should be placed at this location.
    pub fn should_place(&self, kind: SafepointKind) -> bool {
        match self.strategy {
            SafepointStrategy::All => true,
            SafepointStrategy::None => false,
            SafepointStrategy::LoopBackedge => matches!(kind, SafepointKind::LoopBackedge),
            SafepointStrategy::FunctionEntry => matches!(kind, SafepointKind::FunctionEntry),
            SafepointStrategy::CallSite => matches!(kind, SafepointKind::CallSite),
            SafepointStrategy::FunctionReturn => matches!(kind, SafepointKind::FunctionReturn),
        }
    }

    /// Record a safepoint placement decision.
    pub fn place(&mut self, kind: SafepointKind, func: &str, bb: &str, idx: u32) {
        if self.should_place(kind) {
            self.placed_safepoints.push(SafepointLocation {
                kind,
                function_name: func.to_string(),
                basic_block_name: bb.to_string(),
                instruction_index: idx,
                is_polling: true,
            });
        }
    }

    /// Emit the safepoint polling sequence as LLVM IR.
    pub fn emit_poll_sequence(&self) -> String {
        r#"
  ; GC Safepoint Poll
  %poll_addr = load volatile i32*, i32** @llvm.gc.poll.addr
  %poll_val = load i32, i32* %poll_addr
  %should_stop = icmp eq i32 %poll_val, 0
  br i1 %should_stop, label %gc_slow_path, label %continue
gc_slow_path:
  call void @llvm.gc.safepoint_poll()
  br label %continue
continue:
"#
        .to_string()
    }
}

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

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

    // --- Immix Tests ---
    #[test]
    fn test_immix_block_allocate() {
        let mut block = ImmixBlock::new(0, 0);
        let addr = block.bump_allocate(64, 8);
        assert!(addr.is_some());
        assert_eq!(addr.unwrap(), 0);
        assert_eq!(block.cursor, 64);
    }

    #[test]
    fn test_immix_block_fragmentation_threshold() {
        let mut block = ImmixBlock::new(0, 0);
        // Mark several lines
        for i in 0..200 {
            block.mark_line(i);
        }
        block.hole_count = 10;
        assert!(block.should_defrag(0.5));
    }

    #[test]
    fn test_immix_gc_allocate() {
        let mut gc = ImmixGC::new(IMMIX_BLOCK_SIZE);
        let addr = gc.allocate(128, 8);
        assert!(addr.is_some());
        assert!(gc.bytes_allocated > 0);
    }

    // --- Mark-Sweep Tests ---
    #[test]
    fn test_mark_sweep_allocate() {
        let mut gc = MarkSweepGC::new(0, 4096);
        let addr = gc.allocate(256);
        assert!(addr.is_some());
        assert_eq!(gc.object_count, 1);
    }

    #[test]
    fn test_mark_sweep_mark_phase() {
        let mut gc = MarkSweepGC::new(0, 4096);
        let a = gc.allocate(64).unwrap();
        let b = gc.allocate(64).unwrap();
        let roots = vec![a];
        let edges = |_obj: usize| vec![b];
        gc.mark_phase(&roots, &edges);
        assert!(gc.is_marked(a));
        assert!(gc.is_marked(b));
    }

    #[test]
    fn test_mark_sweep_sweep_phase() {
        let mut gc = MarkSweepGC::new(0, 4096);
        let _a = gc.allocate(64).unwrap();
        gc.collect(&[], &|_| vec![]);
        assert!(gc.collections > 0);
        assert!(!gc.free_list.is_empty());
    }

    // --- Cheney Copying GC Tests ---
    #[test]
    fn test_cheney_allocate() {
        let mut gc = CheneyGC::new(0, 4096);
        let addr = gc.allocate(64);
        assert!(addr.is_some());
        assert_eq!(addr.unwrap(), 4096); // tospace starts at 4096
    }

    #[test]
    fn test_cheney_collect() {
        let mut gc = CheneyGC::new(0, 4096);
        gc.allocate(64);
        let mut roots = vec![4096usize];
        gc.collect(&mut roots, &|_| vec![]);
        assert!(gc.collections > 0);
    }

    // --- Generational GC Tests ---
    #[test]
    fn test_generational_nursery_allocate() {
        let mut gc = GenerationalGC::new(0, 2048, 4096, 8192);
        let addr = gc.nursery_allocate(64);
        assert!(addr.is_some());
        assert!(gc.object_ages.contains_key(&addr.unwrap()));
    }

    #[test]
    fn test_generational_minor_collect() {
        let mut gc = GenerationalGC::new(0, 2048, 4096, 8192);
        gc.nursery_allocate(64);
        gc.minor_collect(&[], &|_| vec![]);
        assert!(gc.minor_collections > 0);
    }

    #[test]
    fn test_generational_major_collect() {
        let mut gc = GenerationalGC::new(0, 2048, 4096, 8192);
        gc.major_collect(&[], &|_| vec![]);
        assert!(gc.major_collections > 0);
    }

    #[test]
    fn test_generational_remembered_set() {
        let mut gc = GenerationalGC::new(0, 2048, 4096, 8192);
        gc.record_write(5000);
        assert!(gc.remembered_set.contains(&5000));
    }

    // --- Reference Counting Tests ---
    #[test]
    fn test_rc_inc_ref() {
        let mut gc = ReferenceCountingGC::new();
        gc.objects.insert(
            100,
            RefCountedObject {
                addr: 100,
                size: 64,
                strong_count: 0,
                weak_count: 0,
                is_collected: false,
                color: RCColor::Black,
            },
        );
        gc.inc_ref(100);
        assert_eq!(gc.objects[&100].strong_count, 1);
    }

    #[test]
    fn test_rc_dec_ref_to_zero() {
        let mut gc = ReferenceCountingGC::new();
        gc.objects.insert(
            100,
            RefCountedObject {
                addr: 100,
                size: 64,
                strong_count: 1,
                weak_count: 0,
                is_collected: false,
                color: RCColor::Black,
            },
        );
        let collected = gc.dec_ref(100);
        assert!(collected);
        assert!(gc.objects[&100].is_collected);
    }

    #[test]
    fn test_rc_cycle_detection() {
        let mut gc = ReferenceCountingGC::new();
        gc.objects.insert(
            100,
            RefCountedObject {
                addr: 100,
                size: 64,
                strong_count: 2,
                weak_count: 0,
                is_collected: false,
                color: RCColor::Black,
            },
        );
        gc.objects.insert(
            200,
            RefCountedObject {
                addr: 200,
                size: 64,
                strong_count: 2,
                weak_count: 0,
                is_collected: false,
                color: RCColor::Black,
            },
        );
        gc.dec_ref(100);
        gc.dec_ref(200);
        gc.detect_cycles(&|obj| if obj == 100 { vec![200] } else { vec![100] });
        assert!(gc.stats_cycles_detected > 0);
    }

    // --- ZGC Tests ---
    #[test]
    fn test_zgc_color_strip() {
        let ptr = (1u64 << 46) | 0x1234;
        let stripped = ZGCColor::strip(ptr);
        assert_eq!(stripped, 0x1234);
    }

    #[test]
    fn test_zgc_color_from_pointer() {
        let ptr = (1u64 << 46) | (1u64 << 47);
        let color = ZGCColor::from_pointer(ptr);
        assert!(color.marked0);
        assert!(color.marked1);
        assert!(!color.finalizable);
        assert!(!color.remapped);
    }

    #[test]
    fn test_zgc_load_barrier_good_color() {
        let mut barrier = ZGCLoadBarrier::new(0);
        let ptr = 0x1000; // good color (no color bits)
        let result = barrier.barrier(ptr);
        assert_eq!(result, 0x1000);
        assert_eq!(barrier.barrier_count, 1);
    }

    #[test]
    fn test_zgc_concurrent_marker() {
        let mut marker = ZGCConcurrentMarker::new();
        marker.start_mark(&[1, 2, 3]);
        assert!(marker.is_marking);
        let done = marker.mark_batch(10, &|x| vec![x + 1]);
        assert!(done || !marker.is_marking);
    }

    // --- Shenandoah Tests ---
    #[test]
    fn test_shenandoah_load_reference() {
        let mut gc = ShenandoahGC::new();
        gc.objects.insert(
            100,
            ShenandoahObject {
                forwarding_ptr: 100,
                size: 64,
                mark_word: 0,
                in_cset: false,
            },
        );
        let loaded = gc.load_reference(100);
        assert_eq!(loaded, Some(100));
    }

    #[test]
    fn test_shenandoah_forwarded_reference() {
        let mut gc = ShenandoahGC::new();
        gc.objects.insert(
            100,
            ShenandoahObject {
                forwarding_ptr: 500,
                size: 64,
                mark_word: 0,
                in_cset: false,
            },
        );
        gc.objects.insert(
            500,
            ShenandoahObject {
                forwarding_ptr: 500,
                size: 64,
                mark_word: 0,
                in_cset: false,
            },
        );
        let loaded = gc.load_reference(100);
        assert_eq!(loaded, Some(500));
    }

    #[test]
    fn test_shenandoah_evacuation() {
        let mut gc = ShenandoahGC::new();
        gc.objects.insert(
            100,
            ShenandoahObject {
                forwarding_ptr: 100,
                size: 64,
                mark_word: 0,
                in_cset: true,
            },
        );
        gc.start_evacuation(vec![100]);
        gc.evacuate_object(100, 200, 64);
        assert_eq!(gc.bytes_evacuated, 64);
        assert_eq!(gc.objects[&100].forwarding_ptr, 200);
    }

    // --- Barrier Tests ---
    #[test]
    fn test_read_barrier_shenandoah() {
        let mut gc = ShenandoahGC::new();
        gc.objects.insert(
            100,
            ShenandoahObject {
                forwarding_ptr: 100,
                size: 64,
                mark_word: 0,
                in_cset: false,
            },
        );
        let mut rb = ReadBarrier::new(ReadBarrierType::ShenandoahLoadRefBarrier);
        let result = rb.apply(100, &gc);
        assert_eq!(result, 100);
        assert_eq!(rb.calls, 1);
    }

    #[test]
    fn test_write_barrier_card_marking() {
        let mut wb = WriteBarrier::new(WriteBarrierType::CardMarking);
        let mut card_table = vec![0u8; 256];
        wb.apply(4096, 0x42, &mut card_table, 512);
        assert_eq!(card_table[8], 1);
        assert_eq!(wb.calls, 1);
    }

    #[test]
    fn test_cas_barrier() {
        let mut barrier = CASBarrier::new();
        let mut val: usize = 42;
        let result = barrier.cas_with_barrier(&mut val, 42, 99);
        assert!(result);
        assert_eq!(val, 99);
        assert_eq!(barrier.successes, 1);
    }

    #[test]
    fn test_atomic_rmw_barrier() {
        let mut barrier = AtomicRMWBarrier::new();
        let mut val: usize = 10;
        let old = barrier.apply(&mut val, |x| x * 2);
        assert_eq!(old, 10);
        assert_eq!(val, 20);
        assert_eq!(barrier.calls, 1);
    }

    // --- Allocation Fast Path Tests ---
    #[test]
    fn test_bump_pointer_allocate() {
        let mut alloc = BumpPointerAllocator::new(0, 4096);
        let a1 = alloc.allocate(1024, 8);
        let a2 = alloc.allocate(512, 8);
        assert!(a1.is_some());
        assert!(a2.is_some());
        assert!(a2.unwrap() > a1.unwrap());
    }

    #[test]
    fn test_bump_pointer_overflow() {
        let mut alloc = BumpPointerAllocator::new(0, 64);
        let _ = alloc.allocate(32, 8);
        let a2 = alloc.allocate(40, 8);
        assert!(a2.is_none());
    }

    #[test]
    fn test_free_list_allocate() {
        let mut alloc = FreeListAllocator::new();
        alloc.add_free(0, 128);
        alloc.add_free(256, 64);
        let a = alloc.allocate(64);
        assert!(a.is_some());
    }

    #[test]
    fn test_tlab_allocate() {
        let mut tlab = TLAB::new(0);
        // Manually set up the TLAB
        tlab.base = 1000;
        tlab.cursor = 1000;
        tlab.limit = 2000;
        let a = tlab.allocate(128);
        assert_eq!(a, Some(1000));
        assert_eq!(tlab.cursor, 1128);
    }

    #[test]
    fn test_tlab_refill() {
        let mut tlab = TLAB::new(1);
        tlab.base = 0;
        tlab.cursor = 0;
        tlab.limit = 0;
        let mut global = BumpPointerAllocator::new(10000, 4096);
        let ok = tlab.refill(&mut global, 1024);
        assert!(ok);
        assert!(tlab.base >= 10000);
        assert_eq!(tlab.refill_count, 1);
    }

    #[test]
    fn test_tlab_retire() {
        let tlab = TLAB {
            thread_id: 2,
            base: 1000,
            cursor: 1500,
            limit: 2000,
            refill_count: 0,
        };
        let remaining = tlab.retire();
        assert_eq!(remaining, 500);
    }

    // --- Safepoint Tests ---
    #[test]
    fn test_safepoint_loop_backedge() {
        let placer = SafepointPlacer::new(SafepointStrategy::LoopBackedge);
        assert!(placer.should_place(SafepointKind::LoopBackedge));
        assert!(!placer.should_place(SafepointKind::FunctionEntry));
        assert!(!placer.should_place(SafepointKind::CallSite));
    }

    #[test]
    fn test_safepoint_all() {
        let placer = SafepointPlacer::new(SafepointStrategy::All);
        assert!(placer.should_place(SafepointKind::LoopBackedge));
        assert!(placer.should_place(SafepointKind::FunctionEntry));
        assert!(placer.should_place(SafepointKind::CallSite));
        assert!(placer.should_place(SafepointKind::FunctionReturn));
    }

    #[test]
    fn test_safepoint_none() {
        let placer = SafepointPlacer::new(SafepointStrategy::None);
        assert!(!placer.should_place(SafepointKind::LoopBackedge));
    }

    #[test]
    fn test_safepoint_placement() {
        let mut placer = SafepointPlacer::new(SafepointStrategy::LoopBackedge);
        placer.place(SafepointKind::LoopBackedge, "foo", "bb1", 5);
        placer.place(SafepointKind::FunctionEntry, "bar", "entry", 0);
        assert_eq!(placer.placed_safepoints.len(), 1);
        assert_eq!(placer.placed_safepoints[0].function_name, "foo");
    }

    #[test]
    fn test_safepoint_poll_sequence() {
        let placer = SafepointPlacer::new(SafepointStrategy::CallSite);
        let seq = placer.emit_poll_sequence();
        assert!(seq.contains("llvm.gc.poll.addr"));
        assert!(seq.contains("gc_slow_path"));
    }
}