llvm-native-core 0.1.9

//! SelectionDAG Node Types — SDNode, SDValue, SDNodeFlags, SDOpcode.
//! Clean-room behavioral reconstruction. Phase 5 — LLVM.CODEGEN.DAG.1 Court.
//!
//! This module defines the core types used by LLVM's SelectionDAG:
//! - `SDOpcode`: SelectionDAG node opcode enumeration (50+ variants)
//! - `SDValue`: A reference to a specific result of an SDNode (node_id + res_no)
//! - `SDNodeFlags`: Flags propagating fast-math and overflow properties
//! - `SDNode`: The DAG node representing an operation
//! - `SelectionDAG`: Container managing the DAG of nodes
//!
//! @llvm_behavior: In LLVM, SDNodes are allocated on a BumpPtrAllocator
//! and never individually freed. SDValues are lightweight handles (4 bytes).
//! Nodes produce zero or more values; most produce 1, some produce 2
//! (value + chain). The chain enforces memory ordering.

use crate::opcode::ICmpPred;
use crate::types::{Type, TypeKind};
use std::collections::HashMap;

// ============================================================================
// SDNodeFlags — per-node optimization/property flags
// ============================================================================

/// Flags attached to an SDNode that propagate fast-math, overflow, and
/// other semantic properties from the IR to the backend.
///
/// @llvm_behavior: These flags correspond to LLVM's SDNodeFlags which
/// are derived from IR-level fast-math flags, nsw/nuw markings, etc.
/// They allow the DAG combiner and instruction selector to apply
/// more aggressive optimizations.
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub struct SDNodeFlags {
    /// No unsigned wrap (nuw) — for add/sub/mul/shift
    pub has_no_unsigned_wrap: bool,
    /// No signed wrap (nsw) — for add/sub/mul/shift
    pub has_no_signed_wrap: bool,
    /// Exact division — no remainder for sdiv/udiv/lshr/ashr
    pub has_exact: bool,
    /// No NaNs — fast-math flag
    pub has_no_nans: bool,
    /// No infinities — fast-math flag
    pub has_no_infs: bool,
    /// No signed zeros — fast-math flag
    pub has_no_signed_zeros: bool,
    /// Allow reciprocal — fast-math flag
    pub has_allow_reciprocal: bool,
    /// Allow contraction (FMA) — fast-math flag
    pub has_allow_contract: bool,
    /// Allow reassociation — fast-math flag
    pub has_allow_reassociation: bool,
    /// Approximate functions — fast-math flag
    pub has_approx_func: bool,
    /// Disjoint — for OR operations (no overlapping bits)
    pub is_disjoint: bool,
}

impl Default for SDNodeFlags {
    fn default() -> Self {
        Self {
            has_no_unsigned_wrap: false,
            has_no_signed_wrap: false,
            has_exact: false,
            has_no_nans: false,
            has_no_infs: false,
            has_no_signed_zeros: false,
            has_allow_reciprocal: false,
            has_allow_contract: false,
            has_allow_reassociation: false,
            has_approx_func: false,
            is_disjoint: false,
        }
    }
}

impl SDNodeFlags {
    /// Create flags with all properties set to false.
    pub fn new() -> Self {
        Self::default()
    }

    /// Returns true if any fast-math flag is set.
    pub fn has_fast_math_flags(&self) -> bool {
        self.has_no_nans
            || self.has_no_infs
            || self.has_no_signed_zeros
            || self.has_allow_reciprocal
            || self.has_allow_contract
            || self.has_allow_reassociation
            || self.has_approx_func
    }

    /// Returns true if any overflow flag is set.
    pub fn has_overflow_flags(&self) -> bool {
        self.has_no_unsigned_wrap || self.has_no_signed_wrap
    }
}

// ============================================================================
// SDOpcode — SelectionDAG node opcodes
// ============================================================================

/// Opcodes for SelectionDAG nodes.
///
/// Each opcode identifies the operation a node performs. The opcode
/// determines how many operands the node expects, how many values it
/// produces, and whether it has chain/glue edges.
///
/// @llvm_behavior: LLVM's ISD::NodeType enum has ~200+ variants. This
/// is a representative subset covering the most common operations.
#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
pub enum SDOpcode {
    // ---- Constants ----
    /// Integer constant
    Constant,
    /// Floating-point constant
    ConstantFP,
    /// Target-specific constant (e.g., immediate for a specific ISA)
    TargetConstant,

    // ---- Register / Copy ----
    /// Virtual register read
    Register,
    /// Copy from a virtual register (produces chain)
    CopyFromReg,
    /// Copy to a virtual register (produces chain)
    CopyToReg,

    // ---- Memory ----
    /// Load from memory (chain → value + chain)
    Load,
    /// Store to memory (chain + value + ptr → chain)
    Store,
    /// Atomic load
    AtomicLoad,
    /// Atomic store
    AtomicStore,
    /// Atomic compare-and-swap
    AtomicCmpSwap,
    /// Atomic read-modify-write
    AtomicRMW,

    // ---- Integer Arithmetic ----
    Add,
    Sub,
    Mul,
    UDiv,
    SDiv,
    URem,
    SRem,

    // ---- Floating-Point Arithmetic ----
    FAdd,
    FSub,
    FMul,
    FDiv,
    FRem,
    /// Floating-point negate
    FNeg,
    /// Floating-point absolute value
    FAbs,
    /// Fused multiply-add
    FMA,
    /// Square root
    FSqrt,
    /// Sine
    FSin,
    /// Cosine
    FCos,
    /// Base-2 logarithm
    FLog2,
    /// Base-2 exponential
    FExp2,

    // ---- Bitwise ----
    And,
    Or,
    Xor,
    Shl,
    Sra,
    Srl,

    // ---- Extended Arithmetic ----
    /// Signed multiply overflow high (smul_overflow hi part)
    SMulOh,
    /// Unsigned multiply overflow high (umul_overflow hi part)
    UMulOh,
    /// Unsigned add with overflow flag
    UAddO,
    /// Signed add with overflow flag
    SAddO,
    /// Unsigned sub with overflow flag
    USubO,
    /// Signed sub with overflow flag
    SSubO,

    // ---- Extended Bitwise ----
    /// Rotate left
    Rotl,
    /// Rotate right
    Rotr,
    /// Byte swap
    BSwap,
    /// Count leading zeros
    CtLz,
    /// Count trailing zeros
    CtTz,
    /// Population count
    CtPop,

    // ---- Select ----
    /// Conditional select (cond ? true_val : false_val)
    Select,
    /// Select with condition code (select_cc)
    SelectCC,
    /// Vector select (blend / vselect)
    VSelect,

    // ---- Comparison ----
    /// Set condition code (icmp/fcmp → i1)
    SetCC,

    // ---- Vector Operations ----
    /// Shuffle two vectors with a mask
    VectorShuffle,
    /// Extract a subvector from a larger vector
    ExtractSubvector,
    /// Insert a subvector into a larger vector
    InsertSubvector,
    /// Extract a scalar element from a vector
    ExtractElement,
    /// Insert a scalar element into a vector
    InsertElement,
    /// Build a vector from scalar elements
    BuildVector,
    /// Build a pair (two values into a 2-element struct/vector)
    BuildPair,
    /// Concatenate multiple vectors
    ConcatVectors,
    /// Convert scalar to vector (splat)
    ScalarToVector,

    // ---- Conversion ----
    /// Bitwise reinterpret cast
    Bitcast,
    /// Zero extend
    ZExt,
    /// Sign extend
    SExt,
    /// Truncate
    Trunc,
    /// Float to signed integer
    FPToSI,
    /// Float to unsigned integer
    FPToUI,
    /// Signed integer to float
    SIToFP,
    /// Unsigned integer to float
    UIToFP,
    /// Float rounding (narrow: f64 → f32)
    FpRound,
    /// Float extension (widen: f32 → f64)
    FpExtend,

    // ---- Frame / Address Operations ----
    /// Frame index (stack slot reference)
    FrameIndex,
    /// Global address
    GlobalAddress,
    /// External symbol address
    ExternalSymbol,
    /// Block address (for indirectbr)
    BlockAddress,
    /// Jump table entry
    JumpTable,
    /// Constant pool entry address
    ConstantPool,
    /// Target-specific index
    TargetIndex,

    // ---- Control Flow ----
    /// Unconditional branch
    Br,
    /// Conditional branch
    BrCond,
    /// Return
    Ret,
    /// Function call
    Call,

    // ---- Misc ----
    /// Undefined value
    Undef,
    /// Token factor (merge multiple chains into one)
    TokenFactor,
    /// Entry token (root of the chain dependency graph)
    EntryToken,

    // ---- Assertions ----
    /// Assert that a value is zero-extended to a wider type
    AssertZExt,
    /// Assert that a value is sign-extended to a wider type
    AssertSExt,

    // ---- Freeze ----
    /// Freeze a value (yields a poison-free copy)
    Freeze,

    // ---- Extended Loads ----
    /// Any-extend load (don't care about high bits)
    AnyExt,
    /// Sign-extending load
    SExtLoad,
    /// Zero-extending load
    ZExtLoad,

    // ---- Strict floating-point (exception-raising) ----
    /// Strict floating-point add (raises exceptions)
    StrictFAdd,
    /// Strict floating-point subtract
    StrictFSub,
    /// Strict floating-point multiply
    StrictFMul,
    /// Strict floating-point divide
    StrictFDiv,

    // ---- Overflow-checking arithmetic ----
    /// Signed multiply with overflow flag
    SMulo,
    /// Unsigned multiply with overflow flag
    UMulo,

    // ---- Bit manipulation ----
    /// Reverse bits
    BitReverse,

    // ---- Float-to-int saturating conversions ----
    /// Float to signed integer (saturating)
    FpToSIntSat,
    /// Float to unsigned integer (saturating)
    FpToUIntSat,

    // ---- Floating-point special operations ----
    /// Copy sign bit from one float to another (fcopysign)
    FCopySign,
    /// Canonicalize floating-point value (fcanonicalize)
    FCanonicalize,

    // ---- Saturating integer arithmetic ----
    /// Unsigned add with saturation
    UAddSat,
    /// Unsigned sub with saturation
    USubSat,
    /// Signed add with saturation
    SAddSat,
    /// Signed sub with saturation
    SSubSat,

    // ---- Library call placeholder ----
    /// Placeholder for a library call (will be lowered to a real call)
    LibCall,
}

impl SDOpcode {
    /// Returns a human-readable name for the opcode.
    pub fn as_str(&self) -> &'static str {
        match self {
            SDOpcode::Constant => "Constant",
            SDOpcode::ConstantFP => "ConstantFP",
            SDOpcode::TargetConstant => "TargetConstant",
            SDOpcode::Register => "Register",
            SDOpcode::CopyFromReg => "CopyFromReg",
            SDOpcode::CopyToReg => "CopyToReg",
            SDOpcode::Load => "Load",
            SDOpcode::Store => "Store",
            SDOpcode::AtomicLoad => "AtomicLoad",
            SDOpcode::AtomicStore => "AtomicStore",
            SDOpcode::AtomicCmpSwap => "AtomicCmpSwap",
            SDOpcode::AtomicRMW => "AtomicRMW",
            SDOpcode::Add => "Add",
            SDOpcode::Sub => "Sub",
            SDOpcode::Mul => "Mul",
            SDOpcode::UDiv => "UDiv",
            SDOpcode::SDiv => "SDiv",
            SDOpcode::URem => "URem",
            SDOpcode::SRem => "SRem",
            SDOpcode::FAdd => "FAdd",
            SDOpcode::FSub => "FSub",
            SDOpcode::FMul => "FMul",
            SDOpcode::FDiv => "FDiv",
            SDOpcode::FRem => "FRem",
            SDOpcode::FNeg => "FNeg",
            SDOpcode::FAbs => "FAbs",
            SDOpcode::FMA => "FMA",
            SDOpcode::FSqrt => "FSqrt",
            SDOpcode::FSin => "FSin",
            SDOpcode::FCos => "FCos",
            SDOpcode::FLog2 => "FLog2",
            SDOpcode::FExp2 => "FExp2",
            SDOpcode::And => "And",
            SDOpcode::Or => "Or",
            SDOpcode::Xor => "Xor",
            SDOpcode::Shl => "Shl",
            SDOpcode::Sra => "Sra",
            SDOpcode::Srl => "Srl",
            SDOpcode::SMulOh => "SMulOh",
            SDOpcode::UMulOh => "UMulOh",
            SDOpcode::UAddO => "UAddO",
            SDOpcode::SAddO => "SAddO",
            SDOpcode::USubO => "USubO",
            SDOpcode::SSubO => "SSubO",
            SDOpcode::Rotl => "Rotl",
            SDOpcode::Rotr => "Rotr",
            SDOpcode::BSwap => "BSwap",
            SDOpcode::CtLz => "CtLz",
            SDOpcode::CtTz => "CtTz",
            SDOpcode::CtPop => "CtPop",
            SDOpcode::Select => "Select",
            SDOpcode::SelectCC => "SelectCC",
            SDOpcode::VSelect => "VSelect",
            SDOpcode::SetCC => "SetCC",
            SDOpcode::VectorShuffle => "VectorShuffle",
            SDOpcode::ExtractSubvector => "ExtractSubvector",
            SDOpcode::InsertSubvector => "InsertSubvector",
            SDOpcode::ExtractElement => "ExtractElement",
            SDOpcode::InsertElement => "InsertElement",
            SDOpcode::BuildVector => "BuildVector",
            SDOpcode::BuildPair => "BuildPair",
            SDOpcode::ConcatVectors => "ConcatVectors",
            SDOpcode::ScalarToVector => "ScalarToVector",
            SDOpcode::Bitcast => "Bitcast",
            SDOpcode::ZExt => "ZExt",
            SDOpcode::SExt => "SExt",
            SDOpcode::Trunc => "Trunc",
            SDOpcode::FPToSI => "FPToSI",
            SDOpcode::FPToUI => "FPToUI",
            SDOpcode::SIToFP => "SIToFP",
            SDOpcode::UIToFP => "UIToFP",
            SDOpcode::FpRound => "FpRound",
            SDOpcode::FpExtend => "FpExtend",
            SDOpcode::FrameIndex => "FrameIndex",
            SDOpcode::GlobalAddress => "GlobalAddress",
            SDOpcode::ExternalSymbol => "ExternalSymbol",
            SDOpcode::BlockAddress => "BlockAddress",
            SDOpcode::JumpTable => "JumpTable",
            SDOpcode::ConstantPool => "ConstantPool",
            SDOpcode::TargetIndex => "TargetIndex",
            SDOpcode::Br => "Br",
            SDOpcode::BrCond => "BrCond",
            SDOpcode::Ret => "Ret",
            SDOpcode::Call => "Call",
            SDOpcode::Undef => "Undef",
            SDOpcode::TokenFactor => "TokenFactor",
            SDOpcode::EntryToken => "EntryToken",
            SDOpcode::AssertZExt => "AssertZExt",
            SDOpcode::AssertSExt => "AssertSExt",
            SDOpcode::Freeze => "Freeze",
            SDOpcode::AnyExt => "AnyExt",
            SDOpcode::SExtLoad => "SExtLoad",
            SDOpcode::ZExtLoad => "ZExtLoad",
            SDOpcode::StrictFAdd => "StrictFAdd",
            SDOpcode::StrictFSub => "StrictFSub",
            SDOpcode::StrictFMul => "StrictFMul",
            SDOpcode::StrictFDiv => "StrictFDiv",
            SDOpcode::SMulo => "SMulo",
            SDOpcode::UMulo => "UMulo",
            SDOpcode::BitReverse => "BitReverse",
            SDOpcode::FpToSIntSat => "FpToSIntSat",
            SDOpcode::FpToUIntSat => "FpToUIntSat",
            SDOpcode::FCopySign => "FCopySign",
            SDOpcode::FCanonicalize => "FCanonicalize",
            SDOpcode::UAddSat => "UAddSat",
            SDOpcode::USubSat => "USubSat",
            SDOpcode::SAddSat => "SAddSat",
            SDOpcode::SSubSat => "SSubSat",
            SDOpcode::LibCall => "LibCall",
        }
    }
}

// ============================================================================
// SDValue — lightweight handle to an SDNode result
// ============================================================================

/// A value in the SelectionDAG: a node reference + result number.
///
/// SDValue is a lightweight (8-byte) handle that refers to a specific
/// result of an SDNode. Most nodes produce one result (res_no = 0);
/// nodes like Load and CopyFromReg produce two (value + chain).
///
/// @llvm_behavior: In LLVM, SDValue is 4 bytes (union of SDNode* and
/// result number in the low bits). Our implementation uses a pair of
/// node index + result number for safe indexing.
#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
pub struct SDValue {
    /// Index into the SelectionDAG's nodes vector
    pub node_id: usize,
    /// Which result of the node (0 for most nodes, 1 for chain results)
    pub res_no: u32,
}

impl SDValue {
    /// Create a new SDValue referencing a specific node and result number.
    pub fn new(node_id: usize, res_no: u32) -> Self {
        Self { node_id, res_no }
    }

    /// Get the opcode of the node this value references.
    ///
    /// Panics if the node_id is out of bounds.
    pub fn get_opcode(&self, dag: &SelectionDAG) -> SDOpcode {
        dag.get_node(*self).opcode
    }

    /// Get the type of this specific result.
    ///
    /// Panics if res_no is out of bounds for the node's value_types.
    pub fn get_value_type(&self, dag: &SelectionDAG) -> Type {
        let node = dag.get_node(*self);
        node.get_value_type(self.res_no)
            .cloned()
            .unwrap_or_else(|| {
                panic!(
                    "SDValue::get_value_type: res_no {} out of range",
                    self.res_no
                )
            })
    }

    /// Check if the node has exactly one use in the DAG.
    ///
    /// Walks all nodes to count uses. O(n) operation.
    pub fn has_one_use(&self, dag: &SelectionDAG) -> bool {
        let mut count = 0;
        for node in &dag.nodes {
            for op in &node.operands {
                if op.node_id == self.node_id && op.res_no == self.res_no {
                    count += 1;
                    if count > 1 {
                        return false;
                    }
                }
            }
        }
        count == 1
    }

    /// Get the number of operands of the underlying node.
    pub fn get_num_operands(&self, dag: &SelectionDAG) -> usize {
        dag.get_node(*self).operands.len()
    }

    /// Get the i-th operand of the underlying node.
    pub fn get_operand(&self, dag: &SelectionDAG, i: usize) -> Option<SDValue> {
        dag.get_node(*self).get_operand(i)
    }

    /// Returns true if this value is the entry token.
    pub fn is_entry_token(&self, dag: &SelectionDAG) -> bool {
        dag.get_node(*self).opcode == SDOpcode::EntryToken
    }

    /// Returns true if this is a constant value.
    pub fn is_constant(&self, dag: &SelectionDAG) -> bool {
        dag.get_node(*self).is_constant()
    }
}

// ============================================================================
// SDNode — a node in the SelectionDAG
// ============================================================================

/// A node in the SelectionDAG.
///
/// Each SDNode represents a single operation (arithmetic, memory, control
/// flow, etc.). It has an opcode, a list of operand SDValues, the types
/// of values it produces, and optional flags.
///
/// @llvm_behavior: In LLVM, SDNode is a base class with many subclasses
/// (ConstantSDNode, MemSDNode, LoadSDNode, StoreSDNode, etc.). Our flat
/// representation uses the opcode and flags to differentiate behavior.
#[derive(Debug, Clone)]
pub struct SDNode {
    /// Index of this node in the SelectionDAG's nodes vector
    pub id: usize,
    /// The operation this node performs
    pub opcode: SDOpcode,
    /// Input operands (other SDValues this node depends on)
    pub operands: Vec<SDValue>,
    /// Types of values produced by this node (one per result)
    pub value_types: Vec<Type>,
    /// Number of values this node produces (0 for terminators, 1 or 2 for most)
    pub num_values: u32,
    /// Semantic flags (fast-math, overflow, etc.)
    pub flags: SDNodeFlags,
    /// Debug source location (if available)
    pub debug_loc: Option<String>,
    /// Unique identifier across all nodes ever created
    pub node_id: usize,
    /// Whether this is a target-specific node (e.g., X86ISD::CALL)
    pub is_target_node: bool,
    /// Whether this is a memory intrinsic (memcpy, memmove, memset)
    pub is_mem_intrinsic: bool,
}

impl SDNode {
    /// Create a new SDNode with the given id and opcode.
    ///
    /// The number of values produced is inferred from value_types.len().
    pub fn new(id: usize, opcode: SDOpcode, value_types: Vec<Type>) -> Self {
        Self {
            id,
            opcode,
            operands: Vec::new(),
            num_values: value_types.len() as u32,
            value_types,
            flags: SDNodeFlags::default(),
            debug_loc: None,
            node_id: id,
            is_target_node: false,
            is_mem_intrinsic: false,
        }
    }

    /// Create a new SDNode with a specific unique node_id.
    pub fn new_with_node_id(
        id: usize,
        node_id: usize,
        opcode: SDOpcode,
        value_types: Vec<Type>,
    ) -> Self {
        Self {
            id,
            opcode,
            operands: Vec::new(),
            num_values: value_types.len() as u32,
            value_types,
            flags: SDNodeFlags::default(),
            debug_loc: None,
            node_id,
            is_target_node: false,
            is_mem_intrinsic: false,
        }
    }

    /// Attach operands to this node (builder pattern).
    pub fn with_operands(mut self, ops: Vec<SDValue>) -> Self {
        self.operands = ops;
        self
    }

    /// Attach flags to this node (builder pattern).
    pub fn with_flags(mut self, flags: SDNodeFlags) -> Self {
        self.flags = flags;
        self
    }

    /// Set the number of values this node produces.
    pub fn with_num_values(mut self, n: u32) -> Self {
        self.num_values = n;
        self
    }

    /// Set the debug location.
    pub fn with_debug_loc(mut self, loc: Option<String>) -> Self {
        self.debug_loc = loc;
        self
    }

    /// Mark this node as a target-specific node.
    pub fn with_target_node(mut self, is_target: bool) -> Self {
        self.is_target_node = is_target;
        self
    }

    /// Get the i-th operand, if it exists.
    pub fn get_operand(&self, i: usize) -> Option<SDValue> {
        self.operands.get(i).copied()
    }

    /// Get the number of operands.
    pub fn get_num_operands(&self) -> usize {
        self.operands.len()
    }

    /// Get the type of the i-th result value.
    pub fn get_value_type(&self, i: u32) -> Option<&Type> {
        self.value_types.get(i as usize)
    }

    // --- Classification methods ---

    /// Returns true if this node uses or produces a chain (token) edge.
    ///
    /// Chain edges enforce memory ordering between memory operations,
    /// calls, and control flow.
    pub fn has_chain(&self) -> bool {
        matches!(
            self.opcode,
            SDOpcode::Load
                | SDOpcode::Store
                | SDOpcode::AtomicLoad
                | SDOpcode::AtomicStore
                | SDOpcode::AtomicCmpSwap
                | SDOpcode::AtomicRMW
                | SDOpcode::CopyFromReg
                | SDOpcode::CopyToReg
                | SDOpcode::Call
                | SDOpcode::Ret
                | SDOpcode::Br
                | SDOpcode::BrCond
                | SDOpcode::TokenFactor
                | SDOpcode::EntryToken
        )
    }

    /// Returns true if this node uses or produces a glue edge.
    ///
    /// Glue edges enforce scheduling constraints between nodes
    /// that must be adjacent (e.g., a compare feeding a branch).
    pub fn has_glue(&self) -> bool {
        matches!(
            self.opcode,
            SDOpcode::CopyToReg | SDOpcode::CopyFromReg | SDOpcode::SetCC
        )
    }

    /// Returns true if this is a memory operation (load/store/atomic).
    pub fn is_memory_op(&self) -> bool {
        matches!(
            self.opcode,
            SDOpcode::Load
                | SDOpcode::Store
                | SDOpcode::AtomicLoad
                | SDOpcode::AtomicStore
                | SDOpcode::AtomicCmpSwap
                | SDOpcode::AtomicRMW
        )
    }

    /// Returns true if this is a terminator (br/ret).
    pub fn is_terminator(&self) -> bool {
        matches!(self.opcode, SDOpcode::Br | SDOpcode::BrCond | SDOpcode::Ret)
    }

    /// Returns true if this is a binary arithmetic or bitwise operation.
    pub fn is_binary_op(&self) -> bool {
        matches!(
            self.opcode,
            SDOpcode::Add
                | SDOpcode::Sub
                | SDOpcode::Mul
                | SDOpcode::UDiv
                | SDOpcode::SDiv
                | SDOpcode::URem
                | SDOpcode::SRem
                | SDOpcode::FAdd
                | SDOpcode::FSub
                | SDOpcode::FMul
                | SDOpcode::FDiv
                | SDOpcode::FRem
                | SDOpcode::And
                | SDOpcode::Or
                | SDOpcode::Xor
                | SDOpcode::Shl
                | SDOpcode::Sra
                | SDOpcode::Srl
                | SDOpcode::Rotl
                | SDOpcode::Rotr
                | SDOpcode::SMulOh
                | SDOpcode::UMulOh
        )
    }

    /// Returns true if this binary operation is commutative.
    ///
    /// Commutative operations: Add, Mul, FAdd, FMul, And, Or, Xor,
    /// UAddO, SAddO, UMulOh, SMulOh.
    pub fn is_commutative(&self) -> bool {
        matches!(
            self.opcode,
            SDOpcode::Add
                | SDOpcode::Mul
                | SDOpcode::FAdd
                | SDOpcode::FMul
                | SDOpcode::And
                | SDOpcode::Or
                | SDOpcode::Xor
                | SDOpcode::UAddO
                | SDOpcode::SAddO
                | SDOpcode::UMulOh
                | SDOpcode::SMulOh
        )
    }

    /// Returns true if this node is a constant (integer or FP).
    pub fn is_constant(&self) -> bool {
        matches!(self.opcode, SDOpcode::Constant | SDOpcode::ConstantFP)
    }

    /// Returns true if this node is an undef.
    pub fn is_undef(&self) -> bool {
        self.opcode == SDOpcode::Undef
    }

    /// Returns true if this node is a load.
    pub fn is_load(&self) -> bool {
        self.opcode == SDOpcode::Load
    }

    /// Returns true if this node is a store.
    pub fn is_store(&self) -> bool {
        self.opcode == SDOpcode::Store
    }

    /// Returns true if this is a conversion/cast operation.
    pub fn is_conversion(&self) -> bool {
        matches!(
            self.opcode,
            SDOpcode::Bitcast
                | SDOpcode::ZExt
                | SDOpcode::SExt
                | SDOpcode::Trunc
                | SDOpcode::FPToSI
                | SDOpcode::FPToUI
                | SDOpcode::SIToFP
                | SDOpcode::UIToFP
                | SDOpcode::FpRound
                | SDOpcode::FpExtend
        )
    }

    /// Returns the chain operand index for this node.
    ///
    /// For chain-producing nodes, the chain is typically the first operand.
    /// Returns None if the node does not use a chain.
    pub fn get_chain_index(&self) -> Option<usize> {
        if self.has_chain() && !matches!(self.opcode, SDOpcode::EntryToken) {
            Some(0)
        } else {
            None
        }
    }
}

// ============================================================================
// SelectionDAG — DAG container
// ============================================================================

/// The SelectionDAG for a basic block or function.
///
/// Manages all SDNodes, provides factory methods for common node types,
/// and tracks the chain dependency and constant pool.
///
/// @llvm_behavior: In LLVM, SelectionDAG is the central data structure
/// for instruction selection. It owns all SDNodes (allocated on a
/// BumpPtrAllocator) and provides methods like getNode(), getConstant(),
/// getLoad(), etc. that create nodes with appropriate types.
#[derive(Debug, Clone)]
pub struct SelectionDAG {
    /// Current live nodes in the DAG
    pub nodes: Vec<SDNode>,
    /// The entry token (root of the chain dependency graph)
    pub entry_token: SDValue,
    /// The root of the DAG (the final result of the block)
    pub root: Option<SDValue>,
    /// All nodes ever created (for tracking/debugging)
    pub all_nodes: Vec<SDNode>,
    /// Map from IR value IDs to SDNode ids
    pub node_map: HashMap<usize, usize>,
    /// Constant pool: maps (value, type_id) → SDValue for integer constants
    pub constant_pool: HashMap<(u64, u64), SDValue>,
    /// Constant pool for floating-point values: maps (fp_bits, type_id) → SDValue
    pub constant_fp_pool: HashMap<(u64, u64), SDValue>,
    /// Target triple string (e.g., "x86_64-unknown-linux-gnu")
    pub target: Option<String>,
    /// Monotonic counter for unique node IDs
    next_node_id: usize,
}

impl Default for SelectionDAG {
    fn default() -> Self {
        Self::new()
    }
}

/// Compute a stable hash key from a Type's kind (not its globally-unique ID).
/// This allows constant deduplication across different Type instances of the same kind.
fn type_kind_key(ty: &Type) -> u64 {
    match &ty.kind {
        TypeKind::Void => 0,
        TypeKind::Half => 1,
        TypeKind::BFloat => 2,
        TypeKind::Float => 3,
        TypeKind::Double => 4,
        TypeKind::FP128 => 5,
        TypeKind::X86FP80 => 6,
        TypeKind::PPCFP128 => 7,
        TypeKind::Label => 8,
        TypeKind::Metadata => 9,
        TypeKind::X86AMX => 10,
        TypeKind::X86MMX => 11,
        TypeKind::Token => 12,
        TypeKind::Integer { bits } => 13u64 | ((*bits as u64) << 8),
        TypeKind::Pointer { addr_space } => 14u64 | ((*addr_space as u64) << 8),
        TypeKind::Array {
            len,
            element_type_id: _,
        } => 15u64 | ((*len as u64) << 8),
        TypeKind::Struct { .. } => 16,
        TypeKind::FixedVector {
            len,
            element_type_id: _,
        } => 17u64 | ((*len as u64) << 8),
        TypeKind::ScalableVector {
            min_elems,
            element_type_id: _,
        } => 18u64 | ((*min_elems as u64) << 8),
        TypeKind::Function { .. } => 19,
    }
}

impl SelectionDAG {
    /// Create a new empty SelectionDAG with an EntryToken node.
    pub fn new() -> Self {
        let entry = SDNode::new_with_node_id(0, 0, SDOpcode::EntryToken, vec![Type::token()]);
        let et = SDValue::new(0, 0);
        Self {
            nodes: vec![entry.clone()],
            entry_token: et,
            root: None,
            all_nodes: vec![entry],
            node_map: HashMap::new(),
            constant_pool: HashMap::new(),
            constant_fp_pool: HashMap::new(),
            target: None,
            // next_node_id starts at 1 since EntryToken is 0
            next_node_id: 1,
        }
    }

    /// Create a new SelectionDAG for a specific target triple.
    pub fn with_target(target: &str) -> Self {
        let mut dag = Self::new();
        dag.target = Some(target.to_string());
        dag
    }

    /// Add a node to the DAG and return its first result SDValue.
    ///
    /// For nodes producing multiple values (e.g., Load produces value + chain),
    /// the chain is available at `SDValue::new(id, 1)`.
    pub fn add_node(
        &mut self,
        opcode: SDOpcode,
        value_types: Vec<Type>,
        operands: Vec<SDValue>,
    ) -> SDValue {
        let id = self.nodes.len();
        let node_id = self.next_node_id;
        self.next_node_id += 1;

        let node =
            SDNode::new_with_node_id(id, node_id, opcode, value_types).with_operands(operands);

        self.nodes.push(node.clone());
        self.all_nodes.push(node);
        SDValue::new(id, 0)
    }

    /// Add a node with explicit num_values (for nodes that produce chain on res_no=1).
    pub fn add_node_with_values(
        &mut self,
        opcode: SDOpcode,
        value_types: Vec<Type>,
        operands: Vec<SDValue>,
        num_values: u32,
    ) -> SDValue {
        let id = self.nodes.len();
        let node_id = self.next_node_id;
        self.next_node_id += 1;

        let node = SDNode::new_with_node_id(id, node_id, opcode, value_types)
            .with_operands(operands)
            .with_num_values(num_values);

        self.nodes.push(node.clone());
        self.all_nodes.push(node);
        SDValue::new(id, 0)
    }

    /// Get a reference to a node by its SDValue.
    ///
    /// Panics if the node_id is out of bounds.
    pub fn get_node(&self, val: SDValue) -> &SDNode {
        &self.nodes[val.node_id]
    }

    /// Get a mutable reference to a node by its SDValue.
    ///
    /// Panics if the node_id is out of bounds.
    pub fn get_node_mut(&mut self, val: SDValue) -> &mut SDNode {
        &mut self.nodes[val.node_id]
    }

    /// Set the root of the DAG (the overall result of the block/function).
    pub fn set_root(&mut self, val: SDValue) {
        self.root = Some(val);
    }

    /// Get the current root, if set.
    pub fn get_root(&self) -> Option<SDValue> {
        self.root
    }

    // === Node factory methods ===

    /// Get or create a constant integer node for the given value and type.
    ///
    /// Constants are deduplicated: two requests for the same value+type
    /// return the same SDValue.
    pub fn get_constant(&mut self, val: u64, ty: Type) -> SDValue {
        let type_id = type_kind_key(&ty);
        let key = (val, type_id);
        if let Some(&existing) = self.constant_pool.get(&key) {
            return existing;
        }
        let sdval = self.add_node(SDOpcode::Constant, vec![ty], vec![]);
        self.constant_pool.insert(key, sdval);
        sdval
    }

    /// Get or create a constant floating-point node.
    ///
    /// Constants are deduplicated by their bit pattern and type.
    pub fn get_constant_fp(&mut self, fp_bits: u64, ty: Type) -> SDValue {
        let type_id = type_kind_key(&ty);
        let key = (fp_bits, type_id);
        if let Some(&existing) = self.constant_fp_pool.get(&key) {
            return existing;
        }
        let sdval = self.add_node(SDOpcode::ConstantFP, vec![ty], vec![]);
        self.constant_fp_pool.insert(key, sdval);
        sdval
    }

    /// Create an undef node for the given type.
    pub fn get_undef(&mut self, ty: Type) -> SDValue {
        self.add_node(SDOpcode::Undef, vec![ty], vec![])
    }

    /// Create a Register node (virtual register read).
    pub fn get_register(&mut self, ty: Type) -> SDValue {
        self.add_node(SDOpcode::Register, vec![ty], vec![])
    }

    /// Create a CopyToReg node: copies a value into a register.
    /// Returns the chain result.
    pub fn get_copy_to_reg(&mut self, chain: SDValue, val: SDValue) -> SDValue {
        // CopyToReg produces a chain (no data type on result 0)
        let _ty = self
            .get_node(val)
            .value_types
            .first()
            .cloned()
            .unwrap_or(Type::token());
        let sdval = self.add_node_with_values(
            SDOpcode::CopyToReg,
            vec![Type::token()],
            vec![chain, val],
            1,
        );
        // The chain is result 0 for CopyToReg
        sdval
    }

    /// Create a CopyFromReg node: reads a value from a register.
    /// Returns the data value. The chain is at res_no=1.
    pub fn get_copy_from_reg(&mut self, chain: SDValue, ty: Type) -> SDValue {
        self.add_node_with_values(
            SDOpcode::CopyFromReg,
            vec![ty, Type::token()],
            vec![chain],
            2,
        )
    }

    /// Create a Load node. Returns the loaded value.
    /// The chain result is at `SDValue::new(result.node_id, 1)`.
    pub fn get_load(&mut self, chain: SDValue, ptr: SDValue, ty: Type) -> SDValue {
        self.add_node_with_values(SDOpcode::Load, vec![ty, Type::token()], vec![chain, ptr], 2)
    }

    /// Create a Store node. Returns the chain.
    pub fn get_store(&mut self, chain: SDValue, val: SDValue, ptr: SDValue) -> SDValue {
        // Store produces a chain (no data value types)
        self.add_node_with_values(
            SDOpcode::Store,
            vec![Type::token()],
            vec![chain, val, ptr],
            1,
        )
    }

    /// Create a binary operation node.
    pub fn get_binary_op(&mut self, op: SDOpcode, ty: Type, lhs: SDValue, rhs: SDValue) -> SDValue {
        self.add_node(op, vec![ty], vec![lhs, rhs])
    }

    /// Create a SetCC (comparison) node with the given integer predicate.
    pub fn get_setcc(&mut self, _cond: ICmpPred, ty: Type, lhs: SDValue, rhs: SDValue) -> SDValue {
        self.add_node(SDOpcode::SetCC, vec![ty], vec![lhs, rhs])
    }

    /// Create a Select node (cond ? true_val : false_val).
    pub fn get_select(
        &mut self,
        cond: SDValue,
        true_val: SDValue,
        false_val: SDValue,
        ty: Type,
    ) -> SDValue {
        self.add_node(SDOpcode::Select, vec![ty], vec![cond, true_val, false_val])
    }

    /// Create a TokenFactor node that merges multiple chain tokens into one.
    pub fn get_token_factor(&mut self, tokens: Vec<SDValue>) -> SDValue {
        self.add_node(SDOpcode::TokenFactor, vec![Type::token()], tokens)
    }

    /// Create a MergeValues node (for merging multiple SDValues into one).
    /// This is useful for merging the results of multiple chains.
    pub fn get_merge_values(&mut self, values: Vec<SDValue>) -> SDValue {
        // Use TokenFactor semantics for merging chains
        self.add_node(SDOpcode::TokenFactor, vec![Type::token()], values)
    }

    // === Chain/Glue management ===

    /// Get the chain result from a load operation.
    /// load_val is the data result (res_no=0); the chain is at res_no=1.
    pub fn get_load_chain(&self, load_val: SDValue) -> SDValue {
        SDValue::new(load_val.node_id, 1)
    }

    /// Get the chain result from a CopyFromReg.
    pub fn get_copy_from_reg_chain(&self, copy_val: SDValue) -> SDValue {
        SDValue::new(copy_val.node_id, 1)
    }

    // === Node replacement and deletion ===

    /// Replace all uses of `from` with `to` across all nodes in the DAG.
    ///
    /// Walks all nodes and replaces any operand matching `from` with `to`.
    pub fn replace_all_uses_with(&mut self, from: SDValue, to: SDValue) {
        for node in &mut self.nodes {
            for op in &mut node.operands {
                if op.node_id == from.node_id && op.res_no == from.res_no {
                    *op = to;
                }
            }
        }
    }

    /// Mark a node as dead (does not actually remove it, but clears its operands).
    ///
    /// In a real DAG, dead nodes would be removed during legalization.
    pub fn remove_dead_node(&mut self, val: SDValue) {
        if val.node_id < self.nodes.len() {
            self.nodes[val.node_id].operands.clear();
        }
    }

    /// Delete a node from the DAG by clearing it and removing from root if needed.
    ///
    /// Note: the node's index in the nodes vector is preserved (as a tombstone)
    /// because other values may reference it. In a full implementation, you would
    /// use a mapping from old to new indices.
    pub fn delete_node(&mut self, val: SDValue) {
        if val.node_id < self.nodes.len() {
            // Clear operands
            self.nodes[val.node_id].operands.clear();
            self.nodes[val.node_id].value_types.clear();
        }
        // If this was the root, clear root
        if self.root == Some(val) {
            self.root = None;
        }
    }

    /// Get the total number of nodes currently in the DAG.
    pub fn num_nodes(&self) -> usize {
        self.nodes.len()
    }

    /// Get the total number of nodes ever allocated.
    pub fn num_all_nodes(&self) -> usize {
        self.all_nodes.len()
    }

    /// Returns true if the DAG is empty (has only the EntryToken).
    pub fn is_empty(&self) -> bool {
        self.nodes.len() <= 1
    }

    /// Create a deep copy of the DAG (with new node IDs).
    pub fn deep_clone(&self) -> Self {
        let mut new_dag = SelectionDAG::new();
        // Skip the first node (EntryToken) and copy the rest
        for node in self.nodes.iter().skip(1) {
            new_dag.add_node(node.opcode, node.value_types.clone(), node.operands.clone());
        }
        new_dag.root = self.root;
        new_dag.target = self.target.clone();
        new_dag.constant_pool = self.constant_pool.clone();
        new_dag.constant_fp_pool = self.constant_fp_pool.clone();
        new_dag.node_map = self.node_map.clone();
        new_dag
    }
}

// ============================================================================
// Extended SDNode Flags — NuW/NSW/Exact accessors
// ============================================================================

impl SDNodeFlags {
    /// Check if No Unsigned Wrap flag is set.
    pub fn has_nuw(&self) -> bool {
        self.has_no_unsigned_wrap
    }

    /// Check if No Signed Wrap flag is set.
    pub fn has_nsw(&self) -> bool {
        self.has_no_signed_wrap
    }

    /// Check if Exact flag is set.
    pub fn has_exact_flag(&self) -> bool {
        self.has_exact
    }

    /// Check if No NaNs flag is set.
    pub fn has_no_nans_flag(&self) -> bool {
        self.has_no_nans
    }

    /// Set the No Unsigned Wrap flag.
    pub fn set_nuw(&mut self, val: bool) {
        self.has_no_unsigned_wrap = val;
    }

    /// Set the No Signed Wrap flag.
    pub fn set_nsw(&mut self, val: bool) {
        self.has_no_signed_wrap = val;
    }

    /// Set the Exact flag.
    pub fn set_exact(&mut self, val: bool) {
        self.has_exact = val;
    }

    /// Set Disjoint flag.
    pub fn set_disjoint(&mut self, val: bool) {
        self.is_disjoint = val;
    }
}

// ============================================================================
// MachineMemOperand — memory reference metadata
// ============================================================================

/// Memory operation flags.
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub enum MemOpFlags {
    None = 0,
    Load = 1 << 0,
    Store = 1 << 1,
    Volatile = 1 << 2,
    NonTemporal = 1 << 3,
    Invariant = 1 << 4,
    MayAlias = 1 << 5,
}

/// MachineMemOperand describes a memory reference: pointer value,
/// size, alignment, AA info, and flags.
#[derive(Debug, Clone)]
pub struct MachineMemOperand {
    /// Pointer info: base + offset.
    pub pointer_value: Option<SDValue>,
    /// Size of the memory access in bytes.
    pub size: u64,
    /// Alignment of the access (power of 2).
    pub alignment: u32,
    /// Address space.
    pub addr_space: u32,
    /// AA info: the underlying IR value for alias analysis.
    pub aa_info: Option<SDValue>,
    /// Flags: load/store/volatile/non-temporal/invariant.
    pub flags: u32,
}

impl MachineMemOperand {
    pub fn new(pointer_value: Option<SDValue>, size: u64, alignment: u32, addr_space: u32) -> Self {
        Self {
            pointer_value,
            size,
            alignment,
            addr_space,
            aa_info: None,
            flags: 0,
        }
    }

    /// Create a machine mem operand for a load.
    pub fn new_load(ptr: SDValue, size: u64, alignment: u32, addr_space: u32) -> Self {
        let mut mmo = Self::new(Some(ptr), size, alignment, addr_space);
        mmo.flags |= MemOpFlags::Load as u32;
        mmo
    }

    /// Create a machine mem operand for a store.
    pub fn new_store(ptr: SDValue, size: u64, alignment: u32, addr_space: u32) -> Self {
        let mut mmo = Self::new(Some(ptr), size, alignment, addr_space);
        mmo.flags |= MemOpFlags::Store as u32;
        mmo
    }

    pub fn is_load(&self) -> bool {
        self.flags & (MemOpFlags::Load as u32) != 0
    }

    pub fn is_store(&self) -> bool {
        self.flags & (MemOpFlags::Store as u32) != 0
    }

    pub fn is_volatile(&self) -> bool {
        self.flags & (MemOpFlags::Volatile as u32) != 0
    }

    pub fn set_volatile(&mut self, val: bool) {
        if val {
            self.flags |= MemOpFlags::Volatile as u32;
        } else {
            self.flags &= !(MemOpFlags::Volatile as u32);
        }
    }

    pub fn is_non_temporal(&self) -> bool {
        self.flags & (MemOpFlags::NonTemporal as u32) != 0
    }

    pub fn set_non_temporal(&mut self, val: bool) {
        if val {
            self.flags |= MemOpFlags::NonTemporal as u32;
        } else {
            self.flags &= !(MemOpFlags::NonTemporal as u32);
        }
    }

    pub fn is_invariant(&self) -> bool {
        self.flags & (MemOpFlags::Invariant as u32) != 0
    }

    pub fn get_alignment(&self) -> u32 {
        self.alignment
    }

    pub fn get_size(&self) -> u64 {
        self.size
    }

    pub fn get_addr_space(&self) -> u32 {
        self.addr_space
    }

    pub fn get_pointer_info(&self) -> Option<SDValue> {
        self.pointer_value
    }

    pub fn with_aa_info(mut self, aa: SDValue) -> Self {
        self.aa_info = Some(aa);
        self
    }
}

impl Default for MachineMemOperand {
    fn default() -> Self {
        Self {
            pointer_value: None,
            size: 0,
            alignment: 1,
            addr_space: 0,
            aa_info: None,
            flags: 0,
        }
    }
}

// ============================================================================
// MemSDNode — base class for memory-accessing SDNodes
// ============================================================================

/// MemSDNode is the base class for SDNodes that access memory
/// (Load, Store, Atomic operations). It carries a MachineMemOperand.
pub struct MemSDNode {
    pub node: SDNode,
    pub mem_operand: MachineMemOperand,
}

impl MemSDNode {
    pub fn new(node: SDNode, mem_operand: MachineMemOperand) -> Self {
        Self { node, mem_operand }
    }

    pub fn get_mem_operand(&self) -> &MachineMemOperand {
        &self.mem_operand
    }

    pub fn get_memory_size(&self) -> u64 {
        self.mem_operand.size
    }

    pub fn get_alignment(&self) -> u32 {
        self.mem_operand.alignment
    }

    pub fn is_volatile(&self) -> bool {
        self.mem_operand.is_volatile()
    }

    pub fn is_load(&self) -> bool {
        self.mem_operand.is_load()
    }

    pub fn is_store(&self) -> bool {
        self.mem_operand.is_store()
    }

    pub fn get_chain(&self) -> Option<SDValue> {
        self.node.operands.first().copied()
    }

    pub fn get_pointer(&self) -> Option<SDValue> {
        self.node.operands.get(1).copied()
    }
}

// ============================================================================
// AtomicSDNode — atomic memory operations with ordering
// ============================================================================

/// Memory ordering for atomic operations.
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub enum AtomicOrdering {
    NotAtomic,
    Unordered,
    Monotonic,
    Acquire,
    Release,
    AcquireRelease,
    SequentiallyConsistent,
}

/// Synchronization scope for atomic operations.
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub enum SyncScope {
    SingleThread,
    System,
}

/// AtomicSDNode — SDNode with atomic ordering and sync scope.
pub struct AtomicSDNode {
    pub node: SDNode,
    pub ordering: AtomicOrdering,
    pub failure_ordering: AtomicOrdering,
    pub sync_scope: SyncScope,
}

impl AtomicSDNode {
    pub fn new(node: SDNode, ordering: AtomicOrdering, sync_scope: SyncScope) -> Self {
        Self {
            node,
            ordering,
            failure_ordering: AtomicOrdering::NotAtomic,
            sync_scope,
        }
    }

    pub fn with_failure_ordering(mut self, ord: AtomicOrdering) -> Self {
        self.failure_ordering = ord;
        self
    }

    pub fn get_ordering(&self) -> AtomicOrdering {
        self.ordering
    }

    pub fn get_sync_scope(&self) -> SyncScope {
        self.sync_scope
    }

    pub fn is_cmpxchg(&self) -> bool {
        self.node.opcode == SDOpcode::AtomicCmpSwap
    }

    pub fn is_rmw(&self) -> bool {
        self.node.opcode == SDOpcode::AtomicRMW
    }
}

// ============================================================================
// LSBaseSDNode — load/store base with address space and alignment
// ============================================================================

/// LSBaseSDNode is the common base for LoadSDNode and StoreSDNode,
/// carrying address space and alignment information.
pub struct LSBaseSDNode {
    pub node: SDNode,
    pub addr_space: u32,
    pub alignment: u32,
}

impl LSBaseSDNode {
    pub fn new(node: SDNode, addr_space: u32, alignment: u32) -> Self {
        Self {
            node,
            addr_space,
            alignment,
        }
    }

    pub fn get_addr_space(&self) -> u32 {
        self.addr_space
    }

    pub fn get_alignment(&self) -> u32 {
        self.alignment
    }

    pub fn get_chain(&self) -> Option<SDValue> {
        self.node.operands.first().copied()
    }

    pub fn get_pointer(&self) -> Option<SDValue> {
        self.node.operands.get(1).copied()
    }

    pub fn get_value(&self) -> Option<SDValue> {
        self.node.operands.get(1).copied()
    }

    pub fn has_nontemporal(&self) -> bool {
        self.node.flags.has_allow_contract
    }
}

// ============================================================================
// EVT — Extended Value Type system
// ============================================================================

/// EVT (Extended Value Type) — an extension of MVT that includes
/// types not representable as simple MVTs (e.g., i13, v7i32, etc.).
#[derive(Debug, Clone, PartialEq, Eq)]
pub enum EVTKind {
    Simple(MVT),
    ExtendedInteger { bits: u32 },
    ExtendedFloat { bits: u32 },
    ExtendedVector { num_elems: u32, elem_type: Box<EVT> },
}

/// Extended Value Type.
#[derive(Debug, Clone, PartialEq, Eq)]
pub struct EVT {
    pub kind: EVTKind,
}

impl EVT {
    pub fn new(kind: EVTKind) -> Self {
        Self { kind }
    }

    pub fn is_simple(&self) -> bool {
        matches!(self.kind, EVTKind::Simple(_))
    }

    pub fn get_simple_vt(&self) -> Option<MVT> {
        match &self.kind {
            EVTKind::Simple(vt) => Some(*vt),
            _ => None,
        }
    }

    pub fn get_size_in_bits(&self) -> u32 {
        match &self.kind {
            EVTKind::Simple(vt) => vt.get_size_in_bits(),
            EVTKind::ExtendedInteger { bits } => *bits,
            EVTKind::ExtendedFloat { bits } => *bits,
            EVTKind::ExtendedVector {
                num_elems,
                elem_type,
            } => num_elems * elem_type.get_size_in_bits(),
        }
    }

    pub fn is_integer(&self) -> bool {
        match &self.kind {
            EVTKind::Simple(vt) => vt.is_integer(),
            EVTKind::ExtendedInteger { .. } => true,
            _ => false,
        }
    }

    pub fn is_vector(&self) -> bool {
        match &self.kind {
            EVTKind::Simple(vt) => vt.is_vector(),
            EVTKind::ExtendedVector { .. } => true,
            _ => false,
        }
    }

    pub fn is_floating_point(&self) -> bool {
        match &self.kind {
            EVTKind::Simple(vt) => vt.is_floating_point(),
            EVTKind::ExtendedFloat { .. } => true,
            _ => false,
        }
    }

    pub fn get_vector_num_elements(&self) -> u32 {
        match &self.kind {
            EVTKind::Simple(vt) => vt.get_vector_num_elements(),
            EVTKind::ExtendedVector { num_elems, .. } => *num_elems,
            _ => 1,
        }
    }

    pub fn get_vector_element_type(&self) -> EVT {
        match &self.kind {
            EVTKind::Simple(vt) => EVT::new(EVTKind::Simple(vt.get_vector_element_type())),
            EVTKind::ExtendedVector { elem_type, .. } => *elem_type.clone(),
            _ => MVT::i32.into(),
        }
    }

    pub fn get_scalar_type(&self) -> EVT {
        match &self.kind {
            EVTKind::Simple(vt) => EVT::new(EVTKind::Simple(vt.get_scalar_type())),
            EVTKind::ExtendedVector { elem_type, .. } => *elem_type.clone(),
            _ => self.clone(),
        }
    }
}

impl From<MVT> for EVT {
    fn from(vt: MVT) -> Self {
        Self::new(EVTKind::Simple(vt))
    }
}

impl Default for EVT {
    fn default() -> Self {
        Self::new(EVTKind::Simple(MVT::Other))
    }
}

// ============================================================================
// MVT — Machine Value Type enumeration
// ============================================================================

/// MVT (Machine Value Type) — enumeration of all simple value types
/// that can be represented in the target machine.
#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
#[allow(non_camel_case_types)]
pub enum MVT {
    // Simple types
    Other,
    i1,
    i8,
    i16,
    i32,
    i64,
    i128,
    f16,
    bf16,
    f32,
    f64,
    f80,
    f128,
    ppcf128,
    // Token types
    Token,
    Metadata,
    Untyped,
    // Vector types (generic)
    v1i1,
    v2i1,
    v4i1,
    v8i1,
    v16i1,
    v1i8,
    v2i8,
    v4i8,
    v8i8,
    v16i8,
    v32i8,
    v1i16,
    v2i16,
    v4i16,
    v8i16,
    v16i16,
    v1i32,
    v2i32,
    v4i32,
    v8i32,
    v16i32,
    v1i64,
    v2i64,
    v4i64,
    v8i64,
    v1f16,
    v2f16,
    v4f16,
    v8f16,
    v1f32,
    v2f32,
    v4f32,
    v8f32,
    v16f32,
    v1f64,
    v2f64,
    v4f64,
    v8f64,
}

impl MVT {
    pub fn get_size_in_bits(&self) -> u32 {
        match self {
            MVT::Other => 0,
            MVT::i1 => 1,
            MVT::i8 => 8,
            MVT::i16 => 16,
            MVT::i32 => 32,
            MVT::i64 => 64,
            MVT::i128 => 128,
            MVT::f16 | MVT::bf16 => 16,
            MVT::f32 => 32,
            MVT::f64 => 64,
            MVT::f80 => 80,
            MVT::f128 | MVT::ppcf128 => 128,
            MVT::Token | MVT::Metadata | MVT::Untyped => 0,
            MVT::v1i1 => 1,
            MVT::v2i1 => 2,
            MVT::v4i1 => 4,
            MVT::v8i1 => 8,
            MVT::v16i1 => 16,
            MVT::v1i8 => 8,
            MVT::v2i8 => 16,
            MVT::v4i8 => 32,
            MVT::v8i8 => 64,
            MVT::v16i8 => 128,
            MVT::v32i8 => 256,
            MVT::v1i16 => 16,
            MVT::v2i16 => 32,
            MVT::v4i16 => 64,
            MVT::v8i16 => 128,
            MVT::v16i16 => 256,
            MVT::v1i32 => 32,
            MVT::v2i32 => 64,
            MVT::v4i32 => 128,
            MVT::v8i32 => 256,
            MVT::v16i32 => 512,
            MVT::v1i64 => 64,
            MVT::v2i64 => 128,
            MVT::v4i64 => 256,
            MVT::v8i64 => 512,
            MVT::v1f16 => 16,
            MVT::v2f16 => 32,
            MVT::v4f16 => 64,
            MVT::v8f16 => 128,
            MVT::v1f32 => 32,
            MVT::v2f32 => 64,
            MVT::v4f32 => 128,
            MVT::v8f32 => 256,
            MVT::v16f32 => 512,
            MVT::v1f64 => 64,
            MVT::v2f64 => 128,
            MVT::v4f64 => 256,
            MVT::v8f64 => 512,
        }
    }

    pub fn is_integer(&self) -> bool {
        matches!(
            self,
            MVT::i1 | MVT::i8 | MVT::i16 | MVT::i32 | MVT::i64 | MVT::i128
        )
    }

    pub fn is_floating_point(&self) -> bool {
        matches!(
            self,
            MVT::f16 | MVT::bf16 | MVT::f32 | MVT::f64 | MVT::f80 | MVT::f128 | MVT::ppcf128
        )
    }

    pub fn is_vector(&self) -> bool {
        matches!(
            self,
            MVT::v1i1
                | MVT::v2i1
                | MVT::v4i1
                | MVT::v8i1
                | MVT::v16i1
                | MVT::v1i8
                | MVT::v2i8
                | MVT::v4i8
                | MVT::v8i8
                | MVT::v16i8
                | MVT::v32i8
                | MVT::v1i16
                | MVT::v2i16
                | MVT::v4i16
                | MVT::v8i16
                | MVT::v16i16
                | MVT::v1i32
                | MVT::v2i32
                | MVT::v4i32
                | MVT::v8i32
                | MVT::v16i32
                | MVT::v1i64
                | MVT::v2i64
                | MVT::v4i64
                | MVT::v8i64
                | MVT::v1f16
                | MVT::v2f16
                | MVT::v4f16
                | MVT::v8f16
                | MVT::v1f32
                | MVT::v2f32
                | MVT::v4f32
                | MVT::v8f32
                | MVT::v16f32
                | MVT::v1f64
                | MVT::v2f64
                | MVT::v4f64
                | MVT::v8f64
        )
    }

    pub fn get_vector_num_elements(&self) -> u32 {
        match self {
            MVT::v1i1
            | MVT::v1i8
            | MVT::v1i16
            | MVT::v1i32
            | MVT::v1i64
            | MVT::v1f16
            | MVT::v1f32
            | MVT::v1f64 => 1,
            MVT::v2i1
            | MVT::v2i8
            | MVT::v2i16
            | MVT::v2i32
            | MVT::v2i64
            | MVT::v2f16
            | MVT::v2f32
            | MVT::v2f64 => 2,
            MVT::v4i1
            | MVT::v4i8
            | MVT::v4i16
            | MVT::v4i32
            | MVT::v4i64
            | MVT::v4f16
            | MVT::v4f32
            | MVT::v4f64 => 4,
            MVT::v8i1
            | MVT::v8i8
            | MVT::v8i16
            | MVT::v8i32
            | MVT::v8i64
            | MVT::v8f16
            | MVT::v8f32
            | MVT::v8f64 => 8,
            MVT::v16i1 | MVT::v16i8 | MVT::v16i16 | MVT::v16i32 | MVT::v16f32 => 16,
            MVT::v32i8 => 32,
            _ => 1,
        }
    }

    pub fn get_vector_element_type(&self) -> MVT {
        match self {
            MVT::v1i1 | MVT::v2i1 | MVT::v4i1 | MVT::v8i1 | MVT::v16i1 => MVT::i1,
            MVT::v1i8 | MVT::v2i8 | MVT::v4i8 | MVT::v8i8 | MVT::v16i8 | MVT::v32i8 => MVT::i8,
            MVT::v1i16 | MVT::v2i16 | MVT::v4i16 | MVT::v8i16 | MVT::v16i16 => MVT::i16,
            MVT::v1i32 | MVT::v2i32 | MVT::v4i32 | MVT::v8i32 | MVT::v16i32 => MVT::i32,
            MVT::v1i64 | MVT::v2i64 | MVT::v4i64 | MVT::v8i64 => MVT::i64,
            MVT::v1f16 | MVT::v2f16 | MVT::v4f16 | MVT::v8f16 => MVT::f16,
            MVT::v1f32 | MVT::v2f32 | MVT::v4f32 | MVT::v8f32 | MVT::v16f32 => MVT::f32,
            MVT::v1f64 | MVT::v2f64 | MVT::v4f64 | MVT::v8f64 => MVT::f64,
            _ => MVT::i32,
        }
    }

    pub fn get_scalar_type(&self) -> MVT {
        if self.is_vector() {
            self.get_vector_element_type()
        } else {
            *self
        }
    }

    pub fn get_scalar_size_in_bits(&self) -> u32 {
        self.get_scalar_type().get_size_in_bits()
    }
}

impl Default for MVT {
    fn default() -> Self {
        MVT::Other
    }
}

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

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

    // --- SDValue tests ---

    #[test]
    fn test_sdvalue_creation() {
        let v = SDValue::new(0, 0);
        assert_eq!(v.node_id, 0);
        assert_eq!(v.res_no, 0);

        let v2 = SDValue::new(5, 1);
        assert_eq!(v2.node_id, 5);
        assert_eq!(v2.res_no, 1);
    }

    #[test]
    fn test_sdvalue_equality() {
        let a = SDValue::new(1, 0);
        let b = SDValue::new(1, 0);
        let c = SDValue::new(1, 1);
        assert_eq!(a, b);
        assert_ne!(a, c);
    }

    #[test]
    fn test_sdvalue_get_opcode() {
        let dag = SelectionDAG::new();
        let v = SDValue::new(0, 0);
        assert_eq!(v.get_opcode(&dag), SDOpcode::EntryToken);
    }

    #[test]
    fn test_sdvalue_get_value_type() {
        let dag = SelectionDAG::new();
        let v = SDValue::new(0, 0);
        assert!(v.get_value_type(&dag).is_token());
    }

    #[test]
    fn test_sdvalue_is_entry_token() {
        let dag = SelectionDAG::new();
        let v = SDValue::new(0, 0);
        assert!(v.is_entry_token(&dag));

        let dag2 = SelectionDAG::new();
        let c = &dag2.nodes[0].operands; // entry token has no operands
        assert!(c.is_empty());
    }

    // --- SDNodeFlags tests ---

    #[test]
    fn test_flags_default() {
        let f = SDNodeFlags::default();
        assert!(!f.has_no_unsigned_wrap);
        assert!(!f.has_no_signed_wrap);
        assert!(!f.has_no_nans);
        assert!(!f.has_fast_math_flags());
        assert!(!f.has_overflow_flags());
    }

    #[test]
    fn test_flags_fast_math() {
        let f = SDNodeFlags {
            has_no_nans: true,
            has_no_infs: true,
            ..SDNodeFlags::default()
        };
        assert!(f.has_fast_math_flags());
        assert!(!f.has_overflow_flags());
    }

    #[test]
    fn test_flags_overflow() {
        let f = SDNodeFlags {
            has_no_unsigned_wrap: true,
            has_no_signed_wrap: true,
            ..SDNodeFlags::default()
        };
        assert!(f.has_overflow_flags());
        assert!(!f.has_fast_math_flags());
    }

    // --- SDNode tests ---

    #[test]
    fn test_sdnode_creation() {
        let n = SDNode::new(0, SDOpcode::Add, vec![Type::i32()]);
        assert_eq!(n.id, 0);
        assert_eq!(n.opcode, SDOpcode::Add);
        assert_eq!(n.num_values, 1);
        assert_eq!(n.operands.len(), 0);
        assert_eq!(n.value_types.len(), 1);
        // Compare by kind since Type IDs may differ
        assert!(n.value_types[0].is_integer());
        assert_eq!(n.value_types[0].integer_bit_width(), 32);
    }

    #[test]
    fn test_sdnode_with_operands() {
        let n = SDNode::new(1, SDOpcode::Add, vec![Type::i32()])
            .with_operands(vec![SDValue::new(0, 0), SDValue::new(1, 0)]);
        assert_eq!(n.get_num_operands(), 2);
        assert_eq!(n.get_operand(0), Some(SDValue::new(0, 0)));
        assert_eq!(n.get_operand(1), Some(SDValue::new(1, 0)));
        assert_eq!(n.get_operand(2), None); // out of bounds
    }

    #[test]
    fn test_sdnode_flags_builder() {
        let flags = SDNodeFlags {
            has_no_unsigned_wrap: true,
            ..SDNodeFlags::default()
        };
        let n = SDNode::new(0, SDOpcode::Add, vec![Type::i32()]).with_flags(flags);
        assert!(n.flags.has_no_unsigned_wrap);
    }

    #[test]
    fn test_sdnode_get_value_type() {
        let n = SDNode::new(0, SDOpcode::Load, vec![Type::i32(), Type::token()]);
        assert!(n.get_value_type(0).unwrap().is_integer());
        assert_eq!(n.get_value_type(0).unwrap().integer_bit_width(), 32);
        assert!(n.get_value_type(1).unwrap().is_token());
        assert_eq!(n.get_value_type(2), None);
        assert_eq!(n.num_values, 2);
    }

    #[test]
    fn test_sdnode_is_binary_op() {
        assert!(SDNode::new(0, SDOpcode::Add, vec![]).is_binary_op());
        assert!(SDNode::new(0, SDOpcode::Sub, vec![]).is_binary_op());
        assert!(SDNode::new(0, SDOpcode::And, vec![]).is_binary_op());
        assert!(SDNode::new(0, SDOpcode::FAdd, vec![]).is_binary_op());
        assert!(!SDNode::new(0, SDOpcode::Load, vec![]).is_binary_op());
        assert!(!SDNode::new(0, SDOpcode::Br, vec![]).is_binary_op());
    }

    #[test]
    fn test_sdnode_is_commutative() {
        assert!(SDNode::new(0, SDOpcode::Add, vec![]).is_commutative());
        assert!(SDNode::new(0, SDOpcode::Mul, vec![]).is_commutative());
        assert!(SDNode::new(0, SDOpcode::And, vec![]).is_commutative());
        assert!(SDNode::new(0, SDOpcode::Or, vec![]).is_commutative());
        assert!(SDNode::new(0, SDOpcode::Xor, vec![]).is_commutative());
        assert!(!SDNode::new(0, SDOpcode::Sub, vec![]).is_commutative());
        assert!(!SDNode::new(0, SDOpcode::SDiv, vec![]).is_commutative());
    }

    #[test]
    fn test_sdnode_is_memory_op() {
        assert!(SDNode::new(0, SDOpcode::Load, vec![]).is_memory_op());
        assert!(SDNode::new(0, SDOpcode::Store, vec![]).is_memory_op());
        assert!(!SDNode::new(0, SDOpcode::Add, vec![]).is_memory_op());
    }

    #[test]
    fn test_sdnode_is_terminator() {
        assert!(SDNode::new(0, SDOpcode::Br, vec![]).is_terminator());
        assert!(SDNode::new(0, SDOpcode::BrCond, vec![]).is_terminator());
        assert!(SDNode::new(0, SDOpcode::Ret, vec![]).is_terminator());
        assert!(!SDNode::new(0, SDOpcode::Add, vec![]).is_terminator());
    }

    #[test]
    fn test_sdnode_is_constant() {
        assert!(SDNode::new(0, SDOpcode::Constant, vec![]).is_constant());
        assert!(SDNode::new(0, SDOpcode::ConstantFP, vec![]).is_constant());
        assert!(!SDNode::new(0, SDOpcode::Add, vec![]).is_constant());
    }

    #[test]
    fn test_sdnode_has_chain() {
        assert!(SDNode::new(0, SDOpcode::Load, vec![]).has_chain());
        assert!(SDNode::new(0, SDOpcode::Store, vec![]).has_chain());
        assert!(SDNode::new(0, SDOpcode::Ret, vec![]).has_chain());
        assert!(SDNode::new(0, SDOpcode::Br, vec![]).has_chain());
        assert!(SDNode::new(0, SDOpcode::Call, vec![]).has_chain());
        assert!(SDNode::new(0, SDOpcode::EntryToken, vec![]).has_chain());
        assert!(!SDNode::new(0, SDOpcode::Add, vec![]).has_chain());
        assert!(!SDNode::new(0, SDOpcode::Constant, vec![]).has_chain());
    }

    #[test]
    fn test_sdnode_is_conversion() {
        assert!(SDNode::new(0, SDOpcode::ZExt, vec![]).is_conversion());
        assert!(SDNode::new(0, SDOpcode::SExt, vec![]).is_conversion());
        assert!(SDNode::new(0, SDOpcode::Trunc, vec![]).is_conversion());
        assert!(SDNode::new(0, SDOpcode::Bitcast, vec![]).is_conversion());
        assert!(!SDNode::new(0, SDOpcode::Add, vec![]).is_conversion());
    }

    // --- SelectionDAG tests ---

    #[test]
    fn test_dag_creation() {
        let dag = SelectionDAG::new();
        assert_eq!(dag.num_nodes(), 1); // EntryToken
        assert_eq!(dag.num_all_nodes(), 1);
        assert!(dag.root.is_none());
        assert_eq!(dag.get_node(dag.entry_token).opcode, SDOpcode::EntryToken);
    }

    #[test]
    fn test_dag_with_target() {
        let dag = SelectionDAG::with_target("x86_64-unknown-linux-gnu");
        assert_eq!(dag.target.as_deref(), Some("x86_64-unknown-linux-gnu"));
    }

    #[test]
    fn test_dag_add_node() {
        let mut dag = SelectionDAG::new();
        let val = dag.add_node(
            SDOpcode::Add,
            vec![Type::i32()],
            vec![dag.entry_token, dag.entry_token],
        );
        assert_eq!(dag.num_nodes(), 2);
        assert_eq!(dag.get_node(val).opcode, SDOpcode::Add);
    }

    #[test]
    fn test_dag_add_node_with_values() {
        let mut dag = SelectionDAG::new();
        let val = dag.add_node_with_values(
            SDOpcode::Load,
            vec![Type::i32(), Type::token()],
            vec![dag.entry_token, dag.entry_token],
            2,
        );
        assert_eq!(dag.num_nodes(), 2);
        let node = dag.get_node(val);
        assert_eq!(node.opcode, SDOpcode::Load);
        assert_eq!(node.num_values, 2);
    }

    #[test]
    fn test_dag_set_and_get_root() {
        let mut dag = SelectionDAG::new();
        assert!(dag.get_root().is_none());

        let ret_val = dag.add_node(SDOpcode::Ret, vec![], vec![dag.entry_token]);
        dag.set_root(ret_val);
        assert_eq!(dag.get_root(), Some(ret_val));
    }

    #[test]
    fn test_dag_get_constant_dedup() {
        let mut dag = SelectionDAG::new();
        let c1 = dag.get_constant(42, Type::i32());
        let c2 = dag.get_constant(42, Type::i32());
        // Same value + type should return the same SDValue
        assert_eq!(c1, c2);
        // Node count should only increase by 1 (the constant itself)
        assert_eq!(dag.num_nodes(), 2); // EntryToken + Constant
    }

    #[test]
    fn test_dag_get_constant_different_types() {
        let mut dag = SelectionDAG::new();
        let c_i32 = dag.get_constant(7, Type::i32());
        let c_i64 = dag.get_constant(7, Type::i64());
        // Different types → different nodes
        assert_ne!(c_i32, c_i64);
        assert_eq!(dag.num_nodes(), 3); // EntryToken + 2 constants
    }

    #[test]
    fn test_dag_get_constant_different_values() {
        let mut dag = SelectionDAG::new();
        let c1 = dag.get_constant(10, Type::i32());
        let c2 = dag.get_constant(20, Type::i32());
        assert_ne!(c1, c2);
        assert_eq!(dag.num_nodes(), 3); // EntryToken + 2 constants
    }

    #[test]
    fn test_dag_get_constant_fp() {
        let mut dag = SelectionDAG::new();
        let c = dag.get_constant_fp(0x3FF0000000000000, Type::double()); // 1.0
        assert_eq!(dag.num_nodes(), 2);
        let node = dag.get_node(c);
        assert_eq!(node.opcode, SDOpcode::ConstantFP);
        // Dedup test
        let c2 = dag.get_constant_fp(0x3FF0000000000000, Type::double());
        assert_eq!(c, c2);
    }

    #[test]
    fn test_dag_get_register() {
        let mut dag = SelectionDAG::new();
        let reg = dag.get_register(Type::i32());
        assert_eq!(dag.get_node(reg).opcode, SDOpcode::Register);
        assert_eq!(dag.num_nodes(), 2);
    }

    #[test]
    fn test_dag_get_undef() {
        let mut dag = SelectionDAG::new();
        let undef = dag.get_undef(Type::i64());
        assert_eq!(dag.get_node(undef).opcode, SDOpcode::Undef);
        assert!(dag.get_node(undef).is_undef());
    }

    #[test]
    fn test_dag_get_copy_to_reg() {
        let mut dag = SelectionDAG::new();
        let val = dag.get_register(Type::i32());
        let copy = dag.get_copy_to_reg(dag.entry_token, val);
        assert_eq!(dag.get_node(copy).opcode, SDOpcode::CopyToReg);
    }

    #[test]
    fn test_dag_get_copy_from_reg() {
        let mut dag = SelectionDAG::new();
        let copy = dag.get_copy_from_reg(dag.entry_token, Type::i32());
        assert_eq!(dag.get_node(copy).opcode, SDOpcode::CopyFromReg);
        assert_eq!(dag.get_node(copy).num_values, 2);
    }

    #[test]
    fn test_dag_get_load() {
        let mut dag = SelectionDAG::new();
        let ptr = dag.get_register(Type::pointer(0));
        let load = dag.get_load(dag.entry_token, ptr, Type::i32());
        assert_eq!(dag.get_node(load).opcode, SDOpcode::Load);
        assert_eq!(dag.get_node(load).num_values, 2);
        // Chain is at res_no=1
        let chain = dag.get_load_chain(load);
        assert_eq!(chain.node_id, load.node_id);
        assert_eq!(chain.res_no, 1);
    }

    #[test]
    fn test_dag_get_store() {
        let mut dag = SelectionDAG::new();
        let val = dag.get_register(Type::i32());
        let ptr = dag.get_register(Type::pointer(0));
        let store = dag.get_store(dag.entry_token, val, ptr);
        assert_eq!(dag.get_node(store).opcode, SDOpcode::Store);
        assert_eq!(dag.get_node(store).num_values, 1);
    }

    #[test]
    fn test_dag_get_binary_op() {
        let mut dag = SelectionDAG::new();
        let lhs = dag.get_constant(10, Type::i32());
        let rhs = dag.get_constant(20, Type::i32());
        let add = dag.get_binary_op(SDOpcode::Add, Type::i32(), lhs, rhs);
        let node = dag.get_node(add);
        assert_eq!(node.opcode, SDOpcode::Add);
        assert_eq!(node.get_num_operands(), 2);
    }

    #[test]
    fn test_dag_replace_all_uses() {
        let mut dag = SelectionDAG::new();
        let c1 = dag.get_constant(10, Type::i32());
        let c2 = dag.get_constant(20, Type::i32());
        let add = dag.get_binary_op(SDOpcode::Add, Type::i32(), c1, c2);

        // Before replacement
        assert_eq!(dag.get_node(add).get_operand(0), Some(c1));
        assert_eq!(dag.get_node(add).get_operand(1), Some(c2));

        // Replace c1 with c2
        dag.replace_all_uses_with(c1, c2);
        assert_eq!(dag.get_node(add).get_operand(0), Some(c2));
        assert_eq!(dag.get_node(add).get_operand(1), Some(c2));
    }

    #[test]
    fn test_dag_delete_node() {
        let mut dag = SelectionDAG::new();
        let val = dag.get_register(Type::i32());
        assert_eq!(dag.num_nodes(), 2);

        dag.delete_node(val);
        assert_eq!(dag.get_node(val).operands.len(), 0);
        // Node still exists but is cleared
        assert_eq!(dag.num_nodes(), 2);
    }

    #[test]
    fn test_sdvalue_has_one_use() {
        let mut dag = SelectionDAG::new();
        let c = dag.get_constant(42, Type::i32());
        // Initially, the constant has one use (in the DAG, but our count walks nodes)
        // Actually there are no uses yet since no node references it
        assert!(!c.has_one_use(&dag)); // 0 uses

        let _add = dag.get_binary_op(SDOpcode::Add, Type::i32(), c, c);
        // Now c is used twice by the add node
        assert!(!c.has_one_use(&dag)); // 2 uses

        let _another = dag.get_binary_op(SDOpcode::Sub, Type::i32(), c, dag.entry_token);
        assert!(!c.has_one_use(&dag)); // 3 uses
    }

    #[test]
    fn test_opcode_as_str() {
        assert_eq!(SDOpcode::Add.as_str(), "Add");
        assert_eq!(SDOpcode::Store.as_str(), "Store");
        assert_eq!(SDOpcode::EntryToken.as_str(), "EntryToken");
        assert_eq!(SDOpcode::VectorShuffle.as_str(), "VectorShuffle");
        assert_eq!(SDOpcode::FpExtend.as_str(), "FpExtend");
    }

    #[test]
    fn test_sdnode_get_chain_index() {
        assert_eq!(
            SDNode::new(0, SDOpcode::Load, vec![]).get_chain_index(),
            Some(0)
        );
        assert_eq!(
            SDNode::new(0, SDOpcode::Store, vec![]).get_chain_index(),
            Some(0)
        );
        assert_eq!(
            SDNode::new(0, SDOpcode::Call, vec![]).get_chain_index(),
            Some(0)
        );
        assert_eq!(
            SDNode::new(0, SDOpcode::Ret, vec![]).get_chain_index(),
            Some(0)
        );
        assert_eq!(
            SDNode::new(0, SDOpcode::Add, vec![]).get_chain_index(),
            None
        );
        assert_eq!(
            SDNode::new(0, SDOpcode::EntryToken, vec![]).get_chain_index(),
            None
        );
    }

    #[test]
    fn test_dag_is_empty() {
        let dag = SelectionDAG::new();
        assert!(dag.is_empty());

        let mut dag2 = SelectionDAG::new();
        dag2.get_register(Type::i32());
        assert!(!dag2.is_empty());
    }

    #[test]
    fn test_full_opcode_coverage() {
        // Verify all opcodes have a string representation
        let opcodes = [
            SDOpcode::Constant,
            SDOpcode::ConstantFP,
            SDOpcode::TargetConstant,
            SDOpcode::Register,
            SDOpcode::CopyFromReg,
            SDOpcode::CopyToReg,
            SDOpcode::Load,
            SDOpcode::Store,
            SDOpcode::AtomicLoad,
            SDOpcode::AtomicStore,
            SDOpcode::AtomicCmpSwap,
            SDOpcode::AtomicRMW,
            SDOpcode::Add,
            SDOpcode::Sub,
            SDOpcode::Mul,
            SDOpcode::UDiv,
            SDOpcode::SDiv,
            SDOpcode::URem,
            SDOpcode::SRem,
            SDOpcode::FAdd,
            SDOpcode::FSub,
            SDOpcode::FMul,
            SDOpcode::FDiv,
            SDOpcode::And,
            SDOpcode::Or,
            SDOpcode::Xor,
            SDOpcode::Shl,
            SDOpcode::Sra,
            SDOpcode::Srl,
            SDOpcode::SetCC,
            SDOpcode::Br,
            SDOpcode::BrCond,
            SDOpcode::Ret,
            SDOpcode::Call,
            SDOpcode::Undef,
            SDOpcode::TokenFactor,
            SDOpcode::EntryToken,
        ];
        for op in &opcodes {
            let s = op.as_str();
            assert!(!s.is_empty(), "Opcode {:?} has empty string", op);
        }
    }
}