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

Methods

showsPrec :: Int -> CFG -> ShowS

show :: CFG -> String

showList :: [CFG] -> ShowS

type BB = BasicBlock' (BBId, BlockLabel)

data BBId

Instances

Eq BBId

Methods

(==) :: BBId -> BBId -> Bool

(/=) :: BBId -> BBId -> Bool

Show BBId

Methods

showsPrec :: Int -> BBId -> ShowS

show :: BBId -> String

showList :: [BBId] -> ShowS

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