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

用户对源程序进行优化（和编译器无关，与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的值就可以了
中间可以夹杂着用常量定值表对原有四元式进行替换，如果四元式都变成常量的就删除，否则就留着

文章目录
循环优化概述.
计算必经节点集.
循环查找算法.
1.查找回边.
2.查找循环.
代码外提.
强度削弱.
删除归纳变量.

循环优化概述.
什么叫做循环？循环就是程序中那些可能反复执行的代码序列。也正是由于这部分代码序列可能会被反复执行，所以在进行中间代码优化时应着重考虑循环优化，这对提高目标代码的效率起到很大的作用。为了进行循环优化，首先需要确定的是程序流图中哪些基本块构成一个循环。按照结构程序设计思想，程序员在编程时应使用高级语言所提供的结构性的循环语句来编写循环。而由高级语言的循环语句所形成的循环，是不难找出的。对于循环中的代码，可以实行代码外提、强度削弱和删除归纳变量等优化操作。一个中间代码序列的程序流图如下所示：



我们不难看出，其中B$_2$和B$_3$分别构成一个循环，{B$_2$,B$_3$,B$_4$,B$_5$}构成一个范围更大的循环。而我们要进行循环优化，首先需要知道循环在哪里，接下来，我们就一步步给出，整个循环优化的过程。
计算必经节点集.

【定义】：若从首结点出发到达结点N$_j$的每一条通路都必须经过结点N$_i$，那么我们称N$_i$是N$_j$的必经节点，记为N$_i$ dom N$_j$，其中dom是dominate的简写。那么N$_j$所有必经节点的集合，就是N$_j$的必经节点集，记为D(N$_j$).

计算程序流图中必经节点集的算法也是一个不动点算法，通过每一次的迭代来计算一个结点的必经节点集。当程序流图中所有结点的迭代计算结果都不发生改变时，说明已经获得了最终的结果，算法宣布结束。下面我们给出计算必经节点集的算法：



这里我们也给出一个例题，作为计算必经节点集算法的收尾：



【下图引用自中南大学徐德智老师的编译原理2020年授课PPT】



需要注意的是，该算法并不像图中那样，一次迭代计算就可以确定结果，而是需要再一次迭代确认了所有的结点都没有发生变化，才能确定最终结果的。
循环查找算法.
1.查找回边.

【定义】如果一个程序流图中存在有向边<N$_i$→N$_j$>，并且N$_j$∈D(N$_i$)，那么我们称有向边<N$_i$→N$_j$>是一条回边。

依旧是我们前一部分给出的实例，考察其中的回边：



【下图引用自中南大学徐德智老师的编译原理2020年授课PPT】


2.查找循环.
求出了程序流图中的回边之后，我们就可以基于回边来查找循环。具体的方法是，若<N$_i$→N$_j$>是一条回边，那么该回边构成的循环中的结点包括：N$_i$和N$_j$以及所有不经过N$_i$能够到达N$_j$的结点。我们以上图中求出的三条回边为例，6→6确定的循环中只包括结点6；7→4确定的循环中包括结点有{4，7，5，6}；4→2确定的循环中包括的结点有{2，4，3，5，6，7}。



【下图引用自中南大学徐德智老师的编译原理2020年授课PPT】


代码外提.
至此我们已经完成了查找循环包含结点的工作，接下来就是要对循环体中的中间代码进行优化了。循环中的某些代码虽然随着循环反复地执行，但其中某些运算的结果并没有发生改变，例如循环中有形如A:=B op C的代码，并且如果B和C都是常数，或者到达它们的定值点都在循环外，那么不管循环多少次，每次计算出来得到的B op C的结果都是不变的，对于这样的不变运算，我们完全可以将其外提到循环以外，避免其随着循环多次计算。如此一来，程序的结果没有发生变化，但程序的运行速率却得到了一定程度的提高，这就是代码外提。

【定义】所谓变量A在程序中某一点d的定值到达了另一点u，或者说变量A的定值点d达到另一点u，指的是程序流图中从d有一条通路到达u，并且通路上没有A的其它定值点。

实行代码外提时，我们在循环的入口结点之前建立一个新结点(基本块)，称为循环的前置结点，该前置结点以循环的入口结点为其唯一后继。并且原来流图中从循环外引到循环入口结点的有向边，都改为引到该前置结点。如下图所示：



我们考虑的循环结构，其入口结点都是唯一的，从而其前置结点也是唯一的，我们后续进行代码外提时所有外提的代码都将提到前置结点中。下面一段Pascal源程序，是我们叙述代码外提的第一个例子：
for I:=1 to 10 do
	A[I,2*J]:=A[I,2*J]+1

它对应的中间代码序列如下：



【下图引用自中南大学徐德智老师的编译原理2020年授课PPT】



考察序号为3和7的语句，因为循环中并没有J的定值点，所以其中J所有引用的定值点都在循环外，从而3和7都是循环不变运算；
考察序号为6和10的语句，分配给数组A的首地址addr(A)的值并不会随着循环的一次次执行而改变，所以6和10也都是循环不变运算。

所以我们可以做出这样的判断：3与7、6与10都可以外提到该循环的前置节点中，进行了代码外提之后的中间代码序列如下所示：



【下图引用自中南大学徐德智老师的编译原理2020年授课PPT】



那么问题又来了，是不是在任何情况下，都可以将循环不变运算进行外提呢？我们看第二个例子：



从程序流图中我们不难看出，{B$_2$,B$_3$,B$_4$}构成了一个循环，并且B$_2$是入口结点，B$_4$是出口结点。

【定义】出口结点是指循环中具有如下性质的结点：从该结点有一条有向边引到循环外的某结点。

图中我们也不难看出，基本块B$_3$中的I:=2语句是循环不变语句，那么我们是否可以直接将这一语句外提到循环以外的前置结点B$_2'$呢？我们暂且认为可以这样做，外提之后的程序流图如下所示：



我们看外提了I:=2这一语句的程序流图，执行到基本块B$_5$时，变量I的值总会是2，从而J的值也会是2.但我们需要注意的是，在原始的、没有进行I:=2外提的程序流图中，B$_3$并不是B$_4$的必经结点。我们在原始流图中考虑X=30、Y=25的情况，这样的情况下B$_3$是不会被执行的，所以执行到B$_5$时变量I的值应该是1，从而J的值也应该是1而非2.那么很显然，我们进行了I:=2外提的程序已经改变了程序运行的结果，这必然是不允许的。问题到底出在什么地方呢？其实前面已经点出，B$_3$并不是循环出口结点B$_4$的必经节点，再直白一点说，B$_3$中的代码并不一定会对B$_4$中的代码起到作用，但如果我们将其外提到循环的前置结点，那么该外提的语句必然是会对B$_4$产生影响的，这就导致了程序运行结果被改变的风险，我们并不允许这样的风险存在。

所以从这个例子中我们可以看到，当一个循环不变运算要外提到循环的前置结点时，要求该循环不变运算的语句所在的结点是循环的所有出口结点的必经结点。

另外，我们注意到，如果循环中变量I的所有引用点都是B$_3$中I的定值点所能到达的，I在循环中不再有其它的定值点，并且出循环之后也不会再引用变量I的值(即在循环外的循环后继结点入口，变量I不是活跃的)，那么即使B$_3$不是B$_4$的必经结点，还是可以将I:=2外提到循环的前置结点，因为这样做并不会改变程序的结果。

再一个例子，如果我们将上述程序流图中的基本块B$_2$改为：
I:=3
if X<Y goto B3

考虑B$_2$中I:=3外提的问题。

通过计算必经结点集可以发现，B$_2$确实是循环出口结点B$_4$的必经结点，那么我们是否可以将I:=3进行代码外提呢？同样的论述过程，我们姑且认为可以，那么如果程序的执行过程是2-3-4-2-4-5，则执行B$_5$时的变量I值为2，从而J的值也是2；而如果不进行外提操作，那么同样的执行过程下，I和J的值都应该是3，而非2.这一错误的原因在于，循环中除了B$_2$以外，B$_3$也对同一个变量进行了定值。

所以从这个例子中我们可以看到，当我们将循环不变运算A:=B op C外提时，要求循环中的其它地方不再有A的定值点。

第三个例子，也是最后一个例子，我们看下面一个程序流图：



考察基本块B$_4$中循环不变运算I:=2这一语句的外提操作。首先，B$_4$结点就是整个循环的出口结点，并且B$_4$结点也是其本身的必经结点；其次整个循环{B$_2$,B$_3$,B$_4$}中也没有第二个对于变量I定值的语句。那么我们是否可以将这一语句外提呢？同样的方法，我们还是暂且认为这一语句可以外提，再比较对于同一个执行过程，外提前后的执行结果。我们考虑X=0、Y=2的情况，循环的执行流程是2-3-4-2-4-5，代码外提前，程序的执行结果为J=2；而代码外提后，程序的执行结果为J=3.

通过这个例子，我们看到，当将循环不变语句A:=B op C进行代码外提时，要求循环中所有对于A的引用点都是并且仅仅是这一定值语句所能到达的。上述的例子中，能够到达A:=I+1这一对于I的引用的定值语句，不仅有B$_4$中的I:=2，还有B$_1$中的I:=1.

最后我们给出查找循环L中不变运算的算法：



以及代码外提算法：


强度削弱.
我们要介绍的第二种循环优化技术叫做强度削弱。强度削弱是将程序中执行时间较长的运算替换为执行时间较短的运算。例如，最常见的就是将循环中的乘法运算用递归的加法运算来代替。我们考察前面经过了代码外提的示例流图：



【下图引用自中南大学徐德智老师的编译原理2020年授课PPT】



不难看出{B$_2$,B$_5$}是一个循环，并且B$_2$是循环的入口结点。我们注意序号为13的语句，这里的变量I是一个递归赋值的变量，每循环一次，它增加一个常量1。另外，序号为4和8的语句在计算T$_2$和T$_6$时，都会使用I的值，并且T$_2$和T$_6$都是I的线性函数，每循环一次，它们都增加一个常量10.因此，如果把4和8外提到循环的前置结点中，并且在13号语句之后添加上为T$_2$和T$_6$增加常量10的语句，程序的运行结果依然不变。



【下图引用自中南大学徐德智老师的编译原理2020年授课PPT】



经过上述变换，循环中原来的乘法运算4和8被替换为了在前置结点中进行一次初始化的乘法运算(计算初值)以及在循环中递归赋值的加法运算(4’)和(8’).不仅加法运算一般来说比乘法运算快，而且这种在循环前计算初值，再于循环末尾进行常量递增的运算，可以利用变址器提高运算速度，从而使运算的强度得到削弱。所以我们称这种优化技术为强度削弱。

强度削弱不仅对于乘法可以实行，对于加法也可以实行。例如上图中序号为5和9的语句，T$_3$与T$_7$的计算中引用到了T$_2$和T$_6$，并且T$_2$和T$_6$也是递归赋值的变量，每循环一次，它们的值就增加一个常量10.而T$_3$与T$_7$的另一个运算对象都是循环不变量，所以每循环一次，T$_3$与T$_7$的值就增加一个常量10.很自然地，我们会想到对它们进行强度削弱，即外提一个初始化语句，在循环的末尾添加常量递增语句，得到的优化结果如下所示：



【下图引用自中南大学徐德智老师的编译原理2020年授课PPT】



从上面的例子中我们可以看到：

如果循环中有A的递归赋值A:=A±b$_1$，并且循环中另一个变量B的赋值运算可以写为B:=k*A±b$_2$的形式，那么对于B的赋值运算，我们可以进行强度削弱；
进行强度削弱之后，循环中可能会出现一些新的无用赋值，例如上图中的(4’)和(8’)，因为循环中不再使用T$_2$和T$_6$，那么如果循环出口之后它们也不是活跃变量，是完全可以删除的；
循环中下标变量的地址计算是相当耗费时间的，这里介绍的方法对削弱下标变量地址计算的强度是非常有效的。前面的例子中，数组是二维的，如果我们考察一个更高维度的数组，将会进一步看到强度削弱的作用。对于下标变量地址计算来说，强度削弱实际上就是实现下标变量地址的递归计算。

删除归纳变量.
我们要介绍的最后一种循环赋值技术叫做删除归纳变量。讲述具体的流程之前，首先给出基本归纳变量以及归纳变量的定义：

【定义】基本归纳变量：循环中对于变量A的赋值只有唯一的、形如A:=A±b$_1$的赋值，那么称A为循环中的基本归纳变量；

【定义】归纳变量：如果A是一个基本归纳变量，循环中对于B的赋值总是可以化归为A的同一个线性函数，即B:=k*A±b$_2$，那么我们称B是一个归纳变量。

考察进行了代码外提之后的示例程序流图：



【下图引用自中南大学徐德智老师的编译原理2020年授课PPT】



不难发现变量I是循环{B$_2$,B$_3$}的基本归纳变量，T$_2$和T$_6$是循环中与I同族的归纳变量，再继续发掘，T$_3$和T$_7$也是与I同族的归纳变量。

一个基本归纳变量除了用于自身的递归赋值以外，往往只在循环中用于计算其他的归纳变量和控制循环的进行。经过了强度削弱之后的示例程序流图如下所示：



【下图引用自中南大学徐德智老师的编译原理2020年授课PPT】



关注基本块B$_3$可以发现变量I除了用于自身的递归赋值以外，只用于控制循环的进行。这时，我们可以使用与I同族的某一个归纳变量来代替I控制循环的进行，从而删除变量I.例如，我们选取T$_3$(T$_7$与T$_3$都在循环中被引用，所以是一样的，而T$_2$和T$_6$在循环中没有被引用)来代替I，	由于T$_3$可以写为10*I+T1，并且循环的控制条件为I>10，所以用T$_3$代替了I之后，控制条件变为了T3>100+T1.为了不在每一次进行判断时都计算100+T$_1$的值，我们引入新的临时变量R:=100+T$_1$，所以序号为2的if语句改写为：
R:=100+T1
if T3>R goto (15)

然后我们就可以删去变量I了，这一优化技术称为删除归纳变量，也叫变换循环控制条件。如果我们假定T$_2$和T$_6$在循环出口之后也不是活跃的，那么我们完全可以删去这两个临时变量(因为它们在循环中也没有被使用)。但如果我们在选择代替I的变量时选择了T$_2$或T$_6$，那么(4’)或(8’)就不能删除了，最后完成删除归纳变量的中间代码如下：



【下图引用自中南大学徐德智老师的编译原理2020年授课PPT】



删除归纳变量是在强度削弱之后进行的。我们在下面统一给出强度削弱和删除归纳变量的算法：

一、生成中间代码的目的

便于优化

让生成的目标代码效率更高

优化不等同于对代码的精简和算法的优化

（对于高级程序设计语言中可能不能继续进行优化，但是仍然可以在编译中进行优化）

比方说多维下标变量地址计算过程，比方说a[i][j]和 a[i][k]，我们在计算他们的地址的时候都先要计算a[i]的地址然后再计算j k 的地址，实际上a[i]的计算过程实际上是重复计算了
便于移植

编译前端：与目标机无关

编译后端：与目标机相关

中间代码起到一个将一对一翻译转换成一对多对一的关系，通过编译前段可以不用改变，编译后端根据目标机相关需要变化，把编译前端的工作做的越多越好。比如java多平台开发，依赖java字节码


二、中间代码结构
2.1 三元式


计算顺序确定，逐条执行即可，不用考虑后序顺序问题
结果没有单独运算分量表示，使用指令的标号表示，在指令优化的时候比较麻烦，比如某些指令执行完之后vanish，标号消失就得重新命名

2.2 逆波兰式

2.3 抽象语法树

2.4 四元式（tag——本课程使用）


基本结构解释：第一个式操作符，后面两个是操作数按照第一个操作符来进行运算，结果保留在第四个element（中间变量）中
t1相当于之前所说的中间变量保存中间的运行结果，和三元式不同的地方就在于有中间变量表示每条的运行结果
算术、逻辑、关系运算符（可以在具体文法规则中插入下面的相关运算）

ADDI(整数加)、ADDF(浮点数加)、SUBI、SUBF、MULTI、MULTF、DIVI、DIVF、MOD
AND、OR、EQ、NE、GT、GE、LT、LE
READI,READF,FLOAT,ASSIG,AADD...


在运行文法的时候遇到时随时解释


三、语法制导方法
如何创建四元式？语法制导技术在处理和规则相关联的任务中有着重要的应用

语法制导就是在进行语法分析的同时要完成相应的语义动作（语法分析过程中插入自己所写的执行其他功能的函数），这些语义动作都是由一些程序组成的，要完成和用户的需求相关联的任务
编译器对一个串进行语法检查的同时，可以按照语法分析的程序的结构对程序进行我们所需要的操作，从而解决我们想要解决的问题



INIT 添加到S开始头部——sum=0；

则有:  S-> #Init# AB

A-> aA│ b #Add#

B-> b #Add# B│c #Out#

其中：

Init：m = 0;

Add : m++ ;

Out ：print(m);



起始符S首先进入符号栈，然后使用S的右侧代替S得到#init# AB，执行#init#使得m=0；执行完之后剩下AB#，不能与输入流中的字符消去；继续将A使用aA代替得到aAB，将输入流中的a和符号栈中的a匹配掉得到AB；没有匹配的，继续使用文法的右部进行替换，这次选择替换的指令是A->b# Add#，将b匹配上，然后剩下# Add# B,执Add，然后剩下B#，后面和前面的运行步骤相同，最后剩下#则证明成功实现。



匹配过程中仍然按照原来的规则选择语法压入符号栈，在进行匹配之前直接执行插入的相关操作，然后继续进行匹配

四、中间代码生成中的几个问题


四元式当前的表示形式是便于直接读写的方式，而实际上存储在x和y的不是x和y的符号，而是一个指向xy在符号表中位置的指针。

将语义信息（种类信息，类型信息，抽象地址）写在四元式中，但是如果全部写入会出现大量的冗余信息，所以最好的一种方式是指向对应存在语义信息的符号表中的指针，需要信息的时候直接通过指针在符号表中提取出所需信息。



五、表达式的中间代码生成
具体表达式的四元式生成的语义程序写法：


自底向上只能添加在末尾，在归约的时候才能执行添加操作。


Gen表示生成四元式的函数

将栈顶元素按照四元式进行计算之后将栈顶元素取出计算将结果压栈





首先画出其语法树，然后使用自底向上的方法看能否生成相应的四元式，过程如下：

前面提到了经过了词法分析->语法分析->语义分析->中间代码优化，最后的阶段便是在目标机器上运行的目标代码的生成了。目标代码生成阶段的任务是：将此前的中间代码转换成特定机器上的机器语言或汇编语言，这种转换程序便被称为代码生成器。

1. 程序移植性和编译器模块设计的关系 

之所以将编译原理分成这种多阶段多模块的组织形式，本质的考虑其实只有两个方面： 
一、代码复用：尽可能在不增加程序员工作量的前提下，增加应用程序的可移植性。 

（可我们知道不同机器的机器指令集和硬件结构，千差万别，而前面又提到了为了将程序的执行效率提升到最大，显然是需要将软件按照硬件特性极尽可能地定制化优化，其实现在AI芯片的发展趋势也是这种思想的另一面体现。现今AI芯片为了加速深度学习为代码的超强度计算效率，出现了针对具体程序架构定制化芯片的需求，如CPU->GPU的发展，便是GPU迎合了深度学习单轮多次简单运算的需求，CPU->FPGA的矩阵运算侧重也是Facebook引领的另一硬件绑定具体软件计算需求的工程案例，而最为极端者莫过于当下Google推出的TPU计算芯片，完全剔除不必要的硬件设备，根据Google的深度学习Tensorflow架构定制化的计算芯片，更是以极致的定制化获取比CPU计算速度高200倍的显著成果。）。


所以再一次验证了“银弹”理论，如果有问题解决不了，那就加一层抽象层了。所以提高代码移植性的集大成者Java，便是通过引入JVM将应用程序层和具体硬件层隔开。 


图1. Java-多目标机 

显然对于Java程序可以共享一套“词法分析+语法分析+语义分析+中间代码优化引擎”这一套前端套件，而针对不同机型的定制化目标代码生成器则可以通过官方渠道的支持和更新来组装成自己所需的后端套件组。这样便可以让程序员尽可能地有较多的自由编写的空间，极大地提升代码可移植性，而不像C++编写的DLL库，即便采用复杂的COM规则，极为小心地编写，但也可能因为编译器版本不同导致移植性不通过。


二、特定机器的优化器和生成器复用：针对特定机器的目标代码生成和优化器的工作极为复杂精深，有一套成功的，当然要尽可能复用它。

由于代码生成阶段的目标代码和具体计算机的结构有关，如指令格式、字长以及寄存器的个数和种类，并与指令的语义和所用操作系统等都密切相关，特别是高级语言的语义功能复杂，并且计算机硬件结构多样性都给代码生成的理论研究带来很大的复杂性，因此实际实现起来是非常困难的。所以难得生成一款后端的代码生成器，当然是想让它可以独立出来，被多次组装参与其他编译器的生产过程。 


图2. 多种语言-一种目标机型


这种情况被称为定计算机情况：当限定某种计算机时，而高级语言为多种情况下所设计的中间语言，应能充分反映限定计算机的特点称MSIL(Machine Specific Intermediate language)。对这种机器的所有编译程序在分析阶段都生成MSIL，在实现一个编译程序时，尽量把编译过程的大量工作放在代码生成阶段，即MSIL到目标程序的翻译上，以减轻不同语言翻译的分析任务。因不管多少种高级语言，MSIL到目标程序的代码生成只需做一次即可。

当然也正是这种组织特性，让本来是集团作战的编译器生成工作，现如今变得不再是难以企及。同时也让各行各业根据自身需求和侧重点不同，甚至可以定制化自己的行业的专属语言（Domain Specific Language)变得可实现。

 2. 代码生成的优化手段：寄存器分配 

说了这么多，其实只需要明白代码生成器是结合目标机器平台定制化的一套后端套件，这也是为何业界的主流计算机都是按照x86、x64_86这些业界标准来设计的，如果你家公司另辟蹊径自己设计出一套硬件体系，即便你能设计生产出来，但你确定IT界会有下游供应商给你设计类似于代码生成器这种配套套件吗？


衡量最终生成的目标代码的质量无非是从两个方面来进行评估：空间占用和运行效率，这其中涉及到诸多和具体硬件绑定的细节，大多数都属于难度高且并不通用的范畴。而寄存器的使用规则则是少数具有通用的手段，故而可以借分析寄存器分配来分析一下目标代码优化和生成过程。

Q: 为什么在代码生成时要考虑充分利用寄存器？ 

A: 因为当变量值存在寄存器时，引用的变量值可直接从寄存器中取，减少对内存的存取次数，这样便可提高运行速度。因此如何充分利用寄存器是提高目标代码运行效率的重要途径。

Q: 寄存器分配的原则是什么？ 

A: (1)逻辑有效范围内尽量保留： 当生成某变量的目标代码时，尽量让变量的值或计算结果保留在寄存器中，直到寄存器不够分配时为止。 

　(2) 逻辑块出口处，和内存中的源数据同步：当到基本块出口时，将变量的值存放在内存中，因为一个基本块可能有多个后继结点或多个前驱结点，同一个变量名在不同前驱结点的基本块内出口前存放的R可能不同，或没有定值，所以应在出口前把寄存器的内容放在内存中，这样从基本块外入口的变量值都在内存中 

　(3)  及时释放，提升寄存器使用效率：对于在一个基本块内后边不再被引用的变量所占用的寄存器应尽早释放，以提高寄存器的利用效率。 

可以看到在进行缓存淘汰更新时我们采用了LRU策略，LRU策略是属于经典的“线性思维”–即过去常被使用的，在未来也会常被使用。而这里寄存器则不能采用“线性思维”，因为我们看自己的代码都知道，变量的使用虽然在局部范围还算符合“局部性原理”，但是稍微放宽到一定尺度上的变量集使用情况，则发现更多是无序的。所以在进行寄存器分配策略的研究上，只能比较粗暴点，事先将目标代码再次遍历一遍，将变量的使用情况事先整理好，并用所谓“待用信息链”的数据结构来保存每个变量的使用情况。这种策略并非LRU那种后视推导逻辑，而是耍赖的先知般论断逻辑，但是考虑到一旦将目标代码的寄存器使用效率最大化，则无疑是一劳永逸的，故而也是划算的。

 变量的待用信息链计算方法 

前面根据寄存器的使用原则可以看到，寄存器的分配是以基本块为单位的，因为基本块作为程序流的最小单元，存在着数据同步和异步的问题，故而在进行寄存器分配时，要审核的代码范围只需要涉及到当前基本块即可。

首先为任一变量设置两个信息链：待用信息链和活跃变量信息链。

考虑到处理的方便，可假定对基本块中的变量在出口处都是活跃的，而对基本块内的临时变量可分为两种情况处理。 

　　a) 一般情况下基本块内的临时变量在出口处都认为是不活跃的。 

　　b) 如果中间代码生成时的算法允许某些临时变量在基本块外可以被引用时，则这些临时变量也是活跃的。 

　　 

在基本块内计算变量的使用信息链（觉得采用栈式更符合这种信息链的更新情况），步骤如下：

① 对各基本块的符号表中的”待用信息”栏和”活跃信息”栏置初值，即把”待用信息”栏置”非待用”，对”活跃信息”栏按在基本块出口处是否为活跃而置成”活跃”或”非活跃”。现假定变量都是活跃的，临时变量都是非活跃的。　　 

② 倒着来从基本块出口到基本块入口由后向前依次处理每个四元式。对每个四元式i：A:=B op C，依次执行下述步骤： 

　　a) 把符号表中变量A的待用信息和活跃信息附加到四元式i上。 

　　b) 把符号表中变量A的待用信息栏和活跃信息栏分别置为 “非待用” 和 “非 活跃”。由于在i中对A的定值只能在i以后的四元式才能引用，因而对i以前的四元式来说A是不活跃也不可能是待用的。 

　　c) 把符号表中B和C的待用信息和活跃信息附加到四元式i上。 

　　d) 把符号表中B和C的待用信息栏置为”i”，活跃信息栏置为”活跃”。

说的麻烦，举个例子就好了：



　　(1) T∶=A-B
　　(2) U∶=A-C
　　(3) V∶=T+U
　　(4) D∶=V+U

加上信息链条之后，则标记情况如下



　　(1) T【(3)L】:= A【(2)L】 - B【FL】
　　(2) U【(3)L】:= A【FL】 - C【FL】
　　(3) V【(4)L】:= T【FF】 + U【(4)L】
　　(4) D【FL】:= V【FF】 + U【FF】

这样根据信息链表法，在每次运算到一个表达式时，如果寄存器数目不够，即无空余寄存器可用，则可以遍历一下当前在寄存器中的变量的待用信息链，然后选择接下来最远将被调用的变量释放其所占用寄存器，分配寄存器的算法为：

　　① 如果B的现行值在某寄存器Ri中，且该寄存器只包含B的值，或者B与A是同一标识符，或B在该四元式后不会再被引用，则可选取Ri作为所需的寄存器R，并转(4); 

　　② 如果有尚未分配的寄存器，则从中选用一个Ri为所需的寄存器R，并转(4); 

　　③ 从已分配的寄存器中选取一个Ri作为所需寄存器R，其选择原则为：占用该寄存器的变量值同时在主存中，或在基本块中引用的位置最远，这样对寄存器Ri所含的变量和变量在主存中的情况必须先做如下调整：即对RVALUE[Ri]中的每一变量M，如果M不是A且AVALUE[M]不包含M，则需完成以下处理; 

　　a) 生成目标代码ST Ri,M即把不是A的变量值由Ri中送入内存中; 

　　b) 如果M不是B，则令AVALUE[M]={M}，否则，令AVALUE[M]={M, Ri}; 

　　c) 删除RVALUE[Ri]中的M; 

　　④ 给出R，返回。

至此可以看到，单纯是寄存器分配便是需要较多数据结构配合和工作时间消耗的，管中窥豹，可以看到代码生成器的一个部件工作量便是很复杂的。