编译原理讲义课件8

§8目标代码生成学时：6知识点：涉及的问题

基本块、程序流图下次引用信息代码生成算法1§8目标代码生成学时：61§8目标代码生成目标代码生成程序的任务将前端产生的中间代码转换为等价的目标代码对目标代码生成器的要求：正确高质量1.有效地利用目标机器的资源2.所生成的目标代码应高效地运行本章目标：介绍一个简单的代码生成器算法产生最优化代码问题是不可判定的，实践中能够产生好的（虽不是最优的）代码的启发式技术就很令人满意了2§8目标代码生成目标代码生成程序的任务1.有效地利用目本章主要内容8.1代码生成器设计中的问题8.2目标机器8.3运行时的存储管理8.4基本块和流图8.5下次引用信息8.6简单的代码生成器小结作业3本章主要内容8.1代码生成器设计中的问题38.1代码生成器设计中的问题代码生成器的具体细节依赖于目标机器和操作系统所有的代码生成器固有的问题代码生成器的输入代码生成器的输出存储管理指令选择寄存器分配计算顺序选择代码生成器的设计48.1代码生成器设计中的问题代码生成器的具体细节依赖于目一、代码生成器的输入中间代码经过语法分析、语义检查之后得到的正确的符号表记录了与名字有关的信息决定中间表示中的名字所代表的数据对象的运行地址假定：前期工作结果正确、可信中间代码足够详细必要的类型转换符已正确插入明显的语义错误已经发现、且正确恢复5一、代码生成器的输入中间代码5二、代码生成器的输出目标代码形式绝对机器代码可把代码放在内存中固定的地方、立即执行可重定位机器代码.obj（DOS）、.o（UNIX）开发灵活，允许各子模块单独编译需要由连接装配程序将它们连接在一起，生成可执行文件汇编代码代码生成过程容易，但需要汇编6二、代码生成器的输出目标代码6三、存储管理从名字到存储单元的映射由前端和代码生成器共同完成三地址代码中的名字指向该名字在符号表中位置的指针符号表中的信息在处理声明语句时填入“类型”决定了它的域宽“地址”确定该名字在过程的数据区域中的相对位置上述信息用于确定中间代码中的名字对应的数据对象在运行时的地址生成机器代码时，指令地址通过计数器来实现7三、存储管理从名字到存储单元的映射由前端和代码生成器共同完成例如：中间代码与目标代码的对应对于四元式j：gotoii<ji>j目标代码...0n四元式100的机器码四元式地址长度...100(，，，)101(，，，)102(，，，)103(，，，)...n1212n+12n+12四元式101的机器码88n+20n+20四元式102的机器码1616n+36n+36四元式103的机器码44n+40...将四元式j的地址记入与i相关的链表中，等待回填四元式i的地址已有，可以直接生成机器指令8例如：中间代码与目标代码的对应对于四元式j：gotoi目标四、指令选择机器指令系统的性质决定了指令选择的难易程度代码质量取决于它的执行速度和长度对每一类三地址语句，可以设计它的代码框架如：x:=y+z的代码框架可以是：MOVy,R0ADDz,R0MOVR0,xa:=b+cd:=a+ea:=a+1MOVb,R0ADDc,R0MOVR0,aMOVa,R0ADDe,R0MOVR0,dMOVa,R0ADD#1,R0MOVR0,aINCa9四、指令选择机器指令系统的性质决定了指令选择的难易程度a:=五、寄存器分配充分利用寄存器可以生成好的代码寄存器使用的两个问题哪些变量要放在寄存器中指定的变量放在哪个寄存器中寄存器指派的困难可用寄存器专用寄存器通用寄存器寄存器对把寄存器指派给相应的变量变量需要什么样的寄存器操作需要什么样的寄存器选择最优的寄存器指派方案是一个NP完全问题10五、寄存器分配充分利用寄存器可以生成好的代码10六、计算顺序的选择计算顺序影响目标代码的效率选择最佳计算次序是一个NP完全问题七、代码生成器的设计设计原则能够正确地生成代码易于实现、便于测试和维护只介绍一个简单的代码生成算法主要考虑寄存器的有效使用11六、计算顺序的选择计算顺序影响目标代码的效率七、代码生成器的8.2目标机器设计代码生成器的必要条件：熟悉目标机器一般信息编址方式：按字节编址每个字有4个字节寄存器：n个通用寄存器：R0、R1、Rn-1指令形式：OPS,D其中OP：MOV、ADD、SUBS：源操作数D：目的操作数128.2目标机器设计代码生成器的必要条件：熟悉目标机器12寻址方式地址形式汇编方式地址占用存储空间

绝对地址MM1寄存器RR0

变址c(R)c+contents(R)1间接寄存器*Rcontents(R)0

间接变址*c(R)contents(c+contents(R))1立即数#c常数c1指令代价指令所占用存储单元字数=1+S寻址方式占用字数+D寻址方式占用字数13寻址方式地址形式汇编方式地址举例MOVR0，R1将寄存器R0的内容复制到R1中代价：1MOVR5，M将寄存器R5的内容放到存储单元M中代价：2ADD#1，R3将寄存器R3的内容增加1代价：2SUB4(R0)，*12(R1)将地址为(contents(12+contents(R1))的单元中的值减去contents(4+contents(R0))，结果仍存放到地址为(contents(12+contents(R1))的单元中。代价：314举例MOVR0，R114三地址语句a:=b+c的代码(1)MOVb,R0ADDc,R0指令代价为6MOVR0,a(2)MOVb,aADDc,a指令代价为6(3)假定R0、R1和R2中分别存放了a、b和c的地址：MOV*R1,*R0ADD*R2,*R0指令代价为2(4)假定R1和R2中分别包含b和c的值，b的值以后不再需要：ADDR2,R1MOVR1,a指令代价为315三地址语句a:=b+c的代码(1)MOVb,R0过程的语义决定了运行时名字如何与存储单元相联系。存储分配策略静态存储分配存储器中活动记录的位置在编译时刻已经确定栈式存储分配当开始执行一个过程时，一个新的活动记录压入栈顶当该过程的活动结束时，其活动记录从栈中弹出活动记录的内容参数、返回值控制链、访问链、机器状态局部数据、临时变量8.3运行时的存储管理活动记录的分配和释放是调用序列和返回序列的一部分讨论三地址语句

callreturnhaltaction16过程的语义决定了运行时名字如何与存储单元相联系。8.3运静态存储分配情况三地址代码：/*S的代码*/action1callpaction2halt/*P的代码*/action3returnS的活动记录(64字节)：045660返回地址arrijP的活动记录(88字节)：04返回地址buf84n17静态存储分配情况三地址代码：/*S的代码*//*P的代三地址语句call的目标机器指令：MOV指令：存放返回地址GOTO指令：将控制转移到被调用过程的目标代码

MOV#here+20,callee.static_areaGOTOcallee.code_areahere：该MOV指令的地址20：call的机器指令的代价#here+20：返回地址被调用过程活动记录的开始地址被调用过程代码的第一条指令地址三地址语句return的目标机器指令：GOTO*callee.static_area代码结构18三地址语句call的目标机器指令：here：该MOV指令的地静态存储分配举例100:action1120:MOV#140,364 132:GOTO200 140:action2160:HALT… 200:action3220:GOTO*364… 300: 304: …364: 368: …保存返回地址调用过程P返回到364存储单元里存放的地址S的代码：P的代码：S的活动记录：(300-363)P的活动记录：(364-451)返回地址单元返回地址单元局部数据单元局部数据单元140返回地址19静态存储分配举例100:action1保存返回地址栈式存储分配情况活动记录分配在栈中活动记录在栈中的位置，直到运行时才能确定这个位置常被存放在一个寄存器中寄存器SP保存指向栈顶活动记录开始位置的指针当发生过程调用时，调用过程给SP一个增量，使之指向被调用过程的活动记录的开始位置，同时将控制转移到被调用过程；当控制返回到调用过程时，再将SP减去原来的增量，从而释放了被调用过程的活动记录。20栈式存储分配情况活动记录分配在栈中20代码结构主程序的代码MOV#stackstart,SP第一个过程的代码HALT初始化控制栈三地址语句call的机器代码ADD#caller.recordsize,SPMOV#here+16,SPGOTOcallee.code_areaSP指向下一个活动记录三地址语句return的机器代码GOTO*0(SP)SUB#caller.recordsize,SP间接变址，返回调用过程该指令在被调用过程的代码中SP指回调用过程的活动记录该指令在调用过程的代码中21代码结构主程序的代码初始化控制栈三地址语句call的机器代码程序说明三地址代码：/*S的代码*/action1callqaction2halt/*P的代码*/action3return/*q的代码*/action4callpaction5callqaction6callqreturn各过程目标代码的起址：s：#100p：#200q：#300活动记录的大小：ssize=20psize=40qsize=60控制栈的开始位置：#60022程序说明三地址代码：/*S的代码*//*P的代码*//*q的100:MOV#600,SP108:action1128:ADD#ssize,SP136:MOV#152,*SP144:GOTO300152:SUB#ssize,SP160:action2180:HALT… 200:action3220:GOTO*0(SP)… 栈式存储分配举例300:action4320:ADD#qsize,SP328:MOV#344,*SP336:GOTO200344:SUB#qsize,SP352:action5372:ADD#qsize,SP380:MOV#396,*SP388:GOTO300396:SUB#qsize,SP404:action6424:ADD#qsize,SP432:MOV#448,*SP440:GOTO300448:SUB#qsize,SP456:GOTO*0(SP)… 600: SPq初始化栈callqcallpreturncallqcallqreturn23100:MOV#600,SP栈式存储分配举例30程序执行及栈的变化情况SP=600SS的活动记录20callqSP=620返回地址152q的活动记录60qcallpSP=680p的活动记录40返回地址344preturn返回地址344SP=620p的活动记录40callqSP=680q的活动记录60返回地址396qreturn返回地址396SP=620q的活动记录60callqSP=680q的活动记录60返回地址448qreturn返回地址448SP=620q的活动记录60return返回地址152SP=600q的活动记录60haltS的活动记录2024程序执行及栈的变化情况SP=600SS的活动记录20call运行时名字的地址假定三地址语句为：x:=0静态存储分配情况静态数据区的基址：staticx在数据区中的位置是12x的实际地址应为：static+12尽管在编译时可确定static+12的值，但在生成中间代码时，static的值可能并不知道。这样，必须生成相应的三地址代码以“计算”static+12的值。赋值语句x:=0

被翻译为如下三地址代码：static[12]:=0若static=100，则相应的目标代码为：MOV#0,11225运行时名字的地址假定三地址语句为：x:=0尽管在编译时可确定用display表存取非局部名字，该表存放在寄存器中x局部于一个活动记录，该活动记录的display表指针在寄存器R3中将语句x:=0翻译成为如下三地址语句：

t1:=12+R3*t1:=0栈式存储分配情况t1中存放的是x的地址这个序列可由如下机器指令来实现：MOV#0,12(R3)26用display表存取非局部名字，该表存放在寄存器中栈式存储8.4基本块和流图基本块具有原子性的一组连续语句序列。控制从第一条语句流入，从最后一条语句流出，中途没有停止或分支（末尾除外）划分基本块的方法确定入口语句三地址代码的第一条语句条件/无条件语句转移到的语句紧跟在条件/无条件语句后面的语句确定基本块从一个入口语句（含该语句）到下一个入口语句（不含）从一个入口语句（含该语句）到停止语句（含该语句）278.4基本块和流图基本块27举例基本块：t1:=a*at2:=a*bt3:=2*t2t4:=t1+t3t5:=b*bt6:=t4+t5(1)i:=m-1(2)j:=n(3)t1:=4*n(4)v:=a[t1](5)i:=i+1(6)t2:=4*i(7)t3:=a[t2](8)ift3<vgoto(5)(9)j:=j-1(10)t4:=4*j(11)t5:=a[t4](12)ift5>vgoto(9)(13)ifi>=jgoto(23)(14)t6:=4*i(15)x:=a[t6](16)t7:=4*i(17)t8:=4*j(18)t9:=a[t8](19)a[t7]:=t9(20)t10:=4*j(21)a[t10]:=x(22)goto(5)(23)t11:=4*i(24)x:=a[t11](25)t12:=4*i(26)t13:=4*n(27)t14:=a[t13](28)a[t12]:=t14(29)t15:=4*n(30)a[t15]:=x基本块划分：B1B2B3B4B5B628举例基本块：(1)i:=m-1(14)流图定义：把控制流信息加到基本块集合中，形成程序的有向图，称为流图（控制流图）构造：流图的结点是基本块如果一个结点基本块的入口语句是程序的第一条语句，则称此基本块结点为首结点。如果在某个执行序列中，基本块B2紧跟在基本块B1之后执行，则从B1到B2有一条有向边，B1是B2的前驱，B2是B1的后继。即如果：有一个条件/无条件转移语句从B1的最后一条语句转移到B2的第一条语句；B1的最后一条语句不是无条件转移语句，并且在程序的语句序列中，B2紧跟在B1之后。实现：①用记录；②用链表转移语句指向块而不是指向三地址语句因为基本块变换后，语句会发生变化循环的定义：①强连通；②唯一入口29流图定义：把控制流信息加到基本块集合中，形成程序的有向图，称举例(1)i:=m-1(2)j:=n(3)t1:=4*n(4)v:=a[t1](5)i:=i+1(6)t2:=4*i(7)t3:=a[t2](8)ift3<vgoto(5)(9)j:=j-1(10)t4:=4*j(11)t5:=a[t4](12)ift5>vgoto(9)(13)ifi>=jgoto(23)(14)t6:=4*i(15)x:=a[t6](16)t7:=4*i(17)t8:=4*j(18)t9:=a[t8](19)a[t7]:=t9(20)t10:=4*j(21)a[t10]:=x(22)goto(5)(23)t11:=4*i(24)x:=a[t11](25)t12:=4*i(26)t13:=4*n(27)t14:=a[t13](28)a[t12]:=t14(29)t15:=4*n(30)a[t15]:=xB1B2B3B4B5B6B2B3B6B230举例(1)i:=m-1(2)8.5下次引用信息在把三地址代码转换成为目标代码时，遇到的一个重要问题：如何充分利用寄存器？作用：如果存于寄存器的名字的值以后不再需要，那么该寄存器可以分配给其它名字基本思路：在一个基本块范围内考虑把在基本块内还要被引用的变量的值尽可能保存在寄存器中把在基本块内不再被引用的变量所占用的寄存器尽早地释放如：翻译语句x:=yopzx、y、z在基本块中是否还会被引用？在哪些三地址语句中被引用？318.5下次引用信息在把三地址代码转换成为目标代码时，遇到计算下次引用信息三地址语句序列：i:x:=1j:y:=xopzj是三地址语句i中x的下次引用信息假定讨论在一个基本块内的引用信息所有的变量在基本块出口处都是活跃的符号表中含有记录下次引用信息和活跃信息的域语句i对变量x定值没有对变量x定值的其他语句语句j引用x在语句i处定的值32计算下次引用信息三地址语句序列：j是三地址语句i中x算法输入：组成基本块的三地址语句序列输出：基本块中各名字的下次引用信息方法：1.把基本块中各变量在符号表中的下次引用信息域置为“无下次引用”、活跃信息域置为“活跃”。2.从基本块出口到入口由后向前依次处理各语句，对每个三地址语句i:x:=yopz，依次执行下述步骤：a)把当前符号表中变量x的下次引用信息和活跃信息附加到语句i上；b)把符号表中x的下次引用信息和活跃信息分别置为“无下次引用”和“非活跃”；c)把当前符号表中变量y和z的下次引用信息和活跃信息附加到语句i上；d)把符号表中y和z的下次引用信息均置为i，活跃信息均置为“活跃”。abcd次序不能颠倒!33算法输入：组成基本块的三地址语句序列abcd33举例计算向量点积的程序beginprod:=0;i:=1;dobeginprod:=prod+a[i]*b[i];i:=i+1endwhilei<=20end.程序的控制流图：B1(1)prod:=0(2)i:=1(3)t1:=4*i(4)t2:=a-4(5)t3:=t2[t1](6)t4:=4*i(7)t5:=b-4(8)t6:=t5[t4](9)t7:=t3*t6(10)t8:=prod+t7(11)prod:=t8(12)t9:=i+1(13)i:=t9(14)ifi<=20gotoB2B234举例计算向量点积的程序程序的控制流图：B1(1)prod计算B2中变量的下次引用信息初始化符号表：变量下次活跃i无活prod无活a无活b无活t1无活t2无活t3无活t4无活t5无活t6无活t7无活t8无活t9无活附加信息语句变量下次活跃从出口到入口依次检查每条三地址语句：(14)ifi<=20 i无活14活(13)i:=t9

i14活无非活t9无活13活(12)t9:=i+1 t913活无非活i无非活12活(11)prod:=t8

prod无活无非活t8无活11活(10)t8:=prod+t7

t811活无非活prod无非活10活t7无活10活35计算B2中变量的下次引用信息初始化符号表：变量下次活跃变量下次活跃i无活prod无活a无活b无活t1无活t2无活t3无活t4无活t5无活t6无活t7无活t8无活t9无活14活无非活13活无非活12活无非活11活无非活10活10活符号表：附加信息语句变量下次活跃(9)t7:=t3*t6t710活无非活t3无活9活t6无活9活(8)t6:=t5[t4]t69活无非活t5无活8活t4无活8活(7)t5:=b-4t58活无非活b无活7活(6)t4:=4*it48活无非活i12活6活(5)t3:=t2[t1]t39活无非活t2无活5活t1无活5活(4)t2:=a-4t25活无非活a无活4活(3)t1:=4*it15活无非活i6活3活36变量下次活跃14活无非活138.6简单的代码生成器思想：在基本块内充分利用寄存器方法：尽可能让变量的值保存在寄存器中，只有在下面两种情况下存储它们如果此寄存器要用于其它计算已到达基本块出口后续的代码尽可能引用变量在寄存器中的值，而不访问主存在基本块之间如何充分利用寄存器的困难：一个基本块可能有多个后继，而每个后继又可能有多个前驱，因而后继基本块不易判断变量的值是否存放在寄存器中，以及存放在那个寄存器中假定：三地址语句中的每个算符都对应一个相应目标语言算符378.6简单的代码生成器思想：在基本块内充分利用寄存器37考虑引用信息代码生成时，要考察不同的情况不同的情况下，生成的目标代码也不同如a:=b+c(1)b的值在Ri中，c的值在Rj中，且b不再活跃ADDRj,Ri代价为1(2)b的值在Ri中，c的值在存储单元Mc中，且b不再活跃ADDMc,Ri代价为2或MOVMc,RjADDRj,Ri代价为338考虑引用信息代码生成时，要考察不同的情况38数据结构寄存器描述器记录每个寄存器的当前内容开始时，寄存器描述器指示所有的寄存器均为空代码生成过程中，每个寄存器在任一给定时刻将保留0个或多个名字的值。地址描述器记录某时刻一个名字的当前值存放的位置，可能是：一个寄存器地址一个栈地址一个存储单元地址或这些地址的一个集合这些信息可以存放在符号表中，用来确定对一个名字的存取方式39数据结构寄存器描述器39寄存器分配函数getreg输入：三地址语句x:=yopz寄存器描述器和名字的地址描述器输出：地址L（L或者是寄存器，或者是存储单元）算法(1)若y的值在R中，且该R中不含其它名字的值，并且以后y不再活跃，没有下次引用信息，则返回R作为L。(2)若(1)失败，有空R时，就返回一个空R作为L。(3)若(2)失败，x在块中有下次引用，或op是一个需要寄存器的算符，则找一个已被占用的R。如果R的值尚未在存储单元中，用指令MOVR，M将R的值存放到一个存储单元中，如果R同时保存有几个变量的值，则对每一个需要存储的变量值都应产生一条MOV指令。并且更新地址描述器为，返回R。(4)如x在块中不再被引用，或找不到合适的被占用的寄存器，则返回x的存储单元Mx作为L。40寄存器分配函数getreg输入：三地址语句x:=yop代码生成算法输入：基本块的三地址语句输出：基本块的目标代码方法：对基本块中每个三地址语句x:=yopz执行以下操作：(1)确定工作单元L：=getreg(i:x:=yopz)(2)查看y的地址描述器，以确定y的值存放的当前位置y’若y的值同时存放在存储器和寄存器中，那么选择寄存器作为y’如果y的值在寄存器L中，更新y的地址描述器（y不在L中）和L的寄存器描述器（L中不含y的值）如果y的值不在L中，则生成指令：MOVy’,L(3)生成指令：opz’,L更新x的地址描述器（x的值在L中），如果L为寄存器，更新L的寄存器描述器（L中只含x的值）(4)若y/z的当前值没有下次引用，在块的出口非活跃，并且在寄存器中，则更新寄存器描述器及y/z的地址描述器（此后，这些寄存器不再包含y和/或z的值）41代码生成算法输入：基本块的三地址语句41特殊情况若三地址语句是x:=opy与x:=yopz类似若三地址语句是x:=y（复写语句）若y的值在R中，更新R的寄存器描述器和x的地址描述器，以记录x的值仅在保存y的那个寄存器中。若y没有下次引用，且在块的出口非活跃，则该寄存器不再保留y的值。若y的值仅在存储器My中，原则上可以在地址描述器中指出X在My中，但是这样会复杂代码生成算法，因为以后若要改变y的值必须先保存x的值。调用函数getreg来找一个存放x值的寄存器R，生成指令MOVy,R，并更新R的寄存器描述器和x、y的地址描述器。或者，若X无下次引用信息，生成指令MOVMy，Mx，更新x的地址描述器。42特殊情况若三地址语句是x:=opy42处理：使用MOV指令把那些在块出口是活跃的、且当前值还不在存储单元中的名字的值存储到它们的存储器地址中。方法：使用寄存器描述器确定哪些名字的当前值仍保留在寄存器中使用地址描述器确定其中哪些名字的当前值还不在存储单元里使用活跃变量信息来确定是否需要存储其当前值在没有进行数据流分析的情况下，需要假定用户定义的所有变量在基本块出口处都是活跃变量在计算下次引用信息的算法中，第一步要把活跃信息域置为“活跃”基本块的出口处43处理：基本块的出口处43举例考虑赋值语句d:=(a-b)+(a-c)+(a-c)三地址语句序列：t:=a-bu:=a-cv:=t+ud:=v+u假定在基本块的出口d是活跃的有两个寄存器R0和R144举例考虑赋值语句d:=(a-b)+(a-c)+(a-c)4翻译过程t:=a-bu:=a-cv:=t+ud:=v+u寄存器全空MOVa,R0SUBb,R0R0含tt在R0中MOVa,R1SUBc,R1R0含tR1含ut在R0中u在R1中ADDR1,R0R0含vR1含uv在R0中u在R1中ADDR1,R0R0含dd在R0中MOVR0,dd在R0和内存单元中语句生成的代码寄存器描述器地址描述器45翻译过程t:=a-bu:=a-cv:=t+ud:=v+u寄存为索引赋值语句生成目标代码考虑两种语句形式：a:=b[i]和a[i]:=b假定数组采用静态存储分配基址已知，用数组名表示下标i存放的位置不同，生成的目标代码也不同i在Ri中i在Mi中i在栈中a:=b[i]a[i]:=bMOVb(Ri),RMOVb,a(Ri)MOVMi,RMOVb(R),RMOVMi,RMOVb,a(R)MOVSi(A),RMOVb(R),RMOVSi(A),RMOVb,a(R)244355i的位置46为索引赋值语句生成目标代码考虑两种语句形式：a:=b[i]为指针赋值语句生成目标代码考虑两种语句形式：a:=*p和*p:=aP存放的位置不同，生成的目标代码也不同p在Rp中p在Mp中p在栈中a:=*p*p:=aMOV*Rp,aMOVa,*RpMOVMp,RMOV*R,RMOVMp,RMOVa,*RMOVSp(A),RMOV*R,RMOVa,RMOVR,*Sp(A)233244p的位置47为指针赋值语句生成目标代码考虑两种语句形式：a:=*p和*ifx<ygotoz实现：x-y的结果送入寄存器R判断R的值为正、负、还是零若为负，则转移到z利用条件码表示计算结果或存入寄存器R的值为正、负、还是零如：ifx<ygotoz目标代码：CMPx,yCJ<z为条件语句生成目标代码目标代码：MOVy,R0ADDz,R0MOVR0,xCJ<P语句序列x:=y+zifx<0gotoP48ifx<ygotoz为条件语句生成目标代码目标小结设计代码生成器时要考虑的问题输入、输出存储管理、寄存器分配目标机器相关问题（指令、寄存器、编址方式、寻址能力、寻址模式等）指令选择、计算顺序选择基本块和控制流图基本块：具有原子性的语句序列基本块的划分：入口语句的确定流图：有向图，结点：基本块，边：控制流49小结设计代码生成器时要考虑的问题49小结（续）下次引用信息作用计算方法代码生成器寄存器描述器地址描述器寄存器分配函数getreg代码生成算法50小结（续）下次引用信息50作业51作业51§8目标代码生成学时：6知识点：涉及的问题

基本块、程序流图下次引用信息代码生成算法52§8目标代码生成学时：61§8目标代码生成目标代码生成程序的任务将前端产生的中间代码转换为等价的目标代码对目标代码生成器的要求：正确高质量1.有效地利用目标机器的资源2.所生成的目标代码应高效地运行本章目标：介绍一个简单的代码生成器算法产生最优化代码问题是不可判定的，实践中能够产生好的（虽不是最优的）代码的启发式技术就很令人满意了53§8目标代码生成目标代码生成程序的任务1.有效地利用目本章主要内容8.1代码生成器设计中的问题8.2目标机器8.3运行时的存储管理8.4基本块和流图8.5下次引用信息8.6简单的代码生成器小结作业54本章主要内容8.1代码生成器设计中的问题38.1代码生成器设计中的问题代码生成器的具体细节依赖于目标机器和操作系统所有的代码生成器固有的问题代码生成器的输入代码生成器的输出存储管理指令选择寄存器分配计算顺序选择代码生成器的设计558.1代码生成器设计中的问题代码生成器的具体细节依赖于目一、代码生成器的输入中间代码经过语法分析、语义检查之后得到的正确的符号表记录了与名字有关的信息决定中间表示中的名字所代表的数据对象的运行地址假定：前期工作结果正确、可信中间代码足够详细必要的类型转换符已正确插入明显的语义错误已经发现、且正确恢复56一、代码生成器的输入中间代码5二、代码生成器的输出目标代码形式绝对机器代码可把代码放在内存中固定的地方、立即执行可重定位机器代码.obj（DOS）、.o（UNIX）开发灵活，允许各子模块单独编译需要由连接装配程序将它们连接在一起，生成可执行文件汇编代码代码生成过程容易，但需要汇编57二、代码生成器的输出目标代码6三、存储管理从名字到存储单元的映射由前端和代码生成器共同完成三地址代码中的名字指向该名字在符号表中位置的指针符号表中的信息在处理声明语句时填入“类型”决定了它的域宽“地址”确定该名字在过程的数据区域中的相对位置上述信息用于确定中间代码中的名字对应的数据对象在运行时的地址生成机器代码时，指令地址通过计数器来实现58三、存储管理从名字到存储单元的映射由前端和代码生成器共同完成例如：中间代码与目标代码的对应对于四元式j：gotoii<ji>j目标代码...0n四元式100的机器码四元式地址长度...100(，，，)101(，，，)102(，，，)103(，，，)...n1212n+12n+12四元式101的机器码88n+20n+20四元式102的机器码1616n+36n+36四元式103的机器码44n+40...将四元式j的地址记入与i相关的链表中，等待回填四元式i的地址已有，可以直接生成机器指令59例如：中间代码与目标代码的对应对于四元式j：gotoi目标四、指令选择机器指令系统的性质决定了指令选择的难易程度代码质量取决于它的执行速度和长度对每一类三地址语句，可以设计它的代码框架如：x:=y+z的代码框架可以是：MOVy,R0ADDz,R0MOVR0,xa:=b+cd:=a+ea:=a+1MOVb,R0ADDc,R0MOVR0,aMOVa,R0ADDe,R0MOVR0,dMOVa,R0ADD#1,R0MOVR0,aINCa60四、指令选择机器指令系统的性质决定了指令选择的难易程度a:=五、寄存器分配充分利用寄存器可以生成好的代码寄存器使用的两个问题哪些变量要放在寄存器中指定的变量放在哪个寄存器中寄存器指派的困难可用寄存器专用寄存器通用寄存器寄存器对把寄存器指派给相应的变量变量需要什么样的寄存器操作需要什么样的寄存器选择最优的寄存器指派方案是一个NP完全问题61五、寄存器分配充分利用寄存器可以生成好的代码10六、计算顺序的选择计算顺序影响目标代码的效率选择最佳计算次序是一个NP完全问题七、代码生成器的设计设计原则能够正确地生成代码易于实现、便于测试和维护只介绍一个简单的代码生成算法主要考虑寄存器的有效使用62六、计算顺序的选择计算顺序影响目标代码的效率七、代码生成器的8.2目标机器设计代码生成器的必要条件：熟悉目标机器一般信息编址方式：按字节编址每个字有4个字节寄存器：n个通用寄存器：R0、R1、Rn-1指令形式：OPS,D其中OP：MOV、ADD、SUBS：源操作数D：目的操作数638.2目标机器设计代码生成器的必要条件：熟悉目标机器12寻址方式地址形式汇编方式地址占用存储空间

绝对地址MM1寄存器RR0

变址c(R)c+contents(R)1间接寄存器*Rcontents(R)0

间接变址*c(R)contents(c+contents(R))1立即数#c常数c1指令代价指令所占用存储单元字数=1+S寻址方式占用字数+D寻址方式占用字数64寻址方式地址形式汇编方式地址举例MOVR0，R1将寄存器R0的内容复制到R1中代价：1MOVR5，M将寄存器R5的内容放到存储单元M中代价：2ADD#1，R3将寄存器R3的内容增加1代价：2SUB4(R0)，*12(R1)将地址为(contents(12+contents(R1))的单元中的值减去contents(4+contents(R0))，结果仍存放到地址为(contents(12+contents(R1))的单元中。代价：365举例MOVR0，R114三地址语句a:=b+c的代码(1)MOVb,R0ADDc,R0指令代价为6MOVR0,a(2)MOVb,aADDc,a指令代价为6(3)假定R0、R1和R2中分别存放了a、b和c的地址：MOV*R1,*R0ADD*R2,*R0指令代价为2(4)假定R1和R2中分别包含b和c的值，b的值以后不再需要：ADDR2,R1MOVR1,a指令代价为366三地址语句a:=b+c的代码(1)MOVb,R0过程的语义决定了运行时名字如何与存储单元相联系。存储分配策略静态存储分配存储器中活动记录的位置在编译时刻已经确定栈式存储分配当开始执行一个过程时，一个新的活动记录压入栈顶当该过程的活动结束时，其活动记录从栈中弹出活动记录的内容参数、返回值控制链、访问链、机器状态局部数据、临时变量8.3运行时的存储管理活动记录的分配和释放是调用序列和返回序列的一部分讨论三地址语句

callreturnhaltaction67过程的语义决定了运行时名字如何与存储单元相联系。8.3运静态存储分配情况三地址代码：/*S的代码*/action1callpaction2halt/*P的代码*/action3returnS的活动记录(64字节)：045660返回地址arrijP的活动记录(88字节)：04返回地址buf84n68静态存储分配情况三地址代码：/*S的代码*//*P的代三地址语句call的目标机器指令：MOV指令：存放返回地址GOTO指令：将控制转移到被调用过程的目标代码

MOV#here+20,callee.static_areaGOTOcallee.code_areahere：该MOV指令的地址20：call的机器指令的代价#here+20：返回地址被调用过程活动记录的开始地址被调用过程代码的第一条指令地址三地址语句return的目标机器指令：GOTO*callee.static_area代码结构69三地址语句call的目标机器指令：here：该MOV指令的地静态存储分配举例100:action1120:MOV#140,364 132:GOTO200 140:action2160:HALT… 200:action3220:GOTO*364… 300: 304: …364: 368: …保存返回地址调用过程P返回到364存储单元里存放的地址S的代码：P的代码：S的活动记录：(300-363)P的活动记录：(364-451)返回地址单元返回地址单元局部数据单元局部数据单元140返回地址70静态存储分配举例100:action1保存返回地址栈式存储分配情况活动记录分配在栈中活动记录在栈中的位置，直到运行时才能确定这个位置常被存放在一个寄存器中寄存器SP保存指向栈顶活动记录开始位置的指针当发生过程调用时，调用过程给SP一个增量，使之指向被调用过程的活动记录的开始位置，同时将控制转移到被调用过程；当控制返回到调用过程时，再将SP减去原来的增量，从而释放了被调用过程的活动记录。71栈式存储分配情况活动记录分配在栈中20代码结构主程序的代码MOV#stackstart,SP第一个过程的代码HALT初始化控制栈三地址语句call的机器代码ADD#caller.recordsize,SPMOV#here+16,SPGOTOcallee.code_areaSP指向下一个活动记录三地址语句return的机器代码GOTO*0(SP)SUB#caller.recordsize,SP间接变址，返回调用过程该指令在被调用过程的代码中SP指回调用过程的活动记录该指令在调用过程的代码中72代码结构主程序的代码初始化控制栈三地址语句call的机器代码程序说明三地址代码：/*S的代码*/action1callqaction2halt/*P的代码*/action3return/*q的代码*/action4callpaction5callqaction6callqreturn各过程目标代码的起址：s：#100p：#200q：#300活动记录的大小：ssize=20psize=40qsize=60控制栈的开始位置：#60073程序说明三地址代码：/*S的代码*//*P的代码*//*q的100:MOV#600,SP108:action1128:ADD#ssize,SP136:MOV#152,*SP144:GOTO300152:SUB#ssize,SP160:action2180:HALT… 200:action3220:GOTO*0(SP)… 栈式存储分配举例300:action4320:ADD#qsize,SP328:MOV#344,*SP336:GOTO200344:SUB#qsize,SP352:action5372:ADD#qsize,SP380:MOV#396,*SP388:GOTO300396:SUB#qsize,SP404:action6424:ADD#qsize,SP432:MOV#448,*SP440:GOTO300448:SUB#qsize,SP456:GOTO*0(SP)… 600: SPq初始化栈callqcallpreturncallqcallqreturn74100:MOV#600,SP栈式存储分配举例30程序执行及栈的变化情况SP=600SS的活动记录20callqSP=620返回地址152q的活动记录60qcallpSP=680p的活动记录40返回地址344preturn返回地址344SP=620p的活动记录40callqSP=680q的活动记录60返回地址396qreturn返回地址396SP=620q的活动记录60callqSP=680q的活动记录60返回地址448qreturn返回地址448SP=620q的活动记录60return返回地址152SP=600q的活动记录60haltS的活动记录2075程序执行及栈的变化情况SP=600SS的活动记录20call运行时名字的地址假定三地址语句为：x:=0静态存储分配情况静态数据区的基址：staticx在数据区中的位置是12x的实际地址应为：static+12尽管在编译时可确定static+12的值，但在生成中间代码时，static的值可能并不知道。这样，必须生成相应的三地址代码以“计算”static+12的值。赋值语句x:=0

被翻译为如下三地址代码：static[12]:=0若static=100，则相应的目标代码为：MOV#0,11276运行时名字的地址假定三地址语句为：x:=0尽管在编译时可确定用display表存取非局部名字，该表存放在寄存器中x局部于一个活动记录，该活动记录的display表指针在寄存器R3中将语句x:=0翻译成为如下三地址语句：

t1:=12+R3*t1:=0栈式存储分配情况t1中存放的是x的地址这个序列可由如下机器指令来实现：MOV#0,12(R3)77用display表存取非局部名字，该表存放在寄存器中栈式存储8.4基本块和流图基本块具有原子性的一组连续语句序列。控制从第一条语句流入，从最后一条语句流出，中途没有停止或分支（末尾除外）划分基本块的方法确定入口语句三地址代码的第一条语句条件/无条件语句转移到的语句紧跟在条件/无条件语句后面的语句确定基本块从一个入口语句（含该语句）到下一个入口语句（不含）从一个入口语句（含该语句）到停止语句（含该语句）788.4基本块和流图基本块27举例基本块：t1:=a*at2:=a*bt3:=2*t2t4:=t1+t3t5:=b*bt6:=t4+t5(1)i:=m-1(2)j:=n(3)t1:=4*n(4)v:=a[t1](5)i:=i+1(6)t2:=4*i(7)t3:=a[t2](8)ift3<vgoto(5)(9)j:=j-1(10)t4:=4*j(11)t5:=a[t4](12)ift5>vgoto(9)(13)ifi>=jgoto(23)(14)t6:=4*i(15)x:=a[t6](16)t7:=4*i(17)t8:=4*j(18)t9:=a[t8](19)a[t7]:=t9(20)t10:=4*j(21)a[t10]:=x(22)goto(5)(23)t11:=4*i(24)x:=a[t11](25)t12:=4*i(26)t13:=4*n(27)t14:=a[t13](28)a[t12]:=t14(29)t15:=4*n(30)a[t15]:=x基本块划分：B1B2B3B4B5B679举例基本块：(1)i:=m-1(14)流图定义：把控制流信息加到基本块集合中，形成程序的有向图，称为流图（控制流图）构造：流图的结点是基本块如果一个结点基本块的入口语句是程序的第一条语句，则称此基本块结点为首结点。如果在某个执行序列中，基本块B2紧跟在基本块B1之后执行，则从B1到B2有一条有向边，B1是B2的前驱，B2是B1的后继。即如果：有一个条件/无条件转移语句从B1的最后一条语句转移到B2的第一条语句；B1的最后一条语句不是无条件转移语句，并且在程序的语句序列中，B2紧跟在B1之后。实现：①用记录；②用链表转移语句指向块而不是指向三地址语句因为基本块变换后，语句会发生变化循环的定义：①强连通；②唯一入口80流图定义：把控制流信息加到基本块集合中，形成程序的有向图，称举例(1)i:=m-1(2)j:=n(3)t1:=4*n(4)v:=a[t1](5)i:=i+1(6)t2:=4*i(7)t3:=a[t2](8)ift3<vgoto(5)(9)j:=j-1(10)t4:=4*j(11)t5:=a[t4](12)ift5>vgoto(9)(13)ifi>=jgoto(23)(14)t6:=4*i(15)x:=a[t6](16)t7:=4*i(17)t8:=4*j(18)t9:=a[t8](19)a[t7]:=t9(20)t10:=4*j(21)a[t10]:=x(22)goto(5)(23)t11:=4*i(24)x:=a[t11](25)t12:=4*i(26)t13:=4*n(27)t14:=a[t13](28)a[t12]:=t14(29)t15:=4*n(30)a[t15]:=xB1B2B3B4B5B6B2B3B6B281举例(1)i:=m-1(2)8.5下次引用信息在把三地址代码转换成为目标代码时，遇到的一个重要问题：如何充分利用寄存器？作用：如果存于寄存器的名字的值以后不再需要，那么该寄存器可以分配给其它名字基本思路：在一个基本块范围内考虑把在基本块内还要被引用的变量的值尽可能保存在寄存器中把在基本块内不再被引用的变量所占用的寄存器尽早地释放如：翻译语句x:=yopzx、y、z在基本块中是否还会被引用？在哪些三地址语句中被引用？828.5下次引用信息在把三地址代码转换成为目标代码时，遇到计算下次引用信息三地址语句序列：i:x:=1j:y:=xopzj是三地址语句i中x的下次引用信息假定讨论在一个基本块内的引用信息所有的变量在基本块出口处都是活跃的符号表中含有记录下次引用信息和活跃信息的域语句i对变量x定值没有对变量x定值的其他语句语句j引用x在语句i处定的值83计算下次引用信息三地址语句序列：j是三地址语句i中x算法输入：组成基本块的三地址语句序列输出：基本块中各名字的下次引用信息方法：1.把基本块中各变量在符号表中的下次引用信息域置为“无下次引用”、活跃信息域置为“活跃”。2.从基本块出口到入口由后向前依次处理各语句，对每个三地址语句i:x:=yopz，依次执行下述步骤：a)把当前符号表中变量x的下次引用信息和活跃信息附加到语句i上；b)把符号表中x的下次引用信息和活跃信息分别置为“无下次引用”和“非活跃”；c)把当前符号表中变量y和z的下次引用信息和活跃信息附加到语句i上；d)把符号表中y和z的下次引用信息均置为i，活跃信息均置为“活跃”。abcd次序不能颠倒!84算法输入：组成基本块的三地址语句序列abcd33举例计算向量点积的程序beginprod:=0;i:=1;dobeginprod:=prod+a[i]*b[i];i:=i+1endwhilei<=20end.程序的控制流图：B1(1)prod:=0(2)i:=1(3)t1:=4*i(4)t2:=a-4(5)t3:=t2[t1](6)t4:=4*i(7)t5:=b-4(8)t6:=t5[t4](9)t7:=t3*t6(10)t8:=prod+t7(11)prod:=t8(12)t9:=i+1(13)i:=t9(14)ifi<=20gotoB2B285举例计算向量点积的程序程序的控制流图：B1(1)prod计算B2中变量的下次引用信息初始化符号表：变量下次活跃i无活prod无活a无活b无活t1无活t2无活t3无活t4无活t5无活t6无活t7无活t8无活t9无活附加信息语句变量下次活跃从出口到入口依次检查每条三地址语句：(14)ifi<=20 i无活14活(13)i:=t9

i14活无非活t9无活13活(12)t9:=i+1 t913活无非活i无非活12活(11)prod:=t8

prod无活无非活t8无活11活(10)t8:=prod+t7

t811活无非活prod无非活10活t7无活10活86计算B2中变量的下次引用信息初始化符号表：变量下次活跃变量下次活跃i无活prod无活a无活b无活t1无活t2无活t3无活t4无活t5无活t6无活t7无活t8无活t9无活14活无非活13活无非活12活无非活11活无非活10活10活符号表：附加信息语句变量下次活跃(9)t7:=t3*t6t710活无非活t3