radiance · commit

compiler: Own switch tables and check case insertion

a14104e22b731ed92d00e1f878c117832366397bb4afddf0a5355fc572dc236a

Alexis Sellier committed 6 days ago 1 parent b05a8d87

lib/std/lang/lower.rad +23 -27

        }
    }
    return try finalizeBlocks(self);
}

/// Append an initialized switch case to owned storage.
fn appendSwitchCase(
    cases: &mut *mut [il::SwitchCase],
    value: i64,
    target: BlockId,
    args: *unsafe mut [il::Val],
    allocator: alloc::Allocator,
) {
    cases.append(il::SwitchCase { value, target: *target, args }, allocator);
}

/// Lower a scalar match as a switch instruction.
unsafe fn lowerMatchSwitch 'arena 'phase 'function (self: &mut FnLowerer 'arena 'phase 'function, prongs: *[*ast::Node], subject: &MatchSubject, mergeBlock: &mut ?BlockId) throws (LowerError) where 'arena: 'phase, 'phase: 'function {
    let mut blocks: *mut [BlockId] = &mut [];
    let mut cases: *unsafe mut [il::SwitchCase] = &mut [];
    let mut cases: *mut [il::SwitchCase] = &mut [];
    let mut defaultIdx: u32 = 0;
    let entry = currentBlock(self);

    for p, i in prongs {
        let case ast::NodeValue::MatchProng(prong) = p.value

                blocks.append(try createBlock(self, "case"), alloc::arenaAllocator(self.arena));
                for pat in pats {
                    let cv = resolver::constValueEntry(self.low.resolver, pat)
                        else throw LowerError::MissingConst(pat);

                    cases.append(il::SwitchCase {
                        value: constToScalar(cv),
                        target: *blocks[i],
                        args: &mut []
                    }, alloc::arenaAllocator(self.arena));
                    appendSwitchCase(&mut cases, constToScalar(cv), blocks[i], &mut [], alloc::arenaAllocator(self.arena));
                }
            }
        }
        addPredecessor(self, blocks[i], entry);
    }
    emit(self, il::Instr::Switch {
        val: subject.val,
        defaultTarget: *blocks[defaultIdx],
        defaultArgs: &mut [],
        cases: &mut cases[..]
        cases: (&mut cases[..]) as *unsafe mut [il::SwitchCase]
    });

    for p, i in prongs {
        let case ast::NodeValue::MatchProng(prong) = p.value
            else throw LowerError::UnexpectedNodeValue(p);

    addPredecessor(self, mergeBlock, currentBlock(self));

    // Create comparison blocks for each non-void variant and build switch cases.
    // Void variants jump directly to merge with `true`.
    let trueArgs = try allocVal(self, il::Val::Imm(1));
    let mut cases: *unsafe mut [il::SwitchCase] = &mut [];
    let mut cases: *mut [il::SwitchCase] = &mut [];
    for variant, i in unionInfo.variants {
        if variant.valueType == resolver::Type::Void {
            cases.append(il::SwitchCase {
                value: i as i64,
                target: *mergeBlock,
                args: trueArgs
            }, alloc::arenaAllocator(self.arena));
            appendSwitchCase(&mut cases, i as i64, mergeBlock, trueArgs, alloc::arenaAllocator(self.arena));
        } else {
            let payloadBlock = try createBlock(self, "eq#payload");
            cases.append(il::SwitchCase {
                value: i as i64,
                target: *payloadBlock,
                args: &mut []
            }, alloc::arenaAllocator(self.arena));
            appendSwitchCase(&mut cases, i as i64, payloadBlock, &mut [], alloc::arenaAllocator(self.arena));
        }
    }

    // Emit switch in @tag block. Default arm is unreachable since we cover all variants.
    let unreachableBlock = try createBlock(self, "eq#unreachable");
    try switchToAndSeal(self, tagBlock);
    emit(self, il::Instr::Switch {
        val: tagA,
        defaultTarget: *unreachableBlock,
        defaultArgs: &mut [],
        cases
        cases: (&mut cases[..]) as *unsafe mut [il::SwitchCase]
    });

    // Add predecessor edges for switch targets.
    addPredecessor(self, unreachableBlock, tagBlock);
    for c in cases {
    for c in &cases[..] {
        addPredecessor(self, BlockId(c.target), tagBlock);
    }
    let valOffset = unionInfo.valOffset as i32;

    // Emit payload comparison blocks for non-void variants.

) throws (LowerError) where 'arena: 'phase, 'phase: 'function {
    let entry = currentBlock(self);

    // First pass: create blocks, resolve error types, and build switch cases.
    let mut targets: [?CatchTarget; MAX_CATCH_CLAUSES] = [nil; MAX_CATCH_CLAUSES];
    let mut cases: *unsafe mut [il::SwitchCase] = &mut [];
    let mut cases: *mut [il::SwitchCase] = &mut [];
    let mut defaultIdx: ?u32 = nil;

    for clauseNode, i in catches {
        let case ast::NodeValue::CatchClause(clause) = clauseNode.value
            else panic "lowerMultiCatch: expected CatchClause";


        if let typeNode = clause.typeNode {
            let errTy = try typeOf(self, typeNode);
            set targets[i] = CatchTarget { block, errorType: errTy };

            cases.append(il::SwitchCase {
                value: getOrAssignErrorTag(self.low, errTy) as i64,
                target: *block,
                args: &mut []
            }, alloc::arenaAllocator(self.arena));
            let tag = getOrAssignErrorTag(self.low, errTy) as i64;
            appendSwitchCase(&mut cases, tag, block, &mut [], alloc::arenaAllocator(self.arena));
        } else {
            set targets[i] = CatchTarget { block, errorType: nil };
            set defaultIdx = i;
        }
    }

    let defaultTarget = selectedDefault else panic "lowerMultiCatch: missing default destination";
    emit(self, il::Instr::Switch {
        val: il::Val::Reg(tagReg),
        defaultTarget: *defaultTarget,
        defaultArgs: &mut [],
        cases
        cases: (&mut cases[..]) as *unsafe mut [il::SwitchCase]
    });

    // Second pass: emit each catch clause body.
    for clauseNode, i in catches {
        let case ast::NodeValue::CatchClause(clause) = clauseNode.value

test/tests/match.switch.capacity.rad +16 -0

        case 63 => return 163,
        else => return 999,
    }
}

/// Multiple case values can share a destination and its merged value.
fn grouped(value: u32) -> u32 {
    let mut result: u32 = 0;
    match value {
        case 0, 2, 4, 6 => set result = 10,
        case 1, 3, 5, 7 => set result = 20,
        else => set result = 30,
    }
    return result + value;
}

/// Exercise every case and each fallback.
@default fn main() -> u32 {
    for value in 0..31 { assert select31(value) == value + 100; }
    assert select31(31) == 999;
    for value in 0..32 { assert select32(value) == value + 100; }
    assert select32(32) == 999;
    for value in 0..64 { assert select64(value) == value + 100; }
    assert select64(64) == 999;
    for value in 0..8 {
        let base: u32 = 10 if value % 2 == 0 else 20;
        assert grouped(value) == base + value;
    }
    assert grouped(8) == 38;
    return 0;
}

3756	3756		}
3757	3757		}
3758	3758		return try finalizeBlocks(self);
3759	3759		}
3760	3760
	3761	+	/// Append an initialized switch case to owned storage.
	3762	+	fn appendSwitchCase(
	3763	+	cases: &mut *mut [il::SwitchCase],
	3764	+	value: i64,
	3765	+	target: BlockId,
	3766	+	args: *unsafe mut [il::Val],
	3767	+	allocator: alloc::Allocator,
	3768	+	) {
	3769	+	cases.append(il::SwitchCase { value, target: *target, args }, allocator);
	3770	+	}
	3771	+
3761	3772		/// Lower a scalar match as a switch instruction.
3762	3773		unsafe fn lowerMatchSwitch 'arena 'phase 'function (self: &mut FnLowerer 'arena 'phase 'function, prongs: [ast::Node], subject: &MatchSubject, mergeBlock: &mut ?BlockId) throws (LowerError) where 'arena: 'phase, 'phase: 'function {
3763	3774		let mut blocks: *mut [BlockId] = &mut [];
3764		-	let mut cases: *unsafe mut [il::SwitchCase] = &mut [];
	3775	+	let mut cases: *mut [il::SwitchCase] = &mut [];
3765	3776		let mut defaultIdx: u32 = 0;
3766	3777		let entry = currentBlock(self);
3767	3778
3768	3779		for p, i in prongs {
3769	3780		let case ast::NodeValue::MatchProng(prong) = p.value

3778	3789		blocks.append(try createBlock(self, "case"), alloc::arenaAllocator(self.arena));
3779	3790		for pat in pats {
3780	3791		let cv = resolver::constValueEntry(self.low.resolver, pat)
3781	3792		else throw LowerError::MissingConst(pat);
3782	3793
3783		-	cases.append(il::SwitchCase {
3784		-	value: constToScalar(cv),
3785		-	target: *blocks[i],
3786		-	args: &mut []
3787		-	}, alloc::arenaAllocator(self.arena));
	3794	+	appendSwitchCase(&mut cases, constToScalar(cv), blocks[i], &mut [], alloc::arenaAllocator(self.arena));
3788	3795		}
3789	3796		}
3790	3797		}
3791	3798		addPredecessor(self, blocks[i], entry);
3792	3799		}
3793	3800		emit(self, il::Instr::Switch {
3794	3801		val: subject.val,
3795	3802		defaultTarget: *blocks[defaultIdx],
3796	3803		defaultArgs: &mut [],
3797		-	cases: &mut cases[..]
	3804	+	cases: (&mut cases[..]) as *unsafe mut [il::SwitchCase]
3798	3805		});
3799	3806
3800	3807		for p, i in prongs {
3801	3808		let case ast::NodeValue::MatchProng(prong) = p.value
3802	3809		else throw LowerError::UnexpectedNodeValue(p);

4850	4857		addPredecessor(self, mergeBlock, currentBlock(self));
4851	4858
4852	4859		// Create comparison blocks for each non-void variant and build switch cases.
4853	4860		// Void variants jump directly to merge with `true`.
4854	4861		let trueArgs = try allocVal(self, il::Val::Imm(1));
4855		-	let mut cases: *unsafe mut [il::SwitchCase] = &mut [];
	4862	+	let mut cases: *mut [il::SwitchCase] = &mut [];
4856	4863		for variant, i in unionInfo.variants {
4857	4864		if variant.valueType == resolver::Type::Void {
4858		-	cases.append(il::SwitchCase {
4859		-	value: i as i64,
4860		-	target: *mergeBlock,
4861		-	args: trueArgs
4862		-	}, alloc::arenaAllocator(self.arena));
	4865	+	appendSwitchCase(&mut cases, i as i64, mergeBlock, trueArgs, alloc::arenaAllocator(self.arena));
4863	4866		} else {
4864	4867		let payloadBlock = try createBlock(self, "eq#payload");
4865		-	cases.append(il::SwitchCase {
4866		-	value: i as i64,
4867		-	target: *payloadBlock,
4868		-	args: &mut []
4869		-	}, alloc::arenaAllocator(self.arena));
	4868	+	appendSwitchCase(&mut cases, i as i64, payloadBlock, &mut [], alloc::arenaAllocator(self.arena));
4870	4869		}
4871	4870		}
4872	4871
4873	4872		// Emit switch in @tag block. Default arm is unreachable since we cover all variants.
4874	4873		let unreachableBlock = try createBlock(self, "eq#unreachable");
4875	4874		try switchToAndSeal(self, tagBlock);
4876	4875		emit(self, il::Instr::Switch {
4877	4876		val: tagA,
4878	4877		defaultTarget: *unreachableBlock,
4879	4878		defaultArgs: &mut [],
4880		-	cases
	4879	+	cases: (&mut cases[..]) as *unsafe mut [il::SwitchCase]
4881	4880		});
4882	4881
4883	4882		// Add predecessor edges for switch targets.
4884	4883		addPredecessor(self, unreachableBlock, tagBlock);
4885		-	for c in cases {
	4884	+	for c in &cases[..] {
4886	4885		addPredecessor(self, BlockId(c.target), tagBlock);
4887	4886		}
4888	4887		let valOffset = unionInfo.valOffset as i32;
4889	4888
4890	4889		// Emit payload comparison blocks for non-void variants.

6642	6641		) throws (LowerError) where 'arena: 'phase, 'phase: 'function {
6643	6642		let entry = currentBlock(self);
6644	6643
6645	6644		// First pass: create blocks, resolve error types, and build switch cases.
6646	6645		let mut targets: [?CatchTarget; MAX_CATCH_CLAUSES] = [nil; MAX_CATCH_CLAUSES];
6647		-	let mut cases: *unsafe mut [il::SwitchCase] = &mut [];
	6646	+	let mut cases: *mut [il::SwitchCase] = &mut [];
6648	6647		let mut defaultIdx: ?u32 = nil;
6649	6648
6650	6649		for clauseNode, i in catches {
6651	6650		let case ast::NodeValue::CatchClause(clause) = clauseNode.value
6652	6651		else panic "lowerMultiCatch: expected CatchClause";

6656	6655
6657	6656		if let typeNode = clause.typeNode {
6658	6657		let errTy = try typeOf(self, typeNode);
6659	6658		set targets[i] = CatchTarget { block, errorType: errTy };
6660	6659
6661		-	cases.append(il::SwitchCase {
6662		-	value: getOrAssignErrorTag(self.low, errTy) as i64,
6663		-	target: *block,
6664		-	args: &mut []
6665		-	}, alloc::arenaAllocator(self.arena));
	6660	+	let tag = getOrAssignErrorTag(self.low, errTy) as i64;
	6661	+	appendSwitchCase(&mut cases, tag, block, &mut [], alloc::arenaAllocator(self.arena));
6666	6662		} else {
6667	6663		set targets[i] = CatchTarget { block, errorType: nil };
6668	6664		set defaultIdx = i;
6669	6665		}
6670	6666		}

6681	6677		let defaultTarget = selectedDefault else panic "lowerMultiCatch: missing default destination";
6682	6678		emit(self, il::Instr::Switch {
6683	6679		val: il::Val::Reg(tagReg),
6684	6680		defaultTarget: *defaultTarget,
6685	6681		defaultArgs: &mut [],
6686		-	cases
	6682	+	cases: (&mut cases[..]) as *unsafe mut [il::SwitchCase]
6687	6683		});
6688	6684
6689	6685		// Second pass: emit each catch clause body.
6690	6686		for clauseNode, i in catches {
6691	6687		let case ast::NodeValue::CatchClause(clause) = clauseNode.value

147	147		case 63 => return 163,
148	148		else => return 999,
149	149		}
150	150		}
151	151
	152	+	/// Multiple case values can share a destination and its merged value.
	153	+	fn grouped(value: u32) -> u32 {
	154	+	let mut result: u32 = 0;
	155	+	match value {
	156	+	case 0, 2, 4, 6 => set result = 10,
	157	+	case 1, 3, 5, 7 => set result = 20,
	158	+	else => set result = 30,
	159	+	}
	160	+	return result + value;
	161	+	}
	162	+
152	163		/// Exercise every case and each fallback.
153	164		@default fn main() -> u32 {
154	165		for value in 0..31 { assert select31(value) == value + 100; }
155	166		assert select31(31) == 999;
156	167		for value in 0..32 { assert select32(value) == value + 100; }
157	168		assert select32(32) == 999;
158	169		for value in 0..64 { assert select64(value) == value + 100; }
159	170		assert select64(64) == 999;
	171	+	for value in 0..8 {
	172	+	let base: u32 = 10 if value % 2 == 0 else 20;
	173	+	assert grouped(value) == base + value;
	174	+	}
	175	+	assert grouped(8) == 38;
160	176		return 0;
161	177		}