南京大学：《编译原理 Principles and Techniques of Compilers》课程教学电子教案（课件讲义）第八章 代码生成

第八章代码生成 许畅 南京大学计算机系 2022年春季 版权所有南京大学计算机科学与技术系许畅2022春季版

许畅 南京大学计算机系 2022年春季 第八章 代码生成 版权所有 南京大学计算机科学与技术系 许畅 2022春季版 南大编译许畅

主要内容 。代码生成器的设计 目标语言 目标代码中的地址 。基本块和流图 基本块优化 大编译许畅 代码生成器 寄存器分配 2

主要内容 • 代码生成器的设计 • 目标语言 • 目标代码中的地址 • 基本块和流图 • 基本块优化 • 代码生成器 • 寄存器分配 2 南大编译许畅

代码生成器的位置 根据中间表示(R)生成代码 代码生成器之前可能有一个优化组件 代码生成器的三个任务 指令选择：选择适当的指令实现IR语句 寄存器分配和指派：把哪个值放在哪个寄存器中 指令排序：按照什么顺序安排指令执行 源程序· 前端 中间 代码优 中间 代码 目标 代码 化器 代码 生成器 程序 图8-1 代码生成器的位置 3

代码生成器的位置 • 根据中间表示 (IR) 生成代码 • 代码生成器之前可能有一个优化组件 • 代码生成器的三个任务 – 指令选择：选择适当的指令实现IR语句 – 寄存器分配和指派：把哪个值放在哪个寄存器中 – 指令排序：按照什么顺序安排指令执行 3 南大编译许畅

要解决的问题 正确性：正确的机器指令 易于实现、测试和维护 。输入IR的选择 四元式、三元式、字节代码、堆栈机代码、后缀表示、 抽象语法树、DAG图、. 输出 RISC、CISC 可重定向代码、汇编语言 4

要解决的问题 • 正确性：正确的机器指令 • 易于实现、测试和维护 • 输入IR的选择 – 四元式、三元式、字节代码、堆栈机代码、后缀表示、 抽象语法树、DAG图、… • 输出 – RISC、CISC – 可重定向代码、汇编语言 4 南大编译许畅

目标机模型 使用三地址机器的模型 。指令 加载：LD dst,addr(把地址addr中的内容加载到dst所指 的寄存器) 保存：STx,r(把寄存器r中的内容保存到x中) 计算：OP dst,,srC1vsrc2(把srC1和srC2中的值运算后将结 果存放到dst中) 无条件跳转：BRL(控制流转向标号L的指令) 条件跳转：Bcond r,L(对r中的值进行测试，如果为真 则转向L) 5

目标机模型 • 使用三地址机器的模型 • 指令 – 加载：LD dst, addr (把地址addr中的内容加载到dst所指 的寄存器) – 保存：ST x, r (把寄存器r中的内容保存到x中) – 计算：OP dst, src1 , src2 (把src1和src2中的值运算后将结 果存放到dst中) – 无条件跳转：BR L (控制流转向标号L的指令) – 条件跳转：Bcond r, L (对r中的值进行测试，如果为真 则转向L) 5 南大编译许畅

寻址模式 变量x:指向分配x的内存位置 a(r):地址是a的左值加上寄存器r中的值 constant(r):寄存器r中内容加上前面的常数即其 地址 *:寄存器r的内容所表示的位置上存放的内容位 置 *constant(r):寄存器r中内容加上常数所代表的位 置上的内容所表示的位置 。常数#constant 6

寻址模式 • 变量x：指向分配x的内存位置 • a(r)：地址是a的左值加上寄存器r中的值 • constant(r)：寄存器r中内容加上前面的常数即其 地址 • *r：寄存器r的内容所表示的位置上存放的内容位 置 • *constant(r)：寄存器r中内容加上常数所代表的位 置上的内容所表示的位置 • 常数#constant 6 南大编译许畅

例子(1) x=y-Z LD R1,y /R1=y LD R2,Z /∥R2=z SUB R1,R1,R2 /∥R1=R1-R2 ST x,R1 /x=R1 。1 b=a[i] LD R1,i /川R1=i MUL R1,R1,8 /∥R1=R1*8(8字节长元素) LD R2,a(R1) //R2 contents(a contents(R1)) ST b,R2 /b=R2 2

例子 (1) • x = y – z – LD R1, y // R1 = y – LD R2, z // R2 = z – SUB R1, R1, R2 // R1 = R1 – R2 – ST x, R1 // x = R1 • b = a[i] – LD R1, i // R1 = i – MUL R1, R1, 8 // R1 = R1 * 8 (8字节长元素) – LD R2, a(R1) // R2 = contents(a + contents(R1)) – ST b, R2 // b = R2 7 南大编译许畅

例子(2) 。a[j]=c LD R1,c /R1=c LD R2,j /R2=j MUL R2,R2,8 /川R2=R2*8(8字节长元素) ST a(R2),R1 //contents(a contents(R2))=R1 。X=p LD R1,P /R1=P LDR2,0(R1) //R2 contents(0+contents(R1)) ST x,R2 /x=R2 8

例子 (2) • a[j] = c – LD R1, c // R1 = c – LD R2, j // R2 = j – MUL R2, R2, 8 // R2 = R2 * 8 (8字节长元素) – ST a(R2), R1 // contents(a + contents(R2)) = R1 • x = *p – LD R1, p // R1 = p – LD R2, 0(R1) // R2 = contents(0 + contents(R1)) – ST x, R2 // x = R2 8 南大编译许畅

例子(3) 。*p=y LD R1,P /∥R1=p LD R2,y /R2=y ST0(R1),R2 /contents(0+contents(R1))=R2 ·ifx<y goto L -LD R1,x /∥R1=x LD R2,y //R2=y SUB R1,R1,R2 /∥R1=R1-R2 BLTZ R1,M //if R1<0jump to M 9

例子 (3) • *p = y – LD R1, p // R1 = p – LD R2, y // R2 = y – ST 0(R1), R2 // contents(0 + contents(R1)) = R2 • if x < y goto L – LD R1, x // R1 = x – LD R2, y // R2 = y – SUB R1, R1, R2 // R1 = R1 – R2 – BLTZ R1, M // if R1 < 0 jump to M 9 南大编译许畅

程序及指令的代价 不同的目的有不同的度量 最短编译时间、运行时间、目标程序大小、能耗 不可判定一个目标程序是否最优 假设每个指令有固定的代价，设定为1加上运算分 量寻址模式的代价 LDR0,R1:代价为1 LDR0,M:代价是2 LDR1,*100(R2):代价为2 10

程序及指令的代价 • 不同的目的有不同的度量 – 最短编译时间、运行时间、目标程序大小、能耗 • 不可判定一个目标程序是否最优 • 假设每个指令有固定的代价，设定为1加上运算分 量寻址模式的代价 – LD R0, R1：代价为1 – LD R0, M：代价是2 – LD R1, *100(R2)：代价为2 10 南大编译许畅