Compute dominator tree preorder information. This populates child/sibling links and preorder numbers for fast dominance checks.
(&mut self)
| 512 | /// |
| 513 | /// This populates child/sibling links and preorder numbers for fast dominance checks. |
| 514 | fn compute_domtree_preorder(&mut self) { |
| 515 | // Populate the child and sibling links. |
| 516 | // |
| 517 | // By following the CFG post-order and pushing to the front of the lists, we make sure that |
| 518 | // sibling lists are ordered according to the CFG reverse post-order (i.e. decreasing CFG |
| 519 | // post-order number). |
| 520 | for &block in &self.postorder { |
| 521 | if let Some(idom) = self.idom(block) { |
| 522 | let sib = mem::replace(&mut self.nodes[idom].child, block.into()); |
| 523 | self.nodes[block].sibling = sib; |
| 524 | } else { |
| 525 | // The only block without an immediate dominator is the entry. |
| 526 | self.dfs_worklist.push(TraversalEvent::Enter(0, block)); |
| 527 | } |
| 528 | } |
| 529 | |
| 530 | // Assign pre-order numbers from a DFS of the dominator tree. |
| 531 | debug_assert!(self.dfs_worklist.len() <= 1); |
| 532 | let mut n = 0; |
| 533 | while let Some(event) = self.dfs_worklist.pop() { |
| 534 | if let TraversalEvent::Enter(_, block) = event { |
| 535 | n += 1; |
| 536 | let node = &mut self.nodes[block]; |
| 537 | node.dom_pre_number = n; |
| 538 | node.dom_pre_max = n; |
| 539 | if let Some(sibling) = node.sibling.expand() { |
| 540 | self.dfs_worklist.push(TraversalEvent::Enter(0, sibling)); |
| 541 | } |
| 542 | if let Some(child) = node.child.expand() { |
| 543 | self.dfs_worklist.push(TraversalEvent::Enter(0, child)); |
| 544 | } |
| 545 | } |
| 546 | } |
| 547 | |
| 548 | // Propagate the `dom_pre_max` numbers up the tree. |
| 549 | // The CFG post-order is topologically ordered w.r.t. dominance so a node comes after all |
| 550 | // its dominator tree children. |
| 551 | for &block in &self.postorder { |
| 552 | if let Some(idom) = self.idom(block) { |
| 553 | let pre_max = cmp::max(self.nodes[block].dom_pre_max, self.nodes[idom].dom_pre_max); |
| 554 | self.nodes[idom].dom_pre_max = pre_max; |
| 555 | } |
| 556 | } |
| 557 | } |
| 558 | } |
| 559 | |
| 560 | /// An iterator that enumerates the direct children of a block in the dominator tree. |