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

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];
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}符号 现在举一些实际例子，比如 $(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). 通常如果程序中两个语句之间有前面三种依赖关系，我们就不能够简单交换两个语句（不然代码执行结果就不同了）;但是对于最后一种依赖关系,即使出现这种依赖关系，我们还是可以交换两个语句。所以通常情况，我们说到数据依赖关系时，指得是前面三种数据依赖关系。（有时候，编译器可以通过某些手段使得我们可以只考虑第一种依赖关系,这也是为何只有第一种被称为真依赖关系）