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.
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. If there is no common ancestor (disconnected PDT because of multiple exit nodes), the lowest common ancestor is then the virtual exit node, so all of the postdominators of n 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.
Get the list of instructions that an instruction is directly control dependent upon (direct parents in the CDG).