软件工程作业-方舟学习笔记06-初识SSA

了解这篇文章SSA。
在编译器的设计中，静态单赋值形式（static single assignment form，通常简写为SSA form或是SSA）是中介码（IR，intermediate representation)每个变数只赋值一次。在原始的IR在许多教科书中，现有的变数可以分为许多不同的版本。在许多教科书中，旧的变数名称通常被下标，以便标记每个变数及其不同的版本。在SSA，UD链（use-define chain，赋值代表define，使用变数代表use）非常清楚，每个元素只包含单一元素。SSA同等于连续传输样式（CPS，continuation-passing style）子集(不包括非本地端控制过程。当CPS被使用在IR，因此，任何最佳化和转换都将适用于前者CPS。当我们期待C或Fortran使用编译器SSA时，CPS函数编程语言的编译器已广泛应用，如Scheme、ML及Haskell。
SSA最重要的用途是通过简化变数的特点来简化和改进编译器的最佳化。
y := 1 y := 2 x := y
从以上描述可以看出，第一行赋值行为是不必要的，因为y在第二行被二次赋值，y的数值在第三行被使用，一个程式通常会进行定义可达性分析（reaching definition analysis）测量它SSA以下形式：
y1 := 1 y2 := 2 x1 := y2
可以借鉴编译器最佳化算法SSA实现以下改进：
常数传播（constant propagation）
值域传播（value range propagation）
稀疏有条件的常数传播（sparse conditional constant propagation）
消除无用程序码（dead code elimination）
全球数值编号 （global value numbering）
消除部分冗余 （partial redundancy elimination）
强度折减（strength reduction）
暂存器配置（register allocation）

首先，我们需要它Graph中支配点（Dominator）概念：当一个点A到点B在控制过程图中，如果没有其他路线，那么A和B这是控制点。这很有用，因为如果程式进行到B，就意味着A也会执行。我们可以说A主导了B（B也支配着A）。
现在我们可以定义控制边界：如果A不直接控制B，但控制B的预程序，节点B是点A的控制边界（可能点A是点B的预程序，所以，因为任何点都控制自己，点A也控制自己，所以点A也是点B的控制边界），从A的角度来看，其他控制路径，可以让他们更早出现。
需要支配边界Φ函数的准确位置：如果点A定义了一个变数，则该变量将达到所有点A的主导点。只有当我们离开这些点并进入主导边界时，我们才必须考虑其他过程将具有其他相同变量的定义。此外，无需在控制过程图中处理A的定义Φ函式。

要最小化SSA必须放入最小数量Φ函数仍然需要确保每个变数只被赋予一个值，每个变数仍然可以在原始程序的参考中指示一个独立的变数。（以下描述的要求是确保编译器可以在每个操作中写下每个操作子）
然而，有些Φ由于这个原因，函式可能会变成无用的程式码，最小化SSA不一定生产最少数量的产品。Φ函式还需要特定的程序，一些类型的分析Φ函数是多余的，可能导致分析效率低下。

精简的SSA
精简的SSA（Purned SSA form）基于简单的观察：Φ函式只需要一种情况，即变数Φ函式运行后仍然活跃(仍然活跃意味着该值用于某些路径，这些路径是基于Φ函数为起点)。如果不再使用变数，Φ函式的结果不能使用，而且是无用的Φ函式赋值。
在插入Φ在函数阶段，使用活跃的变数信息（Live variable information）来决定Φ是否需要函式来构建一个简化的方法SSA。若原始变数名称为Φ如果函式插入点不再使用，Φ函式不会插入。
其他可能性是将简化视为解决消除无用程序代码的问题。只有在输入程式中，无论如何使用，都将被重写，否则将被用作其他程序Φ我们会认为函数的参数Φ函式是活跃的。当进入SSA形式，每个使用情况都应该改为最接近的定义，这个定义支配它，一个Φ函式将被视为活跃，只要最接近的定义仍然支配至少一个使用或一个活跃的定义Φ的参数。

半精简的 SSA
半精简的SSA（Semi-pruned SSA form）试图减少Φ函数的数量不承担高成本的计算活动变数信息。这是基于以下观察：如果变数从未活跃在基本块中，则不需要变数Φ函式。在SSA本地任何区块变数都将被省略Φ函式。
与活跃变数分析相比，计算本地区块变数的集合是一个简单快捷的程序，使半精简SSA比起精简的SSA在计算上更有效率，换句话说，半精简SSA它将包含更多Φ函式。

SSA转换程式通常不用于直接执行(尽管通过直接翻译)SSA这是可能的)，它经常用于其他直接对应的保留IR以上，这可以借由将SSA构建为函式集合，函式集合对应部分IR(基本块、指令、运算子等。)以及它SSA副本。当SSA当不再需要时，这些相应的函式将被删除，只留下最佳化IR。
SSA最佳化通常会导致混乱SSA网络（SSA-Webs），因为这些Φ并非所有指令的运算子都有相同的根运算子，在这种情况下，可以使用Color-out算法，初始算法，作为计算每个预处理路径的副本，如果这些路径导致不同根符号的来源被放入Φ，而非Φ的终点。解决这些问题的算法有很多，有的会用更少的副本，大部分会用干扰图形（interference graph）或合并相似的副本。

有了这些知识，我们可以分析方舟编译器SSA设计了。