Control Flow Graph

The pyTooling.ControlFlow package describes the control flow graph of a function: its basic blocks and the edges control takes between them. A ControlFlowGraph describes one function - a C or C++ function, or a Python code object. The calls between functions are described by a call graph.

Features

A graph has an entry and an exit block, and optionally an unwind block, through which an exception leaves the function.
A block is looked up by its ID: graph.GetBlock(3) and graph.ContainsBlock(3); graph.IterateBlocks() yields all blocks, graph.BlockCount counts them.
Every edge has a kind, given as an EdgeKind member.
Blocks and edges carry an optional execution count and an optional value of any type, e.g. source lines or a case label.
Graphs, blocks and edges carry key-value pairs, e.g. the results of an analysis under a key of its choice: block["dominator"] = graph.Entry. Their dunder methods (len, in, [], del, iteration) serve these pairs, as in pyTooling.Graph.
ToGraph() converts a control flow graph into a Graph, so it can be written as GraphML or Graphviz DOT, or analysed by the graph algorithms.

Out of Scope

Call graphs and interprocedural edges from a call to the callee’s entry: a call is part of a block, and a call graph refers to that block as the call’s call site.
Parsing source code or byte code into a control flow graph.

Basic Blocks

A BasicBlock is a sequence of code, which control enters at its top and leaves at its bottom. Its ID is unique within its graph, e.g. a compiler’s block number or a line number. A graph creates its entry and exit block, with the IDs "entry" and "exit" unless others are given. Every further block is created with the graph it belongs to:

from pyTooling.ControlFlow import ControlFlowGraph, BasicBlock, BlockKind

graph =  ControlFlowGraph("Sum", entryID=0, exitID=1)
init =   BasicBlock(graph, 2, count=1, value="int s = 0;")
unwind = BasicBlock(graph, "unwind", kind=BlockKind.Unwind)

Block kinds

`BlockKind`	Meaning
`Code`	A block of code.
`Entry`	Control enters the function here. A graph has exactly one.
`Exit`	Control leaves the function here when it returns. A graph has exactly one.
`Unwind`	An exception no handler of the function catches leaves the function here. A graph has at most one.

Edges

An Edge leads from a block to a block control continues with. A block with several outbound edges branches; a switch has an edge per target. Two blocks can be connected by edges of different kinds, but only by one edge of each kind. No edge leads to the entry block, and none leaves the exit or unwind block.

An edge is created by its constructor, or from one of its blocks, as in pyTooling.Graph:

Edge(graph.Entry, body, EdgeKind.FallThrough, count=3)
graph.Entry.EdgeTo(body, 3, edgeKind=EdgeKind.FallThrough)       # the same edge
graph.Exit.EdgeFrom(body, edgeKind=EdgeKind.Jump)

Edge kinds

`EdgeKind`	Meaning
`Default`	Not classified, e.g. an arc between two lines a code coverage tool reports.
`FallThrough`	Control continues with the next block in code order.
`Jump`	Control jumps: a taken branch, a `goto`, `break` or `continue`, or a `switch` case.
`Exception`	An exception leaves the block, to a handler or to the unwind block.
`Abnormal`	Control leaves the block without a jump or an exception, e.g. by calling `exit()` or `longjmp()`.

Exceptions

An exception is an Exception edge: to the block of the handler catching it, or - if no handler in the function does - to the unwind block. A Python finally clause is a block on both paths: on the exceptional path, it ends with an Exception edge, and a return inside it is an edge to the exit block.

from pyTooling.ControlFlow import ControlFlowGraph, BasicBlock, Edge, BlockKind, EdgeKind

# def Read(path):
#   try:
#     data = load(path)
#   except OSError:
#     data = None
#   finally:
#     close()
#   return data
graph =   ControlFlowGraph("Read")
body =    BasicBlock(graph, 3, value="data = load(path)")
handler = BasicBlock(graph, 5, value="data = None")
normal =  BasicBlock(graph, 7, value="close()")
pending = BasicBlock(graph, 107, value="close()")
ret =     BasicBlock(graph, 8, value="return data")
unwind =  BasicBlock(graph, "unwind", kind=BlockKind.Unwind)

Edge(graph.Entry, body, EdgeKind.FallThrough)
Edge(body, normal, EdgeKind.FallThrough)
Edge(body, handler, EdgeKind.Exception, value="OSError")
Edge(body, pending, EdgeKind.Exception)
Edge(handler, normal, EdgeKind.FallThrough)
Edge(normal, ret, EdgeKind.FallThrough)
Edge(ret, graph.Exit, EdgeKind.Jump)
Edge(pending, unwind, EdgeKind.Exception)

A C++ throw is modelled the same way: an Exception edge to the catch block, or to the unwind block. A destructor running while an exception passes is a cleanup block between the two.

Conversion to a Graph

ToGraph() returns a Graph named like the function. A block becomes a vertex, whose ID and value are the block’s; an edge becomes an edge in the direction control flows, whose kind and value are the edge’s. The graph, vertices and edges carry a copy of the key-value pairs of the control flow graph, blocks and edges; vertices and edges carry these two more:

Key	Value
`kind`	The block’s `BlockKind` or the edge’s `EdgeKind` member.
`count`	The execution count; only if it is known.

pyTooling.Graph.GraphML writes them as <data> elements; a kind is written by its name:

from pathlib import Path
from pyTooling.Graph.GraphML import GraphMLDocument

document = GraphMLDocument()
document.FromGraph(graph.ToGraph())
document.WriteToFile(Path("Read.graphml"))

<node id="3">
  <data key="nodeValue">data = load(path)</data>
  <data key="nodekind">Code</data>
</node>
<edge source="3" target="5">
  <data key="edgeValue">OSError</data>
  <data key="edgekind">Exception</data>
</edge>