关于编译器优化方面的知识

mathe · 发表于 2008-2-26 14:50:29

现在来介绍编译器如何识别循环变量的问题。
比如前面各种关于循环的优化中，我们如果要计算依赖向量，起码编译器要能够识别循环变量，
而识别循环变量也是编译器的一个优化过程。
而通常编译器所认为的循环变量可能同我们所看到的有所不同。
通常的循环变量是狭义的，也就是说，如果这个变量在一个循环的任意两次相邻的迭代中变换值是常数，
那么这个变量就是循环变量。最常见的循环变量是如下代码中:

for(i=0;i<n;i++){
....
}

复制代码

如果循环体中没有对变量i的修改，那么i就必然是一个循环变量。
但是如果循环体中对i做了修改，那么虽然看上去i还像是一个循环变量，但是对于编译器来说，i已经不是循环变量了，如:

for(i=0;i<n;i++){
if(..){
i++;
}
...
}

复制代码

像上面的循环体，有时候i增加1，有时候i增加2,那么i就不是循环变量了。
而还有一些情况，循环变量人工不容易看出来，但是编译器确可以判断出来，如:

i=0;
while(...){
j=i+1;
...
k=j+2;
...
i=k;
...
}

复制代码

像上面的代码，如果没有其他对j,k,i的修改，那么这里i,j,k实际上都是循环变量，
其中每次迭代这三个变量都增加了3.
而对于编译器来说，通常还可以识别一些更加复杂的循环变量，如:

i=0;
while(...){
j=i+1;
...
k=j+2;
h=a*k+j;
...
i=k;
u=h-i+b;
...
}

复制代码

像上面代码中，编译器首先可以识别出i,j,k是循环变量，然后编译器发现h,u是循环变量的线性组合，
所以编译器可以识别出它们也是循环变量。(其中a,b可以是变量，只要在循环体内部没有被修改）
比如h每个循环改变的量为3*(a+1),u每个循环改变的量为3*a,编译器可以通过将上面代码改变为:

i=0;
h=3*a+1;
u=3*a+1+b;
step1=3*(a+1);
step2=3*a;
while(...){
j=i+1;
...
k=j+2;
///h=a*k+j;///删除原先这里对h的定义
...
i=k;
///u=h-i+b;///删除这里对u的定义
...
h+=step1;
u+=step2;
}

复制代码

在经过这个变换以后，在循环体内部, 所有关于循环变量的计算均可以不包含乘法运算，从而比原先代码应该可以快一些。
同样，如果在编译器优化比较后面的部分，通常，对于数组的访问都已经被展开，
如代码

for(i=0;i<n;i++){
a[i] =....;
}

复制代码

可能被展开成:

for(i=0;i<n;i++){
p=a+i*S; ///这里S是常数，代表数组a中每个元素在内存中占用的空间大小
*p=...;
}

复制代码

那么对于编译器来说，指针p也是一个循环变量，所以代码可以被转化为

p=a;
for(i=0;i<n;i++){
*p=...;
p=p+S;
}

复制代码

变化以后同样计算地址中的乘法运算被消除了。
我看到郭给出链接中一篇英文文章中介绍到对于数组，最好让每个元素数据的大小是2的幂，这样，计算每个元素的地址时候，
乘法就可以被移位替换掉，从而提高了速度。但是，如果那样的数组通常都是被通过循环变量访问的，我们可以看出来，完全没有
必要做那样的优化（实际上那样可能会消耗更多的内存空间，从而性能更加差).
此外，有一些比较优秀的程序员，他们知道计算机计算移位比乘法运算快，所以对于下面的代码

for(i=0;i<n;i++){
a[2*i]=...;
...
}

复制代码

他们可能写成了

for(i=0;i<n;i++){
a[i<<1]=...;
...
}

复制代码

其实，对于编译器来说，反而前面的代码更加容易优化，因为编译器可以非常容易识别出2*i是一个循环变量，从而我们可以计算依赖向量，
做一些前面提到过的如么模变换，仿射变换之类的优化。反而对于后面的代码，由于通常编译器是不会将移位运算转化为乘法运算的，所以
通常的编译器反而无法知道后面的i<<1也是一个循环变量，从而阻止了进一步优化的可能。

此外，部分编译器还会对一些循环变量之间的相乘做优化（比如Open64),比如代码:

i=0;
while(...){
j=i+1;
...
k=j+2;
h=a*k+j;
...
i=k;
u=h-i+b;
...
sum+=h*u;
}

复制代码

在编译器分析出h和u都是循环变量以后，编译器就可以对h*u做进一步优化
我们知道 h=h0+i*step1,u=u0+i*step2;
所以h*u=h0*u0+(h0*step2+u0*step1)*i+i*i*step1*step2
分别对于i和i+1计算上面的表达式并相减，我们可以得到对于第i次迭代，h*u的变换值是
h0*step2+u0*step1+step1*step2+i*2*step1*step2;
所以我们知道，上面代码于是可以优化成:

i=0;
h=3*a+1;
u=3*a+1+b;
step1=3*(a+1);
step2=3*a;
hu=h*u;
ddhu=2*step1*step2;
dhu=h0*step2+u0*step1+step1*step2+ddhu*i;
while(...){
j=i+1;
...
k=j+2;
///h=a*k+j;///删除原先这里对h的定义
...
i=k;
///u=h-i+b;///删除这里对u的定义
...
h+=step1;
u+=step2;
sum+=hu;
hu+=dhu;
dhu+=ddhu;
}

复制代码

从而计算循环体内计算h*u的乘法运算由两次加法运算代替，从而提高了速度。
同样道理，对于三个循环变量的相乘，从理论上，我们同样可以转化为若干次加法运算。
不过据我所知，并没有编译器真正这样去做，毕竟实际中，这样代码的例子会非常少见。
当然，如果换成用郭的HugeCalc代码中大整数做循环变量的代码，那么遇到上面的代码编译器
的优化同样无能为力了，那么就需要手工做类似的优化了。

gxqcn · 发表于 2008-2-26 19:54:40

现在的编译器优化能力真强啊！

看来之前对它有些低估了！
为了避免循环体内的加法，我常常得分析是否可以用加法来替换，比如图像处理中指针的定位。

mathe · 发表于 2008-2-27 07:55:03

不过编译器的优化还是要依赖于代码质量如何。
比如如果循环体内部使用了全局变量，即使这个全局变量也是循环变量，但是编译器就可能很难分析出来了。同样，如果一个循环变量在函数任何地方被取了地址，那么编译器也很难分析出来这个变量是循环变量。
通常来说，只要是没有歧异的局部变量（歧异翻译自编译器中的Alias一词，指这个变量或内存位置由于被指针引用等原因，导致可能跟其他变量或指针指向的内存位置重叠），编译器能够非常好的分析出循环变量。

mathe · 发表于 2008-3-2 13:35:28

18#中举了两个通过仿射变换增加线程级并行度的例子。也就是想办法经过仿射变换后使得所有依赖向量最高一维分量全部为0(对应最外层循环没有跨循环迭代的依赖)。
同样，如果通过仿射变换使得变换后的所有依赖向量最低一维分量全部为0，那么，最里层循环就没有跨迭代的依赖，所以如果我们将最里层循环展开，就可以增加指令级并行机会。

mathe · 发表于 2008-3-2 13:49:11

前面介绍过还有一个余数变换（不知道英文叫什么，这是唯一个我从中文书上了解到的编译器优化技术，而且奇怪的找不到英文版的相关信息，而中文名字，我是通过google搜索找到这么一个名字，估计就是这种变换了，但是没有确认，下面我们就都使用这个名字），它也可以提供更多的指令级优化机会。
假设有一个一层的循环，那么这时所有依赖向量都是一维的，是一个标量，我们可以称为依赖距离。如果这个循环的所有依赖距离的最大公因子d>0,那么说明这个循环所有相邻的d次迭代之间都没有依赖关系，我们可以把循环相邻d次迭代展开，比如代码

for(i=0;i<n;i++){
...
}

复制代码

变成

for(I=0;I<n;I+=d){
for(k=0;k<d;k++){
i=I+k;
...
}
}

复制代码

变换以后的代码，最里层循环迭代次数只有d,但是所有迭代之间独立，所以展开后可以指令级并行

mathe · 发表于 2008-3-2 15:47:08

对于余数变换，我知道一个优化过程，但是不知道是否被正式公开发表过。
曾经有一个清华学生到我们公司，提出过一些相应命题和结论，而其中一个关键部分是一个复杂的数学问题，后来我花了好几天时间加以证明。不过关于这个结论，我们没有正式发表过，也没有查过是否以前曾有人发表过。
下面简单介绍一下整个思路
现在我们看一个例子

for(i=0;i<n;i++){
A[i] = B[i-1]; //(1)
B[i]=A[i-2]; //(2)
}

复制代码

对于上面的例子，语句(1)到语句(2)有一个依赖距离为2的真依赖，语句(2)到语句(1)有一个依赖距离为1的逆依赖。
我们可以看出对于这个例子，由于所有依赖距离的最大公因子为1，无法使用余数变换。
如果我们对第一个语句做Statement Shift,也就是单单对第一个语句关于循环变量平移一下，代码变成

A[0]=B[-1];
for(i=0;i<n-1;i++){
A[i+1]=B[i];
B[i] = A[i-2];
}
B[n-1]=A[n-3];

复制代码

那么经过变换后，循环中所有依赖距离都是3的倍数了（分别为0和3）
而关于这个优化的一般情况，转化为一个数学问题，我们可以得到:
http://bbs.emath.ac.cn/thread-214-1-1.html
中的一个难题。
在证明那个数学问题的同时，我们可以得到一个非常有效的计算变换的方法。这个数学问题大家可以先好好考虑下看看

可以看出在编译器中，数学也是无处不在的。
当然，如果再次把这个问题推广到多重循环，如果再结合么模变换或仿射变换，将是一个非常复杂的问题，
我还不知道是否有什么有效的方法。

kenmark · 发表于 2008-3-8 18:02:59

已作简单汇编，进行以下处理：
1.排版，消去无用回车N个（耗费人力时间N多。。），添加标题，大标题居中加粗小三，小标题加粗居中
2.去除无用回复，仅收录gxqcn老大的资源目录作为附录
3.图片，超级链接修复
4.公式作为图片插入（一个不行$g:V->bar(z^-)$）
5.图论问题并入文档
6.代码框简化，消去“复制到剪贴板”（未加严格排版）
由于最近比较忙，时间仓促，没有多加阅读，没有沟通mathe，水平有限，只能尽量做到不失真，仅仅作简单的汇总汇编。
期待下文，将继续关注，适时整理

关于编译器优化方面的知识.rar (100.34 KB, 下载次数: 23)

kenmark · 发表于 2008-3-8 20:14:04

呵呵，以前逛PEDIY，那里总是隔三岔五地整理精华本，现在看到LZ的连载，不免有整理之心，顺手就弄了一下呵呵～

kenmark · 发表于 2008-3-9 11:05:32

终于有时间看了一下！
关于Binary Translation我想提两句，最初的Reverse Engineering逆向工程技术就是为了进行Binary Translation，最早的：
D-Neliac decompiler, 1960.
正如Halstead在[Hal62]中所言，Donnelly-Neliac (D-Neliac) 反编译器是在1960年由J.K.Donnelly和H.Englander在海军电子实验室(NEL)制造。Neliac是NEL在1955年开发的一个Algol类型语言。D-Neliac反编译器从机器代码程序产生Neliac代码；为雷明顿兰德公司的 Univac M-460 伯爵夫人计算机和控制数据公司的1604计算机编写了不同版本。
事实证明，D-Neliac可应用于把非Neliac编译的程序转换为Neliac程序，以及在原来的高级程序中检测逻辑错误。这个反编译器证明了编写反编译器的可行性。

之后的很多时候，反编译的研究都是为了实现代码移植而进行的。
关于这部分的资料（有关IR2Src的技术，可以参考Reverse Compilation Techniques by Cristina Cifuentes http://www.itee.uq.edu.au/~cristina/dcc.html）
看雪学院上也有很好的中文译版

kenmark · 发表于 2008-3-9 11:11:43

常见的编译器优化在Code Optimization Effective Memory Usage里面有所提及（对于C和C++程序的）而且作者还列举了那时候主流的（现在淘汰了的）编译器对优化的支持，可惜作者只是介绍可以优化的内容，而不是理论，他用了一句“Unfortunately, providing a detailed description of the optimizing principles is a thankless job. Therefore, I will only describe what should be optimized.”“很遗憾，对优化原理进行详细的描述是一件吃力不讨好的事情。因而，这里只打算描述应该加以优化的内容。”
如果想了解一下关于可以优化的内容的话可以参考一下本书，当然书中还有一些关于Cache Subsystem等的优化，值得一看（不过比较老了，是VC6时代的内容了）
Code Optimization Effective Memory Usage 中文本《代码优化——有效使用内存》by Kris Kaspersky
英文版chm文件太大10.4M，就不上传了（网上可以搜到）

账号		自动登录	找回密码
密码			欢迎注册

[原创] 关于编译器优化方面的知识

循环变量的优化

简单汇编

评分

关于常见的编译器优化内容