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

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)
children

Alias for field number 1

node

Alias for field number 0

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