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