radiance · commit

regalloc: Avoid rescanning current operands

80166a832bc5984877f11eb326ffff6d40a6ef5baf5b3f294b4ae192c7223112

`isLastUse` searched the current instruction even though its only
caller invoked it while visiting an operand of that instruction.

Express the query as `hasLaterUse` and inspect only later
instructions and live-out state. This removes one complete operand
traversal from every last-use query.

Assisted-by: Codex:gpt-5.6-sol

Alexis Sellier committed 1 month ago 1 parent abd19748

lib/std/lang/gen/regalloc/assign.rad +1 -1

}

/// Callback for [`il::forEachReg`]: free last uses and allocate missing uses.
fn processInstrRegCb(reg: il::Reg, ctxPtr: *mut opaque) {
    let ctx = ctxPtr as *mut InstrCtx;
    if liveness::isLastUse(ctx.live, ctx.func, ctx.blockIdx, ctx.instrIdx, reg) {
    if not liveness::hasLaterUse(ctx.live, ctx.func, ctx.blockIdx, ctx.instrIdx, reg) {
        if let phys = rmapFind(ctx.current, reg.n) {
            bitset::clear(ctx.usedRegs, *phys as u32);
            rmapRemove(ctx.current, reg.n);
        }
    }

lib/std/lang/gen/regalloc/liveness.rad +7 -11

//!         liveOut[b] = newOut
//!
//! Usage:
//!
//!   let live = liveness::analyze(func, ...);
//!   if liveness::isLastUse(&live, func, blockIdx, instrIdx, reg) {
//!       // `reg` last use is at this instruction.
//!   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;

/// 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]);
}

/// Check if this is the last use of a register at this instruction.
export fn isLastUse(info: *LiveInfo, func: *il::Fn, blockIdx: u32, instrIdx: u32, reg: il::Reg) -> bool {
/// 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];
    let instr = block.instrs[instrIdx];

    if not instrUsesReg(instr, reg) {
        return false;
    }
    if bitset::contains(&info.liveOut[blockIdx], reg.n) {
        return false;
        return true;
    }
    for i in (instrIdx + 1)..block.instrs.len {
        if instrUsesReg(block.instrs[i], reg) {
            return false;
            return true;
        }
    }
    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 };

279	279		}
280	280
281	281		/// Callback for [`il::forEachReg`]: free last uses and allocate missing uses.
282	282		fn processInstrRegCb(reg: il::Reg, ctxPtr: *mut opaque) {
283	283		let ctx = ctxPtr as *mut InstrCtx;
284		-	if liveness::isLastUse(ctx.live, ctx.func, ctx.blockIdx, ctx.instrIdx, reg) {
	284	+	if not liveness::hasLaterUse(ctx.live, ctx.func, ctx.blockIdx, ctx.instrIdx, reg) {
285	285		if let phys = rmapFind(ctx.current, reg.n) {
286	286		bitset::clear(ctx.usedRegs, *phys as u32);
287	287		rmapRemove(ctx.current, reg.n);
288	288		}
289	289		}

222	222		/// Union a target block's "live in" set into scratch.
223	223		fn unionBlockLiveIn(target: u32, liveIn: [bitset::Bitset], scratch: mut bitset::Bitset) {
224	224		bitset::union_(scratch, &liveIn[target]);
225	225		}
226	226
227		-	/// Check if this is the last use of a register at this instruction.
228		-	export fn isLastUse(info: LiveInfo, func: il::Fn, blockIdx: u32, instrIdx: u32, reg: il::Reg) -> bool {
	227	+	/// Check if a register has any use after this instruction.
	228	+	export fn hasLaterUse(info: LiveInfo, func: il::Fn, blockIdx: u32, instrIdx: u32, reg: il::Reg) -> bool {
229	229		let block = &func.blocks[blockIdx];
230		-	let instr = block.instrs[instrIdx];
231	230
232		-	if not instrUsesReg(instr, reg) {
233		-	return false;
234		-	}
235	231		if bitset::contains(&info.liveOut[blockIdx], reg.n) {
236		-	return false;
	232	+	return true;
237	233		}
238	234		for i in (instrIdx + 1)..block.instrs.len {
239	235		if instrUsesReg(block.instrs[i], reg) {
240		-	return false;
	236	+	return true;
241	237		}
242	238		}
243		-	return true;
	239	+	return false;
244	240		}
245	241
246	242		/// Check if an instruction uses a specific register.
247	243		fn instrUsesReg(instr: il::Instr, reg: il::Reg) -> bool {
248	244		let mut ctx = FindCtx { target: reg.n, found: false };

17	17		//! liveOut[b] = newOut
18	18		//!
19	19		//! Usage:
20	20		//!
21	21		//! let live = liveness::analyze(func, ...);
22		-	//! if liveness::isLastUse(&live, func, blockIdx, instrIdx, reg) {
23		-	//! // `reg` last use is at this instruction.
	22	+	//! if not liveness::hasLaterUse(&live, func, blockIdx, instrIdx, reg) {
	23	+	//! // `reg` dies at this instruction.
24	24		//! }
25	25
26	26		use std::mem;
27	27		use std::lang::il;
28	28		use std::lang::alloc;