| 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); |