cubecl_opt/
phi_frontiers.rs

1use cubecl_ir::{Id, Type, Variable, VariableKind};
2use petgraph::graph::NodeIndex;
3
4use crate::{
5    Optimizer,
6    analyses::{dominance::DomFrontiers, liveness::Liveness, writes::Writes},
7};
8
9use super::version::{PhiEntry, PhiInstruction};
10
11impl Optimizer {
12    /// Places a phi node for each live variable at each frontier
13    pub fn place_phi_nodes(&mut self) {
14        let keys: Vec<_> = self.program.variables.keys().cloned().collect();
15        let writes = self.analysis::<Writes>();
16        let liveness = self.analysis::<Liveness>();
17        let dom_frontiers = self.analysis::<DomFrontiers>();
18
19        for var in keys {
20            let mut workset: Vec<_> = self
21                .node_ids()
22                .iter()
23                .filter(|index| writes[*index].contains(&var))
24                .copied()
25                .collect();
26            let mut considered = workset.clone();
27            let mut already_inserted = Vec::new();
28
29            while let Some(node) = workset.pop() {
30                for frontier in dom_frontiers[&node].clone() {
31                    if already_inserted.contains(&frontier) || liveness.is_dead(frontier, var) {
32                        continue;
33                    }
34                    self.insert_phi(frontier, var, self.program.variables[&var]);
35                    already_inserted.push(frontier);
36                    if !considered.contains(&frontier) {
37                        workset.push(frontier);
38                        considered.push(frontier);
39                    }
40                }
41            }
42        }
43    }
44
45    /// Insert a phi node for variable `id` at `block`
46    pub fn insert_phi(&mut self, block: NodeIndex, id: Id, item: Type) {
47        let var = Variable::new(VariableKind::Versioned { id, version: 0 }, item);
48        let entries = self.predecessors(block).into_iter().map(|pred| PhiEntry {
49            block: pred,
50            value: var,
51        });
52        let phi = PhiInstruction {
53            out: var,
54            entries: entries.collect(),
55        };
56        self.program[block].phi_nodes.borrow_mut().push(phi);
57    }
58}
cubecl_opt/phi_frontiers.rs

cubecl_opt/
phi_frontiers.rs
