关于文章AnEfficientAlgorithmForComputingSSAFormAndCDG

今天在看这篇文章，有一个地方很不明白。
在文章的3.1.3部分，RHS（A）为什么是MayUse（S）+（MayMod(S)-MustMod(S)）？我觉得应该只是MayUse(S)。

这篇文章终于看完了，好长。也许这是我认真看完的最长的论文了。
不过，它的内容还是蛮值得看的。
首先说一下形式。我觉得这篇文章的形式很好，很像真正的论文。它给出定义，给出算法。每一个算法有正确性的证明和复杂度的评估。并且在大量实际程序上进行了实验并给出了结果。很严谨，很不错，很值得学习。

好的，它的内容比较老，还是当年提出SSA不久的时候给出的。
当时，大家都比较普遍的认为SSA的确是一种比较好的中间表示，并且，有很多优化和分析可以在其上方便的进行。但是，将一个程序转换成SSA的形式却不简单，尤其是要找出插入PHI函数的节点的算法。
如果在每一个汇合节点为每一个变量都插入PHI函数，显然，算法简单，但是得到的结果将含有大量的无用的PHI函数，如果只是插入必须的PHI节点，算法的复杂度有比较高。
本文章提出了DominaceFronter的概念，通过计算节点的DominanceFronter集合来找出需要插入PHI函数的节点。同时，DF这个概念对于构造控制依赖也很有帮助。
文章通过证明和实验指出，对于绝大部分实际的程序，使用DF计算SSA形式和控制依赖的复杂度和程序的长度成线性关系，并且得到的SSA的代码的大小也和程序的长度成线性关系。充分证明了，在实际的使用中可以使用SSA作为编译器的中间表示。
文章同时也给出了从SSA形式转换成一般形式的算法。这个算法是平凡算法（将每一个PHI函数用多个赋值替换）加上两个额外的优化：平凡算法之前进行死代码消除，平法算法中使用图染色的方法分配变量。据称，这样可以生成高效的代码。
该文章值得一看。