| 464 | } |
| 465 | |
| 466 | fn compute_domtree(&mut self, cfg: &ControlFlowGraph) { |
| 467 | // Compute semi-dominators. |
| 468 | for w in (1..self.stree.len() as u32).rev() { |
| 469 | let w_node = &mut self.stree[w]; |
| 470 | let block = w_node.block.expect("Virtual root must have been excluded"); |
| 471 | let mut semi = w_node.ancestor; |
| 472 | |
| 473 | let last_linked = w + 1; |
| 474 | |
| 475 | for pred in cfg |
| 476 | .pred_iter(block) |
| 477 | .map(|pred: BlockPredecessor| pred.block) |
| 478 | { |
| 479 | // Skip unreachable nodes. |
| 480 | if self.nodes[pred].pre_number == NOT_VISITED { |
| 481 | continue; |
| 482 | } |
| 483 | |
| 484 | let semi_candidate = self.eval(self.nodes[pred].pre_number, last_linked); |
| 485 | semi = core::cmp::min(semi, semi_candidate); |
| 486 | } |
| 487 | |
| 488 | let w_node = &mut self.stree[w]; |
| 489 | w_node.label = semi; |
| 490 | w_node.semi = semi; |
| 491 | } |
| 492 | |
| 493 | // Compute immediate dominators. |
| 494 | for v in 1..self.stree.len() as u32 { |
| 495 | let semi = self.stree[v].semi; |
| 496 | let block = self.stree[v] |
| 497 | .block |
| 498 | .expect("Virtual root must have been excluded"); |
| 499 | let mut idom = self.stree[v].idom; |
| 500 | |
| 501 | while idom > semi { |
| 502 | idom = self.stree[idom].idom; |
| 503 | } |
| 504 | |
| 505 | self.stree[v].idom = idom; |
| 506 | |
| 507 | self.nodes[block].idom = self.stree[idom].block; |
| 508 | } |
| 509 | } |
| 510 | |
| 511 | /// Compute dominator tree preorder information. |
| 512 | /// |