第八章第八章 代代 码码 生生 成成 本章内容本章内容一个简单的代码生成算法一个简单的代码生成算法涉及存储管理，指令选择，寄存器分配涉及存储管理，指令选择，寄存器分配和计算次序选择和计算次序选择等基本问题等基本问题前端前端代代码码优优化化器器中间中间代码代码源程序源程序代码代码生成生成器器中间中间代码代码目标目标程序程序8.1 代码生成器的设计中的问题代码生成器的设计中的问题8.1.1 目标程序目标程序可执行目标模块可执行目标模块可重定位目标模块可重定位目标模块允许程序模块分别编译允许程序模块分别编译调用其它先前编译好的程序模块调用其它先前编译好的程序模块汇编语言程序汇编语言程序免去编译器重复汇编器的工作免去编译器重复汇编器的工作从教学角度，增加可读性从教学角度，增加可读性8.1 代码生成器的设计中的问题代码生成器的设计中的问题8.1.2 指令的选择指令的选择目标机器指令系统的性质决定了指令选择的目标机器指令系统的性质决定了指令选择的难易程度，指令系统的统一性和完备性是重难易程度，指令系统的统一性和完备性是重要的因素要的因素指令的速度和机器特点是另一些重要的因素指令的速度和机器特点是另一些重要的因素8.1 代码生成器的设计中的问题代码生成器的设计中的问题若不考虑目标程序的效率，指令的选择是直若不考虑目标程序的效率，指令的选择是直截了当的截了当的三地址语句三地址语句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+cd=a+e的代码如下的代码如下MOVb,R0ADDc,R0MOVR0, aMOVa,R0ADDe,R0MOVR0, d8.1 代码生成器的设计中的问题代码生成器的设计中的问题语句序列语句序列 a=b+cd=a+e的代码如下的代码如下MOVb,R0ADDc,R0MOVR0, aMOVa,R0-多余的指令多余的指令ADDe,R0MOVR0, d8.1 代码生成器的设计中的问题代码生成器的设计中的问题语句序列语句序列 a=b+cd=a+e的代码如下的代码如下MOVb,R0ADDc,R0MOVR0, aMOVa,R0-多余的指令多余的指令ADDe,R0-若若a不再使用，第三条也不再使用，第三条也MOVR0, d-多余多余8.1 代码生成器的设计中的问题代码生成器的设计中的问题8.1.3寄存器分配寄存器分配运算对象处于寄存器中的指令通常比运算对运算对象处于寄存器中的指令通常比运算对象处于内存的指令要短一些，执行也快一些象处于内存的指令要短一些，执行也快一些寄存器分配寄存器分配选择驻留在寄存器中的一组变量选择驻留在寄存器中的一组变量寄存器指派寄存器指派挑选变量要驻留的具体寄存器挑选变量要驻留的具体寄存器8.1 代码生成器的设计中的问题代码生成器的设计中的问题8.1.4计算次序的选择计算次序的选择某种计算次序可能会比其它次序需要较少的某种计算次序可能会比其它次序需要较少的寄存器来保存中间结果寄存器来保存中间结果8.2 目目 标标 机机 器器 8.2.1目标机器的指令系统目标机器的指令系统选择可作为几种微机代表的寄存器机器选择可作为几种微机代表的寄存器机器四字节组成一个字，有四字节组成一个字，有n个通用寄存器个通用寄存器R0, ,R1, ,Rn-1。二地址指令二地址指令op 源，目的源，目的MOV源传到目的源传到目的ADD源加到目的源加到目的SUB目的减去源目的减去源8.2 目目 标标 机机 器器 地址模式和它们的汇编语言形式及附加代价地址模式和它们的汇编语言形式及附加代价模式模式形式形式地址地址附加代价附加代价绝对地址绝对地址 MM1寄存器寄存器RR0变址变址c(R)c+contents(R) 1间接寄存器间接寄存器 Rcontents(R)0间接变址间接变址 c(R)contents(c+contents(R)1直接量直接量#cc 18.2 目目 标标 机机 器器 指令实例指令实例MOVR0,MMOV4(R0),Mcontents(4+contents(R0)MOV 4(R0),Mcontents(contents (4+contents(R0)MOV#1,R08.2 目目 标标 机机 器器 8.2.2指令的代价指令的代价指令代价取成指令代价取成1加上它的源和目的地址模式的加上它的源和目的地址模式的附加代价附加代价指令指令代价代价MOVR0，R11MOVR5，M2ADD#1， R32SUB4(R0), 12(R1) 38.2 目目 标标 机机 器器 a=b+c，a、b和和c都静态分配内存单元都静态分配内存单元MOVb,R0ADDc,R0代价代价=6MOVR0,a8.2 目目 标标 机机 器器 a=b+c，a、b和和c都静态分配内存单元都静态分配内存单元MOVb,R0ADDc,R0代价代价=6MOVR0,aMOVb,aADDc,a代价代价=68.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, R0ADD R2, R0代价代价=2若若R1和和R2分别含分别含b和和c的值，并且的值，并且b的值在这个的值在这个赋值后不再需要，则赋值后不再需要，则ADDR2,R1MOVR1,a代价代价=38.3 基本块和流图基本块和流图怎样为三地址语句序列生成目标代码？怎样为三地址语句序列生成目标代码？|(1) prod=0prod=0;|(2) i=1i=1;|(3) t1=4 ido|(4) t2=at1prod=prod+ai bi;|(5) t3=4 ii=i+1;|(6) t4=bt3while(i=20);|(7) t5=t2 t4|(8) t6=prod+t5|(9) prod=t6|(10)t7=i+1|(11) i=t7|(12)ifi=20goto(3)8.3 基本块和流图基本块和流图8.3.1基本块基本块基本块基本块：连续的语句序列，控制流从它的开始：连续的语句序列，控制流从它的开始进入，并从它的末尾离开进入，并从它的末尾离开再用有向边表示基本块之间的控制流信息，就再用有向边表示基本块之间的控制流信息，就能得到程序的流图能得到程序的流图8.3 基本块和流图基本块和流图三地址语句序列的三地址语句序列的划分基本块划分基本块首先确定所有的首先确定所有的入口语句入口语句序列的第一个语句是入口语句序列的第一个语句是入口语句能由条件转移语句或无条件转移语句转到的语句能由条件转移语句或无条件转移语句转到的语句是入口语句是入口语句紧跟在条件转移语句或无条件转移语句后面的语紧跟在条件转移语句或无条件转移语句后面的语句是入口语句句是入口语句每个入口语句每个入口语句到下一个到下一个入口语句之前的语句入口语句之前的语句序列构成一个基本块序列构成一个基本块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) ifi=20goto(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)ifi=20goto(3)B1B28.3 基本块和流图基本块和流图8.3.2基本块的优化基本块的优化三地址语句三地址语句x = y + zx = y + z引用引用y y和和z z并对并对x x定值定值一一个个名名字字的的值值在在基基本本块块的的某某一一点点以以后后还还要要引引用的话，则说这个名字在该点是用的话，则说这个名字在该点是活跃活跃的的基本块的等价基本块的等价两个基本块计算一组同样的表达式两个基本块计算一组同样的表达式这些表达式的值分别代表同样的活跃名字的值这些表达式的值分别代表同样的活跃名字的值有很多等价变换可用于基本块有很多等价变换可用于基本块局部变换局部变换全局变换全局变换8.3 基本块和流图基本块和流图删除局部公共子表达式删除局部公共子表达式a=b+ca=b+cb=a db=a dc=b+cc=b+cd=a dd=b删除死代码删除死代码定值定值x=y+z以后不再引用，以后不再引用，则称则称x为死变量为死变量8.3 基本块和流图基本块和流图交换相邻的独立语句交换相邻的独立语句t1=b+ct2=x+yt2=x+yt1=b+c当且仅当当且仅当t1和和t2不相同不相同，x和和y都不是都不是t1，并且并且b和和c都不是都不是t2代数变换代数变换x=x+0可以删除可以删除x=x 1可以删除可以删除x=y2改成改成x=y y8.3 基本块和流图基本块和流图8.3.3流图流图把把控控制制流流信信息息加加到到基基本本块块集集合合，形形成成一一个个有有向图来表示程序向图来表示程序首结点首结点、前前驱、后继、后继8.3 基本块和流图基本块和流图什么是循环什么是循环?所有结点是所有结点是强连通强连通的的唯一的循环唯一的循环入口入口外循环和内循环外循环和内循环prod=0i=1t1=4 it2=at1t3=4 it4=bt3t5=t2 t4t6=prod+t5prod=t6t7=i+1i=t7ifi=20gotoB2B1B28.3 基本块和流图基本块和流图8.3.4下次引用信息下次引用信息为为每每个个三三地地址址语语句句x=yopz决决定定x、y和和z的的下下次引用信息次引用信息i: x=yopz.没有对没有对x的赋值的赋值j: =x.没有对没有对x的赋值的赋值k: =x8.3 基本块和流图基本块和流图8.3.4下次引用信息下次引用信息为为每每个个三三地地址址语语句句x=yopz决决定定x、y和和z的的下下次引用信息次引用信息i: x=yopz.没有对没有对x的赋值的赋值j: =x.没有对没有对x的赋值的赋值k: =x8.3 基本块和流图基本块和流图对每个基本块从最后一个语句反向扫描到第对每个基本块从最后一个语句反向扫描到第一个语句一个语句，可以得到下次引用信息，可以得到下次引用信息i: x=yopz.没有对没有对x的赋值的赋值j: =x.没有对没有对x的赋值的赋值k: =x8.3 基本块和流图基本块和流图对每个基本块从最后一个语句反向扫描到第对每个基本块从最后一个语句反向扫描到第一个语句一个语句，可以得到下次引用信息，可以得到下次引用信息i: x=yopz.没有对没有对x的赋值的赋值j: =x.没有对没有对x的赋值的赋值k: =x利利用用下下次次引引用用信信息息，可可以以压压缩缩临临时时变变量量需需要要的空间的空间8.4 一个简单的代码生成器一个简单的代码生成器依次考虑基本块的每个语句，为其产生代码依次考虑基本块的每个语句，为其产生代码假假定定三三地地址址语语句句的的每每种种算算符符都都有有对对应应的的目目标标机器算符机器算符假定计算结果留在寄存器中尽可能长的时间假定计算结果留在寄存器中尽可能长的时间, ,除非：除非：该寄存器要用于其它计算该寄存器要用于其它计算，或者，或者到基本块结束到基本块结束8.4 一个简单的代码生成器一个简单的代码生成器在没有收集全局信息在没有收集全局信息前，暂且以基本块为前，暂且以基本块为单位来生成代码单位来生成代码prod=0i=1t1=4 it2=at1t3=4 it4=bt3t5=t2 t4t6=prod+t5prod=t6t7=i+1i=t7ifi=20gotoB2B1B28.4 一个简单的代码生成器一个简单的代码生成器8.4.1寄存器描述和地址描述寄存器描述和地址描述例：对例：对a=b+c如果寄存器如果寄存器Ri含含b，Rj含含c，且且b此后不再活跃此后不再活跃产生产生ADDRj,Ri，结果结果a在在Ri中中如果如果Ri含含b，但但c在内存单元在内存单元，b仍然不再活跃仍然不再活跃产生产生ADDc,Ri，或者或者MOVc,RjADDRj,Ri若若c的值以后还要用的值以后还要用, ,第二种代码比较有吸引力第二种代码比较有吸引力8.4 一个简单的代码生成器一个简单的代码生成器在代码生成过程中，需要跟踪寄存器的内容和在代码生成过程中，需要跟踪寄存器的内容和名字的地址名字的地址寄存器描述记住每个寄存器当前存的是什么寄存器描述记住每个寄存器当前存的是什么在在任任何何一一点点，每每个个寄寄存存器器保保存存若若干干个个( (包包括括零零个个) )名字的值名字的值名名字字的的地地址址描描述述记记住住运运行行时时每每个个名名字字的的当当前前值可以在哪个场所找到值可以在哪个场所找到这这个个场场所所可可以以是是寄寄存存器器、栈栈单单元元、内内存存地地址址、甚甚至是它们的某个集合至是它们的某个集合这些信息可以存于符号表中这些信息可以存于符号表中这两个描述在代码生成过程中是变化的这两个描述在代码生成过程中是变化的8.4 一个简单的代码生成器一个简单的代码生成器8.4.2 代码生成算法代码生成算法对每个三地址语句对每个三地址语句x=yopz调用函数调用函数getreg决定放决定放y op z计算结果的场所计算结果的场所L查查看看y的的地地址址描描述述, ,确确定定y值值当当前前的的一一个个场场所所y .如如果果y的的值值还还不不在在L中中，产产生生指指令令MOVy ，L产产生生指指令令opz ，L，其其中中z 是是z的的当当前前场场所所之一之一如如果果y和和/ /或或z的的当当前前值值不不再再引引用用，在在块块的的出出口口也也不不活活跃跃，并并且且还还在在寄寄存存器器中中，那那么么修修改改寄寄存器描述存器描述8.4 一个简单的代码生成器一个简单的代码生成器8.4.3 寄存器选择函数寄存器选择函数函数函数getreg返回保存返回保存x=yopz的的x值的场所值的场所L如如果果名名字字y在在R中中，这这个个R不不含含其其它它名名字字的的值值, ,并并且且在在执执行行x=yopz后后y不不再再有有下下次次引引用用，那那么么返返回回这这个个R作为作为L否则，返回一个空闲寄存器，如果有的话否则，返回一个空闲寄存器，如果有的话否否则则，如如果果x在在块块中中有有下下次次引引用用，或或者者op是是必必须须用用寄寄存存器器的的算算符符，那那么么找找一一个个已已被被占占用用的的寄寄存存器器R(可能产生可能产生MOVR，M指令，并修改指令，并修改M的描述的描述)否否则则，如如果果x在在基基本本块块中中不不再再引引用用，或或者者找找不不到到适当的被占用寄存器，选择适当的被占用寄存器，选择x的内存单元作为的内存单元作为L8.4 一个简单的代码生成器一个简单的代码生成器赋值语句赋值语句d=(a b)+(a c)+(a c)编译产生三地址语句序列：编译产生三地址语句序列：t1=a bt2=a ct3=t1+t2d=t3+t2 8.4 一个简单的代码生成器一个简单的代码生成器语语句句 生成的代码生成的代码 寄存器描述寄存器描述 名字地址描述名字地址描述 寄存器空寄存器空 t1=a b MOVa,R0SUBb,R0 R0含含t1 t1在在R0中中 t2=a cMOVa,R1SUBc,R1R0含含t1R1含含t2t1在在R0中中t2在在R1中中t3=t1+t2 ADDR1,R0 R0含含t3R1含含t2t3在在R0中中t2在在R1中中 d=t3+t2 ADDR1,R0 R0含含dd在在R0中中 MOVR0,d d在在R0和和内内存存中中8.4 一个简单的代码生成器一个简单的代码生成器前三条指令可以修改，使执行代价降低前三条指令可以修改，使执行代价降低MOVa,R0MOVa,R0SUBb,R0MOVR0，R1MOVa,R1SUBb,R0SUBc,R1SUBc,R1.8.4 一个简单的代码生成器一个简单的代码生成器8.4.4 为为变址和指针变址和指针语句产生代码语句产生代码变变址址与与指指针针运运算算的的三三地地址址语语句句的的处处理理和和二二元元算符的处理相同算符的处理相同 8.4 一个简单的代码生成器一个简单的代码生成器8.4.5 条件语句条件语句实现条件转移有两种方式实现条件转移有两种方式根根据据寄寄存存器器的的值值是是否否为为下下面面六六个个条条件件之之一一进进行分支：负、零、正、非负、非零和非正行分支：负、零、正、非负、非零和非正用用条条件件码码来来表表示示计计算算的的结结果果或或装装入入寄寄存存器器的的值是负、零还是正值是负、零还是正8.4 一个简单的代码生成器一个简单的代码生成器根据寄存器的值是否为下面六个条件之一进行根据寄存器的值是否为下面六个条件之一进行分支：负、零、正、非负、非零和非正分支：负、零、正、非负、非零和非正例如：例如：ifxygotoz把把x减减y的值存入寄存器的值存入寄存器R如果如果R的值为负，则跳到的值为负，则跳到z8.4 一个简单的代码生成器一个简单的代码生成器用条件码的例子用条件码的例子ifxygotozx=y+w的实现：的实现：ifx0gotozCMPx,y的实现：的实现：CJzMOVy， R0ADDw， R0MOVR0，xCJz本本章章要要点点代代码码生生成成器器设设计计中中的的主主要要问问题题：存存储储管管理理、计计算算次次序序的的选选择择、寄寄存存器器的的分分配配、指指令令的的选选择等择等目目标标机机器器几几种种常常用用的的地地址址模模式式和和一一些些常常用用的的指令指令基本块和程序流图基本块和程序流图简单的代码生成算法简单的代码生成算法例例 题题 1在在SPARC/SUNOS上，经某编译器编译，程序的结果上，经某编译器编译，程序的结果是是120。把第。把第4行的行的abs(1)改成改成1的话，则程序结果是的话，则程序结果是1intfact()staticinti=5;if(i=0)return(1);elsei=i-1;return(i+abs(1) fact();main()printf(factorof5=%dn,fact();例例 题题 2下面的程序在下面的程序在X86/Linux机器上编译后的运行结机器上编译后的运行结果是果是7，而在，而在SPARC/SUNOS机器上编译后的运机器上编译后的运行结果是行结果是6。试分析运行结果不同的原因。试分析运行结果不同的原因。main()longi;i=0;printf(%ldn,(+i)+(+i)+(+i);例例 题题 2按一般的代码生成，按一般的代码生成，i=i+1的计算结果保留在的计算结果保留在寄存器中，因此这三个寄存器中，因此这三个i=i+1的计算次序不会的计算次序不会影响最终的结果。结果应该是影响最终的结果。结果应该是6。+=ii+1ii+1ii+1例例 题题 2按一般的代码生成，按一般的代码生成，i=i+1的计算结果保留在的计算结果保留在寄存器中，因此这三个寄存器中，因此这三个i=i+1的计算次序不会的计算次序不会影响最终的结果。结果应该是影响最终的结果。结果应该是6。结果是结果是7的话，一定是的话，一定是某个某个i=i+1的结果未保的结果未保留在寄存器中留在寄存器中。上层上层计算对它的引用落在计算对它的引用落在计算另一个计算另一个i=i+1的的后面后面+=ii+1ii+1ii+1例例 题题 2如果机器有如果机器有INC指令的话，编译器极可能产生指令的话，编译器极可能产生一条一条INC指令来完成指令来完成i=i+1X86/Linux机器上果真是这么做的机器上果真是这么做的+=ii+1ii+1ii+1例例 题题 2将表达式改成将表达式改成(+i)+(+i)+(+i),结果会怎样？结果会怎样？+=ii+1ii+1ii+1例例 题题 2将表达式改成将表达式改成(+i)+(+i)+(+i),结果会怎样？结果会怎样？在在SPARC/SUNOS机器上的结果仍然是机器上的结果仍然是6。在在X86/Linux机器上的结果是机器上的结果是9。+=ii+1ii+1ii+1例例 题题 3下面下面C语言程序如下语言程序如下,运行时输出运行时输出105,为什么？为什么？main()longi;i=10;i=(i+5)+(i=i 5);printf(%dn,i);例例 题题 3下面下面C语言程序如下语言程序如下,运行时输出运行时输出105,为什么？为什么？main()longi;i=10;i=(i+5)+(i=i 5);printf(%dn,i);二元运算二元运算表达式表达式表达式表达式需需2个个R需需3个个R需需几个几个R例例 题题 4下下面面是是一一个个C语语言言程程序序和和在在X86/Linux机机器器上上编编译译（未未使使用用优优化化）该该程程序序得得到到的的汇汇编编代代码码见见下下页页（为为便便于于理理解解，略略去去了了和和讨讨论论本本问问题题无关的部分，并改动了一个地方）无关的部分，并改动了一个地方）main()longi,j;if(j)i+;elsewhile(i)j+;例例 题题 4main()incl-4(%ebp) jmp.L3 longi,j;.L2:.L4:(写在一行以省空间写在一行以省空间)if(j)cmpl$0,-4(%ebp)i+;jne.L6elsejmp.L5while(i)j+;.L6:incl-8(%ebp) pushl%ebp jmp.L4 movl%esp,%ebp .L5:.L3:.L1:subl$8,%esp leave cmpl$0,-8(%ebp) ret je.L2 例例 题题 4为什么会出现一条指令前有多个标号的情况，如为什么会出现一条指令前有多个标号的情况，如.L2和和.L4，还有，还有.L5、.L3和和.L1？从控制流语句的中间代？从控制流语句的中间代码结构加以解释。码结构加以解释。条件语句和循环语句的中间代码结构如下：条件语句和循环语句的中间代码结构如下：if(E)thenS1elseS2while(E)doSE的代码的代码L4:E的代码的代码假转假转L2真转真转L6S1的代码的代码转转L5转转L3L6:S的代码的代码L2:S2的代码的代码转转L4L3:L5:当当while语句作为条件语句的语句作为条件语句的S2时，会出现所说情况时，会出现所说情况例例 题题 4每个函数都有这样的标号每个函数都有这样的标号.L1，它的作用是什，它的作用是什么，为什么本函数没有引用该标号的地方？么，为什么本函数没有引用该标号的地方？例例 题题 4每个函数都有这样的标号每个函数都有这样的标号.L1，它的作用是什，它的作用是什么，为什么本函数没有引用该标号的地方？么，为什么本函数没有引用该标号的地方？.L1标号定义的入口是返回调用者时该执行的标号定义的入口是返回调用者时该执行的指令，在函数内部有指令，在函数内部有return语句时就会跳转到语句时就会跳转到.L1。 习习题题第一次：第一次：8.4（只为（只为8.1(e)生成代码）生成代码）