radiance · commit

regalloc: Index last operand uses per block

95ea08b12d856da1d042dcbb32db0513e4183cf719e317e756e86ffa0aa206d2

Repeated searches through later instructions duplicate operand work.
Record last-use indexes once per block and combine them with live-out
membership during allocation. Keep the public liveness query API.

Assisted-by: Codex:gpt-6-astra

Alexis Sellier committed 15 days ago 1 parent 7c9a7f91

lib/std/lang/gen/regalloc/assign.rad +29 -4


/// Per-instruction context for freeing and allocating register uses.
record InstrCtx: Copy {
    current: *mut RegMap,
    usedRegs: *mut bitset::Bitset,
    func: *il::Fn,
    /// Last operand-use index for each register used in the current block.
    lastUse: *[u32],
    live: *liveness::LiveInfo,
    blockIdx: u32,
    instrIdx: u32,
    allocatable: *[gen::Reg],
    calleeSaved: *[gen::Reg],
    assignments: *mut [?gen::Reg],
    spillInfo: *spill::SpillInfo,
}

/// Context for recording the last operand-use index in a block.
record LastUseCtx: Copy {
    /// Per-register indices, shared by all blocks in the function.
    lastUse: *mut [u32],
    /// Index of the instruction whose operands are being recorded.
    index: u32,
}

/// Compute register assignment.
export fn assign(
    func: *il::Fn,
    live: *liveness::LiveInfo,
    spillInfo: *spill::SpillInfo,

    // Allocate output structures.
    let assignments = try alloc::allocSlice(arena, @sizeOf(?gen::Reg), @alignOf(?gen::Reg), maxReg) as *mut [?gen::Reg];
    for i in 0..maxReg {
        set assignments[i] = nil;
    }
    // Reuse one last-use table for all blocks in the function.
    let lastUse = try alloc::allocSlice(arena, @sizeOf(u32), @alignOf(u32), maxReg) as *mut [u32];
    // Pre-assign function parameters to argument registers.
    // Cross-call params are NOT pre-assigned here; they will be allocated
    // to callee-saved registers by the normal path, and isel emits moves
    // from the arg register to the assigned register at function entry.
    for param, i in func.params {


    // Phase 2: Linear scan allocation.
    for b in 0..blockCount {
        let block = &func.blocks[b];

        // Record every operand before allocation. Only current-block operands
        // query this table, so every read is initialized by this scan.
        // Entries for other registers need not be cleared between blocks.
        for instr, i in block.instrs {
            let mut ctx = LastUseCtx { lastUse, index: i };
            il::forEachReg(instr, recordLastUseCb, &mut ctx as *mut opaque);
        }

        // Reset for new block.
        set current.n = 0;
        bitset::clearAll(&mut usedRegs);

        // Mark all live-in values' registers as used.

        // Process each instruction.
        for instr, i in block.instrs {
            let mut ctx = InstrCtx {
                current: &mut current,
                usedRegs: &mut usedRegs,
                func,
                lastUse,
                live,
                blockIdx: b,
                instrIdx: i,
                allocatable,
                calleeSaved: config.calleeSaved,

        return r;
    }
    panic "rallocReg: no free register, spilling fault";
}

/// Callback for [`il::forEachReg`]: free last uses and allocate missing uses.
/// Record the current index; forward traversal leaves the last operand use.
fn recordLastUseCb(reg: il::Reg, ctxPtr: *mut opaque) {
    let ctx = ctxPtr as *mut LastUseCtx;
    set ctx.lastUse[reg.n] = ctx.index;
}

/// Free operands with no later block use or live-out use, then allocate missing uses.
fn processInstrRegCb(reg: il::Reg, ctxPtr: *mut opaque) {
    let ctx = ctxPtr as *mut InstrCtx;
    if not liveness::hasLaterUse(ctx.live, ctx.func, ctx.blockIdx, ctx.instrIdx, reg) {
    if not (bitset::contains(&ctx.live.liveOut[ctx.blockIdx], reg.n) or ctx.lastUse[reg.n] > ctx.instrIdx) {
        if let phys = rmapRemove(ctx.current, reg.n) {
            bitset::clear(ctx.usedRegs, *phys as u32);
        }
    }
    assert reg.n < ctx.assignments.len, "processInstrRegCb: register out of bounds";

37	37
38	38		/// Per-instruction context for freeing and allocating register uses.
39	39		record InstrCtx: Copy {
40	40		current: *mut RegMap,
41	41		usedRegs: *mut bitset::Bitset,
42		-	func: *il::Fn,
	42	+	/// Last operand-use index for each register used in the current block.
	43	+	lastUse: *[u32],
43	44		live: *liveness::LiveInfo,
44	45		blockIdx: u32,
45	46		instrIdx: u32,
46	47		allocatable: *[gen::Reg],
47	48		calleeSaved: *[gen::Reg],
48	49		assignments: *mut [?gen::Reg],
49	50		spillInfo: *spill::SpillInfo,
50	51		}
51	52
	53	+	/// Context for recording the last operand-use index in a block.
	54	+	record LastUseCtx: Copy {
	55	+	/// Per-register indices, shared by all blocks in the function.
	56	+	lastUse: *mut [u32],
	57	+	/// Index of the instruction whose operands are being recorded.
	58	+	index: u32,
	59	+	}
	60	+
52	61		/// Compute register assignment.
53	62		export fn assign(
54	63		func: *il::Fn,
55	64		live: *liveness::LiveInfo,
56	65		spillInfo: *spill::SpillInfo,

93	104
94	105		// Phase 2: Linear scan allocation.
95	106		for b in 0..blockCount {
96	107		let block = &func.blocks[b];
97	108
	109	+	// Record every operand before allocation. Only current-block operands
	110	+	// query this table, so every read is initialized by this scan.
	111	+	// Entries for other registers need not be cleared between blocks.
	112	+	for instr, i in block.instrs {
	113	+	let mut ctx = LastUseCtx { lastUse, index: i };
	114	+	il::forEachReg(instr, recordLastUseCb, &mut ctx as *mut opaque);
	115	+	}
	116	+
98	117		// Reset for new block.
99	118		set current.n = 0;
100	119		bitset::clearAll(&mut usedRegs);
101	120
102	121		// Mark all live-in values' registers as used.

128	147		// Process each instruction.
129	148		for instr, i in block.instrs {
130	149		let mut ctx = InstrCtx {
131	150		current: &mut current,
132	151		usedRegs: &mut usedRegs,
133		-	func,
	152	+	lastUse,
134	153		live,
135	154		blockIdx: b,
136	155		instrIdx: i,
137	156		allocatable,
138	157		calleeSaved: config.calleeSaved,

250	269		return r;
251	270		}
252	271		panic "rallocReg: no free register, spilling fault";
253	272		}
254	273
255		-	/// Callback for [`il::forEachReg`]: free last uses and allocate missing uses.
	274	+	/// Record the current index; forward traversal leaves the last operand use.
	275	+	fn recordLastUseCb(reg: il::Reg, ctxPtr: *mut opaque) {
	276	+	let ctx = ctxPtr as *mut LastUseCtx;
	277	+	set ctx.lastUse[reg.n] = ctx.index;
	278	+	}
	279	+
	280	+	/// Free operands with no later block use or live-out use, then allocate missing uses.
256	281		fn processInstrRegCb(reg: il::Reg, ctxPtr: *mut opaque) {
257	282		let ctx = ctxPtr as *mut InstrCtx;
258		-	if not liveness::hasLaterUse(ctx.live, ctx.func, ctx.blockIdx, ctx.instrIdx, reg) {
	283	+	if not (bitset::contains(&ctx.live.liveOut[ctx.blockIdx], reg.n) or ctx.lastUse[reg.n] > ctx.instrIdx) {
259	284		if let phys = rmapRemove(ctx.current, reg.n) {
260	285		bitset::clear(ctx.usedRegs, *phys as u32);
261	286		}
262	287		}
263	288		assert reg.n < ctx.assignments.len, "processInstrRegCb: register out of bounds";

71	80		// Allocate output structures.
72	81		let assignments = try alloc::allocSlice(arena, @sizeOf(?gen::Reg), @alignOf(?gen::Reg), maxReg) as *mut [?gen::Reg];
73	82		for i in 0..maxReg {
74	83		set assignments[i] = nil;
75	84		}
	85	+	// Reuse one last-use table for all blocks in the function.
	86	+	let lastUse = try alloc::allocSlice(arena, @sizeOf(u32), @alignOf(u32), maxReg) as *mut [u32];
76	87		// Pre-assign function parameters to argument registers.
77	88		// Cross-call params are NOT pre-assigned here; they will be allocated
78	89		// to callee-saved registers by the normal path, and isel emits moves
79	90		// from the arg register to the assigned register at function entry.
80	91		for param, i in func.params {