GHC.Cmm.Dominators

Dominator analysis and representation of results

data DominatorSet

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.

Constructors

ImmediateDominator

Fields

• ds_label :: Label

  Label of the immediate dominator.

• ds_parent :: DominatorSet

  Set of nodes dominating the immediate dominator.

EntryNode

Instances

Outputable DominatorSet

Defined in GHC.Cmm.Dominators

Methods

ppr :: DominatorSet -> SDoc

Eq DominatorSet

Defined in GHC.Cmm.Dominators

Methods

(==) :: DominatorSet -> DominatorSet -> Bool

(/=) :: DominatorSet -> DominatorSet -> Bool

data GraphWithDominators node

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.

Constructors

GraphWithDominators

Fields

• gwd_graph :: GenCmmGraph node
• gwd_dominators :: LabelMap DominatorSet
• gwd_rpnumbering :: LabelMap RPNum

data RPNum

Reverse postorder number of a node in a CFG

Instances

Show RPNum

Defined in GHC.Cmm.Dominators

Methods

showsPrec :: Int -> RPNum -> ShowS

show :: RPNum -> String

showList :: [RPNum] -> ShowS

Outputable RPNum

Defined in GHC.Cmm.Dominators

Methods

ppr :: RPNum -> SDoc

Eq RPNum

Defined in GHC.Cmm.Dominators

Methods

(==) :: RPNum -> RPNum -> Bool

(/=) :: RPNum -> RPNum -> Bool

Ord RPNum

Defined in GHC.Cmm.Dominators

Methods

compare :: RPNum -> RPNum -> Ordering

(<) :: RPNum -> RPNum -> Bool

(<=) :: RPNum -> RPNum -> Bool

(>) :: RPNum -> RPNum -> Bool

(>=) :: RPNum -> RPNum -> Bool

max :: RPNum -> RPNum -> RPNum

min :: RPNum -> RPNum -> RPNum

graphWithDominators :: forall node. (NonLocal node, HasDebugCallStack) => GenCmmGraph node -> GraphWithDominators node

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 on graphs or graphs-with-dominators

graphMap :: GenCmmGraph n -> LabelMap (Block n C C)

Utility functions

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

gwdRPNumber :: HasDebugCallStack => GraphWithDominators node -> Label -> RPNum

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.

gwdDominatorsOf :: HasDebugCallStack => GraphWithDominators node -> Label -> DominatorSet

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.

gwdDominatorTree :: GraphWithDominators node -> Tree Label

Utility functions on dominator sets

dominatorsMember :: Label -> DominatorSet -> Bool

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.

intersectDominators :: DominatorSet -> DominatorSet -> DominatorSet

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.