未使用赋值的静态分析：基于AST的高效检测算法问询

核心思路：用数据流分析（到达定义+活跃变量）替代逐赋值DFS #

你的原始思路对每个赋值单独做DFS会导致O(n²)的复杂度，而数据流分析可以批量处理所有变量的定义与使用关系，将复杂度降到接近线性。

1. 到达定义分析（正向分析）

• 先构建控制流图（CFG），将代码划分为基本块（无分支的连续语句序列）。
• 对每个基本块，计算到达定义集合：即进入该块时，哪些变量的定义（赋值操作）是有效的（未被后续同变量赋值覆盖）。
• 给每个赋值操作生成唯一的定义标识（比如x_1代表x的第1次赋值），集合中存储这些标识。

2. 活跃变量分析（反向分析）

• 反向遍历CFG，计算每个基本块的活跃变量集合：即离开该块后，哪些变量的值会被后续代码读取。
• 对于块内的赋值操作x = ...，如果x在块的出口活跃，且该赋值的定义标识到达了某个读取x的位置（且没有被后续x的定义覆盖），则这个赋值是被使用的；反之则为未使用。

3. 关键优化点

• 批量处理：无需对每个赋值单独遍历CFG，一次数据流分析就能覆盖所有变量的定义与使用。
• 集合运算优化：用位向量（每个位对应一个定义标识）表示到达定义/活跃变量集合，交、并、差运算直接用位操作，效率极高。
• 局部预检测：先在AST层面做局部过滤，比如同一基本块内，变量赋值后立即被重新赋值且中间无读取，直接标记为未使用，减少全局分析的工作量。

示例说明

假设代码片段：

x = 1;  // 定义x_1
if (flag) {
  println(x);  // 使用x_1
} else {
  x = 2;  // 定义x_2
}
// 后续无x的读取

• 到达定义分析显示x_1进入if的两个分支，在println(x)处被使用，因此x=1是有效赋值。
• x_2在else分支定义后，后续无任何读取操作，活跃变量分析会标记x_2无后续使用，因此x=2是未使用赋值。

复杂度说明 #

数据流分析的迭代次数由CFG的深度和变量数量决定，实际中迭代次数通常是常数级（比如3-5次），每次迭代处理所有基本块的集合运算，整体复杂度为O(n)（n为token数），完全适配百万级代码规模。

内容的提问来源于stack exchange，提问作者otstalyi