control_flow_graph

Description:

control flow graph

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};
}
copied to clipboard
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();
copied to clipboard
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();
copied to clipboard
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
copied to clipboard
You can also access the underlying directed graph:
final graph = cfg.graph;
copied to clipboard
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;
copied to clipboard
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.