radiance · commit

compiler: Check loop-weighted spill cost traversal

bf50fe77d32bcb945f576242f85356a746e69ee3ef8088aa13b4ff62896e52c2

Alexis Sellier committed 6 days ago 1 parent a000c3ac

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

            assert info.slots[0] == 0;
        }
    }
}

/// Loop-weighted uses retain hot values and cap large loop depths.
@test unsafe fn testLoopWeightedSpills() throws (testing::TestError) {
    let first = il::Reg { n: 0 };
    let second = il::Reg { n: 33 };
    let temporary = il::Reg { n: 66 };
    let mut entry = [
        il::Instr::Copy { dst: first, val: il::Val::Imm(1) },
        il::Instr::Copy { dst: second, val: il::Val::Imm(2) },
        il::Instr::Jmp { target: 1, args: &mut [] },
    ];
    let mut body = [
        il::Instr::Copy { dst: temporary, val: il::Val::Reg(first) },
        il::Instr::Jmp { target: 2, args: &mut [] },
    ];
    let mut exit = [il::Instr::Ret { val: il::Val::Reg(second) }];
    for depth in [0 as u32, 1, 10, 11, 32, 0xffffffff] {
        let mut weighted = block("body", &mut body[..]);
        set weighted.loopDepth = depth;
        let blocks = [block("entry", &mut entry[..]), weighted, block("exit", &mut exit[..])];
        let function = il::Fn { name: "weighted", params: &[], returnType: il::Type::W64,
            isExtern: false, isLeaf: true, blocks: &blocks[..] };
        static DATA: [u8; 8192] = [0; 8192];
        let mut arena = alloc::new(&mut DATA[..]);
        use arena as analysis in {
            let live = try! super::analyze(&function, &analysis);
            let info = try! spill::analyze(&function, &live, 1, 0, 8, &analysis);
            assert spill::isSpilled(&info, first) == (depth == 0);
            assert spill::isSpilled(&info, second) == (depth > 0);
            assert not spill::isSpilled(&info, temporary);
            assert info.frameSize == 8;
        }
    }
}

/// Cross-call pressure excludes the result and spills equal-cost values in order.
@test unsafe fn testCrossCallPressure() throws (testing::TestError) {
    let first = il::Reg { n: 0 };
    let second = il::Reg { n: 33 };
    let result = il::Reg { n: 66 };

lib/std/lang/gen/regalloc/spill.rad +27 -24

    // 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.
    fillCosts(func, costs);
    for b in 0..func.blocks.len {
        let block = &func.blocks[b];
        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);

        set frameSize += slotSize as i32;
    }
    return frameSize;
}

/// Calculate spill costs for all registers, weighted by loop depth.
unsafe fn fillCosts(func: &il::Fn, costs: &mut [SpillCost]) {
    for b in 0..func.blocks.len {
        let block = &func.blocks[b];

        // Exponential weight for loop depth, capped to avoid overflow.
        let depth = MAX_LOOP_WEIGHT if block.loopDepth > MAX_LOOP_WEIGHT else block.loopDepth;
        let weight: u32 = 1 << depth;
/// Add one block's register spill costs, weighted by loop depth.
fn fillCosts(params: &[il::Param], instructions: &[il::Instr], loopDepth: u32, costs: &mut [SpillCost]) {
    // Exponential weight for loop depth, capped to avoid overflow.
    let depth = MAX_LOOP_WEIGHT if loopDepth > MAX_LOOP_WEIGHT else loopDepth;
    let weight: u32 = 1 << depth;

        // Count block parameter definitions.
        for p in block.params {
            if p.value.n < costs.len {
                set costs[p.value.n].defs = costs[p.value.n].defs + weight;
            }
    // Count block parameter definitions.
    for p in params {
        if p.value.n < costs.len {
            set costs[p.value.n].defs = costs[p.value.n].defs + weight;
        }
        // Count instruction defs and uses.
        for instr in block.instrs {
    }
    // Count instruction defs and uses.
    for i in 0..instructions.len {
        let instr = &instructions[i];

            // Count definition.
            if let dst = il::instrDst(instr) {
                if dst.n < costs.len {
                    set costs[dst.n].defs = costs[dst.n].defs + weight;
                }
        // Count definition.
        if let dst = il::instrDst(*instr) {
            if dst.n < costs.len {
                set costs[dst.n].defs = costs[dst.n].defs + weight;
            }
            // Count uses.
            let mut registers = il::registers(&instr);
            while let reg = il::nextReg(&mut registers, &instr) {
        }
        // Count uses.
        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) {
                countRegUse(reg, &mut costs[..], weight);
            }
        }
    }
}

186	186		assert info.slots[0] == 0;
187	187		}
188	188		}
189	189		}
190	190
	191	+	/// Loop-weighted uses retain hot values and cap large loop depths.
	192	+	@test unsafe fn testLoopWeightedSpills() throws (testing::TestError) {
	193	+	let first = il::Reg { n: 0 };
	194	+	let second = il::Reg { n: 33 };
	195	+	let temporary = il::Reg { n: 66 };
	196	+	let mut entry = [
	197	+	il::Instr::Copy { dst: first, val: il::Val::Imm(1) },
	198	+	il::Instr::Copy { dst: second, val: il::Val::Imm(2) },
	199	+	il::Instr::Jmp { target: 1, args: &mut [] },
	200	+	];
	201	+	let mut body = [
	202	+	il::Instr::Copy { dst: temporary, val: il::Val::Reg(first) },
	203	+	il::Instr::Jmp { target: 2, args: &mut [] },
	204	+	];
	205	+	let mut exit = [il::Instr::Ret { val: il::Val::Reg(second) }];
	206	+	for depth in [0 as u32, 1, 10, 11, 32, 0xffffffff] {
	207	+	let mut weighted = block("body", &mut body[..]);
	208	+	set weighted.loopDepth = depth;
	209	+	let blocks = [block("entry", &mut entry[..]), weighted, block("exit", &mut exit[..])];
	210	+	let function = il::Fn { name: "weighted", params: &[], returnType: il::Type::W64,
	211	+	isExtern: false, isLeaf: true, blocks: &blocks[..] };
	212	+	static DATA: [u8; 8192] = [0; 8192];
	213	+	let mut arena = alloc::new(&mut DATA[..]);
	214	+	use arena as analysis in {
	215	+	let live = try! super::analyze(&function, &analysis);
	216	+	let info = try! spill::analyze(&function, &live, 1, 0, 8, &analysis);
	217	+	assert spill::isSpilled(&info, first) == (depth == 0);
	218	+	assert spill::isSpilled(&info, second) == (depth > 0);
	219	+	assert not spill::isSpilled(&info, temporary);
	220	+	assert info.frameSize == 8;
	221	+	}
	222	+	}
	223	+	}
	224	+
191	225		/// Cross-call pressure excludes the result and spills equal-cost values in order.
192	226		@test unsafe fn testCrossCallPressure() throws (testing::TestError) {
193	227		let first = il::Reg { n: 0 };
194	228		let second = il::Reg { n: 33 };
195	229		let result = il::Reg { n: 66 };

96	96		// Allocate spill slots array.
97	97		let slots = try storage.fill(-1 as i32, maxReg);
98	98		// Allocate cost array.
99	99		let costs = try storage.fill(SpillCost { defs: 0, uses: 0 }, maxReg);
100	100		// Phase 1: Calculate spill costs.
101		-	fillCosts(func, costs);
	101	+	for b in 0..func.blocks.len {
	102	+	let block = &func.blocks[b];
	103	+	fillCosts(block.params, block.instrs, block.loopDepth, costs);
	104	+	}
102	105
103	106		// Phase 2: Find values that exceed register pressure.
104	107		let spilled = try bitset::allocate(storage, maxReg);
105	108		let calleeClass = try bitset::allocate(storage, maxReg);
106	109		let scratch = try bitset::allocate(storage, maxReg);

199	202		set frameSize += slotSize as i32;
200	203		}
201	204		return frameSize;
202	205		}
203	206
204		-	/// Calculate spill costs for all registers, weighted by loop depth.
205		-	unsafe fn fillCosts(func: &il::Fn, costs: &mut [SpillCost]) {
206		-	for b in 0..func.blocks.len {
207		-	let block = &func.blocks[b];
208		-
209		-	// Exponential weight for loop depth, capped to avoid overflow.
210		-	let depth = MAX_LOOP_WEIGHT if block.loopDepth > MAX_LOOP_WEIGHT else block.loopDepth;
211		-	let weight: u32 = 1 << depth;
	207	+	/// Add one block's register spill costs, weighted by loop depth.
	208	+	fn fillCosts(params: &[il::Param], instructions: &[il::Instr], loopDepth: u32, costs: &mut [SpillCost]) {
	209	+	// Exponential weight for loop depth, capped to avoid overflow.
	210	+	let depth = MAX_LOOP_WEIGHT if loopDepth > MAX_LOOP_WEIGHT else loopDepth;
	211	+	let weight: u32 = 1 << depth;
212	212
213		-	// Count block parameter definitions.
214		-	for p in block.params {
215		-	if p.value.n < costs.len {
216		-	set costs[p.value.n].defs = costs[p.value.n].defs + weight;
217		-	}
	213	+	// Count block parameter definitions.
	214	+	for p in params {
	215	+	if p.value.n < costs.len {
	216	+	set costs[p.value.n].defs = costs[p.value.n].defs + weight;
218	217		}
219		-	// Count instruction defs and uses.
220		-	for instr in block.instrs {
	218	+	}
	219	+	// Count instruction defs and uses.
	220	+	for i in 0..instructions.len {
	221	+	let instr = &instructions[i];
221	222
222		-	// Count definition.
223		-	if let dst = il::instrDst(instr) {
224		-	if dst.n < costs.len {
225		-	set costs[dst.n].defs = costs[dst.n].defs + weight;
226		-	}
	223	+	// Count definition.
	224	+	if let dst = il::instrDst(*instr) {
	225	+	if dst.n < costs.len {
	226	+	set costs[dst.n].defs = costs[dst.n].defs + weight;
227	227		}
228		-	// Count uses.
229		-	let mut registers = il::registers(&instr);
230		-	while let reg = il::nextReg(&mut registers, &instr) {
	228	+	}
	229	+	// Count uses.
	230	+	let mut registers = il::registers(instr);
	231	+	// Argument groups contain raw views into the function's IL storage.
	232	+	unsafe {
	233	+	while let reg = il::nextReg(&mut registers, instr) {
231	234		countRegUse(reg, &mut costs[..], weight);
232	235		}
233	236		}
234	237		}
235	238		}