solar_codegen/analysis/
phi_elimination.rs

1//! Phi elimination for MIR.
2//!
3//! Converts SSA phi nodes into parallel copies inserted at predecessor block exits.
4//! This is necessary because the EVM cannot directly execute phi nodes.
5//!
6//! The algorithm:
7//! 1. For each phi node in block B with incoming value V from predecessor P, insert a copy from V
8//!    to the phi's destination at the end of P.
9//! 2. Handle cycles by detecting when copies form a cycle and using a temporary.
10//! 3. Remove the phi instructions after copies are inserted.
11
12use crate::mir::{BlockId, Function, InstId, InstKind, MirType, Value, ValueId};
13use solar_data_structures::map::FxHashMap;
14
15/// Source for a parallel copy - either a regular value or a temporary.
16#[derive(Clone, Debug, PartialEq, Eq)]
17pub enum CopySource {
18    /// A regular MIR value.
19    Value(ValueId),
20    /// A temporary created during cycle breaking (identified by index).
21    Temp(u32),
22}
23
24/// Destination for a parallel copy - either a regular value or a temporary.
25#[derive(Clone, Debug, PartialEq, Eq)]
26pub enum CopyDest {
27    /// A regular MIR value.
28    Value(ValueId),
29    /// A temporary created during cycle breaking (identified by index).
30    Temp(u32),
31}
32
33/// A parallel copy operation: copy from source to destination.
34#[derive(Clone, Debug, PartialEq, Eq)]
35pub struct ParallelCopy {
36    /// Source value to copy from.
37    pub src: CopySource,
38    /// Destination value (the phi result).
39    pub dst: CopyDest,
40    /// Type of the copy.
41    pub ty: MirType,
42}
43
44/// Copies to insert at the end of a block (before the terminator).
45#[derive(Clone, Debug, Default)]
46pub struct BlockCopies {
47    /// Parallel copies to execute at this block's exit.
48    pub copies: Vec<ParallelCopy>,
49}
50
51/// Result of phi elimination.
52#[derive(Debug)]
53pub struct PhiEliminationResult {
54    /// Copies to insert at each predecessor block.
55    pub block_copies: FxHashMap<BlockId, BlockCopies>,
56    /// Phi instructions to remove (block, instruction index).
57    pub phis_to_remove: Vec<(BlockId, usize)>,
58}
59
60/// Phi elimination query.
61pub struct PhiEliminator;
62
63impl PhiEliminator {
64    /// Analyzes phi nodes and returns parallel copies to insert at predecessor exits.
65    ///
66    /// The caller is responsible for modifying the function.
67    #[must_use]
68    pub fn analyze(func: &Function) -> PhiEliminationResult {
69        let mut block_copies: FxHashMap<BlockId, BlockCopies> = FxHashMap::default();
70        let mut phis_to_remove = Vec::new();
71
72        // Process each block looking for phi instructions
73        for (block_id, block) in func.blocks.iter_enumerated() {
74            for (inst_idx, &inst_id) in block.instructions.iter().enumerate() {
75                let inst = func.instruction(inst_id);
76
77                if let InstKind::Phi(incoming) = &inst.kind {
78                    // Find the value defined by this phi
79                    let phi_dst = find_phi_dst(func, inst_id);
80
81                    if let Some(dst) = phi_dst {
82                        let ty = func.value(dst).ty();
83
84                        // For each predecessor, insert a copy
85                        for &(pred_block, src_val) in incoming {
86                            block_copies.entry(pred_block).or_default().copies.push(ParallelCopy {
87                                src: CopySource::Value(src_val),
88                                dst: CopyDest::Value(dst),
89                                ty,
90                            });
91                        }
92
93                        phis_to_remove.push((block_id, inst_idx));
94                    }
95                }
96            }
97        }
98
99        // Sequentialize parallel copies to handle cycles
100        let mut temp_counter = 0u32;
101        for copies in block_copies.values_mut() {
102            sequentialize_copies(&mut copies.copies, &mut temp_counter);
103        }
104
105        PhiEliminationResult { block_copies, phis_to_remove }
106    }
107}
108
109/// Eliminates phi nodes by inserting parallel copies at predecessor block exits.
110///
111/// Returns the copies to insert and phis to remove. The caller is responsible
112/// for actually modifying the function.
113#[must_use]
114pub fn eliminate_phis(func: &Function) -> PhiEliminationResult {
115    PhiEliminator::analyze(func)
116}
117
118/// Finds the ValueId that is defined by a phi instruction.
119fn find_phi_dst(func: &Function, inst_id: InstId) -> Option<ValueId> {
120    for (val_id, val) in func.values.iter_enumerated() {
121        if let Value::Inst(def_inst) = val
122            && *def_inst == inst_id
123        {
124            return Some(val_id);
125        }
126    }
127    None
128}
129
130/// Helper to extract ValueId from CopySource if it's a value (not a temp).
131fn src_value(src: &CopySource) -> Option<ValueId> {
132    match src {
133        CopySource::Value(v) => Some(*v),
134        CopySource::Temp(_) => None,
135    }
136}
137
138/// Helper to extract ValueId from CopyDest if it's a value (not a temp).
139fn dst_value(dst: &CopyDest) -> Option<ValueId> {
140    match dst {
141        CopyDest::Value(v) => Some(*v),
142        CopyDest::Temp(_) => None,
143    }
144}
145
146/// Sequentializes parallel copies to handle dependencies and cycles.
147///
148/// A chain like: a = b, c = a needs to be ordered as: c = a, a = b
149/// (read from a before writing to a)
150///
151/// A cycle like: a = b, b = a needs a temporary: tmp = a, a = b, b = tmp
152///
153/// Uses the algorithm from "Practical Improvements to the Construction and
154/// Destruction of Static Single Assignment Form" by Briggs et al.
155fn sequentialize_copies(copies: &mut Vec<ParallelCopy>, temp_counter: &mut u32) {
156    if copies.len() <= 1 {
157        return;
158    }
159
160    // Build the copy graph
161    let pending: Vec<ParallelCopy> = std::mem::take(copies);
162    let mut result: Vec<ParallelCopy> = Vec::with_capacity(pending.len() + 2);
163
164    // Map from value to index of copy that writes to it
165    let mut writes_to: FxHashMap<ValueId, usize> = FxHashMap::default();
166    for (i, copy) in pending.iter().enumerate() {
167        if let Some(dst) = dst_value(&copy.dst) {
168            writes_to.insert(dst, i);
169        }
170    }
171
172    // For each copy, count how many other copies need to read its destination
173    // before we can safely write to it
174    let mut blocked_by: Vec<usize> = vec![0; pending.len()];
175    for (i, copy) in pending.iter().enumerate() {
176        if let Some(src) = src_value(&copy.src)
177            && let Some(&writer_idx) = writes_to.get(&src)
178            && writer_idx != i
179        {
180            blocked_by[writer_idx] += 1;
181        }
182    }
183
184    let mut emitted = vec![false; pending.len()];
185
186    // Emit copies in dependency order until we hit cycles
187    loop {
188        let mut made_progress = false;
189
190        for i in 0..pending.len() {
191            if emitted[i] {
192                continue;
193            }
194
195            // Can emit if no one is blocking us (all readers of our dst have been emitted)
196            if blocked_by[i] == 0 {
197                result.push(pending[i].clone());
198                emitted[i] = true;
199                made_progress = true;
200
201                // Unblock anyone who was waiting for us to read their dst
202                if let Some(src) = src_value(&pending[i].src)
203                    && let Some(&blocked_writer) = writes_to.get(&src)
204                    && blocked_writer != i
205                    && !emitted[blocked_writer]
206                {
207                    blocked_by[blocked_writer] = blocked_by[blocked_writer].saturating_sub(1);
208                }
209            }
210        }
211
212        if !made_progress {
213            // All remaining copies form cycles - break one cycle at a time
214            break_cycles(
215                &pending,
216                &mut emitted,
217                &mut blocked_by,
218                &writes_to,
219                &mut result,
220                temp_counter,
221            );
222
223            // If we broke at least one cycle, continue to see if more copies are now unblocked
224            if !emitted.iter().all(|&e| e) {
225                continue;
226            }
227            break;
228        }
229
230        if emitted.iter().all(|&e| e) {
231            break;
232        }
233    }
234
235    *copies = result;
236}
237
238/// Breaks cycles in the remaining copies by inserting a temporary.
239///
240/// For a cycle a -> b -> a, we:
241/// 1. Pick one copy in the cycle (say b = a)
242/// 2. Save its source to a temporary: tmp = a
243/// 3. Emit all copies in the cycle normally: a = b
244/// 4. Replace the broken copy's source with temp: b = tmp
245fn break_cycles(
246    pending: &[ParallelCopy],
247    emitted: &mut [bool],
248    blocked_by: &mut [usize],
249    writes_to: &FxHashMap<ValueId, usize>,
250    result: &mut Vec<ParallelCopy>,
251    temp_counter: &mut u32,
252) {
253    // Find a copy that's part of a cycle (not emitted and blocking > 0)
254    let cycle_start = pending
255        .iter()
256        .enumerate()
257        .find(|(i, _)| !emitted[*i] && blocked_by[*i] > 0)
258        .map(|(i, _)| i);
259
260    let Some(start_idx) = cycle_start else {
261        // No cycles, emit remaining in order
262        for (i, copy) in pending.iter().enumerate() {
263            if !emitted[i] {
264                result.push(copy.clone());
265                emitted[i] = true;
266            }
267        }
268        return;
269    };
270
271    // Trace the cycle to find all participants
272    let mut cycle_indices = vec![start_idx];
273    let mut current = start_idx;
274
275    while let Some(src) = src_value(&pending[current].src) {
276        // Find the copy that writes to our source (the predecessor in the cycle)
277        if let Some(&pred_idx) = writes_to.get(&src) {
278            if emitted[pred_idx] {
279                break;
280            }
281            if pred_idx == start_idx {
282                // We've completed the cycle
283                break;
284            }
285            if cycle_indices.contains(&pred_idx) {
286                // Hit part of the cycle we've already seen
287                break;
288            }
289            cycle_indices.push(pred_idx);
290            current = pred_idx;
291        } else {
292            // Not a true cycle (shouldn't happen if blocked_by > 0)
293            break;
294        }
295    }
296
297    // Pick the first copy in the cycle to break
298    let break_idx = cycle_indices[0];
299    let break_copy = &pending[break_idx];
300
301    // Allocate a temporary ID
302    let temp_id = *temp_counter;
303    *temp_counter += 1;
304
305    // Step 1: Save the source to temporary
306    result.push(ParallelCopy {
307        src: break_copy.src.clone(),
308        dst: CopyDest::Temp(temp_id),
309        ty: break_copy.ty,
310    });
311
312    // Step 2: Emit all other copies in the cycle (they can now proceed)
313    // The copy at break_idx is blocked, so unblock its writer
314    if let Some(src) = src_value(&break_copy.src)
315        && let Some(&blocked_writer) = writes_to.get(&src)
316        && blocked_writer != break_idx
317    {
318        blocked_by[blocked_writer] = blocked_by[blocked_writer].saturating_sub(1);
319    }
320
321    // Emit copies that are now unblocked (in the cycle)
322    for &idx in &cycle_indices[1..] {
323        if !emitted[idx] && blocked_by[idx] == 0 {
324            result.push(pending[idx].clone());
325            emitted[idx] = true;
326
327            // Unblock the writer of our source
328            if let Some(src) = src_value(&pending[idx].src)
329                && let Some(&blocked_writer) = writes_to.get(&src)
330                && !emitted[blocked_writer]
331            {
332                blocked_by[blocked_writer] = blocked_by[blocked_writer].saturating_sub(1);
333            }
334        }
335    }
336
337    // Step 3: Emit the broken copy with temp as source
338    result.push(ParallelCopy {
339        src: CopySource::Temp(temp_id),
340        dst: break_copy.dst.clone(),
341        ty: break_copy.ty,
342    });
343    emitted[break_idx] = true;
344}
345
346#[cfg(test)]
347mod tests {
348    use super::*;
349
350    fn copy(src: usize, dst: usize) -> ParallelCopy {
351        ParallelCopy {
352            src: CopySource::Value(ValueId::from_usize(src)),
353            dst: CopyDest::Value(ValueId::from_usize(dst)),
354            ty: MirType::uint256(),
355        }
356    }
357
358    fn has_temp(copies: &[ParallelCopy]) -> bool {
359        copies.iter().any(|c| matches!(c.src, CopySource::Temp(_)))
360            || copies.iter().any(|c| matches!(c.dst, CopyDest::Temp(_)))
361    }
362
363    #[test]
364    fn test_no_cycle() {
365        let mut copies = vec![copy(0, 1), copy(2, 3)];
366        let mut temp_counter = 0;
367        sequentialize_copies(&mut copies, &mut temp_counter);
368        assert_eq!(copies.len(), 2);
369        assert!(!has_temp(&copies));
370    }
371
372    #[test]
373    fn test_chain() {
374        // a = b, c = a -> should read from 'a' before writing to 'a'
375        let mut copies = vec![copy(1, 0), copy(0, 2)];
376        let mut temp_counter = 0;
377        sequentialize_copies(&mut copies, &mut temp_counter);
378
379        // Find the positions
380        let write_to_a_idx =
381            copies.iter().position(|c| matches!(c.dst, CopyDest::Value(v) if v.index() == 0));
382        let read_from_a_idx =
383            copies.iter().position(|c| matches!(c.src, CopySource::Value(v) if v.index() == 0));
384        assert!(read_from_a_idx.unwrap() < write_to_a_idx.unwrap());
385    }
386
387    #[test]
388    fn test_simple_cycle() {
389        // a = b, b = a (swap) requires a temporary
390        let mut copies = vec![copy(1, 0), copy(0, 1)];
391        let mut temp_counter = 0;
392        sequentialize_copies(&mut copies, &mut temp_counter);
393
394        // Should have extra copies for the temporary
395        // Expected: tmp = a, a = b, b = tmp  OR  tmp = b, b = a, a = tmp
396        assert!(copies.len() >= 3, "Cycle should introduce temporary copies");
397        assert!(has_temp(&copies), "Should use temporaries for cycles");
398        assert!(temp_counter >= 1, "Should allocate at least one temp");
399    }
400
401    #[test]
402    fn test_three_way_cycle() {
403        // a = b, b = c, c = a (rotate) requires a temporary
404        let mut copies = vec![copy(1, 0), copy(2, 1), copy(0, 2)];
405        let mut temp_counter = 0;
406        sequentialize_copies(&mut copies, &mut temp_counter);
407
408        // Should handle the 3-way rotation
409        assert!(copies.len() >= 4, "3-way cycle should introduce temporary copies");
410        assert!(has_temp(&copies), "Should use temporaries for cycles");
411    }
412
413    #[test]
414    fn test_independent_copies() {
415        // Completely independent copies: a = x, b = y, c = z
416        let mut copies = vec![copy(10, 0), copy(11, 1), copy(12, 2)];
417        let mut temp_counter = 0;
418        sequentialize_copies(&mut copies, &mut temp_counter);
419
420        // Should remain as 3 copies with no temporaries
421        assert_eq!(copies.len(), 3);
422        assert!(!has_temp(&copies));
423    }
424}
solar_codegen/analysis/phi_elimination.rs

solar_codegen/analysis/
phi_elimination.rs
