radiance · commit

compiler: Check spill allocation and analysis pipeline

39698da53b5fe7a47668b294244240c0b67055de07830a061c6a79cbc5a4252e

Alexis Sellier committed 6 days ago 1 parent 4a63458b

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

            assert live.blockCount == count;
            assert live.maxReg == 0;
            assert live.words == 0;
            assert live.liveIn.len == 0 and live.liveOut.len == 0;
            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;
        }
    }
}

/// Insufficient matrix storage reports an allocation error.

        };
    }
    assert failed;
}

/// Spill storage exhaustion reports an error after liveness succeeds.
@test unsafe fn testSpillStorageExhaustion() throws (testing::TestError) {
    let mut instructions = [il::Instr::Ret { val: il::Val::Reg(il::Reg { n: 66 }) }];
    let blocks = [block("entry", &mut instructions[..])];
    let function = il::Fn { name: "spillStorage", params: &[], returnType: il::Type::W64,
        isExtern: false, isLeaf: true, blocks: &blocks[..] };
    static DATA: [u8; 128] = [0; 128];
    let mut arena = alloc::new(&mut DATA[..]);
    let mut failed = false;
    use arena as analysis in {
        let live = try! super::analyze(&function, &analysis);
        try spill::analyze(&function, &live, 0, 0, 8, &analysis) catch {
            set failed = true;
        };
    }
    assert failed;
}

/// Switch successors merge distinct words and tolerate repeated destinations.
@test unsafe fn testSwitchSuccessorLiveness() throws (testing::TestError) {
    for count in [0 as u32, 1, 3] {
        let mut cases = [
            il::SwitchCase { value: 0, target: 1, args: &mut [] },

lib/std/lang/gen/regalloc/spill.rad +22 -6

    live: &liveness::LiveInfo 'scratch,
    numRegs: u32,
    numCalleeSaved: u32,
    slotSize: u32,
    storage: &Session 'scratch
) -> SpillInfo 'scratch throws (alloc::AllocError) {
    return try analyzeBlocks(func.blocks, live, numRegs, numCalleeSaved, slotSize, storage);
}

/// Allocate spill storage and analyze pressure over a borrowed block table.
fn analyzeBlocks 'scratch (
    blocks: &[il::Block],
    live: &liveness::LiveInfo 'scratch,
    numRegs: u32,
    numCalleeSaved: u32,
    slotSize: u32,
    storage: &Session 'scratch,
) -> SpillInfo 'scratch throws (alloc::AllocError) {
    let maxReg = live.maxReg;
    if maxReg == 0 {
        let calleeClass = try bitset::allocate(storage, 0);
        return SpillInfo 'scratch {

    // Allocate spill slots array.
    let slots = try storage.fill(-1 as i32, maxReg);
    // Allocate cost array.
    let costs = try storage.fill(SpillCost { defs: 0, uses: 0 }, maxReg);
    // Phase 1: Calculate spill costs.
    for b in 0..func.blocks.len {
        let block = &func.blocks[b];
        fillCosts(block.params, block.instrs, block.loopDepth, costs);
    for b in 0..blocks.len {
        let block = &blocks[b];
        unsafe {
            fillCosts(block.params, block.instrs, block.loopDepth, costs);
        }
    }

    // Phase 2: Find values that exceed register pressure.
    let spilled = try bitset::allocate(storage, maxReg);
    let calleeClass = try bitset::allocate(storage, maxReg);
    let scratch = try bitset::allocate(storage, maxReg);

    for b in 0..func.blocks.len {
        let block = &func.blocks[b];
    for b in 0..blocks.len {
        let block = &blocks[b];

        // Start with live-out set.
        bitset::copy(scratch, liveness::liveOutRow(live, b));

        try limitBlockPressure(block.instrs, scratch, spilled, costs, calleeClass, numRegs, numCalleeSaved);
        unsafe {
            try limitBlockPressure(block.instrs, scratch, spilled, costs, calleeClass, numRegs, numCalleeSaved);
        }
    }

    let frameSize = try finishSpills(slots, spilled, calleeClass, numCalleeSaved, slotSize);
    return SpillInfo 'scratch { slots: &slots[..], frameSize, calleeClass: &calleeClass[..], maxReg };
}

80	80		live: &liveness::LiveInfo 'scratch,
81	81		numRegs: u32,
82	82		numCalleeSaved: u32,
83	83		slotSize: u32,
84	84		storage: &Session 'scratch
	85	+	) -> SpillInfo 'scratch throws (alloc::AllocError) {
	86	+	return try analyzeBlocks(func.blocks, live, numRegs, numCalleeSaved, slotSize, storage);
	87	+	}
	88	+
	89	+	/// Allocate spill storage and analyze pressure over a borrowed block table.
	90	+	fn analyzeBlocks 'scratch (
	91	+	blocks: &[il::Block],
	92	+	live: &liveness::LiveInfo 'scratch,
	93	+	numRegs: u32,
	94	+	numCalleeSaved: u32,
	95	+	slotSize: u32,
	96	+	storage: &Session 'scratch,
85	97		) -> SpillInfo 'scratch throws (alloc::AllocError) {
86	98		let maxReg = live.maxReg;
87	99		if maxReg == 0 {
88	100		let calleeClass = try bitset::allocate(storage, 0);
89	101		return SpillInfo 'scratch {

96	108		// Allocate spill slots array.
97	109		let slots = try storage.fill(-1 as i32, maxReg);
98	110		// Allocate cost array.
99	111		let costs = try storage.fill(SpillCost { defs: 0, uses: 0 }, maxReg);
100	112		// Phase 1: Calculate spill costs.
101		-	for b in 0..func.blocks.len {
102		-	let block = &func.blocks[b];
103		-	fillCosts(block.params, block.instrs, block.loopDepth, costs);
	113	+	for b in 0..blocks.len {
	114	+	let block = &blocks[b];
	115	+	unsafe {
	116	+	fillCosts(block.params, block.instrs, block.loopDepth, costs);
	117	+	}
104	118		}
105	119
106	120		// Phase 2: Find values that exceed register pressure.
107	121		let spilled = try bitset::allocate(storage, maxReg);
108	122		let calleeClass = try bitset::allocate(storage, maxReg);
109	123		let scratch = try bitset::allocate(storage, maxReg);
110	124
111		-	for b in 0..func.blocks.len {
112		-	let block = &func.blocks[b];
	125	+	for b in 0..blocks.len {
	126	+	let block = &blocks[b];
113	127
114	128		// Start with live-out set.
115	129		bitset::copy(scratch, liveness::liveOutRow(live, b));
116	130
117		-	try limitBlockPressure(block.instrs, scratch, spilled, costs, calleeClass, numRegs, numCalleeSaved);
	131	+	unsafe {
	132	+	try limitBlockPressure(block.instrs, scratch, spilled, costs, calleeClass, numRegs, numCalleeSaved);
	133	+	}
118	134		}
119	135
120	136		let frameSize = try finishSpills(slots, spilled, calleeClass, numCalleeSaved, slotSize);
121	137		return SpillInfo 'scratch { slots: &slots[..], frameSize, calleeClass: &calleeClass[..], maxReg };
122	138		}

27	27		assert live.blockCount == count;
28	28		assert live.maxReg == 0;
29	29		assert live.words == 0;
30	30		assert live.liveIn.len == 0 and live.liveOut.len == 0;
31	31		assert live.defs.len == 0 and live.uses.len == 0;
	32	+	let spills = try! spill::analyze(&function, &live, 0, 0, 8, &analysis);
	33	+	assert spills.maxReg == 0;
	34	+	assert spills.frameSize == 0;
	35	+	assert spills.slots.len == 0 and spills.calleeClass.len == 0;
32	36		}
33	37		}
34	38		}
35	39
36	40		/// Insufficient matrix storage reports an allocation error.

48	52		};
49	53		}
50	54		assert failed;
51	55		}
52	56
	57	+	/// Spill storage exhaustion reports an error after liveness succeeds.
	58	+	@test unsafe fn testSpillStorageExhaustion() throws (testing::TestError) {
	59	+	let mut instructions = [il::Instr::Ret { val: il::Val::Reg(il::Reg { n: 66 }) }];
	60	+	let blocks = [block("entry", &mut instructions[..])];
	61	+	let function = il::Fn { name: "spillStorage", params: &[], returnType: il::Type::W64,
	62	+	isExtern: false, isLeaf: true, blocks: &blocks[..] };
	63	+	static DATA: [u8; 128] = [0; 128];
	64	+	let mut arena = alloc::new(&mut DATA[..]);
	65	+	let mut failed = false;
	66	+	use arena as analysis in {
	67	+	let live = try! super::analyze(&function, &analysis);
	68	+	try spill::analyze(&function, &live, 0, 0, 8, &analysis) catch {
	69	+	set failed = true;
	70	+	};
	71	+	}
	72	+	assert failed;
	73	+	}
	74	+
53	75		/// Switch successors merge distinct words and tolerate repeated destinations.
54	76		@test unsafe fn testSwitchSuccessorLiveness() throws (testing::TestError) {
55	77		for count in [0 as u32, 1, 3] {
56	78		let mut cases = [
57	79		il::SwitchCase { value: 0, target: 1, args: &mut [] },