ethanblake4 / control_flow_graph

Dart library for creating and manipulating control flow graphs and SSA form.

control_flow_graph provides a Dart library for creating and running various algorithms on control flow graphs (CFGs), such as converting to SSA form, computing dominators, and more.

Getting started

To use control_flow_graph, you'll first have to create some SSA-based operations. Each operation is a subclass of Operation and must describe the variables it writes to and reads from. For example, here's three example operations that load an integer value, perform a less-than comparison, and return a value:

final class LoadImmediate extends Operation {
  final SSA target;
  final int value;

  LoadImmediate(this.target, this.value);

  @override
  Set<SSA> get writesTo => {target};
}

final class LessThan extends Operation {
  final SSA target;
  final SSA left;
  final SSA right;

  LessThan(this.target, this.left, this.right);

  @override
  Set<SSA> get readsFrom => {left, right};

  @override
  Set<SSA> get writesTo => {target};
}

final class Return extends Operation {
  final SSA value;

  Return(this.value);

  @override
  Set<SSA> get readsFrom => {value};
}

Next, you'll need to create a ControlFlowGraph and add some basic blocks to it. A basic block is a list of operations that are executed in sequence. Only the last operation in a basic block can perform a branch. control_flow_graph includes a helpful builder method to make creating a CFG easier:

final cfg = ControlFlowGraph.builder()
  .root(BasicBlock([
    LoadImmediate(SSA('a'), 1),
    LoadImmediate(SSA('b'), 2),
    LessThan(ControlFlowGraph.branch, SSA('a'), SSA('b')),
  ]))
  .split(
    BasicBlock([LoadImmediate(SSA('z'), 3)]),
    BasicBlock([LoadImmediate(SSA('z'), 4)]),
  )
  .merge(BasicBlock([
    Return(SSA('z'))
  ]))
  .build();

Now that you have a CFG, you can run various algorithms on it:

// Compute dominator tree
final dominatorTree = cfg.dominatorTree;

// Get global variables
final globals = cfg.globals;

// Insert Phi nodes
cfg.insertPhiNodes();

// Convert to SSA form
cfg.computeSemiPrunedSSA();

Accessing the graph

Basic blocks in the graph can be accessed via ID or label simply by indexing into the graph:

final cfg = ControlFlowGraph.builder()
  .root(BasicBlock([
    LoadImmediate(SSA('a'), 1),
    LoadImmediate(SSA('b'), 2),
    LessThan(ControlFlowGraph.branch, SSA('a'), SSA('b')),
  ], label: 'rootBlock')).build();

final block = cfg[0]; // Access block by ID

final block = cfg['rootBlock']; // Access block by label

You can also access the underlying directed graph:

final graph = cfg.graph;

If you modify the graph directly, you'll need to call cfg.invalidate() to signal that the graph has changed.

Available algorithms

Currently, this library provides the following algorithms:

• Compute immediate dominators
• Compute dominator tree
• Compute globals
• Compute DJ-graph
• Compute merge sets (per-basic block DF+ sets)
• Insert Phi nodes
• Convert to semi-pruned SSA form
• Query liveness information (in & out)
• Copy propagation
• Unused defines elimination
• Dead block elimination
• Remove Phi nodes from SSA form
• Find variable version at a given block

Note on SSA algorithm

This library implements a novel SSA renaming algorithm. While it is much faster than other approaches, it requires that variables be defined in the scope they are used. For example, the following PHP code will not work:

$x = 1;
if ($x < 2) {
  $y = 3;
} else {
  $y = 4;
}
echo $y;

To make this code computable, you would have to hoist the declaration of $y above the if-else block. Many languages like Dart, C, and Java already enforce this restriction, so it should not be relevant in practice when used with them.

Features and bugs

Please file feature requests and bugs at the issue tracker.