GHC.Cmm.Dominators

Dominator sets

Node X dominates node Y if and only if every path from the entry to Y includes X. Node Y technically dominates itself, but it is never included in the *representation* of its dominator set.

A dominator set is represented as a linked list in which each node points to its *immediate* dominator, which is its parent in the dominator tree. In many circumstances the immediate dominator will be the only dominator of interest.

The result of dominator analysis. Also includes a reverse postorder numbering, which is needed for dominator analysis and for other (downstream) analyses.

Invariant: Dominators, graph, and RP numberings include only *reachable* blocks.

Reverse postorder number of a node in a CFG

Call this function with a CmmGraph to get back the results of a dominator analysis of that graph (as well as a reverse postorder numbering). The result also includes the subgraph of the original graph that contains only the reachable blocks.

Utility functions

Call graphMap to get the mapping from Label to Block that is embedded in every CmmGraph.

Use gwdRPNumber on the result of the dominator analysis to get a mapping from the Label of each reachable block to the reverse postorder number of that block.

Use gwdDominatorsOf on the result of the dominator analysis to get a mapping from the Label of each reachable block to the dominator set (and the immediate dominator) of that block. The implementation is space-efficient: intersecting dominator sets share the representation of their intersection.

Use to tell if the given label is in the given dominator set. Which is to say, does the bloc with with given label _properly_ and _non-vacuously_ dominate the node whose dominator set this is?

Takes linear time in the height of the dominator tree, but uses space efficiently.

Intersect two dominator sets to produce a third dominator set. This function takes time linear in the size of the sets. As such it is inefficient and should be used only for things like visualizations or linters.