compiler: Check recursive SSA resolution
df26efaaa9fd5b5597438eb0fee9a72aae6e9db53e1f5daf301772952344d5da
1 parent
50f94c5d
lib/std/lang/lower.rad
+14 -8
| 2221 | 2221 | /// Seal a block, indicating all predecessor edges are now known. |
|
| 2222 | 2222 | /// |
|
| 2223 | 2223 | /// Sealing enables SSA construction to resolve variable uses by looking up |
|
| 2224 | 2224 | /// values from predecessors and inserting block parameters as needed. It |
|
| 2225 | 2225 | /// does not prevent instructions from being added to the block. |
|
| 2226 | - | unsafe fn sealBlock 'arena 'phase 'function (self: &mut FnLowerer 'arena 'phase 'function, block: BlockId) throws (LowerError) where 'arena: 'phase, 'phase: 'function { |
|
| 2226 | + | fn sealBlock 'arena 'phase 'function (self: &mut FnLowerer 'arena 'phase 'function, block: BlockId) throws (LowerError) where 'arena: 'phase, 'phase: 'function { |
|
| 2227 | 2227 | let paramCount = markBlockSealed(&mut self.blockData[*block]) else return; |
|
| 2228 | 2228 | ||
| 2229 | 2229 | // Complete each parameter that was created before sealing. |
|
| 2230 | 2230 | for paramIdx in 0..paramCount { |
|
| 2231 | 2231 | let varId = self.blockData[*block].paramVars[paramIdx]; |
| 2243 | 2243 | set block.sealState = Sealed::Yes; |
|
| 2244 | 2244 | return paramCount; |
|
| 2245 | 2245 | } |
|
| 2246 | 2246 | ||
| 2247 | 2247 | /// Seal a block and switch to it. |
|
| 2248 | - | unsafe fn switchToAndSeal 'arena 'phase 'function (self: &mut FnLowerer 'arena 'phase 'function, block: BlockId) throws (LowerError) where 'arena: 'phase, 'phase: 'function { |
|
| 2248 | + | fn switchToAndSeal 'arena 'phase 'function (self: &mut FnLowerer 'arena 'phase 'function, block: BlockId) throws (LowerError) where 'arena: 'phase, 'phase: 'function { |
|
| 2249 | 2249 | try sealBlock(self, block); |
|
| 2250 | 2250 | switchToBlock(self, block); |
|
| 2251 | 2251 | } |
|
| 2252 | 2252 | ||
| 2253 | 2253 | /// Get the number of predecessors for a block. |
| 2997 | 2997 | set self.blockData[*block].vars[*v] = val; |
|
| 2998 | 2998 | } |
|
| 2999 | 2999 | ||
| 3000 | 3000 | /// Use (read) the current value of a variable in the current block. |
|
| 3001 | 3001 | /// May insert block parameters if the value must come from predecessors. |
|
| 3002 | - | unsafe fn useVar 'arena 'phase 'function (self: &mut FnLowerer 'arena 'phase 'function, v: Var) -> il::Val throws (LowerError) where 'arena: 'phase, 'phase: 'function { |
|
| 3002 | + | fn useVar 'arena 'phase 'function (self: &mut FnLowerer 'arena 'phase 'function, v: Var) -> il::Val throws (LowerError) where 'arena: 'phase, 'phase: 'function { |
|
| 3003 | 3003 | return try useVarInBlock(self, currentBlock(self), v); |
|
| 3004 | 3004 | } |
|
| 3005 | 3005 | ||
| 3006 | 3006 | /// Resolve which SSA definition of a variable reaches a use point in a given block. |
|
| 3007 | 3007 | /// |
|
| 3008 | 3008 | /// Given a variable and a block where it's used, this function finds the |
|
| 3009 | 3009 | /// correct [`il::Val`] that holds the variable's value at that program point. |
|
| 3010 | 3010 | /// When control flow merges from multiple predecessors with different |
|
| 3011 | 3011 | /// definitions, it creates a block parameter to unify them. |
|
| 3012 | - | 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 { |
|
| 3012 | + | fn useVarInBlock 'arena 'phase 'function (self: &mut FnLowerer 'arena 'phase 'function, block: BlockId, v: Var) -> il::Val throws (LowerError) where 'arena: 'phase, 'phase: 'function { |
|
| 3013 | 3013 | assert *v < self.vars.len; |
|
| 3014 | 3014 | ||
| 3015 | 3015 | match varSource(&self.blockData[..], block, self.entryBlock, v) { |
|
| 3016 | 3016 | case VarSource::Value(val) => return val, |
|
| 3017 | 3017 | case VarSource::Predecessor(pred) => { |
|
| 3018 | 3018 | let val = try useVarInBlock(self, pred, v); |
|
| 3019 | 3019 | set self.blockData[*block].vars[*v] = val; // Cache. |
|
| 3020 | 3020 | return val; |
|
| 3021 | 3021 | } |
|
| 3022 | - | case VarSource::Merge => return try createBlockParam(self, block, v), |
|
| 3022 | + | case VarSource::Merge => { |
|
| 3023 | + | unsafe { |
|
| 3024 | + | return try createBlockParam(self, block, v); |
|
| 3025 | + | } |
|
| 3026 | + | }, |
|
| 3023 | 3027 | case VarSource::Invalid => throw LowerError::InvalidUse, |
|
| 3024 | 3028 | } |
|
| 3025 | 3029 | } |
|
| 3026 | 3030 | ||
| 3027 | 3031 | /// Select the cached, predecessor, or merge source while borrowing block state. |
| 3161 | 3165 | /// x3 = phi(x1, x2) |
|
| 3162 | 3166 | /// |
|
| 3163 | 3167 | /// This representation avoids the need for phi nodes to reference their |
|
| 3164 | 3168 | /// predecessor blocks explicitly, since the control flow edges already encode |
|
| 3165 | 3169 | /// that information. |
|
| 3166 | - | unsafe fn resolveBlockArgs 'arena 'phase 'function (self: &mut FnLowerer 'arena 'phase 'function, block: BlockId, v: Var, paramIdx: u32) throws (LowerError) where 'arena: 'phase, 'phase: 'function { |
|
| 3170 | + | fn resolveBlockArgs 'arena 'phase 'function (self: &mut FnLowerer 'arena 'phase 'function, block: BlockId, v: Var, paramIdx: u32) throws (LowerError) where 'arena: 'phase, 'phase: 'function { |
|
| 3167 | 3171 | let count = predecessorCount(&self.blockData[..], block); |
|
| 3168 | 3172 | ||
| 3169 | 3173 | // For each predecessor, recursively look up the variable's reaching definition |
|
| 3170 | 3174 | // in that block, then patch the predecessor's terminator to pass that value |
|
| 3171 | 3175 | // as an argument to this block's parameter. |
| 3173 | 3177 | let pred = BlockId(self.blockData[*block].preds[index]); |
|
| 3174 | 3178 | // This may recursively trigger more block arg resolution if the |
|
| 3175 | 3179 | // predecessor also needs to look up the variable from its predecessors. |
|
| 3176 | 3180 | let val = try useVarInBlock(self, pred, v); |
|
| 3177 | 3181 | assert val <> il::Val::Undef, "createBlockParam: predecessor provides undef value for block parameter"; |
|
| 3178 | - | patchTerminatorArg(self, pred, *block, paramIdx, val); |
|
| 3182 | + | unsafe { |
|
| 3183 | + | patchTerminatorArg(self, pred, *block, paramIdx, val); |
|
| 3184 | + | } |
|
| 3179 | 3185 | } |
|
| 3180 | 3186 | } |
|
| 3181 | 3187 | ||
| 3182 | 3188 | /// Check if a block parameter is trivial, i.e. all predecessors provide |
|
| 3183 | 3189 | /// the same value. Returns the trivial value if so. |
|
| 3184 | - | unsafe fn getTrivialPhiVal 'arena 'phase 'function (self: &mut FnLowerer 'arena 'phase 'function, block: BlockId, v: Var) -> ?il::Val throws (LowerError) where 'arena: 'phase, 'phase: 'function { |
|
| 3190 | + | fn getTrivialPhiVal 'arena 'phase 'function (self: &mut FnLowerer 'arena 'phase 'function, block: BlockId, v: Var) -> ?il::Val throws (LowerError) where 'arena: 'phase, 'phase: 'function { |
|
| 3185 | 3191 | let count = predecessorCount(&self.blockData[..], block); |
|
| 3186 | 3192 | // Get the block parameter register. |
|
| 3187 | 3193 | let paramReg = self.blockData[*block].vars[*v]; |
|
| 3188 | 3194 | // Check if all predecessors provide the same value. |
|
| 3189 | 3195 | let mut sameVal: ?il::Val = nil; |