问控制流图导航算法的粗略说明

EN

我想你是在问数据流分析的事。

在SSA之前，我们将使用位向量，其中位向量中的每个位表示正在编译的方法中的一个变量(可以是程序变量或实际或虚拟cpu寄存器)。我们会使用一对位向量，一个用于防御，另一个用于使用，这样的比特向量将在概念上附加到每条指令上；尽管在实践中，我们通常只在每个基本块的开始和结尾存储这样的位向量。

这些位向量最初是通过遍历每个基本块来计算的:向前通过块时，基本块末尾的到达定义对基本块中设置的每个变量( def‘d)都有一个位集，并且，通过向后通过块，基本块开始处的向上暴露的用法对基本块内使用的每个变量都有一个位集。在向后遍历期间，def掩蔽了相同变量的使用，所以只有被使用而不是被如此蒙蔽的变量才能成为存储在块开头的位向量。

然后，通过遍历控制流图，将基本块的位向量传播到正在编译的方法(例如其他基本块)，合并信息直到没有变化(合并函数是不动点，意味着它们收敛). ，如果我们识别特定的控制流结构(而循环，如果是……)，我们可以在最后的迭代之前停止合并，在最后的迭代中不会发生任何变化。

在使用中，一旦计算了该方法的数据流，就可以像死代码一样执行优化。这种优化可以从基本块的末尾开始，从使用位向量开始，然后向后走。反向遍历时，可以根据每条指令修改使用位向量的副本，以便获得指令级信息。

然后，通过知道在特定的def中，该变量不在使用集中，就可以检测死代码(根据赋值但未使用的变量)。可以消除def的指令计算。结果需要更新数据流，然后通常会找到更多的指令(早期的指令，那些计算已删除指令的值以供使用的指令)，这些指令现在也死了。

SSA -通过引入变量的新版本(例如，每次分配变量)，从而跟踪变量的版本而不仅仅是变量--使一些收集到的数据流信息适用于整个方法，而不是像以前那样按代码中的位置变化。