LLVM.Analysis.CDG

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.

Types

data CDG

Instances

HasFunction CDG

ToGraphviz CDG

HasCFG CDG

HasPostdomTree CDG

HasCDG CDG

class HasCDG a where

Methods

getCDG :: a -> CDG

Instances

HasCDG PostdominatorTree

Warning, this is an expensive instance to invoke as it constructs the CDG.

HasCDG CDG

Constructor

controlDependenceGraph :: (HasCFG f, HasPostdomTree f) => f -> CDG

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.

Queries

directControlDependencies :: HasCDG cdg => cdg -> Instruction -> [Instruction]

Get the list of instructions that an instruction is directly control dependent upon (direct parents in the CDG).

controlDependencies :: HasCDG cdg => cdg -> Instruction -> [Instruction]

Get the list of instructions that an instruction is control dependent upon. As noted above, the list will be empty if the instruction is executed unconditionally.