`DomTree` should be parameterized to compute post-dominator info

[vaivaswatha]

LLVM's GenericDomTreeConstruction handles this.

Possible issues to consider:

1. Without a single exit block, a "virtual" exit block (that the existing exit blocks will flow into) should be considered.
2. For blocks that never exit (infinite loops), find the "furthest" block and consider that as an exit node.

Below is an AI analysis of how this works in LLVM:

How does the post-dominators analysis here handle CFGs with multiple exits ?
(that is no single "entry" for the reverse CFG)

Virtual Root

For post-dominators, a virtual root node is created, mapped to nullptr (no real basic block). This synthetic node acts as the single entry of the reverse CFG, absorbing all real exits. This is why:

• Roots is declared as SmallVector<NodeT *, IsPostDom ? 4 : 1> — it can hold multiple real exit blocks.
• isVirtualRoot() checks isPostDominator() && !A->getBlock().
• The doc comment on getRootNode() warns consumers: "this root may be a node with block == NULL... when there are multiple exit nodes".

Root Discovery (FindRoots in GenericDomTreeConstruction.h)

Because there's no single entry for the reverse CFG, FindRoots (line ~350) runs a multi-phase search:

1. Trivial roots (line ~374): Nodes with no forward successors (real ret/exit blocks) are immediately added as roots. DFS is run from each to mark reachable nodes.

2. Non-trivial roots (line ~399): For nodes not reached by any trivial-root DFS — i.e., nodes in infinite loops with no path to any exit — the algorithm:

   • Does a forward DFS to find the "furthest away" node in the loop.
   • Adds that node as a root.
   • This matches GCC's behavior for giving a reasonable (though not necessarily minimal) post-dom answer inside infinite loops.

3. Redundant root removal (RemoveRedundantRoots, line ~510): Among non-trivial roots, any root that is reverse-reachable from another root is dropped, keeping the set non-redundant.

Tree Construction

In CalculateFromScratch (line ~575):

• The SemiNCA algorithm runs with nullptr as the virtual root at DFS index 0, and all discovered real roots at DFS index ≥ 1.
• Root = IsPostDom ? nullptr : DT.Roots[0] — the tree root is always the virtual node.
• attachNewSubtree sets the IDom of each real root's subtree top to nullptr (the virtual root), making all exit blocks (and infinite-loop roots) direct children of it.

Summary

Virtual Root (nullptr)
├── ExitBlock1        ← trivial root (no successors)
│   └── ...
├── ExitBlock2        ← trivial root
│   └── ...
└── InfiniteLoopNode  ← non-trivial root (node in a loop with no exit)
    └── ...

All real exit blocks become children of the virtual root in the post-dominator tree. Nodes in infinite loops get a synthetic root chosen by the "furthest away" heuristic. Callers must handle the block == nullptr root case, as the comment in GenericDomTree.h explicitly notes.