//! RV64 code generation backend.

//!

//! Generates RISC-V 64-bit machine code from IL (intermediate language).

//!

//! # Submodules

//!

//! * encode: Instruction encoding functions

//! * decode: Instruction decoding (for disassembly/printing)

//! * emit: Binary emission context and branch patching

//! * isel: Instruction selection (IL to RV64 instructions)

//! * printer: Assembly text output

pub mod encode;

pub mod decode;

pub mod emit;

pub mod isel;

pub mod printer;

@test mod tests;

use std::mem;

use std::lang::il;

use std::lang::alloc;

use std::lang::gen::labels;

use std::lang::gen::regalloc;

////////////////

// Registers  //

////////////////

/// RISC-V general-purpose register.

pub record Reg { n: u8 }

pub const ZERO: Reg = { n: 0 };   /// Hard-wired zero.

pub const RA:   Reg = { n: 1 };   /// Return address.

pub const SP:   Reg = { n: 2 };   /// Stack pointer.

pub const GP:   Reg = { n: 3 };   /// Global pointer.

pub const TP:   Reg = { n: 4 };   /// Thread pointer.

pub const T0:   Reg = { n: 5 };   /// Temporary/alternate link register.

pub const T1:   Reg = { n: 6 };   /// Temporary.

pub const T2:   Reg = { n: 7 };   /// Temporary.

pub const S0:   Reg = { n: 8 };   /// Saved register/frame pointer.

pub const FP:   Reg = { n: 8 };   /// Frame pointer (alias for S0).

pub const S1:   Reg = { n: 9 };   /// Saved register.

pub const A0:   Reg = { n: 10 };  /// Function argument/return.

pub const A1:   Reg = { n: 11 };  /// Function argument/return.

pub const A2:   Reg = { n: 12 };  /// Function argument.

pub const A3:   Reg = { n: 13 };  /// Function argument.

pub const A4:   Reg = { n: 14 };  /// Function argument.

pub const A5:   Reg = { n: 15 };  /// Function argument.

pub const A6:   Reg = { n: 16 };  /// Function argument.

pub const A7:   Reg = { n: 17 };  /// Function argument.

pub const S2:   Reg = { n: 18 };  /// Saved register.

pub const S3:   Reg = { n: 19 };  /// Saved register.

pub const S4:   Reg = { n: 20 };  /// Saved register.

pub const S5:   Reg = { n: 21 };  /// Saved register.

pub const S6:   Reg = { n: 22 };  /// Saved register.

pub const S7:   Reg = { n: 23 };  /// Saved register.

pub const S8:   Reg = { n: 24 };  /// Saved register.

pub const S9:   Reg = { n: 25 };  /// Saved register.

pub const S10:  Reg = { n: 26 };  /// Saved register.

pub const S11:  Reg = { n: 27 };  /// Saved register.

pub const T3:   Reg = { n: 28 };  /// Temporary.

pub const T4:   Reg = { n: 29 };  /// Temporary.

pub const T5:   Reg = { n: 30 };  /// Temporary.

pub const T6:   Reg = { n: 31 };  /// Temporary.

/// Create a register from a number. Panics if `n > 31`.

pub fn reg(n: u8) -> Reg {

    assert n < 32;

    return Reg { n };

}

////////////////////////////

// Architecture constants //

////////////////////////////

/// Total number of general-purpose registers.

pub const NUM_REGISTERS: u8 = 32;

/// Word size in bytes (32-bit).

pub const WORD_SIZE: i32 = 4;

/// Doubleword size in bytes (64-bit).

pub const DWORD_SIZE: i32 = 8;

/// Instruction size in bytes.

pub const INSTR_SIZE: i32 = 4;

/// Stack alignment requirement in bytes.

pub const STACK_ALIGNMENT: i32 = 16;

/////////////////////////

// Codegen Allocation  //

/////////////////////////

/// Argument registers for function calls.

pub const ARG_REGS: [Reg; 8] = [A0, A1, A2, A3, A4, A5, A6, A7];

/// Scratch register for code gen. Never allocated to user values.

pub const SCRATCH1: Reg = { n: 30 };

/// Second scratch register for operations needing two temporaries.

pub const SCRATCH2: Reg = { n: 31 };

/// Dedicated scratch for address offset adjustment. Never allocated to user

/// values and never used for operand materialization, so it can never

/// conflict with `rd`, `rs`, or `base` in load/store helpers.

pub const ADDR_SCRATCH: Reg = { n: 29 };

/// Callee-saved registers that need save/restore if used.

pub const CALLEE_SAVED: [Reg; 11] = [S1, S2, S3, S4, S5, S6, S7, S8, S9, S10, S11];

/// Maximum 12-bit signed immediate value.

pub const MAX_IMM: i32 = 2047;

/// Minimum 12-bit signed immediate value.

pub const MIN_IMM: i32 = -2048;

/// Allocatable register numbers for register allocation.

const ALLOCATABLE_REGS: [u8; 23] = [

    5, 6, 7, 28,                                // T0-T3

    10, 11, 12, 13, 14, 15, 16, 17,             // A0-A7

    9, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27,  // S1-S11

];

/// Argument register numbers for register allocation.

const ARG_REG_NUMS: [u8; 8] = [10, 11, 12, 13, 14, 15, 16, 17]; // A0-A7

/// Callee-saved register numbers for frame layout.

const CALLEE_SAVED_NUMS: [u8; 11] = [9, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27]; // S1-S11

/// Get target configuration for register allocation.

// TODO: This should be a constant variable.

pub fn targetConfig() -> regalloc::TargetConfig {

    return regalloc::TargetConfig {

        // TODO: Use inline slice when we move to self-hosted compiler.

        allocatable: &ALLOCATABLE_REGS[..],

        argRegs: &ARG_REG_NUMS[..],

        calleeSaved: &CALLEE_SAVED_NUMS[..],

        slotSize: DWORD_SIZE,

    };

}

///////////////////////

// Codegen Constants //

///////////////////////

/// Maximum number of data symbols.

pub const MAX_DATA_SYMS: u32 = 8192;

/// Base address where read-only data is loaded.

pub const RO_DATA_BASE: u32 = 0x10000;

/// Base address where read-write data is loaded.

pub const RW_DATA_BASE: u32 = 0xFFFFF0;

/// Data symbol entry mapping name to address.

pub record DataSym {

    /// Symbol name.

    name: *[u8],

    /// Absolute address, including data base address.

    addr: u32,

}

/// Storage buffers passed from driver for code generation.

pub record Storage {

    /// Buffer for data symbols.

    dataSyms: *mut [DataSym],

}

/// Result of code generation.

pub record Program {

    /// Slice of emitted code.

    code: *[u32],

    /// Slice of function addresses (name + start index).

    funcs: *[emit::FuncAddr],

    /// Number of read-only data bytes emitted.

    roDataSize: u32,

    /// Number of read-write data bytes emitted.

    rwDataSize: u32,

    /// Debug entries mapping PCs to source locations. Empty when debug is off.

    debugEntries: *[emit::DebugEntry],

}

/// Lay out data symbols for a single section.

/// Initialized data is placed first, then uninitialized, so that only

/// initialized data needs to be written to the output file.

/// Returns the updated offset past all placed symbols.

fn layoutSection(

    program: *il::Program,

    syms: *mut [DataSym],

    count: *mut u32,

    base: u32,

    readOnly: bool

) -> u32 {

    let mut offset: u32 = 0;

    // Initialized data first.

    for i in 0..program.data.len {

        let data = &program.data[i];

        if data.readOnly == readOnly and not data.isUndefined {

            offset = mem::alignUp(offset, data.alignment);

            syms[*count] = DataSym { name: data.name, addr: base + offset };

            *count += 1;

            offset += data.size;

        }

    }

    // Uninitialized data after.

    for i in 0..program.data.len {

        let data = &program.data[i];

        if data.readOnly == readOnly and data.isUndefined {

            offset = mem::alignUp(offset, data.alignment);

            syms[*count] = DataSym { name: data.name, addr: base + offset };

            *count += 1;

            offset += data.size;

        }

    }

    return offset;

}

/// Emit data bytes for a single section (read-only or read-write) into `buf`.

/// Iterates initialized data in the IL program, serializing each data item.

/// Returns the total number of bytes written.

pub fn emitSection(

    program: *il::Program,

    dataSyms: *[DataSym],

    fnLabels: *labels::Labels,

    codeBase: u32,

    buf: *mut [u8],

    readOnly: bool

) -> u32 {

    let mut offset: u32 = 0;

    for i in 0..program.data.len {

        let data = &program.data[i];

        if data.readOnly == readOnly and not data.isUndefined {

            offset = mem::alignUp(offset, data.alignment);

            if offset + data.size > buf.len {

                panic "emitSection: buffer overflow";

            }

            for j in 0..data.values.len {

                let v = &data.values[j];

                for _ in 0..v.count {

                    match v.item {

                        case il::DataItem::Val { typ, val } => {

                            let size = il::typeSize(typ);

                            let valPtr = &val as *u8;

                            try! mem::copy(&mut buf[offset..], @sliceOf(valPtr, size));

                            offset += size;

                        },

                        case il::DataItem::Sym(name) => {

                            let addr = lookupDataSymAddr(dataSyms, name) else {

                                panic "emitSection: data symbol not found";

                            };

                            // Write 8-byte pointer: low 4 bytes are the

                            // address, high 4 bytes are zero.

                            // TODO: Use `u64` once it's supported.

                            let lo: u32 = addr;

                            let hi: u32 = 0;

                            let loPtr = &lo as *u8;

                            let hiPtr = &hi as *u8;

                            try! mem::copy(&mut buf[offset..], @sliceOf(loPtr, 4));

                            try! mem::copy(&mut buf[(offset + 4)..], @sliceOf(hiPtr, 4));

                            offset += 8;

                        },

                        case il::DataItem::Fn(name) => {

                            let addr = codeBase + labels::funcOffset(fnLabels, name) as u32;

                            let lo: u32 = addr;

                            let hi: u32 = 0;

                            let loPtr = &lo as *u8;

                            let hiPtr = &hi as *u8;

                            try! mem::copy(&mut buf[offset..], @sliceOf(loPtr, 4));

                            try! mem::copy(&mut buf[(offset + 4)..], @sliceOf(hiPtr, 4));

                            offset += 8;

                        },

                        case il::DataItem::Str(s) => {

                            try! mem::copy(&mut buf[offset..], s);

                            offset += s.len;

                        },

                        case il::DataItem::Undef => {

                            buf[offset] = 0;

                            offset += 1;

                        },

                    }

                }

            }

        }

    }

    return offset;

}

/// Resolve a data symbol to its final absolute address.

fn lookupDataSymAddr(dataSyms: *[DataSym], name: *[u8]) -> ?u32 {

    for i in 0..dataSyms.len {

        let sym = dataSyms[i];

        if mem::eq(sym.name, name) {

            return sym.addr;

        }

    }

    return nil;

}

/// Generate code for an IL program.

pub fn generate(

    program: *il::Program,

    storage: Storage,

    roDataBuf: *mut [u8],

    rwDataBuf: *mut [u8],

    arena: *mut alloc::Arena,

    debug: bool

) -> Program {

    let mut e = try! emit::emitter(arena, debug);

    let config = targetConfig();

    // Build data map.

    let mut dataSymCount: u32 = 0;

    let roLayoutSize = layoutSection(program, storage.dataSyms, &mut dataSymCount, RO_DATA_BASE, true);

    layoutSection(program, storage.dataSyms, &mut dataSymCount, RW_DATA_BASE, false);

    // Code base address: code follows read-only data, aligned to dword boundary.

    let codeBase = mem::alignUp(RO_DATA_BASE + roLayoutSize, DWORD_SIZE as u32);

    // Emit placeholder entry jump to default function if there is one.

    // We'll patch this at the end once we know where the function is.

    let mut defaultName: ?*[u8] = nil;

    if let defIdx = program.defaultFnIdx {

        defaultName = program.fns[defIdx].name;

        emit::emit(&mut e, encode::nop()); // Placeholder for two-instruction jump.

        emit::emit(&mut e, encode::nop()); //

    }

    // Generate code for all functions.

    let dataSyms = &storage.dataSyms[..dataSymCount];

    for i in 0..program.fns.len {

        let func = program.fns[i];

        if not func.isExtern {

            let checkpoint = alloc::save(arena);

            let ralloc = try! regalloc::allocate(func, &config, arena);

            isel::selectFn(&mut e, dataSyms, &ralloc, func);

            // Reclaim unused memory after instruction selection.

            alloc::restore(arena, checkpoint);

        }

    }

    // Patch entry jump now that we know where the default function is.

    // Nb. we use a two-instruction jump even if it isn't always needed.

    if let target = defaultName {

        let offset = emit::branchOffsetToFunc(&e, 0, target);

        let s = emit::splitImm(offset);

        emit::patch(&mut e, 0, encode::auipc(SCRATCH1, s.hi));

        emit::patch(&mut e, 1, encode::jalr(ZERO, SCRATCH1, s.lo));

    }

    // Patch function calls and address loads now that all functions are emitted.

    emit::patchCalls(&mut e);

    emit::patchAddrLoads(&mut e);

    // Emit data sections.

    let roDataSize = emitSection(program, dataSyms, &e.labels, codeBase, roDataBuf, true);

    let rwDataSize = emitSection(program, dataSyms, &e.labels, codeBase, rwDataBuf, false);

    return Program {

        code: emit::getCode(&e),

        funcs: emit::getFuncs(&e),

        roDataSize,

        rwDataSize,

        debugEntries: emit::getDebugEntries(&e),

    };

}