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

mathe

　　一直想给大家介绍一些编译器优化方面的知识，只是又觉得这方面知识内容太多了，介绍起来太花费时间了，实在没有精力去逐一介绍，并且很多编译器方面术语我都不知道中文该如何翻译（国内相关资料应该也比较少，很有可能有些术语都没有标准的翻译），所以一直非常犹豫要不要讨论这方面的内容，所以就先随便试一试看吧，等每次有空有兴趣时就可以试着随便写一点。
　　我觉得大概懂得编译器到底可以做一些什么优化工作，对于写出高效率的程序是非常重要的。只有知道编译器大概会怎么去做，我们才能够知道用怎么样的代码会提供给编译器更多的优化机会，怎样的代码不会阻碍编译器的优化，甚至于，在知道编译器无能为力的情况下，可以通过手工模拟一些编译器的变化过程对代码做优化。
而我讨论的重点将在于通常编译器会做那些平台无关的优化。至于文法分析，代码生成之类的内容，我不会去介绍（其实我也不熟悉）。
　　先大概介绍一下编译器。通常编译器可以分成前端(FrontEnd/FE)和后端(BackEnd/BE)两个部分，其中前端负责将用户的源代码翻译成一种编译器的内部表示(Intermedium Representation/IR),我们简称IR. 这个就是通常词法分析，语法分析所做的事情。对于不同的源代码语言，我们需要不同的前端，但是我们可以通过使用公共的IR,使得对于不同的语言，可以使用相同编译器的后端。而编译器的后端，现在通常分成两个部分，一部分负责同平台无关的优化工作，我们通常称为中间端(MiddleEnd/ME),另外部分负责同平台相同的优化工作和代码生成（通常指生成汇编语言或直接二进制机器代码），我们通常称为代码生成部分(Code Generation/CG).
　　同样，对于不同的平台（不同的CPU,不同的操作系统），我们需要不同的代码生成部分，但是整个编译器的中间端可以在不同的源代码，不同的平台之间共享。
有一点需要注意的是，这里说的不同语言，是指像C/C++/Fortran/Pascal之类的静态编译的语言，而不包含像Java/C#之类需要在运行时间再编译的语言（这是因为这两种编译器的实现方法完全不同），而对于Java/C#之类的语言，所用的编译器就是另外一个话题了，不过其中用到的大部分技术还是类似的。
而我将会把介绍的重点放在编译器的中间端(ME).

　　关于介绍编译器优化的书，我推荐大家可以看一下美国的Steven S. Muchnick写的Advanced Compiler Design and Implementation. 国内有影印版，中文名字叫《高级编译器设计和实现》。但是有没有翻译成中文的版本我就不知道了。
　　而现成的比较好的编译器源代码，我推荐open64,这个可以在http://www.open64.net/上找到，这个编译器的前身是sgi的编译器pro64,后来移植到Itanium芯片上。根据open64网站上的信息，现在可以用于Itanium (IA64), i386 (32位x86通用芯片)和X86_64(64位x86通用芯片)。不过好像只支持Linux (Windows可以试着安装一下cygwin看看).对于语言，它可以同时编译C/C++/Fortran. 在我印象中，这个编译器的前端用的是gcc的前端，也就是说必须安装了gcc才能够使用open64,但是据说编译出来代码的性能比gcc要好很多。

mathe

关于编译器优化的通俗介绍，我过去谈到过一篇关于浮点优化的内容：
http://blog.csdn.net/mathe/archive/2006/11/26/1415321.aspx
从那个里面可以看出，编译器所能够做的优化同通常人的理解会有很大的出入

mathe

刚才又想到一个问题，到底编译器的定义是什么？什么样的软件才能够称为编译器呢？
通常，编译器应该是一个将一种面向用户的"高级语言"翻译成面向机器的"目标语言"的软件。
但是实际上，现在的编译器范畴要远远大于上面的定义。

　　比如现在的编译器可以支持源代码到源代码的编译。比如open64里面，印象中提供了一个叫ir2c和ir2f的工具，也就是可以将open64中经过优化的IR重新翻译成C语言或fortran语言（当然翻译过程可能会有错误）。那么将编译器同这个ir2c或ir2f功能相结合，就可以看成一个从源代码到源代码的编译过程（中间可以有优化）。上面过程可以是同一种语言之间的等价变化，也可以是不同语言之间的等价变换（不同语言之间的变化更难，通常由于语言特性的不同，甚至于有些语句可能无法翻译回去）。

　　而实际上，很多编译器（特别是用于研究的编译器）都是只支持源代码到源代码的编译过程的，我们称这种编译器为Source to Source Compiler.

　　在另外一方面，比如Intel推出Itanium的时候，就遇上一个问题。虽然Itanium提供了许多理论上非常优秀的功能，可是实际上，虽然Itanium硬件直接提供了对x86的支持，但是性能很差，而实际上存在的大部分软件都是编译成x86代码，所以Itanium平台上运行软件的速度非常慢。Intel就提供了一种可以在运行时将x86代码重新编译成Itanium代码的软件，这个软件也可以看成是编译器的一种，通常称为Binary Translation.

gxqcn

这是我在自学汇编时，对我帮助比较大的一些文档，共享出来，希望对大家有所帮助：

• 怎样优化Pentium系列处理器的代码，虽然翻译自2000年，但颇具参考意义
  
• optimization_manuals.zip(3.81MB)，源于Software optimization resources，包含：
  • Optimizing software in C++: An optimization guide for Windows, Linux and Mac platforms
  • Optimizing subroutines in assembly language: An optimization guide for x86 platforms
  • The microarchitecture of Intel and AMD CPU’s: An optimization guide for assembly programmers and compiler makers
  • Instruction tables: Lists of instruction latencies, throughputs and micro-operation breakdowns for Intel and AMD CPU's
  • Calling conventions for different C++ compilers and operating systems
    
  
  
• Intel 官方出品的 Optimization Reference Manual
  
• SIMPLY FPU: SimplyFPU.chm (324.54 KB, 下载次数: 38)
  2008-2-11 15:38 上传

  点击文件名下载附件
  SIMPLY FPU
  by Raymond Filiatreault,Copyright 2003

mathe

大概看了一下Software optimization resources，写得挺不错的

mathe

这里我想先讨论下一类关于循环语句的一种优化，可以统称为么模变换。
这种循环变换理论上结果非常漂亮，可惜我认为很多C/C++写的代码由于指针的存在，
编译器无法准确分析数据依赖关系，很多这样的机会编译器都无法真正做掉。
而这种优化往往可以提高代码对缓存的使用，提高指令级并发度，以及提高线程级并行度。
我们先分析一个最简单的情况。

1. int a[N][M];
   
2. 
   
3. for(i=0;i<M;i++)
   
4.   for(j=0;j<N;j++)
   
5.     a[j]=...;

复制代码

对于这样的代码，如果编译器能够将代码变换成

1. for(j=0;j<N;j++)
   
2.   for(i=0;i<M;i++)
   
3.     a[j]=....;

复制代码

那么变换以后的代码对于数组a的访问将由不连续的方式变成严格顺序方式，由于相邻的数据在
同一条缓存线(Cache Line)上，而且顺序访问硬件非常容易做数据预取，所以速度可以极大提高。
上面这种变换称为Loop Interchange.

同样有时可能由于某些需要，我们需要更改一个循环执行顺序，比如上面循环变化为

1. for(j=0;j<N;j++)
   
2.   for(i=M-1;i>=0;i--)
   
3.     a[j]=....;

复制代码

这种变化称为Loop Reversal

而还有另外一种更加复杂一点的变化，比如：

1. for(i=0;i<M;i++)
   
2.   for(j=0;j<i;j++)
   
3.        a[i-j]=f(i-j);

复制代码

=>

1. for(i=0;i<M;i++)
   
2.   for(j=1;j<=i;j++)
   
3.        a[j]=f(j);

复制代码

这个变换保持i不变，但是新的j变成原先i和j的线性组合(i-j),这种变换称为Loop Skewing.
而这些变换还可以组合起来。
如果我们把循环体里面每次迭代内容(iteration)看成一个点，用图画出来，在图上执行顺序总是先从左到右然后从上到下，
我们可以得到如下的图（循环变换实质上就是改变各个“迭代”被执行的顺序）

当然，对于给定的代码，上面所述的变换不一定都是非法的，实际过程中我们首先需要判断给定的一个代码，到底那些变换以及那些变换组合是合法的。
编译器里面需要通过数组的数据依赖关系(Dependence)分析来系统的解决这个问题。
此外，除了上面的这些变换（么模变换），理论上还有更加广的一类变换称为仿射变换(affine transformation)可以使用更多的变换方法，而它也同样依赖预数据关系的分析。
此外还有一种用于增加指令级并发度的优化（叫余数变换）同样也需要数据依赖关系分析。
所以下一部分我们将先讨论循环中数据依赖关系的表达方式

gxqcn

好文章啊！希望楼主再接再厉，让大家尽早见到下一部

mathe

写这个比较费功夫，还是要多等等。
最近上班一直在写代码，回家还要看宝宝，有点空闲还在想想数学题目，所以比较难抽空出来。

mathe

假设现在有一个k重循环

1. for(i1=....){
   
2.     for(i2=...){
   
3.           ...
   
4.           for(ik=...){
   
5.           }
   
6.           ...
   
7.     }
   
8. }

复制代码

而且所有语句都在最内层循环体里面。
那么i1,i2,...,ik每个不同取值时对应的循环体的一次执行过程(iteration,不知道改如何翻译好，下面称为循环体一次迭代吧）
我们可以用标记(i1,i2,...,ik)来表示这个循环体对应的一次迭代
我们把这个把这个标记称为这个迭代的坐标。
显然，在这个坐标表示下，循环体的一次迭代可以看成k维空间中格点（坐标值都是整数的点）
现在我们查看循环迭代的执行顺序同其坐标之间的关系
比如现在有两个不同的迭代坐标
$(s_1,s_2,...,s_k)$
$(t_1,t_2,....,t_k)$
可以看出，如果$s_1=t_1,s_2=t_2,...,s_h=t_h,s_{h+1}<t_{h+1}$
那么$(s_1,s_2,...,s_k)$必然比$(t_1,t_2,....,t_k)$先执行。
对于给定的一批迭代坐标，如果我们将它们按字典顺序排序(任意两个坐标，从左到右，第一个不同的项小的排在前面），
那么它们的执行顺序就会同这个排列顺序相同。
所以循环迭代的执行顺序是同它们对应的坐标的字典顺序排序是相同的。
对于上面两个坐标，当$(s_1,s_2,...,s_k)$排在$(t_1,t_2,....,t_k)$之前时，我们记$(s_1,s_2,...,s_k)<(t_1,t_2,....,t_k)$
同样，有时我们要看两个迭代坐标的差值，比如对于上面的两个迭代坐标我们可以看
$(s_1,s_2,...,s_k)-(t_1,t_2,....,t_k)=(0,0,...,0,s_{h+1}-t_{h+1},...,s_k-t_k)$
如果一个迭代坐标的差值中，从左到右第一个非零项为负数，我们称这个差值向量为负向量;如果第一个非零项为正数，我们称这个差值向量为正向量。
比如上面例子中$s_{h+1}<t_{h+1}$所以对应的差值向量$(0,0,...,0,s_{h+1}-t_{h+1},...,s_k-t_k)$为负向量，记为
$(0,0,...,0,s_{h+1}-t_{h+1},...,s_k-t_k)<0$
同样可以定义>符号
现在举一些实际例子，比如
$(1,2,3)<(2,1,1)$
$(2,2,3)<(2,3,1)$
$(0,-1,1)<0$
$(0,0,1,-2,1)>0$
$(0,0,0,0,0)=0$

mathe

下面我们来看编译器中数据依赖关系的几种类型
例子1：

1. X=1;                     (1)
   
2. Y= a+X;                  (2)

复制代码

那么上面代码中，语句(1)定义了X而语句(2)使用了这个X,对于这种关系，我们称这里有从语句(1)到语句(2)的真依赖关系(true dependence)
例子2：

1. X=1;                     (3)
   
2. ….
   
3. X= a;                    (4)

复制代码

那么上面代码中，语句(3)定义了X而语句(4)又重新定义了X;对于这种关系，我们称这里有从语句(3)到语句(4)的输出依赖关系(output dependence)
例子3：

1. Y=a+X;                   (5)
   
2. X= b;                    (6)

复制代码

那么上面代码中，语句(5)使用了X而语句(6)又重新定义了X;对于这种关系，我们称这里有从语句(5)到语句(6)的逆依赖关系(anti dependence)
例子4：

1. Y=X+a;                   (7)
   
2. Z= X*2;                  (8)

复制代码

那么上面代码中，语句(7)使用了X而语句(8)也同时使用了X;对于这种关系，我们称这里有从语句(7)到语句(8)的输入依赖关系(input dependence).
通常如果程序中两个语句之间有前面三种依赖关系，我们就不能够简单交换两个语句（不然代码执行结果就不同了）;但是对于最后一种依赖关系,即使出现这种依赖关系，我们还是可以交换两个语句。所以通常情况，我们说到数据依赖关系时，指得是前面三种数据依赖关系。（有时候，编译器可以通过某些手段使得我们可以只考虑第一种依赖关系,这也是为何只有第一种被称为真依赖关系）