armfortas Public

Watch 0 Fork 0 Star 0
Rust · 42296 bytes Raw Blame History
1 //! Shared IR-walking helpers.
2 //!
3 //! This module is the **single canonical source** for operand
4 //! enumeration, terminator queries, and small CFG utilities used by
5 //! both the verifier and the optimizer. Audit B-6: prior to this file
6 //! the same machinery was duplicated five ways across `verify.rs`,
7 //! `opt/util.rs`, `opt/cse.rs`, `opt/dce.rs`, and `opt/const_prop.rs`,
8 //! creating a maintenance footgun — adding a new `InstKind` variant
9 //! required updating every duplicate, and missing one would silently
10 //! break that pass.
11 //!
12 //! Anything operating on `InstKind` or `Terminator` at the level of
13 //! "what operands does this instruction read?" or "where does this
14 //! terminator branch?" should live here.
15
16 use super::inst::*;
17 use std::collections::{HashMap, HashSet, VecDeque};
18
19 // =====================================================================
20 // Operand enumeration (read-only)
21 // =====================================================================
22
23 /// All `ValueId`s consumed as operands by an instruction.
24 pub fn inst_uses(kind: &InstKind) -> Vec<ValueId> {
25 match kind {
26 InstKind::ConstInt(..)
27 | InstKind::ConstFloat(..)
28 | InstKind::ConstBool(..)
29 | InstKind::ConstString(..)
30 | InstKind::Undef(..)
31 | InstKind::Alloca(..)
32 | InstKind::GlobalAddr(..) => vec![],
33
34 InstKind::IAdd(a, b)
35 | InstKind::ISub(a, b)
36 | InstKind::IMul(a, b)
37 | InstKind::IDiv(a, b)
38 | InstKind::IMod(a, b) => vec![*a, *b],
39 InstKind::INeg(a) => vec![*a],
40
41 InstKind::FAdd(a, b)
42 | InstKind::FSub(a, b)
43 | InstKind::FMul(a, b)
44 | InstKind::FDiv(a, b)
45 | InstKind::FPow(a, b) => vec![*a, *b],
46 InstKind::FNeg(a) | InstKind::FAbs(a) | InstKind::FSqrt(a) => vec![*a],
47
48 InstKind::ICmp(_, a, b) | InstKind::FCmp(_, a, b) => vec![*a, *b],
49
50 InstKind::And(a, b) | InstKind::Or(a, b) => vec![*a, *b],
51 InstKind::Not(a) => vec![*a],
52
53 InstKind::Select(c, t, f) => vec![*c, *t, *f],
54
55 InstKind::BitAnd(a, b)
56 | InstKind::BitOr(a, b)
57 | InstKind::BitXor(a, b)
58 | InstKind::Shl(a, b)
59 | InstKind::LShr(a, b)
60 | InstKind::AShr(a, b) => vec![*a, *b],
61 InstKind::BitNot(a)
62 | InstKind::CountLeadingZeros(a)
63 | InstKind::CountTrailingZeros(a)
64 | InstKind::PopCount(a) => vec![*a],
65
66 InstKind::IntToFloat(v, _)
67 | InstKind::FloatToInt(v, _)
68 | InstKind::FloatExtend(v, _)
69 | InstKind::FloatTrunc(v, _)
70 | InstKind::IntExtend(v, _, _)
71 | InstKind::IntTrunc(v, _)
72 | InstKind::PtrToInt(v)
73 | InstKind::IntToPtr(v, _) => vec![*v],
74
75 InstKind::Load(a) => vec![*a],
76 InstKind::Store(v, a) => vec![*v, *a],
77 InstKind::GetElementPtr(base, idxs) => {
78 let mut uses = vec![*base];
79 uses.extend(idxs);
80 uses
81 }
82
83 InstKind::Call(FuncRef::Indirect(target), args) => {
84 let mut uses = vec![*target];
85 uses.extend(args);
86 uses
87 }
88 InstKind::Call(_, args) | InstKind::RuntimeCall(_, args) => args.clone(),
89
90 InstKind::ExtractField(agg, _) => vec![*agg],
91 InstKind::InsertField(agg, _, val) => vec![*agg, *val],
92
93 // ---- SIMD vector ops ----
94 InstKind::VAdd(a, b)
95 | InstKind::VSub(a, b)
96 | InstKind::VMul(a, b)
97 | InstKind::VDiv(a, b)
98 | InstKind::VMin(a, b)
99 | InstKind::VMax(a, b) => vec![*a, *b],
100 InstKind::VNeg(a)
101 | InstKind::VAbs(a)
102 | InstKind::VSqrt(a)
103 | InstKind::VLoad(a)
104 | InstKind::VBitcast(a, _)
105 | InstKind::VExtract(a, _)
106 | InstKind::VBroadcast(a)
107 | InstKind::VReduceSum(a)
108 | InstKind::VReduceMin(a)
109 | InstKind::VReduceMax(a) => vec![*a],
110 InstKind::VFma(a, b, c) => vec![*a, *b, *c],
111 InstKind::VSelect(m, t, f) => vec![*m, *t, *f],
112 InstKind::VICmp(_, a, b) | InstKind::VFCmp(_, a, b) => vec![*a, *b],
113 InstKind::VStore(v, p) => vec![*v, *p],
114 InstKind::VInsert(v, _, s) => vec![*v, *s],
115 }
116 }
117
118 /// All `ValueId`s consumed by a terminator.
119 pub fn terminator_uses(term: &Terminator) -> Vec<ValueId> {
120 match term {
121 Terminator::Return(None) | Terminator::Unreachable => vec![],
122 Terminator::Return(Some(v)) => vec![*v],
123 Terminator::Branch(_, args) => args.clone(),
124 Terminator::CondBranch {
125 cond,
126 true_args,
127 false_args,
128 ..
129 } => {
130 let mut uses = vec![*cond];
131 uses.extend(true_args);
132 uses.extend(false_args);
133 uses
134 }
135 Terminator::Switch { selector, .. } => vec![*selector],
136 }
137 }
138
139 /// All successor `BlockId`s of a terminator.
140 pub fn terminator_targets(term: &Terminator) -> Vec<BlockId> {
141 match term {
142 Terminator::Return(_) | Terminator::Unreachable => vec![],
143 Terminator::Branch(d, _) => vec![*d],
144 Terminator::CondBranch {
145 true_dest,
146 false_dest,
147 ..
148 } => vec![*true_dest, *false_dest],
149 Terminator::Switch { cases, default, .. } => {
150 let mut t: Vec<BlockId> = cases.iter().map(|(_, b)| *b).collect();
151 t.push(*default);
152 t
153 }
154 }
155 }
156
157 // =====================================================================
158 // Operand enumeration (mutable)
159 // =====================================================================
160
161 /// Apply a closure to every operand slot of an instruction in place.
162 pub fn for_each_operand_mut(kind: &mut InstKind, mut r: impl FnMut(&mut ValueId)) {
163 match kind {
164 InstKind::ConstInt(..)
165 | InstKind::ConstFloat(..)
166 | InstKind::ConstBool(..)
167 | InstKind::ConstString(..)
168 | InstKind::Undef(..)
169 | InstKind::Alloca(..)
170 | InstKind::GlobalAddr(..) => {}
171
172 InstKind::IAdd(a, b)
173 | InstKind::ISub(a, b)
174 | InstKind::IMul(a, b)
175 | InstKind::IDiv(a, b)
176 | InstKind::IMod(a, b) => {
177 r(a);
178 r(b);
179 }
180 InstKind::INeg(a) => r(a),
181
182 InstKind::FAdd(a, b)
183 | InstKind::FSub(a, b)
184 | InstKind::FMul(a, b)
185 | InstKind::FDiv(a, b)
186 | InstKind::FPow(a, b) => {
187 r(a);
188 r(b);
189 }
190 InstKind::FNeg(a) | InstKind::FAbs(a) | InstKind::FSqrt(a) => r(a),
191
192 InstKind::ICmp(_, a, b) | InstKind::FCmp(_, a, b) => {
193 r(a);
194 r(b);
195 }
196
197 InstKind::And(a, b) | InstKind::Or(a, b) => {
198 r(a);
199 r(b);
200 }
201 InstKind::Not(a) => r(a),
202
203 InstKind::Select(c, t, f) => {
204 r(c);
205 r(t);
206 r(f);
207 }
208
209 InstKind::BitAnd(a, b)
210 | InstKind::BitOr(a, b)
211 | InstKind::BitXor(a, b)
212 | InstKind::Shl(a, b)
213 | InstKind::LShr(a, b)
214 | InstKind::AShr(a, b) => {
215 r(a);
216 r(b);
217 }
218 InstKind::BitNot(a)
219 | InstKind::CountLeadingZeros(a)
220 | InstKind::CountTrailingZeros(a)
221 | InstKind::PopCount(a) => r(a),
222
223 InstKind::IntToFloat(v, _)
224 | InstKind::FloatToInt(v, _)
225 | InstKind::FloatExtend(v, _)
226 | InstKind::FloatTrunc(v, _)
227 | InstKind::IntExtend(v, _, _)
228 | InstKind::IntTrunc(v, _)
229 | InstKind::PtrToInt(v)
230 | InstKind::IntToPtr(v, _) => r(v),
231
232 InstKind::Load(a) => r(a),
233 InstKind::Store(v, a) => {
234 r(v);
235 r(a);
236 }
237 InstKind::GetElementPtr(base, idxs) => {
238 r(base);
239 for i in idxs {
240 r(i);
241 }
242 }
243
244 InstKind::Call(FuncRef::Indirect(target), args) => {
245 r(target);
246 for a in args {
247 r(a);
248 }
249 }
250 InstKind::Call(_, args) | InstKind::RuntimeCall(_, args) => {
251 for a in args {
252 r(a);
253 }
254 }
255
256 InstKind::ExtractField(agg, _) => r(agg),
257 InstKind::InsertField(agg, _, val) => {
258 r(agg);
259 r(val);
260 }
261
262 // ---- SIMD vector ops ----
263 InstKind::VAdd(a, b)
264 | InstKind::VSub(a, b)
265 | InstKind::VMul(a, b)
266 | InstKind::VDiv(a, b)
267 | InstKind::VMin(a, b)
268 | InstKind::VMax(a, b) => {
269 r(a);
270 r(b);
271 }
272 InstKind::VNeg(a)
273 | InstKind::VAbs(a)
274 | InstKind::VSqrt(a)
275 | InstKind::VLoad(a)
276 | InstKind::VBitcast(a, _)
277 | InstKind::VExtract(a, _)
278 | InstKind::VBroadcast(a)
279 | InstKind::VReduceSum(a)
280 | InstKind::VReduceMin(a)
281 | InstKind::VReduceMax(a) => r(a),
282 InstKind::VFma(a, b, c) => {
283 r(a);
284 r(b);
285 r(c);
286 }
287 InstKind::VSelect(m, t, f) => {
288 r(m);
289 r(t);
290 r(f);
291 }
292 InstKind::VICmp(_, a, b) | InstKind::VFCmp(_, a, b) => {
293 r(a);
294 r(b);
295 }
296 InstKind::VStore(v, p) => {
297 r(v);
298 r(p);
299 }
300 InstKind::VInsert(v, _, s) => {
301 r(v);
302 r(s);
303 }
304 }
305 }
306
307 /// Apply a closure to every operand slot of a terminator in place.
308 pub fn for_each_terminator_operand_mut(term: &mut Terminator, mut r: impl FnMut(&mut ValueId)) {
309 match term {
310 Terminator::Return(None) | Terminator::Unreachable => {}
311 Terminator::Return(Some(v)) => r(v),
312 Terminator::Branch(_, args) => {
313 for a in args {
314 r(a);
315 }
316 }
317 Terminator::CondBranch {
318 cond,
319 true_args,
320 false_args,
321 ..
322 } => {
323 r(cond);
324 for a in true_args {
325 r(a);
326 }
327 for a in false_args {
328 r(a);
329 }
330 }
331 Terminator::Switch { selector, .. } => r(selector),
332 }
333 }
334
335 /// Replace every use of `old` with `new` across the entire function.
336 /// Definitions are unaffected — only operand slots in instructions and
337 /// terminators are rewritten.
338 pub fn substitute_uses(func: &mut Function, old: ValueId, new: ValueId) {
339 let r = |v: &mut ValueId| {
340 if *v == old {
341 *v = new;
342 }
343 };
344 for block in &mut func.blocks {
345 for inst in &mut block.insts {
346 for_each_operand_mut(&mut inst.kind, r);
347 }
348 if let Some(term) = &mut block.terminator {
349 for_each_terminator_operand_mut(term, r);
350 }
351 }
352 }
353
354 // =====================================================================
355 // CFG queries
356 // =====================================================================
357
358 /// Build a predecessor map: for each block, the list of blocks that
359 /// branch into it.
360 pub fn predecessors(func: &Function) -> HashMap<BlockId, Vec<BlockId>> {
361 let mut preds: HashMap<BlockId, Vec<BlockId>> = HashMap::new();
362 for block in &func.blocks {
363 preds.entry(block.id).or_default();
364 }
365 for block in &func.blocks {
366 if let Some(term) = &block.terminator {
367 for tgt in terminator_targets(term) {
368 preds.entry(tgt).or_default().push(block.id);
369 }
370 }
371 }
372 preds
373 }
374
375 /// Compute the dominator set for each block via iterative dataflow.
376 /// Result: `dom[B]` is the set of blocks that dominate `B` (including
377 /// `B` itself).
378 ///
379 /// Audit M4-3: blocks that are **not reachable from the entry** are
380 /// assigned the empty set (they dominate nothing and nothing dominates
381 /// them). The earlier version left unreachable blocks at the initial
382 /// `{all_blocks}` default, which made every edge inside an unreachable
383 /// component look like a back-edge (because the source "dominated"
384 /// the target by default). That in turn let `find_natural_loops`
385 /// fabricate phantom loops in unreachable code. LICM was shielded by
386 /// the N-6 pre-prune, but any future consumer of `compute_dominators`
387 /// would trip over the latent bug.
388 pub fn compute_dominators(func: &Function) -> HashMap<BlockId, HashSet<BlockId>> {
389 let all_blocks: HashSet<BlockId> = func.blocks.iter().map(|b| b.id).collect();
390
391 // First, compute the set of blocks reachable from the entry via
392 // a forward BFS over terminator targets.
393 let mut reachable: HashSet<BlockId> = HashSet::new();
394 let mut queue: VecDeque<BlockId> = VecDeque::new();
395 queue.push_back(func.entry);
396 reachable.insert(func.entry);
397 while let Some(bid) = queue.pop_front() {
398 if let Some(block) = func.blocks.iter().find(|b| b.id == bid) {
399 if let Some(term) = &block.terminator {
400 for tgt in terminator_targets(term) {
401 if reachable.insert(tgt) {
402 queue.push_back(tgt);
403 }
404 }
405 }
406 }
407 }
408
409 let mut doms: HashMap<BlockId, HashSet<BlockId>> = HashMap::new();
410
411 // Entry is dominated only by itself.
412 let mut entry_set = HashSet::new();
413 entry_set.insert(func.entry);
414 doms.insert(func.entry, entry_set);
415
416 // Reachable non-entry blocks: initialize to the universe of
417 // reachable blocks (so the intersection converges).
418 // Unreachable blocks: initialize to the empty set and never
419 // update them — they participate in no meaningful dominance
420 // relationship.
421 for block in &func.blocks {
422 if block.id == func.entry {
423 continue;
424 }
425 if reachable.contains(&block.id) {
426 doms.insert(block.id, reachable.clone());
427 } else {
428 doms.insert(block.id, HashSet::new());
429 }
430 }
431
432 let preds = predecessors(func);
433 let mut changed = true;
434 while changed {
435 changed = false;
436 for block in &func.blocks {
437 if block.id == func.entry {
438 continue;
439 }
440 if !reachable.contains(&block.id) {
441 continue;
442 }
443 let plist = preds.get(&block.id).cloned().unwrap_or_default();
444 // Reachable-only predecessors — an edge from an
445 // unreachable block doesn't contribute to dominance.
446 let reachable_preds: Vec<BlockId> = plist
447 .into_iter()
448 .filter(|p| reachable.contains(p))
449 .collect();
450 if reachable_preds.is_empty() {
451 continue;
452 }
453 let mut new_dom = reachable.clone();
454 for p in &reachable_preds {
455 if let Some(pd) = doms.get(p) {
456 new_dom = new_dom.intersection(pd).copied().collect();
457 }
458 }
459 new_dom.insert(block.id);
460 if doms.get(&block.id) != Some(&new_dom) {
461 doms.insert(block.id, new_dom);
462 changed = true;
463 }
464 }
465 }
466 // Silence unused-var lint for `all_blocks` — kept for potential
467 // future needs (and because removing it would break callers that
468 // expect every block to have an entry in the map).
469 let _ = all_blocks;
470 doms
471 }
472
473 /// A natural loop: header + the set of blocks in the loop body.
474 #[derive(Debug, Clone)]
475 pub struct NaturalLoop {
476 /// The unique entry point of the loop.
477 pub header: BlockId,
478 /// All blocks belonging to the loop body, including the header.
479 pub body: HashSet<BlockId>,
480 /// Blocks containing the back-edges into the header (always a
481 /// subset of `body`).
482 pub latches: Vec<BlockId>,
483 }
484
485 /// Discover natural loops in a function. A natural loop is identified
486 /// by a back edge `(B → H)` where `H` dominates `B`. The body is the
487 /// set of nodes that can reach `B` without going through `H`, plus `H`
488 /// and `B` themselves.
489 ///
490 /// We do not collapse multiple back-edges into the same header into a
491 /// single loop here — each back-edge yields one loop, and downstream
492 /// passes can merge them if needed. (LICM only cares about the body
493 /// set, so identical-header loops are still safe.)
494 pub fn find_natural_loops(func: &Function) -> Vec<NaturalLoop> {
495 let doms = compute_dominators(func);
496 let preds = predecessors(func);
497
498 // Collect back edges: (latch → header) where header dominates latch.
499 let mut back_edges: Vec<(BlockId, BlockId)> = Vec::new();
500 for block in &func.blocks {
501 if let Some(term) = &block.terminator {
502 for tgt in terminator_targets(term) {
503 if let Some(d) = doms.get(&block.id) {
504 if d.contains(&tgt) {
505 back_edges.push((block.id, tgt));
506 }
507 }
508 }
509 }
510 }
511
512 // Group back edges by header so we get one NaturalLoop per header.
513 let mut by_header: HashMap<BlockId, Vec<BlockId>> = HashMap::new();
514 for (latch, hdr) in back_edges {
515 by_header.entry(hdr).or_default().push(latch);
516 }
517
518 // Audit N-4: iterate the grouped back-edges in **stable** header
519 // order. `HashMap` iteration order is nondeterministic across
520 // runs, which would make downstream passes that hoist loop-by-loop
521 // (like LICM) produce different IR on repeated compiles of the
522 // same source — painful for `--emit-ir` bisection and for
523 // differential debugging. Sort by `header.0` (and latches within
524 // each loop for the same reason).
525 let mut headers: Vec<BlockId> = by_header.keys().copied().collect();
526 headers.sort_by_key(|h| h.0);
527
528 let mut loops = Vec::new();
529 for header in headers {
530 let mut latches = by_header.remove(&header).unwrap();
531 latches.sort_by_key(|l| l.0);
532 // Body = {header} ∪ all nodes that can reach any latch without
533 // going through the header.
534 let mut body: HashSet<BlockId> = HashSet::new();
535 body.insert(header);
536 for &latch in &latches {
537 body.insert(latch);
538 }
539 // Audit M-7: filter out latches that *are* the header
540 // (self-loops). If we walk preds(header) the BFS will
541 // enumerate the preheader as a "body" node and absorb
542 // everything reachable from the entry, which both inflates
543 // the body and makes `find_preheader` see no out-of-loop
544 // predecessor for the header.
545 let mut stack: Vec<BlockId> = latches.iter().filter(|&&l| l != header).copied().collect();
546 while let Some(b) = stack.pop() {
547 if let Some(plist) = preds.get(&b) {
548 for &p in plist {
549 if p == header {
550 continue;
551 }
552 if body.insert(p) {
553 stack.push(p);
554 }
555 }
556 }
557 }
558 loops.push(NaturalLoop {
559 header,
560 body,
561 latches,
562 });
563 }
564 loops
565 }
566
567 /// Remove blocks unreachable from the function entry. Returns true if
568 /// any blocks were dropped.
569 ///
570 /// Audit M4-2 / m4-3: uses `try_block` instead of `block` so a stale
571 /// terminator target (pointing at a block that was already pruned,
572 /// e.g., mid-pass state) degrades gracefully to "skip that edge"
573 /// instead of panicking. On valid IR this behaves identically to the
574 /// old version because the verifier rejects dangling targets.
575 pub fn prune_unreachable(func: &mut Function) -> bool {
576 let mut reachable: HashSet<BlockId> = HashSet::new();
577 let mut queue: VecDeque<BlockId> = VecDeque::new();
578 queue.push_back(func.entry);
579 reachable.insert(func.entry);
580 while let Some(bid) = queue.pop_front() {
581 let Some(block) = func.try_block(bid) else {
582 continue;
583 };
584 if let Some(term) = &block.terminator {
585 for tgt in terminator_targets(term) {
586 if reachable.insert(tgt) {
587 queue.push_back(tgt);
588 }
589 }
590 }
591 }
592 let before = func.blocks.len();
593 func.blocks.retain(|b| reachable.contains(&b.id));
594 func.blocks.len() != before
595 }
596
597 // =====================================================================
598 // Dominator tree + dominance frontiers
599 // =====================================================================
600
601 /// Compute the immediate dominator of every reachable block.
602 ///
603 /// The immediate dominator `idom(B)` is the unique closest dominator
604 /// of `B` other than `B` itself. The entry block has no idom; every
605 /// other reachable block does.
606 ///
607 /// Returns a map keyed only by reachable non-entry blocks.
608 /// Unreachable blocks have an empty dominator set (per
609 /// [`compute_dominators`]) and therefore no idom.
610 ///
611 /// **Performance**: this is the naïve O(N³) construction — for each
612 /// block we filter its dominator set, then for each candidate scan
613 /// every other candidate's dominator set looking for the unique
614 /// "smallest". `compute_dominators` itself is O(N²·E) iterative
615 /// data-flow on top, so the asymptotic ceiling for the dominator
616 /// pipeline is roughly O(N³ + N²·E). That is fine for the
617 /// kilo-block functions today's frontend produces, but if we ever
618 /// start lowering huge SSA graphs (autovec spillovers, inlining
619 /// across modules) the right replacement is Lengauer–Tarjan, which
620 /// is O((N+E)·α(N)) in practice. Track separately as an
621 /// optimization-tier replacement, not a correctness fix.
622 pub fn compute_immediate_dominators(func: &Function) -> HashMap<BlockId, BlockId> {
623 let doms = compute_dominators(func);
624 let mut idoms: HashMap<BlockId, BlockId> = HashMap::new();
625
626 for block in &func.blocks {
627 if block.id == func.entry {
628 continue;
629 }
630 let Some(my_doms) = doms.get(&block.id) else {
631 continue;
632 };
633 if my_doms.is_empty() {
634 continue;
635 } // unreachable
636
637 // The immediate dominator is the dominator (other than
638 // self) that is dominated by every other dominator (other
639 // than self). Equivalently: the dominator that has the
640 // largest dominator set — all other dominators of `block`
641 // also dominate the idom.
642 let candidates: Vec<BlockId> = my_doms.iter().copied().filter(|&d| d != block.id).collect();
643
644 let idom = candidates.iter().copied().find(|&cand| {
645 // cand is idom iff no other candidate strictly
646 // dominates it (only cand itself and cand's own
647 // dominators do).
648 let cand_doms = doms.get(&cand).cloned().unwrap_or_default();
649 candidates
650 .iter()
651 .all(|&other| other == cand || cand_doms.contains(&other))
652 });
653
654 if let Some(idom) = idom {
655 idoms.insert(block.id, idom);
656 }
657 }
658
659 idoms
660 }
661
662 /// Compute the **children** of each block in the dominator tree —
663 /// the inverse of the idom map.
664 ///
665 /// `children[B]` is the set of blocks whose immediate dominator is
666 /// `B`. A dominator-tree traversal visits `B` then recurses into
667 /// `children[B]` in some order.
668 pub fn dominator_tree_children(
669 idoms: &HashMap<BlockId, BlockId>,
670 ) -> HashMap<BlockId, Vec<BlockId>> {
671 let mut children: HashMap<BlockId, Vec<BlockId>> = HashMap::new();
672 for (&child, &parent) in idoms {
673 children.entry(parent).or_default().push(child);
674 }
675 // Sort each child list by BlockId.0 for deterministic iteration.
676 for list in children.values_mut() {
677 list.sort_by_key(|b| b.0);
678 }
679 children
680 }
681
682 /// Compute the dominance frontier of every reachable block.
683 ///
684 /// The dominance frontier `DF(B)` is the set of blocks `X` such that
685 /// `B` dominates a predecessor of `X` but does **not** strictly
686 /// dominate `X` itself. Dominance frontiers are where phi nodes
687 /// (block parameters in our IR) must be inserted when promoting an
688 /// alloca that is stored to in `B`.
689 ///
690 /// Uses the Cytron-Ferrante-Rosen-Wegman-Zadeck formulation:
691 /// for every join point `X` (block with ≥ 2 predecessors), walk
692 /// each predecessor `P` upward in the dominator tree, adding `X`
693 /// to `DF(runner)` until `runner == idom(X)`.
694 pub fn compute_dominance_frontiers(func: &Function) -> HashMap<BlockId, HashSet<BlockId>> {
695 let idoms = compute_immediate_dominators(func);
696 let preds = predecessors(func);
697
698 // Audit D2: build the set of reachable blocks (= keys present
699 // in `idoms`, plus the entry block itself). Unreachable blocks
700 // have no idom, so the runner walk would `match idoms.get(&runner)`
701 // → `None` → `break`, but only AFTER inserting `x` into
702 // `df[runner]` — populating `df` with phantom entries for
703 // unreachable predecessors that downstream consumers (mem2reg's
704 // iterated-DF closure in particular) must then defensively
705 // ignore. Filtering at the source keeps the DF map clean.
706 let reachable: HashSet<BlockId> = idoms
707 .keys()
708 .copied()
709 .chain(std::iter::once(func.entry))
710 .collect();
711
712 let mut df: HashMap<BlockId, HashSet<BlockId>> = HashMap::new();
713 // Initialize empty frontiers for every reachable block so
714 // callers can index without checking for `Some`. Unreachable
715 // blocks are excluded entirely from the map.
716 for block in &func.blocks {
717 if reachable.contains(&block.id) {
718 df.insert(block.id, HashSet::new());
719 }
720 }
721
722 for block in &func.blocks {
723 let x = block.id;
724 if !reachable.contains(&x) {
725 continue;
726 }
727 let plist = preds.get(&x).cloned().unwrap_or_default();
728 // Drop unreachable predecessors before counting toward
729 // "join point" status. An unreachable predecessor adds no
730 // runtime control flow into x.
731 let plist: Vec<BlockId> = plist
732 .into_iter()
733 .filter(|p| reachable.contains(p))
734 .collect();
735 if plist.len() < 2 {
736 continue;
737 }
738
739 // `x` is a join point. Walk each predecessor upward.
740 let idom_x = idoms.get(&x).copied();
741 for p in plist {
742 let mut runner = p;
743 // Stop when runner reaches idom(x) — at that point
744 // `runner` strictly dominates `x`, so `x` is no longer
745 // in `DF(runner)`.
746 while Some(runner) != idom_x {
747 df.entry(runner).or_default().insert(x);
748 match idoms.get(&runner) {
749 Some(&parent) => runner = parent,
750 None => break, // runner is entry (no idom)
751 }
752 }
753 }
754 }
755
756 df
757 }
758
759 /// Compute a **preorder** traversal of the dominator tree starting
760 /// at the entry block. This is the correct visit order for mem2reg's
761 /// renaming walk: a block's dominator's values are installed on the
762 /// current-value stack before we enter the block.
763 ///
764 /// Returns a deterministic ordering (children are iterated in
765 /// ascending `BlockId.0` order courtesy of `dominator_tree_children`).
766 pub fn dominator_tree_preorder(func: &Function) -> Vec<BlockId> {
767 let idoms = compute_immediate_dominators(func);
768 let children = dominator_tree_children(&idoms);
769
770 let mut order = Vec::new();
771 let mut stack: Vec<BlockId> = vec![func.entry];
772 while let Some(b) = stack.pop() {
773 order.push(b);
774 if let Some(kids) = children.get(&b) {
775 // Push in reverse so that smaller BlockId.0 is visited first.
776 for &k in kids.iter().rev() {
777 stack.push(k);
778 }
779 }
780 }
781 order
782 }
783
784 #[cfg(test)]
785 mod walk_tests {
786 use super::super::types::IrType;
787 use super::*;
788 use crate::lexer::{Position, Span};
789
790 fn dummy_span() -> Span {
791 let p = Position { line: 1, col: 1 };
792 Span {
793 start: p,
794 end: p,
795 file_id: 0,
796 }
797 }
798
799 /// Build a diamond CFG:
800 /// entry
801 /// / \
802 /// a b
803 /// \ /
804 /// merge
805 /// Used by dom-tree and dominance-frontier tests.
806 fn diamond_function() -> (Function, BlockId, BlockId, BlockId) {
807 let mut f = Function::new("f".into(), vec![], IrType::Void);
808 let a = f.create_block("a");
809 let b = f.create_block("b");
810 let merge = f.create_block("merge");
811
812 let entry = f.entry;
813 let cond = f.next_value_id();
814 f.block_mut(entry).insts.push(Inst {
815 id: cond,
816 kind: InstKind::ConstBool(true),
817 ty: IrType::Bool,
818 span: dummy_span(),
819 });
820 f.block_mut(entry).terminator = Some(Terminator::CondBranch {
821 cond,
822 true_dest: a,
823 true_args: vec![],
824 false_dest: b,
825 false_args: vec![],
826 });
827 f.block_mut(a).terminator = Some(Terminator::Branch(merge, vec![]));
828 f.block_mut(b).terminator = Some(Terminator::Branch(merge, vec![]));
829 f.block_mut(merge).terminator = Some(Terminator::Return(None));
830
831 (f, a, b, merge)
832 }
833
834 #[test]
835 fn immediate_dominators_diamond() {
836 let (f, a, b, merge) = diamond_function();
837 let idoms = compute_immediate_dominators(&f);
838 // entry has no idom.
839 assert!(!idoms.contains_key(&f.entry));
840 // a, b, merge all have entry as their idom.
841 assert_eq!(idoms[&a], f.entry);
842 assert_eq!(idoms[&b], f.entry);
843 assert_eq!(idoms[&merge], f.entry);
844 }
845
846 #[test]
847 fn dominance_frontier_diamond() {
848 let (f, a, b, merge) = diamond_function();
849 let df = compute_dominance_frontiers(&f);
850 // a's frontier is {merge} — a dominates itself (a pred of
851 // merge) but doesn't dominate merge.
852 assert_eq!(df[&a], HashSet::from([merge]));
853 // b's frontier is also {merge}.
854 assert_eq!(df[&b], HashSet::from([merge]));
855 // merge's frontier is empty (it's a join point itself, but
856 // has no successors that are join points of anything else
857 // in this CFG).
858 assert!(df[&merge].is_empty());
859 // entry's frontier is empty.
860 assert!(df[&f.entry].is_empty());
861 }
862
863 #[test]
864 fn dominator_tree_preorder_visits_entry_first() {
865 let (f, _a, _b, _merge) = diamond_function();
866 let order = dominator_tree_preorder(&f);
867 assert_eq!(order[0], f.entry);
868 assert_eq!(order.len(), 4);
869 }
870
871 /// A simple loop:
872 /// entry → header → body → header
873 /// → exit
874 /// Body dominates nothing below header; header dominates body,
875 /// exit, and the back-edge doesn't change dominance.
876 #[test]
877 fn dominance_frontier_loop() {
878 let mut f = Function::new("f".into(), vec![], IrType::Void);
879 let header = f.create_block("header");
880 let body = f.create_block("body");
881 let exit = f.create_block("exit");
882
883 let entry = f.entry;
884 f.block_mut(entry).terminator = Some(Terminator::Branch(header, vec![]));
885
886 let cond = f.next_value_id();
887 f.block_mut(header).insts.push(Inst {
888 id: cond,
889 kind: InstKind::ConstBool(true),
890 ty: IrType::Bool,
891 span: dummy_span(),
892 });
893 f.block_mut(header).terminator = Some(Terminator::CondBranch {
894 cond,
895 true_dest: body,
896 true_args: vec![],
897 false_dest: exit,
898 false_args: vec![],
899 });
900 f.block_mut(body).terminator = Some(Terminator::Branch(header, vec![]));
901 f.block_mut(exit).terminator = Some(Terminator::Return(None));
902
903 let df = compute_dominance_frontiers(&f);
904 // `body`'s frontier is {header} — body is a pred of header
905 // via the back edge, but doesn't dominate header.
906 assert_eq!(df[&body], HashSet::from([header]));
907 // `header`'s frontier is {header} too — header is a join
908 // point (entry + body both branch into it), and though
909 // header dominates itself, it does NOT *strictly* dominate
910 // itself, so header is in its own frontier.
911 assert_eq!(df[&header], HashSet::from([header]));
912 }
913
914 /// `find_promotable-style` usage: verify the idom map is what
915 /// mem2reg would read. Nested if: both branches store to %a;
916 /// both merge blocks need a block param. `iterated_dominance_frontier`
917 /// is effectively DF applied transitively over the store set.
918 #[test]
919 fn iterated_dominance_frontier_via_repeated_df() {
920 // Build:
921 // entry
922 // / \
923 // a b
924 // | / \
925 // | c d
926 // | \ /
927 // | m1
928 // \ /
929 // m2
930 let mut f = Function::new("f".into(), vec![], IrType::Void);
931 let a = f.create_block("a");
932 let b = f.create_block("b");
933 let c = f.create_block("c");
934 let d = f.create_block("d");
935 let m1 = f.create_block("m1");
936 let m2 = f.create_block("m2");
937
938 let entry = f.entry;
939 let c0 = f.next_value_id();
940 f.block_mut(entry).insts.push(Inst {
941 id: c0,
942 kind: InstKind::ConstBool(true),
943 ty: IrType::Bool,
944 span: dummy_span(),
945 });
946 f.block_mut(entry).terminator = Some(Terminator::CondBranch {
947 cond: c0,
948 true_dest: a,
949 true_args: vec![],
950 false_dest: b,
951 false_args: vec![],
952 });
953 let c1 = f.next_value_id();
954 f.block_mut(b).insts.push(Inst {
955 id: c1,
956 kind: InstKind::ConstBool(true),
957 ty: IrType::Bool,
958 span: dummy_span(),
959 });
960 f.block_mut(b).terminator = Some(Terminator::CondBranch {
961 cond: c1,
962 true_dest: c,
963 true_args: vec![],
964 false_dest: d,
965 false_args: vec![],
966 });
967 f.block_mut(c).terminator = Some(Terminator::Branch(m1, vec![]));
968 f.block_mut(d).terminator = Some(Terminator::Branch(m1, vec![]));
969 f.block_mut(m1).terminator = Some(Terminator::Branch(m2, vec![]));
970 f.block_mut(a).terminator = Some(Terminator::Branch(m2, vec![]));
971 f.block_mut(m2).terminator = Some(Terminator::Return(None));
972
973 let df = compute_dominance_frontiers(&f);
974 // c and d both flow into m1; DF(c) = DF(d) = {m1}
975 assert_eq!(df[&c], HashSet::from([m1]));
976 assert_eq!(df[&d], HashSet::from([m1]));
977 // a and m1 both flow into m2; DF(a) = DF(m1) = {m2}
978 assert_eq!(df[&a], HashSet::from([m2]));
979 assert_eq!(df[&m1], HashSet::from([m2]));
980 // b dominates c, d, m1 but not m2 — b is in df of m2 because
981 // it dominates a predecessor of m2 (m1) but not m2 itself.
982 assert_eq!(df[&b], HashSet::from([m2]));
983 // The dominator tree looks like:
984 // entry → {a, b, m2}
985 // b → {c, d, m1}
986 let idoms = compute_immediate_dominators(&f);
987 assert_eq!(idoms[&a], entry);
988 assert_eq!(idoms[&b], entry);
989 assert_eq!(idoms[&m2], entry);
990 assert_eq!(idoms[&c], b);
991 assert_eq!(idoms[&d], b);
992 assert_eq!(idoms[&m1], b);
993 }
994
995 // ----- Edge case: single-block function -----
996 //
997 // A function whose entry block is also its only block must
998 // produce an empty idom map (entry has no idom) and a single
999 // empty dominance frontier entry.
1000 #[test]
1001 fn single_block_function_has_no_idom() {
1002 let mut f = Function::new("f".into(), vec![], IrType::Void);
1003 f.block_mut(f.entry).terminator = Some(Terminator::Return(None));
1004
1005 let idoms = compute_immediate_dominators(&f);
1006 assert!(
1007 idoms.is_empty(),
1008 "single-block function should have no idoms"
1009 );
1010
1011 let df = compute_dominance_frontiers(&f);
1012 // Entry is reachable, so it has an entry in the DF map, but
1013 // its frontier is empty (no successors, no join points).
1014 assert_eq!(df.len(), 1);
1015 assert!(df[&f.entry].is_empty());
1016
1017 let order = dominator_tree_preorder(&f);
1018 assert_eq!(order, vec![f.entry]);
1019 }
1020
1021 // ----- Edge case: self-loop on entry -----
1022 //
1023 // The entry block has itself as a successor. Entry still has no
1024 // idom (it's the root), and entry is its own join point (1 pred,
1025 // itself), so it should NOT appear in any DF set.
1026 #[test]
1027 fn self_loop_on_entry() {
1028 let mut f = Function::new("f".into(), vec![], IrType::Void);
1029 // entry → entry (always loops, no exit). Verifier doesn't run
1030 // here so an unreachable terminator is fine for the dom math.
1031 let cond = f.next_value_id();
1032 f.block_mut(f.entry).insts.push(Inst {
1033 id: cond,
1034 kind: InstKind::ConstBool(true),
1035 ty: IrType::Bool,
1036 span: dummy_span(),
1037 });
1038 let exit = f.create_block("exit");
1039 f.block_mut(f.entry).terminator = Some(Terminator::CondBranch {
1040 cond,
1041 true_dest: f.entry,
1042 true_args: vec![],
1043 false_dest: exit,
1044 false_args: vec![],
1045 });
1046 f.block_mut(exit).terminator = Some(Terminator::Return(None));
1047
1048 let idoms = compute_immediate_dominators(&f);
1049 assert!(
1050 !idoms.contains_key(&f.entry),
1051 "entry has no idom even with a self-edge"
1052 );
1053 assert_eq!(idoms[&exit], f.entry);
1054
1055 let df = compute_dominance_frontiers(&f);
1056 // The self-edge gives entry one in-edge (from itself); plus
1057 // the implicit "function entry edge" doesn't count, so entry
1058 // has 1 reachable pred. Not a join point — entry ∉ any DF.
1059 for (b, frontier) in &df {
1060 assert!(
1061 !frontier.contains(&f.entry),
1062 "entry should not appear in DF[{:?}]",
1063 b
1064 );
1065 }
1066 }
1067
1068 // ----- Edge case: self-loop on a non-entry block -----
1069 //
1070 // entry → b → b (b has both an entry edge and a self-edge,
1071 // so 2 reachable preds → join point.)
1072 // CFRWZ says b ∈ DF(b) here: b dominates itself (a pred of
1073 // itself) but does not strictly dominate itself.
1074 #[test]
1075 fn self_loop_on_non_entry_block_is_in_own_df() {
1076 let mut f = Function::new("f".into(), vec![], IrType::Void);
1077 let b = f.create_block("b");
1078 let exit = f.create_block("exit");
1079
1080 f.block_mut(f.entry).terminator = Some(Terminator::Branch(b, vec![]));
1081
1082 let cond = f.next_value_id();
1083 f.block_mut(b).insts.push(Inst {
1084 id: cond,
1085 kind: InstKind::ConstBool(true),
1086 ty: IrType::Bool,
1087 span: dummy_span(),
1088 });
1089 f.block_mut(b).terminator = Some(Terminator::CondBranch {
1090 cond,
1091 true_dest: b,
1092 true_args: vec![],
1093 false_dest: exit,
1094 false_args: vec![],
1095 });
1096 f.block_mut(exit).terminator = Some(Terminator::Return(None));
1097
1098 let df = compute_dominance_frontiers(&f);
1099 assert_eq!(
1100 df[&b],
1101 HashSet::from([b]),
1102 "b's self-edge puts b in its own dominance frontier"
1103 );
1104 let idoms = compute_immediate_dominators(&f);
1105 assert_eq!(idoms[&b], f.entry);
1106 assert_eq!(idoms[&exit], b);
1107 }
1108
1109 // ----- Edge case: irreducible CFG -----
1110 //
1111 // entry → a → b → a (cross-edge into the loop)
1112 // entry → b
1113 //
1114 // Both `a` and `b` have 2 preds, neither dominates the other,
1115 // and the loop has no single header. The dom math should still
1116 // produce a sensible answer: entry idom both, and each is in
1117 // the other's dominance frontier.
1118 #[test]
1119 fn irreducible_cfg_has_consistent_doms() {
1120 let mut f = Function::new("f".into(), vec![], IrType::Void);
1121 let a = f.create_block("a");
1122 let b = f.create_block("b");
1123 let exit = f.create_block("exit");
1124
1125 // entry → cond ? a : b
1126 let c0 = f.next_value_id();
1127 f.block_mut(f.entry).insts.push(Inst {
1128 id: c0,
1129 kind: InstKind::ConstBool(true),
1130 ty: IrType::Bool,
1131 span: dummy_span(),
1132 });
1133 f.block_mut(f.entry).terminator = Some(Terminator::CondBranch {
1134 cond: c0,
1135 true_dest: a,
1136 true_args: vec![],
1137 false_dest: b,
1138 false_args: vec![],
1139 });
1140
1141 // a → b
1142 f.block_mut(a).terminator = Some(Terminator::Branch(b, vec![]));
1143
1144 // b → cond ? a : exit (so b → a is a back edge into a, but
1145 // a is not the only header — entry → b
1146 // bypasses it).
1147 let c1 = f.next_value_id();
1148 f.block_mut(b).insts.push(Inst {
1149 id: c1,
1150 kind: InstKind::ConstBool(true),
1151 ty: IrType::Bool,
1152 span: dummy_span(),
1153 });
1154 f.block_mut(b).terminator = Some(Terminator::CondBranch {
1155 cond: c1,
1156 true_dest: a,
1157 true_args: vec![],
1158 false_dest: exit,
1159 false_args: vec![],
1160 });
1161 f.block_mut(exit).terminator = Some(Terminator::Return(None));
1162
1163 let idoms = compute_immediate_dominators(&f);
1164 // Neither a nor b dominates the other; entry idoms both.
1165 assert_eq!(idoms[&a], f.entry);
1166 assert_eq!(idoms[&b], f.entry);
1167 assert_eq!(idoms[&exit], b);
1168
1169 let df = compute_dominance_frontiers(&f);
1170 // a dominates a (a pred of b) → b ∈ DF(a) because a doesn't
1171 // strictly dominate b.
1172 assert!(df[&a].contains(&b), "b should be in DF(a)");
1173 // b dominates b (a pred of a) → a ∈ DF(b).
1174 assert!(df[&b].contains(&a), "a should be in DF(b)");
1175
1176 // dominator_tree_preorder must terminate and visit every
1177 // reachable block once (no infinite loop on the irreducible
1178 // back edge).
1179 let order = dominator_tree_preorder(&f);
1180 assert_eq!(order.len(), 4); // entry, a, b, exit
1181 assert_eq!(order[0], f.entry);
1182 }
1183 }
1184