Data.LLVM.CFG

Point-of-contact : jstanley

Documentation

data CFG

The control-flow graph for LLVM functions

Constructors

CFG

Fields

cfgGraph :: Gr BB ()

entryId :: BBId

The BBId of the entry node in the control-flow graph

exitId :: BBId

The BBId of the exit node from the control-flow graph

allBBs :: [BB]

All basic blocks in the CFG

bbById :: BBId -> BB

Obtain a basic block from a BBId (runtime error if it DNE)

asId :: BlockLabel -> BBId

Obtain the BBId of a block from its name (runtime error if it DNE)

asName :: BBId -> BlockLabel

Obtain the name of a block from a BBId (runtime error if it DNE)

bbPreds :: BBId -> [BBId]

Obtain all predecessor basic blocks from a BBId

bbSuccs :: BBId -> [BBId]

Obtain all successor basic blocks from a BBId

dom :: BBId -> BBId -> Bool

dom x y yields True iff x dominates y in the CFG (i.e., all paths from the entry node to y must pass through x)

idom :: BBId -> Maybe BBId

idom x yields the unique immediate dominator of x in the CFG (intuitively, the "nearest" dominator of x; formally, y immediately dominates x iff y dominates x and there is no intervening block z such that y dominates z and z dominates x). The entry node has no immediate dominator.

pdom :: BBId -> BBId -> Bool

pdom x y yields True iff x postdominates y in the CFG (i.e., all paths in the CFG from y to the exit node pass through x)

ipdom :: BBId -> Maybe BBId

ipdom x yields the unique immediate postdominator of x in the CFG (intuitively, the "nearest" postdominator; formally, y immediately postdominates x iff y postdominates x and there is no intervening block z such that y postdominates z and z postdominates x). The exit node has no immediate postdominator.

pdoms :: [(BBId, [BBId])]

pdom yields post-dominator analysis for the entire CFG; the resulting list associates each node with a list of its postdominators. The postdominator list is sorted in order of ascending immediacy; i.e., the last element of the list associated with a node n is n's immediate dominator, the penultimate element of the list is the immediate postdominator of n's immediate postdominator, and so forth. NB: note the postdominator lists do not explicitly reflect that a node postdominates itself.

Instances

Show CFG

type BB = BasicBlock' (BBId, BlockLabel)

data BBId

Instances

Eq BBId

Show BBId

blockId :: BB -> BBId

blockName :: BB -> BlockLabel

buildCFG :: [BasicBlock] -> CFG

Builds the control-flow graph of a function. Assumes that the entry node is the first basic block in the list. Note that when multiple exit nodes are present in the list, they will all end up connected to a single, unique "dummy" exit node. Note, also, that the CFG basic blocks are of type BasicBlock' (BBId, Ident); that is, they are all named, which is not the case with the input BBs. It is expected that clients use these versions of the basic blocks rather than those that are passed in.

dummyExitName :: String