llvm-native-core 0.1.10

//! ARC Instruction Selection — maps LLVM IR operations to ARC instructions.
//!
//! The ARC is a 32-bit target with rich addressing modes, 3-operand
//! instructions, and optional 16-bit compact instructions. This selector
//! performs legalization and lowering from target-independent DAG nodes
//! to ARC-specific operations.
//!
//! Clean-room reconstruction from the Synopsys ARC Programmer's Reference
//! Manual and the GCC `arc` backend.

use std::collections::HashMap;

use crate::arc::arc_instr_info::{ArcInstrInfo, ArcOpcode};

// ============================================================================
// Selection DAG Opcodes
// ============================================================================

/// Simplified ISel DAG opcodes for ARC.
#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
pub enum ArcSelOpcode {
    Add,
    Sub,
    And,
    Or,
    Xor,
    Shl,
    Sra,
    Srl,
    Mul,
    UDiv,
    SDiv,
    URem,
    SRem,
    Load,
    Store,
    LoadI8,
    LoadI16,
    LoadI32,
    StoreI8,
    StoreI16,
    StoreI32,
    Br,
    BrCond,
    Call,
    Return,
    Copy,
    CopyToReg,
    RegSequence,
    Constant,
    Setcc,
    FrameIndex,
    Abs,
    Neg,
    Sext,
    Zext,
    Min,
    Max,
}

/// Operand type for ARC.
#[derive(Debug, Clone)]
pub enum ArcOperand {
    Reg(u8),     // 0..31 for r0-r31
    RegPair(u8), // even register for 64-bit pair
    Imm32(i32),
    Imm16(u16),
    Imm8(u8),
    Imm5(u8),
    Shim32(i32), // short immediate (signed 9-bit)
    Label(String),
    Global(String),
}

/// A single ISel DAG node.
#[derive(Debug, Clone)]
pub struct ArcSelNode {
    pub opcode: ArcSelOpcode,
    pub operands: Vec<ArcOperand>,
    pub result_reg: Option<u8>,
    pub can_use_short_instr: bool,
}

// ============================================================================
// ARC Instruction Selector
// ============================================================================

/// Converts target-independent operations into ARC instructions.
pub struct ArcInstructionSelector {
    instr_info: ArcInstrInfo,
}

impl ArcInstructionSelector {
    pub fn new() -> Self {
        ArcInstructionSelector {
            instr_info: ArcInstrInfo::new(),
        }
    }

    /// Select ARC instructions for a sequence of ISel DAG nodes.
    pub fn select(&self, nodes: &[ArcSelNode]) -> Vec<ArcOpcode> {
        let mut selected = Vec::new();
        for node in nodes {
            if let Some(opcodes) = self.select_node(node) {
                selected.extend(opcodes);
            }
        }
        selected
    }

    fn select_node(&self, node: &ArcSelNode) -> Option<Vec<ArcOpcode>> {
        let short = node.can_use_short_instr;
        match node.opcode {
            ArcSelOpcode::Add => {
                if short {
                    Some(vec![ArcOpcode::ADD1, ArcOpcode::ADD2, ArcOpcode::ADD3])
                } else {
                    Some(vec![ArcOpcode::ADD])
                }
            }
            ArcSelOpcode::Sub => {
                if short {
                    Some(vec![ArcOpcode::SUB1, ArcOpcode::SUB2, ArcOpcode::SUB3])
                } else {
                    Some(vec![ArcOpcode::SUB])
                }
            }
            ArcSelOpcode::And => Some(vec![ArcOpcode::AND]),
            ArcSelOpcode::Or => Some(vec![ArcOpcode::OR]),
            ArcSelOpcode::Xor => Some(vec![ArcOpcode::XOR]),
            ArcSelOpcode::Shl => {
                if short {
                    Some(vec![ArcOpcode::ASL1])
                } else {
                    Some(vec![ArcOpcode::ASL])
                }
            }
            ArcSelOpcode::Sra => {
                if short {
                    Some(vec![ArcOpcode::ASR1])
                } else {
                    Some(vec![ArcOpcode::ASR])
                }
            }
            ArcSelOpcode::Srl => {
                if short {
                    Some(vec![ArcOpcode::LSR1])
                } else {
                    Some(vec![ArcOpcode::LSR])
                }
            }
            ArcSelOpcode::Mul => Some(self.select_mul(node)),
            ArcSelOpcode::UDiv => Some(vec![ArcOpcode::DIV]),
            ArcSelOpcode::SDiv => Some(vec![ArcOpcode::DIV]),
            ArcSelOpcode::URem | ArcSelOpcode::SRem => {
                // Remainder: div + msub sequence
                Some(vec![ArcOpcode::DIV])
            }
            ArcSelOpcode::Load => {
                if short {
                    Some(vec![ArcOpcode::LD_S])
                } else {
                    Some(vec![ArcOpcode::LD])
                }
            }
            ArcSelOpcode::Store => {
                if short {
                    Some(vec![ArcOpcode::ST_S])
                } else {
                    Some(vec![ArcOpcode::ST])
                }
            }
            ArcSelOpcode::LoadI8 => {
                if short {
                    Some(vec![ArcOpcode::LDB_S])
                } else {
                    Some(vec![ArcOpcode::LDB])
                }
            }
            ArcSelOpcode::LoadI16 => Some(vec![ArcOpcode::LDW]),
            ArcSelOpcode::LoadI32 => Some(vec![ArcOpcode::LD]),
            ArcSelOpcode::StoreI8 => {
                if short {
                    Some(vec![ArcOpcode::STB_S])
                } else {
                    Some(vec![ArcOpcode::STB])
                }
            }
            ArcSelOpcode::StoreI16 => Some(vec![ArcOpcode::STW]),
            ArcSelOpcode::StoreI32 => Some(vec![ArcOpcode::ST]),
            ArcSelOpcode::Br => {
                if short {
                    Some(vec![ArcOpcode::B_S])
                } else {
                    Some(vec![ArcOpcode::B])
                }
            }
            ArcSelOpcode::BrCond => Some(vec![ArcOpcode::BR]),
            ArcSelOpcode::Call => {
                if short {
                    Some(vec![ArcOpcode::BL_S])
                } else {
                    Some(vec![ArcOpcode::BL])
                }
            }
            ArcSelOpcode::Return => Some(vec![ArcOpcode::J]),
            ArcSelOpcode::Copy => {
                if short {
                    Some(vec![ArcOpcode::MOV_S])
                } else {
                    Some(vec![ArcOpcode::MOV])
                }
            }
            ArcSelOpcode::CopyToReg => {
                if short {
                    Some(vec![ArcOpcode::MOV_S])
                } else {
                    Some(vec![ArcOpcode::MOV])
                }
            }
            ArcSelOpcode::RegSequence => Some(vec![ArcOpcode::MOV]),
            ArcSelOpcode::Constant => Some(self.select_constant(node)),
            ArcSelOpcode::Setcc => Some(vec![ArcOpcode::CMP]),
            ArcSelOpcode::FrameIndex => Some(vec![ArcOpcode::ADD]),
            ArcSelOpcode::Abs => Some(vec![ArcOpcode::ABS]),
            ArcSelOpcode::Neg => Some(vec![ArcOpcode::NEG]),
            ArcSelOpcode::Sext => Some(vec![ArcOpcode::SEXB]),
            ArcSelOpcode::Zext => Some(vec![ArcOpcode::EXTB]),
            ArcSelOpcode::Min => Some(vec![ArcOpcode::MIN]),
            ArcSelOpcode::Max => Some(vec![ArcOpcode::MAX]),
        }
    }

    fn select_mul(&self, _node: &ArcSelNode) -> Vec<ArcOpcode> {
        // ARC has hardware MUL64/MULU64 for 32x32=64
        vec![ArcOpcode::MUL64]
    }

    fn select_constant(&self, node: &ArcSelNode) -> Vec<ArcOpcode> {
        // Check if immediate fits in MOVHI range (upper 16 bits)
        if let Some(ArcOperand::Imm32(val)) = node.operands.first() {
            let v = *val as u32;
            if (v & 0xFFFF) == 0 && v != 0 {
                // Pure upper-half: use MOVHI
                return vec![ArcOpcode::MOVHI];
            }
            if (-512..=511).contains(val) {
                // Short immediate range (9-bit signed): MOV_S
                return vec![ArcOpcode::MOV_S];
            }
        }
        // Default: MOV with full 32-bit immediate
        vec![ArcOpcode::MOV]
    }

    /// Legalize a 64-bit operation into 32-bit ARC instruction pairs.
    pub fn legalize_i64_add(&self) -> Vec<ArcOpcode> {
        vec![ArcOpcode::ADD, ArcOpcode::ADDS]
    }

    /// Legalize a 64-bit subtraction.
    pub fn legalize_i64_sub(&self) -> Vec<ArcOpcode> {
        vec![ArcOpcode::SUB, ArcOpcode::SUBS]
    }

    /// Load a 32-bit immediate via MOVHI+MOV sequence.
    pub fn emit_load_i32(&self, imm: u32) -> Vec<(ArcOpcode, u16)> {
        let hi = ((imm >> 16) & 0xFFFF) as u16;
        let lo = (imm & 0xFFFF) as u16;
        if hi != 0 {
            vec![(ArcOpcode::MOVHI, hi), (ArcOpcode::MOV, lo)]
        } else {
            vec![(ArcOpcode::MOV, lo)]
        }
    }

    /// Check if an operation is legal on ARC without library call.
    pub fn is_legal(&self, node: &ArcSelNode) -> bool {
        match node.opcode {
            ArcSelOpcode::URem | ArcSelOpcode::SRem => false,
            _ => true,
        }
    }

    /// Check if selection for a node requires a runtime library call.
    pub fn requires_libcall(&self, node: &ArcSelNode) -> bool {
        matches!(node.opcode, ArcSelOpcode::URem | ArcSelOpcode::SRem)
    }

    /// Get the instruction info reference.
    pub fn get_instr_info(&self) -> &ArcInstrInfo {
        &self.instr_info
    }

    /// Get the condition code opcode from an ICC condition.
    pub fn get_cond_branch(&self, cond: &str) -> Option<ArcOpcode> {
        match cond {
            "eq" => Some(ArcOpcode::BEQ),
            "ne" => Some(ArcOpcode::BNE),
            "gt" => Some(ArcOpcode::BGT),
            "ge" => Some(ArcOpcode::BGE),
            "lt" => Some(ArcOpcode::BLT),
            "le" => Some(ArcOpcode::BLE),
            "hi" => Some(ArcOpcode::BHI),
            "hs" => Some(ArcOpcode::BHS),
            "lo" => Some(ArcOpcode::BLO),
            "ls" => Some(ArcOpcode::BLS),
            _ => None,
        }
    }
}

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

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

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

    fn node(opcode: ArcSelOpcode) -> ArcSelNode {
        ArcSelNode {
            opcode,
            operands: vec![],
            result_reg: None,
            can_use_short_instr: false,
        }
    }

    fn short_node(opcode: ArcSelOpcode) -> ArcSelNode {
        ArcSelNode {
            opcode,
            operands: vec![],
            result_reg: None,
            can_use_short_instr: true,
        }
    }

    #[test]
    fn test_select_add() {
        let isel = ArcInstructionSelector::new();
        let result = isel.select(&[node(ArcSelOpcode::Add)]);
        assert_eq!(result, vec![ArcOpcode::ADD]);
    }

    #[test]
    fn test_select_add_short() {
        let isel = ArcInstructionSelector::new();
        let result = isel.select(&[short_node(ArcSelOpcode::Add)]);
        assert_eq!(
            result,
            vec![ArcOpcode::ADD1, ArcOpcode::ADD2, ArcOpcode::ADD3]
        );
    }

    #[test]
    fn test_select_sub() {
        let isel = ArcInstructionSelector::new();
        let result = isel.select(&[node(ArcSelOpcode::Sub)]);
        assert_eq!(result, vec![ArcOpcode::SUB]);
    }

    #[test]
    fn test_select_logical() {
        let isel = ArcInstructionSelector::new();
        assert_eq!(
            isel.select(&[node(ArcSelOpcode::And)]),
            vec![ArcOpcode::AND]
        );
        assert_eq!(isel.select(&[node(ArcSelOpcode::Or)]), vec![ArcOpcode::OR]);
        assert_eq!(
            isel.select(&[node(ArcSelOpcode::Xor)]),
            vec![ArcOpcode::XOR]
        );
    }

    #[test]
    fn test_select_shifts() {
        let isel = ArcInstructionSelector::new();
        assert_eq!(
            isel.select(&[node(ArcSelOpcode::Shl)]),
            vec![ArcOpcode::ASL]
        );
        assert_eq!(
            isel.select(&[node(ArcSelOpcode::Sra)]),
            vec![ArcOpcode::ASR]
        );
        assert_eq!(
            isel.select(&[node(ArcSelOpcode::Srl)]),
            vec![ArcOpcode::LSR]
        );
    }

    #[test]
    fn test_select_shifts_short() {
        let isel = ArcInstructionSelector::new();
        assert_eq!(
            isel.select(&[short_node(ArcSelOpcode::Shl)]),
            vec![ArcOpcode::ASL1]
        );
        assert_eq!(
            isel.select(&[short_node(ArcSelOpcode::Sra)]),
            vec![ArcOpcode::ASR1]
        );
        assert_eq!(
            isel.select(&[short_node(ArcSelOpcode::Srl)]),
            vec![ArcOpcode::LSR1]
        );
    }

    #[test]
    fn test_select_load_store() {
        let isel = ArcInstructionSelector::new();
        assert_eq!(
            isel.select(&[node(ArcSelOpcode::Load)]),
            vec![ArcOpcode::LD]
        );
        assert_eq!(
            isel.select(&[node(ArcSelOpcode::Store)]),
            vec![ArcOpcode::ST]
        );
    }

    #[test]
    fn test_select_load_store_short() {
        let isel = ArcInstructionSelector::new();
        assert_eq!(
            isel.select(&[short_node(ArcSelOpcode::Load)]),
            vec![ArcOpcode::LD_S]
        );
        assert_eq!(
            isel.select(&[short_node(ArcSelOpcode::Store)]),
            vec![ArcOpcode::ST_S]
        );
    }

    #[test]
    fn test_select_branch() {
        let isel = ArcInstructionSelector::new();
        assert_eq!(isel.select(&[node(ArcSelOpcode::Br)]), vec![ArcOpcode::B]);
        assert_eq!(
            isel.select(&[short_node(ArcSelOpcode::Br)]),
            vec![ArcOpcode::B_S]
        );
    }

    #[test]
    fn test_select_call_return() {
        let isel = ArcInstructionSelector::new();
        assert_eq!(
            isel.select(&[node(ArcSelOpcode::Call)]),
            vec![ArcOpcode::BL]
        );
        assert_eq!(
            isel.select(&[node(ArcSelOpcode::Return)]),
            vec![ArcOpcode::J]
        );
        assert_eq!(
            isel.select(&[short_node(ArcSelOpcode::Call)]),
            vec![ArcOpcode::BL_S]
        );
    }

    #[test]
    fn test_select_copy() {
        let isel = ArcInstructionSelector::new();
        assert_eq!(
            isel.select(&[node(ArcSelOpcode::Copy)]),
            vec![ArcOpcode::MOV]
        );
        assert_eq!(
            isel.select(&[short_node(ArcSelOpcode::Copy)]),
            vec![ArcOpcode::MOV_S]
        );
    }

    #[test]
    fn test_select_constant_small() {
        let isel = ArcInstructionSelector::new();
        let n = ArcSelNode {
            opcode: ArcSelOpcode::Constant,
            operands: vec![ArcOperand::Imm32(42)],
            result_reg: None,
            can_use_short_instr: false,
        };
        assert_eq!(isel.select(&[n]), vec![ArcOpcode::MOV_S]);
    }

    #[test]
    fn test_select_constant_movhi() {
        let isel = ArcInstructionSelector::new();
        let n = ArcSelNode {
            opcode: ArcSelOpcode::Constant,
            operands: vec![ArcOperand::Imm32(0x10000)],
            result_reg: None,
            can_use_short_instr: false,
        };
        assert_eq!(isel.select(&[n]), vec![ArcOpcode::MOVHI]);
    }

    #[test]
    fn test_select_unary() {
        let isel = ArcInstructionSelector::new();
        assert_eq!(
            isel.select(&[node(ArcSelOpcode::Abs)]),
            vec![ArcOpcode::ABS]
        );
        assert_eq!(
            isel.select(&[node(ArcSelOpcode::Neg)]),
            vec![ArcOpcode::NEG]
        );
    }

    #[test]
    fn test_select_min_max() {
        let isel = ArcInstructionSelector::new();
        assert_eq!(
            isel.select(&[node(ArcSelOpcode::Min)]),
            vec![ArcOpcode::MIN]
        );
        assert_eq!(
            isel.select(&[node(ArcSelOpcode::Max)]),
            vec![ArcOpcode::MAX]
        );
    }

    #[test]
    fn test_select_extension() {
        let isel = ArcInstructionSelector::new();
        assert_eq!(
            isel.select(&[node(ArcSelOpcode::Sext)]),
            vec![ArcOpcode::SEXB]
        );
        assert_eq!(
            isel.select(&[node(ArcSelOpcode::Zext)]),
            vec![ArcOpcode::EXTB]
        );
    }

    #[test]
    fn test_select_div_requires_libcall() {
        let isel = ArcInstructionSelector::new();
        let div_node = node(ArcSelOpcode::UDiv);
        assert_eq!(isel.select(&[div_node]), vec![ArcOpcode::DIV]);
        assert!(!isel.requires_libcall(&node(ArcSelOpcode::UDiv)));
        assert!(isel.requires_libcall(&node(ArcSelOpcode::URem)));
        assert!(!isel.requires_libcall(&node(ArcSelOpcode::Add)));
    }

    #[test]
    fn test_is_legal() {
        let isel = ArcInstructionSelector::new();
        assert!(isel.is_legal(&node(ArcSelOpcode::Add)));
        assert!(!isel.is_legal(&node(ArcSelOpcode::URem)));
    }

    #[test]
    fn test_legalize_i64_add() {
        let isel = ArcInstructionSelector::new();
        let ops = isel.legalize_i64_add();
        assert_eq!(ops, vec![ArcOpcode::ADD, ArcOpcode::ADDS]);
    }

    #[test]
    fn test_legalize_i64_sub() {
        let isel = ArcInstructionSelector::new();
        let ops = isel.legalize_i64_sub();
        assert_eq!(ops, vec![ArcOpcode::SUB, ArcOpcode::SUBS]);
    }

    #[test]
    fn test_emit_load_i32() {
        let isel = ArcInstructionSelector::new();
        // Low 16 bits only
        let ops = isel.emit_load_i32(0xABCD);
        assert_eq!(ops.len(), 1);
        assert_eq!(ops[0].1, 0xABCD);
        // Full 32-bit
        let ops = isel.emit_load_i32(0x1234ABCD);
        assert_eq!(ops.len(), 2);
        assert_eq!(ops[0], (ArcOpcode::MOVHI, 0x1234));
        assert_eq!(ops[1], (ArcOpcode::MOV, 0xABCD));
    }

    #[test]
    fn test_get_cond_branch() {
        let isel = ArcInstructionSelector::new();
        assert_eq!(isel.get_cond_branch("eq"), Some(ArcOpcode::BEQ));
        assert_eq!(isel.get_cond_branch("ne"), Some(ArcOpcode::BNE));
        assert_eq!(isel.get_cond_branch("gt"), Some(ArcOpcode::BGT));
        assert_eq!(isel.get_cond_branch("le"), Some(ArcOpcode::BLE));
        assert_eq!(isel.get_cond_branch("xx"), None);
    }

    #[test]
    fn test_get_instr_info() {
        let isel = ArcInstructionSelector::new();
        let info = isel.get_instr_info();
        assert!(info.get_desc(ArcOpcode::ADD).is_some());
    }

    #[test]
    fn test_default() {
        let isel = ArcInstructionSelector::default();
        let info = isel.get_instr_info();
        assert!(info.get_desc(ArcOpcode::SUB).is_some());
    }
}