memory ssa

昨天白天在睡觉的空余大概浏览了一遍mem-ssa。
ssa的确是一种很好的中间表示，它显式地表示了数据流，并且ud dd构成的网络非常稀疏，有利于编译器的分析和优化。SSA对于所有的局部标量而言很适合，但在处理主存操作、聚合量、全局量（或某些语言中的非局部量）的时候遇见了比较麻烦的问题。而这些东西在每个高级语言中都很重要。
于是，很多人提出了在SSA中如何解决这些问题。普遍的想法就是，在CFG上再附加一个数据结构，用于表示这些操作。其中，一个概念是factored STORE/LOAD。
在mem-ssa中，主要的问题是如何解决Virtual SSA产生的大量的Virtual Operand（Virtual SSA会在每一个factored STORE/LOAD处，为每一个may-alias的符号添加一个Virtual Operand），而又不像Virtual SSA中通过简单的分组（一个alias set就是一个组，每一个组用同一个符号代表）而降低表示精度（也就是降低了ssa的稀疏性）。其实mem-ssa也是通过分组的方法来解决这个问题的，它试图找到更好的分组策略。它的分组方法分为两种，Dynamic partition 和 static partition。前者在SSA的换名过程中进行，而后者则在换名之前就已经确定了。目前作者的实现，是一个纯粹的static partition，它在性能的提升上似乎不是非常好，作者归因于分组策略的简单，希望通过改进分组策略来达到更好的效果。而纯粹的Dynamic partition是有问题的，因为它会产生同一个符号的不同版本的生命期的互相重叠，这个阻止了很多优化的进行，例如pre。并且，它会产生大量的PHI节点，这些PHI节点把本已经factored的符号重新区分开，也就“undo”了大量由于factored store所带来的好处。所以，作者还提出了一种“混合方法”，也就是把动态和静态的方法结合起来使用。这种方法还没有具体的数据评测。