第八章代码生成 许畅 南京大学计算机系 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 南大编译许畅