Compilers Chaper 9 总结

这一章介绍了常见的代码优化。其实，着重讲了一下数据流分析技术和常用的几种数据流分析。
这些分析和优化是与机器无关了。

1、全局公共子表达式。一个重要的优化就是找到在两个不同的基本块中对同一个表达式的计算。如果前一个是后一个的前驱，我们可以在第一次计算出该表达式的时候，将它的值存储在一个变量中，在第二次需要的时候直接使用变量中保存的值。
2、拷贝传播。一个拷贝语句u=v将变量v的值赋给u。在某些情况下，我们可以把对u的使用换成v。
3、代码移动。另一个优化是将循环中的某些代码移动到循环的外面。当然，只有循环不变量可以这么做。
4、递推变量。大部分循环都有递推变量，这些变量随着迭代的进行线性地增长。很多这样的变量都可以被强度减弱或删除。
5、数据流分析。一个数据流分析模式，在程序的每一个点上定义了一个值。程序的语句有相关联的转移函数，这个函数将该语句之前的数据流值映射为语句之后的数据流值。有多于一个前驱的语句之前点的数据流值需要使用与操作符计算出来，参数是所有前驱的数据流值。
6、基于基本块的数据流分析。因为数据流值在基本块中的传播通常是很简单的，数据流等式一般建立在基本块的粒度上。基本块之前的值叫做IN，之后的叫做OUT。一个基本块的转移函数可以通过复合基本块内语句的转移函数得到。
7、可达定义。可达定义是一种数据流分析。其数据流值是一个定义的集合。一个基本块的转移函数可能会kill一些定义，生成一些定义。与操作符是集合的并。
8、活变量分析。数据流分析。计算出在程序的每一个点上有哪些变量是活的。该分析是反向的。
9、可用表达式。这个分析用于发现全局公共子表达式。数据流值是每一个点上的所有可用的表达式的集合。可用表达式指，表达式已经被计算出来，并且表达式的任何一个参数都没有被重新定义过。这里的与操作符是集合的交。
10、抽象的数据流问题。通用的数据流问题可以用一种数学结构来描述。数据流值构成一个半格。转移函数将半格的元素映射到半格的元素。所有的转移函数构成的集合必须在函数结合的运算下是封闭的，同时含有恒等函数。
11、单调框架。半格上的元素根据与操作可以定义一个偏序<＝，如果一个数据流分析框架中的所有的转移函数都满足if a<=b， f(a)<=f(b)，那么这个框架称为单调数据流框架。
12、可分布框架。如果所有的转移函数都满足f(a^b)=f(a)^f(b)，那么该框架叫做可分布框架。可以证明，可分布框架一定是单调框架。
13、数据流分析问题的迭代算法。所有的单调框架都可以使用迭代算法来解决。
14、常量传播。常量传播也是一种利用数据流分析的技术优化的方法。
15、部分冗余消除。很多有用的优化，例如代码移动和全局公共子表达式消除都可以被一般化为部分冗余消除。表达式只有在某些路径上是冗余的，叫做部分冗余。这个算法的实现使用了4个数据流分析问题。
16、Dominator。如果在流图中，任何一条从入口到节点B的路径一定会到达A，则称A Dominate B。B的一个proper dominater指除了自己以外的其它任何一个Dominator。B的immediate dominator是被B的所有proper dominator Dominate的proper dominator。
17、流图的深度优先序。如果我们对流图做一个深度优先搜索，将会得到流图的一个深度优先扩展树。深度优先序就是后序遍历这棵树的相反的序列。
18、边的分类。构造一个流图的深度优先扩展树，流图的所有的边都可以被分为三类。指向后代节点的边是advancing 边，指向祖先节点的边是retreating 边，其它的边是cross边。一个重要的性质是，如果树的节点的子节点按照插入的顺序从左向右排列，那么所有的cross边都是从右向左的。另一个性质是，a->b是一个retreating边，当且仅当a的深度优先序号大于b的序号。
19、back 边。a->b是back边，当且仅当b Dominate a。每一个back边一定是一个retreating 边。
20、可规约流图。如果一个流图的所有retreating边都是back边，则称为可规约的。
21、自然循环。一个自然循环是一组节点的集合。其中一个称为头节点的Dominate所有的节点。并且，至少有一条back边从集合中的某个节点指向头节点。给定一个back边，我们就能找到一个自然循环。两个有不同头结点的自然循环，要么一个嵌套在另外一个里面，要么二者不相交。
22、深度优先序会使得数据流的迭代收敛得更快。
23、Region。区域是一个节点和边构成的集合，并且拥有一个头节点，这个节点Dominate所有区域中的节点。除了头结点以外的其它区域内的节点的任何前驱节点也一定在该区域内。所有区域内节点之间的边也在区域内，除了指向头结点的back边。
24、区域和可规约流图。可规约流图可以被分解为区域的层次结构。这些区域要么是loop region，包含指向头结点的back边，要么是body region，不包括指向头结点的back边。
25、基于区域的数据流分析。另一种数据流分析的方法。自底向上地为每一个区域计算转移函数。这些转移函数可以用于计算数据流值。
26、基于区域的递推变量分析（其实是符号分析）。一个基于区域的数据流分析的应用。跟踪每一个变量的值，将这些值表示为输入变量或是迭代计数等引用变量的仿射表达式。