//! 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;

/// Maximum number of SSA registers supported.

export constant MAX_SSA_REGS: u32 = 8192;

/// 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) {

    let blockCount = func.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;

    for p in func.params {

        set maxReg = maxRegNum(p.value.n, maxReg);

    }

    for b in 0..blockCount {

        let block = &func.blocks[b];

        for p in block.params {

            set maxReg = maxRegNum(p.value.n, maxReg);

        }

        for instr in block.instrs {

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

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

                updateMaxReg(reg, &mut maxReg);

            }

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

                set maxReg = maxRegNum(dst.n, maxReg);

            }

        }

    }

    if maxReg > MAX_SSA_REGS {

        throw alloc::AllocError::OutOfMemory;

    }

    // 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 {

        computeLocalDefsUses(&func.blocks[b], &mut defs[b * words..(b + 1) * words], &mut uses[b * words..(b + 1) * words]);

    }

    // 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 = blockCount;

        while b > 0 {

            set b -= 1;

            let block = &func.blocks[b];

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

            addSuccessorLiveIn(func, block, 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;

            }

        }

    }

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

}

/// 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.

unsafe fn computeLocalDefsUses(block: &il::Block, defs: &mut [u32], uses: &mut [u32]) {

    for p in block.params {

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

    }

    for instr in block.instrs {

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

        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);

    }

}

/// Update the largest register number.

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

    set *max = maxRegNum(reg.n, *max);

}

/// Return the larger of n+1 and current.

fn maxRegNum(n: u32, current: u32) -> u32 {

    if n >= MAX_SSA_REGS {

        return MAX_SSA_REGS + 1;

    }

    if n + 1 > current {

        return n + 1;

    }

    return current;

}

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

unsafe fn addSuccessorLiveIn(func: &il::Fn, block: &il::Block, liveIn: &[u32], words: u32, liveOut: &mut [u32]) {

    if block.instrs.len == 0 {

        return;

    }

    let term = block.instrs[block.instrs.len - 1];

    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, cases, .. } => {

            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;

    }

    for i in (instrIdx + 1)..block.instrs.len {

        if instrUsesReg(block.instrs[i], reg) {

            return true;

        }

    }

    return false;

}

/// Check if an instruction uses a specific register.

unsafe fn instrUsesReg(instr: il::Instr, reg: il::Reg) -> bool {

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

    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];

}