home blog microblog favorites pl resources bread recipes rss

Tree numbering

Diagram from *Validating Dominator Trees for a Fast, Verified Dominance Test* by Blazy, Demange, and Pichardie showing a CFG, its domtree, and reverse post-order interval numbering of its domtree.
Figure and below caption from Validating Dominator Trees for a Fast, Verified Dominance Test (PDF) by Blazy, Demange, and Pichardie.

Left: example CFG, with entry point 17, and nodes ordered in reverse post-order (on the left). Center: its dominator tree (where, if i has j as a child, then i is the immediate dominator of j). Right: dominator tree (solid arrows), annotated with a DFS traversal (dotted arrows), and its corresponding DFS intervals.

See also paren_repr.py.