compiler: Check SSA variable source selection
8b5ccb063df3a345c1a38709e30d8b642eb9a92ea4178c28933a705fd846d3b7
1 parent
294a5bd7
lib/std/lang/lower.rad
+33 -9
| 461 | 461 | ||
| 462 | 462 | /// A variable handle. Represents a source-level variable during lowering. |
|
| 463 | 463 | /// The same [`Var`] can have different SSA values in different blocks. |
|
| 464 | 464 | export record Var: Copy(u32); |
|
| 465 | 465 | ||
| 466 | + | /// Source of a variable value at a block entry or use. |
|
| 467 | + | union VarSource: Copy { |
|
| 468 | + | /// A value already available in the block. |
|
| 469 | + | Value(il::Val), |
|
| 470 | + | /// A value supplied by one distinct predecessor. |
|
| 471 | + | Predecessor(BlockId), |
|
| 472 | + | /// A block parameter must merge incoming values. |
|
| 473 | + | Merge, |
|
| 474 | + | /// A sealed non-entry block has no predecessor. |
|
| 475 | + | Invalid, |
|
| 476 | + | } |
|
| 477 | + | ||
| 466 | 478 | /// Metadata for a source-level variable, stored once per function. |
|
| 467 | 479 | /// |
|
| 468 | 480 | /// Each variable declaration in the source creates one [`VarData`] entry in the |
|
| 469 | 481 | /// function's `variables` array, indexed by `id`. This contains static |
|
| 470 | 482 | /// properties that don't change across basic blocks. |
| 2990 | 3002 | /// When control flow merges from multiple predecessors with different |
|
| 2991 | 3003 | /// definitions, it creates a block parameter to unify them. |
|
| 2992 | 3004 | unsafe fn useVarInBlock 'arena 'phase 'function (self: &mut FnLowerer 'arena 'phase 'function, block: BlockId, v: Var) -> il::Val throws (LowerError) where 'arena: 'phase, 'phase: 'function { |
|
| 2993 | 3005 | assert *v < self.vars.len; |
|
| 2994 | 3006 | ||
| 2995 | - | let blk = getBlockMut(self, block); |
|
| 3007 | + | match varSource(&self.blockData[..], block, self.entryBlock, v) { |
|
| 3008 | + | case VarSource::Value(val) => return val, |
|
| 3009 | + | case VarSource::Predecessor(pred) => { |
|
| 3010 | + | let val = try useVarInBlock(self, pred, v); |
|
| 3011 | + | set self.blockData[*block].vars[*v] = val; // Cache. |
|
| 3012 | + | return val; |
|
| 3013 | + | } |
|
| 3014 | + | case VarSource::Merge => return try createBlockParam(self, block, v), |
|
| 3015 | + | case VarSource::Invalid => throw LowerError::InvalidUse, |
|
| 3016 | + | } |
|
| 3017 | + | } |
|
| 3018 | + | ||
| 3019 | + | /// Select the cached, predecessor, or merge source while borrowing block state. |
|
| 3020 | + | fn varSource(blocks: &[BlockData], block: BlockId, entryBlock: ?BlockId, v: Var) -> VarSource { |
|
| 3021 | + | let blk = &blocks[*block]; |
|
| 2996 | 3022 | if let val = blk.vars[*v] { |
|
| 2997 | - | return val; |
|
| 3023 | + | return VarSource::Value(val); |
|
| 2998 | 3024 | } |
|
| 2999 | 3025 | // Entry block cannot have block parameters. If variable isn't defined |
|
| 3000 | 3026 | // in entry, we return undefined. |
|
| 3001 | - | if block == self.entryBlock { |
|
| 3002 | - | return il::Val::Undef; |
|
| 3027 | + | if block == entryBlock { |
|
| 3028 | + | return VarSource::Value(il::Val::Undef); |
|
| 3003 | 3029 | } |
|
| 3004 | 3030 | if blk.sealState == Sealed::Yes { |
|
| 3005 | 3031 | if blk.preds.len == 0 { |
|
| 3006 | 3032 | // Variable used in sealed block with no predecessors. |
|
| 3007 | - | throw LowerError::InvalidUse; |
|
| 3033 | + | return VarSource::Invalid; |
|
| 3008 | 3034 | } |
|
| 3009 | 3035 | // Single predecessor means no merge needed, variable is implicitly |
|
| 3010 | 3036 | // available without a block parameter. |
|
| 3011 | 3037 | if blk.preds.len == 1 { |
|
| 3012 | 3038 | let pred = BlockId(blk.preds[0]); |
|
| 3013 | 3039 | if *pred <> *block { |
|
| 3014 | - | let val = try useVarInBlock(self, pred, v); |
|
| 3015 | - | set blk.vars[*v] = val; // Cache. |
|
| 3016 | - | return val; |
|
| 3040 | + | return VarSource::Predecessor(pred); |
|
| 3017 | 3041 | } |
|
| 3018 | 3042 | } |
|
| 3019 | 3043 | } |
|
| 3020 | 3044 | // Multiple predecessors or unsealed block: need a block parameter to merge |
|
| 3021 | 3045 | // the control flow paths. |
|
| 3022 | - | return try createBlockParam(self, block, v); |
|
| 3046 | + | return VarSource::Merge; |
|
| 3023 | 3047 | } |
|
| 3024 | 3048 | ||
| 3025 | 3049 | /// Look up a variable by name in the current scope. |
|
| 3026 | 3050 | /// Searches from most recently declared to first, enabling shadowing. |
|
| 3027 | 3051 | fn lookupVarByName 'function (variables: &Variables 'function, name: *[u8]) -> ?Var { |
test/tests/ssa.lookup.paths.rad
added
+42 -0
| 1 | + | //! returns: 0 |
|
| 2 | + | ||
| 3 | + | /// Resolve carried values through single-predecessor paths and nested joins. |
|
| 4 | + | fn run(value: u32, first: bool, second: bool) -> u32 { |
|
| 5 | + | let mut result = value; |
|
| 6 | + | if first { |
|
| 7 | + | if second { |
|
| 8 | + | set result += 3; |
|
| 9 | + | } else { |
|
| 10 | + | set result += 5; |
|
| 11 | + | } |
|
| 12 | + | } else { |
|
| 13 | + | if second { |
|
| 14 | + | set result += 7; |
|
| 15 | + | } else { |
|
| 16 | + | set result += 11; |
|
| 17 | + | } |
|
| 18 | + | } |
|
| 19 | + | let saved = result; |
|
| 20 | + | if second { |
|
| 21 | + | set result += saved; |
|
| 22 | + | } else { |
|
| 23 | + | set result += saved * 3; |
|
| 24 | + | } |
|
| 25 | + | return result; |
|
| 26 | + | } |
|
| 27 | + | ||
| 28 | + | /// Check each path against an independent arithmetic result. |
|
| 29 | + | @default fn main() -> u32 { |
|
| 30 | + | for value in 0..16 { |
|
| 31 | + | for first in [false, true] { |
|
| 32 | + | for second in [false, true] { |
|
| 33 | + | let firstAmount: u32 = 3 if second else 5; |
|
| 34 | + | let secondAmount: u32 = 7 if second else 11; |
|
| 35 | + | let amount = firstAmount if first else secondAmount; |
|
| 36 | + | let multiplier: u32 = 2 if second else 4; |
|
| 37 | + | assert run(value, first, second) == (value + amount) * multiplier; |
|
| 38 | + | } |
|
| 39 | + | } |
|
| 40 | + | } |
|
| 41 | + | return 0; |
|
| 42 | + | } |