第八章 中间代码生成

中间代码生成程序

任务 - 把经分析后得到的源程序的中间表示形式翻译成中间代码表示

位置 - 语义分析后

优点

  • 便于编译程序的建立和移植
  • 便于进行与机器无关的代码优化工作

缺点

  • 增加了I/O操作、效率有所下降

中间代码形式

图形表示

语法树

描绘了源程序的自然层次结构。

dag图
以更紧凑的方式给出了与语法树同样的信息。在dag中，公共子表达式被标识出来了。

三地址代码

三地址语句组成的序列，类似于汇编语言的代码

一般形式

x:=y  op  zx:=y\ \ op\ \ z

  • x可以是名字、临时变量
  • y、z 可以是名字、常数、或临时变量
  • op 代表运算符号，如算数运算符、或逻辑运算符等
  • 语句中，最多有三个地址

实现时，语句中的名字，将由指向该名字在符号表中表项的指针所代替

常见的三地址语句

简单赋值语句

  • x:=y op z
  • x:=op y
  • x:=y

含有变址的赋值语句

  • x:=y[i]
  • x[i]:=y

含有地址和指针的赋值语句

  • x:=&y
  • x:=*y
  • x:=y

转移语句

  • goto L

  • if x relop y goto L

过程调用语句

  • param x
  • call p, n

返回语句

  • return y

三地址语句的表示方法

四元式

需要引入临时变量，表示清晰但效率不高，占用内存大

  • (op，arg1，arg2，result)

    如x:=y+z (‘+’, y, z, x)

  • (op，arg1， ，result)

    如: x:=-y (‘uminus’, y, , x)

  • (param，arg1， ， )

    如:param x (param, x, , )

  • (goto， ， ，语句标号)

    如:goto L (goto, , , L)

image-20231219101924472

三元式

(op，arg1，arg2)

  • 避免把临时变量名也存入符号表，不引入临时变量
  • 计算结果直接提供给引用它的语句
  • 用语句的指针代替存放中间结果的临时变量

image-20231219101934020

间接三元式

间接码表:为三元式序列建立的一个指针数组，其每个元素依次指向三元式序列中的一项

image-20231219102059985

赋值语句的翻译

一般语句的翻译

1
2
3
4
5
6
7
8
x:=a*b+y


t1:=a * b

t2:=t1+y

x:=t2

数组的翻译

一维数组a[N],使用三地址代码表示 x := a[i]

1
2
3
4
5
6
7
8
9
a[i] = a + w * (i - low)
(*low是下标起始值*)

t1:=w * i
t2:=t1 - C
t3:=t2[t1]
x:= t3

// C = w * low,定值

二维数组a[M][N]，使用三地址代码表示 x:=a[i,j]

1
2
3
4
5
6
7
8
9
10
11
a[i][j] = a + w * ((i-low1) * N + (j-low2))
// 整理，a[i][j] = a - w * (low1 * N + low2) + w * (i*N+j)
  
t1:= i * n
t1:= t1 + j
t2:= a - C
t3:= t1 * w
t4:= t2[t3]
x:= t4

// C = w * (low1 * N + low2)

布尔语句的翻译

1
2
3
4
5
6
a or not b and c

t1:= not b
t2:= t1 and c
t3:= a or t2
// 优先级 not > and > or

关系表达式的翻译

1
2
3
4
5
6
7
8
9
10
11
12
x > y 等价于

if x > y
  A()
else
  B()

100: if x > y goto 103
101: B() 
102: goto 104
103: A()
104: ...

回填

翻译控制语句的过程中，无法确定goto语句的标号时，可以先产生没有目标标号的转移指令，然后建立一个链表，把转向这个目标标号的所有转移指令的标号填入；当目标标号确定后，再把目标标号回填进这个链表中记录的所有转移指令中

控制语句的翻译

1
2
3
4
5
6
7
8
9
10
if x > y
  A()
else
  B()
  
100: if x > y goto 103
101: B() 
102: goto 104
103: A()
104: ...
1
2
3
4
5
6
7
8
while E
  A()

100: if E goto 102
101: goto 104
102: A()
103: goto 100
104: ...

第九章 目标代码生成

概述

目标代码生成程序的任务

将前端产生的源程序的中间代码表示转换为等价的目标代码

目标代码生成程序的要求

  • 正确
  • 高质量

有效地利用目标机器的资源

占用空间少，运行效率高

代码生成程序的输入

  • 中间代码:经过语法分析**/**语义检查之后得到的中间表示

  • 符号表
    记录了与名字有关的信息，决定中间表示中的名字所代表的数据对象的运行地址

代码生成程序的输出

与源程序等价的目标代码

目标代码的形式

  • 绝对地址的机器语言程序

    可把目标代码放在内存中固定的地方、立即执行

  • 可重定位的机器语言程序

    .obj(DOS)、.o(UNIX)

    开发灵活，允许各子模块单独编译

    由连接装配程序将它们连接在一起，生成可执行文件

  • 汇编语言程序

基本块与流图

具有原子性的一组连续语句序列。

控制从第一条语句(入口语句)流入，从最后一条语句 (出口语句)流出，中途没有停止或分支

基本块的划分方法

确定入口语句:

  • 三地址代码的第一条语句
  • goto语句转移到的目标语句
  • 紧跟在goto语句后面的语句

确定基本块:

  • 从一个入口语句(含该语句)到下一个入口语句(不含)之间的语句序列;
  • 从一个入口语句(含该语句)到停止语句(含该语句)之间的语句序列。

流图（控制流图，CFG）

把控制信息加到基本块集合中，形成程序的有向图， 称为流图(控制流图)。

  • 流图的结点是基本块。

  • 由程序的第一条语句开始的基本块，称为流图的首结点

  • 如果在某个执行序列中，基本块B2紧跟在基本块B1之后执行，则从B1到B2有一条有向边，B1是B2的前驱，B2是B1的后继。

    即如果:
    有一个条件/无条件转移语句从B1的最后一条语句转移到B2的第一条语句;(转移语句导致的)
    B1的最后一条语句不是转移语句，并且在程序的语句序列中，B2紧跟在B1之后。（本身就在B1后面）

第十章 代码优化

概述

代码优化程序的任务

  • 对中间代码或目标代码进行等价变换，使变换后的代码质量更高。

对代码优化程序的要求

  • 提高目标代码的执行速度
  • 减少目标代码占用的空间
  • 等价变换

代码优化程序的位置

  • 目标代码生成之前的中间代码优化
  • 目标代码生成之后的目标代码优化

代码优化的种类

中间代码优化

  • 基本块优化

    • 在基本块内进行的优化
    • 常数合并与传播、删除公共子表达式、复制传播、削弱计算强度、改变计算次序等

  • 循环优化

    • 在循环语句所生成的中间代码序列上进行的优化。
    • 循环展开、代码外提、削弱计算强度、删除归纳变量等

  • 全局优化

    • 在非线性程序段上(含多个基本块)进行的优化

目标代码优化

  • 窥孔优化
    • 在目标代码上进行局部改进的优化
    • 删除冗余指令、控制流优化、代数化简等。

基本块优化

常数合并及常数传播

常数合并:将在编译时可计算出值的表达式用其值替代。

x=2+3+y 可代之以: x=5+y

常数传播:用在编译时已知的变量值代替程序正文中对这些 变量的引用。

PI:=3.14;

D-to-R:=0.01744

注意：不可跨越基本块

常数合并的实现

  • 在符号表中增加两个信息域
    • 标志域:指示当前该变量的值是否存在。
    • 常数域:如果变量值存在，则该域存放的即是该变量的当前值。

常数合并时，注意事项:

  • 不能将结合律与交换律用于浮点表达式。
    • 浮点运算的精度有限，这两条定律并非是恒真的
  • 不应将任何附加的错误引入。

删除公共表达式

在一个基本块中，当第一次对表达式E求值之后，如果E中的运算对象都没有改变，再次对E求值，则除E的第一次出现之外， 其余的都是冗余的公共表达式。

n删除冗余的公共表达式，用第一次出现时的求值结果代替之。

10.2.3 复制传播

在复制语句 f:=g 之后，尽可能用 g 代替 f。

IMG_20231226_104831

image-20231226105135913

删除死代码

死代码:如果对一个变量 x 求值之后却不引用它的值， 则称对 x 求值的代码为死代码。

死块:控制流不可到达的块称为死块。

  • 如果一个基本块是在某一条件为真时进入执行的，经数据流分析的结果知该条件恒为假，则此块是死块。

  • 如果一个基本块是在某个条件为假时才进入执行，而 该条件却恒为真，则这个块也是死块。

在确定一个基本块是死块之前，需要检查转移到该块的所有转移语句的条件。

死块的删除，可能使其后继块成为无控制转入的块，这样的块也成为死块，同样应该删除。（连续删除）

削弱计算强度

对基本块的代数变换:对表达式中的求值计算用代数上等价的形式替换，以便使复杂的运算变换成为 简单的运算。

*x:=y*2 可以用代数上等价的乘式(如:x:=y*y)代替

x:=x+0 和 x:=x*1

  • 执行的运算没有任何意义,应将这样的语句从基本块中删除。

改变计算次序

考虑语句序列:
t1:=b+c
t2:=x+y

  • 如果这两个语句是互不依赖的，即x、y均不为t1**，b、 **c均不为t2，则交换这两个语句的位置不影响基本块的执行结果。

  • 对基本块中的临时变量重新命名不会改变基本块的执行结果。

    如:语句 t:=b+c 改成语句 u:=b+c

    把块中出现的所有t都改成u，不改变基本块的值。

循环优化

为循环语句生成的中间代码包括如下4部分:

  • 初始化部分:对循环控制变量及其他变量赋初值。此部分组成的基本块位于循环体语句之前，可视为构成循环的第一个基本块。

  • 测试部分:测试循环控制变量是否满足循环终止条件。这部分的位置依赖于循环语句的性质，若循环语句允许循环体执行0 次，则在执行循环体之前进行测试;若循环语句要求循环体至少执行1次，则在执行循环体之后进行测试。

  • 循环体:由需要重复执行的语句构成的一个或多个基本块组成。

  • 调节部分:根据步长对循环控制变量进行调节，使其增加或减少一个特定的量。可把这部分视为构成该循环的最后一个基本块。

循环结构中的调节部分和测试部分也可以与循环体中的其他语句一起出现在基本块中

循环展开

以空间换时间的优化过程。

  • 循环次数在编译时可以确定
  • 针对每次循环生成循环体(不包括调节部分和测试部分) 的一个副本。

进行循环展开的条件:

  • 识别出循环结构，而且编译时可以确定循环控制变量的初值、终值、以及变化步长。
  • 用空间换时间的权衡结果是可以接受的。

在重复产生代码时，必须确保每次重复产生时，都对循环控制变量进行了正确的合并。

image-20231226110838861

代码外提/频度削弱

降低计算频度的优化方法。

将循环结构中的循环无关代码提到循环结构的外面 (通常提到循环结构的前面)，从而减少循环中的代码总数。

如C语言程序中的语句:

1
2
3
while (i<=limit-2) {
... 
}

如果limit的值在循环过程中保持不变，则 limit-2的计算与循环无关。

优化为

1
2
3
4
t:=limit-2; 
while (i<=t) {
...
}

削弱计算强度

将当前运算类型代之以需要较少执行时间的运算类型的优化方法。

大多数计算机上乘法运算比加法运算需要更多的执行时间。

如可用+代替*，则可节省许多时间，特别是当这种替代发生在循环中时更是如此

删除归纳变量

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

如果i是循环中的一个基本归纳变量，j在循环中的定值总可以化归为i的同一线性函数，即j:=c1*i+c2， 这里c1和c2都是循环不变量，则称j是归纳变量，并称j与i同族。

通常，一个基本归纳变量除用于其自身的递归定值外，往往只用于计算其他归纳变量的值、以及用来 控制循环的进行。

对语句

if i<=10 goto B4 {

​ t2 = 4*i

}

由于t2和i之间具有线性函数关系:t2=4*i

所以，i<=10 与 t2<=40 是等价的。

因此，可以用 t2<=40 来替换 i<=10

变换为:if t2<=40 goto B4