编译原理 第十一章 代码生成 编译原理.

Presentation on theme: "编译原理 第十一章 代码生成 编译原理."— Presentation transcript:

1 编译原理 第十一章 代码生成 编译原理

2 源程序 表 词法分析器 出 单词符号 格 错 语法分析器 管 处 语法单位 理 理 中间代码生成器 四元式 优化段 四元式 目标代码生成器
编译原理

3 代码生成是把语法分析后或优化后的中间代码变换成目标代码。 目标代码一般有以下三种形式：
能够立即执行的机器语言代码，所有地址已经定位； 待装配的机器语言模块。执行时，由连接装配程序把它们和某些运行程序连接起来，转换成能执行的机器语言代码； 汇编语言代码。尚须经过汇编程序汇编，转换成可执行的机器语言代码。 编译原理

4 代码生成着重考虑的问题： 如何使生成的目标代码较短； 如何充分利用计算机的寄存器，减少目标代码中访问存贮单元的次数。
如何充分利用计算机的指令系统的特点。 编译原理

5 11.1 基本问题 代码生成器的输入 代码生成器的输入包括源程序的中间表示，以及符号表中的信息 类型检查 编译原理
11.1 基本问题 代码生成器的输入 代码生成器的输入包括源程序的中间表示，以及符号表中的信息 类型检查 假定已经作过必要的类型检查，所以在必要的地方已经加入了类型转换操作，并且已检测出一些明显的语义错误。这样代码生成阶段就可以假设它的输入是没有错误的。 编译原理

6 11.1 基本问题 目标程序 指令选择 绝对机器代码、可再定位机器语言、汇编语言 采用汇编代码作为目标语言 a:=a+1 INC a
11.1 基本问题 目标程序 绝对机器代码、可再定位机器语言、汇编语言 采用汇编代码作为目标语言 指令选择 a:=a+1 INC a LD R0, a ADD R0, #1 ST R0, a 编译原理

7 11.1 基本问题 寄存器分配 计算顺序选择 在寄存器分配期间，为程序的某一点选择驻留在寄存器中的一组变量。
11.1 基本问题 寄存器分配 在寄存器分配期间，为程序的某一点选择驻留在寄存器中的一组变量。 在随后的寄存器指派阶段，挑出变量将要驻留的具体寄存器。 计算顺序选择 编译原理

8 11.2 目标机器模型 考虑一个抽象的计算机模型 具有多个通用寄存器，他们既可以作为累加器，也可以作为变址器。 运算必须在某个寄存器中进行。
11.2 目标机器模型 考虑一个抽象的计算机模型 具有多个通用寄存器，他们既可以作为累加器，也可以作为变址器。 运算必须在某个寄存器中进行。 含有四种类型的指令形式 编译原理

9 如果op是一目运行符，则“op Ri, M”的意义为：op（M） Ri，其余类型可类推。
编译原理

10 op 包括一般计算机上常见的一些运算符，如 ADD 加 SUB 减 MUL 乘 DIV 除
编译原理

11 编译原理

12 11.3 一个简单代码生成器 不考虑代码的执行效率，目标代码生成是不难的，例如： A:=(B+C)*D+E 翻译为四元式： T1:=B+C
11.3 一个简单代码生成器 不考虑代码的执行效率，目标代码生成是不难的，例如： A:=(B+C)*D+E 翻译为四元式： T1:=B+C T2:=T1*D T3:=T2+E A:=T3 编译原理

13 假设只有一个寄存器可供使用 目标代码： LD R0，B ADD R0 ，C ST R0 ，T1 四元式T1:=B+C
假设T1，T2，T3在基本块之后不再引用: LD R0，B ADD R0，C MUL R0，D ADD R0，E ST R0，A T2:=T1*D LD R0 ，T1 MUL R0，D ST R0 ，T2 T3:=T2+E LD R0 ，T2 ADD R0 ，E ST R0 ，T3 A:=T3 LD R0，T3 ST R0 ，A 编译原理

14 11.3 一个简单代码生成器 四元式的中间代码变换成目标代码，并在一个基本块的范围内考虑如何充分利用寄存器：
11.3 一个简单代码生成器 四元式的中间代码变换成目标代码，并在一个基本块的范围内考虑如何充分利用寄存器： 尽可能留：在生成计算某变量值的目标代码 时，尽可能让该变量保留在寄存器中。 尽可能用：后续的目标代码尽可能引用变量 在寄存器中的值，而不访问内存。 及时腾空：在离开基本块时，把存在寄存器 中的现行的值放到主存中。 编译原理

15 待用信息 如果在一个基本块内，四元式i对A定值，四元式j要引用A值，而从i到j之间没有A的其他定值，那么，我们称j是四元式i的变量A的待用信息。（即下一个引用点） i: A:=B op C … j: D:=A op E 假设在变量的符号表登记项中含有记录待用信息和活跃信息的栏。 编译原理

16 1 (x,x)表示变量的待用信息和活跃信息。其中i表示待用信息，y表示活跃，^表示非待用和非活跃；
待用信息和活跃信息的表示： 1 (x,x)表示变量的待用信息和活跃信息。其中i表示待用信息，y表示活跃，^表示非待用和非活跃； 2 在符号表中，(x，x)→(x，x)表示后面 的符号对代替前面的符号对； 3 不特别说明，所有说明变量在基本块出 口之后均为非活跃变量。 编译原理

17 计算待用信息和活跃信息的算法步骤： 1. 开始时，把基本块中各变量的符号表登记项中的待用信息栏填为“非待用”，并根据该变量在基本块出口之后是不是活跃的，把其中的活跃信息栏填为“活跃”或“非活跃”； 编译原理

18 2. 从基本块出口到基本块入口由后向前依次处理各个四元式。对每一个四元式i: A:=B op C，依次执行下面的步骤：
1) 把符号表中变量A的待用信息和活跃信息附加到四元式i上； 2) 把符号表中A的待用信息和活跃信息分别置为“非待用”和“非活跃”； 3) 把符号表中变量B和C的待用信息和活跃信息附加到四元式i上； 4) 把符号表中B和C的待用信息均置为i，活跃信息均置为“活跃”。 编译原理

19 建立待用信息链表与活跃变量信息链表如下：
例：基本块 1. T:=A-B 2. U:=A-C 3. V:=T+U 4. W:=V+U 设W是基本块出口之后的活跃变量。 建立待用信息链表与活跃变量信息链表如下： 编译原理

20 编译原理

21 附加在四元式上的待用/活跃信息表： 序号 四元式 左值 左操作数 右操作数 (4) W:=V+U (^,y) (^,^) (^,^)
序号 四元式 左值 左操作数 右操作数 (4) W:=V+U (^,y) (^,^) (^,^) (4,y) (3) V:=T+U (^,^) (4,y) (3,y) (^,^) (^,^) (2) U:=A-C (1) T:=A-B (3,y) (2,y) (^,^) 变量名 初始状态→信息链(待用/活跃信息栏) T (^,^) A B C U V W (^,y) → (3,y) → (^,^) → (2,y) → (1,y) → (1,y) → (2,y) → (4,y) → (3,y) → (^,^) → (4,y) → (^,^) → (^,^) 编译原理

22 编译原理

23 寄存器描述数组RVALUE 变量地址描述数组AVALUE 动态记录各寄存器的使用信息 RVALUE[R]={A,B}
动态记录各变量现行值的存放位置 AVALUE[A]={R1, R2, A} 编译原理

24 补充说明： 因为寄存器的分配是局限于基本块范围之内的，一旦处理完基本块中所有四元式，对现行值在寄存器中的每个变量，如果它在基本块之后是活跃的，则要把它存在寄存器中的值存放到它的主存单元中。 要特别强调的是，对形如：A:=B的四元式，如果B的现行值在某寄存器Ri中，则无须生成目标代码，只须在RVALUE(Ri)中增加一个A，(即把Ri同时分配给B和A)，并把AVALUE(A)改为Ri 。 编译原理

25 对每个四元式: i: A:=B op C，依次执行：
代码生成算法： 对每个四元式: i: A:=B op C，依次执行： 1. 以四元式: i: A:=B op C 为参数，调用函数过程GETREG(i: A:=B op C)，返回一个寄存器R，用作存放A的寄存器。 2. 利用AVALUE[B]和AVALUE[C]，确定B和C现行值的存放位置B’和C’。如果其现行值在寄存器中，则把寄存器取作B’和C’ 编译原理

26 如果B’或C’为R，则删除AVALUE[B]或AVALUE[C]中的R。 4. 令AVALUE[A]={R}, RVALUE[R]={A}。
3. 如果B’≠R，则生成目标代码： LD R, B’ op R, C’ 否则生成目标代码 op R, C’ 如果B’或C’为R，则删除AVALUE[B]或AVALUE[C]中的R。 4. 令AVALUE[A]={R}, RVALUE[R]={A}。 编译原理

27 5. 若B或C的现行值在基本块中不再被引用， 也不是基本块出口之后的活跃变量，且其 现行值在某寄存器Rk中，则删除 RVALUE[Rk]中的B或C以及AVALUE[B]或 AVALUE[C] 中的Rk ，使得该寄存器不再 为B或C占用。 编译原理

28 寄存器分配：GETREG(i: A:=B op C) 返回一个用来存放A的值的寄存器
1 如果B的现行值在某个寄存器Ri中，RVALUE[Ri]中只包含B，此外，或者B与A是同一个标识符，或者B的现行值在执行四元式A:=B op C之后不会再引用，则选取Ri为所需要的寄存器R，并转4； 2 如果有尚未分配的寄存器，则从中选取一个Ri为所需要的寄存器R，并转4； 1 尽可能用B独占的寄存器 2 后尽可能用空闲寄存器 3 抢占用非空闲寄存器 编译原理

29 3 从已分配的寄存器中选取一个Ri为所需要的寄存器R。最好使得Ri满足一下条件：
1 尽可能用B所在的寄存器 2 后尽可能用空闲寄存器 3 抢占用非空闲寄存器 3 从已分配的寄存器中选取一个Ri为所需要的寄存器R。最好使得Ri满足一下条件： 占用Ri的变量的值也同时存放在该变量的贮存单元中，或者在基本块中要在最远的将来才会引用到或不会引用到。 要不要为Ri中的变量生成存数指令？ 编译原理

30 要不要为Ri中的变量生成存数指令？ 4 给出R，返回。
对RVALUE[Ri]中每一变量M，如果M不是A，或者如果M是A又是C，但不是B并且B也不在RVALUE[Ri]中，则 (1) 如果AVALUE[M]不包含M，则生成 目标代码 ST Ri，M (2) 如果M是B，或者M是C但同时B也在RVALUE[Ri]中，则令AVALUE[M]={M， Ri} ，否则令AVALUE[M]={M} (3) 删除RVALUE[Ri]中的M 4 给出R，返回。 编译原理

31 设W是基本块出口之后的活跃变量，只有R0和R1是可用寄存器，生成的目标代码和相应的RVALUE和AVALUE:
例：基本块 1. T:=A-B 2. U:=A-C 3. V:=T+U 4. W:=V+U 设W是基本块出口之后的活跃变量，只有R0和R1是可用寄存器，生成的目标代码和相应的RVALUE和AVALUE: 编译原理

32 中间代码 目标代码 RVALUE AVALUE
LD R0，A SUB R0，B R0含有T T在R0中 T:=A－B U:=A－C LD R1，A SUB R1，C R0含有T R1含有U T在R0中 U在R1中 V:=T＋U ADD R0，R1 R0含有V R1含有U V在R0中 U在R1中 W:=V＋U ADD R0，R1 R0含有W W在R0中 ST R0，W 编译原理

33 作业 P327-1 编译原理