wave_compiler/mir/
basic_block.rs

1// Copyright 2026 Ojima Abraham
2// SPDX-License-Identifier: Apache-2.0
3
4//! Basic blocks with terminators for MIR control flow graphs.
5//!
6//! A basic block is a straight-line sequence of instructions ending
7//! with a terminator that transfers control to one or more successor blocks.
8
9use super::instruction::MirInst;
10use super::value::{BlockId, ValueId};
11use crate::mir::types::MirType;
12
13/// Phi node at a block join point, merging values from different predecessors.
14#[derive(Debug, Clone, PartialEq)]
15pub struct PhiNode {
16    /// Destination value.
17    pub dest: ValueId,
18    /// Type of the phi value.
19    pub ty: MirType,
20    /// Incoming values from predecessor blocks.
21    pub incoming: Vec<(BlockId, ValueId)>,
22}
23
24/// Block terminator transferring control to successor blocks.
25#[derive(Debug, Clone, PartialEq)]
26pub enum Terminator {
27    /// Unconditional branch.
28    Branch {
29        /// Target block.
30        target: BlockId,
31    },
32    /// Conditional branch.
33    CondBranch {
34        /// Condition (must be Bool type).
35        cond: ValueId,
36        /// Target if condition is true.
37        true_target: BlockId,
38        /// Target if condition is false.
39        false_target: BlockId,
40    },
41    /// Return from kernel.
42    Return,
43}
44
45impl Terminator {
46    /// Returns all successor block IDs.
47    #[must_use]
48    pub fn successors(&self) -> Vec<BlockId> {
49        match self {
50            Self::Branch { target } => vec![*target],
51            Self::CondBranch {
52                true_target,
53                false_target,
54                ..
55            } => vec![*true_target, *false_target],
56            Self::Return => vec![],
57        }
58    }
59
60    /// Returns all value IDs used by this terminator.
61    #[must_use]
62    pub fn operands(&self) -> Vec<ValueId> {
63        match self {
64            Self::Branch { .. } | Self::Return => vec![],
65            Self::CondBranch { cond, .. } => vec![*cond],
66        }
67    }
68}
69
70/// A basic block in the MIR control flow graph.
71#[derive(Debug, Clone, PartialEq)]
72pub struct BasicBlock {
73    /// Unique block identifier.
74    pub id: BlockId,
75    /// Phi nodes at the start of this block.
76    pub phis: Vec<PhiNode>,
77    /// Instructions in this block.
78    pub instructions: Vec<MirInst>,
79    /// Block terminator.
80    pub terminator: Terminator,
81}
82
83impl BasicBlock {
84    /// Create a new empty basic block.
85    #[must_use]
86    pub fn new(id: BlockId) -> Self {
87        Self {
88            id,
89            phis: Vec::new(),
90            instructions: Vec::new(),
91            terminator: Terminator::Return,
92        }
93    }
94
95    /// Returns all successor block IDs.
96    #[must_use]
97    pub fn successors(&self) -> Vec<BlockId> {
98        self.terminator.successors()
99    }
100
101    /// Returns all value IDs defined in this block (phi dests + instruction dests).
102    #[must_use]
103    pub fn defs(&self) -> Vec<ValueId> {
104        let mut defs: Vec<ValueId> = self.phis.iter().map(|phi| phi.dest).collect();
105        for inst in &self.instructions {
106            if let Some(dest) = inst.dest() {
107                defs.push(dest);
108            }
109        }
110        defs
111    }
112
113    /// Returns all value IDs used in this block.
114    #[must_use]
115    pub fn uses(&self) -> Vec<ValueId> {
116        let mut uses = Vec::new();
117        for phi in &self.phis {
118            for (_, val) in &phi.incoming {
119                uses.push(*val);
120            }
121        }
122        for inst in &self.instructions {
123            uses.extend(inst.operands());
124        }
125        uses.extend(self.terminator.operands());
126        uses
127    }
128}
129
130#[cfg(test)]
131mod tests {
132    use super::*;
133    use crate::hir::expr::BinOp;
134    use crate::mir::types::MirType;
135
136    #[test]
137    fn test_basic_block_successors() {
138        let mut bb = BasicBlock::new(BlockId(0));
139        bb.terminator = Terminator::CondBranch {
140            cond: ValueId(0),
141            true_target: BlockId(1),
142            false_target: BlockId(2),
143        };
144        let succs = bb.successors();
145        assert_eq!(succs, vec![BlockId(1), BlockId(2)]);
146    }
147
148    #[test]
149    fn test_basic_block_defs_and_uses() {
150        let mut bb = BasicBlock::new(BlockId(0));
151        bb.instructions.push(MirInst::BinOp {
152            dest: ValueId(2),
153            op: BinOp::Add,
154            lhs: ValueId(0),
155            rhs: ValueId(1),
156            ty: MirType::I32,
157        });
158        bb.terminator = Terminator::Return;
159
160        let defs = bb.defs();
161        assert_eq!(defs, vec![ValueId(2)]);
162
163        let uses = bb.uses();
164        assert_eq!(uses, vec![ValueId(0), ValueId(1)]);
165    }
166
167    #[test]
168    fn test_phi_node() {
169        let phi = PhiNode {
170            dest: ValueId(3),
171            ty: MirType::I32,
172            incoming: vec![(BlockId(0), ValueId(1)), (BlockId(1), ValueId(2))],
173        };
174        assert_eq!(phi.dest, ValueId(3));
175        assert_eq!(phi.incoming.len(), 2);
176    }
177
178    #[test]
179    fn test_terminator_operands() {
180        let term = Terminator::CondBranch {
181            cond: ValueId(5),
182            true_target: BlockId(1),
183            false_target: BlockId(2),
184        };
185        assert_eq!(term.operands(), vec![ValueId(5)]);
186
187        let ret = Terminator::Return;
188        assert!(ret.operands().is_empty());
189    }
190}
wave_compiler/mir/basic_block.rs

wave_compiler/mir/
basic_block.rs
