共有回帖数 0 个
-
No.1，2简单介绍了两个体系无关优化，由于通常这些优化也运行在中间端，也常被称作中间端优化
有一定经验的同学仔细检查上面优化中给出的例子应该不难发现两点：
1.这些优化的对象都是冗余的代码
2.这些例子都是渣代码，正常水准的程序猿都不会写成这德性
关于第1点是正确的，体系无关优化的主要目标就是冗余代码，冗余的计算冗余的赋值冗余的分支冗余的循环甚至冗余的函数调用和冗余的定义。
关于第2点则不尽然，LZ所举的例子确实都是渣代码，那只是因为LZ实在很懒同时也为了直观而那些简单表达式来举例。实际上体系无关所针对的冗余一部分确实可能是由渣程序猿写出来的渣代码，但是更多的则是高级程序语言带来的副作用。
高级程序语言一定程度的掩盖了底层的细节，而这些掩盖则是冗余的主要来源，一般来说说特性越复杂往往代表越多的细节被掩盖同时带来越多的冗余。
比如我们一般不大可能写下x = a + b; y = a + b;这样的代码
但是我相信绝大多数人都写过
int a;
func1(&a);
func2(&a);
从C语言的角度来说，&a已经是一元表达式，简无可简。但是实际上它隐藏了对a的寻址过程，这个寻址过程一般来说是个加法:栈顶+偏移。于是对于上面这段代码CSE后用C语言表示可以是这样
int a;
register int* t = &a; // a的地址存入寄存器
func1(t); //直接使用寄存器值
func2(t);
所以即使最简单的&a都隐藏了一个加法，更不用说a[n]或者s.a这些更复杂的表达式所隐藏的计算则更多。比如a[n]的实际求值相当于*(&a + (sizeof(a[n]) * b))，当然其中的乘法一般会被优化成左移。
这种时候优化的力量才真正显现出来
接下来介绍一些过程优化（是过程优化不是过程间优化哟）。过程优化的主要目的是节省调用的开销以及增加优化机会。主要的实现手段就是过程展开。过程展开可以将函数体展开于被调用处，或者将调用替换成跳转。这可以节省调用的开销，同时向编译器展现调用与被调用过程之间的值传递，增加优化的机会
比较主流的过程优化有三对：尾递归删除(Tail recursive elimination)和尾调用优化(Tailcall optimization)，过程集成(Procedure integration)和内嵌扩展(inline expansion)，叶例程化(leaf routine optimization)和收缩包装(shrink wrapping)。
No.4 尾调用(tail call)和尾递归(tail recursive)的优化
【中心思想】
有过程f(), g()，若f()对g()的调用是尾调用。我们可以将g()展开在f()的调用处，这样可以显著的减少调用的开销。特别的对于尾递归，在这样的优化过后，我们经常可以接着做展开前不能做的循环优化。
尾调用的定义：
若过程f()调用过程g()，在g()返回后过程f()做的唯一的事就是返回自己，那么这个f()对g()的调用就是尾调用。弱若f()和g()是同一个过程，则该调用是尾递归。
【详细】
对于尾调用和尾递归的优化，本质上是过程的展开，所以下面介绍过程展开的通用形式而不特别针对这俩优化。
要进行过程展开，一般来说我们要求调用被调过程的过程体是可见的，或者至少要求调用过程掌握被调过程足够的必要信息：
1. 被调过程希望参数放在哪
2. 为了开始执行被调过程的过程体，控制应该转向何处
3. 被调过程的栈帧大小
对于尾递归这自然不是问题，因为调用和被调过程就是同一个，但是对于其他形式的展开，包括尾调用，inline等，这是编译器必须考虑的一个问题。因为编译时仅要求过程有声明而无需定义，因此在编译时编译器是否能看到过程的过程体就是一个问题。所以实际上，很多的展开优化实际上是由链接器完成的，而非编译器。这也是编译器难以进行过程间优化的一个重要原因。
在已知上述3点的情况下，编译器即可开始展开被调过程于调用处：
1. 计算调用的实参，并将实参传递给被调过程
2. 调整调用过程的栈帧大小使其合适调用与被调过程的栈帧大小
3. 转移控制到被调过程的开始处
下面以一个尾调用的例子来说明上面的优化过程, 不要吐槽程序本身有没意义
int f(int b, int c)
{
int a;
if (a) {
g(b, c);
}
}
void g(int b, int c)
{
int d, e = 1, f= 2;
d = 0;
return b+c+d+e+f;
}
对于上面的例子，f()对g()的调用就是一个尾调用，如果要对其进行展开，如果用C语言表述展开后的结果大致如下：
int f(int b, int c)
{
int a;
int g_b, g_c, g_d, g_e = 1, g_f = 2;
if(a) {
g_b = b;
g_c = c;
g_d = 0;
return g_b+g_c+g_d+g_e+g_f;
}
}
需要注意三点：
1.区分调用过程的实参和被调过程的形参，它们可能同名，可能值也相等，但是它们不是同一个“变量”。
2.对于栈帧的调整，如果优化在比较底层的情况下进行，那么通常我们可以重新生成调用过程的prologue和epilogue，这样的调整最为直观。另外一种在相对高层的情况下进行，我们则一般如例子中一样向调用过程中插入被调过程的变量。
3.关于栈帧的大小，调整后的栈帧大小应该能容纳原调用和被调过程的所有变量(包括编译过程时的临时变量)，因此一般来说栈帧大小等于调用过程和被调用过程的栈帧之和。但是对于尾调用和尾递归来说，由于在g()返回后f()立刻返回，即某种程度上，无需保证在g()返回后f()的栈帧内容依然有效，这意味着进入g()时，原f()中的栈帧即进入了闲置状态，因此在进入g()时我们可以让g()的变量占用f()那些闲置的栈帧，因此对于尾调用和尾递归来说，栈帧的大小通常等于被调过程和调用过程的差。
Note: 第3点的讨论基于调用和被调过程的栈帧彼此分离的情况，但是通常来说被调过程可以引用调用过程的栈帧，对于这种情况请独立考虑。
所以对于尾调用来说，上面的例子也可以优化成下面的样子：
int f(int b, int c)
{
int a;
int e = 1, f =2;
if(a) {
a = 0;
return b+c+a+e+f;
}
}
// 上面的例子表示的是，在f()中分配给a的栈将被分配给d
小题目：尾递归会被如何优化
NODE* find_list(NODE* node, int goal)
{
if(node-next== NULL) {
return NULL;
}
if (node-value== goal) {
return node;
} else {
return find_list(node-next);
}
}
// NODE是一个典型的单链表结构体，next指向下一个节点, value存值
楼主 2015-11-19 13:39 回复
Copyright © 2010~2015 直线网 版权所有,All Rights Reserved.沪ICP备10039589号
意见反馈 |
关于直线 |
版权声明 |
会员须知
