//! Tests for liveness analysis.

use std::testing;

use std::lang::alloc;

use std::lang::il;

use std::lang::gen::bitset;

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

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

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

/// Construct a block whose instruction storage belongs to the caller.

unsafe fn block(name: *[u8], instructions: *unsafe mut [il::Instr]) -> il::Block {

    return il::Block { label: name, params: &[], instrs: instructions,

        locs: &[], preds: &[], loopDepth: 0 };

}

/// Empty functions and register-free blocks produce empty liveness matrices.

@test unsafe fn testEmptyLivenessStorage() throws (testing::TestError) {

    let mut instructions = [il::Instr::Ret { val: il::Val::Imm(0) }];

    let blocks = [block("entry", &mut instructions[..])];

    for count in [0 as u32, 1] {

        let function = il::Fn { name: "empty", params: &[], returnType: il::Type::W64,

            isExtern: false, isLeaf: true, blocks: &blocks[..count] };

        static DATA: [u8; 1024] = [0; 1024];

        let mut arena = alloc::new(&mut DATA[..]);

        use arena as analysis in {

            let live = try! super::analyze(&function, &analysis);

            assert live.blockCount == count;

            assert live.maxReg == 0;

            assert live.words == 0;

            assert live.liveIn.len == 0 and live.liveOut.len == 0;

            assert live.defs.len == 0 and live.uses.len == 0;

            let spills = try! spill::analyze(&function, &live, 0, 0, 8, &analysis);

            assert spills.maxReg == 0;

            assert spills.frameSize == 0;

            assert spills.slots.len == 0 and spills.calleeClass.len == 0;

            let config = regalloc::TargetConfig { allocatable: &[], argRegs: &[], calleeSaved: &[], slotSize: 8 };

            let assigned = try! assign::assign(&function, &live, &spills, &config, &analysis);

            assert assigned.assignments.len == 0;

            assert assigned.usedCalleeSaved == 0;

        }

    }

}

/// Insufficient matrix storage reports an allocation error.

@test unsafe fn testLivenessStorageExhaustion() throws (testing::TestError) {

    let mut instructions = [il::Instr::Ret { val: il::Val::Reg(il::Reg { n: 66 }) }];

    let blocks = [block("entry", &mut instructions[..])];

    let function = il::Fn { name: "storage", params: &[], returnType: il::Type::W64,

        isExtern: false, isLeaf: true, blocks: &blocks[..] };

    static DATA: [u8; 16] = [0; 16];

    let mut arena = alloc::new(&mut DATA[..]);

    let mut failed = false;

    use arena as analysis in {

        try super::analyze(&function, &analysis) catch {

            set failed = true;

        };

    }

    assert failed;

}

/// Spill storage exhaustion reports an error after liveness succeeds.

@test unsafe fn testSpillStorageExhaustion() throws (testing::TestError) {

    let mut instructions = [il::Instr::Ret { val: il::Val::Reg(il::Reg { n: 66 }) }];

    let blocks = [block("entry", &mut instructions[..])];

    let function = il::Fn { name: "spillStorage", params: &[], returnType: il::Type::W64,

        isExtern: false, isLeaf: true, blocks: &blocks[..] };

    static DATA: [u8; 128] = [0; 128];

    let mut arena = alloc::new(&mut DATA[..]);

    let mut failed = false;

    use arena as analysis in {

        let live = try! super::analyze(&function, &analysis);

        try spill::analyze(&function, &live, 0, 0, 8, &analysis) catch {

            set failed = true;

        };

    }

    assert failed;

}

/// Switch successors merge distinct words and tolerate repeated destinations.

@test unsafe fn testSwitchSuccessorLiveness() throws (testing::TestError) {

    for count in [0 as u32, 1, 3] {

        let mut cases = [

            il::SwitchCase { value: 0, target: 1, args: &mut [] },

            il::SwitchCase { value: 1, target: 1, args: &mut [] },

            il::SwitchCase { value: 2, target: 2, args: &mut [] },

        ];

        let mut entry = [il::Instr::Switch { val: il::Val::Imm(0),

            defaultTarget: 3, defaultArgs: &mut [], cases: &mut cases[..count] }];

        let mut first = [il::Instr::Ret { val: il::Val::Reg(il::Reg { n: 0 }) }];

        let mut second = [il::Instr::Ret { val: il::Val::Reg(il::Reg { n: 33 }) }];

        let mut fallback = [il::Instr::Ret { val: il::Val::Reg(il::Reg { n: 66 }) }];

        let blocks = [block("entry", &mut entry[..]), block("first", &mut first[..]),

            block("second", &mut second[..]), block("default", &mut fallback[..]),

            block("empty", &mut [])];

        let function = il::Fn { name: "switch", params: &[], returnType: il::Type::W64,

            isExtern: false, isLeaf: true, blocks: &blocks[..] };

        static DATA: [u8; 8192] = [0; 8192];

        let mut arena = alloc::new(&mut DATA[..]);

        use arena as analysis in {

            let live = try! super::analyze(&function, &analysis);

            try check(super::liveOutRow(&live, 0), count > 0, count == 3, true);

            try check(super::liveInRow(&live, 0), count > 0, count == 3, true);

            try check(super::liveOutRow(&live, 4), false, false, false);

        }

    }

}

/// A cyclic graph propagates uses against block order until all rows stabilize.

@test unsafe fn testDelayedCyclicPropagation() throws (testing::TestError) {

    let value = il::Reg { n: 66 };

    let mut entry = [il::Instr::Copy { dst: value, val: il::Val::Imm(7) },

        il::Instr::Jmp { target: 3, args: &mut [] }];

    let mut exit = [il::Instr::Ret { val: il::Val::Reg(value) }];

    let mut bridge = [il::Instr::Jmp { target: 1, args: &mut [] }];

    let mut cycle = [il::Instr::Br { op: il::CmpOp::Eq, typ: il::Type::W64,

        a: il::Val::Imm(0), b: il::Val::Imm(1), thenTarget: 3, thenArgs: &mut [],

        elseTarget: 2, elseArgs: &mut [] }];

    let blocks = [block("entry", &mut entry[..]), block("exit", &mut exit[..]),

        block("bridge", &mut bridge[..]), block("cycle", &mut cycle[..]),

        block("empty", &mut [])];

    let function = il::Fn { name: "cycle", params: &[], returnType: il::Type::W64,

        isExtern: false, isLeaf: true, blocks: &blocks[..] };

    static DATA: [u8; 8192] = [0; 8192];

    let mut arena = alloc::new(&mut DATA[..]);

    use arena as analysis in {

        let live = try! super::analyze(&function, &analysis);

        for index in 0..blocks.len {

            try check(super::liveInRow(&live, index), false, false, index > 0 and index < 4);

            try check(super::liveOutRow(&live, index), false, false, index <> 1 and index < 4);

        }

    }

}

/// Later-use queries include outgoing values and exclude the current instruction.

@test unsafe fn testLaterUses() throws (testing::TestError) {

    let outgoing = il::Reg { n: 0 };

    let argument = il::Reg { n: 1 };

    let result = il::Reg { n: 33 };

    let unused = il::Reg { n: 66 };

    let params = [il::Param { value: argument, type: il::Type::W64 }];

    let args = [il::Val::Imm(0), il::Val::Reg(argument), il::Val::Reg(argument)];

    let mut entry = [

        il::Instr::Copy { dst: outgoing, val: il::Val::Imm(1) },

        il::Instr::Call { retTy: il::Type::W64, dst: result,

            func: il::Val::FnAddr("callee"), args: &args[..] },

        il::Instr::Copy { dst: unused, val: il::Val::Reg(result) },

        il::Instr::Jmp { target: 1, args: &mut [] },

    ];

    let mut exit = [il::Instr::Ret { val: il::Val::Reg(outgoing) }];

    let blocks = [block("entry", &mut entry[..]), block("exit", &mut exit[..])];

    let function = il::Fn { name: "later", params: &params[..], returnType: il::Type::W64,

        isExtern: false, isLeaf: false, blocks: &blocks[..] };

    static DATA: [u8; 8192] = [0; 8192];

    let mut arena = alloc::new(&mut DATA[..]);

    use arena as analysis in {

        let live = try! super::analyze(&function, &analysis);

        for index in 0..entry.len {

            assert super::hasLaterUse(&live, &function, 0, index, outgoing);

            assert super::hasLaterUse(&live, &function, 0, index, argument) == (index == 0);

            assert super::hasLaterUse(&live, &function, 0, index, result) == (index < 2);

            assert not super::hasLaterUse(&live, &function, 0, index, unused);

        }

        assert not super::hasLaterUse(&live, &function, 1, 0, outgoing);

    }

}

/// Local uses precede definitions, and block parameters define their registers.

@test unsafe fn testLocalDefinitionOrder() throws (testing::TestError) {

    let parameter = il::Reg { n: 33 };

    let temporary = il::Reg { n: 66 };

    let external = il::Reg { n: 0 };

    let params = [il::Param { value: parameter, type: il::Type::W64 }];

    let mut instructions = [

        il::Instr::BinOp { op: il::BinOp::Add, typ: il::Type::W64, dst: temporary,

            a: il::Val::Reg(external), b: il::Val::Reg(parameter) },

        il::Instr::Copy { dst: external, val: il::Val::Reg(temporary) },

        il::Instr::Ret { val: il::Val::Reg(external) },

    ];

    let blocks = [il::Block { label: "entry", params: &params[..],

        instrs: &mut instructions[..], locs: &[], preds: &[], loopDepth: 0 },

        block("empty", &mut [])];

    let function = il::Fn { name: "local", params: &[], returnType: il::Type::W64,

        isExtern: false, isLeaf: true, blocks: &blocks[..] };

    static DATA: [u8; 8192] = [0; 8192];

    let mut arena = alloc::new(&mut DATA[..]);

    use arena as analysis in {

        let live = try! super::analyze(&function, &analysis);

        try check(&live.defs[..live.words], true, true, true);

        try check(&live.uses[..live.words], true, false, false);

        try check(super::liveInRow(&live, 0), true, false, false);

        try check(&live.defs[live.words..], false, false, false);

        try check(&live.uses[live.words..], false, false, false);

    }

}

/// Liveness sizes its rows from register operands and definitions.

@test unsafe fn testLargeRegisterExtent() throws (testing::TestError) {

    for index in [8191 as u32, 8192, 8193, 16384] {

        let source = il::Reg { n: index };

        let destination = il::Reg { n: index + 1 };

        let mut instructions = [

            il::Instr::Copy { dst: destination, val: il::Val::Reg(source) },

            il::Instr::Ret { val: il::Val::Reg(destination) },

        ];

        let blocks = [block("entry", &mut instructions[..])];

        let function = il::Fn { name: "extent", params: &[], returnType: il::Type::W64,

            isExtern: false, isLeaf: true, blocks: &blocks[..] };

        static DATA: [u8; 16384] = [0; 16384];

        let mut arena = alloc::new(&mut DATA[..]);

        use arena as analysis in {

            let live = try super::analyze(&function, &analysis) catch {

                throw testing::TestError::Failed;

            };

            assert live.maxReg == index + 2;

            assert bitset::contains(super::liveInRow(&live, 0), source.n);

            assert bitset::contains(&live.defs[..], destination.n);

            assert not bitset::contains(super::liveInRow(&live, 0), destination.n);

        }

    }

}

/// Nested switch arguments contribute to the extent and reject index overflow.

@test unsafe fn testSwitchArgumentExtent() throws (testing::TestError) {

    for index in [8192 as u32, 16384, 0xffffffff] {

        for inDefault in [false, true] {

            let source = il::Reg { n: index };

            let mut caseArgs = [il::Val::Imm(0)];

            let mut defaultArgs = [il::Val::Imm(0)];

            if inDefault {

                set defaultArgs[0] = il::Val::Reg(source);

            } else {

                set caseArgs[0] = il::Val::Reg(source);

            }

            let mut cases = [il::SwitchCase { value: 1, target: 1, args: &mut caseArgs[..] }];

            let mut entry = [il::Instr::Switch { val: il::Val::Imm(0),

                defaultTarget: 1, defaultArgs: &mut defaultArgs[..], cases: &mut cases[..] }];

            let params = [il::Param { value: il::Reg { n: 0 }, type: il::Type::W64 }];

            let mut exit = [il::Instr::Ret { val: il::Val::Reg(il::Reg { n: 0 }) }];

            let blocks = [block("entry", &mut entry[..]), il::Block { label: "exit",

                params: &params[..], instrs: &mut exit[..], locs: &[], preds: &[], loopDepth: 0 }];

            let function = il::Fn { name: "argument", params: &[], returnType: il::Type::W64,

                isExtern: false, isLeaf: true, blocks: &blocks[..] };

            static DATA: [u8; 32768] = [0; 32768];

            let mut arena = alloc::new(&mut DATA[..]);

            use arena as analysis in {

                let live = try super::analyze(&function, &analysis) catch {

                    assert index == 0xffffffff;

                    continue;

                };

                assert index <> 0xffffffff;

                assert live.maxReg == index + 1;

                assert bitset::contains(super::liveInRow(&live, 0), index);

            }

        }

    }

}

/// An unrepresentable register extent fails before any bitset access.

@test unsafe fn testRegisterExtentOverflow() throws (testing::TestError) {

    for instruction in [

        il::Instr::Ret { val: il::Val::Reg(il::Reg { n: 0xffffffff }) },

        il::Instr::Copy { dst: il::Reg { n: 0xffffffff }, val: il::Val::Imm(0) },

    ] {

        let mut instructions = [instruction];

        let blocks = [block("entry", &mut instructions[..])];

        let function = il::Fn { name: "overflow", params: &[], returnType: il::Type::W64,

            isExtern: false, isLeaf: true, blocks: &blocks[..] };

        static DATA: [u8; 1024] = [0; 1024];

        let mut arena = alloc::new(&mut DATA[..]);

        let mut failed = false;

        use arena as analysis in {

            try super::analyze(&function, &analysis) catch {

                set failed = true;

            };

        }

        assert failed;

        assert arena.offset == 0;

    }

}

/// Check one bit in each word of a three-word row.

fn check(words: &[u32], first: bool, second: bool, third: bool) throws (testing::TestError) {

    try testing::expect(words.len == 3);

    try testing::expect(bitset::contains(words, 0) == first);

    try testing::expect(bitset::contains(words, 33) == second);

    try testing::expect(bitset::contains(words, 66) == third);

}

/// Multiple spill slots preserve register order and reject total-frame overflow.

@test unsafe fn testMultipleSpillOffsets() throws (testing::TestError) {

    for size in [0 as u32, 8, 0x2aaaaaaa, 0x2aaaaaab] {

        let first = il::Reg { n: 0 };

        let second = il::Reg { n: 33 };

        let result = il::Reg { n: 66 };

        let mut instructions = [

            il::Instr::Copy { dst: first, val: il::Val::Imm(1) },

            il::Instr::Copy { dst: second, val: il::Val::Imm(2) },

            il::Instr::BinOp { op: il::BinOp::Add, typ: il::Type::W64,

                dst: result, a: il::Val::Reg(first), b: il::Val::Reg(second) },

            il::Instr::Ret { val: il::Val::Reg(result) },

        ];

        let blocks = [block("entry", &mut instructions[..])];

        let function = il::Fn { name: "offsets", params: &[], returnType: il::Type::W64,

            isExtern: false, isLeaf: true, blocks: &blocks[..] };

        static DATA: [u8; 16384] = [0; 16384];

        let mut arena = alloc::new(&mut DATA[..]);

        use arena as analysis in {

            let live = try! super::analyze(&function, &analysis);

            let info = try spill::analyze(&function, &live, 0, 0, size, &analysis) catch {

                assert size == 0x2aaaaaab;

                continue;

            };

            assert size <= 0x2aaaaaaa;

            assert info.slots[0] == 0;

            assert info.slots[33] == size as i32;

            assert info.slots[66] == (size * 2) as i32;

            assert info.slots[1] == -1;

            assert info.frameSize == (size * 3) as i32;

        }

    }

}

/// Spill frame sizes must fit their signed byte-offset representation.

@test unsafe fn testSpillFrameExtent() throws (testing::TestError) {

    for size in [0x7fffffff as u32, 0x80000000, 0xffffffff] {

        let value = il::Reg { n: 0 };

        let mut instructions = [

            il::Instr::Copy { dst: value, val: il::Val::Imm(1) },

            il::Instr::Ret { val: il::Val::Reg(value) },

        ];

        let blocks = [block("entry", &mut instructions[..])];

        let function = il::Fn { name: "frame", params: &[], returnType: il::Type::W64,

            isExtern: false, isLeaf: true, blocks: &blocks[..] };

        static DATA: [u8; 4096] = [0; 4096];

        let mut arena = alloc::new(&mut DATA[..]);

        use arena as analysis in {

            let live = try! super::analyze(&function, &analysis);

            let info = try spill::analyze(&function, &live, 0, 0, size, &analysis) catch {

                assert size > 0x7fffffff;

                continue;

            };

            assert size == 0x7fffffff;

            assert info.frameSize == 2147483647;

            assert info.slots[0] == 0;

        }

    }

}

/// Loop-weighted uses retain hot values and cap large loop depths.

@test unsafe fn testLoopWeightedSpills() throws (testing::TestError) {

    let first = il::Reg { n: 0 };

    let second = il::Reg { n: 33 };

    let temporary = il::Reg { n: 66 };

    let mut entry = [

        il::Instr::Copy { dst: first, val: il::Val::Imm(1) },

        il::Instr::Copy { dst: second, val: il::Val::Imm(2) },

        il::Instr::Jmp { target: 1, args: &mut [] },

    ];

    let mut body = [

        il::Instr::Copy { dst: temporary, val: il::Val::Reg(first) },

        il::Instr::Jmp { target: 2, args: &mut [] },

    ];

    let mut exit = [il::Instr::Ret { val: il::Val::Reg(second) }];

    for depth in [0 as u32, 1, 10, 11, 32, 0xffffffff] {

        let mut weighted = block("body", &mut body[..]);

        set weighted.loopDepth = depth;

        let blocks = [block("entry", &mut entry[..]), weighted, block("exit", &mut exit[..])];

        let function = il::Fn { name: "weighted", params: &[], returnType: il::Type::W64,

            isExtern: false, isLeaf: true, blocks: &blocks[..] };

        static DATA: [u8; 8192] = [0; 8192];

        let mut arena = alloc::new(&mut DATA[..]);

        use arena as analysis in {

            let live = try! super::analyze(&function, &analysis);

            let info = try! spill::analyze(&function, &live, 1, 0, 8, &analysis);

            assert spill::isSpilled(&info, first) == (depth == 0);

            assert spill::isSpilled(&info, second) == (depth > 0);

            assert not spill::isSpilled(&info, temporary);

            assert info.frameSize == 8;

        }

    }

}

/// Cross-call pressure excludes the result and spills equal-cost values in order.

@test unsafe fn testCrossCallPressure() throws (testing::TestError) {

    let first = il::Reg { n: 0 };

    let second = il::Reg { n: 33 };

    let result = il::Reg { n: 66 };

    let sum = il::Reg { n: 67 };

    let total = il::Reg { n: 68 };

    let params = [il::Param { value: first, type: il::Type::W64 },

        il::Param { value: second, type: il::Type::W64 }];

    let args = [il::Val::Reg(first), il::Val::Reg(second)];

    let mut instructions = [

        il::Instr::Call { retTy: il::Type::W64, dst: result,

            func: il::Val::FnAddr("callee"), args: &args[..] },

        il::Instr::BinOp { op: il::BinOp::Add, typ: il::Type::W64, dst: sum,

            a: il::Val::Reg(first), b: il::Val::Reg(second) },

        il::Instr::BinOp { op: il::BinOp::Add, typ: il::Type::W64, dst: total,

            a: il::Val::Reg(sum), b: il::Val::Reg(result) },

        il::Instr::Ret { val: il::Val::Reg(total) },

    ];

    let blocks = [block("entry", &mut instructions[..]), block("empty", &mut [])];

    let function = il::Fn { name: "crossing", params: &params[..], returnType: il::Type::W64,

        isExtern: false, isLeaf: false, blocks: &blocks[..] };

    for capacity in [0 as u32, 1, 2] {

        static DATA: [u8; 8192] = [0; 8192];

        let mut arena = alloc::new(&mut DATA[..]);

        use arena as analysis in {

            let live = try! super::analyze(&function, &analysis);

            let info = try! spill::analyze(&function, &live, 8, capacity, 8, &analysis);

            assert spill::isSpilled(&info, first) == (capacity < 2);

            assert spill::isSpilled(&info, second) == (capacity == 0);

            assert not spill::isSpilled(&info, result);

            assert not spill::isSpilled(&info, sum);

            assert not spill::isSpilled(&info, total);

            assert bitset::contains(info.calleeClass, first.n) == (capacity == 2);

            assert bitset::contains(info.calleeClass, second.n) == (capacity > 0);

            assert not bitset::contains(info.calleeClass, result.n);

            assert info.frameSize == ((2 - capacity) * 8) as i32;

        }

    }

}

/// Function and block parameter extents receive the same overflow checks.

@test unsafe fn testParameterRegisterExtent() throws (testing::TestError) {

    for index in [16384 as u32, 0xffffffff] {

        for isFunction in [false, true] {

            let parameters = [il::Param { value: il::Reg { n: index }, type: il::Type::W64 }];

            let mut instructions = [il::Instr::Ret { val: il::Val::Imm(0) }];

            let mut entry = block("entry", &mut instructions[..]);

            if not isFunction {

                set entry.params = &parameters[..];

            }

            let blocks = [entry];

            let mut function = il::Fn { name: "parameter", params: &[], returnType: il::Type::W64,

                isExtern: false, isLeaf: true, blocks: &blocks[..] };

            if isFunction {

                set function.params = &parameters[..];

            }

            static DATA: [u8; 16384] = [0; 16384];

            let mut arena = alloc::new(&mut DATA[..]);

            use arena as analysis in {

                let live = try super::analyze(&function, &analysis) catch {

                    assert index == 0xffffffff;

                    continue;

                };

                assert index == 16384;

                assert live.maxReg == index + 1;

                assert bitset::contains(&live.defs[..], index) == not isFunction;

            }

        }

    }

}

@test unsafe fn testLoopLiveness() throws (testing::TestError) {

    let r0 = il::Reg { n: 0 };

    let r33 = il::Reg { n: 33 };

    let r66 = il::Reg { n: 66 };

    let mut entry = [

        il::Instr::Copy { dst: r0, val: il::Val::Imm(7) },

        il::Instr::Jmp { target: 1, args: &mut [] },

    ];

    let mut head = [

        il::Instr::Copy { dst: r33, val: il::Val::Reg(r0) },

        il::Instr::Br { op: il::CmpOp::Eq, typ: il::Type::W64,

            a: il::Val::Reg(r33), b: il::Val::Imm(0),

            thenTarget: 2, thenArgs: &mut [], elseTarget: 3, elseArgs: &mut [] },

    ];

    let mut body = [

        il::Instr::BinOp { op: il::BinOp::Add, typ: il::Type::W64,

            dst: r66, a: il::Val::Reg(r33), b: il::Val::Imm(1) },

        il::Instr::Jmp { target: 1, args: &mut [] },

    ];

    let mut exit = [il::Instr::Ret { val: il::Val::Reg(r33) }];

    let blocks = [block("entry", &mut entry[..]), block("head", &mut head[..]),

        block("body", &mut body[..]), block("exit", &mut exit[..])];

    let function = il::Fn { name: "loop", params: &[], returnType: il::Type::W64,

        isExtern: false, isLeaf: true, blocks: &blocks[..] };

    static DATA: [u8; 8192] = [0; 8192];

    let mut arena = alloc::new(&mut DATA[..]);

    let mut answer: u32 = 0;

    use arena as analysis in {

        let live = try! super::analyze(&function, &analysis);

        try testing::expect(live.blockCount == 4);

        try testing::expect(live.maxReg == 67);

        try testing::expect(live.words == 3);

        try check(super::liveInRow(&live, 0), false, false, false);

        try check(super::liveOutRow(&live, 0), true, false, false);

        try check(super::liveInRow(&live, 1), true, false, false);

        try check(super::liveOutRow(&live, 1), true, true, false);

        try check(super::liveInRow(&live, 2), true, true, false);

        try check(super::liveOutRow(&live, 2), true, false, false);

        try check(super::liveInRow(&live, 3), false, true, false);

        try check(super::liveOutRow(&live, 3), false, false, false);

        try check(&live.defs[6..9], false, false, true);

        try check(&live.uses[6..9], false, true, false);

        set answer = 42;

    }

    alloc::reset(&mut arena);

    try testing::expect(answer == 42);

}