lower: Reuse pending block parameter state
ecdf6a84d599477eb0b8759cc296bd4f17b666e5a9a12bb8da0fd17f0170038c
Unsealed block parameters already record each pending variable. Use that list during sealing and pass known parameter indexes to avoid duplicate storage and repeated searches. Assisted-by: Codex:gpt-6-astra
1 parent
95ea08b1
lib/std/lang/lower.rad
+41 -54
| 497 | 497 | /// |
|
| 498 | 498 | /// The key invariants: |
|
| 499 | 499 | /// |
|
| 500 | 500 | /// - A block is "open" if it has no terminator; instructions can be added. |
|
| 501 | 501 | /// - A block is "sealed" when all predecessor edges are known. |
|
| 502 | - | /// - Sealing is required before SSA construction can insert block parameters. |
|
| 502 | + | /// - Sealing resolves the predecessor arguments for block parameters. |
|
| 503 | 503 | /// |
|
| 504 | 504 | /// This differs from the final [`il::Block`] which is immutable and fully formed. |
|
| 505 | 505 | record BlockData: Copy { |
|
| 506 | 506 | /// Block label for debugging and IL printing. |
|
| 507 | 507 | label: *[u8], |
|
| 508 | 508 | /// Block parameters for merging values at control flow joins. These |
|
| 509 | 509 | /// receive values from predecessor edges when control flow merges. |
|
| 510 | 510 | params: *mut [il::Param], |
|
| 511 | - | /// Variable ids corresponding to each parameter. Used to map block params |
|
| 512 | - | /// back to source variables when building argument lists for jumps. |
|
| 511 | + | /// Variable ids in parameter order. Before sealing, these are the variables |
|
| 512 | + | /// whose predecessor arguments must be resolved. |
|
| 513 | 513 | paramVars: *mut [u32], |
|
| 514 | 514 | /// Instructions accumulated so far. The last instruction should eventually |
|
| 515 | 515 | /// be a terminator. |
|
| 516 | 516 | instrs: *mut [il::Instr], |
|
| 517 | 517 | /// Debug source locations, one per instruction. Only populated when |
| 532 | 532 | } |
|
| 533 | 533 | ||
| 534 | 534 | /// Block sealing state for SSA construction. |
|
| 535 | 535 | /// |
|
| 536 | 536 | /// A block is "unsealed" while its predecessors are still being discovered. |
|
| 537 | - | /// During this time, variables used before being defined locally are tracked. |
|
| 538 | - | /// Once all predecessors are known, the block is sealed and those variables |
|
| 539 | - | /// are resolved via [`resolveBlockArgs`]. |
|
| 537 | + | /// Before sealing, `BlockData.paramVars` records each variable that needs a |
|
| 538 | + | /// block parameter. Once all predecessors are known, the block is sealed and |
|
| 539 | + | /// those parameters are resolved via [`resolveBlockArgs`]. |
|
| 540 | 540 | union Sealed: Copy { |
|
| 541 | 541 | /// Block is unsealed; predecessors may still be added. |
|
| 542 | - | No { incompleteVars: *mut [u32] }, |
|
| 542 | + | No, |
|
| 543 | 543 | /// Block is sealed; all predecessors are known. |
|
| 544 | 544 | Yes, |
|
| 545 | 545 | } |
|
| 546 | 546 | ||
| 547 | 547 | /////////////////////////////////// |
| 2036 | 2036 | paramVars: &mut [], |
|
| 2037 | 2037 | instrs: &mut [], |
|
| 2038 | 2038 | locs: &mut [], |
|
| 2039 | 2039 | preds: &mut [], |
|
| 2040 | 2040 | vars, |
|
| 2041 | - | sealState: Sealed::No { incompleteVars: &mut [] }, |
|
| 2041 | + | sealState: Sealed::No, |
|
| 2042 | 2042 | loopDepth: self.loopDepth, |
|
| 2043 | 2043 | }, self.allocator); |
|
| 2044 | 2044 | ||
| 2045 | 2045 | return id; |
|
| 2046 | 2046 | } |
| 2069 | 2069 | /// Sealing enables SSA construction to resolve variable uses by looking up |
|
| 2070 | 2070 | /// values from predecessors and inserting block parameters as needed. It |
|
| 2071 | 2071 | /// does not prevent instructions from being added to the block. |
|
| 2072 | 2072 | fn sealBlock(self: *mut FnLowerer, block: BlockId) throws (LowerError) { |
|
| 2073 | 2073 | let blk = getBlockMut(self, block); |
|
| 2074 | - | let case Sealed::No { incompleteVars } = blk.sealState else { |
|
| 2074 | + | let case Sealed::No = blk.sealState else { |
|
| 2075 | 2075 | return; // Already sealed. |
|
| 2076 | 2076 | }; |
|
| 2077 | + | // Keep the current parameter list. Resolution can add more parameters. |
|
| 2078 | + | let paramVars = blk.paramVars; |
|
| 2077 | 2079 | set blk.sealState = Sealed::Yes; |
|
| 2078 | 2080 | ||
| 2079 | - | // Complete all incomplete block parameters. |
|
| 2080 | - | for varId in incompleteVars { |
|
| 2081 | - | try resolveBlockArgs(self, block, Var(varId)); |
|
| 2081 | + | // Complete each parameter that was created before sealing. |
|
| 2082 | + | for varId, paramIdx in paramVars { |
|
| 2083 | + | try resolveBlockArgs(self, block, Var(varId), paramIdx); |
|
| 2082 | 2084 | } |
|
| 2083 | 2085 | } |
|
| 2084 | 2086 | ||
| 2085 | 2087 | /// Seal a block and switch to it. |
|
| 2086 | 2088 | fn switchToAndSeal(self: *mut FnLowerer, block: BlockId) throws (LowerError) { |
| 2713 | 2715 | // |
|
| 2714 | 2716 | // 2. **Sealed block with single predecessor**: If all incoming edges are known |
|
| 2715 | 2717 | // and there's exactly one predecessor, recurse to that predecessor. No merge |
|
| 2716 | 2718 | // is needed since there's only one path. The result is cached. |
|
| 2717 | 2719 | // |
|
| 2718 | - | // 3. **Multiple predecessors**: Create a block parameter to receive the merged |
|
| 2719 | - | // value. If the block is sealed, immediately look up each predecessor's value |
|
| 2720 | - | // and patch their terminators via [`resolveBlockArgs`]. If unsealed, defer by |
|
| 2721 | - | // recording the variable in `incompleteVars`; when [`sealBlock`] is called, |
|
| 2722 | - | // all incomplete block params are resolved at that point. |
|
| 2720 | + | // 3. **Unsealed block or multiple predecessors**: Create a block parameter to |
|
| 2721 | + | // receive the merged value. If sealed, look up each predecessor's value and |
|
| 2722 | + | // patch its terminator via [`resolveBlockArgs`]. If unsealed, `paramVars` |
|
| 2723 | + | // records the variable in parameter order. [`sealBlock`] resolves these |
|
| 2724 | + | // parameters after all incoming edges are known. |
|
| 2723 | 2725 | // |
|
| 2724 | 2726 | // Consider this code: |
|
| 2725 | 2727 | // |
|
| 2726 | 2728 | // let mut x = 1; |
|
| 2727 | 2729 | // if cond { |
| 2877 | 2879 | } |
|
| 2878 | 2880 | ||
| 2879 | 2881 | /// Create a block parameter to merge a variable's value from multiple |
|
| 2880 | 2882 | /// control flow paths. |
|
| 2881 | 2883 | /// |
|
| 2882 | - | /// Called when [`useVarInBlock`] can't find a local definition and the block has |
|
| 2883 | - | /// multiple predecessors. For example, when `x` is used in `@end` but defined |
|
| 2884 | - | /// differently in `@then` and `@else`: |
|
| 2884 | + | /// Called when [`useVarInBlock`] cannot find a local definition and the block is |
|
| 2885 | + | /// unsealed or has multiple predecessors. For example, `x` can be used in `@end` |
|
| 2886 | + | /// but defined differently in `@then` and `@else`: |
|
| 2885 | 2887 | /// |
|
| 2886 | 2888 | /// @then |
|
| 2887 | 2889 | /// jmp @end(1); // x = 1 |
|
| 2888 | 2890 | /// @else |
|
| 2889 | 2891 | /// jmp @end(2); // x = 2 |
|
| 2890 | 2892 | /// @end(w32 %1) // x = %1, merged from predecessors |
|
| 2891 | 2893 | /// ret %1; |
|
| 2892 | 2894 | /// |
|
| 2893 | - | /// This function creates a fresh register `%1` as a block parameter, then patches |
|
| 2894 | - | /// each predecessor's jump to pass its value of `x` as an argument. |
|
| 2895 | + | /// Create a register `%1` as a block parameter. In a sealed block, patch each |
|
| 2896 | + | /// predecessor's jump to pass its value of `x`. Otherwise, defer until sealing. |
|
| 2895 | 2897 | fn createBlockParam(self: *mut FnLowerer, block: BlockId, v: Var) -> il::Val throws (LowerError) { |
|
| 2896 | 2898 | // Entry block must not have block parameters. |
|
| 2897 | 2899 | assert block <> self.entryBlock, "createBlockParam: entry block must not have block parameters"; |
|
| 2898 | 2900 | // Allocate a register to hold the merged value. |
|
| 2899 | 2901 | let reg = nextReg(self); |
|
| 2900 | 2902 | let type = getVar(self, v).type; |
|
| 2901 | 2903 | ||
| 2902 | 2904 | // Create block parameter and add it to the block. |
|
| 2903 | 2905 | let param = il::Param { value: reg, type }; |
|
| 2904 | 2906 | let blk = getBlockMut(self, block); |
|
| 2907 | + | let paramIdx = blk.paramVars.len; |
|
| 2905 | 2908 | blk.params.append(param, self.allocator); |
|
| 2906 | 2909 | blk.paramVars.append(*v, self.allocator); // Associate variable with parameter. |
|
| 2907 | 2910 | ||
| 2908 | 2911 | // Record that this variable's value in this block is now the parameter register. |
|
| 2909 | 2912 | // This must happen before the predecessor loop to handle self-referential loops. |
|
| 2910 | 2913 | set blk.vars[*v] = il::Val::Reg(reg); |
|
| 2911 | 2914 | ||
| 2912 | - | match &mut blk.sealState { |
|
| 2913 | - | case Sealed::No { incompleteVars } => { |
|
| 2914 | - | // Block unsealed: defer until sealing. |
|
| 2915 | - | incompleteVars.append(*v, self.allocator); |
|
| 2916 | - | }, |
|
| 2917 | - | case Sealed::Yes => { |
|
| 2918 | - | // Block sealed: check for trivial phi before committing. If all |
|
| 2919 | - | // predecessors provide the same value, we can remove the param we |
|
| 2920 | - | // just created and use that value directly. |
|
| 2921 | - | if let trivial = try getTrivialPhiVal(self, block, v) { |
|
| 2922 | - | let provisional = il::Val::Reg(reg); |
|
| 2923 | - | removeLastBlockParam(self, block); |
|
| 2924 | - | rewriteCachedVarValue(self, v, provisional, trivial); |
|
| 2925 | - | set getBlockMut(self, block).vars[*v] = trivial; |
|
| 2926 | - | return trivial; |
|
| 2927 | - | } |
|
| 2928 | - | // Non-trivial phi: patch predecessors to pass their values. |
|
| 2929 | - | try resolveBlockArgs(self, block, v); |
|
| 2930 | - | }, |
|
| 2915 | + | if blk.sealState == Sealed::Yes { |
|
| 2916 | + | // Block sealed: check for trivial phi before committing. If all |
|
| 2917 | + | // predecessors provide the same value, we can remove the param we |
|
| 2918 | + | // just created and use that value directly. |
|
| 2919 | + | if let trivial = try getTrivialPhiVal(self, block, v) { |
|
| 2920 | + | let provisional = il::Val::Reg(reg); |
|
| 2921 | + | removeLastBlockParam(self, block); |
|
| 2922 | + | rewriteCachedVarValue(self, v, provisional, trivial); |
|
| 2923 | + | set getBlockMut(self, block).vars[*v] = trivial; |
|
| 2924 | + | return trivial; |
|
| 2925 | + | } |
|
| 2926 | + | // Non-trivial phi: patch predecessors to pass their values. |
|
| 2927 | + | try resolveBlockArgs(self, block, v, paramIdx); |
|
| 2931 | 2928 | } |
|
| 2932 | 2929 | return il::Val::Reg(reg); |
|
| 2933 | 2930 | } |
|
| 2934 | 2931 | ||
| 2935 | - | /// Complete a block parameter by looking up the variable's value in all |
|
| 2936 | - | /// predecessors and patching their terminator instructions with edge arguments. |
|
| 2932 | + | /// Complete the block parameter at `paramIdx`. Look up the variable's value in |
|
| 2933 | + | /// each predecessor and patch its terminator with the edge argument. |
|
| 2937 | 2934 | /// |
|
| 2938 | 2935 | /// This is the block-parameter equivalent of adding operands to a phi-function in |
|
| 2939 | 2936 | /// traditional SSA. Where a phi-function merges values at the join point: |
|
| 2940 | 2937 | /// |
|
| 2941 | 2938 | /// x3 = phi(x1, x2) |
|
| 2942 | 2939 | /// |
|
| 2943 | 2940 | /// This representation avoids the need for phi nodes to reference their |
|
| 2944 | 2941 | /// predecessor blocks explicitly, since the control flow edges already encode |
|
| 2945 | 2942 | /// that information. |
|
| 2946 | - | fn resolveBlockArgs(self: *mut FnLowerer, block: BlockId, v: Var) throws (LowerError) { |
|
| 2943 | + | fn resolveBlockArgs(self: *mut FnLowerer, block: BlockId, v: Var, paramIdx: u32) throws (LowerError) { |
|
| 2947 | 2944 | let blk = getBlock(self, block); |
|
| 2948 | 2945 | ||
| 2949 | - | // Find the parameter index corresponding to this variable. |
|
| 2950 | - | // Each variable that needs merging gets its own block parameter slot. |
|
| 2951 | - | let mut paramIdx: u32 = 0; |
|
| 2952 | - | for i in 0..blk.paramVars.len { |
|
| 2953 | - | if blk.paramVars[i] == *v { |
|
| 2954 | - | set paramIdx = i; |
|
| 2955 | - | break; |
|
| 2956 | - | } |
|
| 2957 | - | } |
|
| 2958 | - | ||
| 2959 | 2946 | // For each predecessor, recursively look up the variable's reaching definition |
|
| 2960 | 2947 | // in that block, then patch the predecessor's terminator to pass that value |
|
| 2961 | 2948 | // as an argument to this block's parameter. |
|
| 2962 | 2949 | for predId in blk.preds { |
|
| 2963 | 2950 | let pred = BlockId(predId); |