radiance · commit

compiler: Select instructions with published parameter tables

b6aefd8ac36e03cdb6ef2726638db096c186f04cda519e4e249b486653dec125

Alexis Sellier committed 5 days ago 1 parent a359ca0d

lib/std/arch/rv64.rad +1 -1

    config: &regalloc::TargetConfig,
    storage: &Session 'scratch
) throws (alloc::AllocError) {
    let view = try il::published::publish(func, storage);
    let ralloc = try regalloc::allocate(&view, config, storage);
    isel::selectFn(&mut generator.e, &ralloc, func);
    isel::selectFn(&mut generator.e, &ralloc, func, &view);
}

/// Record an alternate name for the next function emitted.
export fn recordFunctionAlias(generator: &mut Generator, name: *[u8]) {
    let codeLen = generator.e.codeLen;

lib/std/arch/rv64/bounds.rad +63 -0

use std::lang::gen::bitset;
use std::lang::gen::regalloc;
use std::collections::dict;
use super::emit;
use super::encode;
use super::isel;

/// Branch forms whose taken edge supplies block parameters.
union ParameterEdge: Copy { Jump, Then, Else, Case, Default }

/// Selection uses published parameter definitions after source tables change.
@test unsafe fn publishedParameters() throws (testing::TestError) {
    for edge in [ParameterEdge::Jump, ParameterEdge::Then, ParameterEdge::Else,
        ParameterEdge::Case, ParameterEdge::Default]
    {
        let mut params = [il::Param { value: il::Reg { n: 0 }, type: il::Type::W64 }];
        let mut targetParams = [il::Param { value: il::Reg { n: 1 }, type: il::Type::W64 }];
        let mut args = [il::Val::Reg(il::Reg { n: 0 })];
        let mut cases = [il::SwitchCase { value: 1, target: 1, args: &mut args[..] }];
        let mut entry = [il::Instr::Jmp { target: 1, args: &mut args[..] }];
        match edge {
            case ParameterEdge::Then => set entry[0] = il::Instr::Br {
                op: il::CmpOp::Eq, typ: il::Type::W64, a: il::Val::Imm(1), b: il::Val::Imm(1),
                thenTarget: 1, thenArgs: &mut args[..], elseTarget: 2, elseArgs: &mut [],
            },
            case ParameterEdge::Else => set entry[0] = il::Instr::Br {
                op: il::CmpOp::Eq, typ: il::Type::W64, a: il::Val::Imm(1), b: il::Val::Imm(1),
                thenTarget: 2, thenArgs: &mut [], elseTarget: 1, elseArgs: &mut args[..],
            },
            case ParameterEdge::Case => set entry[0] = il::Instr::Switch {
                val: il::Val::Imm(1), defaultTarget: 2, defaultArgs: &mut [], cases: &mut cases[..],
            },
            case ParameterEdge::Default => set entry[0] = il::Instr::Switch {
                val: il::Val::Imm(0), defaultTarget: 1, defaultArgs: &mut args[..], cases: &mut [],
            },
            else => {},
        }
        let mut target = [il::Instr::Ret { val: il::Val::Reg(il::Reg { n: 1 }) }];
        let mut other = [il::Instr::Ret { val: il::Val::Imm(0) }];
        let blocks = [
            il::Block { label: "entry", params: &[], instrs: &mut entry[..], locs: &[], preds: &[], loopDepth: 0 },
            il::Block { label: "target", params: &targetParams[..], instrs: &mut target[..], locs: &[], preds: &[], loopDepth: 0 },
            il::Block { label: "other", params: &[], instrs: &mut other[..], locs: &[], preds: &[], loopDepth: 0 },
        ];
        let func = il::Fn { name: "p::parameters", params: &params[..], returnType: il::Type::W64,
            isExtern: false, isLeaf: true, blocks: &blocks[..] };
        let mut arena = alloc::new(&mut SCRATCH[..]);
        let mut code = alloc::new(&mut MEMORY[..]);
        let mut gen = generator(&mut code);
        use arena as storage in {
            let view = try! il::published::publish(&func, &storage);
            let config = super::targetConfig();
            let allocation = try! regalloc::allocate(&view, &config, &storage);
            isel::selectFn(&mut gen.e, &allocation, &func, &view);
            assert gen.e.error == nil;
            let expected = try! storage.copy(&gen.e.code[..gen.e.codeLen]);
            set params[0].value.n = 0xffffffff;
            set targetParams[0].value.n = 0xffffffff;
            alloc::reset(&mut code);
            set gen = generator(&mut code);
            isel::selectFn(&mut gen.e, &allocation, &func, &view);
            assert gen.e.error == nil and gen.e.codeLen == expected.len;
            for word, i in expected {
                assert gen.e.code[i] == word;
            }
        }
    }
}

/// Reusable emitter allocation storage.
static MEMORY: [u8; 16777216] = [0; 16777216];
/// Function and liveness test storage.
static SCRATCH: [u8; 65536] = [0; 65536];

lib/std/arch/rv64/isel.rad +19 -17

        }
    }
    return ReserveInfo { size: offset, isDynamic };
}

/// Select instructions for a function.
/// Select instructions with published parameter definitions and assignments.
/// Published inputs and assignments must describe the selected instruction tables.
export unsafe fn selectFn 'scratch (
    e: &mut emit::Emitter,
    ralloc: &regalloc::AllocResult 'scratch,
    func: &il::Fn
    func: &il::Fn,
    view: &il::published::Function 'scratch
) {
    if e.error <> nil {
        return;
    }
    // Reset block offsets for this function.

    let isLeaf = func.isLeaf;
    // Compute frame layout from spill slots, reserve slots, and used callee-saved registers.
    let frame = emit::computeFrame(
        ralloc.spill.frameSize + reserveInfo.size,
        ralloc.usedCalleeSaved,
        func.blocks.len,
        view.blocks.len,
        isLeaf,
        reserveInfo.isDynamic
    );
    // Synthetic block indices start after real blocks and the epilogue block.
    let resultRef: 'selection = &*ralloc, emitterRef = &mut *e where 'scratch: 'selection in {
        let mut s = Selector 'scratch 'selection {
            e: emitterRef,
            ralloc: resultRef,
            frameSize: frame.totalSize,
            reserveOffset: 0, pendingSpill: nil,
            nextSynthBlock: func.blocks.len + 1,
            nextSynthBlock: view.blocks.len + 1,
            isDynamic: frame.isDynamic,
        };
        // Record function name for printing.
        emit::recordFunc(s.e, func.name);
        // Record function code offset for call patching.


        // Move function params from arg registers to assigned registers.
        // Cross-call params may have been assigned to callee-saved registers
        // instead of their natural arg registers. Spilled params are stored
        // directly to their spill slots.
        for funcParam, i in func.params {
        for funcParam, i in view.params {
            if i < super::ARG_REGS.len {
                let param = funcParam.value;
                let argReg = super::ARG_REGS[i];

                if let slot = regalloc::spill::spillSlot(&ralloc.spill, param) {

                }
            }
        }

        // Emit each block.
        for i in 0..func.blocks.len {
        for i in 0..view.blocks.len {
            if s.e.error <> nil {
                return;
            }
            selectBlock(&mut s, i, &func.blocks[i], &frame, func);
            selectBlock(&mut s, i, &func.blocks[i], &frame, view);
        }
        // Emit epilogue.
        emit::emitEpilogue(s.e, &frame);
        // Patch local branches now that all blocks are emitted.
        emit::patchLocalBranches(s.e);
    }
}

/// Select instructions for a block.
unsafe fn selectBlock 'scratch 'selection (s: &mut Selector 'scratch 'selection, blockIdx: u32, block: &il::Block, frame: &emit::Frame, func: &il::Fn) where 'scratch: 'selection {
unsafe fn selectBlock 'scratch 'selection (s: &mut Selector 'scratch 'selection, blockIdx: u32, block: &il::Block, frame: &emit::Frame, view: &il::published::Function 'scratch) where 'scratch: 'selection {
    // Record block address for branch patching.
    emit::recordBlock(s.e, blockIdx);

    // Block parameters are handled at jump sites (in `Jmp`/`Br`).
    // By the time we enter the block, the arguments have already been

        // Record debug location before emitting machine instructions.
        if hasLocs {
            emit::recordSrcLoc(s.e, block.locs[i]);
        }
        set s.pendingSpill = nil;
        selectInstr(s, blockIdx, &instr, frame, func);
        selectInstr(s, blockIdx, &instr, frame, view);

        // Flush the pending spill store, if any.
        if let p = s.pendingSpill {
            if let slot = regalloc::spill::spillSlot(&s.ralloc.spill, p.ssa) {
                emit::emitSd(s.e, p.rd, spillBase(s), spillOffset(s, slot));

        }
    }
}

/// Select instructions for a single IL instruction.
unsafe fn selectInstr 'scratch 'selection (s: &mut Selector 'scratch 'selection, blockIdx: u32, instr: &il::Instr, frame: &emit::Frame, func: &il::Fn) where 'scratch: 'selection {
unsafe fn selectInstr 'scratch 'selection (s: &mut Selector 'scratch 'selection, blockIdx: u32, instr: &il::Instr, frame: &emit::Frame, view: &il::published::Function 'scratch) where 'scratch: 'selection {
    match *instr {
        case il::Instr::Jmp { target, args } => {
            selectJump(s, blockIdx, target, func.blocks[target].params, args);
            selectJump(s, blockIdx, target, view.blocks[target].params, args);
        },
        case il::Instr::Br { thenTarget, thenArgs, elseTarget, elseArgs, .. } => {
            let params: *unsafe [il::Param] = func.blocks[thenTarget].params
            let params: &'scratch [il::Param] = view.blocks[thenTarget].params
                if thenArgs.len > 0 and elseArgs.len == 0
                else func.blocks[elseTarget].params if elseArgs.len > 0 and thenArgs.len == 0
                else &[];
                else view.blocks[elseTarget].params if elseArgs.len > 0 and thenArgs.len == 0
                else &view.params[..0];
            selectBranch(s, blockIdx, instr, params, thenArgs, elseArgs);
        },
        case il::Instr::Switch { val, defaultTarget, defaultArgs, cases } => {
            let rs1 = resolveVal(s, super::SCRATCH1, val);
            for c in cases {
                let params: *unsafe [il::Param] = func.blocks[c.target].params
                    if c.args.len > 0 else &[];
                let params: &'scratch [il::Param] = view.blocks[c.target].params
                    if c.args.len > 0 else &view.params[..0];
                selectSwitchCase(s, rs1, c.value, c.target, params, c.args);
            }
            // Fall through to default.
            emitBlockArgs(s, func.blocks[defaultTarget].params, defaultArgs);
            emitBlockArgs(s, view.blocks[defaultTarget].params, defaultArgs);
            emit::recordBranch(s.e, defaultTarget, emit::BranchKind::Jump);
        },
        case il::Instr::Call { dst, func, args, .. } => selectCall(s, &func, args, dst),
        else => selectFixedInstr(s, blockIdx, instr, frame),
    }

311	311		config: &regalloc::TargetConfig,
312	312		storage: &Session 'scratch
313	313		) throws (alloc::AllocError) {
314	314		let view = try il::published::publish(func, storage);
315	315		let ralloc = try regalloc::allocate(&view, config, storage);
316		-	isel::selectFn(&mut generator.e, &ralloc, func);
	316	+	isel::selectFn(&mut generator.e, &ralloc, func, &view);
317	317		}
318	318
319	319		/// Record an alternate name for the next function emitted.
320	320		export fn recordFunctionAlias(generator: &mut Generator, name: *[u8]) {
321	321		let codeLen = generator.e.codeLen;

297	297		}
298	298		}
299	299		return ReserveInfo { size: offset, isDynamic };
300	300		}
301	301
302		-	/// Select instructions for a function.
	302	+	/// Select instructions with published parameter definitions and assignments.
	303	+	/// Published inputs and assignments must describe the selected instruction tables.
303	304		export unsafe fn selectFn 'scratch (
304	305		e: &mut emit::Emitter,
305	306		ralloc: &regalloc::AllocResult 'scratch,
306		-	func: &il::Fn
	307	+	func: &il::Fn,
	308	+	view: &il::published::Function 'scratch
307	309		) {
308	310		if e.error <> nil {
309	311		return;
310	312		}
311	313		// Reset block offsets for this function.

325	327		let isLeaf = func.isLeaf;
326	328		// Compute frame layout from spill slots, reserve slots, and used callee-saved registers.
327	329		let frame = emit::computeFrame(
328	330		ralloc.spill.frameSize + reserveInfo.size,
329	331		ralloc.usedCalleeSaved,
330		-	func.blocks.len,
	332	+	view.blocks.len,
331	333		isLeaf,
332	334		reserveInfo.isDynamic
333	335		);
334	336		// Synthetic block indices start after real blocks and the epilogue block.
335	337		let resultRef: 'selection = &ralloc, emitterRef = &mut e where 'scratch: 'selection in {
336	338		let mut s = Selector 'scratch 'selection {
337	339		e: emitterRef,
338	340		ralloc: resultRef,
339	341		frameSize: frame.totalSize,
340	342		reserveOffset: 0, pendingSpill: nil,
341		-	nextSynthBlock: func.blocks.len + 1,
	343	+	nextSynthBlock: view.blocks.len + 1,
342	344		isDynamic: frame.isDynamic,
343	345		};
344	346		// Record function name for printing.
345	347		emit::recordFunc(s.e, func.name);
346	348		// Record function code offset for call patching.

350	352
351	353		// Move function params from arg registers to assigned registers.
352	354		// Cross-call params may have been assigned to callee-saved registers
353	355		// instead of their natural arg registers. Spilled params are stored
354	356		// directly to their spill slots.
355		-	for funcParam, i in func.params {
	357	+	for funcParam, i in view.params {
356	358		if i < super::ARG_REGS.len {
357	359		let param = funcParam.value;
358	360		let argReg = super::ARG_REGS[i];
359	361
360	362		if let slot = regalloc::spill::spillSlot(&ralloc.spill, param) {

365	367		}
366	368		}
367	369		}
368	370
369	371		// Emit each block.
370		-	for i in 0..func.blocks.len {
	372	+	for i in 0..view.blocks.len {
371	373		if s.e.error <> nil {
372	374		return;
373	375		}
374		-	selectBlock(&mut s, i, &func.blocks[i], &frame, func);
	376	+	selectBlock(&mut s, i, &func.blocks[i], &frame, view);
375	377		}
376	378		// Emit epilogue.
377	379		emit::emitEpilogue(s.e, &frame);
378	380		// Patch local branches now that all blocks are emitted.
379	381		emit::patchLocalBranches(s.e);
380	382		}
381	383		}
382	384
383	385		/// Select instructions for a block.
384		-	unsafe fn selectBlock 'scratch 'selection (s: &mut Selector 'scratch 'selection, blockIdx: u32, block: &il::Block, frame: &emit::Frame, func: &il::Fn) where 'scratch: 'selection {
	386	+	unsafe fn selectBlock 'scratch 'selection (s: &mut Selector 'scratch 'selection, blockIdx: u32, block: &il::Block, frame: &emit::Frame, view: &il::published::Function 'scratch) where 'scratch: 'selection {
385	387		// Record block address for branch patching.
386	388		emit::recordBlock(s.e, blockIdx);
387	389
388	390		// Block parameters are handled at jump sites (in `Jmp`/`Br`).
389	391		// By the time we enter the block, the arguments have already been

9	9		use std::lang::gen::bitset;
10	10		use std::lang::gen::regalloc;
11	11		use std::collections::dict;
12	12		use super::emit;
13	13		use super::encode;
	14	+	use super::isel;
	15	+
	16	+	/// Branch forms whose taken edge supplies block parameters.
	17	+	union ParameterEdge: Copy { Jump, Then, Else, Case, Default }
	18	+
	19	+	/// Selection uses published parameter definitions after source tables change.
	20	+	@test unsafe fn publishedParameters() throws (testing::TestError) {
	21	+	for edge in [ParameterEdge::Jump, ParameterEdge::Then, ParameterEdge::Else,
	22	+	ParameterEdge::Case, ParameterEdge::Default]
	23	+	{
	24	+	let mut params = [il::Param { value: il::Reg { n: 0 }, type: il::Type::W64 }];
	25	+	let mut targetParams = [il::Param { value: il::Reg { n: 1 }, type: il::Type::W64 }];
	26	+	let mut args = [il::Val::Reg(il::Reg { n: 0 })];
	27	+	let mut cases = [il::SwitchCase { value: 1, target: 1, args: &mut args[..] }];
	28	+	let mut entry = [il::Instr::Jmp { target: 1, args: &mut args[..] }];
	29	+	match edge {
	30	+	case ParameterEdge::Then => set entry[0] = il::Instr::Br {
	31	+	op: il::CmpOp::Eq, typ: il::Type::W64, a: il::Val::Imm(1), b: il::Val::Imm(1),
	32	+	thenTarget: 1, thenArgs: &mut args[..], elseTarget: 2, elseArgs: &mut [],
	33	+	},
	34	+	case ParameterEdge::Else => set entry[0] = il::Instr::Br {
	35	+	op: il::CmpOp::Eq, typ: il::Type::W64, a: il::Val::Imm(1), b: il::Val::Imm(1),
	36	+	thenTarget: 2, thenArgs: &mut [], elseTarget: 1, elseArgs: &mut args[..],
	37	+	},
	38	+	case ParameterEdge::Case => set entry[0] = il::Instr::Switch {
	39	+	val: il::Val::Imm(1), defaultTarget: 2, defaultArgs: &mut [], cases: &mut cases[..],
	40	+	},
	41	+	case ParameterEdge::Default => set entry[0] = il::Instr::Switch {
	42	+	val: il::Val::Imm(0), defaultTarget: 1, defaultArgs: &mut args[..], cases: &mut [],
	43	+	},
	44	+	else => {},
	45	+	}
	46	+	let mut target = [il::Instr::Ret { val: il::Val::Reg(il::Reg { n: 1 }) }];
	47	+	let mut other = [il::Instr::Ret { val: il::Val::Imm(0) }];
	48	+	let blocks = [
	49	+	il::Block { label: "entry", params: &[], instrs: &mut entry[..], locs: &[], preds: &[], loopDepth: 0 },
	50	+	il::Block { label: "target", params: &targetParams[..], instrs: &mut target[..], locs: &[], preds: &[], loopDepth: 0 },
	51	+	il::Block { label: "other", params: &[], instrs: &mut other[..], locs: &[], preds: &[], loopDepth: 0 },
	52	+	];
	53	+	let func = il::Fn { name: "p::parameters", params: &params[..], returnType: il::Type::W64,
	54	+	isExtern: false, isLeaf: true, blocks: &blocks[..] };
	55	+	let mut arena = alloc::new(&mut SCRATCH[..]);
	56	+	let mut code = alloc::new(&mut MEMORY[..]);
	57	+	let mut gen = generator(&mut code);
	58	+	use arena as storage in {
	59	+	let view = try! il::published::publish(&func, &storage);
	60	+	let config = super::targetConfig();
	61	+	let allocation = try! regalloc::allocate(&view, &config, &storage);
	62	+	isel::selectFn(&mut gen.e, &allocation, &func, &view);
	63	+	assert gen.e.error == nil;
	64	+	let expected = try! storage.copy(&gen.e.code[..gen.e.codeLen]);
	65	+	set params[0].value.n = 0xffffffff;
	66	+	set targetParams[0].value.n = 0xffffffff;
	67	+	alloc::reset(&mut code);
	68	+	set gen = generator(&mut code);
	69	+	isel::selectFn(&mut gen.e, &allocation, &func, &view);
	70	+	assert gen.e.error == nil and gen.e.codeLen == expected.len;
	71	+	for word, i in expected {
	72	+	assert gen.e.code[i] == word;
	73	+	}
	74	+	}
	75	+	}
	76	+	}
14	77
15	78		/// Reusable emitter allocation storage.
16	79		static MEMORY: [u8; 16777216] = [0; 16777216];
17	80		/// Function and liveness test storage.
18	81		static SCRATCH: [u8; 65536] = [0; 65536];

398	400		// Record debug location before emitting machine instructions.
399	401		if hasLocs {
400	402		emit::recordSrcLoc(s.e, block.locs[i]);
401	403		}
402	404		set s.pendingSpill = nil;
403		-	selectInstr(s, blockIdx, &instr, frame, func);
	405	+	selectInstr(s, blockIdx, &instr, frame, view);
404	406
405	407		// Flush the pending spill store, if any.
406	408		if let p = s.pendingSpill {
407	409		if let slot = regalloc::spill::spillSlot(&s.ralloc.spill, p.ssa) {
408	410		emit::emitSd(s.e, p.rd, spillBase(s), spillOffset(s, slot));

411	413		}
412	414		}
413	415		}
414	416
415	417		/// Select instructions for a single IL instruction.
416		-	unsafe fn selectInstr 'scratch 'selection (s: &mut Selector 'scratch 'selection, blockIdx: u32, instr: &il::Instr, frame: &emit::Frame, func: &il::Fn) where 'scratch: 'selection {
	418	+	unsafe fn selectInstr 'scratch 'selection (s: &mut Selector 'scratch 'selection, blockIdx: u32, instr: &il::Instr, frame: &emit::Frame, view: &il::published::Function 'scratch) where 'scratch: 'selection {
417	419		match *instr {
418	420		case il::Instr::Jmp { target, args } => {
419		-	selectJump(s, blockIdx, target, func.blocks[target].params, args);
	421	+	selectJump(s, blockIdx, target, view.blocks[target].params, args);
420	422		},
421	423		case il::Instr::Br { thenTarget, thenArgs, elseTarget, elseArgs, .. } => {
422		-	let params: *unsafe [il::Param] = func.blocks[thenTarget].params
	424	+	let params: &'scratch [il::Param] = view.blocks[thenTarget].params
423	425		if thenArgs.len > 0 and elseArgs.len == 0
424		-	else func.blocks[elseTarget].params if elseArgs.len > 0 and thenArgs.len == 0
425		-	else &[];
	426	+	else view.blocks[elseTarget].params if elseArgs.len > 0 and thenArgs.len == 0
	427	+	else &view.params[..0];
426	428		selectBranch(s, blockIdx, instr, params, thenArgs, elseArgs);
427	429		},
428	430		case il::Instr::Switch { val, defaultTarget, defaultArgs, cases } => {
429	431		let rs1 = resolveVal(s, super::SCRATCH1, val);
430	432		for c in cases {
431		-	let params: *unsafe [il::Param] = func.blocks[c.target].params
432		-	if c.args.len > 0 else &[];
	433	+	let params: &'scratch [il::Param] = view.blocks[c.target].params
	434	+	if c.args.len > 0 else &view.params[..0];
433	435		selectSwitchCase(s, rs1, c.value, c.target, params, c.args);
434	436		}
435	437		// Fall through to default.
436		-	emitBlockArgs(s, func.blocks[defaultTarget].params, defaultArgs);
	438	+	emitBlockArgs(s, view.blocks[defaultTarget].params, defaultArgs);
437	439		emit::recordBranch(s.e, defaultTarget, emit::BranchKind::Jump);
438	440		},
439	441		case il::Instr::Call { dst, func, args, .. } => selectCall(s, &func, args, dst),
440	442		else => selectFixedInstr(s, blockIdx, instr, frame),
441	443		}