Safe Haskell | Safe-Inferred |
---|---|
Language | Haskell2010 |
Synopsis
- data DominatorSet
- = ImmediateDominator { }
- | EntryNode
- data GraphWithDominators node = GraphWithDominators {}
- data RPNum
- graphWithDominators :: forall node. (NonLocal node, HasDebugCallStack) => GenCmmGraph node -> GraphWithDominators node
- graphMap :: GenCmmGraph n -> LabelMap (Block n C C)
- gwdRPNumber :: HasDebugCallStack => GraphWithDominators node -> Label -> RPNum
- gwdDominatorsOf :: HasDebugCallStack => GraphWithDominators node -> Label -> DominatorSet
- gwdDominatorTree :: GraphWithDominators node -> Tree Label
- dominatorsMember :: Label -> DominatorSet -> Bool
- intersectDominators :: DominatorSet -> DominatorSet -> DominatorSet
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.
ImmediateDominator | |
| |
EntryNode |
Instances
Outputable DominatorSet Source # | |
Defined in GHC.Cmm.Dominators ppr :: DominatorSet -> SDoc Source # | |
Eq DominatorSet Source # | |
Defined in GHC.Cmm.Dominators (==) :: DominatorSet -> DominatorSet -> Bool # (/=) :: DominatorSet -> DominatorSet -> Bool # |
data GraphWithDominators node 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.
Reverse postorder number of a node in a CFG
graphWithDominators :: forall node. (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
gwdRPNumber :: 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 :: 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.
gwdDominatorTree :: GraphWithDominators node -> Tree Label Source #
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.