代码优化概述
1.1.代码优化简介
代码优化是指对程序进行各种等价变换，使得从变换后的程序出发，能生成更高效的目标代码。

目标代码的质量，通常有两个衡量的标准：空间效率和时间效率。

有时空间优化也会导致时间优化（如减少指令条数），但通常它们是一对矛盾，不能兼顾。

代码优化的目的是产生更高效的代码，使程序以更快的速度、占用更少的空间运行。

对于编译器，代码优化分为三个阶段：
图1-1 代码优化流程图
为了获得更优化的程序，可以从各个环节着手。

首先，在源代码这一级，程序员可以通过选择适当的算法和安排适当的实现语句来提高程序的效率。

其次，再设计语义动作时，要尽可能产生高效的中间代码，同时还可以安排专门的编译优化阶段对中间代码进行各种等价变换，改进代码的效率。

最后，在目标代码这一级上，应该考虑如何有效地利用寄存器，如何选择指令，以及进行窥孔优化等。

对于编译优化，最主要的时机是在语法、语义分析生成中间代码之后，在中间代码上进行。

这一类优化不依赖于具体的计算机，而取决于语言的结构。

另一类优
化则是在生成目标程序时进行的，它在很大程度上与具体的计算机有关。

由优化编译程序提供的对代码的各种变换必须遵循如下原则[1]：
1)等价：经过优化后不改变程序运行的结果；
2)有效：优化后产生的目标代码运行时间较短，占用的存储空间较小；
3)合算：应尽可能以较低的代价取得较好的优化效果。

如果为实现一种
优化变换所花时间和精力，以及编译器编译源程序时的额外开销，不能
从目标程序的运行中得到补偿，那么是没有意义的。

在设计一个编译程序时，究竟应考虑哪些优化项目以及各种优化项目进行到何种程度，应权衡利弊，根据具体情况而定。

其中，控制流分析主要目的是分析出程序的循环结构.循环结构中的代码的效率是整个程序的效率的关键。

数据流分析进行数据流信息的收集,主要是变量的值的定义和使用情况的数据流信息.包括到达-定值分析;可用表达式;活跃变量。

最后，根据上面的分析,对中间代码进行等价变换。

对现代体系结构的编译器来说，代码优化非常重要，通过它能充分发挥硬件性能，提高执行效率。

所以对编译器的优化有更高的要求。

1.2.优化技术的分类
优化技术的分类有很多种方式，下面简单介绍传统的两种划分方式[2]：
1.根据优化所涉及的范围，现代编译器所使用的优化技术可以分为以下几
类：
1)局部优化（local optimization）
局部优化是指在基本块内进行的优化，考察一个基本块就可完成。

所谓基本块是指程序中顺序执行的语句序列，其中只有一个入口语句和一个出口语句。

程序的执行只能从入口语句进入，从出口语句退出。

这个代码序列中没有跳进或跳出语句（过程调用表示一种特殊的跳转），而且是顺序执行。

基本块可以通过有向无循环图(DAG)来表示，那么优化工作就是在DAG上所进行的一系列的变换，但是并不改变基本块所计算的表达式集合。

常用的局部优化技术包括局部公共子表达式删除、删除多余代码、交换语句次序、重命名临时变量。

2)循环优化（loop optimization）
所谓循环，简单而言就是指程序中可能反复执行的代码序列。

因为循环中的代码会反复的执行，所以循环的优化对于提高整个代码的质量有很大的帮助。

首先在控制流程图(CFG)中根据循环的定义找出循环，然后就可以针对每个循环进行相应的优化工作。

主要有以下三种：代码外提、删除归纳变量、强度削弱。

循环优化一直是研究的热点和难点，尤其是在并行处理系统中如何根据不同的循环类型进行循环置换(loop permutation)，提高循环内矢量运算的并行性，都是当前的热门研究课题。

3)全局优化(global optimization)
一个过程可以由多个基本块按照相应的流程来组成。

全局优化就是基于这些基本块之间的优化。

为了进行全局代码优化，必须在考察基本块之间的相互联系与影响的基础上才能完成。

首先必须进行过程内数据流分析(intraprocedural dataflow analysis)，然后编译器将收集的信息分配给各个基本块。

根据这些信息，我们可以建立相应的数据流方程，进而可以生成类似于ud链（引用-定值链）和du链（定值-引用链）这样的标准全局数据流分析结构。

基于这样的数据结构，进行过程内的全局优化工作。

常用的全局优化技术有复写传播(copy propagation) 、常量折叠(constant folding) 、删除全局公共子表达式等。

2.按照机器相关性，现代编译器所使用的优化技术可以分为以下几类：
1)机器相关优化
针对机器语言，依赖于目标机的结构和特点。

例如，寄存器优化，多处理器优化，特殊指令优化等。

2)机器无关优化
针对中间代码，不依赖于目标机的结构和特点。

例如，合并常量优化，消除公共子表达式,代码外提，删除归纳变量，强度削弱和删除无用代码等。

1.3.机器无关优化
本课题只涉及了机器无关优化工作。

那么我们就对机器无关优化作较为详细的讨论。

常用的机器无关优化技术有[2]：
1.代码外提
循环中的代码，要随着循环反复执行，但其中某些运算的结果往往是不变的。

对于这种不变运算，我们可以把它提到循环外。

这样，程序运行的结果保持不变，但程序运行的速度却提高了。

这种优化即即为代码外提。

2.强度削弱
强度削弱是指把程序中执行时间较长的运算替换为执行时间较短的运算。

例如把循环中的乘法运算用递归加法来替换。

进行强度削弱后，循环中可能出现一些新的无用赋值，可以把它们删除。

强度削弱对下标地址变量计算来说，实际上就是实现了下标变量地址的递归计算，对于减小下标地址计算的强度是非常有效的。

3.归纳变量删除（删除无用代码）
归纳变量是指在循环中每次执行增长值固定的变量。

它包括循环控制变量和其它依赖于循环控制变量的变量。

如果循环中对变量I只有唯一的形如I:=I+C
的赋值，且其中C为循环不变量，则称I为循环中的基本归纳变量。

如果I是循环中一基本归纳变量，J在循环中的定值总是可归化为I的同一线性函数，则称J是归纳变量，并称它与I同族。

一个基本归纳变量也是一归纳变量。

删除归纳变量是在强度削弱后进行的。

4.循环展开
循环展开是指针对源程序中的循环结构，编译时在循环次数已知的前提下，通过将循环体重复多次来减少循环转移的开销，同时通过循环体的增大提高循环体内进一步优化的可能性。

循环展开技术虽然能够减少转移开销、提高程序的执行速度，但它同时也增加了程序的空间开销，对cache命中率产生不良的影响。

而且，循环体重复的次数也要视目标机中通用寄存器的个数而定。

如果每次重复都只是简单的复制，那么便会出现寄存器相关的问题，从而大大降低循环展开技术的优化效果。

5.过程内嵌
过程内嵌是指针对源程序中的某些过程调用，找到被调过程的过程体，如果该过程体短小而且没有循环，则将它拷贝到调用处，从而消除过程调用的开销，增大指令调度的可能性。

同循环展开技术的不良影响一样，过程内嵌也大大增加了程序的空间开销，降低了cache的命中率。

6.常量合并
常量合并又称为常数表达式求值（constant expression evaluation），是指在编译时刻就对已知操作数的值为常数的表达式求值，并且用该结果值来替代这部分表达式。

7.常数传播
所谓常数传播是指对于基本块中的某个变量，如果该变量的值始终为一常数，那么就用这个常数值来替代所有表达式中的这个变量。

常数传播不仅为全局范围内进行常量合并优化提供了基础，而且还有助于不可达代码删除优化的进行，因为在测试变量被发现是常数之后，某些代码便会变得不可到达。

8.局部公共子表达式删除
如果表达式E已经被计算过，并且从先前的计算到现在E中所有变量的值没有改变，那么E的这次出现就称为公共子表达式。

对于公共子表达式，没有必要对它们再进行计算，只需将前面计算过的值赋给表达式的结果变量就行了，这种优化方法用在程序基本块之内便称为局部公共子表达式删除。

9.复制传播（复写传播）
形为A:=X的赋值称为复制(copy)。

若用X来替代所有表达式中的变量A，便称为复制传播。

如果变量A的值不再用到的话，则赋值表达式A:=X.便是多余的，可以消除掉。

（上面用红色字体标注的优化方式为实验四要求做的内容）。