//! 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::il::published;

use std::lang::alloc;

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

use super::flow;

/// 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 fn analyze 'input 'scratch (func: &published::Function 'input, 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 'input 'scratch (params: &[il::Param], blocks: &[published::Block 'input], 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;

    for parameter in params {

        try updateMaxReg(parameter.value, &mut maxReg);

    }

    for b in 0..blockCount {

        let block = &blocks[b];

        try updateExtent(block.params, block.instructions, &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];

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

    }

    let mut owner = flow::Permission {};

    let permission: 'permission = &mut owner in {

        let topology = try flow::snapshot(blocks, storage, permission);

        propagateLiveness(&topology, permission, blockCount, 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 'scratch 'permission (

    topology: &flow::Flow 'scratch 'permission,

    permission: &'permission mut flow::Permission,

    blockCount: u32,

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

        while b > 0 {

            set b -= 1;

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

            for successor in flow::successors(topology, b, permission) {

                unionBlockLiveIn(flow::index(successor), 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 'input (params: &[il::Param], instructions: &[published::Instruction 'input], 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];

        // Fixed operands precede the instruction's variable argument groups.

        for reg in published::registers(instr) {

            addUse(reg, defs, uses);

        }

        if let dst = published::destination(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 'input (params: &[il::Param], instructions: &[published::Instruction 'input], 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];

        // Fixed operands precede the instruction's variable argument groups.

        for reg in published::registers(instr) {

            try updateMaxReg(reg, max);

        }

        if let dst = published::destination(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;

    }

}

/// 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 fn hasLaterUse 'input 'scratch (info: &LiveInfo 'scratch, func: &published::Function 'input, 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.instructions, instrIdx, reg);

}

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

fn usesRegisterAfter 'input (instructions: &[published::Instruction 'input], instrIdx: u32, reg: il::Reg) -> bool {

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

        let instr = &instructions[i];

        // Fixed operands precede the instruction's variable argument groups.

        for source in published::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];

}