radiance · commit

regalloc: Grow liveness sets monotonically

2c74c0a9818708dfff9a32e527ddac87b405b62c51e88101a7f631eb5238adb1

Liveness sets start empty and only grow while the graph is fixed.
Accumulate successor live-in sets directly into live-out to avoid
scratch allocation, clearing, comparison, and copying.

Assisted-by: Codex:gpt-6-astra

Alexis Sellier committed 15 days ago 1 parent 02871810

lib/std/lang/gen/regalloc/liveness.rad +20 -25

//!
//! 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 iterative dataflow analysis:
//! 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
//!       newOut = UNION(liveIn[succ] FOR EACH SUCCESSOR OF b)
//!       newIn = uses[b] | (newOut - defs[b])
//!       IF newIn <> liveIn[b] OR newOut <> liveOut[b] THEN
//!       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
//!         liveOut[b] = newOut
//!
//! 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) {

record FindCtx: Copy {
    target: u32,
    found: bool,
}

/// Compute liveness information for a function.
/// 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 [],


    // Compute local defs and uses for each block.
    for b in 0..blockCount {
        computeLocalDefsUses(&func.blocks[b], &mut defs[b], &mut uses[b]);
    }
    // Iterative dataflow analysis.
    // Live sets grow monotonically from empty sets; no scratch set is needed.
    let mut changed = true;
    let mut scratch = try bitset::allocate(arena, maxReg);

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

            // Compute new `liveOut` as union of successor `liveIn` sets.
            bitset::clearAll(&mut scratch);
            addSuccessorLiveIn(func, block, liveIn, &mut scratch);
            // Add successor live-in sets directly to this block's live-out set.
            addSuccessorLiveIn(func, block, liveIn, &mut liveOut[b]);

            if not bitset::eq(&liveOut[b], &scratch) {
                bitset::copy(&mut liveOut[b], &scratch);
                set changed = true;
            }
            if computeAndUpdateLiveIn(&mut liveIn[b], &liveOut[b], &defs[b], &uses[b]) {
                set changed = true;
            }
        }
    }

        return n + 1;
    }
    return current;
}

/// Add successor "live in" sets to the scratch bitset.
fn addSuccessorLiveIn(func: *il::Fn, block: *il::Block, liveIn: *[bitset::Bitset], scratch: *mut bitset::Bitset) {
/// 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, scratch),
            unionBlockLiveIn(target, liveIn, liveOut),
        case il::Instr::Br { thenTarget, elseTarget, .. } => {
            unionBlockLiveIn(thenTarget, liveIn, scratch);
            unionBlockLiveIn(elseTarget, liveIn, scratch);
            unionBlockLiveIn(thenTarget, liveIn, liveOut);
            unionBlockLiveIn(elseTarget, liveIn, liveOut);
        },
        case il::Instr::Switch { defaultTarget, cases, .. } => {
            unionBlockLiveIn(defaultTarget, liveIn, scratch);
            unionBlockLiveIn(defaultTarget, liveIn, liveOut);
            for c in cases {
                unionBlockLiveIn(c.target, liveIn, scratch);
                unionBlockLiveIn(c.target, liveIn, liveOut);
            }
        },
        else => {},
    }
}

/// Union a target block's "live in" set into scratch.
fn unionBlockLiveIn(target: u32, liveIn: *[bitset::Bitset], scratch: *mut bitset::Bitset) {
    bitset::union_(scratch, &liveIn[target]);
/// 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];

57	58		record FindCtx: Copy {
58	59		target: u32,
59	60		found: bool,
60	61		}
61	62
62		-	/// Compute liveness information for a function.
	63	+	/// Compute liveness by growing live sets until no live-in set changes.
63	64		export fn analyze(func: il::Fn, arena: mut alloc::Arena) -> LiveInfo throws (alloc::AllocError) {
64	65		let blockCount = func.blocks.len;
65	66		if blockCount == 0 {
66	67		return LiveInfo {
67	68		liveIn: &mut [],

106	107
107	108		// Compute local defs and uses for each block.
108	109		for b in 0..blockCount {
109	110		computeLocalDefsUses(&func.blocks[b], &mut defs[b], &mut uses[b]);
110	111		}
111		-	// Iterative dataflow analysis.
	112	+	// Live sets grow monotonically from empty sets; no scratch set is needed.
112	113		let mut changed = true;
113		-	let mut scratch = try bitset::allocate(arena, maxReg);
114	114
115	115		while changed {
116	116		set changed = false;
117	117
118	118		// Process blocks in reverse order (approximates post-order).
119	119		let mut b = blockCount;
120	120		while b > 0 {
121	121		set b -= 1;
122	122		let block = &func.blocks[b];
123	123
124		-	// Compute new `liveOut` as union of successor `liveIn` sets.
125		-	bitset::clearAll(&mut scratch);
126		-	addSuccessorLiveIn(func, block, liveIn, &mut scratch);
	124	+	// Add successor live-in sets directly to this block's live-out set.
	125	+	addSuccessorLiveIn(func, block, liveIn, &mut liveOut[b]);
127	126
128		-	if not bitset::eq(&liveOut[b], &scratch) {
129		-	bitset::copy(&mut liveOut[b], &scratch);
130		-	set changed = true;
131		-	}
132	127		if computeAndUpdateLiveIn(&mut liveIn[b], &liveOut[b], &defs[b], &uses[b]) {
133	128		set changed = true;
134	129		}
135	130		}
136	131		}

193	188		return n + 1;
194	189		}
195	190		return current;
196	191		}
197	192
198		-	/// Add successor "live in" sets to the scratch bitset.
199		-	fn addSuccessorLiveIn(func: il::Fn, block: il::Block, liveIn: [bitset::Bitset], scratch: mut bitset::Bitset) {
	193	+	/// Add successor live-in sets to the block's live-out set.
	194	+	fn addSuccessorLiveIn(func: il::Fn, block: il::Block, liveIn: [bitset::Bitset], liveOut: mut bitset::Bitset) {
200	195		if block.instrs.len == 0 {
201	196		return;
202	197		}
203	198		let term = block.instrs[block.instrs.len - 1];
204	199
205	200		match term {
206	201		case il::Instr::Jmp { target, .. } =>
207		-	unionBlockLiveIn(target, liveIn, scratch),
	202	+	unionBlockLiveIn(target, liveIn, liveOut),
208	203		case il::Instr::Br { thenTarget, elseTarget, .. } => {
209		-	unionBlockLiveIn(thenTarget, liveIn, scratch);
210		-	unionBlockLiveIn(elseTarget, liveIn, scratch);
	204	+	unionBlockLiveIn(thenTarget, liveIn, liveOut);
	205	+	unionBlockLiveIn(elseTarget, liveIn, liveOut);
211	206		},
212	207		case il::Instr::Switch { defaultTarget, cases, .. } => {
213		-	unionBlockLiveIn(defaultTarget, liveIn, scratch);
	208	+	unionBlockLiveIn(defaultTarget, liveIn, liveOut);
214	209		for c in cases {
215		-	unionBlockLiveIn(c.target, liveIn, scratch);
	210	+	unionBlockLiveIn(c.target, liveIn, liveOut);
216	211		}
217	212		},
218	213		else => {},
219	214		}
220	215		}
221	216
222		-	/// Union a target block's "live in" set into scratch.
223		-	fn unionBlockLiveIn(target: u32, liveIn: [bitset::Bitset], scratch: mut bitset::Bitset) {
224		-	bitset::union_(scratch, &liveIn[target]);
	217	+	/// Union a target block's live-in set into the block's live-out set.
	218	+	fn unionBlockLiveIn(target: u32, liveIn: [bitset::Bitset], liveOut: mut bitset::Bitset) {
	219	+	bitset::union_(liveOut, &liveIn[target]);
225	220		}
226	221
227	222		/// Check if a register has any use after this instruction.
228	223		export fn hasLaterUse(info: LiveInfo, func: il::Fn, blockIdx: u32, instrIdx: u32, reg: il::Reg) -> bool {
229	224		let block = &func.blocks[blockIdx];

2	2		//!
3	3		//! Computes live-in and live-out sets for each basic block. A register is
4	4		//! "live" at a program point if its value may be used on some path from that
5	5		//! point to program exit.
6	6		//!
7		-	//! Uses iterative dataflow analysis:
	7	+	//! Uses monotone iterative dataflow analysis. All sets start empty and grow:
8	8		//!
9	9		//! REPEAT UNTIL changed == false
10	10		//! changed = false
11	11		//! FOR EACH BLOCK b IN POST-ORDER DO
12		-	//! newOut = UNION(liveIn[succ] FOR EACH SUCCESSOR OF b)
13		-	//! newIn = uses[b] \| (newOut - defs[b])
14		-	//! IF newIn <> liveIn[b] OR newOut <> liveOut[b] THEN
	12	+	//! liveOut[b] \|= UNION(liveIn[succ] FOR EACH SUCCESSOR OF b)
	13	+	//! newIn = uses[b] \| (liveOut[b] - defs[b])
	14	+	//! IF newIn <> liveIn[b] THEN
15	15		//! changed = true
16	16		//! liveIn[b] = newIn
17		-	//! liveOut[b] = newOut
	17	+	//!
	18	+	//! Only live-in changes require another pass, since predecessors read live-in.
18	19		//!
19	20		//! Usage:
20	21		//!
21	22		//! let live = liveness::analyze(func, ...);
22	23		//! if not liveness::hasLaterUse(&live, func, blockIdx, instrIdx, reg) {