//! Backward dataflow liveness analysis.

//!

//! Computes live-in and live-out sets for each basic block. A register is

//! "live" at a program point if its value may be used on some path from that

//! point to program exit.

//!

//! Uses monotone iterative dataflow analysis. All sets start empty and grow:

//!

//!   REPEAT UNTIL changed == false

//!     changed = false

//!     FOR EACH BLOCK b IN POST-ORDER DO

//!       liveOut[b] |= UNION(liveIn[succ] FOR EACH SUCCESSOR OF b)

//!       newIn = uses[b] | (liveOut[b] - defs[b])

//!       IF newIn <> liveIn[b] THEN

//!         changed = true

//!         liveIn[b] = newIn

//!

//! Only live-in changes require another pass, since predecessors read live-in.

//!

//! Usage:

//!

//!   let live = liveness::analyze(func, ...);

//!   if not liveness::hasLaterUse(&live, func, blockIdx, instrIdx, reg) {

//!       // `reg` dies at this instruction.

//!   }

@test mod tests;

use std::lang::il;

use std::lang::alloc;

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

/// Largest register index whose required entry count fits in u32.

constant MAX_REGISTER_INDEX: u32 = 0xfffffffe;

/// Liveness information for a function.

export record LiveInfo: 'scratch + Copy {

    /// Per-block live-in words, stored in consecutive rows.

    liveIn: &'scratch [u32],

    /// Per-block live-out words, stored in consecutive rows.

    liveOut: &'scratch [u32],

    /// Per-block definition words, stored in consecutive rows.

    defs: &'scratch [u32],

    /// Per-block use-before-definition words, stored in consecutive rows.

    uses: &'scratch [u32],

    /// Number of words in one block row.

    words: u32,

    /// Number of blocks.

    blockCount: u32,

    /// Maximum register number used.

    maxReg: u32,

}

/// Compute liveness by growing live sets until no live-in set changes.

export unsafe fn analyze 'scratch (func: &il::Fn, storage: &Session 'scratch) -> LiveInfo 'scratch throws (alloc::AllocError) {

    return try analyzeTables(func.params, func.blocks, storage);

}

/// Allocate and compute live sets for borrowed function parameter and block tables.

fn analyzeTables 'scratch (params: &[il::Param], blocks: &[il::Block], storage: &Session 'scratch) -> LiveInfo 'scratch throws (alloc::AllocError) {

    let blockCount = blocks.len;

    if blockCount == 0 {

        let empty = try storage.fill(0 as u32, 0);

        let frozen: &'scratch [u32] = &empty[..];

        return LiveInfo 'scratch { liveIn: frozen, liveOut: frozen, defs: frozen, uses: frozen, words: 0, blockCount: 0, maxReg: 0 };

    }

    // Find max register number.

    let mut maxReg: u32 = 0;

    try updateExtent(params, &[], &mut maxReg);

    for b in 0..blockCount {

        let block = &blocks[b];

        unsafe {

            try updateExtent(block.params, block.instrs, &mut maxReg);

        }

    }

    // Allocate one contiguous word matrix for each set class.

    let words = bitset::wordsFor(maxReg);

    let count64 = blockCount as u64 * words as u64;

    if count64 > 0xFFFFFFFF {

        throw alloc::AllocError::OutOfMemory;

    }

    let count = count64 as u32;

    let liveIn = try storage.fill(0 as u32, count);

    let liveOut = try storage.fill(0 as u32, count);

    let defs = try storage.fill(0 as u32, count);

    let uses = try storage.fill(0 as u32, count);

    // Compute local defs and uses for each block.

    for b in 0..blockCount {

        let block = &blocks[b];

        unsafe {

            computeLocalDefsUses(block.params, block.instrs, &mut defs[b * words..(b + 1) * words], &mut uses[b * words..(b + 1) * words]);

        }

    }

    propagateLiveness(blocks, liveIn, liveOut, defs, uses, words);

    return LiveInfo 'scratch { liveIn: &liveIn[..], liveOut: &liveOut[..], defs: &defs[..], uses: &uses[..], words, blockCount, maxReg };

}

/// Propagate successor uses until every block's live-in row is stable.

fn propagateLiveness(

    blocks: &[il::Block],

    liveIn: &mut [u32],

    liveOut: &mut [u32],

    defs: &[u32],

    uses: &[u32],

    words: u32,

) {

    // Live sets grow monotonically from empty sets; no scratch set is needed.

    let mut changed = true;

    while changed {

        set changed = false;

        // Process blocks in reverse order (approximates post-order).

        let mut b = blocks.len;

        while b > 0 {

            set b -= 1;

            let block = &blocks[b];

            // Add successor live-in sets directly to this block's live-out set.

            unsafe {

                addSuccessorLiveIn(block.instrs, liveIn, words, &mut liveOut[b * words..(b + 1) * words]);

            }

            if computeAndUpdateLiveIn(&mut liveIn[b * words..(b + 1) * words], &liveOut[b * words..(b + 1) * words], &defs[b * words..(b + 1) * words], &uses[b * words..(b + 1) * words]) {

                set changed = true;

            }

        }

    }

}

/// Compute `liveIn = uses | (liveOut - defs)` and update `dst`.

/// Returns `true` if `dst` changed. Combined loop avoids multiple passes.

fn computeAndUpdateLiveIn(

    dst: &mut [u32],

    liveOut: &[u32],

    defs: &[u32],

    uses: &[u32]

) -> bool {

    let mut changed = false;

    for i in 0..dst.len {

        let newWord = uses[i] | (liveOut[i] & ~defs[i]);

        if dst[i] <> newWord {

            set dst[i] = newWord;

            set changed = true;

        }

    }

    return changed;

}

/// Compute local defs and uses for a single block.

fn computeLocalDefsUses(params: &[il::Param], instructions: &[il::Instr], defs: &mut [u32], uses: &mut [u32]) {

    for p in params {

        bitset::put(defs, p.value.n);

    }

    for i in 0..instructions.len {

        let instr = &instructions[i];

        let mut registers = il::registers(instr);

        // Argument groups contain raw views into the function's IL storage.

        unsafe {

            while let reg = il::nextReg(&mut registers, instr) {

                addUse(reg, defs, uses);

            }

        }

        if let dst = il::instrDst(*instr) {

            bitset::put(defs, dst.n);

        }

    }

}

/// Add an undefined register to the use set.

fn addUse(reg: il::Reg, defs: &[u32], uses: &mut [u32]) {

    if not bitset::contains(defs, reg.n) {

        bitset::put(uses, reg.n);

    }

}

/// Include all parameter, source, and destination registers in the entry count.

fn updateExtent(params: &[il::Param], instructions: &[il::Instr], max: &mut u32) throws (alloc::AllocError) {

    for p in params {

        try updateMaxReg(p.value, max);

    }

    for i in 0..instructions.len {

        let instr = &instructions[i];

        let mut registers = il::registers(instr);

        // Argument groups contain raw views into the function's IL storage.

        unsafe {

            while let reg = il::nextReg(&mut registers, instr) {

                try updateMaxReg(reg, max);

            }

        }

        if let dst = il::instrDst(*instr) {

            try updateMaxReg(dst, max);

        }

    }

}

/// Retain the larger of the current entry count and the register index plus one.

fn updateMaxReg(reg: il::Reg, max: &mut u32) throws (alloc::AllocError) {

    if reg.n > MAX_REGISTER_INDEX {

        throw alloc::AllocError::OutOfMemory;

    }

    let count = reg.n + 1;

    if count > *max {

        set *max = count;

    }

}

/// Add successor live-in sets to the block's live-out set.

fn addSuccessorLiveIn(instructions: &[il::Instr], liveIn: &[u32], words: u32, liveOut: &mut [u32]) {

    if instructions.len == 0 {

        return;

    }

    let term = &instructions[instructions.len - 1];

    if let case il::Instr::Switch { cases, .. } = term {

        unsafe {

            mergeSuccessorLiveIn(term, *cases, liveIn, words, liveOut);

        }

    } else {

        mergeSuccessorLiveIn(term, &[], liveIn, words, liveOut);

    }

}

/// Merge live-in rows selected by a terminator and its borrowed switch cases.

fn mergeSuccessorLiveIn(term: &il::Instr, cases: &[il::SwitchCase], liveIn: &[u32], words: u32, liveOut: &mut [u32]) {

    match term {

        case il::Instr::Jmp { target, .. } =>

            unionBlockLiveIn(*target, liveIn, words, liveOut),

        case il::Instr::Br { thenTarget, elseTarget, .. } => {

            unionBlockLiveIn(*thenTarget, liveIn, words, liveOut);

            unionBlockLiveIn(*elseTarget, liveIn, words, liveOut);

        },

        case il::Instr::Switch { defaultTarget, .. } => {

            unionBlockLiveIn(*defaultTarget, liveIn, words, liveOut);

            for c in cases {

                unionBlockLiveIn(c.target, liveIn, words, liveOut);

            }

        },

        else => {},

    }

}

/// Union a target block's live-in set into the block's live-out set.

fn unionBlockLiveIn(target: u32, liveIn: &[u32], words: u32, liveOut: &mut [u32]) {

    bitset::union_(liveOut, &liveIn[target * words..(target + 1) * words]);

}

/// Check if a register has any use after this instruction.

export unsafe fn hasLaterUse 'scratch (info: &LiveInfo 'scratch, func: &il::Fn, blockIdx: u32, instrIdx: u32, reg: il::Reg) -> bool {

    let block = &func.blocks[blockIdx];

    if bitset::contains(liveOutRow(info, blockIdx), reg.n) {

        return true;

    }

    return usesRegisterAfter(block.instrs, instrIdx, reg);

}

/// Check if an instruction after the given index uses a specific register.

fn usesRegisterAfter(instructions: &[il::Instr], instrIdx: u32, reg: il::Reg) -> bool {

    for i in (instrIdx + 1)..instructions.len {

        let instr = &instructions[i];

        let mut registers = il::registers(instr);

        // Argument groups contain raw views into the function's IL storage.

        unsafe {

            while let source = il::nextReg(&mut registers, instr) {

                if source.n == reg.n {

                    return true;

                }

            }

        }

    }

    return false;

}

/// Borrow the live-in words for one block.

export fn liveInRow 'scratch (info: &LiveInfo 'scratch, block: u32) -> &'scratch [u32] {

    assert block < info.blockCount;

    return &info.liveIn[block * info.words..(block + 1) * info.words];

}

/// Borrow the live-out words for one block.

export fn liveOutRow 'scratch (info: &LiveInfo 'scratch, block: u32) -> &'scratch [u32] {

    assert block < info.blockCount;

    return &info.liveOut[block * info.words..(block + 1) * info.words];

}