1、第八章第八章 代代 码码 生生 成成 本章内容本章内容 一个简单的代码生成算法一个简单的代码生成算法 涉及存储管理，指令选择，寄存器分配涉及存储管理，指令选择，寄存器分配和计算次序选择和计算次序选择等基本问题等基本问题前端前端代代 码码 优优 化化 器器中间中间代码代码源程序源程序代码代码生成生成器器中间中间代码代码目标目标程序程序8.1 代码生成器的设计中的问题代码生成器的设计中的问题8.1.1 目标程序目标程序 可执行目标模块可执行目标模块 可重定位目标模块可重定位目标模块允许程序模块分别编译允许程序模块分别编译调用其它先前编译好的程序模块调用其它先前编译好的程序模块 汇编语言程序汇编语言
2、程序免去编译器重复汇编器的工作免去编译器重复汇编器的工作从教学角度，增加可读性从教学角度，增加可读性8.1 代码生成器的设计中的问题代码生成器的设计中的问题8.1.2 指令的选择指令的选择目标机器指令系统的性质决定了指令选择的目标机器指令系统的性质决定了指令选择的难易程度，指令系统的统一性和完备性是重难易程度，指令系统的统一性和完备性是重要的因素要的因素指令的速度和机器特点是另一些重要的因素指令的速度和机器特点是另一些重要的因素8.1 代码生成器的设计中的问题代码生成器的设计中的问题若不考虑目标程序的效率，指令的选择是直若不考虑目标程序的效率，指令的选择是直截了当的。截了当的。三地址语句三地址
3、语句x:=y+z（x x，y y和和z z都是静态分配）都是静态分配）MOVy,R0/*把把y装入寄存器装入寄存器R0*/ADDz,R0/*z加到加到R0上上*/MOVR0,x/*把把R0存入存入x中中*/逐个语句地产生代码，常常得到低质量的代码逐个语句地产生代码，常常得到低质量的代码 8.1 代码生成器的设计中的问题代码生成器的设计中的问题语句序列语句序列 a:=b+c d:=a+e的代码如下的代码如下MOV b,R0ADDc,R0MOVR0,aMOVa,R0ADDe,R0MOVR0,d8.1 代码生成器的设计中的问题代码生成器的设计中的问题语句序列语句序列 a:=b+c d:=a+e的代码
4、如下的代码如下MOV b,R0ADDc,R0MOVR0,aMOVa,R0-多余的指令多余的指令ADDe,R0MOVR0,d8.1 代码生成器的设计中的问题代码生成器的设计中的问题语句序列语句序列 a:=b+c d:=a+e的代码如下的代码如下MOV b,R0ADDc,R0MOVR0,aMOVa,R0-多余的指令多余的指令ADDe,R0-若若a不再使用，第三条也不再使用，第三条也MOVR0,d-多余多余8.1 代码生成器的设计中的问题代码生成器的设计中的问题8.1.3 寄存器分配寄存器分配运算对象处于寄存器中的指令通常比运算对运算对象处于寄存器中的指令通常比运算对象处于内存的指令要短一些，执行也
5、快一些象处于内存的指令要短一些，执行也快一些 寄存器分配寄存器分配选择驻留在寄存器中的一组变量选择驻留在寄存器中的一组变量 寄存器指派寄存器指派挑选变量要驻留的具体寄存器挑选变量要驻留的具体寄存器8.1 代码生成器的设计中的问题代码生成器的设计中的问题8.1.4 计算次序的选择计算次序的选择某种计算次序可能会比其它次序需要较少的某种计算次序可能会比其它次序需要较少的寄存器来保存中间结果寄存器来保存中间结果8.2 目目 标标 机机 器器 8.2.1 目标机器的指令系统目标机器的指令系统选择可作为几种微机代表的寄存器机器选择可作为几种微机代表的寄存器机器四字节组成一个字，有四字节组成一个字，有n个
6、通用寄存器个通用寄存器R0,R1,Rn-1。二地址指令二地址指令 op 源，目的源，目的MOV源传到目的源传到目的ADD源加到目的源加到目的SUB目的减去源目的减去源 8.2 目目 标标 机机 器器 地址模式和它们的汇编语言形式及附加代价地址模式和它们的汇编语言形式及附加代价模式模式 形式形式地址地址 附加代价附加代价绝对地址绝对地址 M M 1寄存器寄存器 R R 0变址变址 c(R)c+contents(R)1间接寄存器间接寄存器*Rcontents(R)0间接变址间接变址 *c(R)contents(c+contents(R)1 直接量直接量#cc 1 8.2 目目 标标 机机 器器 指
7、令实例指令实例MOVR0,MMOV4(R0),Mcontents(4+contents(R0)MOV*4(R0),Mcontents(contents(4+contents(R0)MOV#1,R08.2 目目 标标 机机 器器 8.2.2 指令的代价指令的代价指令代价取成指令代价取成1加上它的源和目的地址模式的加上它的源和目的地址模式的附加代价附加代价指令指令代价代价MOV R0，R11MOV R5，M 2ADD#1，R32SUB 4(R0),*12(R1)38.2 目目 标标 机机 器器 a:=b+c，a、b和和c都静态分配内存单元都静态分配内存单元MOV b,R0ADD c,R0代价代价=
8、6MOV R0,a8.2 目目 标标 机机 器器 a:=b+c，a、b和和c都静态分配内存单元都静态分配内存单元MOV b,R0ADD c,R0代价代价=6MOV R0,aMOV b,aADD c,a代价代价=6 8.2 目目 标标 机机 器器 a:=b+c，a、b和和c都静态分配内存单元都静态分配内存单元若若R0，R1和和R2分别含分别含a，b和和c的地址，则的地址，则MOV*R1,*R0ADD*R2,*R0代价代价=28.2 目目 标标 机机 器器 a:=b+c，a、b和和c都静态分配内存单元都静态分配内存单元若若R0，R1和和R2分别含分别含a，b和和c的地址，则的地址，则MOV*R1,
9、*R0ADD*R2,*R0代价代价=2若若R1和和R2分别含分别含b和和c的值，并且的值，并且b的值在这个的值在这个赋值后不再需要，则赋值后不再需要，则ADD R2,R1MOV R1,a代价代价=3 8.3 基本块和流图基本块和流图怎样为三地址语句序列生成目标代码？怎样为三地址语句序列生成目标代码？begin|(1)prod:=0 prod:=0;|(2)i:=1 i:=1;|(3)t1:=4*i do begin|(4)t2:=at1 prod:=prod+ai*bi;|(5)t3:=4*i i:=i+1|(6)t4:=bt3 end while i=20|(7)t5:=t2*t4 end|
10、(8)t6:=prod+t5|(9)prod:=t6|(10)t7:=i+1|(11)i:=t7|(12)if i=20 goto(3)8.3 基本块和流图基本块和流图8.3.1 基本块基本块基本块基本块：连续的语句序列，控制流从它的开始：连续的语句序列，控制流从它的开始进入，并从它的末尾离开进入，并从它的末尾离开再用有向边表示基本块之间的控制流信息，就再用有向边表示基本块之间的控制流信息，就能得到程序的流图能得到程序的流图8.3 基本块和流图基本块和流图三地址语句序列的三地址语句序列的划分基本块划分基本块 首先确定所有的首先确定所有的入口语句入口语句序列的第一个语句是入口语句序列的第一个语句
11、是入口语句能由条件转移语句或无条件转移语句转到的语句能由条件转移语句或无条件转移语句转到的语句是入口语句是入口语句紧跟在条件转移语句或无条件转移语句后面的语紧跟在条件转移语句或无条件转移语句后面的语句是入口语句句是入口语句 每个入口语句每个入口语句到下一个到下一个入口语句之前的语句入口语句之前的语句序列构成一个基本块序列构成一个基本块 8.3 基本块和流图基本块和流图(1)prod:=0(2)i:=1(3)t1:=4*i(4)t2:=at1(5)t3:=4*i(6)t4:=bt3(7)t5:=t2*t4(8)t6:=prod+t5(9)prod:=t6(10)t7:=i+1(11)i:=t7(
12、12)if i=20 goto(3)(1)prod:=0(2)i:=1(3)t1:=4*i(4)t2:=at1(5)t3:=4*I(6)t4:=bt3(7)t5:=t2*t4(8)t6:=prod+t5(9)prod:=t6(10)t7:=i+1(11)i:=t7(12)if i=20 goto(3)B1B28.3 基本块和流图基本块和流图8.3.2 基本块的变换基本块的变换 三地址语句三地址语句x:=y+zx:=y+z引用引用y y和和z z并对并对x x定值定值 一个名字的值在基本块的某一点以后还要引一个名字的值在基本块的某一点以后还要引用的话，我们说这个名字在该点是用的话，我们说这个名字
13、在该点是活跃活跃的的 基本块的等价基本块的等价两个基本块计算一组同样的表达式两个基本块计算一组同样的表达式这些表达式的值分别代表同样的活跃名字的值这些表达式的值分别代表同样的活跃名字的值 有很多等价变换可用于基本块有很多等价变换可用于基本块局部变换局部变换 全局变换全局变换8.3 基本块和流图基本块和流图 删除局部公共子表达式删除局部公共子表达式a:=b+c a:=b+cb:=a d b:=a dc:=b+c c:=b+cd:=a d d:=b 删除死代码删除死代码定值定值x:=y+z以后不再引用，以后不再引用，则称则称x为死变量为死变量8.3 基本块和流图基本块和流图 交换相邻的独立语句交换
14、相邻的独立语句t1:=b+c t2:=x+yt2:=x+y t1:=b+c当且仅当当且仅当x和和y都不是都不是t1，b和和c都不是都不是t2 代数变换代数变换x:=x+0可以删除可以删除x:=x*1 可以删除可以删除x:=y*2 改成改成x:=y*y 8.3 基本块和流图基本块和流图8.3.3 流图流图把控制流信息加到基本块集合，形成一个有把控制流信息加到基本块集合，形成一个有向图来表示程序向图来表示程序首结点首结点、前前驱驱、后继、后继8.3 基本块和流图基本块和流图 什么是循环什么是循环?所有结点是所有结点是强连通强连通的的唯一的循环唯一的循环入口入口 外循环和内循环外循环和内循环prod
15、:=0i:=1t1:=4*it2:=at1t3:=4*It4:=bt3t5:=t2*t4t6:=prod+t5prod:=t6t7:=i+1i:=t7if i=20 goto B2B1B28.3 基本块和流图基本块和流图8.3.4 下次引用信息下次引用信息为每个三地址语句为每个三地址语句x:=y op z决定决定x、y和和z的的下次引用信息下次引用信息i:x :=y op z .没有对没有对x的赋值的赋值j:=x .没有对没有对x的赋值的赋值k:=x8.3 基本块和流图基本块和流图8.3.4 下次引用信息下次引用信息为每个三地址语句为每个三地址语句x:=y op z决定决定x、y和和z的的下次
16、引用信息下次引用信息i:x :=y op z .没有对没有对x的赋值的赋值j:=x .没有对没有对x的赋值的赋值k:=x8.3 基本块和流图基本块和流图 对每个基本块从最后一个语句反向扫描到第对每个基本块从最后一个语句反向扫描到第一个语句一个语句，可以得到下次引用信息，可以得到下次引用信息i:x :=y op z .没有对没有对x的赋值的赋值j:=x .没有对没有对x的赋值的赋值k:=x8.3 基本块和流图基本块和流图 对每个基本块从最后一个语句反向扫描到第对每个基本块从最后一个语句反向扫描到第一个语句一个语句，可以得到下次引用信息，可以得到下次引用信息i:x :=y op z .没有对没有对
17、x的赋值的赋值j:=x .没有对没有对x的赋值的赋值k:=x 利用下次引用信息，可以压缩临时变量需要利用下次引用信息，可以压缩临时变量需要的空间的空间8.4 一个简单的代码生成器一个简单的代码生成器 依次考虑基本块的每个语句，为其产生代码依次考虑基本块的每个语句，为其产生代码 假定三地址语句的每种算符都有对应的目标假定三地址语句的每种算符都有对应的目标机器算符机器算符 假定计算结果留在寄存器中尽可能长的时间假定计算结果留在寄存器中尽可能长的时间,除非：除非：该寄存器要用于其它计算该寄存器要用于其它计算，或者，或者 到基本块结束到基本块结束8.4 一个简单的代码生成器一个简单的代码生成器在没有收
18、集全局信息在没有收集全局信息前，暂且以基本块为前，暂且以基本块为单位来生成代码单位来生成代码prod:=0i:=1t1:=4*it2:=at1t3:=4*It4:=bt3t5:=t2*t4t6:=prod+t5prod:=t6t7:=i+1i:=t7if i=20 goto B2B1B28.4 一个简单的代码生成器一个简单的代码生成器8.4.1 寄存器描述和地址描述寄存器描述和地址描述例：对例：对a:=b+c 如果寄存器如果寄存器Ri含含b，Rj含含c，且且b此后不再活跃此后不再活跃 产生产生ADD Rj,Ri，结果结果a在在Ri中中 如果如果Ri含含b，但但c在内存单元在内存单元，b仍然不再
19、活跃仍然不再活跃 产生产生ADD c,Ri，或者或者 MOV c,RjADD Rj,Ri若若c的值以后还要用的值以后还要用,第二种代码比较有吸引力第二种代码比较有吸引力8.4 一个简单的代码生成器一个简单的代码生成器在代码生成过程中，需要跟踪寄存器的内容和在代码生成过程中，需要跟踪寄存器的内容和名字的地址名字的地址 寄存器描述记住每个寄存器当前存的是什么寄存器描述记住每个寄存器当前存的是什么在任何一点，每个寄存器保存若干个在任何一点，每个寄存器保存若干个(包括零个包括零个)名字的值名字的值 名字的地址描述记住运行时每个名字的当前名字的地址描述记住运行时每个名字的当前值可以在哪个场所找到值可以在
20、哪个场所找到这个场所可以是寄存器、栈单元、内存地址、甚这个场所可以是寄存器、栈单元、内存地址、甚至是它们的某个集合至是它们的某个集合这些信息可以存于符号表中这些信息可以存于符号表中 这两个描述在代码生成过程中是变化的。这两个描述在代码生成过程中是变化的。8.4 一个简单的代码生成器一个简单的代码生成器8.4.2 代码生成算法代码生成算法对每个三地址语句对每个三地址语句x:=y op z 调用函数调用函数getreg决定放决定放y op z计算结果的场所计算结果的场所L 查看查看y的地址描述的地址描述,确定确定y值当前的一个场所值当前的一个场所y.如果如果y的值还不在的值还不在L中，产生指令中，
21、产生指令MOV y，L 产生指令产生指令op z，L，其中其中z 是是z的当前场所之一的当前场所之一 如果如果y和和/或或z的当前值不再引用，在块的出口的当前值不再引用，在块的出口也不活跃，并且还在寄存器中，那么修改寄也不活跃，并且还在寄存器中，那么修改寄存器描述存器描述8.4 一个简单的代码生成器一个简单的代码生成器8.4.3 寄存器选择函数寄存器选择函数函数函数getreg返回保存返回保存x:=y op z的的x值的场所值的场所L如果名字如果名字y在在R R中，这个中，这个R R不含其它名字的值不含其它名字的值,并且并且在执行在执行x:=y op z后后y不再有下次引用，那么返回不再有下次
22、引用，那么返回这个这个R R作为作为L。否则，返回一个空闲寄存器，如果有的话否则，返回一个空闲寄存器，如果有的话 否则，如果否则，如果x在块中有下次引用，或者在块中有下次引用，或者op是必须用是必须用寄存器的算符，那么找一个已被占用的寄存器寄存器的算符，那么找一个已被占用的寄存器R(可能产生可能产生MOV R，M指令，并修改指令，并修改 M的描述的描述)否则，如果否则，如果x在基本块中不再引用，或者找不到在基本块中不再引用，或者找不到适当的被占用寄存器，选择适当的被占用寄存器，选择x的内存单元作为的内存单元作为L。8.4 一个简单的代码生成器一个简单的代码生成器赋值语句赋值语句d:=(a b)
23、+(a c)+(a c)编译产生三地址语句序列：编译产生三地址语句序列：t1:=a bt2:=a ct3:=t1+t2d:=t3+t2 8.4 一个简单的代码生成器一个简单的代码生成器语语 句句 生成的代码生成的代码 寄存器描述寄存器描述 名字地址描述名字地址描述 寄存器空寄存器空 t1:=a b MOV a,R0SUB b,R0 R0含含t1 t1在在R0中中 t2:=a cMOV a,R1SUB c,R1R0含含t1R1含含t2t1在在R0中中t2在在R1中中t3:=t1+t2 ADD R1,R0 R0含含t3 R1含含t2 t3在在R0中中t2在在R1中中 d:=t3+t2 ADD R1
24、,R0 R0含含dd在在R0中中 MOV R0,d d在在R0和内存和内存中中 8.4 一个简单的代码生成器一个简单的代码生成器前三条指令可以修改，使执行代价降低前三条指令可以修改，使执行代价降低MOV a,R0MOV a,R0SUB b,R0MOV R0，R1 MOV a,R1SUB b,R0SUB c,R1SUB c,R1.8.4 一个简单的代码生成器一个简单的代码生成器8.4.4 为为变址和指针变址和指针语句产生代码语句产生代码变址与指针运算的三地址语句的处理和二元变址与指针运算的三地址语句的处理和二元算符的处理相同算符的处理相同 8.4 一个简单的代码生成器一个简单的代码生成器8.4.
25、5 条件语句条件语句实现条件转移有两种方式实现条件转移有两种方式 根据寄存器的值是否为下面六个条件之一进根据寄存器的值是否为下面六个条件之一进行分支：负、零、正、非负、非零和非正行分支：负、零、正、非负、非零和非正 用条件码来表示计算的结果或装入寄存器的用条件码来表示计算的结果或装入寄存器的值是负、零还是正值是负、零还是正8.4 一个简单的代码生成器一个简单的代码生成器根据寄存器的值是否为下面六个条件之一进行根据寄存器的值是否为下面六个条件之一进行分支：负、零、正、非负、非零和非正分支：负、零、正、非负、非零和非正例如：例如：if x y goto z 把把x减减y的值存入寄存器的值存入寄存器
26、R，如果如果R的值为负，则跳到的值为负，则跳到z 8.4 一个简单的代码生成器一个简单的代码生成器用条件码的例子用条件码的例子if x y goto zx:=y+z的实现：的实现：if x 0 goto zCMP x,y的实现：的实现：CJzMOVy，R0ADDz，R0MOVR0，xCJz本本 章章 要要 点点 代码生成器设计中的主要问题：存储管理、代码生成器设计中的主要问题：存储管理、计算次序的选择、寄存器的分配、指令的选计算次序的选择、寄存器的分配、指令的选择等。择等。目标机器几种常用的地址模式和一些常用的目标机器几种常用的地址模式和一些常用的指令。指令。基本块和程序流图。基本块和程序流图
27、。简单的代码生成算法。简单的代码生成算法。例例 题题 1在在SPARC/SUNOS上，经某编译器编译，程序的结果上，经某编译器编译，程序的结果是是120。把第。把第4行的行的abs(1)改成改成1的话，则程序结果是的话，则程序结果是1int fact()static int i=5;if(i=0)return(1);else i=i-1;return(i+abs(1)*fact();main()printf(factor of 5=%dn,fact();例例 题题 2下面的程序在下面的程序在X86/Linux机器上编译后的运行结机器上编译后的运行结果是果是7，而在，而在SPARC/SUNOS机
28、器上编译后的运机器上编译后的运行结果是行结果是6。试分析运行结果不同的原因。试分析运行结果不同的原因。main()long i;i=0;printf(%ldn,(+i)+(+i)+(+i);例例 题题 2按一般的代码生成，按一般的代码生成，i=i+1的计算结果保留在的计算结果保留在寄存器中，因此这三个寄存器中，因此这三个i=i+1的计算次序不会的计算次序不会影响最终的结果。结果应该是影响最终的结果。结果应该是6。+:=i+i1:=i+i1:=i+i1例例 题题 2按一般的代码生成，按一般的代码生成，i=i+1的计算结果保留在的计算结果保留在寄存器中，因此这三个寄存器中，因此这三个i=i+1的计
29、算次序不会的计算次序不会影响最终的结果。结果应该是影响最终的结果。结果应该是6。结果是结果是7 7的话，一定是的话，一定是某个某个i=i+1的结果未保的结果未保留在寄存器中留在寄存器中。上层上层计算对它的引用落在计算对它的引用落在计算另一个计算另一个i=i+1的的后面后面+:=i+i1:=i+i1:=i+i1例例 题题 2 如果机器有如果机器有INC指令的话，编译器极可能产指令的话，编译器极可能产生一条生一条INC指令来完成指令来完成i=i+1 X86/Linux机器上果真是这么做的机器上果真是这么做的+:=i+i1:=i+i1:=i+i1例例 题题 2将表达式改成将表达式改成(+i)+(+i
30、)+(+i),结果会怎样？结果会怎样？+:=i+i1+:=i+i1:=i+i1例例 题题 2将表达式改成将表达式改成(+i)+(+i)+(+i),结果会怎样？结果会怎样？在在SPARC/SUNOS机器上的结果仍然是机器上的结果仍然是6。在在X86/Linux机器上的结果是机器上的结果是9。+:=i+i1+:=i+i1:=i+i1例例 题题 3下面下面C语言程序如下语言程序如下,运行时输出运行时输出105,为什么？为什么？main()long i;i=10;i=(i+5)+(i=i*5);printf(%dn,i);例例 题题 3下面下面C语言程序如下语言程序如下,运行时输出运行时输出105,为什么？为什么？main()long i;i=10;i=(i+5)+(i=i*5);printf(%dn,i);表达式表达式 表达式表达式 表达式表达式 需需2个个R 需需3个个R 需需几个几个R 习习 题题 第一次：第一次：8.4（只为（只为8.1(e)生成代码）生成代码）
