Safe Haskell | None |
---|

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 :: (HasCFG f, HasPostdomTree f) => f -> CDG
- directControlDependencies :: HasCDG cdg => cdg -> Instruction -> [Instruction]
- controlDependencies :: HasCDG cdg => cdg -> Instruction -> [Instruction]

# Types

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

HasCDG CDG |

# Constructor

controlDependenceGraph :: (HasCFG f, HasPostdomTree f) => f -> 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. 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]Source

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

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

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.