//! Radiance Intermediate Language (RIL).

//!

//! A minimal, low-level, SSA-based intermediate language.

//!

//! > The single-assignment property simplifies reasoning about variables,

//! > since for every value instance its (single) defining assignment is known.

//! > Because every assignment creates a new value name it cannot kill

//! > (i.e., invalidate) expressions previously computed from other values.

//! > In particular, if two expressions are textually the same, they are sure

//! > to evaluate the same result.

//! >

//! >   -- "Single-Pass Generation of Static Single-Assignment Form for

//! >       Structured Languages", by Marc M. Brandis and Hanspeter Mossenbock

//!

//! # Type System

//!

//! Primitive types: `W8`, `W16`, `W32` (word sizes).

//! Signedness is encoded in operations (e.g., `Sdiv` vs `Udiv`), not types.

//!

//! Types on arithmetic operations indicate logical width but don't

//! change code generation. Arithmetic is always machine word sized,

//! no 8-bit or 16-bit add instruction.

//!

//! # Truncation and Narrowing

//!

//! There is no truncation instruction.

//! * Narrow values are stored in word-sized registers with undefined high bits.

//! * Truncation happens implicitly via narrow store instructions.

//! * To normalize a narrow value, mask explicitly via a bitwise `and`.

//!

//! # Widerning

//!

//! `Zext`/`Sext` widen values when loading from memory.

//!

//! # Aggregate Types

//!

//! The IL provides no aggregate types. Records, slices, optionals, and unions

//! are represented as bytes in memory with explicit layout computed during

//! lowering. Access is via explicit address arithmetic plus load/store/blit.

//!

//! # Lowering Strategy

//!

//! * Slices lower to a pointer+length layout in memory.

//! * Optionals lower to a tag+value layout in memory.

//! * Tagged unions lower to a tag+payload layout in memory.

//! * Results lower to a tag+payload layout in memory.

//!

//! Field access is expressed as address arithmetic plus load/store.

//!

//! Bounds check elimination and nullable pointer optimization happen during

//! this lowering phase.

//!

//! # Control Flow

//!

//! Uses block parameters instead of phi nodes (like MLIR/SIL). Each block

//! can declare parameters, and jumps/branches pass arguments to their targets.

// TODO: Labels should have their own type.

// TODO: Blocks should have an instruction in `Instr`.

export mod printer;

export mod binary;

@test mod tests;

use std::mem;

use std::lang::alloc;

/// Source location for debug info.

///

/// Associates an IL instruction with its originating source module and

/// byte offset.

export record SrcLoc: Copy {

    /// Module identifier.

    moduleId: u16,

    /// Byte offset into the module's source file.

    offset: u32,

}

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

// Name Formatting   //

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

/// Separator for qualified symbol names.

export constant PATH_SEPARATOR: *[u8] = "::";

/// Format a qualified symbol name: `pkg::mod::path::name`.

export unsafe fn formatQualifiedName(arena: &mut alloc::Arena, path: &[*[u8]], name: *[u8]) -> *[u8] {

    let mut totalLen: u32 = name.len;

    for segment in path {

        set totalLen += segment.len + PATH_SEPARATOR.len;

    }

    let buf = try! alloc::allocSlice(arena, 1, 1, totalLen) as *mut [u8];

    let mut pos: u32 = 0;

    for segment in path {

        set pos += try! mem::copy(&mut buf[pos..], segment);

        set pos += try! mem::copy(&mut buf[pos..], PATH_SEPARATOR);

    }

    try! mem::copy(&mut buf[pos..], name);

    return &buf[..totalLen];

}

///////////

// Types //

///////////

/// IL type representation. Integer signedness is encoded in operations, not types.

export union Type: Copy {

    /// 8-bit value.

    W8,

    /// 16-bit value.

    W16,

    /// 32-bit value.

    W32,

    /// 64-bit value (used for pointers on RV64).

    W64,

}

/// Get the size of a type in bytes.

export fn typeSize(t: Type) -> u32 {

    match t {

        case Type::W8 => return 1,

        case Type::W16 => return 2,

        case Type::W32 => return 4,

        case Type::W64 => return 8,

    }

}

/// SSA register reference.

export record Reg: Copy { n: u32 }

/// Instruction value.

export union Val: Copy {

    /// Register reference.

    Reg(Reg),

    /// Immediate integer value.

    Imm(i64),

    /// Data symbol address (globals, constants, string literals).

    DataSym(*[u8]),

    /// Function address by symbol name. Used directly in call instructions

    /// for direct calls, or stored first for indirect calls.

    FnAddr(*[u8]),

    /// Undefined value. Used when the value is to be discarded,

    /// eg. in void returns.

    Undef,

}

/// Comparison operation for compare-and-branch.

export union CmpOp: Copy { Eq, Ne, Slt, Ult }

/// Binary ALU operation kind.

export union BinOp: Copy {

    // Arithmetic.

    Add, Sub, Mul, Sdiv, Udiv, Srem, Urem,

    // Comparison.

    Eq, Ne, Slt, Sge, Ult, Uge,

    // Bitwise.

    And, Or, Xor, Shl, Sshr, Ushr,

}

/// Unary ALU operation kind.

export union UnOp: Copy {

    Neg, Not,

}

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

// Instructions //

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

/// Block parameter.

export record Param: Copy {

    /// SSA register.

    value: Reg,

    /// Parameter type.

    type: Type,

}

/// Switch case mapping a constant value to a branch target.

export record SwitchCase: Copy {

    /// The constant value to match against.

    value: i64,

    /// The target block index.

    target: u32,

    /// Arguments to pass to the target block.

    args: *unsafe mut [Val],

}

/// IL instruction.

/// SSA registers are represented as `Reg`, values as `Val`.

export union Instr: Copy {

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

    // Memory operations //

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

    /// Allocate space on the stack: `reserve %dst <size> <alignment>;`

    /// Size can be a register for dynamic stack allocation (eg. VLAs).

    Reserve { dst: Reg, size: Val, alignment: u32 },

    /// Load a value from memory (zero-extending): `load <type> %dst %src <offset>;`

    Load { typ: Type, dst: Reg, src: Reg, offset: i32 },

    /// Signed load from memory (sign-extending): `sload <type> %dst %src <offset>;`

    Sload { typ: Type, dst: Reg, src: Reg, offset: i32 },

    /// Store a value to memory: `store <type> <src> %dst <offset>;`

    Store {

        /// Type being stored.

        typ: Type,

        /// Value being stored.

        src: Val,

        /// Destination address.

        dst: Reg,

        /// Byte offset from the base address.

        offset: i32

    },

    /// Copy memory region: `blit %dst %src <size>;`

    /// Size can be an immediate or a register (eg. for generics).

    Blit {

        /// Destination address.

        dst: Reg,

        /// Source address.

        src: Reg,

        /// Size to copy in bytes.

        size: Val

    },

    /// Copy a value into a register: `copy %dst <val>;`.

    Copy { dst: Reg, val: Val },

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

    // ALU operations  //

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

    /// Binary ALU operation: `<op> <type> %dst <a> <b>;`

    BinOp { op: BinOp, typ: Type, dst: Reg, a: Val, b: Val },

    /// Unary ALU operation: `<op> <type> %dst <a>;`

    UnOp { op: UnOp, typ: Type, dst: Reg, a: Val },

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

    // Conversions //

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

    /// Zero-extend from narrower type to word: `zext <type> %dst <val>;`

    Zext {

        /// Source type (I8 or I16).

        typ: Type,

        /// Destination register, always I32.

        dst: Reg,

        /// Source value.

        val: Val,

    },

    /// Sign-extend from narrower type to word: `sext <type> %dst <val>;`

    Sext {

        /// Source type (I8 or I16).

        typ: Type,

        /// Destination register, always I32.

        dst: Reg,

        /// Source value.

        val: Val,

    },

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

    // Function calls //

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

    /// Call a function: `call <type> %dst $func(<arg>...);`

    Call {

        /// Return type.

        retTy: Type,

        /// Holds return value, for non-void function.

        dst: ?Reg,

        /// Function value, either a symbol or an address in a register.

        func: Val,

        /// Function arguments.

        args: *unsafe [Val]

    },

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

    // Terminators //

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

    /// Return from function: `ret <val>;` or `ret;`

    Ret { val: ?Val },

    /// Unconditional jump: `jmp @block(<arg>...);`

    Jmp { target: u32, args: *unsafe mut [Val] },

    /// Compare-and-branch: `br.<op> <type> <a> <b> @then @else;`

    Br { op: CmpOp, typ: Type, a: Val, b: Val, thenTarget: u32, thenArgs: *unsafe mut [Val], elseTarget: u32, elseArgs: *unsafe mut [Val] },

    /// Multi-way branch: `switch <val> (<n> @block) ... @default;`

    Switch { val: Val, defaultTarget: u32, defaultArgs: *unsafe mut [Val], cases: *unsafe mut [SwitchCase] },

    /// Unreachable code marker: `unreachable;`

    /// Indicates control flow cannot reach this point to allow for optimizations.

    Unreachable,

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

    // Intrinsics  //

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

    /// Environment call: `ecall %dst <num> <a0> <a1> <a2> <a3>;`

    Ecall { dst: Reg, num: Val, a0: Val, a1: Val, a2: Val, a3: Val },

    /// Environment break: `ebreak;`.

    /// Triggers a breakpoint exception for debugging.

    Ebreak,

    /// Full acquire/release memory fence.

    MemoryFence,

    /// Read one register through a live Device handle.

    DeviceRead {

        /// Register access width.

        typ: Type,

        /// Destination for the zero-extended register value.

        dst: Reg,

        /// Domain-relative Device capability.

        handle: Val,

        /// Byte offset within the device region.

        offset: Val,

    },

    /// Write one register through a live Device handle.

    DeviceWrite {

        /// Register access width.

        typ: Type,

        /// Domain-relative Device capability.

        handle: Val,

        /// Byte offset within the device region.

        offset: Val,

        /// Value whose low bits are written at the selected width.

        value: Val,

    },

}

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

// Blocks and Functions //

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

/// A basic block in a function.

///

/// Basic blocks are instruction sequences with a single entry point and no branch

/// instruction, except possibly at the end of the sequence, where a terminator

/// may be found, ie. an instruction that terminates the sequence by jumping

/// to another sequence.

export record Block: Copy {

    /// Block label.

    label: *[u8],

    /// Block parameters.

    params: *unsafe [Param],

    /// Instructions in the block. The last instruction must be a terminator.

    instrs: *unsafe mut [Instr],

    /// Source locations for debugging and error reporting.

    /// One entry per instruction when debug info is enabled, empty otherwise.

    locs: *unsafe [SrcLoc],

    /// Predecessor block indices. Used for control flow analysis.

    preds: *unsafe [u32],

    /// Loop nesting depth.

    /// Used for spill cost weighting in register allocation.

    loopDepth: u32,

}

/// An IL function.

export record Fn: Copy {

    /// Qualified function name (e.g. `$mod$path$func`).

    name: *[u8],

    /// Function parameters.

    params: *unsafe [Param],

    /// Return type.

    returnType: Type,

    /// Whether the function is extern (no body).

    isExtern: bool,

    /// Whether the function is a leaf (contains no call or ecall instructions).

    isLeaf: bool,

    /// Basic blocks. Empty for extern functions.

    blocks: *unsafe [Block],

}

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

// Program //

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

/// Data initializer item.

export union DataItem: Copy {

    /// Typed value: `w32 42;` or `w8 255;`

    Val { typ: Type, val: i64 },

    /// Symbol reference: `$symbol`

    Sym(*[u8]),

    /// Function reference: `$fnName`

    Fn(*[u8]),

    /// String literal bytes: `"hello"` (no auto null-terminator)

    Str(*[u8]),

    /// Undefined value. Used for padding and `void` returns.

    Undef,

}

/// Data initializer value with optional repeat count.

export record DataValue: Copy {

    /// The item contained in the value.

    item: DataItem,

    /// The number of times the item should be repeated.

    count: u32,

}

/// Global data definition.

export record Data: Copy {

    /// Data name.

    name: *[u8],

    /// Size in bytes.

    size: u32,

    /// Alignment requirement.

    alignment: u32,

    /// Whether this is read-only data.

    /// Typically, `constant` declaration are read-only, while `static`

    /// declarations are not.

    readOnly: bool,

    /// Whether writable data can be represented by zero-filled memory.

    /// Zero-initialized data doesn't need to be written to the sidecar image.

    isZeroInit: bool,

    /// Initializer values.

    values: *[DataValue],

}

/// An IL program (compilation unit).

export record Program: Copy {

    /// Immutable global data.

    data: *[Data],

    /// Functions.

    fns: *unsafe [*unsafe Fn],

}

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

// Utility Functions //

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

/// Compiler-generated metadata call for one MMIO access.

/// a0 is the handle, a1 the offset, and a2 the byte width plus bit 8 for a write.

/// a3 holds a write value and is preserved. Success returns the address in a0.

/// Any failure terminates the caller before the user-mode register access.

export constant DEVICE_ACCESS: u32 = 74;

/// Get the destination register of an instruction, if any.

export fn instrDst(instr: Instr) -> ?Reg {

    match instr {

        case Instr::Reserve { dst, .. } => return dst,

        case Instr::Load { dst, .. } => return dst,

        case Instr::Sload { dst, .. } => return dst,

        case Instr::Copy { dst, .. } => return dst,

        case Instr::BinOp { dst, .. } => return dst,

        case Instr::UnOp { dst, .. } => return dst,

        case Instr::Zext { dst, .. } => return dst,

        case Instr::Sext { dst, .. } => return dst,

        case Instr::Call { dst, .. } => return dst,

        case Instr::Ecall { dst, .. } => return dst,

        case Instr::DeviceRead { dst, .. } => return dst,

        else => return nil,

    }

}

/// Check if an instruction is a function call.

export fn isCall(instr: Instr) -> bool {

    match instr {

        case Instr::Call { .. },

             Instr::Ecall { .. }, Instr::DeviceRead { .. }, Instr::DeviceWrite { .. } => return true,

        else => return false,

    }

}

/// Position within an instruction's source operands.

export record RegCursor: Copy {

    /// Registers in the instruction's fixed operands, in operand order.

    fixed: [Reg; 5],

    /// Number of initialized fixed registers.

    count: u32,

    /// Next fixed register.

    next: u32,

    /// Next argument in the current argument group.

    argument: u32,

    /// Argument group: zero for the first group, then one per switch case.

    branch: u32,

    /// Whether the instruction has variable argument groups left to scan.

    arguments: bool,

}

/// Start a source-register scan in instruction operand order.

export unsafe fn registers(instr: &Instr) -> RegCursor {

    let mut cursor = RegCursor { fixed: undefined, count: 0, next: 0, argument: 0, branch: 0, arguments: false };

    match *instr {

        case Instr::Reserve { size, .. } => addOperand(&mut cursor, size),

        case Instr::Load { src, .. } => addOperand(&mut cursor, Val::Reg(src)),

        case Instr::Sload { src, .. } => addOperand(&mut cursor, Val::Reg(src)),

        case Instr::Store { src, dst, .. } => {

            addOperand(&mut cursor, src);

            addOperand(&mut cursor, Val::Reg(dst));

        }

        case Instr::Blit { dst, src, size } => {

            addOperand(&mut cursor, Val::Reg(dst));

            addOperand(&mut cursor, Val::Reg(src));

            addOperand(&mut cursor, size);

        }

        case Instr::Copy { val, .. } => addOperand(&mut cursor, val),

        case Instr::BinOp { a, b, .. } => {

            addOperand(&mut cursor, a);

            addOperand(&mut cursor, b);

        }

        case Instr::UnOp { a, .. } => addOperand(&mut cursor, a),

        case Instr::Zext { val, .. } => addOperand(&mut cursor, val),

        case Instr::Sext { val, .. } => addOperand(&mut cursor, val),

        case Instr::Call { func, .. } => {

            addOperand(&mut cursor, func);

            set cursor.arguments = true;

        }

        case Instr::Ret { val } => {

            if let value = val {

                addOperand(&mut cursor, value);

            }

        }

        case Instr::Jmp { .. } => set cursor.arguments = true,

        case Instr::Br { a, b, .. } => {

            addOperand(&mut cursor, a);

            addOperand(&mut cursor, b);

            set cursor.arguments = true;

        }

        case Instr::Switch { val, .. } => {

            addOperand(&mut cursor, val);

            set cursor.arguments = true;

        }

        case Instr::Ecall { num, a0, a1, a2, a3, .. } => {

            addOperand(&mut cursor, num);

            addOperand(&mut cursor, a0);

            addOperand(&mut cursor, a1);

            addOperand(&mut cursor, a2);

            addOperand(&mut cursor, a3);

        }

        case Instr::DeviceRead { handle, offset, .. } => {

            addOperand(&mut cursor, handle);

            addOperand(&mut cursor, offset);

        }

        case Instr::DeviceWrite { handle, offset, value, .. } => {

            addOperand(&mut cursor, handle);

            addOperand(&mut cursor, offset);

            addOperand(&mut cursor, value);

        }

        case Instr::Unreachable, Instr::Ebreak, Instr::MemoryFence => {

        }

    }

    return cursor;

}

/// Append a fixed register operand to the cursor.

fn addOperand(cursor: &mut RegCursor, value: Val) {

    if let case Val::Reg(reg) = value {

        set cursor.fixed[cursor.count] = reg;

        set cursor.count += 1;

    }

}

/// Return the next source register, including repeated uses.

/// Supply the unchanged instruction for every step of a scan.

export unsafe fn nextReg(cursor: &mut RegCursor, instr: &Instr) -> ?Reg {

    if cursor.next < cursor.count {

        let reg = cursor.fixed[cursor.next];

        set cursor.next += 1;

        return reg;

    }

    if not cursor.arguments {

        return nil;

    }

    match *instr {

        case Instr::Call { args, .. } => {

            if let reg = nextArgument(cursor, args) {

                return reg;

            }

        }

        case Instr::Jmp { args, .. } => {

            if let reg = nextArgument(cursor, args) {

                return reg;

            }

        }

        case Instr::Br { thenArgs, elseArgs, .. } => {

            if cursor.branch == 0 {

                if let reg = nextArgument(cursor, thenArgs) {

                    return reg;

                }

                set cursor.branch = 1;

                set cursor.argument = 0;

            }

            if let reg = nextArgument(cursor, elseArgs) {

                return reg;

            }

        }

        case Instr::Switch { defaultArgs, cases, .. } => {

            if cursor.branch == 0 {

                if let reg = nextArgument(cursor, defaultArgs) {

                    return reg;

                }

                set cursor.branch = 1;

                set cursor.argument = 0;

            }

            while cursor.branch - 1 < cases.len {

                if let reg = nextArgument(cursor, cases[cursor.branch - 1].args) {

                    return reg;

                }

                set cursor.branch += 1;

                set cursor.argument = 0;

            }

        }

        else => panic "nextReg: expected instruction argument groups",

    }

    set cursor.arguments = false;

    return nil;

}

/// Scan an argument group from the cursor's current position.

unsafe fn nextArgument(cursor: &mut RegCursor, args: *unsafe [Val]) -> ?Reg {

    while cursor.argument < args.len {

        let value = args[cursor.argument];

        set cursor.argument += 1;

        if let case Val::Reg(reg) = value {

            return reg;

        }

    }

    return nil;

}