llvm-native-core 0.1.10

//! AVR Instruction Selection — maps LLVM IR operations to AVR instructions.
//!
//! The AVR is an 8-bit target, so most operations use pairs of 8-bit
//! registers to emulate 16-bit values. This selector performs legalization
//! and lowering from target-independent DAG nodes to AVR-specific operations.

use std::collections::HashMap;

use crate::avr::avr_instr_info::{AvrInstrInfo, AvrOpcode};

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

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

/// Operand type for AVR.
#[derive(Debug, Clone)]
pub enum AvrOperand {
    Reg(u8),     // 0..31 for r0-r31
    RegPair(u8), // even register for a pair (r0:r1, r2:r3, ...)
    Imm8(u8),
    Imm16(u16),
    Label(String),
}

/// A single ISel DAG node.
#[derive(Debug, Clone)]
pub struct AvrSelNode {
    pub opcode: AvrSelOpcode,
    pub operands: Vec<AvrOperand>,
    pub result_reg: Option<u8>,
}

// ============================================================================
//  AVR Instruction Selector
// ============================================================================

/// Converts target-independent operations into AVR instructions.
pub struct AvrInstructionSelector {
    instr_info: AvrInstrInfo,
}

impl AvrInstructionSelector {
    pub fn new() -> Self {
        AvrInstructionSelector {
            instr_info: AvrInstrInfo::new(),
        }
    }

    /// Select AVR instructions for a sequence of ISel DAG nodes.
    pub fn select(&self, nodes: &[AvrSelNode]) -> Vec<AvrOpcode> {
        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: &AvrSelNode) -> Option<Vec<AvrOpcode>> {
        match node.opcode {
            AvrSelOpcode::Add => Some(vec![AvrOpcode::ADD]),
            AvrSelOpcode::Sub => Some(vec![AvrOpcode::SUB]),
            AvrSelOpcode::And => Some(vec![AvrOpcode::AND]),
            AvrSelOpcode::Or => Some(vec![AvrOpcode::OR]),
            AvrSelOpcode::Xor => Some(vec![AvrOpcode::EOR]),
            AvrSelOpcode::Shl => Some(vec![AvrOpcode::LSL]),
            AvrSelOpcode::Sra => Some(vec![AvrOpcode::ASR]),
            AvrSelOpcode::Srl => Some(vec![AvrOpcode::LSR]),
            AvrSelOpcode::Mul => Some(self.select_mul(node)),
            AvrSelOpcode::UDiv | AvrSelOpcode::SDiv | AvrSelOpcode::URem | AvrSelOpcode::SRem => {
                // Division/remainder requires a runtime library call
                Some(vec![AvrOpcode::RCALL])
            }
            AvrSelOpcode::Load => Some(vec![AvrOpcode::LD]),
            AvrSelOpcode::Store => Some(vec![AvrOpcode::ST]),
            AvrSelOpcode::LoadI8 => Some(vec![AvrOpcode::LD]),
            AvrSelOpcode::LoadI16 => Some(vec![AvrOpcode::LDS]),
            AvrSelOpcode::StoreI8 => Some(vec![AvrOpcode::ST]),
            AvrSelOpcode::StoreI16 => Some(vec![AvrOpcode::STS]),
            AvrSelOpcode::Br => Some(vec![AvrOpcode::RJMP]),
            AvrSelOpcode::BrCond => Some(vec![AvrOpcode::BRBS]),
            AvrSelOpcode::Call => Some(vec![AvrOpcode::CALL]),
            AvrSelOpcode::Return => Some(vec![AvrOpcode::RET]),
            AvrSelOpcode::Copy => Some(vec![AvrOpcode::MOV]),
            AvrSelOpcode::CopyToReg => Some(vec![AvrOpcode::MOV]),
            AvrSelOpcode::RegSequence => Some(vec![AvrOpcode::MOV]),
            AvrSelOpcode::Constant => Some(vec![AvrOpcode::LDI]),
            AvrSelOpcode::Setcc => Some(vec![AvrOpcode::BSET]),
            AvrSelOpcode::FrameIndex => Some(vec![AvrOpcode::ADIW]), // adjust frame pointer
        }
    }

    fn select_mul(&self, _node: &AvrSelNode) -> Vec<AvrOpcode> {
        // AVR has hardware MUL for 8x8=16
        vec![AvrOpcode::MUL]
    }

    /// Legalize a 16-bit operation into 8-bit AVR instruction pairs.
    pub fn legalize_i16_add(&self) -> Vec<AvrOpcode> {
        // Add low bytes, then add with carry high bytes
        vec![AvrOpcode::ADD, AvrOpcode::ADC]
    }

    /// Legalize a 16-bit subtraction.
    pub fn legalize_i16_sub(&self) -> Vec<AvrOpcode> {
        vec![AvrOpcode::SUB, AvrOpcode::SBC]
    }

    /// Legalize a 16-bit AND.
    pub fn legalize_i16_and(&self) -> Vec<AvrOpcode> {
        vec![AvrOpcode::AND, AvrOpcode::AND]
    }

    /// Legalize a 16-bit OR.
    pub fn legalize_i16_or(&self) -> Vec<AvrOpcode> {
        vec![AvrOpcode::OR, AvrOpcode::OR]
    }

    /// Load immediate value into an even/odd register pair.
    pub fn emit_load_i16(&self, imm: u16) -> Vec<(AvrOpcode, u8)> {
        let lo = (imm & 0xFF) as u8;
        let hi = ((imm >> 8) & 0xFF) as u8;
        // LDI into high/low pairs: ldi r25, hi; ldi r24, lo
        vec![(AvrOpcode::LDI, hi), (AvrOpcode::LDI, lo)]
    }

    /// Check if an operation is legal on AVR without splitting.
    pub fn is_legal(&self, node: &AvrSelNode) -> bool {
        match node.opcode {
            AvrSelOpcode::UDiv | AvrSelOpcode::SDiv | AvrSelOpcode::URem | AvrSelOpcode::SRem => {
                false
            }
            _ => true,
        }
    }

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

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

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

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

    fn node(opcode: AvrSelOpcode) -> AvrSelNode {
        AvrSelNode {
            opcode,
            operands: vec![],
            result_reg: None,
        }
    }

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

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

    #[test]
    fn test_select_and() {
        let isel = AvrInstructionSelector::new();
        let result = isel.select(&[node(AvrSelOpcode::And)]);
        assert_eq!(result, vec![AvrOpcode::AND]);
    }

    #[test]
    fn test_select_or() {
        let isel = AvrInstructionSelector::new();
        let result = isel.select(&[node(AvrSelOpcode::Or)]);
        assert_eq!(result, vec![AvrOpcode::OR]);
    }

    #[test]
    fn test_select_xor() {
        let isel = AvrInstructionSelector::new();
        let result = isel.select(&[node(AvrSelOpcode::Xor)]);
        assert_eq!(result, vec![AvrOpcode::EOR]);
    }

    #[test]
    fn test_select_shifts() {
        let isel = AvrInstructionSelector::new();
        assert_eq!(
            isel.select(&[node(AvrSelOpcode::Shl)]),
            vec![AvrOpcode::LSL]
        );
        assert_eq!(
            isel.select(&[node(AvrSelOpcode::Sra)]),
            vec![AvrOpcode::ASR]
        );
        assert_eq!(
            isel.select(&[node(AvrSelOpcode::Srl)]),
            vec![AvrOpcode::LSR]
        );
    }

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

    #[test]
    fn test_select_branch() {
        let isel = AvrInstructionSelector::new();
        assert_eq!(
            isel.select(&[node(AvrSelOpcode::Br)]),
            vec![AvrOpcode::RJMP]
        );
        assert_eq!(
            isel.select(&[node(AvrSelOpcode::BrCond)]),
            vec![AvrOpcode::BRBS]
        );
    }

    #[test]
    fn test_select_call_return() {
        let isel = AvrInstructionSelector::new();
        assert_eq!(
            isel.select(&[node(AvrSelOpcode::Call)]),
            vec![AvrOpcode::CALL]
        );
        assert_eq!(
            isel.select(&[node(AvrSelOpcode::Return)]),
            vec![AvrOpcode::RET]
        );
    }

    #[test]
    fn test_select_copy() {
        let isel = AvrInstructionSelector::new();
        assert_eq!(
            isel.select(&[node(AvrSelOpcode::Copy)]),
            vec![AvrOpcode::MOV]
        );
        assert_eq!(
            isel.select(&[node(AvrSelOpcode::CopyToReg)]),
            vec![AvrOpcode::MOV]
        );
    }

    #[test]
    fn test_select_constant() {
        let isel = AvrInstructionSelector::new();
        assert_eq!(
            isel.select(&[node(AvrSelOpcode::Constant)]),
            vec![AvrOpcode::LDI]
        );
    }

    #[test]
    fn test_select_div_requires_libcall() {
        let isel = AvrInstructionSelector::new();
        let result = isel.select(&[node(AvrSelOpcode::UDiv)]);
        assert_eq!(result, vec![AvrOpcode::RCALL]);
        assert!(isel.requires_libcall(&node(AvrSelOpcode::UDiv)));
        assert!(isel.requires_libcall(&node(AvrSelOpcode::SDiv)));
        assert!(!isel.requires_libcall(&node(AvrSelOpcode::Add)));
    }

    #[test]
    fn test_is_legal() {
        let isel = AvrInstructionSelector::new();
        assert!(isel.is_legal(&node(AvrSelOpcode::Add)));
        assert!(!isel.is_legal(&node(AvrSelOpcode::UDiv)));
    }

    #[test]
    fn test_legalize_i16_add() {
        let isel = AvrInstructionSelector::new();
        let ops = isel.legalize_i16_add();
        assert_eq!(ops, vec![AvrOpcode::ADD, AvrOpcode::ADC]);
    }

    #[test]
    fn test_legalize_i16_sub() {
        let isel = AvrInstructionSelector::new();
        let ops = isel.legalize_i16_sub();
        assert_eq!(ops, vec![AvrOpcode::SUB, AvrOpcode::SBC]);
    }

    #[test]
    fn test_legalize_i16_and() {
        let isel = AvrInstructionSelector::new();
        let ops = isel.legalize_i16_and();
        assert_eq!(ops.len(), 2);
    }

    #[test]
    fn test_legalize_i16_or() {
        let isel = AvrInstructionSelector::new();
        let ops = isel.legalize_i16_or();
        assert_eq!(ops.len(), 2);
    }

    #[test]
    fn test_emit_load_i16() {
        let isel = AvrInstructionSelector::new();
        let ops = isel.emit_load_i16(0x1234);
        assert_eq!(ops.len(), 2);
        assert_eq!(ops[0].0, AvrOpcode::LDI);
        assert_eq!(ops[1].0, AvrOpcode::LDI);
        // hi byte should be 0x12, lo byte should be 0x34
        assert_eq!(ops[0].1, 0x12);
        assert_eq!(ops[1].1, 0x34);
    }

    #[test]
    fn test_emit_load_i16_zero() {
        let isel = AvrInstructionSelector::new();
        let ops = isel.emit_load_i16(0);
        assert_eq!(ops[0].1, 0);
        assert_eq!(ops[1].1, 0);
    }

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