radiance · commit

compiler: Check block sealing and parameter binding

9066f1a303ecda6243adbe4355d997e66fa2f5b68a81c3a8c89f4b44e70a6369

Alexis Sellier committed 6 days ago 1 parent 8b5ccb06

lib/std/lang/lower.rad +30 -19

    self: &mut FnLowerer 'arena 'phase 'function,
    labelBase: *[u8],
    param: il::Param
) -> BlockId throws (LowerError) where 'arena: 'phase, 'phase: 'function {
    let block = try createBlock(self, labelBase);
    let blk = getBlockMut(self, block);
    blk.params.append(param, alloc::arenaAllocator(self.arena));
    let allocator = alloc::arenaAllocator(self.arena);
    self.blockData[*block].params.append(param, allocator);

    return block;
}

/// Switch to building a different block.

///
/// Sealing enables SSA construction to resolve variable uses by looking up
/// values from predecessors and inserting block parameters as needed. It
/// does not prevent instructions from being added to the block.
unsafe fn sealBlock 'arena 'phase 'function (self: &mut FnLowerer 'arena 'phase 'function, block: BlockId) throws (LowerError) where 'arena: 'phase, 'phase: 'function {
    let blk = getBlockMut(self, block);
    let case Sealed::No = blk.sealState else {
        return; // Already sealed.
    };
    // Keep the current parameter count. Resolution can add more parameters.
    let paramCount = blk.paramVars.len;
    set blk.sealState = Sealed::Yes;
    let paramCount = markBlockSealed(&mut self.blockData[*block]) else return;

    // Complete each parameter that was created before sealing.
    for paramIdx in 0..paramCount {
        let varId = self.blockData[*block].paramVars[paramIdx];
        try resolveBlockArgs(self, block, Var(varId), paramIdx);
    }
}

/// Mark a block sealed and return its pending parameter count, or nil if already sealed.
fn markBlockSealed(block: &mut BlockData) -> ?u32 {
    let case Sealed::No = block.sealState else {
        return nil; // Already sealed.
    };
    // Keep the current parameter count. Resolution can add more parameters.
    let paramCount = block.paramVars.len;
    set block.sealState = Sealed::Yes;
    return paramCount;
}

/// Seal a block and switch to it.
unsafe fn switchToAndSeal 'arena 'phase 'function (self: &mut FnLowerer 'arena 'phase 'function, block: BlockId) throws (LowerError) where 'arena: 'phase, 'phase: 'function {
    try sealBlock(self, block);
    switchToBlock(self, block);
}

    let reg = nextReg(self);
    let type = getVar(&self.vars, v).type;

    // Create block parameter and add it to the block.
    let param = il::Param { value: reg, type };
    let blk = getBlockMut(self, block);
    let paramIdx = blk.paramVars.len;
    blk.params.append(param, alloc::arenaAllocator(self.arena));
    blk.paramVars.append(*v, alloc::arenaAllocator(self.arena)); // Associate variable with parameter.

    // Record that this variable's value in this block is now the parameter register.
    // This must happen before the predecessor loop to handle self-referential loops.
    set blk.vars[*v] = il::Val::Reg(reg);
    let allocator = alloc::arenaAllocator(self.arena);
    let paramIdx = bindBlockParam(&mut self.blockData[*block], param, v, allocator);

    if blk.sealState == Sealed::Yes {
    if self.blockData[*block].sealState == Sealed::Yes {
        // Block sealed: check for trivial phi before committing. If all
        // predecessors provide the same value, we can remove the param we
        // just created and use that value directly.
        if let trivial = try getTrivialPhiVal(self, block, v) {
            let provisional = il::Val::Reg(reg);
            removeLastBlockParam(self, block);
            rewriteCachedVarValue(self, v, provisional, trivial);
            set getBlockMut(self, block).vars[*v] = trivial;
            set self.blockData[*block].vars[*v] = trivial;
            return trivial;
        }
        // Non-trivial phi: patch predecessors to pass their values.
        try resolveBlockArgs(self, block, v, paramIdx);
    }
    return il::Val::Reg(reg);
}

/// Register a block parameter and its provisional variable value.
fn bindBlockParam(block: &mut BlockData, param: il::Param, v: Var, allocator: alloc::Allocator) -> u32 {
    let paramIdx = block.paramVars.len;
    block.params.append(param, allocator);
    block.paramVars.append(*v, allocator); // Associate variable with parameter.

    // Record that this variable's value in this block is now the parameter register.
    // This must happen before the predecessor loop to handle self-referential loops.
    set block.vars[*v] = il::Val::Reg(param.value);
    return paramIdx;
}

/// Complete the block parameter at `paramIdx`. Look up the variable's value in
/// each predecessor and patch its terminator with the edge argument.
///
/// This is the block-parameter equivalent of adding operands to a phi-function in
/// traditional SSA. Where a phi-function merges values at the join point:

test/tests/ssa.predecessor.storage.rad +16 -0

        set count += 1;
    }
    return first + second + count;
}

/// Seal nested loop headers with stable and changing carried values.
fn nested(limit: u32) -> u32 {
    let mut count: u32 = 0;
    let mut stable: u32 = 23;
    for outer in 0..limit {
        for inner in 0..outer + 1 {
            set count += 1;
            if inner % 2 == 0 {
                set stable = 23;
            }
        }
    }
    return count + stable;
}

/// Compare both branch paths over empty and repeated loop iterations.
@default fn main() -> u32 {
    for limit in 0..32 {
        assert unchanged(limit) == 18 + limit;
        assert nested(limit) == 23 + limit * (limit + 1) / 2;
        for choose in [false, true] {
            let mut total: u32 = 3;
            let mut carry: u32 = 5;
            for index in 0..limit {
                set carry += 7 if choose and index % 2 == 0 else 13;

2206	2206		self: &mut FnLowerer 'arena 'phase 'function,
2207	2207		labelBase: *[u8],
2208	2208		param: il::Param
2209	2209		) -> BlockId throws (LowerError) where 'arena: 'phase, 'phase: 'function {
2210	2210		let block = try createBlock(self, labelBase);
2211		-	let blk = getBlockMut(self, block);
2212		-	blk.params.append(param, alloc::arenaAllocator(self.arena));
	2211	+	let allocator = alloc::arenaAllocator(self.arena);
	2212	+	self.blockData[*block].params.append(param, allocator);
2213	2213
2214	2214		return block;
2215	2215		}
2216	2216
2217	2217		/// Switch to building a different block.

2224	2224		///
2225	2225		/// Sealing enables SSA construction to resolve variable uses by looking up
2226	2226		/// values from predecessors and inserting block parameters as needed. It
2227	2227		/// does not prevent instructions from being added to the block.
2228	2228		unsafe fn sealBlock 'arena 'phase 'function (self: &mut FnLowerer 'arena 'phase 'function, block: BlockId) throws (LowerError) where 'arena: 'phase, 'phase: 'function {
2229		-	let blk = getBlockMut(self, block);
2230		-	let case Sealed::No = blk.sealState else {
2231		-	return; // Already sealed.
2232		-	};
2233		-	// Keep the current parameter count. Resolution can add more parameters.
2234		-	let paramCount = blk.paramVars.len;
2235		-	set blk.sealState = Sealed::Yes;
	2229	+	let paramCount = markBlockSealed(&mut self.blockData[*block]) else return;
2236	2230
2237	2231		// Complete each parameter that was created before sealing.
2238	2232		for paramIdx in 0..paramCount {
2239	2233		let varId = self.blockData[*block].paramVars[paramIdx];
2240	2234		try resolveBlockArgs(self, block, Var(varId), paramIdx);
2241	2235		}
2242	2236		}
2243	2237
	2238	+	/// Mark a block sealed and return its pending parameter count, or nil if already sealed.
	2239	+	fn markBlockSealed(block: &mut BlockData) -> ?u32 {
	2240	+	let case Sealed::No = block.sealState else {
	2241	+	return nil; // Already sealed.
	2242	+	};
	2243	+	// Keep the current parameter count. Resolution can add more parameters.
	2244	+	let paramCount = block.paramVars.len;
	2245	+	set block.sealState = Sealed::Yes;
	2246	+	return paramCount;
	2247	+	}
	2248	+
2244	2249		/// Seal a block and switch to it.
2245	2250		unsafe fn switchToAndSeal 'arena 'phase 'function (self: &mut FnLowerer 'arena 'phase 'function, block: BlockId) throws (LowerError) where 'arena: 'phase, 'phase: 'function {
2246	2251		try sealBlock(self, block);
2247	2252		switchToBlock(self, block);
2248	2253		}

3110	3115		let reg = nextReg(self);
3111	3116		let type = getVar(&self.vars, v).type;
3112	3117
3113	3118		// Create block parameter and add it to the block.
3114	3119		let param = il::Param { value: reg, type };
3115		-	let blk = getBlockMut(self, block);
3116		-	let paramIdx = blk.paramVars.len;
3117		-	blk.params.append(param, alloc::arenaAllocator(self.arena));
3118		-	blk.paramVars.append(*v, alloc::arenaAllocator(self.arena)); // Associate variable with parameter.
3119		-
3120		-	// Record that this variable's value in this block is now the parameter register.
3121		-	// This must happen before the predecessor loop to handle self-referential loops.
3122		-	set blk.vars[*v] = il::Val::Reg(reg);
	3120	+	let allocator = alloc::arenaAllocator(self.arena);
	3121	+	let paramIdx = bindBlockParam(&mut self.blockData[*block], param, v, allocator);
3123	3122
3124		-	if blk.sealState == Sealed::Yes {
	3123	+	if self.blockData[*block].sealState == Sealed::Yes {
3125	3124		// Block sealed: check for trivial phi before committing. If all
3126	3125		// predecessors provide the same value, we can remove the param we
3127	3126		// just created and use that value directly.
3128	3127		if let trivial = try getTrivialPhiVal(self, block, v) {
3129	3128		let provisional = il::Val::Reg(reg);
3130	3129		removeLastBlockParam(self, block);
3131	3130		rewriteCachedVarValue(self, v, provisional, trivial);
3132		-	set getBlockMut(self, block).vars[*v] = trivial;
	3131	+	set self.blockData[block].vars[v] = trivial;
3133	3132		return trivial;
3134	3133		}
3135	3134		// Non-trivial phi: patch predecessors to pass their values.
3136	3135		try resolveBlockArgs(self, block, v, paramIdx);
3137	3136		}
3138	3137		return il::Val::Reg(reg);
3139	3138		}
3140	3139
	3140	+	/// Register a block parameter and its provisional variable value.
	3141	+	fn bindBlockParam(block: &mut BlockData, param: il::Param, v: Var, allocator: alloc::Allocator) -> u32 {
	3142	+	let paramIdx = block.paramVars.len;
	3143	+	block.params.append(param, allocator);
	3144	+	block.paramVars.append(*v, allocator); // Associate variable with parameter.
	3145	+
	3146	+	// Record that this variable's value in this block is now the parameter register.
	3147	+	// This must happen before the predecessor loop to handle self-referential loops.
	3148	+	set block.vars[*v] = il::Val::Reg(param.value);
	3149	+	return paramIdx;
	3150	+	}
	3151	+
3141	3152		/// Complete the block parameter at `paramIdx`. Look up the variable's value in
3142	3153		/// each predecessor and patch its terminator with the edge argument.
3143	3154		///
3144	3155		/// This is the block-parameter equivalent of adding operands to a phi-function in
3145	3156		/// traditional SSA. Where a phi-function merges values at the join point:

36	36		set count += 1;
37	37		}
38	38		return first + second + count;
39	39		}
40	40
	41	+	/// Seal nested loop headers with stable and changing carried values.
	42	+	fn nested(limit: u32) -> u32 {
	43	+	let mut count: u32 = 0;
	44	+	let mut stable: u32 = 23;
	45	+	for outer in 0..limit {
	46	+	for inner in 0..outer + 1 {
	47	+	set count += 1;
	48	+	if inner % 2 == 0 {
	49	+	set stable = 23;
	50	+	}
	51	+	}
	52	+	}
	53	+	return count + stable;
	54	+	}
	55	+
41	56		/// Compare both branch paths over empty and repeated loop iterations.
42	57		@default fn main() -> u32 {
43	58		for limit in 0..32 {
44	59		assert unchanged(limit) == 18 + limit;
	60	+	assert nested(limit) == 23 + limit * (limit + 1) / 2;
45	61		for choose in [false, true] {
46	62		let mut total: u32 = 3;
47	63		let mut carry: u32 = 5;
48	64		for index in 0..limit {
49	65		set carry += 7 if choose and index % 2 == 0 else 13;