Paper: A Simple, Fast Dominance Algorithm https://www.cs.rice.edu/~keith/EMBED/dom.pdf Note: requires nodes in reverse postorder If a result is None, that means the block is unreachable, and therefore has no idom.
(preds: &[Vec<usize>], reachable_blocks: &[bool])
| 88 | // Note: requires nodes in reverse postorder |
| 89 | // If a result is None, that means the block is unreachable, and therefore has no idom. |
| 90 | fn compute_idom(preds: &[Vec<usize>], reachable_blocks: &[bool]) -> Vec<Option<usize>> { |
| 91 | fn intersect(doms: &[Option<usize>], mut finger1: usize, mut finger2: usize) -> usize { |
| 92 | // TODO: This may return an optional result? |
| 93 | while finger1 != finger2 { |
| 94 | // Note: The comparisons here are inverted from the paper, because the paper uses |
| 95 | // comparison to be postorder index. However, we have reverse postorder indices. |
| 96 | while finger1 > finger2 { |
| 97 | finger1 = doms[finger1].unwrap(); |
| 98 | } |
| 99 | while finger2 > finger1 { |
| 100 | finger2 = doms[finger2].unwrap(); |
| 101 | } |
| 102 | } |
| 103 | finger1 |
| 104 | } |
| 105 | |
| 106 | let mut idom = vec![None; preds.len()]; |
| 107 | idom[0] = Some(0); |
| 108 | let mut changed = true; |
| 109 | while changed { |
| 110 | changed = false; |
| 111 | // Unreachable blocks have no preds, and therefore no idom |
| 112 | for node in (1..(preds.len())).filter(|&i| reachable_blocks[i]) { |
| 113 | let mut new_idom: Option<usize> = None; |
| 114 | for &pred in &preds[node] { |
| 115 | if idom[pred].is_some() { |
| 116 | new_idom = |
| 117 | Some(new_idom.map_or(pred, |new_idom| intersect(&idom, pred, new_idom))); |
| 118 | } |
| 119 | } |
| 120 | // TODO: This may return an optional result? |
| 121 | let new_idom = new_idom.unwrap(); |
| 122 | if idom[node] != Some(new_idom) { |
| 123 | idom[node] = Some(new_idom); |
| 124 | changed = true; |
| 125 | } |
| 126 | } |
| 127 | } |
| 128 | assert!( |
| 129 | idom.iter() |
| 130 | .enumerate() |
| 131 | .all(|(i, x)| x.is_some() == reachable_blocks[i]) |
| 132 | ); |
| 133 | idom |
| 134 | } |
| 135 | |
| 136 | // Same paper as above |
| 137 | fn compute_dominance_frontier( |