radiance · commit

compiler: Check register assignment pipeline and block scans

91d5c00e4e1e17dac2b2bd77d910ddfa9fe7460fc38c284d9f2713cce66805f2

Alexis Sellier committed 6 days ago 1 parent 39698da5

lib/std/lang/gen/regalloc/assign.rad +77 -47

    assignments: &'scratch [?gen::Reg],
    /// Bitmask of used callee-saved registers.
    usedCalleeSaved: u32,
}

/// Per-instruction context for freeing and allocating register uses.
/// Register state for scanning one block's instructions.
record InstrCtx: 'scratch + 'step where 'scratch: 'step {
    current: &'step mut RegMap 'scratch,
    usedRegs: &'step mut [u32],
    /// Last operand-use index for each register used in the current block.
    lastUse: &'step [u32],
    lastUse: &'step mut [u32],
    live: &'step liveness::LiveInfo 'scratch,
    blockIdx: u32,
    instrIdx: u32,
    allocatable: *[gen::Reg],
    calleeSaved: *[gen::Reg],

    func: &il::Fn,
    live: &liveness::LiveInfo 'scratch,
    spillInfo: &spill::SpillInfo 'scratch,
    config: &super::TargetConfig,
    storage: &Session 'scratch
) -> AssignInfo 'scratch throws (alloc::AllocError) {
    return try assignTables(func.params, func.blocks, live, spillInfo, config, storage);
}

/// Allocate register mappings for borrowed function parameter and block tables.
fn assignTables 'scratch (
    params: &[il::Param],
    blocks: &[il::Block],
    live: &liveness::LiveInfo 'scratch,
    spillInfo: &spill::SpillInfo 'scratch,
    config: &super::TargetConfig,
    storage: &Session 'scratch,
) -> AssignInfo 'scratch throws (alloc::AllocError) {
    let maxReg = live.maxReg;
    let blockCount = func.blocks.len;
    let blockCount = blocks.len;
    let allocatable = config.allocatable;

    if maxReg == 0 or blockCount == 0 {
        return AssignInfo 'scratch {
            assignments: try storage.fill(nil as ?gen::Reg, 0),

    let assignments = try storage.fill(nil as ?gen::Reg, maxReg);
    // 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 {
    for param, i in params {
        if i < config.argRegs.len {
            if not bitset::contains(spillInfo.calleeClass, param.value.n) {
                set assignments[param.value.n] = config.argRegs[i];
            }
        }

    let lastUse = try storage.fill(0 as u32, maxReg);
    let mut current = try createRegMap(storage);

    // 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 registers = il::registers(&instr);
            while let reg = il::nextReg(&mut registers, &instr) {
                recordLastUse(reg, &mut lastUse[..], i);
            }
        }

        enterBlock(&mut current, usedRegs, liveness::liveInRow(live, b), block.params, assignments, config, spillInfo);

        // Process each instruction.
        for instr, i in block.instrs {
            let currentRef: 'step = &mut current, usedRef = &mut usedRegs[..],
                lastUseRef = &lastUse[..], liveRef = &*live,
                assignmentsRef = &mut assignments[..], spillRef = &*spillInfo
            where 'scratch: 'step in {
                let mut ctx = InstrCtx 'scratch 'step {
                    current: currentRef,
                    usedRegs: usedRef,
                    lastUse: lastUseRef,
                    live: liveRef,
                    blockIdx: b,
                    instrIdx: i,
                    allocatable,
                    calleeSaved: config.calleeSaved,
                    assignments: assignmentsRef,
                    spillInfo: spillRef,
                };
                let mut registers = il::registers(&instr);
                while let reg = il::nextReg(&mut registers, &instr) {
                    processInstrReg(reg, &mut ctx);
                }
            }

            // Allocate destination.
            if let dst = il::instrDst(instr) {
                if dst.n < maxReg and not spill::isSpilled(spillInfo, dst) {
                    set assignments[dst.n] = rallocReg(&mut current, usedRegs, dst.n, allocatable, config.calleeSaved, spillInfo);
                }
        let block = &blocks[b];
        let currentRef: 'step = &mut current, usedRef = &mut usedRegs[..],
            lastUseRef = &mut lastUse[..], liveRef = &*live,
            assignmentsRef = &mut assignments[..], spillRef = &*spillInfo
        where 'scratch: 'step in {
            let mut ctx = InstrCtx 'scratch 'step {
                current: currentRef,
                usedRegs: usedRef,
                lastUse: lastUseRef,
                live: liveRef,
                blockIdx: b,
                instrIdx: 0,
                allocatable,
                calleeSaved: config.calleeSaved,
                assignments: assignmentsRef,
                spillInfo: spillRef,
            };
            unsafe {
                assignBlock(block.params, block.instrs, &mut ctx, config);
            }
        }
    }
    // Compute bitmask of used callee-saved registers.
    let mut usedCalleeSaved: u32 = 0;

        assignments: &assignments[..],
        usedCalleeSaved,
    };
}

/// Assign one block's source and destination registers in instruction order.
fn assignBlock 'scratch 'step (
    params: &[il::Param],
    instructions: &[il::Instr],
    ctx: &mut InstrCtx 'scratch 'step,
    config: &super::TargetConfig,
) where 'scratch: 'step {
    // 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 i in 0..instructions.len {
        let instr = &instructions[i];
        let mut registers = il::registers(instr);
        unsafe {
            while let reg = il::nextReg(&mut registers, instr) {
                recordLastUse(reg, ctx.lastUse, i);
            }
        }
    }

    enterBlock(ctx.current, ctx.usedRegs, liveness::liveInRow(ctx.live, ctx.blockIdx), params, ctx.assignments, config, ctx.spillInfo);

    // Process each instruction.
    for i in 0..instructions.len {
        let instr = &instructions[i];
        set ctx.instrIdx = i;
        let mut registers = il::registers(instr);
        unsafe {
            while let reg = il::nextReg(&mut registers, instr) {
                processInstrReg(reg, ctx);
            }
        }

        // Allocate destination.
        if let dst = il::instrDst(*instr) {
            if dst.n < ctx.assignments.len and not spill::isSpilled(ctx.spillInfo, dst) {
                set ctx.assignments[dst.n] = rallocReg(ctx.current, ctx.usedRegs, dst.n, ctx.allocatable, ctx.calleeSaved, ctx.spillInfo);
            }
        }
    }
}

/// Reserve live-in registers before assigning the block's parameter registers.
fn enterBlock 'scratch (
    current: &mut RegMap 'scratch,
    usedRegs: &mut [u32],
    liveIn: &[u32],

lib/std/lang/gen/regalloc/liveness/tests.rad +6 -0

use std::testing;
use std::lang::alloc;
use std::lang::il;
use std::lang::gen::bitset;
use std::lang::gen::regalloc::spill;
use std::lang::gen::regalloc::assign;
use std::lang::gen::regalloc;


/// Construct a block whose instruction storage belongs to the caller.
unsafe fn block(name: *[u8], instructions: *unsafe mut [il::Instr]) -> il::Block {
    return il::Block { label: name, params: &[], instrs: instructions,

            assert live.defs.len == 0 and live.uses.len == 0;
            let spills = try! spill::analyze(&function, &live, 0, 0, 8, &analysis);
            assert spills.maxReg == 0;
            assert spills.frameSize == 0;
            assert spills.slots.len == 0 and spills.calleeClass.len == 0;
            let config = regalloc::TargetConfig { allocatable: &[], argRegs: &[], calleeSaved: &[], slotSize: 8 };
            let assigned = try! assign::assign(&function, &live, &spills, &config, &analysis);
            assert assigned.assignments.len == 0;
            assert assigned.usedCalleeSaved == 0;
        }
    }
}

/// Insufficient matrix storage reports an allocation error.

73	85		let assignments = try storage.fill(nil as ?gen::Reg, maxReg);
74	86		// Pre-assign function parameters to argument registers.
75	87		// Cross-call params are NOT pre-assigned here; they will be allocated
76	88		// to callee-saved registers by the normal path, and isel emits moves
77	89		// from the arg register to the assigned register at function entry.
78		-	for param, i in func.params {
	90	+	for param, i in params {
79	91		if i < config.argRegs.len {
80	92		if not bitset::contains(spillInfo.calleeClass, param.value.n) {
81	93		set assignments[param.value.n] = config.argRegs[i];
82	94		}
83	95		}

90	102		let lastUse = try storage.fill(0 as u32, maxReg);
91	103		let mut current = try createRegMap(storage);
92	104
93	105		// Phase 2: Linear scan allocation.
94	106		for b in 0..blockCount {
95		-	let block = &func.blocks[b];
96		-
97		-	// Record every operand before allocation. Only current-block operands
98		-	// query this table, so every read is initialized by this scan.
99		-	// Entries for other registers need not be cleared between blocks.
100		-	for instr, i in block.instrs {
101		-	let mut registers = il::registers(&instr);
102		-	while let reg = il::nextReg(&mut registers, &instr) {
103		-	recordLastUse(reg, &mut lastUse[..], i);
104		-	}
105		-	}
106		-
107		-	enterBlock(&mut current, usedRegs, liveness::liveInRow(live, b), block.params, assignments, config, spillInfo);
108		-
109		-	// Process each instruction.
110		-	for instr, i in block.instrs {
111		-	let currentRef: 'step = &mut current, usedRef = &mut usedRegs[..],
112		-	lastUseRef = &lastUse[..], liveRef = &*live,
113		-	assignmentsRef = &mut assignments[..], spillRef = &*spillInfo
114		-	where 'scratch: 'step in {
115		-	let mut ctx = InstrCtx 'scratch 'step {
116		-	current: currentRef,
117		-	usedRegs: usedRef,
118		-	lastUse: lastUseRef,
119		-	live: liveRef,
120		-	blockIdx: b,
121		-	instrIdx: i,
122		-	allocatable,
123		-	calleeSaved: config.calleeSaved,
124		-	assignments: assignmentsRef,
125		-	spillInfo: spillRef,
126		-	};
127		-	let mut registers = il::registers(&instr);
128		-	while let reg = il::nextReg(&mut registers, &instr) {
129		-	processInstrReg(reg, &mut ctx);
130		-	}
131		-	}
132		-
133		-	// Allocate destination.
134		-	if let dst = il::instrDst(instr) {
135		-	if dst.n < maxReg and not spill::isSpilled(spillInfo, dst) {
136		-	set assignments[dst.n] = rallocReg(&mut current, usedRegs, dst.n, allocatable, config.calleeSaved, spillInfo);
137		-	}
	107	+	let block = &blocks[b];
	108	+	let currentRef: 'step = &mut current, usedRef = &mut usedRegs[..],
	109	+	lastUseRef = &mut lastUse[..], liveRef = &*live,
	110	+	assignmentsRef = &mut assignments[..], spillRef = &*spillInfo
	111	+	where 'scratch: 'step in {
	112	+	let mut ctx = InstrCtx 'scratch 'step {
	113	+	current: currentRef,
	114	+	usedRegs: usedRef,
	115	+	lastUse: lastUseRef,
	116	+	live: liveRef,
	117	+	blockIdx: b,
	118	+	instrIdx: 0,
	119	+	allocatable,
	120	+	calleeSaved: config.calleeSaved,
	121	+	assignments: assignmentsRef,
	122	+	spillInfo: spillRef,
	123	+	};
	124	+	unsafe {
	125	+	assignBlock(block.params, block.instrs, &mut ctx, config);
138	126		}
139	127		}
140	128		}
141	129		// Compute bitmask of used callee-saved registers.
142	130		let mut usedCalleeSaved: u32 = 0;

154	142		assignments: &assignments[..],
155	143		usedCalleeSaved,
156	144		};
157	145		}
158	146
	147	+	/// Assign one block's source and destination registers in instruction order.
	148	+	fn assignBlock 'scratch 'step (
	149	+	params: &[il::Param],
	150	+	instructions: &[il::Instr],
	151	+	ctx: &mut InstrCtx 'scratch 'step,
	152	+	config: &super::TargetConfig,
	153	+	) where 'scratch: 'step {
	154	+	// Record every operand before allocation. Only current-block operands
	155	+	// query this table, so every read is initialized by this scan.
	156	+	// Entries for other registers need not be cleared between blocks.
	157	+	for i in 0..instructions.len {
	158	+	let instr = &instructions[i];
	159	+	let mut registers = il::registers(instr);
	160	+	unsafe {
	161	+	while let reg = il::nextReg(&mut registers, instr) {
	162	+	recordLastUse(reg, ctx.lastUse, i);
	163	+	}
	164	+	}
	165	+	}
	166	+
	167	+	enterBlock(ctx.current, ctx.usedRegs, liveness::liveInRow(ctx.live, ctx.blockIdx), params, ctx.assignments, config, ctx.spillInfo);
	168	+
	169	+	// Process each instruction.
	170	+	for i in 0..instructions.len {
	171	+	let instr = &instructions[i];
	172	+	set ctx.instrIdx = i;
	173	+	let mut registers = il::registers(instr);
	174	+	unsafe {
	175	+	while let reg = il::nextReg(&mut registers, instr) {
	176	+	processInstrReg(reg, ctx);
	177	+	}
	178	+	}
	179	+
	180	+	// Allocate destination.
	181	+	if let dst = il::instrDst(*instr) {
	182	+	if dst.n < ctx.assignments.len and not spill::isSpilled(ctx.spillInfo, dst) {
	183	+	set ctx.assignments[dst.n] = rallocReg(ctx.current, ctx.usedRegs, dst.n, ctx.allocatable, ctx.calleeSaved, ctx.spillInfo);
	184	+	}
	185	+	}
	186	+	}
	187	+	}
	188	+
159	189		/// Reserve live-in registers before assigning the block's parameter registers.
160	190		fn enterBlock 'scratch (
161	191		current: &mut RegMap 'scratch,
162	192		usedRegs: &mut [u32],
163	193		liveIn: &[u32],

31	33		assert live.defs.len == 0 and live.uses.len == 0;
32	34		let spills = try! spill::analyze(&function, &live, 0, 0, 8, &analysis);
33	35		assert spills.maxReg == 0;
34	36		assert spills.frameSize == 0;
35	37		assert spills.slots.len == 0 and spills.calleeClass.len == 0;
	38	+	let config = regalloc::TargetConfig { allocatable: &[], argRegs: &[], calleeSaved: &[], slotSize: 8 };
	39	+	let assigned = try! assign::assign(&function, &live, &spills, &config, &analysis);
	40	+	assert assigned.assignments.len == 0;
	41	+	assert assigned.usedCalleeSaved == 0;
36	42		}
37	43		}
38	44		}
39	45
40	46		/// Insufficient matrix storage reports an allocation error.

33	33		assignments: &'scratch [?gen::Reg],
34	34		/// Bitmask of used callee-saved registers.
35	35		usedCalleeSaved: u32,
36	36		}
37	37
38		-	/// Per-instruction context for freeing and allocating register uses.
	38	+	/// Register state for scanning one block's instructions.
39	39		record InstrCtx: 'scratch + 'step where 'scratch: 'step {
40	40		current: &'step mut RegMap 'scratch,
41	41		usedRegs: &'step mut [u32],
42	42		/// Last operand-use index for each register used in the current block.
43		-	lastUse: &'step [u32],
	43	+	lastUse: &'step mut [u32],
44	44		live: &'step liveness::LiveInfo 'scratch,
45	45		blockIdx: u32,
46	46		instrIdx: u32,
47	47		allocatable: *[gen::Reg],
48	48		calleeSaved: *[gen::Reg],

55	55		func: &il::Fn,
56	56		live: &liveness::LiveInfo 'scratch,
57	57		spillInfo: &spill::SpillInfo 'scratch,
58	58		config: &super::TargetConfig,
59	59		storage: &Session 'scratch
	60	+	) -> AssignInfo 'scratch throws (alloc::AllocError) {
	61	+	return try assignTables(func.params, func.blocks, live, spillInfo, config, storage);
	62	+	}
	63	+
	64	+	/// Allocate register mappings for borrowed function parameter and block tables.
	65	+	fn assignTables 'scratch (
	66	+	params: &[il::Param],
	67	+	blocks: &[il::Block],
	68	+	live: &liveness::LiveInfo 'scratch,
	69	+	spillInfo: &spill::SpillInfo 'scratch,
	70	+	config: &super::TargetConfig,
	71	+	storage: &Session 'scratch,
60	72		) -> AssignInfo 'scratch throws (alloc::AllocError) {
61	73		let maxReg = live.maxReg;
62		-	let blockCount = func.blocks.len;
	74	+	let blockCount = blocks.len;
63	75		let allocatable = config.allocatable;
64	76
65	77		if maxReg == 0 or blockCount == 0 {
66	78		return AssignInfo 'scratch {
67	79		assignments: try storage.fill(nil as ?gen::Reg, 0),

3	3		use std::testing;
4	4		use std::lang::alloc;
5	5		use std::lang::il;
6	6		use std::lang::gen::bitset;
7	7		use std::lang::gen::regalloc::spill;
	8	+	use std::lang::gen::regalloc::assign;
	9	+	use std::lang::gen::regalloc;
8	10
9	11
10	12		/// Construct a block whose instruction storage belongs to the caller.
11	13		unsafe fn block(name: [u8], instructions: unsafe mut [il::Instr]) -> il::Block {
12	14		return il::Block { label: name, params: &[], instrs: instructions,