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

//!   }

use std::mem;

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: Copy {

    /// Per-block live-in sets (indexed by block index).

    liveIn: *mut [bitset::Bitset],

    /// Per-block live-out sets (indexed by block index).

    liveOut: *mut [bitset::Bitset],

    /// Per-block defs sets (registers defined in block).

    defs: *mut [bitset::Bitset],

    /// Per-block uses sets (registers used before defined in block).

    uses: *mut [bitset::Bitset],

    /// Number of blocks.

    blockCount: u32,

    /// Maximum register number used.

    maxReg: u32,

}

/// Context for collecting defs and uses during block analysis.

record DefsUses: Copy {

    defs: *bitset::Bitset,

    uses: *mut bitset::Bitset,

}

/// Context for searching for a specific register in an instruction.

record FindCtx: Copy {

    target: u32,

    found: bool,

}

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

export fn analyze(func: *il::Fn, arena: *mut alloc::Arena) -> LiveInfo throws (alloc::AllocError) {

    let blockCount = func.blocks.len;

    if blockCount == 0 {

        return LiveInfo {

            liveIn: &mut [],

            liveOut: &mut [],

            defs: &mut [],

            uses: &mut [],

            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 i in 0..block.instrs.len {

            il::forEachReg(block.instrs[i], maxRegCallback, &mut maxReg as *mut opaque);

            if let dst = il::instrDst(block.instrs[i]) {

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

            }

        }

    }

    assert maxReg <= MAX_SSA_REGS, "analyze: maximum SSA registers exceeded";

    // Allocate per-block bitsets.

    let liveIn = try alloc::allocSlice(arena, @sizeOf(bitset::Bitset), @alignOf(bitset::Bitset), blockCount) as *mut [bitset::Bitset];

    let liveOut = try alloc::allocSlice(arena, @sizeOf(bitset::Bitset), @alignOf(bitset::Bitset), blockCount) as *mut [bitset::Bitset];

    let defs = try alloc::allocSlice(arena, @sizeOf(bitset::Bitset), @alignOf(bitset::Bitset), blockCount) as *mut [bitset::Bitset];

    let uses = try alloc::allocSlice(arena, @sizeOf(bitset::Bitset), @alignOf(bitset::Bitset), blockCount) as *mut [bitset::Bitset];

    for b in 0..blockCount {

        set liveIn[b] = try bitset::allocate(arena, maxReg);

        set liveOut[b] = try bitset::allocate(arena, maxReg);

        set defs[b] = try bitset::allocate(arena, maxReg);

        set uses[b] = try bitset::allocate(arena, maxReg);

    }

    // Compute local defs and uses for each block.

    for b in 0..blockCount {

        computeLocalDefsUses(&func.blocks[b], &mut defs[b], &mut uses[b]);

    }

    // 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, &mut liveOut[b]);

            if computeAndUpdateLiveIn(&mut liveIn[b], &liveOut[b], &defs[b], &uses[b]) {

                set changed = true;

            }

        }

    }

    return LiveInfo { liveIn, liveOut, defs, uses, blockCount, maxReg };

}

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

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

fn computeAndUpdateLiveIn(

    dst: *mut bitset::Bitset,

    liveOut: *bitset::Bitset,

    defs: *bitset::Bitset,

    uses: *bitset::Bitset

) -> bool {

    let numWords = dst.bits.len;

    let mut changed = false;

    for i in 0..numWords {

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

        if dst.bits[i] <> newWord {

            set dst.bits[i] = newWord;

            set changed = true;

        }

    }

    return changed;

}

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

fn computeLocalDefsUses(block: *il::Block, defs: *mut bitset::Bitset, uses: *mut bitset::Bitset) {

    for p in block.params {

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

    }

    for i in 0..block.instrs.len {

        let instr = block.instrs[i];

        let mut ctx = DefsUses { defs, uses };

        il::forEachReg(instr, addUseCallback, &mut ctx as *mut opaque);

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

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

        }

    }

}

/// Callback for [`il::forEachReg`]: adds register to uses if not already defined.

fn addUseCallback(reg: il::Reg, ctx: *mut opaque) {

    let c = ctx as *mut DefsUses;

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

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

    }

}

/// Callback for [`il::forEachReg`]: updates max register number.

fn maxRegCallback(reg: il::Reg, ctx: *mut opaque) {

    let max = ctx as *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 + 1 > current {

        return n + 1;

    }

    return current;

}

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

fn addSuccessorLiveIn(func: *il::Fn, block: *il::Block, liveIn: *[bitset::Bitset], liveOut: *mut bitset::Bitset) {

    if block.instrs.len == 0 {

        return;

    }

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

    match term {

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

            unionBlockLiveIn(target, liveIn, liveOut),

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

            unionBlockLiveIn(thenTarget, liveIn, liveOut);

            unionBlockLiveIn(elseTarget, liveIn, liveOut);

        },

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

            unionBlockLiveIn(defaultTarget, liveIn, liveOut);

            for c in cases {

                unionBlockLiveIn(c.target, liveIn, liveOut);

            }

        },

        else => {},

    }

}

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

fn unionBlockLiveIn(target: u32, liveIn: *[bitset::Bitset], liveOut: *mut bitset::Bitset) {

    bitset::union_(liveOut, &liveIn[target]);

}

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

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

    let block = &func.blocks[blockIdx];

    if bitset::contains(&info.liveOut[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.

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

    let mut ctx = FindCtx { target: reg.n, found: false };

    il::forEachReg(instr, findRegCallback, &mut ctx as *mut opaque);

    return ctx.found;

}

/// Callback for [`il::forEachReg`]: sets found if register matches target.

fn findRegCallback(reg: il::Reg, ctx: *mut opaque) {

    let c = ctx as *mut FindCtx;

    if reg.n == c.target {

        set c.found = true;

    }

}