Control flow graph¶
Reference¶
Control flow graph algorithms.
Functions present:
- dominators
- post dominators
- reachability
- dominator tree
- dominance frontier
-
class
ppci.graph.cfg.
ControlFlowGraph
¶ Control flow graph.
Has methods to query properties of the control flow graph and its nodes.
Such as: - Dominators - Strict dominators - Immediate dominators - Post dominators - Strict post dominators - Immediate post dominators - Reachable nodes - Loops
-
bottom_up
(tree)¶ Generator that yields all nodes in bottom up way
-
calculate_dominance_frontier
()¶ Calculate the dominance frontier.
Algorithm from Ron Cytron et al.
how to calculate the dominance frontier for all nodes using the dominator tree.
-
calculate_loops
()¶ Calculate loops by use of the dominator info
-
calculate_reach
()¶ Calculate which nodes can reach what other nodes
-
children
(n)¶ Return all children for node n
-
dominates
(one, other)¶ Test whether a node dominates another node.
To test this, use the dominator tree, check where of the other node is below the one node in the tree by comparing discovery and finish intervals.
-
get_immediate_dominator
(node)¶ Retrieve a nodes immediate dominator
-
get_immediate_post_dominator
(node)¶ Retrieve a nodes immediate post dominator
-
post_dominates
(one, other)¶ Test whether a node post dominates another node
-
strictly_dominates
(one, other)¶ Test whether a node strictly dominates another node
-
validate
()¶ Run some sanity checks on the control flow graph
-
-
class
ppci.graph.cfg.
ControlFlowNode
(graph, name=None)¶ -
can_reach
(other)¶ Test if this node can reach the another node
-
dominates
(other)¶ Test whether this node dominates the other node
-
post_dominates
(other)¶ Test whether this node post-dominates the other node
-
reached
()¶ Test if this node is reached
-
-
class
ppci.graph.cfg.
DomTreeNode
(node, children, interval)¶ A single node in the dominator tree.
-
below
(other)¶ Test if this node is a descendant of this node.
-
below_or_same
(other)¶ Test if this node is a descendant of this node (or is self)
-
-
class
ppci.graph.cfg.
Loop
(header, rest)¶ -
header
¶ Alias for field number 0
-
rest
¶ Alias for field number 1
-
-
ppci.graph.cfg.
bottom_up
(tree)¶ Generator that yields all nodes in bottom up way
-
ppci.graph.cfg.
bottom_up_recursive
(tree)¶ Generator that yields all nodes in bottom up way
-
ppci.graph.cfg.
ir_function_to_graph
(ir_function)¶ Take an ir function and create a cfg of it
-
ppci.graph.cfg.
pre_order
(tree)¶ Traverse tree in pre-order