编译原理_目标代码生成（PDF58页）

第11章代码生成本章内容• 一个简单的代码生成算法• 涉及存储管理，指令选择，寄存器分配和计算次序选择等基本问题前端代码优化器中间代码源程序代码生成器中间代码目标程序11.1代码生成器的设计中的问题11.1.1目标程序• 可执行目标模块• 可重定位目标模块– 允许程序模块分别编译– 调用其它先前编译好的程序模块• 汇编语言程序– 免去编译器重复汇编器的工作– 从教学角度，增加可读性11.1代码生成器的设计中的问题11.1.2指令的选择目标机器指令系统的性质决定了指令选择的难易程度，指令系统的统一性和完备性是重要的因素指令的速度和机器特点是另一些重要的因素11.1代码生成器的设计中的问题若不考虑目标程序的效率，指令的选择是直截了当的。三地址语句x:=y+z（x，y和z都是静态分配）MOVy,R0/*把y装入寄存器R0*/ADDz,R0/*z加到R0上*/MOVR0,x/*把R0存入x中*/11.1代码生成器的设计中的问题逐个语句地产生代码，常常得到低质量的代码语句序列a:=b+c的代码如下d:=a+eMOVb,R0ADDc,R0MOVR0,aMOVa,R0ADDe,R0MOVR0,d11.1代码生成器的设计中的问题语句序列a:=b+cd:=a+e的代码如下MOVb,R0ADDc,R0MOVR0,aMOVa,R0--多余的指令ADDe,R0MOVR0,d11.1代码生成器的设计中的问题语句序列a:=b+cd:=a+e的代码如下MOVb,R0ADDc,R0MOVR0,aMOVa,R0--多余的指令ADDe,R0--若a不再使用，第三条也MOVR0,d--多余11.1代码生成器的设计中的问题11.1.3寄存器分配运算对象处于寄存器中的指令通常比运算对象处于内存的指令要短一些，执行也快一些• 寄存器分配选择驻留在寄存器中的一组变量• 寄存器指派挑选变量要驻留的具体寄存器11.1代码生成器的设计中的问题11.1.4计算次序的选择某种计算次序可能会比其它次序需要较少的寄存器来保存中间结果11.2目标机器11.2.1目标机器的指令系统选择可作为几种微机代表的寄存器机器四字节组成一个字，有n个通用寄存器R0,R1,…,Rn-1。二地址指令op源，目的MOV{源传到目的}ADD{源加到目的}SUB{目的减去源}11.2目标机器地址模式和它们的汇编语言形式及附加代价模式形式地址附加代价绝对地址MM1寄存器RR0变址c(R)c+contents(R)1间接寄存器*Rcontents(R)0间接变址*c(R)contents(c+contents(R))1直接量#cc111.2目标机器指令实例MOVR0,MMOV4(R0),Mcontents(4+contents(R0))MOV*4(R0),Mcontents(contents(4+contents(R0)))MOV#1,R011.2目标机器11.2.2指令的代价指令代价取成1加上它的源和目的地址模式的附加代价指令代价MOVR0，R11MOVR5，M2ADD#1，R32SUB4(R0),*12(R1)311.2目标机器a:=b+c，a、b和c都静态分配内存单元MOVb,R0ADDc,R0代价=6MOVR0,a11.2目标机器a:=b+c，a、b和c都静态分配内存单元MOVb,R0ADDc,R0代价=6MOVR0,aMOVb,aADDc,a代价=611.2目标机器a:=b+c，a、b和c都静态分配内存单元若R0，R1和R2分别含a，b和c的地址，则MOV*R1,*R0ADD*R2,*R0代价=211.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代价=311.3基本块和流图怎样为三地址语句序列生成目标代码？begin|(1)prod:=0prod:=0;|(2)i:=1i:=1;|(3)t1:=4*idobegin|(4)t2:=a[t1]prod:=prod+a[i]*b[i];|(5)t3:=4*ii:=i+1|(6)t4:=b[t3]endwhilei=20|(7)t5:=t2*t4end|(8)t6:=prod+t5|(9)prod:=t6|(10)t7:=i+1|(11)i:=t7|(12)ifi=20goto(3)11.3基本块和流图11.3.1基本块基本块：连续的语句序列，控制流从它的开始进入，并从它的末尾离开再用有向边表示基本块之间的控制流信息，就能得到程序的流图11.3基本块和流图三地址语句序列的划分基本块• 首先确定所有的入口语句– 序列的第一个语句是入口语句– 能由条件转移语句或无条件转移语句转到的语句是入口语句– 紧跟在条件转移语句或无条件转移语句后面的语句是入口语句• 每个入口语句到下一个入口语句之前的语句序列构成一个基本块11.3基本块和流图(1)prod:=0(2)i:=1(3)t1:=4*i(4)t2:=a[t1](5)t3:=4*i(6)t4:=b[t3](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:=a[t1](5)t3:=4*I(6)t4:=b[t3](7)t5:=t2*t4(8)t6:=prod+t5(9)prod:=t6(10)t7:=i+1(11)i:=t7(12)ifi=20goto(3)B1B211.3基本块和流图11.3.2基本块的变换• 三地址语句x:=y+z引用y和z并对x定值• 一个名字的值在基本块的某一点以后还要引用的话，我们说这个名字在该点是活跃的• 基本块的等价– 两个基本块计算一组同样的表达式– 这些表达式的值分别代表同样的活跃名字的值• 有很多等价变换可用于基本块– 局部变换– 全局变换11.3基本块和流图• 删除局部公共子表达式a:=b+ca:=b+cb:=a-db:=a-dc:=b+cc:=b+cd:=a-dd:=b• 删除死代码定值x:=y+z以后不再引用，则称x为死变量11.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:=y**2改成x:=y*y11.3基本块和流图11.3.3流图把控制流信息加到基本块集合，形成一个有向图来表示程序首结点、前驱、后继11.3基本块和流图• 什么是循环?– 所有结点是强连通的– 唯一的循环入口• 外循环和内循环prod:=0i:=1t1:=4*it2:=a[t1]t3:=4*It4:=b[t3]t5:=t2*t4t6:=prod+t5prod:=t6t7:=i+1i:=t7ifi=20gotoB2B1B211.3基本块和流图11.3.4下次引用信息为每个三地址语句x:=yopz决定x、y和z的下次引用信息i:x:=yopz...--没有对x的赋值j:…:=x…...--没有对x的赋值k:…:=…x11.3基本块和流图11.3.4下次引用信息为每个三地址语句x:=yopz决定x、y和z的下次引用信息i:x:=yopz...--没有对x的赋值j:…:=x…...--没有对x的赋值k:…:=…x11.3基本块和流图• 对每个基本块从最后一个语句反向扫描到第一个语句，可以得到下次引用信息i:x:=yopz...--没有对x的赋值j:…:=x…...--没有对x的赋值k:…:=…x11.3基本块和流图• 对每个基本块从最后一个语句反向扫描到第一个语句，可以得到下次引用信息i:x:=yopz...--没有对x的赋值j:…:=x…...--没有对x的赋值k:…:=…x• 利用下次引用信息，可以压缩临时变量需要的空间11.4一个简单的代码生成器• 依次考虑基本块的每个语句，为其产生代码• 假定三地址语句的每种算符都有对应的目标机器算符• 假定计算结果留在寄存器中尽可能长的时间,除非：– 该寄存器要用于其它计算，或者– 到基本块结束11.4一个简单的代码生成器在没有收集全局信息前，暂且以基本块为单位来生成代码prod:=0i:=1t1:=4*it2:=a[t1]t3:=4*It4:=b[t3]t5:=t2*t4t6:=prod+t5prod:=t6t7:=i+1i:=t7ifi=20gotoB2B1B211.4一个简单的代码生成器11.4.1寄存器描述和地址描述例：对a:=b+c• 如果寄存器Ri含b，Rj含c，且b此后不再活跃– 产生ADDRj,Ri，结果a在Ri中• 如果Ri含b，但c在内存单元，b仍然不再活跃– 产生ADDc,Ri，或者– MOVc,RjADDRj,Ri若c的值以后还要用,第二种代码比较有吸引力11.4一个简单的代码生成器在代码生成过程中，需要跟踪寄存器的内容和名字的地址• 寄存器描述记住每个寄存器当前存的是什么– 在任何一点，每个寄存器保存若干个(包括零个)名字的值• 名字的地址描述记住运行时每个名字的当前值可以在哪个场所找到– 这个场所可以是寄存器、栈单元、内存地址、甚至是它们的某个集合– 这些信息可以存于符号表中• 这两个描述在代码生成过程中是变化的。11.4一个简单的代码生成器11.4.2代码生成算法对每个三地址语句x:=yopz• 调用函数getreg决定放yopz计算结果的场所L• 查看y的地址描述,确定y值当前的一个场所yʹ.如果y的值还不在L中，产生指令MOVyʹ，L• 产生指令opzʹ，L，其中zʹ是z的当前场所之一• 如果y和/或z的当前值不再引用，在块的出口也不活跃，并且还在寄存器中，那么修改寄存器描述11.4一个简单的代码生成器11.4.3寄存器选择函数函数getreg返回保存x:=yopz的x值的场所L– 如果名字y在R中，这个R不含其它名字的值,并且在执行x:=yopz后y不再有下次引用，那么返回这个R作为L。– 否则，返回一个空闲寄存器，如果有的话– 否则，如果x在块中有下次引用，或者op是必须用寄存器的算符，那么找一个已被占用的寄存器R(可能产生MOVR，M指令，并修改M的描述)– 否则，如果x在基本块中不再引用，或者找不到适当的被占用寄存器，选择x的内存单元作为L。11.4一个简单的代码生成器赋值语句d:=(a-b)+(a-c)+(a-c)编译产生三地址语句序列：t1:=a-bt2:=a-ct3:=t1+t2d:=t3+t211.4一个简单的代码生成器语句生成的代码寄存器描述名字地址描述寄存器空t1:=a-bMOVa,R0SUBb,R0R0含t1t1在R0中t2:=a-cMOVa,R1SUBc,R1R0含t1R1含t2t1在R0中t2在R1中t3:=t1+t2ADDR1,R0R0含t3R1含t2t3在R0中t2在R1中d:=t3+t2ADDR1,R0R0含dd在R0中MOVR0,dd在R0和内存中11.4一个简单的代码生成器前三条指令可以修改，使执行代价降低MOVa,R0MOVa,R0SUBb,R0MOVR0，R1MOVa,R1SUBb,R0SUBc,R1SUBc,R1......11.4一个简单的代码生成器11.4.4为变址和指针语句产生代码变址与指针运算的三地址语句的处理和二元算符的处理相同11.4一个简单的代码生成器11.4.5条件语句实现条件转移有两种方式• 根据寄存器的值是否为下面六个条件之一进行分支：负、零、正、非负、非零和非正• 用条件码来表示计算的结果或装入寄存器的值是负、零还是正11.4一个简单的代码生成器根据寄存器的值是否为下面六个条件之一进行分支：负、零、正、非负、非零和非正例如：ifxygotoz• 把x减y的值存入寄存器R，• 如果R的值为负，则跳到z11.4一个简单的代码生成器用条件码的