use std::collections::{HashMap, HashSet};
use super::cfg::{block_id_index, compute_dominators, reachable_blocks, terminator_successors};
use crate::codegen::ir::{BlockId, MirBlock, MirTerminator};
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub(crate) enum HeaderKind {
Selection { merge: BlockId },
Loop {
merge: BlockId,
continue_target: BlockId,
},
}
#[derive(Debug, Default)]
pub(crate) struct StructuredCfg {
headers: HashMap<BlockId, HeaderKind>,
}
impl StructuredCfg {
pub(crate) fn header(&self, block: BlockId) -> Option<HeaderKind> {
self.headers.get(&block).copied()
}
}
pub(crate) fn analyze(blocks: &[MirBlock]) -> StructuredCfg {
let n = blocks.len();
if n == 0 {
return StructuredCfg::default();
}
let id_to_index = block_id_index(blocks);
let reachable = reachable_blocks(blocks);
let dom = compute_dominators(blocks);
let postdom = compute_post_dominators(blocks, &id_to_index, &reachable);
let succs: Vec<Vec<usize>> = blocks
.iter()
.map(|b| terminator_successors(&b.terminator, &id_to_index))
.collect();
let mut headers = HashMap::new();
for (h, block) in blocks.iter().enumerate() {
if !reachable[h] {
continue;
}
let Some(MirTerminator::If {
then_block,
else_block,
..
}) = &block.terminator
else {
continue;
};
let then_i = id_to_index.get(&then_block.0).copied();
let else_i = id_to_index.get(&else_block.0).copied();
let (Some(then_i), Some(else_i)) = (then_i, else_i) else {
continue;
};
let back_edge_src = back_edge_source(h, &succs, &dom, &reachable);
if let Some(latch) = back_edge_src {
let loop_body = loop_body_blocks(h, latch, blocks, &id_to_index, &reachable);
let (merge_i, continue_i) =
if loop_body.contains(&then_i) && !loop_body.contains(&else_i) {
(else_i, then_i)
} else if loop_body.contains(&else_i) && !loop_body.contains(&then_i) {
(then_i, else_i)
} else {
#[cfg(debug_assertions)]
eprintln!(
"buildc[structured-cfg]: ambiguous loop-body classification for \
header block {} (then={}, else={}, both-or-neither arm in body); \
defaulting to then=body/else=exit. If while-lowering changed, \
verify this convention still holds.",
block.id.0, then_block.0, else_block.0
);
(else_i, then_i)
};
headers.insert(
block.id,
HeaderKind::Loop {
merge: blocks[merge_i].id,
continue_target: blocks[continue_i].id,
},
);
} else {
if let Some(merge_i) = immediate_post_dominator(h, &postdom, &reachable) {
headers.insert(
block.id,
HeaderKind::Selection {
merge: blocks[merge_i].id,
},
);
}
}
}
StructuredCfg { headers }
}
fn back_edge_source(
h: usize,
succs: &[Vec<usize>],
dom: &[HashSet<usize>],
reachable: &[bool],
) -> Option<usize> {
for (p, ss) in succs.iter().enumerate() {
if !reachable[p] {
continue;
}
if ss.contains(&h) && dom[p].contains(&h) {
return Some(p);
}
}
None
}
fn loop_body_blocks(
h: usize,
latch: usize,
blocks: &[MirBlock],
id_to_index: &HashMap<u32, usize>,
reachable: &[bool],
) -> HashSet<usize> {
let n = blocks.len();
let mut preds: Vec<Vec<usize>> = vec![Vec::new(); n];
for (i, b) in blocks.iter().enumerate() {
if !reachable[i] {
continue;
}
for s in terminator_successors(&b.terminator, id_to_index) {
preds[s].push(i);
}
}
let mut body: HashSet<usize> = HashSet::new();
body.insert(h);
body.insert(latch);
let mut stack = vec![latch];
while let Some(b) = stack.pop() {
if b == h {
continue;
}
for &p in &preds[b] {
if body.insert(p) {
stack.push(p);
}
}
}
body
}
fn immediate_post_dominator(
h: usize,
postdom: &[HashSet<usize>],
reachable: &[bool],
) -> Option<usize> {
let candidates: Vec<usize> = postdom[h].iter().copied().filter(|&b| b != h).collect();
if candidates.is_empty() {
return None;
}
for &c in &candidates {
if !reachable[c] {
continue;
}
let is_ipdom = candidates
.iter()
.all(|&d| d == c || postdom[c].contains(&d));
if is_ipdom {
return Some(c);
}
}
candidates
.into_iter()
.filter(|&c| reachable[c])
.min_by_key(|&c| postdom[c].len())
}
fn compute_post_dominators(
blocks: &[MirBlock],
id_to_index: &HashMap<u32, usize>,
reachable: &[bool],
) -> Vec<HashSet<usize>> {
let n = blocks.len();
let mut rev_succ: Vec<Vec<usize>> = vec![Vec::new(); n];
let mut exits: Vec<usize> = Vec::new();
for (i, b) in blocks.iter().enumerate() {
if !reachable[i] {
continue;
}
let ss: Vec<usize> = terminator_successors(&b.terminator, id_to_index)
.into_iter()
.filter(|&s| reachable[s])
.collect();
if ss.is_empty() {
exits.push(i);
}
for s in ss {
rev_succ[s].push(i);
}
}
let all: HashSet<usize> = (0..n).collect();
let mut postdom: Vec<HashSet<usize>> = vec![all; n];
for &e in &exits {
postdom[e] = std::iter::once(e).collect();
}
let rev_preds: Vec<Vec<usize>> = {
let mut rp: Vec<Vec<usize>> = vec![Vec::new(); n];
for (i, outs) in rev_succ.iter().enumerate() {
for &o in outs {
rp[o].push(i);
}
}
rp
};
let exit_set: HashSet<usize> = exits.iter().copied().collect();
let mut changed = true;
while changed {
changed = false;
for i in 0..n {
if !reachable[i] || exit_set.contains(&i) {
continue;
}
let mut new_set: Option<HashSet<usize>> = None;
for &s in &rev_preds[i] {
new_set = Some(match new_set {
None => postdom[s].clone(),
Some(acc) => acc.intersection(&postdom[s]).copied().collect(),
});
}
let mut new_set = new_set.unwrap_or_default();
new_set.insert(i);
if new_set != postdom[i] {
postdom[i] = new_set;
changed = true;
}
}
}
postdom
}
#[cfg(test)]
mod tests {
use super::*;
use crate::codegen::ir::{MirBlock, MirValue};
fn blk(id: u32, term: MirTerminator) -> MirBlock {
MirBlock {
id: BlockId(id),
label: None,
stmts: Vec::new(),
terminator: Some(term),
}
}
fn cond() -> MirValue {
MirValue::Const(crate::codegen::ir::MirConst::Bool(true))
}
#[test]
fn plain_selection_merge_is_reconvergence() {
let blocks = vec![
blk(
0,
MirTerminator::If {
cond: cond(),
then_block: BlockId(1),
else_block: BlockId(2),
},
),
blk(1, MirTerminator::Goto(BlockId(3))),
blk(2, MirTerminator::Goto(BlockId(3))),
blk(3, MirTerminator::Return(None)),
];
let cfg = analyze(&blocks);
assert_eq!(
cfg.header(BlockId(0)),
Some(HeaderKind::Selection { merge: BlockId(3) })
);
}
#[test]
fn loop_nested_in_selection() {
let blocks = vec![
blk(
0,
MirTerminator::If {
cond: cond(),
then_block: BlockId(1),
else_block: BlockId(2),
},
),
blk(1, MirTerminator::Goto(BlockId(4))),
blk(2, MirTerminator::Goto(BlockId(3))),
blk(3, MirTerminator::Return(None)),
blk(
4,
MirTerminator::If {
cond: cond(),
then_block: BlockId(5),
else_block: BlockId(6),
},
),
blk(5, MirTerminator::Goto(BlockId(4))),
blk(6, MirTerminator::Goto(BlockId(3))),
];
let cfg = analyze(&blocks);
assert_eq!(
cfg.header(BlockId(0)),
Some(HeaderKind::Selection { merge: BlockId(3) }),
"outer selection merge must be the reconvergence bb3, not the nested loop header"
);
assert_eq!(
cfg.header(BlockId(4)),
Some(HeaderKind::Loop {
merge: BlockId(6),
continue_target: BlockId(5),
}),
"loop header must name exit bb6 as merge and bb5 as continue target"
);
}
#[test]
fn selection_nested_in_loop() {
let blocks = vec![
blk(0, MirTerminator::Goto(BlockId(1))),
blk(
1,
MirTerminator::If {
cond: cond(),
then_block: BlockId(2),
else_block: BlockId(6),
},
),
blk(
2,
MirTerminator::If {
cond: cond(),
then_block: BlockId(3),
else_block: BlockId(4),
},
),
blk(3, MirTerminator::Goto(BlockId(5))),
blk(4, MirTerminator::Goto(BlockId(5))),
blk(5, MirTerminator::Goto(BlockId(1))),
blk(6, MirTerminator::Return(None)),
];
let cfg = analyze(&blocks);
assert_eq!(
cfg.header(BlockId(1)),
Some(HeaderKind::Loop {
merge: BlockId(6),
continue_target: BlockId(2),
}),
"loop header must name exit bb6 as merge and the body entry bb2 as continue target"
);
assert_eq!(
cfg.header(BlockId(2)),
Some(HeaderKind::Selection { merge: BlockId(5) }),
"inner selection merge must be its reconvergence bb5 inside the loop body, \
not the loop exit bb6 nor the loop header bb1"
);
}
#[test]
fn bare_loop() {
let blocks = vec![
blk(0, MirTerminator::Goto(BlockId(1))),
blk(
1,
MirTerminator::If {
cond: cond(),
then_block: BlockId(2),
else_block: BlockId(3),
},
),
blk(2, MirTerminator::Goto(BlockId(1))),
blk(3, MirTerminator::Return(None)),
];
let cfg = analyze(&blocks);
assert_eq!(
cfg.header(BlockId(1)),
Some(HeaderKind::Loop {
merge: BlockId(3),
continue_target: BlockId(2),
})
);
}
}