Flutter控制流图分析插件control_flow_graph的使用

Flutter控制流图分析插件control_flow_graph的使用

control_flow_graph 提供了一个 Dart 库，用于创建和运行各种算法在控制流图（CFG）上，如转换为 SSA 形式、计算支配树、寄存器溢出等。这在编写编译器、解释器和静态分析工具时非常有用。

开始使用

要使用 control_flow_graph，首先需要创建一些基于 SSA 的操作。每个操作都是 Operation 类的一个子类，并且必须描述它写入和读取的变量。例如，这里有三个示例操作：加载一个整数值，执行小于比较，然后返回一个值：

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

  LoadImmediate(this.target, this.value);

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

  Operation copyWith({SSA? writesTo, Set<SSA>? readsFrom}) {
    return LoadImmediate(writesTo ?? target, value);
  }
}

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};

  Operation copyWith({SSA? writesTo, Set<SSA>? readsFrom}) {
    return LessThan(writesTo ?? target, readsFrom?.firstOrNull ?? left, readsFrom?.lastOrNull ?? right);
  }
}

final class Return extends Operation {
  final SSA value;

  Return(this.value);

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

  Operation copyWith({SSA? writesTo, Set<SSA>? readsFrom}) {
    return Return(readsFrom?.single ?? value);
  }
}

接下来，你需要创建一个 ControlFlowGraph 并添加一些基本块到其中。基本块是一个按顺序执行的操作列表。只有最后一个操作在一个基本块中可以执行分支。control_flow_graph 包含一个有用的构建方法来简化创建 CFG 的过程：

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();

现在你有了一个 CFG，你可以在这个 CFG 上运行各种算法：

// 计算支配树
final dominatorTree = cfg.dominatorTree;

// 获取全局变量
final globals = cfg.globals;

// 插入 Phi 节点
cfg.insertPhiNodes();

// 转换为 SSA 形式
cfg.computeSemiPrunedSSA();

访问图

图中的基本块可以通过 ID 或标签通过索引访问：

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]; // 通过 ID 访问块

final block = cfg['rootBlock']; // 通过标签访问块

你还可以访问底层的有向图：

final graph = cfg.graph;

如果你直接修改了图，你需要调用 cfg.invalidate() 来通知图已经改变。

可用算法

目前，此库提供了以下算法：

• 计算即时支配者
• 计算支配树
• 计算全局变量
• 计算 DJ 图
• 计算合并集（每基本块 DF+ 集）
• 插入 Phi 节点
• 转换为半修剪的 SSA 形式
• 查询存活信息（入和出）
• 计算存活入集
• 计算全局下次使用距离
• 查找给定块上的变量版本
• 复制传播
• 删除未使用的定义
• 删除死块
• 计算寄存器压力
• 将变量从内存中溢出和重新加载
• 从 SSA 形式中删除 Phi 节点

关于 SSA 算法的说明

该库实现了一种新的 SSA 重命名算法。虽然它比其他方法更快，但它要求变量在其作用域内或之上定义。例如，以下 PHP 代码将无法工作：

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