共有回帖数 0 个
-
优化写腻，暂时换个口味，这次介绍编译器4大分析（现在可能是5大了，LZ的姿势有时候也木有与时俱进）之一的控制流分析。
为了进行编译器优化，编译器需要对程序有全局性的“理解”能力，编译器需要了解程序的控制流走向以及对数据的操作信息，以便删除那些冗余或者低效的做法，代之以更高效的做法。而编译器对程序进行的发现控制流层次结构的分析就叫控制流分析。
控制流分析是编译器分析中最为基础的分析之一，它是数据流分析和依赖关系分析的基础，没有控制流分析你将无法知道程序的走向，也就无从谈起语句的先后关系，因此更加不可能知道其如何操作数据的了。
【基础】
基本块(Basic Block)：基本块是一个单入口单出口的最长的语句序列，基本块的第一条语句就是入口，而最后一条语句就是出口。显然啊基本块的入口只可能是：
1. 过程的入口
2. 分支的目标
3. 直接跟在分支或者返回之后的语句/指令
因此一个基本块就是紧邻的两条上述语句之间的语句序列。绝大多数时候这种方法都可以确定出一个基本块。
Note：关于调用。上面并没有说函数调用是否视为一个分支。绝大多数时候，由于函数调用/返回的关系，调用不必被视作分支，这样能产生更长更少的基本块。但是有些语言比如Fortran就不一样，不过LZ不懂Fortran，于是LZ就不详说了。另外对C也有特例，那就是setjmp,
longjmp这对冤家。它们的机制就不提了，总之它们使得函数不再是单入口的而可以被任意的跳入，所以它们也必须被当作分支目标和分支。一般的编译器都不尝试优化它们所在的函数，不过由于LZ的姿势不能与时俱进，也许现在有编译器做优化也说不定。总的来说，是否将调用视作基本块的边界是可以具体问题具体分析地，同一编译器可能有的优化视作有的优化又不视作。
在识别出基本块后，我们根据基本块的跳转关系，为其标出前驱后继的基本块，于是我们得到了一个这样的有向图：图中的节点代表基本块，有向边代表前驱/后继关系。由此我们将控制流分析成功转到了图论上
到这里，最基本的控制流分析结束了，它的目的是：找出基本块，标出其前驱后继
【进阶】
在进行了基础的控制流分析后，我们已经可以对程序的控制流走向有最基本的认识了，我们可以知道每条语句属于哪个基本块，也可以知道每个基本块前面有什么块后面有什么块。但是更进一步的信息就没有了，我们无法知道基本块是否处于循环上（分支倒是比较好了解，有多个前驱/后继肯定就是分支了）。
于是进阶的控制流分析的最主要功能就是检查循环了，虽然大部分情况下高级程序语言会提供如for, while这样的循环语句，但是我们还是遭不住goto形成的循环（不要盲目的斥责为垃圾，clang里某个优化就是用goto写的大循环，目测是因为循环终结条件无比复杂）。
总之为了检测循环，主要有两种分析方法，不过绝大多数编译器都采用的第一种，虽然鲸书对第二种吹的天花乱坠外加用了大量篇幅，而且他们说的也很有道理。但是相信我，目前来说任何一个拿薪水的程序猿都不会为了检测循环去动手实现第二种方法那么复杂的玩意的。当然，如果你有兴趣，自己搞个然后告诉我用起来比第一种好多少也可以……。不过今后，也许吧
第一种：使用必经节点找出循环
大部分编译器都采用这种方法，优点是简单，快速，够用……
必经结点：如果从入口entry到结点i的每一条的可能执行路径都包含d，我们说结点d是结点i的必经结点，记做d dom i. 具有如下特性：
回边：指对于一条边a-b来说，如果边的头b是边的尾a的必经结点，那么这条边是回边
自然循环：已知一条回边a-b，那么a-b的自然循环的结点**是由结点b以及流图中那些从它们可以到达a但不经过b的所有结点组成，边**是由所有连接其结点**中结点的边组成。b为自然循环的首结点
很简单吧，算法什么的自己想吧!
另外【基础】中已经说了，控制流分析已经转换成了一个有向图的问题，图论的各种方法概念我就不介绍了，SCC，DAG等等，各位请自行科普吧……
第二种：区间分析
区间分析包含一系列的分析方法，它将整个过程分解成称为区间的嵌套区域，嵌套结构则称为控制数。鲸书语“因为这种方法十分重要，故我们单辟一节专门讲述它”另外鲸书顺便列绝了各种好处，比如可以让数据流分析结构化，或者可以局部的更新以应对控制流的变化等。不过总之很少有编译器采用它，因为它的实现很复杂。
区间分析的本质是利用有向图的可规约性，将每一个区域规约成一个新的抽象节点，从而一步步的规约有向图达到最简。同时这些规约的区域则形成一颗控制数来代表程序的控制流层次。
LZ这里介绍一种最简单的区间分析（T1-T2分析）来描述它的原理，至于更复杂的被称为结构分析的东西只不过是它的复杂化而已了。
T1-T2分析由两组规约构成
- T1将仅一个结点的自然循环规约为单个结点
- T2将第一个结点是第二个结点唯一前驱的两个结点规约为单个结点
于是对于下面的控制流结构其规约过程如下：
由于T1-T2变换很简单，它并不能规约所有形式，所以有了更为复杂的结构分析，它的本质就是将T1,T2扩展成Tn，用更多复杂的规约区域来规约有向图，最后得到控制树。过程不再详述……
控制流分析至此告一段落！几十页的内容简单写也是很难办的，于是随便介绍下就差不多了，欢迎额外交流，题目就不出了，想不到简单的题目…………
死代码删除 (Dead Code Elimination)
首先
并介绍一个悲伤的概念：死(dead)。
如果一个变量的值被设定开始到出口的任何路径上都不是用这个变量，这个变量是死的
如果一条指令仅计算从该指令开始的任何可执行路径上都不会使用的值，这个指令是死的
将一个死去变量赋值给一个局部变量，如果在过程出口的所有路径上都不是用这个局部变量，这个局部变量是死的
如果将一个死去变量赋值给一个有更大作用域的变量(比如所谓的全局变量)，这个通常需要过程间分析才能知道是不是死的，不过如果到过程出口的每一条路径上都有对该变量的重新赋值，那么它也是死的
【详细】
当然，实际上编译器通常采用更激进的也更为有效的做法：找出必要的(essential)，剩下的都干掉。所谓必要的是指：
- 过程必须返回或输出的值
- 可能影响过程外的存储单元的值
DCE所针对的代码通常不是程序猿有意引入的，当然不排除某些渣渣程序猿。通常死代码是由一些优化引入的，比如之前提到的复制传播。
另外，绝大多数的编译器都采用前述所谓的激进做法，即仅标识出必要的部分，而将不必要的都删掉，所以被DCE删除的并不一定是概念中所定义的死代码。
这个过程一般是迭代的，比如首先标识出返回值，指针参数，全局变量的修改，然后一步步迭代表示出这些计算所必要的计算，直到迭代至标识区域不再变化为止。最后将标识以外的代码通通删除。它通常会利用数据流分析方法来分析数据之间的关系，这里就不具体说明了，鲸书有较详细的算法说明并附有为代码。
DCE的理论比较简单，应该很好接受，所以就不用太多篇幅了，小题目一个，仅DCE优化后，下面的函数会被优化成什么样
int x;
int func(int a, int*b, int*c)
{
int i, j;
for(i = 0, j =0; i 10; i++) {
j+=2;
a+=x;
b =a;
c++;
}
return a;
}
楼主 2015-11-19 13:41 回复
Copyright © 2010~2015 直线网 版权所有,All Rights Reserved.沪ICP备10039589号
意见反馈 |
关于直线 |
版权声明 |
会员须知
