3. 数据流分析

各位同学好，今天我们来聊聊编译优化里最核心的一块——数据流分析。说实话，我在NPU集群上做编译优化这些年，踩过最多的坑就是数据流没分析透。你想想看，编译器连数据怎么流动都搞不清楚，怎么可能做出好的优化？

这一节我们重点讲四个东西：控制流图（CFG）、数据依赖分析、别名分析、指针分析。它们环环相扣，缺一不可。

控制流图（CFG）—— 优化的骨架

控制流图，说白了就是程序执行路径的地图。每个基本块是一个节点，跳转关系是边。我习惯把CFG比作地铁线路图——你知道从哪站上车，哪站下车，中间经过哪些站。

构建CFG时，我一般分三步走：

1. 划分基本块 —— 遇到跳转指令就切一刀
2. 建立边关系 —— 条件跳转、无条件跳转、函数调用
3. 识别循环结构 —— 自然循环、可归约流图

这里有个坑，我曾经在分析一个复杂的循环嵌套时，CFG构建错了，导致后面的数据流分析全白做。嗯，所以第一步一定要扎实。

// 示例：基本块划分
int a = 10;          // B1
if (a > 5) {         // B1
    a = a + 1;       // B2
} else {
    a = a - 1;       // B3
}
return a;            // B4
// CFG: B1 -> B2, B1 -> B3, B2 -> B4, B3 -> B4

数据依赖分析 —— 优化的灵魂

数据依赖分析，说白了就是搞清楚变量之间的"谁等谁"关系。在NPU集群上，这个尤其重要——因为你得决定哪些计算可以并行，哪些必须串行。

数据依赖分三种：

依赖类型	含义	能否并行
真依赖（RAW）	写后读	不能
反依赖（WAR）	读后写	可以（重命名）
输出依赖（WAW）	写后写	可以（重命名）

数据依赖分析的核心算法是到达定值分析。我习惯用数据流方程来表达：

// 到达定值数据流方程
IN[B] = ∪(OUT[p])  // p是B的前驱
OUT[B] = GEN[B] ∪ (IN[B] - KILL[B])

你想想看，这个方程其实就是在做"哪些变量定义能到达当前点"的传播。在NPU集群上，我们经常用这个来判断哪些数据可以复用——如果某个定义能到达多个使用点，那就可以把数据留在本地缓存里。

别名分析 —— 指针的迷雾

别名分析，说白了就是判断两个指针是否指向同一块内存。这个问题在C/C++里特别头疼。我记得有一次在调试一个NPU上的算子融合时，因为没做好别名分析，导致两个本应融合的算子被拆开了，性能直接掉了30%。

别名分析主要分两类：

• 基于类型的别名分析 —— 利用类型信息判断，速度快但精度低
• 基于流图的别名分析 —— 沿着CFG传播指针信息，精度高但慢

别名分析的结果通常用别名集来表示。每个指针变量都有一个别名集，里面是所有可能指向同一地址的指针。我一般用位向量来存储——每个位代表一个变量，1表示可能别名。

指针分析 —— 追踪指针的足迹

指针分析是别名分析的升级版。它不仅要判断两个指针是否别名，还要追踪指针的指向关系。说白了，就是搞清楚"这个指针到底指向哪个变量"。

指针分析的主流方法有两种：

1. Andersen算法 —— 基于约束的指针分析，精度高但复杂度O(n³)
2. Steensgaard算法 —— 基于等价类的指针分析，速度快但精度低

我个人习惯在NPU编译优化中用Andersen算法。为什么？因为NPU上的指针操作相对简单，n不会太大，O(n³)完全扛得住。而且精度高，能发现更多优化机会。

// 指针分析示例
int a, b;
int *p = &a;   // p -> {a}
int **q = &p;  // q -> {p}
int *r = *q;   // r -> {a}  (通过q间接指向a)

这里有个技巧：在NPU集群上做指针分析时，我通常会结合上下文敏感分析。因为同一个函数在不同调用点的指针行为可能完全不同。我曾经在一个图像处理流水线中，通过上下文敏感分析发现了两个本应独立的指针其实指向同一块缓冲区，从而成功合并了两次内存访问。

实战：在NPU集群上应用数据流分析

好了，理论讲完了，咱们来点实际的。在NPU集群上，数据流分析主要用在以下几个场景：

• 指令调度 —— 根据数据依赖关系，把不相关的指令并行发射
• 寄存器分配 —— 通过到达定值分析，确定变量的生命周期
• 循环优化 —— 分析循环携带依赖，决定是否可以做流水线
• 内存优化 —— 通过别名分析，判断哪些内存访问可以合并

最后，我画了一张图，把今天讲的知识体系串起来：

这张图把今天的内容串起来了。从CFG这个骨架开始，到数据依赖分析这个灵魂，再到别名和指针分析这两个细节。每一步都是下一层的基础。