ghc-9.8.0.20230919: The GHC API
Safe HaskellNone
LanguageHaskell2010

GHC.Cmm.Dominators

Synopsis

Dominator analysis and representation of results

data DominatorSet Source #

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

EntryNode 

Instances

Instances details
Outputable DominatorSet Source # 
Instance details

Defined in GHC.Cmm.Dominators

Eq DominatorSet Source # 
Instance details

Defined in GHC.Cmm.Dominators

data GraphWithDominators (node :: Extensibility -> Extensibility -> Type) Source #

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.

data RPNum Source #

Reverse postorder number of a node in a CFG

Instances

Instances details
Show RPNum Source # 
Instance details

Defined in GHC.Cmm.Dominators

Outputable RPNum Source # 
Instance details

Defined in GHC.Cmm.Dominators

Methods

ppr :: RPNum -> SDoc Source #

Eq RPNum Source # 
Instance details

Defined in GHC.Cmm.Dominators

Methods

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

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

Ord RPNum Source # 
Instance details

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 :: Extensibility -> Extensibility -> Type). (NonLocal node, HasDebugCallStack) => GenCmmGraph node -> GraphWithDominators node Source #

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 :: forall (n :: Extensibility -> Extensibility -> Type). GenCmmGraph n -> LabelMap (Block n C C) Source #

Utility functions

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

gwdRPNumber :: forall (node :: Extensibility -> Extensibility -> Type). HasDebugCallStack => GraphWithDominators node -> Label -> RPNum Source #

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 :: forall (node :: Extensibility -> Extensibility -> Type). HasDebugCallStack => GraphWithDominators node -> Label -> DominatorSet Source #

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.

Utility functions on dominator sets

dominatorsMember :: Label -> DominatorSet -> Bool Source #

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 Source #

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.