| Safe Haskell | None |
|---|
LLVM.Analysis.Dominance
Contents
Description
Tools to compute dominance information for functions. Includes postdominators.
A node m postdominates a node n iff every path from n to
exit passes through m.
This implementation is based on the dominator implementation in fgl, which is based on the algorithm from Cooper, Harvey, and Kennedy:
http:www.cs.rice.edu~keithEmbed/dom.pdf
- data DominatorTree
- data PostdominatorTree
- class HasDomTree a where
- getDomTree :: a -> DominatorTree
- class HasPostdomTree a where
- getPostdomTree :: a -> PostdominatorTree
- dominators :: CFG -> [(Instruction, [Instruction])]
- immediateDominators :: CFG -> [(Instruction, Instruction)]
- postdominators :: RCFG -> [(Instruction, [Instruction])]
- immediatePostdominators :: RCFG -> [(Instruction, Instruction)]
- dominatorTree :: CFG -> DominatorTree
- postdominatorTree :: RCFG -> PostdominatorTree
- dominates :: DominatorTree -> Instruction -> Instruction -> Bool
- postdominates :: PostdominatorTree -> Instruction -> Instruction -> Bool
- nearestCommonPostdominator :: PostdominatorTree -> Instruction -> Instruction -> Maybe Instruction
- instructionPostdominators :: PostdominatorTree -> Instruction -> [Instruction]
- domTreeGraphvizRepr :: DominatorTree -> DotGraph Vertex
- postdomTreeGraphvizRepr :: PostdominatorTree -> DotGraph Vertex
Types
data DominatorTree Source
The standard dominator tree
data PostdominatorTree Source
The dominator tree of the reversed CFG.
Constructors
dominators :: CFG -> [(Instruction, [Instruction])]Source
Compute the full set of dominators for the given CFG
immediateDominators :: CFG -> [(Instruction, Instruction)]Source
Compute the immediate dominators for a given CFG
postdominators :: RCFG -> [(Instruction, [Instruction])]Source
Get a mapping from Instructions to each of their postdominators
immediatePostdominators :: RCFG -> [(Instruction, Instruction)]Source
dominatorTree :: CFG -> DominatorTreeSource
Construct a dominator tree from a CFG
postdominatorTree :: RCFG -> PostdominatorTreeSource
Construct a postdominator tree from a reversed CFG
Queries
dominates :: DominatorTree -> Instruction -> Instruction -> BoolSource
Check whether n dominates m
postdominates :: PostdominatorTree -> Instruction -> Instruction -> BoolSource
Check whether n postdominates m
postdominates pdt n m
n postdominates m if there is a path from n to m in the postdominator tree.
nearestCommonPostdominator :: PostdominatorTree -> Instruction -> Instruction -> Maybe InstructionSource
Given two instructions, find their nearest common postdominator. This uses a DFS search from each instruction to the root.
instructionPostdominators :: PostdominatorTree -> Instruction -> [Instruction]Source
Compute the transitive postdominators of a single Instruction. Instructions postdominate themselves, and the list of postdominators begins with the input instruction and ends with the root of the postdominator tree (usually the ret node).
Visualization
domTreeGraphvizRepr :: DominatorTree -> DotGraph VertexSource
postdomTreeGraphvizRepr :: PostdominatorTree -> DotGraph VertexSource