第六章优化与中间代码生成

type

status

date

slug

summary

中间代码生成

翻译生成中间代码的过程就是遍历抽象语法树的过程

临时变量实际上就是一个寄存器。这样就能理解为什么三地址代码最多只能有两个操作数了，两个操作数是因为cpu中的运算单元只能有两个输入，而赋值操作实际上就是一个mov操作。说白了就是三地址代码对应着计算机的三地址指令（如果能复用寄存器的话就是二地址指令了，将结果存回寄存器），所以这个时候是能进行下图这样的操作的：

本质上就是cpu接收两个寄存器的值做加法再存入另一个寄存器

下面是一些中间代码生成的时候的一点问题：

一个翻译成三地址代码的例子：

源代码：

三地址代码：

注意写三地址代码的时候如果是将单个变量的值赋给单个变量，那么就直接去赋值，不需要中间变量了。如果右侧是一个表达式，就想想计算机会怎么做（比如一个加法表达式，计算机一定是分步进行的，就是先进行加法运算，然后再进行赋值）。注意布尔表达式也是一种表达式，所以也需要使用中间变量进行暂存。

生成循环的三地址代码的时候要注意循环开始的标号的位置，因为循环条件中的变量也可能在循环中进行改变，所以循环的条件需要重新计算，也就是循环的标号应该在计算布尔表达式那一段，也就是右边这一段三地址代码中的L0标号。

翻译中间代码的要点：

而对于具体的赋值语句，就需要检查下面这些信息：

而对于赋值语句的右操作数，需要检查下面的信息：

这些要点实际上都是通过查找符号表解决的（有的是在第一次遍历抽象语法树的时候进行的，或者可以把两次对语法树的遍历都看成是生成中间代码，或者说语义分析的过程）

三地址代码中临时变量的作用：

这里说的就是每次运算的值，比如加法表达式的加法运算，布尔表达式的逻辑运算等（详见上面的三地址代码示例），但是要注意在复合表达式中赋值也算是一种运算，只不过没有结果所以不需要临时变量暂存，但是简单的赋值，也就是单个变量赋值给单个变量不是一种运算，此时就不需要临时变量

上面都是对一个赋值语句的翻译，如果是复合的赋值语句（就是右操作数有多个运算），此时每一个运算都是一个临时变量，所以：

也就是运算结果沿着语法树向上返回的时候返回的是当前节点代表的临时变量（实验四也是这样的，每次都向传入的char*参数中刷当前节点代表的临时变量）

这个表达式的翻译就是实验四里的思想了（也是目前正在写的那个函数）

对于这些情况需要分类去考虑：

所以在实验四中去返回节点的类型是很重要的（所以需要用到函数的返回值字段）

实验四的核心思想如上

这里说的操作数结果中的第一条代表的是——当有一个表达式的一个操作数就是一个变量的时候，就直接引用这个变量，如果是常量的话也直接引用这个常量。但是如果一个表达式的一个操作数还是一个表达式的话，那么这个操作数就是用临时变量来代替。

这里的赋值指令就是最后的一条（形如a=t1，就是将临时变量t1的值赋给变量a）

所以赋值语句的中间代码翻译就是下面的步骤（对于单变量赋值就直接使用赋值指令即可）：

对控制语句的翻译主要就是如下两个

循环（while和for）

分支（if 和if else）

对分支语句的翻译

ifz是条件不满足

if语句的抽象语法树如下

处理if语句的中间代码的时候会有如下的问题：

这里说的才知道是指知道跳转的行数。因为处理的时候行数未知，所以需要使用一些标号

翻译if语句的具体实例如下：

这里的yyy和xxx就是上一张图片中所说的标号

生成的分支语句的三地址代码结构应该如下：

尽量写if的时候就按照上面的代码结构来写，也就是如下图：

对循环语句的翻译

循环语句的三地址代码结构如下：

下面是一个循环语句的例题：

不要写标号，最好还是写行号

函数调用翻译

这里的又写标号了难绷，而且if的判断后面也不是两个goto了，还是按照自己的习惯来吧（除非题目中给出了行号，不然就用标号。除非题中的分支给出了两个goto，不然就只写一个goto）

而函数的实现实际上就是一个栈

小知识（实际上是计组的知识）：

注意这里的向上向下增长是指栈是向高地址方向生长还是向低地址方向生长的

下面是栈的四种形式：

满还是空就是看栈顶指针所指向的单元有没有有效元素。递增递减就是看栈的生长方向

模型机内的栈就是向下生长并且是满堆栈，也就是满递减栈

这个实际上就是批量读和批量写，这个时候对应的寄存器就会自增（读的时候是自增）或者自减（写的时候是自减）

回到函数调用的翻译上来，函数调用的时候需要进行压栈操作，也就是为函数执行开辟一个空间。注意栈帧里面先存的是参数（这个也就是将函数的参数压栈，这个时候函数内部使用的就是变量的副本了，对于函数外部使用的临时变量也是这样的，所以这个操作就是在保护现场），然后才是一些函数内部使用的临时变量（这里的临时变量并不是代表存储在寄存器中的临时变量，而是寄存器不够用了将寄存器中的变量压入到堆栈中了）和局部变量。具体的例子如下：

这里选择在跳转到函数之前进行现场的保护，实际上是可以在函数内部进行现场保护的（想想综设的汇编代码，也想想计组的中断是在哪里进行现场保护的），考试的时候如果出现了函数调用的三地址代码，那么就选择在函数外部进行现场保护

这里的一些记号是要记住的比如BeginFunc（函数开始，对应栈帧内部的临时变量和局部变量的开辟）、EndFunc（函数结束，对应着栈帧内临时变量和局部变量的销毁）、PushParam（参数压栈，这这个参数压栈可以理解为两种操作，一种操作是为函数处理空出寄存器，另一种就是参数传递的时候只传递副本。这个操作实际上就是保护现场，对应着栈帧内的参数压栈）、PopParams（参数出栈，恢复现场，对应着栈帧内的参数出栈）、LCall（函数调用）

函数名后面的数字还有pop后面的数字都代表的是栈帧的大小

下面是一个关于栈帧的例题：

这里问到的栈帧的大小就使用字节数来描述就好了，内容就是函数的参数，上层函数的栈帧指针，返回地址。

栈帧指针的位置如下，指向的是当前正在执行的函数的中间:

当前栈帧指针指向的栈帧位置如下（指向当前函数的参数和返回函数的栈帧指针之间。这里的返回函数就是调用当前函数的函数）：

函数调用本质上是一个转子指令，所以还需要存储返回地址（也就是存储上层函数的栈帧），如下图（至于为什么返回栈帧在参数之后，局部变量之前，是因为参数对应的操作是push和pop，在当前模式下这些指令都在上层函数内部，所以这些变量的push和pop就交给上层函数处理。如果换一种模式将push和pop放在子函数中处理的话，就需要将参数全部pop出来之后再返回，所以这个时候返回栈帧就应该放在当前函数的栈帧的栈底了。这个操作就相当于是恢复现场，但是此时指令还没有回到之前的位置）：

上面一张图片代表的是栈帧返回，也就是将程序中的数据返回，但实际上还需要将程序的指令返回，也就是下图的ra（存储指令返回地址）：

生成mips指令

这里就是计组的知识了：

mips指令应该不做要求，但是这里的这些指令还是看一看。lw（读命令，就是ldr）、add（加法）、sw（写命令，就是sdr）、addiu（不考虑溢出加法）、li（转移指令，相当于mov）

栈计算机实际上就是当时icoding上做的那个后缀表达式（只有两个寄存器能用，一个是中间变量寄存器，一个就是变量寄存器。想要存储数据的时候只能使用堆栈）

代码逐行解释如下：

将a0的值存入堆栈（堆栈是空堆栈）

将sp自减一个单位（因为栈是向下生长的）

从堆栈中取出e1存在临时变量t1中

将临时变量和a0（存储的是e2）做加法并存储在a0中

恢复堆栈（也就是将sp自增一个单位）

这里面的cgen函数就是将当前的输入存到a0中，也就是li a0，e1

一个更复杂的例子，这样就能看出来树状结构了（这里的1是一个节点，然后5+ 6是一个节点，节点内部再进行递归）

这里是一个分支语句的mips代码，当函数参数为条件分支的时候就不是单纯的将值移动到a0中了，而是先处理条件（这个时候条件的每个变量也是需要用栈进行操作的），然后进行跳转

下面是一个mips函数调用的代码：

这里是mips代码，在三地址代码中的函数调用就是直接push、call然后pop

这里的fp就是栈帧地址。注意这里是先将栈帧地址存入堆栈（前面看的三地址代码就没有存储栈帧这个操作，而是直接进行参数压栈然后跳转了。并且这里是先将栈帧压入然后再压入参数，这个时候的栈就跟之前三地址代码是不一样的了。三地址代码中的栈是先将参数压栈，然后再压入当前函数栈帧，然后再进行跳转。如果是当前mips这种代码生成方式的话，返回指令的地址就需要加上一些偏移量跳过下面的push操作）。这里和三地址代码一样的操作就是——参数都是逆序压栈的，也就是生成的栈帧是最后一个参数在最底下的。此时栈帧的大小应该是4n+4（4n是参数部分，4是返回栈帧部分）

小知识:三地址代码中的临时变量可以存储布尔表达式的结果（除了大于小于等逻辑判断，还可以存储判等的逻辑结果，如下面的临时变量t3），如下图：

还有就是，三地址代码之后需要加上分号

这一题就先不进行三地址代码的翻译，而是先将流程控制全部表示出来之后（就是将所有的goto都写出来，或者说将所有的流程控制都表示出来）再将表达式改变成三地址代码

代码优化及目标代码生成

经过上面的语义分析之后就能生成中间代码（语义分析的核心任务是类型检查还有中间代码生成）了

所以接下来的步骤应该是对语义分析生成的中间代码进行优化，优化之后再生成目标代码，也就是机器代码

优化本质上就是在保证程序等价的情况下去降低程序的时空复杂度（也就是删除一些无用的代码）

在编译阶段，代码优化需要解决下面的几个问题：

两种中间代码优化

局部优化：在基本块内进行优化

全局优化：在基本块之间进行优化

基本块定义

如下（就是入口出口确定的一段语句序列，入口需要是这一段语句的第一条语句，而出口语句需要是这一段程序的最后一条语句。序列的意思就是连续的意思）：

如何寻找一个基本快

第一步：寻找入口语句和出口语句

入口语句（下列这些语句都是入口语句）：

第二条规则就是goto跳转到的语句是一个入口语句

第三条规则就是goto语句的下一条指令（紧跟着的，不是跳转后的语句）是入口指令

出口语句（下列这些语句都是出口语句）：

这里的停止语句就是程序的最后一条语句，转向语句就是goto语句

第二步：根据找到的入口语句和出口语句进行基本块的划分，如下（也就是从入口语句到下一个入口语句的前一条语句之间是一个基本块，从入口语句到出口语句是一个基本块）：

第三步：删除没有在基本块内的语句，因为这些语句是没办法到达的

基本块划分的例题如下：

小技巧：寻找入口和出口先将程序的第一条语句和最后一条语句写了，然后再处理跳转语句。每一个goto语句都有三个点要处理：

当前的跳转语句是出口语句

目的地是入口语句

下一条语句是入口语句

注意这上面的基本块4只有一条语句（因为他既是入口语句，也是出口语句）

程序流图

画程序流图之前需要先进行基本块的划分

程序流图的定义如下（其中的n0就相当于是程序的开始节点）：

如何绘制程序流图

节点就是每一个基本块，现在主要就是处理有向边

有向边的绘制如下：

一种就是基本块直接穿了，另一种就是跳转

注意if语句的goto可能是跳转（就是第二种情况）也有可能直接穿了（就是第一种情况）

两种优化方式

局部优化

常量传播

常量传播示例如下：

也就是编译的时候将一些已知值进行替换（想想c语言的宏定义替换）

删除公共子表达式

删除公共子表达式示例如下：

这里面的C*D就是一个公共子表达式（可以通过有向无环图解决，也可以通过可用表达式来解决。如果使用可用表达式法就是在后面的程序中将可用表达式替换成对应的变量）

删除无用赋值

删除无用赋值示例如下：

可以通过活跃变量来解决（第一个语句之后遍历那个a不是活跃的，所以这个赋值表达式是无用赋值）

删除死代码

死代码最常见的就是条件分支某个语句没办法走到。注意这个死代码是没办法通过基本块划分实现的，因为这里是局部优化，是在基本块内的优化

复写传播

基本思想如下：

注意这里可以发现复写传播只处理变量复制的情况，也就是如果有a=b，就将下面的a换成b（注意这个才叫做复制，而如果是出现a=1+b，下面就不将a替换为b了，因为这个不是复制的操作），可以通过可用表达式解决。如果对上面的例子而言，这个时候可用表达式是就是单个变量b，然后在进行复写传播的时候就是将后续语句中的变量a替换为表达式b

示例如下：

需要考虑以下的问题：

以上面的例子为例，第一个问题就是需要找到x（变量y的副本）在哪里使用了；第二条规则就是说复写传播可以向内部作用域传播，但是没办法跨作用域（如一个函数内部定义了一个x=y，就不能说把另一个函数中的x替换）

窥孔优化：

就是只关注一个滑动窗口（也就是窥孔），然后在这个窥孔内进行代码优化

但是窥孔优化就像这里所说的，是针对已经生成的汇编代码（目标代码，也就是机器代码）的优化，所以这个应该算是目标代码优化的内容。而且这里说的是结合CPU自己指令的特点，所以应该是目标代码优化中的机器有关优化（或者机器相关优化）。但是实际上这个方法也可以用在中间代码上（龙书上说的），所以这里也认为他是一个中间代码优化的方式

下面举一个窥孔优化的例子（目标代码是不考的，这里了解一下）：

这里就相当于是将栈顶的64位清空然后把这些值都存到f1中，这个时候就可以将这个操作改为给fl赋零

再举一个例子：

上面两条mov指令中就有一条是无效的，这个时候就可以进行机器有关优化

局部优化方法总结

通常局部优化的步骤如下：

删除死代码（先进行比较大的代码优化。删除死代码一次可以删除很多行）

常量传播（注意常量传播之后最开始的常量赋值语句不一定没有用，可能在下一个基本块中用到了，所以常量传播之后最开始的常量赋值语句需要保留，因为常量传播是没办法传到之后的基本块中的，所以此时他就变成了可能的无用赋值语句）

复写传播（复写传播之后的表达式也不将其删去，因为如果出现了a=b的情况然后将下面的a替换为b了，但是有可能在之后的基本块中会用到，复写传播是没办法传到后面的基本块中的，所以最开始的复制语句就变成了可能的无用赋值语句）

删除无用赋值

注意有些赋值语句可能在当前代码块中没有出现无用赋值，但是如果将几个代码块合在一起看就有可能出现无用赋值，也就是下图（注意常量赋值语句进行常量传播之后还需要保留）：

注意这里面的所谓的无用赋值都是上面常量传播和复写传播生成的可能无用赋值，而不是说在当前基本块中看不出来就是一个无用赋值（将删除无用赋值放在常量传播和复写传播之后也是因为常量传播和复写传播有可能会生成新的无用赋值）。当然这里到底认不认为这些可能的无用赋值就是无用赋值还是要看题目的提示，如果说了认为是无用赋值就直接去掉就好了，如果没说的话就像上面写的那样，说这些是可能的无用赋值

删除公共子表达式

这个题的删除公共子表达式比较明显，就是下面两行可以使用常量传播

此时由于右操作数就是公共子表达式，所以这个时候直接将T2当成中间变量，这个时候下面就变成了T4=T2，这个时候又可以进行复写传播了

所以按照上面的流程走了一遍之后还需要再检查几遍（也可以理解为多走几遍上面的流程，直到当前的基本块不再变化，就相当于做闭包运算了）

还有一些局部代码优化是根据一些特性进行的，比如说乘2就替换成左移一位（因为移位运算比乘法运算快）

可用表达式

实际上就是某一个时刻（两行代码之间的时候），有哪些表达式是可以使用的。表现形式为一个集合，这个集合里面的元素表示为一个变量（等号左侧）和这个变量持有（也就是代表）的表达式（在右侧）

例题如下：

这里下图的这两行中d的表达式变化了，这是因为当前d持有的表达式从a+b变成了b，所以可用表达式集也需要进行相应的更新（所以可以看出可用表达式集中的变量是不能重复的，但是表达式是可以重复的）

如果想使用公共表达式法来进行删除公共子表达式的话，那就要对每一行语句进行公共子表达式的查询，能替换就替换（就算有复写传播的逆过程也进行替换），这样替换一遍之后就能通过活跃变量来删除无用赋值了

使用活跃变量进行删除无用赋值的时候删除一遍了之后还要继续删除（类似做一个闭包运算）直到当前的语句不再减少

活跃变量的定义如下：

说白了就是当前变量的下一次使用是读取操作，也就是说当前变量在某个点里面的值是有用的

对删除了无用赋值的基本块可能还需要使用复写传播，如上图

另一种实现删除公共子表达式的方法——有向无环图

如下图，根据生成的一个语法树构建一个有向无环图（也可以直接根据语句构建），这个有向无环图要求叶子节点对应原子运算分量（如单个变量），内部节点对应运算符

如何根据有向无环图来判断哪些表达式是公共表达式？

如果一个节点N有多个父节点，就说明他被多次引用，也就说明他是公共子表达式

全局优化

这里只讨论循环优化

循环的定义：

注意这里说的是程序流图中，所以在求循环的时候需要先求强连通子图（也就是上面基本块划分那一套）

如何找到循环？

根据定义求解几乎不可能（很容易错）

首先引入一些概念

必经节点

定义如下：

就是如果要到n一定要经过d

必经节点集：某个节点n的必经节点的集合称为n的必经节点集，记为D（n）

所以根据循环的定义，如果要到循环内部的节点（体现在程序上就是进入循环内部），就一定要经过循环的入口，所以循环的入口一定在所有循环内部节点的必经节点集中

必经节点的一些性质（可以用于求节点的必经节点集）：

计算必经节点集的例题如下：

注意第一遍的时候把10的必经节点集求错了，总结出一个方法：

总体而言从上向下求解

如果遇到从上到下的跳转边（就是比较长的边）就要注意，跳转边内部包含的节点都不在跳转边终点的必经节点集中了，如上图的4->10

回边

定义如下：

就是从自身到自己的必经节点集中的边（就相当于循环重新开始了，既然是循环开始，那么当前的状态就一定是循环的出口，循环重新开始的时候一定是从循环入口开始的，所以这个时候就能确定一个循环了，也就是n是循环的出口，d是循环的入口，这个时候只需要从结循环结束节点开始向开始节点回溯直到回到循环的开始节点，就能确定循环内部所有的节点了，这个回溯确定循环内部节点使用广搜的思想就不容易错了）

也就是下图：

这里说的到达n但是不到达d就是从n开始向上回溯直到循环开始节点结束（注意循环的开始节点和结束节点都是循环的节点）

下面是一个简单的回边的例子：

找到循环之后就是进行全局优化——循环代码优化

循环优化方法

有如下几种：

代码外提：

也就是循环内部有一些表达式在循环过程中是不变的，就将其从循环中提出（提到循环的入口节点之前）

强度削弱：

归纳变量就是循环中在变化的量

基本归纳变量就是在循环中主动变化的量

当一个归纳变量是由另一个归纳变量经过常数线性运算得出的，那么他们就是同族的。可以发现同族归纳变量是同时变化的（也就是上面的i变化就会引起j变化，并且引起变化的量是固定的，如上面的i变化一次就会引起j增加c*c1）

这个时候就能进行强度的削弱（就是将乘法削弱为加法，如上例中将计算j的乘法修改为加法）

删除基本归纳变量：

这里可以发现，删除基本归纳变量是要在强度削弱之后的。

这里说的无用实际上就是i的作用已经被j替代了（这个时候就将所有带有i的代码换成j相关的计算式）

下面是一个示例：

这个j就是经过强度削弱的归纳变量，这个时候i的作用就可以被j替代了（说白了就是基本归纳变量是为了控制循环存在的，这个时候可以根据同族归纳变量来代替基本归纳变量的控制循环的作用，所以这个时候基本归纳变量就删除了，但是同族的归纳变量不能删除，因为他们可能还有其他的用处）

所以循环优化的顺序如下：

代码外提：进行代码外提的时候就看基本归纳变量是什么（就是在循环中值自己变化的变量），然后找哪一些表达式的右侧出现了归纳变量，那么这个变量就变成了基本归纳变量的同族归纳变量，然后根据新找到的同族归纳变量继续向下寻找同族归纳变量直到归纳变量不再增多，剩下的语句就是不变量，可以进行代码外提

强度削弱：

如下图：

强度削弱的时候需要注意变量的初始化，如循环内部第一条语句t2=t2+10，但是在这之前t2可能还没有初始化，所以需要在循环外部进行初始化（初始化值的计算：根据第一次循环的值来计算就好了，以这里的t2为例，第一次循环的时候执行循环内第一条语句之后t2的值应该是10，所以t2的初始化值就应该是右侧t2的值，也就是10=t2的初始化值+10，所以t2的初始化值应该是0，但是最好在初始化的时候保留原始形式，便于之后进行基本归纳变量的删除）

删除基本归纳变量

注意局部优化方法也可以用于全局优化，只不过在局部优化中只是考虑语句之间的传播，但是如果用在全局优化之中的时候就是将所有的程序流图中的节点当成局部优化过程中的语句来进行基本块之间的常量传播（但是这个时候就要考虑基本块之间是否有作用域等限制，甚至如果到要替换的节点的时候前面有多个节点，就需要检查每一条到达当前节点的路径上是否有改变需要传播的常量的值，也就是需要在每一条路径上检查X的最后一次赋值是在什么时候。检查所有路径可以以循环为例，因为循环的基本归纳变量在外面初始化了，但是并不能通过常量传播传到循环的判断条件上，因为循环的判断条件节点还有其他的入边，就是循环结束的节点）

在全局优化中也可以使用活跃变量法来实现删除无用赋值，具体在基本块之间（或者说对一段程序）如何求活跃变量就看寄存器分配的ppt了，这里给出一个简略的计算：

就是如果当前变量在某一个状态的出边上是活跃的，并且这个基本块内最上面一条对这个变量的引用不是写操作，那么这个变量在当前状态的入边上也是活跃的（就是上面说的第二条规则）。然后就是变量在一条边上要么都是活跃的，要么都是不活跃的（也就是上面说的第一条规则）

目标代码生成

目标代码就是最终的机器代码

目标代码生成时需要考虑的主要问题

如何选择合适的指令生成最短的目标代码

如何合理使用机器的寄存器（可以提高代码的执行效率，是目标代码生成的时候一个很重要的东西——寄存器分配）

首先需要对一些指令还有寻址方式有了解（想想计组）

立即寻址（给立即数）

直接寻址（给地址）

寄存器寻址（数在寄存器中）

寄存器间址（寄存器中存储地址）

主存直接寻址（给出数据的主存地址）

主存间接寻址（给出数据的主存间接地址）

寄存器分配的三种情况（所以寄存器分配应该是目标代码生成的内容）

还有空余寄存器，就是用寄存器（将变量的值存储在寄存器中）

寄存器不空闲，但是当前寄存器内存储的值已经无用了，此时就将变量的值存储在寄存器中

寄存器不空闲，并且当前寄存器内所有的值都是有用的，此时就需要将一个寄存器内的值存储到内存中，然后再进行寄存器的分配

上面是一个寄存器分配的例子，上面红色的那一行就是把变量u溢出到内存内了（这个时候这个变量就放在当前函数的栈帧中了）

循环中的寄存器分配

首先需要先有一个概念——每一个基本块之后所有的活跃变量都会被存储到内存中以便下一个基本块进行引用

在循环中有一些变量是频繁使用的，如果将其存在内存内就会出现频繁的读写操作，所以选择将其存储在寄存器中（c语言的register类型变量）

也就是下图所说的固定寄存器分配

小知识：变量是存储在内存中的，但是运算的时候需要放到寄存器中，也就是下图中标红的部分（将变量从内存中取出就是引用过程，也就下面的使用y和z，但是这里周尔强实在是nt，赋值操作应该是这一整个操作叫对x的一个赋值操作，而且赋值操作并不一定就是将ri的值存储到内存中）：

寄存器分配的主要目的就是将访存次数最小化

如何计算访存次数（计组）

注意这里的引用变量是计算基本块内的引用次数，而赋值变量是在计算基本块间的引用次数

对引用变量（也就是当前变量是在内存中的）的访存次数计算，每引用一次就需要做一次访存（注意引用变量是关注一个基本块内的）

计算引用变量的访存次数有一些注意点，如下：

引用变量是应该在内存中的，但是如果在当前基本块内已经计算出了x的值（就是对x的值进行赋值操作了）那么当前很有可能有寄存器记录了x的值（因为寄存器需要存储计算x的中间值），这个时候就不需要通过访存来访问变量x了，就可以直接使用寄存器中的值。也就是说如果给x赋过值，那么他就是一个寄存器变量了。所以计算某个引用变量的访存次数的时候，应该在对该变量赋值之前寻找

引用次数就等于访存次数

变量赋值的访存次数计算

变量如果在一个基本块内赋值然后在另一个基本块内使用，就相当于进行了一次写内存操作（基本块退出的时候需要写入内存）和一次读内存操作（在其他的基本块中使用）。也就是访存次数=2*赋值引用组合次数

上面这个live实际上就是赋值引用组合次数。这里说道对x赋值了（就是上面说的x是在基本块B中的变量，此时x在基本块B退出的时候被存入内存），然后如果被引用（需要重新从内存中加载，也就是在基本块B的出口处是活跃的），这个时候live=1，否则就是没有进行赋值，所以live是0。所以这里如果将x固定放在寄存器中，节省的次数就应该是上图的最后一个式子

总结——如果在循环中固定将寄存器分配某一个变量x，那么节省的访存次数如下：

所以如果要进行循环的寄存器分配的话，就是要根据程序流图（因为计算引用变量还有赋值变量都是基于基本块的，画程序流图要进行基本块的划分）来计算循环内每一个变量的上面的这表达式的值，然后选取最大的给他分配寄存器（也就是去最大程度减少访存次数）

注意这个公式计算出来的只是一个估计值

小知识:mov指令是将后面的数（源操作数）移动到前面的地址上（目的操作数）

下面是一个例题：

当寄存器不够用的时候就将值存储到内存里面（如计算出t2 t3的时候寄存器需要存储e和f的值了，所以需要将t2和t3存到内存里面）。这里还需要知道一些汇编指令（考试如果考到就直接用arm汇编吧，就是LDR、SDR、MOV、ADD、SUB、MUL、DIV等指令即可）

寄存器分配及SSA

寄存器分配实际上已经到了目标代码生成的步骤了

活跃变量

根据自己的理解，如果一个变量是活跃的，就说明当前变量里面的值是有用的（所以需要给活跃变量分配寄存器）

所以活跃变量可以处理无用赋值（如果一次赋值之后被赋值变量还不是活跃的，也就是这次赋值并没有给这个变量一个有用的值，就是一次无用赋值，这个时候删除的是语句，并且是在基本块内的。而且并不是所有的变量的不活跃都是无用赋值造成的，比如说对变量a的一次操作到下一次写入操作之前，变量a都不是活跃的，但是这个时候就不是无用赋值造成的，只不过说当前变量a内的值已经用完了，而寄存器分配就是处理这种情况的）

活跃变量还可以用来做寄存器分配（就是说如果一个变量是不活跃的，就说明当前变量在当前基本块内是没有用的，所以没必要给分配一个寄存器，这个时候就不是做语句删除的操作了，做寄存器分配的情况详见上面一段最后括号内的内容，而是进行寄存器分配，并且不是基本块内的操作）

活跃变量的求解

基本块内的活跃变量求解

也就是删除无用赋值的时候的规则（在基本块内的活跃变量求解）

简单描述如下:

如果在l行引用了变量x，那么变量x在l行（就是l行和l-1行之间）是活跃的

如果在l行对变量x进行了赋值，那么变量x在l行就是不活跃的（因为在第l行时给x写一个新的值，所以这个时候x的值是没有用的）

如果变量u在第l+1行是活跃的，并且在l行的语句中没有对其进行赋值操作，那么u在l行也是活跃的（也就是活跃变量可以向上传递，并且能发现活跃变量的求解顺序应该是从下向上求解）

与之间基本块中求解活跃变量不同的地方：return语句之后的所有变量都不活跃

基本块间的活跃变量计算

对于无条件跳转指令，就需要看跳转的目的地，并且如果在该行某个变量是活跃的，那么在跳转指令处也是活跃的（也就是程序流图中如果一个变量在一条边的箭头处活跃，那么他就在箭尾处活跃，对应程序流图中只有一个后继的情况）

而对于if语句，就需要看他的下一条指令还有对应的跳转指令的目的地。如果某个变量在这两个位置其中一个活跃，那么变量就在当前的if语句处活跃（也就是程序流图中如果一个变量在一条边的箭头处活跃，那么他就在箭尾处活跃，对应程序流图中某个节点有多个后继的情况，这个时候箭尾的活跃变量应该是所有箭头处活跃变量的交集）

所以基本块间的活跃变量求解是可以通过程序流图来快速求解的（也可以是求解完基本块间的活跃变量之后使用程序流图来进行检查）

所以得出一个结论：活跃变量是向上传递的，所以要求一条语句的活跃变量就需要去找到他可能的下一条语句。这个不论是对基本块内活跃变量的求解还是对基本块间的活跃变量的求解都是一样的

将上面的两种情况的活跃变量的求解总结乘如下规则：

如果在l行使用到了变量x，那么变量x在l行活跃

如果在k行变量u是活跃的，并且l行的下一条语句可能是第k行的语句，并且在第l行没有给变量u赋值（定义）的话，那么变量u在第l行也是活跃的（也就是活跃变量在基本块内和基本块间的向上传播）

将上述的总结抽象到程序流图中如下（也就是向上传播）：

上面的第一个规则就是基本块内活跃变量的传播（活跃变量集中加上右操作数中的变量，右操作数也就是这里说的使用过的变量）

第二条规则就是活跃变量的向上传递（对应基本块间的活跃变量求解）

第三条规则对应基本块内的活跃变量的删除（活跃变量集中删去左操作数中的变量）

注意求基本块中的活跃变量的时候需要先减去左边的变量然后再加上右边的变量

上面所有的规则总结起来就是：活跃变量的求解是自下而上的

具体实现的伪代码如下：

周尔强真是nt（一定要简化之后显得自己很牛吗），最后一行说本次循环产生的入边活跃变量集跟上一次循环产生的入边活跃变量集相同（就是入边的活跃变量集不再变化），还有就是当前循环产生的出边的活跃变量集跟上一次循环产生的出边活跃变量集相同（也就是入边的活跃变量集不再变化）

下面是一个使用这个算法的例题：

这实际上就是上面说的活跃变量的求解（但是要多次求解然后将基本块间的活跃变量也处理进来，也就是说重新进行算法的时候要注意程序流图中的节点的入边是否更新，更新了的话就会影响他的父节点，就会重新向上传播一次活跃变量。）

总结：如果要求一段程序（多个基本块）的活跃变量的话，最好使用上面的这种算法（当然题目要求直接求就直接求），然后求完一遍之后需要继续进行这个算法直到表不再变化，然后画出程序流图来进行检查

如果要直接求的话也是一样的（讲道理没什么区别，都是需要找到当前语句的下一条语句可能是什么，然后将活跃变量向上传播），也是要多次从程序的最后一遍遍向上查询，直到当前每一行语句的活跃变量集不再变化，然后最后画出基本块来进行检查

寄存器分配

在计算机中寄存器是稀缺资源，所以只将有用的变量值存储在寄存器中（也就是将当前活跃的变量存储在寄存器中）

无分配算法

此时将所有的变量都存储在内存中，而寄存器就起到存储中间变量的作用，需要一个变量的时候就将当前变量从内存中读出，然后计算结束之后再将结果存入内存。这里说的存入内存实际上就是存入当前函数的栈帧中（就是之前栈帧内的局部变量和临时变量的那一部分）

当一个函数中使用到变量的时候，如果是静态语言，这个时候在创建栈帧的时候就会直接分配这些变量的地址，然后在栈帧内直接进行读取（在栈帧内的读取操作实际上是随机的，而不是像栈一样的。可能栈帧的帧的意思就是一个栈的最小单位，最早进来的栈帧最晚出栈。如下图，这里的变量abcd就是在栈帧中随机存取的）

无分配算法的优缺点：

缺点：多了很多不必要的访存操作（没有合理利用寄存器）

优点：实现简单，可以直接将指令转化为汇编指令

所以如果想要有一个分配算法的话，就需要考虑如何实现寄存器分配

寄存器分配算法

本质上就是将当前状态下活跃的变量存储到寄存器中，使活跃变量对寄存器实现分时共用（不同时刻寄存器内可能是不同的变量，不同时刻变量可能存储在不同的寄存器中）

那么如果要进行寄存器分配，就需要找到所有的活跃变量

寄存器分配中的概念

活跃区间：活跃区间是拉通的（就是将第一个活跃点和最后一个活跃点之间拉通），如下

记忆：区间是一个连续的概念，所以活跃区间是拉通的

活跃范围：是活跃点的集合，如下

变量溢出：就是当寄存器不够用的时候，选择一个变量将其存储到内存中，此时就说这个变量溢出了。这个时候就能处理当前的程序了（变量的活跃点应该是不会变化的，只不过活跃变量并没有存储在寄存器中了，而是存储在内存中。计算活跃变量只是为了知道哪一些变量当前是有用的，然后期望将所有有用的变量都存储在寄存器中，但是寄存器不够的话还是要存在内存中的，并不是说存储在内存内就不可能是活跃变量了），而代价是当前的栈帧需要开的更大（也就是需要留出空间来存储当前溢出的变量，静态语言在编译的时候就能确定哪些变量需要溢出了，这个时候就能确定每一个函数的栈帧大小了），如下图：

注意活跃点应该是在两行语句之间的，所以变量的活跃状态的切换就是在语句内部进行切换的（实际上也是这样，因为如果一个变量从活跃变量变成一个不活跃变量，一定是因为语句执行了一些操作才导致的，所以活跃状态的变化是在语句中进行的），如下图：

上面绿色部分都是变量的活跃区间

这样就可以根据活跃区间来大概估计哪一些变量当前是活跃的了，也就是下图中说的可以根据活跃区间来进行寄存器分配：

注意，在这种算法中变量处于活跃区间并不意味着当前变量就是活跃的，只是认为当前变量是活跃的，那么就尝试在当前状态下给每一个当前处于活跃区间的变量分配一个寄存器

但是有一个问题，寄存器不够的时候应该如何选择溢出变量（溢出变量的时候需要将选中的需要溢出的变量存储到内存中，然后将当前需要存储的变量移动到寄存器中）？选择溢出变量的算法如下：

线性扫描算法

线性扫描算法的溢出变量选择如下：

就是出现需要溢出变量的情况的时候，就选择当前活跃区间最晚结束的变量（当然溢出最短的也行）。

对溢出活跃区间最晚结束的变量的理解

因为活跃区间是活跃点拉通，所以就认为最长的活跃区间里面的不活跃点占比是最高的，也就是该变量是使用频率最低的（如果占用一个寄存器的话），所以将该变量溢出。

线性扫描算法例题：

线性扫描算法的伪代码（代码逻辑）：

外层循环应该是当前程序的点的个数（就是从程序头到程序尾，然后通过循环内的归纳变量来模拟当前程序运行到的语句）

针对每一个程序执行点，都计算出哪些变量当前是活跃的（也就是start<当前点<end）并构建一个集合

然后查询当前寄存器分配给了哪些变量，如果当前已经占据寄存器的变量不在上一步生成的集合中，就将对应的寄存器进行释放。

然后逐个检查第二步生成的集合，选取活跃区间最早结束（也就是end最小）的三个（寄存器数量，如果第二步生成的集合里面都没有这么多变量，也就是说当前活跃的变量数小于寄存器数量，然后直接将这些变量放在寄存器内就好了。当然放入的时候也是需要看一下当前寄存器里面有没有这些变量，只将没有的变量存入空闲的寄存器）变量

将第四步找到的三个变量存储到寄存器中（只需要将这三个变量中不在寄存器内的变量存入寄存器即可就是加入当前寄存器内是变量abc，然后找到的是变量abd，那么就将c溢出然后将d存入寄存器。也就是说这里实际上还要找到两个集合不同的部分然后进行操作），到这里其实当前程序点的寄存器分配就完成了

进行下一次循环

注意上面的代码逻辑是错误的

这里根据论文原文的伪代码来说一遍实现逻辑

首先将所有的活跃区间展昭开始时间进行排序

然后按照活跃区间开始时间顺序进行寄存器的分配

遇到一个活跃区间时（所以是在每一次遇到区间开始的时候进行操作，区间结束的时候不进行操作），先将之前活跃区间已经结束的变量从寄存器组中弹出，这个时候可能会增加一些空闲的寄存器。释放完之后就有两种情况：

如果当前寄存器组中还有空闲寄存器，那么就直接将当前变量存储到寄存器中

如果当前寄存器组中没有空闲寄存器了，就选取当前寄存器组和当前变量（所以就不考虑之前已经溢出的变量了）中最晚结束的变量进行溢出

论文上的伪代码的执行结果就应该是下面的这种情况：

这里也是，每次出现溢出情况的时候都只考虑当前寄存器内的变量还有刚刚开始的变量（就是上面说的寄存器组内的变量还有当前变量），不考虑之前已经溢出的变量

这里最后r1和r2可用的时候也不能将r2分配给变量c

还有就是，如果函数有返回值的话也需要将返回值分配到寄存器内

图着色算法

线性扫描算法使用的信息是变量的活跃区间（活跃区间是不准确的），但是图着色算法使用的是变量的活跃范围（所以更加准确，对寄存器的使用率是更高的）

图着色算法的构造：

就是先创建一段程序中每一个变量的节点，然后如果一些变量在一个时间点上都是活跃的，那么他们就不能存在一个寄存器内，也就是不能涂上同一个颜色

图着色算法是一个NP问题，没有最优解

所以这里提供一个启发式算法：

这里的k在寄存器分配里面实际上就是寄存器的数量

这个原因还是很好理解的。一个节点连接的边少于k（假设为n），那么他周围的节点至多使用n个颜色（颜色重复的时候周围节点使用的颜色只会更少），那么当前节点添加回来的时候就一定能找到一个颜色

注意这里就是递归地删除节点了，如下图：

删除了节点c的时候节点d的边也少于4了（原来是有四条的），所以这个时候d也是能删掉的，只不过之后添加回来的时候就需要先添加d节点，然后再添加c节点（出的时候顺序是c、d，回来的时候顺序是d、c，相当于用栈实现。删除的时候将c压栈再将d压栈，然后添加回来的时候就先将d出栈，然后在将c出栈），也就是下图：

注意删除节点总不能一直删除删到节点全部都没了，删除节点删到剩下k个节点的时候就能保证相邻颜色是不同的了

注意此时变量d仍然有三条边，这个时候仍然将其删去（虽然不满足启发式算法，但是可以通过变量溢出来处理），也就是当讲节点回填的时候如果没有颜色可以选择了，就将当前回填的节点溢出

注意上述两个方法都可以用于基本块之间的寄存器分配（虽然线性扫描看着好像不太像基本块间的寄存器分配，但是只要把活跃区间求出来了，什么玩意都能用线性扫描）

使用线性扫描算法的时候需要将每一条语句的活跃变量求出来（这个时候就可以构造一个比较诡异的程序流图——每一条语句都是一个节点，这个时候显然他也可以像正常的程序流图一样去处理所有的活跃变量），也就是下图所说的所有指令（就是要求出来每一行的活跃变量，因为线性扫描需要使用活动范围，所以做线性扫描就需要求出来所有语句的活跃变量）

活跃变量的分析可以在中间代码上用（这个时候就是用来删除无用赋值的了），也可以不在中间代码上用（这个时候就是针对源代码来进行寄存器分配了）

下面是活跃变量的定义，说的是在程序中（所以在源代码上就能进行活跃变量的求解了，只不过可能要对源程序做一点点改造，比如将while等语句改成goto语句，这样求活跃变量就会方便一点。有一些活跃变量的题都会出现return，就说明一定是源代码了）

注意，图着色算法不一定比线性扫描好，虽然图着色是考虑了活跃范围，但是他并没有区分程序的状态；线性扫描虽然考虑的是活跃区间（拉通的），但是考虑了程序的状态。

总结：活跃变量可以对中间代码用，也可以对源代码用。

如果对中间代码求活跃变量，主要目的是对当前的代码进行删除无用赋值

如果对源代码使用，主要的目的就有两个：一个是对源代码进行无用赋值的删除，另一个是进行寄存器的分配

静态单一赋值

SSA（静态单一赋值）的定义如下：

这里的ir是中间形式的意思

现在谈谈自己对静态单一赋值的理解：实际上就是对程序中（所以不是对程序的一条通路进行处理，而是对所有的变量。可以把他理解为这个是静态单一赋值的第一步，就比如说对ifelse中的变量就要一起处理。虽然是对程序中所有的变量进行静态单一赋值，但是最终的目的是希望生成的代码中每一个变量都只被赋值一次，所以在下面φ函数的实现中可以在两个互斥的分支中进行对同一变量的赋值，但是这个也是属于改造的部分了，也可以把这个看成是静态单一赋值的第二个步骤——消除冲突）的多个赋值语句进行处理，让每一个赋值语句都有一个唯一的标号（也就是给多出来的赋值语句增加一个变量，最终可以使得程序中的每一个变量都只被赋过一次值。也就是上面所说的每个变量最多被赋值一次），这个时候在程序的任意一个位置引用一个变量都能很简单的确定当前变量的值是多少（也就是使得程序的处理更加简单了）

也就是：

下面是一个静态单一赋值的例题：

上面说道静态单一赋值是对程序中所有变量进行处理的，但实际上一些变量的赋值是跟程序流有关系的，这个时候就不知道怎么赋值了，如下图：

这个时候为了继续进行静态单一赋值就需要让当前的赋值语句的右操作数是确定的，但是这个时候赋值语句的右操作数应该是上面相关流程中变量的函数，所以在这里增加一个φ函数，如下：

如上，这个φ函数的参数为之前程序中的相关变量，输出是当前函数需要的右操作数变量（注意这个时候变量名也不能重复，因为每一个变量只能赋一次值）

所以这里φ函数的作用就是从多个程序分支中计算出当前赋值语句需要的右操作数

φ函数的实现如下：

程序因为分支的问题出现了右操作数不确定的情况，那么就在这里将φ函数上提（虽然说是静态单一赋值，但是这里其实就是对生成的静态单一赋值代码进行了改造。程序执行的时候永远是只对a3进行了一次赋值。时刻记得静态单一赋值的目的——使生成的代码中每一个变量都只有一次赋值）。

但是如果是按照上面的情况来进行处理的话，那就需要在分一次分支汇合的时候都插入φ函数，就会出现如下图所说的：

这里是为每一个活跃变量都创建了φ函数，所以这个时候生成的就是最大的SSA。

但是实际上只有当在两个路径上都进行赋值了的变量才需要进行φ函数的合并，所以就有了下面的最小SSA：

这里y是两个路径上都进行了赋值的，但是x没有，所以x的值在合并的时候是确定的，进而就可以消除x的φ函数只保留y的φ函数

上面是一个循环中的SSA示例。

说白了就是要先找到多条路径汇聚的节点，然后再为这几条路径中都有赋值的活跃变量进行φ函数的插入。如上图中的第二个基本块，他就是第一个基本块和第二个基本块的交汇点。而在这两个基本块中都有对变量a的赋值，所以这里在第二个基本块的开头加入一个关于a1（就是从循环外部进入的）和a2（从上一次循环进入的）的φ函数

上面是一个插入φ函数的条件。前面五条都是说在多个赋值节点的交汇处进行插入。

这里的注要看一下。这个xy可能是z的意思就是右边的那一张图的情况

变量的定义会支配变量的使用

下面的idom就相当于求出来一个最近的dom节点。

也就是下面这个例题：

也就是上面这个图（上面这个图错了，D12应该是12和1）

所以求idom节点的时候，就是找离当前节点最近的一个节点。

总结——如何求解idom节点：

先求解出所有节点的必经节点集

根据必经节点集找到离当前节点最近的并且非自身的节点，该节点就是当前节点的idom节点

自身也是自身的一个idom节点

绘制支配树的时候就根据idom节点来画就好了（要省去自环）

然后在idom集中再求一次sdom，就得到了下面的6、7、8节点

上面的支配边界的求解需要先得到被5idom的节点5，6,7,8然后再在5，6,7,8支配的节点中向下寻找，找到一个最近的不被5支配（这个时候如果没有被dom，就一定没有被sdom。但是没有被sdom，不一定没有被dom，如对这个节点自身，当前节点自身没有自身sdom，但是被自身dom，所以算支配边界的时候要额外考虑一下自身是不是也在支配边界内，也或者说向后查找节点a的dom集的时候不考虑节点a自身）的节点，然后这些节点就构成了节点5的支配边界

接下来就只需要在支配边界中插入5节点中变量a的φ函数即可，如下：

现在谈谈支配的理解：

如果一个节点a被另一个节点b支配，那么a里面的所有的变量都应该是由b中的节点确定的。当找到了b的支配边界中的某个节点c了之后，由于c不是被b支配的，但是到达c有可能（这里只是说有可能是因为b已经不是c的必经节点了，这个时候到达c就有多条路径，其中一条是经过b的，然后这些路径在c处汇合）经过b，所以需要在节点c中插入φ函数。

所有φ函数插入之后从头开始分配变量名，还是不用他这里的这个栈方法了，感觉直接看就能看出来

使用了SSA之后，由于变量都是唯一赋值的，这个时候就能将常量随便传播了（之前不能随便传播是因为在程序执行的路径上可能对常量变量又进行了赋值，所以这个时候常量传播就只能从想要进行替换的地方向上寻找，找到最近的一个常量进行赋值，而且碰到分支的时候还不知道要用哪一个常量进行替换。所以就不能像SSA一样确定下来当前变量的常量值到底是多少了），甚至可以直接从上向下传播（之前如果要做常量传播的话就只能从下向上找最近的一个常量来传播）