armfortas Public

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