| Safe Haskell | None |
|---|
LLVM.Analysis.CDG
Contents
Description
Control Dependence Graphs for the LLVM IR
This module follows the definition of control dependence of Cytron et al (http:dl.acm.org/citation.cfm?doid=115372.115320):
Let X and Y be nodes in the CFG. If X appears on every path from Y to Exit, then X postdominates Y. If X postdominates Y but X != Y, then X strictly postdominates Y.
A CFG node Y is control dependent on a CFG node X if both:
- There is a non-null path p from X->Y such that Y postdominates every node *after* X on p.
- The node Y does not strictly postdominate the node X.
This CDG formulation does not insert a dummy Start node to link together all of the top-level nodes. This just means that the set of control dependencies can be empty if code will be executed unconditionally.
- data CDG
- class HasCDG a where
- controlDependenceGraph :: CFG -> CDG
- directControlDependencies :: CDG -> Instruction -> [Instruction]
- controlDependencies :: CDG -> Instruction -> [Instruction]
- controlDependentOn :: CDG -> Instruction -> Instruction -> Bool
- cdgGraphvizRepr :: CDG -> DotGraph Vertex
Types
Constructor
controlDependenceGraph :: CFG -> CDGSource
Construct the control dependence graph for a function (from its CFG). This follows the construction from chapter 9 of the Munchnick Compiler Design and Implementation book.
For an input function F:
1) Construct the CFG G for F
2) Construct the postdominator tree PT for F
3) Let S be the set of edges m->n in G such that n does not postdominate m
4) For each edge m->n in S, find the lowest common ancestor l of m and n in the postdominator tree. All nodes on the path from l->n (not including l) in PT are control dependent on m.
Note: the typical construction augments the CFG with a fake start node. Doing that here would be a bit complicated, so the graph just isn't connected by a fake Start node.
Queries
directControlDependencies :: CDG -> Instruction -> [Instruction]Source
Get the list of instructions that i is directly control
dependent upon.
controlDependencies :: CDG -> Instruction -> [Instruction]Source
Get the list of instructions that i is control dependent upon.
This list does not include i. As noted above, the list will be
empty if i is executed unconditionally.
controlDependences cdg i
controlDependentOn :: CDG -> Instruction -> Instruction -> BoolSource
Return True if n is control dependent on m.
controlDependentOn cdg m n
Visualization
cdgGraphvizRepr :: CDG -> DotGraph VertexSource