Build a dominator tree from a control flow graph using Keith D. Cooper's "Simple, Fast Dominator Algorithm."
(&mut self, func: &Function, cfg: &ControlFlowGraph)
| 255 | /// Build a dominator tree from a control flow graph using Keith D. Cooper's |
| 256 | /// "Simple, Fast Dominator Algorithm." |
| 257 | fn compute_domtree(&mut self, func: &Function, cfg: &ControlFlowGraph) { |
| 258 | // During this algorithm, `rpo_number` has the following values: |
| 259 | // |
| 260 | // 0: block is not reachable. |
| 261 | // 1: block is reachable, but has not yet been visited during the first pass. This is set by |
| 262 | // `compute_postorder`. |
| 263 | // 2+: block is reachable and has an assigned RPO number. |
| 264 | |
| 265 | // We'll be iterating over a reverse post-order of the CFG, skipping the entry block. |
| 266 | let (entry_block, postorder) = match self.postorder.as_slice().split_last() { |
| 267 | Some((&eb, rest)) => (eb, rest), |
| 268 | None => return, |
| 269 | }; |
| 270 | debug_assert_eq!(Some(entry_block), func.layout.entry_block()); |
| 271 | |
| 272 | // Do a first pass where we assign RPO numbers to all reachable nodes. |
| 273 | self.nodes[entry_block].rpo_number = 2 * STRIDE; |
| 274 | for (rpo_idx, &block) in postorder.iter().rev().enumerate() { |
| 275 | // Update the current node and give it an RPO number. |
| 276 | // The entry block got 2, the rest start at 3 by multiples of STRIDE to leave |
| 277 | // room for future dominator tree modifications. |
| 278 | // |
| 279 | // Since `compute_idom` will only look at nodes with an assigned RPO number, the |
| 280 | // function will never see an uninitialized predecessor. |
| 281 | // |
| 282 | // Due to the nature of the post-order traversal, every node we visit will have at |
| 283 | // least one predecessor that has previously been visited during this RPO. |
| 284 | self.nodes[block] = DomNode { |
| 285 | idom: self.compute_idom(block, cfg).into(), |
| 286 | rpo_number: (rpo_idx as u32 + 3) * STRIDE, |
| 287 | } |
| 288 | } |
| 289 | |
| 290 | // Now that we have RPO numbers for everything and initial immediate dominator estimates, |
| 291 | // iterate until convergence. |
| 292 | // |
| 293 | // If the function is free of irreducible control flow, this will exit after one iteration. |
| 294 | let mut changed = true; |
| 295 | while changed { |
| 296 | changed = false; |
| 297 | for &block in postorder.iter().rev() { |
| 298 | let idom = self.compute_idom(block, cfg).into(); |
| 299 | if self.nodes[block].idom != idom { |
| 300 | self.nodes[block].idom = idom; |
| 301 | changed = true; |
| 302 | } |
| 303 | } |
| 304 | } |
| 305 | } |
| 306 | |
| 307 | // Compute the immediate dominator for `block` using the current `idom` states for the reachable |
| 308 | // nodes. |
no test coverage detected