radiance · commit

compiler: Check register extent table traversal

891b61aee05c8e01cc48bdc1b0f28014b852564b7db40695b4c60c582658b928

Alexis Sellier committed 6 days ago 1 parent bf50fe77

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

        return LiveInfo 'scratch { liveIn: frozen, liveOut: frozen, defs: frozen, uses: frozen, words: 0, blockCount: 0, maxReg: 0 };
    }

    // Find max register number.
    let mut maxReg: u32 = 0;
    for p in func.params {
        try updateMaxReg(p.value, &mut maxReg);
    }
    try updateExtent(func.params, &[], &mut maxReg);
    for b in 0..blockCount {
        let block = &func.blocks[b];
        for p in block.params {
            try updateMaxReg(p.value, &mut maxReg);
        }
        for instr in block.instrs {
            let mut registers = il::registers(&instr);
            while let reg = il::nextReg(&mut registers, &instr) {
                try updateMaxReg(reg, &mut maxReg);
            }
            if let dst = il::instrDst(instr) {
                try updateMaxReg(dst, &mut maxReg);
            }
        }
        try updateExtent(block.params, block.instrs, &mut maxReg);
    }
    // Allocate one contiguous word matrix for each set class.
    let words = bitset::wordsFor(maxReg);
    let count64 = blockCount as u64 * words as u64;
    if count64 > 0xFFFFFFFF {

    if not bitset::contains(defs, reg.n) {
        bitset::put(uses, reg.n);
    }
}

/// Include all parameter, source, and destination registers in the entry count.
fn updateExtent(params: &[il::Param], instructions: &[il::Instr], max: &mut u32) throws (alloc::AllocError) {
    for p in params {
        try updateMaxReg(p.value, max);
    }
    for i in 0..instructions.len {
        let instr = &instructions[i];
        let mut registers = il::registers(instr);
        // Argument groups contain raw views into the function's IL storage.
        unsafe {
            while let reg = il::nextReg(&mut registers, instr) {
                try updateMaxReg(reg, max);
            }
        }
        if let dst = il::instrDst(*instr) {
            try updateMaxReg(dst, max);
        }
    }
}

/// Retain the larger of the current entry count and the register index plus one.
fn updateMaxReg(reg: il::Reg, max: &mut u32) throws (alloc::AllocError) {
    if reg.n > MAX_REGISTER_INDEX {
        throw alloc::AllocError::OutOfMemory;
    }

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

            assert not bitset::contains(super::liveInRow(&live, 0), destination.n);
        }
    }
}

/// Nested switch arguments contribute to the extent and reject index overflow.
@test unsafe fn testSwitchArgumentExtent() throws (testing::TestError) {
    for index in [8192 as u32, 16384, 0xffffffff] {
        for inDefault in [false, true] {
            let source = il::Reg { n: index };
            let mut caseArgs = [il::Val::Imm(0)];
            let mut defaultArgs = [il::Val::Imm(0)];
            if inDefault {
                set defaultArgs[0] = il::Val::Reg(source);
            } else {
                set caseArgs[0] = il::Val::Reg(source);
            }
            let mut cases = [il::SwitchCase { value: 1, target: 1, args: &mut caseArgs[..] }];
            let mut entry = [il::Instr::Switch { val: il::Val::Imm(0),
                defaultTarget: 1, defaultArgs: &mut defaultArgs[..], cases: &mut cases[..] }];
            let params = [il::Param { value: il::Reg { n: 0 }, type: il::Type::W64 }];
            let mut exit = [il::Instr::Ret { val: il::Val::Reg(il::Reg { n: 0 }) }];
            let blocks = [block("entry", &mut entry[..]), il::Block { label: "exit",
                params: &params[..], instrs: &mut exit[..], locs: &[], preds: &[], loopDepth: 0 }];
            let function = il::Fn { name: "argument", params: &[], returnType: il::Type::W64,
                isExtern: false, isLeaf: true, blocks: &blocks[..] };
            static DATA: [u8; 32768] = [0; 32768];
            let mut arena = alloc::new(&mut DATA[..]);
            use arena as analysis in {
                let live = try super::analyze(&function, &analysis) catch {
                    assert index == 0xffffffff;
                    continue;
                };
                assert index <> 0xffffffff;
                assert live.maxReg == index + 1;
                assert bitset::contains(super::liveInRow(&live, 0), index);
            }
        }
    }
}

/// An unrepresentable register extent fails before any bitset access.
@test unsafe fn testRegisterExtentOverflow() throws (testing::TestError) {
    for instruction in [
        il::Instr::Ret { val: il::Val::Reg(il::Reg { n: 0xffffffff }) },
        il::Instr::Copy { dst: il::Reg { n: 0xffffffff }, val: il::Val::Imm(0) },

165	152		if not bitset::contains(defs, reg.n) {
166	153		bitset::put(uses, reg.n);
167	154		}
168	155		}
169	156
	157	+	/// Include all parameter, source, and destination registers in the entry count.
	158	+	fn updateExtent(params: &[il::Param], instructions: &[il::Instr], max: &mut u32) throws (alloc::AllocError) {
	159	+	for p in params {
	160	+	try updateMaxReg(p.value, max);
	161	+	}
	162	+	for i in 0..instructions.len {
	163	+	let instr = &instructions[i];
	164	+	let mut registers = il::registers(instr);
	165	+	// Argument groups contain raw views into the function's IL storage.
	166	+	unsafe {
	167	+	while let reg = il::nextReg(&mut registers, instr) {
	168	+	try updateMaxReg(reg, max);
	169	+	}
	170	+	}
	171	+	if let dst = il::instrDst(*instr) {
	172	+	try updateMaxReg(dst, max);
	173	+	}
	174	+	}
	175	+	}
	176	+
170	177		/// Retain the larger of the current entry count and the register index plus one.
171	178		fn updateMaxReg(reg: il::Reg, max: &mut u32) throws (alloc::AllocError) {
172	179		if reg.n > MAX_REGISTER_INDEX {
173	180		throw alloc::AllocError::OutOfMemory;
174	181		}

95	95		assert not bitset::contains(super::liveInRow(&live, 0), destination.n);
96	96		}
97	97		}
98	98		}
99	99
	100	+	/// Nested switch arguments contribute to the extent and reject index overflow.
	101	+	@test unsafe fn testSwitchArgumentExtent() throws (testing::TestError) {
	102	+	for index in [8192 as u32, 16384, 0xffffffff] {
	103	+	for inDefault in [false, true] {
	104	+	let source = il::Reg { n: index };
	105	+	let mut caseArgs = [il::Val::Imm(0)];
	106	+	let mut defaultArgs = [il::Val::Imm(0)];
	107	+	if inDefault {
	108	+	set defaultArgs[0] = il::Val::Reg(source);
	109	+	} else {
	110	+	set caseArgs[0] = il::Val::Reg(source);
	111	+	}
	112	+	let mut cases = [il::SwitchCase { value: 1, target: 1, args: &mut caseArgs[..] }];
	113	+	let mut entry = [il::Instr::Switch { val: il::Val::Imm(0),
	114	+	defaultTarget: 1, defaultArgs: &mut defaultArgs[..], cases: &mut cases[..] }];
	115	+	let params = [il::Param { value: il::Reg { n: 0 }, type: il::Type::W64 }];
	116	+	let mut exit = [il::Instr::Ret { val: il::Val::Reg(il::Reg { n: 0 }) }];
	117	+	let blocks = [block("entry", &mut entry[..]), il::Block { label: "exit",
	118	+	params: &params[..], instrs: &mut exit[..], locs: &[], preds: &[], loopDepth: 0 }];
	119	+	let function = il::Fn { name: "argument", params: &[], returnType: il::Type::W64,
	120	+	isExtern: false, isLeaf: true, blocks: &blocks[..] };
	121	+	static DATA: [u8; 32768] = [0; 32768];
	122	+	let mut arena = alloc::new(&mut DATA[..]);
	123	+	use arena as analysis in {
	124	+	let live = try super::analyze(&function, &analysis) catch {
	125	+	assert index == 0xffffffff;
	126	+	continue;
	127	+	};
	128	+	assert index <> 0xffffffff;
	129	+	assert live.maxReg == index + 1;
	130	+	assert bitset::contains(super::liveInRow(&live, 0), index);
	131	+	}
	132	+	}
	133	+	}
	134	+	}
	135	+
100	136		/// An unrepresentable register extent fails before any bitset access.
101	137		@test unsafe fn testRegisterExtentOverflow() throws (testing::TestError) {
102	138		for instruction in [
103	139		il::Instr::Ret { val: il::Val::Reg(il::Reg { n: 0xffffffff }) },
104	140		il::Instr::Copy { dst: il::Reg { n: 0xffffffff }, val: il::Val::Imm(0) },

60	60		return LiveInfo 'scratch { liveIn: frozen, liveOut: frozen, defs: frozen, uses: frozen, words: 0, blockCount: 0, maxReg: 0 };
61	61		}
62	62
63	63		// Find max register number.
64	64		let mut maxReg: u32 = 0;
65		-	for p in func.params {
66		-	try updateMaxReg(p.value, &mut maxReg);
67		-	}
	65	+	try updateExtent(func.params, &[], &mut maxReg);
68	66		for b in 0..blockCount {
69	67		let block = &func.blocks[b];
70		-	for p in block.params {
71		-	try updateMaxReg(p.value, &mut maxReg);
72		-	}
73		-	for instr in block.instrs {
74		-	let mut registers = il::registers(&instr);
75		-	while let reg = il::nextReg(&mut registers, &instr) {
76		-	try updateMaxReg(reg, &mut maxReg);
77		-	}
78		-	if let dst = il::instrDst(instr) {
79		-	try updateMaxReg(dst, &mut maxReg);
80		-	}
81		-	}
	68	+	try updateExtent(block.params, block.instrs, &mut maxReg);
82	69		}
83	70		// Allocate one contiguous word matrix for each set class.
84	71		let words = bitset::wordsFor(maxReg);
85	72		let count64 = blockCount as u64 * words as u64;
86	73		if count64 > 0xFFFFFFFF {