一、代码优化的阶段

欲提高源程序的运行速度，需要经过几个阶段的优化：

用户对源程序进行优化（和编译器无关，与coder设计的算法有关）编译器前端对中间代码进行优化编译器后端对目标代码进行优化

两个编译器必须等价，编译的结果必须是正确的，即使有99.99%的可能性是不正确的，但是效率很好也不行，正确性是根本。

二、中间代码优化的分类

从优化的种类来看，中间代码的优化可有如下分类：

局部优化

循环上的优化（所有优化方法效果最好的） 1. 循环不变体外提 循环中不因循环而改变的部分可以提到循环的外部 2. 削减运算强度 在一些循环上的计算转换成另一种计算方式实现，比如b=a*2 -> b=a+a 基本块的优化（按照某些规则划分成基本块） 1. 常表达式节省 2. 公共子表达式节省

全局优化

全局数据流分析，从而使优化的效果更好 考虑基本块里如何优化，已经得到的值和变量的表，全局得到更多的信息进行分析。 在局部优化的基础上进行全局优化才有更大的提高，否则直接进行全局优化的提升效果不明显。

三、常见的编译优化的种类

1. 数学上的优化

情况一：（主要是在生成中间代码的时候会产生）

(-,a,0,t1) (*,a,1,t2) //这种a+0，和a*1的没有太大意义的运算，这样的四元式可以删除 //正常写普通的代码一般不会出现这种情况 //但是在一些不明显的地方，比如计算数组中的元素a[i]时，用【i-（数组下界）】xsize //数组下界为0的时候和size=1的时候都会产生上面的四元式 //可直接换但是还要将运算结果进行处理

情况二：

2*a->a+a a^2->a*a

原则上说，可以不计算的直接删去其四元式，直接写出结果；高运算强度的可以转化成低运算强度的。

2. 表达式短路问题

如果在计算一个表达式的时候可以不用将整个表达式的值都计算出来就可以确定表达式的结果，在这种情况下，后面的计算可以省略。 或运算：如果计算出第一个表达式的结果是1可以直接返回 true 与运算：如果计算出第一个表达式的结果是0可以直接返回false

3. 常表达式的节省

计算过程中有一个表达式是33.14，这个实际上是两个常数，他的结果我是可以计算出来的，这样我们在编译的过程中把33.14算出来，在目标程序的进行中就不用进行计算了。通过编译程序将可以计算出的结果直接计算出来然后将相应位置替换成计算出的结果。把有关工作交给编译程序进行可以提高生成的目标程序的运行效率，编译程序可以稍微慢些的工作，因为最后看的还是生成的目标程序的运行效率。

4. 公共子表达式节省（消除重复操作）

所谓公共子表达式即两个子表达式的计算结果是一样的，不需要重复的进行计算，第一次计算出来之后，后面的计算可以利用前面的计算结果。例如前面有表达式ab，后面又有表达式也是ab，而且在第二个表达式和第一个表达式中间，a和b的值没有被改变过，那第二个a*b表达式实际上是可以不用计算的，只需要把前面的计算结果拿过来就可以达到计算的目的。这种情况在下标变量的计算中体现的非常明显，比方说a[i][j]和a[i][k]，下标变量的计算先计算a[i]的地址然后计算j，然后计算a[i][j]的地址，a[i][k]也是一样先计算a[i]的地址在根据k计算a[i][k]的地址，所以前面关于a[i]的计算结果是完全一样的。这样就可以不用重复计算，利用前面的结果达到计算目的。

5. 循环不变量式外提

循环不变式外提，在循环中，如果有一个表达式的值在循环中不会改变，就需要把它提到循环体的外面去。比方说有一个双重循环1-100和1-100，那么整个两重循环计算下来就是1万次，比方说里面有一个ab的表达式，在循环过程中ab的值如果不改变，那他就重复计算了9999次，假如把ab提到循环体的外面只需要计算1次，在循环里只需要用到它的计算结果。所以这样的表达式在循环体里面是不变的，我们要把他提到循环体的外面，从而提高我们的执行效率，这种效率的提高是最高的。特别是计算量很大的情况下，比方说有多重循环，这种循环不不变式外提可以大大提高程序的执行效率，这种提高的效率大概可以提高十几倍甚至是几十倍，串式程序的并行处理很大的一个研究重点，都是放在循环的并行计算上，比方说1~1000次的循环把它分成段，在不同的处理机上进行执行，从而提高程序的执行效率

6. 削减程序的运算强度

削减程序的运算强度。这个也通常是针对循环的，一种特例的情形，比方说在程序设计语言中通常来说，一般的程序循环有三种方式分别是： 1）for循环（有的语言中也称作是步长式的循环），循环形式是for i=e1 to e2 ;step e3{} 也就是说它的执行是i开始获取一个循环初值e1，然后每次循环i都加上e3的值，一直当i大于e2就结束循环，比方说for1=1to 100;step 1,就是1-100步长是1执行100次。 2）while循环，“当型循环”（） 3）直到型循环 do until ~~的形式。

7. 寄存器优化

生成目标代码的时候一定是和目标机相关的，对于目标机来说提供多少个寄存器，比方说提供了8个，当目标程序真正执行的时候，这8个寄存器是如何被分配的，这是一个问题。简单的说假如说寄存器有空闲的时候，分配方案比较简单，空闲的就分配，这个没问题，什么时候会有问题呢？ 有这样几种情况： 要用寄存器的时候，是否有空闲的寄存器，如果没有空闲的怎么办？需要剥夺一个寄存器，如何来剥夺？类似的还有内存和外存进行淘汰页的算法是类似的，只不过这个是在更高一级的层面上，寄存器和内存间的变换。这是寄存器分配优化

8. 消除无用语句，消除冗余代码

消除无用语句，消除冗余代码，假如一个条件语句，if e s1 else s2 ，如果表达式E的值是一个true，那么s2是不可能用到了，所以这个命令就可以删掉了，这个命令也直接可以用s1来替换掉，当然这是一种特殊的情形，产生冗余代码实际上也是这么产生的

9. 中间变量优化

中间变量的优化，生成中间代码的时候会产生大量的临时变量，大量的临时变量的特点一般都是产生之后使用一次就会不再用了，如果是说有一些临时变量和另外一些临时变量之间没有交集的话，不需要为每一个临时变量都分配独立的存储单元。最简单的方式，把产生临时变量一直到使用临时变量这个区域比方说把它定义为临时变量的活动区，假如两个临时变量的活动区不相交，实际上他们可以共用同一个存储单元，那么这种优化实际上就是临时变量的存储空间上的优化

10. 目标代码优化

是目标代码的优化，可以通过确定目标代码来减少目标程序的指令个数来提高目标程序的执行效率，比方说有一个变量的值在寄存器里，运算出来的中间结果在寄存器里，假如直接让他参与运算之后，就不用往内存中存了，什么时候需要存，什么时候不存，什么时候需要把它放在寄存器里，这就是需要对目标程序进行的一种优化，根据使用情况来进行。

11. 全局优化

总而言之这种优化还有很多，比方说全局的数据流分析和全局的优化，因为前面考虑实现的时候由于优化的技术可能比较复杂，都是在局部区做的，比方说一个基本块上做的，要想做到全局的需要对全局的程序做全局的数据流分析，这样的话可能就更复杂了，如果没有特殊需求，一般来说是不做这样的优化的： 第一个原因就是编译代价太大，因为要做各种各样的分析，导致编译代价很大。 第二就是提高的效率也并不是十分的明显。

如果说没有特殊的需求，前面做的局部优化已经能达到想要的效果，全局优化就不用做了，特殊需求的时候才想办法处理。

⚠️优化中要注意的一个问题就是优化是在保证正确的情况下进行的，任何一个程序的优化也不能做到最优，而是在一定程度上来提高程序的执行效率。所以优化的过程一定是在保证程序正确的前提下来进行的。

四、基本块

（一）基本块的定义

基本快：是一个命令的序列，每一条命令都是按照顺序来执行的，进入基本块只能从第一条命令进入，退出基本块只能从最后一条命令退出，也就是说基本块是一个整体，要执行的话就全都执行从头到尾的顺序执行，这样一个特性对于程序进行分析或者是对中间代码进行分析有什么好处呢？对程序基本块中变量的性质是可判定的，假如不是基本块的话，x=10；L y=x+1；如果说只能从x=10这条语句顺序执行的话，y=x+1，这个x就是一个已知的，就是10，y就是11.但是假如说它有另外一个入口，其他地方有一个goto L，就不能判断x的值是不是10，因为外面有一个转移，比方说x=1； goto L x的值就不一定是10了，不是基本块的话程序的性质就不太好判断。假如说是一个基本块都是顺序往下执行的话，那么每一个变量的值是怎么获取的、怎么传播出来的，就可以判断出来，这对我们的处理就非常有意义。因此在基本块上做优化使得问题变的相对简单了。

（二）基本块的划分原则

进入一个程序，（整个程序的第一条)四元式就是一个基本块的入口四元式；遇到一个转移性的四元式，这条转移性的四元式是结束了一个基本块，它的后续四元式就可以作为下一个基本块的第一条四元式；遇到一个定位性的四元式或者是标号性的四元式，就结束一个基本块，并作为下一个基本块的第一条四元式；那么遇到一些函数的结束标示，就结束当前的四元式。例如p=&x； *p=5； y=x+x； 因为p是间接取址的，所以要结束这个标准块，否则也还是不知道如何来判断。

比方说goto还有（then t1，- ，-）目标程序运行到这的时候要判断t1是真是假，如果是假的话就要跳过t1，所以一定是要产生一个跳转指令的，还比如else这种，也就是说s1执行完一定要产生一个跳转指令跳过s2。 比方说循环指令中的while四元式，当循环体循环结束之后要产生一个跳转指令，要转移到前面重复计算的表达式的位置，假如没有这样一个四元式， 就没有办法确定转移到什么地方。这样的四元式就起到一个定位型四元式，还有比方说endif等等。还有对间接变量的赋值，也表示一个基本块的结束，这是基本块划分的原则，总的来说最关键的两点就是遇到转移型四元式和定位型四元式的开始

五、常表达式节省

在编译过程中能够计算出值的表达式，就在中间代码这级给它计算一个结果，这样就不需要在目标程序执行的时候进行计算了。

首先构造一个表，即变量的值表，表中元素是一个二元组，表项左部是一个变量名或者是一个临时变量，右边是已知它的值是什么，就填到这里。以后的优化算法也就比较简单，通常来说是这样做的：进入到一个基本快的时候把这个表清空，遇到一个运算型的四元式，比方说有算符 a b t1，首先看一下a和b是不是常量，如果是常量当然可以进行计算，就把t1填到表里。如果是变量的话，就要去表中查一下有没有变量对应的值，如果有值，就把这个变量用值来替换然后来看看可不可以进行计算，能计算就进行计算，不能计算替换完了之后，值就放到四元式中。如果遇到一个赋值型四元式，比方说b=a，就要到表里去查a有没有值，如果a是已知的，就把b填到表里，把a的值取出来填给b。按照这样顺序进行计算，能够算出常量值的四元式就被节省掉了。这里要注意，运算型的四元式实际上第一步，严格来说，用常量值替代运算符，比方说3*3.14 t1，就算出t1的结果，以后用到t1的时候就从表里取t1的值就可以了中间可以夹杂着用常量定值表对原有四元式进行替换，如果四元式都变成常量的就删除，否则就留着