中间代码生成

中间代码生成1第1页，共30页，2023年，2月20日，星期三第八章：中间代码生成：概述编译器的分析综合模型分析部分：源程序=〉基本块=〉中间表示综合部分：中间表示=〉目标程序图8-1：中间代码生成器的位置使用中间表示（形式）的优点重置目标比较容易可在中间表示上应用与机器无关的代码优化器如何实现？语法制导翻译2第2页，共30页，2023年，2月20日，星期三第八章：中间代码生成：概述中间表示后缀表示（表达式）语法树/分析树和DAG：图8-2图8-3：语法制导定义产生语法树/DAG语法树：mkunode和mknode每次返回新节点指针图8-4：图8-2a中语法树的两种表示DAG：mkunode和mknode尽可能返回现存节点指针三地址码3第3页，共30页，2023年，2月20日，星期三第八章：中间代码生成概述三地址码声明语句赋值语句布尔表达式4第4页，共30页，2023年，2月20日，星期三第八章：中间代码生成：三地址码三地址码的一般形式x:=yopz三地址码是语法树或DAG的线性表示图8-5：图8-2中的语法树和DAG相对应的三地址码5第5页，共30页，2023年，2月20日，星期三第八章：中间代码生成：三地址码三地址语句的类型（通用）x:=yopzx:=opyx:=yx:=y[i]及x[i]:=yx:=&y,x:=*y及*x:=ygotoLifxrelopygotoLp(x1,x2…xn)paramx1paramx2…paramxncallp,nreturny6第6页，共30页，2023年，2月20日，星期三第八章：中间代码生成：三地址码语法制导翻译生成三地址码临时名字成了语法树的内节点图8-6：S属性定义生成赋值语句的三地址码图8-7：为while语句生成代码的语义规则7第7页，共30页，2023年，2月20日，星期三第八章：中间代码生成：三地址码三地址语句的实现抽象形式：三地址语句具体实现：通过带有操作符合操作数的记录结构来实现四元式三元式间接三元式8第8页，共30页，2023年，2月20日，星期三第八章：中间代码生成：三地址码三地址语句的实现四元式带有四个域的记录结构：op,arg1,arg2,resultarg1,arg2,result域的内容正常情况下指向这些域所代表的名字在符号表表项的指针临时名字在生成时一定要被写入符号表图8-8a：三地址语句的四元式表示9第9页，共30页，2023年，2月20日，星期三第八章：中间代码生成：三地址码三地址语句的实现三元式为了避免临时名字在生成时被写入符号表中，可以通过计算临时值的语句的位置来引用它带有四个域的记录结构：op,arg1,arg2arg1,arg2指向符号表（对于程序员定义的名字或常量）的指针或者三元组结构（对于临时变量）的指针图8-8b：三地址语句的三元式表示图8-9：更多三元式表示10第10页，共30页，2023年，2月20日，星期三第八章：中间代码生成：三地址码三地址语句的实现间接三元式列出指向三元式的指针，而不是列出三元式本身图8-10：三地址语句的间接三元式表示11第11页，共30页，2023年，2月20日，星期三第八章：中间代码生成：三地址码三地址语句的实现表示方法比较：间址的使用使用四元式表示，定义或使用临时变量的三地址语句可以通过符号表直接访问临时变量的地址使用四元式表示，符号表在值的计算及使用之间提供了一次额外间址，有利于优化。使用三元式表示，移动一条定义临时值的语句需要我们改变在arg1及arg2数组中所有对该语句的引用，难以优化。使用间接三元式表示，可以通过statement列表的重新排序来移动语句。12第12页，共30页，2023年，2月20日，星期三第八章：中间代码生成概述三地址码声明语句赋值语句布尔表达式13第13页，共30页，2023年，2月20日，星期三第八章：中间代码生成：声明语句过程中的声明语句单个过程中所有的声明语句作为一个组来处理（Pascal,C,Fortran）使用一个全局变量offset跟踪下一个可用的相对地址图8-11：计算声明语句中名字的类型和相对地址重写产生式P->{offset:=0}D以便所有的动作都出现在产生式右部的未端P->MDM->ε{offset:=0}14第14页，共30页，2023年，2月20日，星期三第八章：中间代码生成：声明语句跟踪作用域信息嵌套过程当看到嵌套的过程时，应暂时挂起对外围过程声明语句的处理假定每个过程都有一个单独的符号表，当遇到过程声明D->procid;D1;S时，便创建一个新的符号表，并在此符号表中为D1中的声明创建相应的表项。新表有一个指针指回外围过程的符号表；由id代表的名字本身是该外围过程的局部名字。15第15页，共30页，2023年，2月20日，星期三第八章：中间代码生成：声明语句跟踪作用域信息嵌套过程图8-12：嵌套过程的符号表图8-13：处理嵌套过程中的声明语句两个栈：1）一个存放嵌套过程的外围符号表；2）1）一个存放嵌套过程的外围offset16第16页，共30页，2023年，2月20日，星期三第八章：中间代码生成：声明语句记录中的域名图8-14：为记录中的域名建立符号表记录的布局与过程的活动记录的布局相似17第17页，共30页，2023年，2月20日，星期三第八章：中间代码生成概述三地址码声明语句赋值语句布尔表达式18第18页，共30页，2023年，2月20日，星期三第八章：中间代码生成：赋值语句表达式的类型整型、实型、数组、记录主要问题在符号表中查找名字存储数组及记录中的元素19第19页，共30页，2023年，2月20日，星期三第八章：中间代码生成：赋值语句符号表中的名字图8-15：为赋值语句产生三地址码的翻译模式通过适当的lookup操作和嵌套过程的符号表指针top(tblptr)，实现最近嵌套作用域规则（图8-13）临时名字的产生newtemp临时名字的重用代码生成阶段将独立的临时变量封装到同一个地址20第20页，共30页，2023年，2月20日，星期三第八章：中间代码生成：赋值语句临时名字的重用通过一个小数组（栈）保存临时名字实现例8.1：图8-16带有栈临时变量的三地址码有些时候（如条件赋值语句）不能使用，因为此时临时名字不能以后进先出方式指派名字，需单独指派自己的名字一个合理策略每当创建一个额外的定义或使用一个临时名字或移动其计算时，均创建一个新的名字21第21页，共30页，2023年，2月20日，星期三第八章：中间代码生成：赋值语句寻址数组元素图8-17：二维数据的布局（行/列优先）产生数组引用A[i1,i2…ik]的前m个下标的Elist生成三地址码（8-7）和（8-8）22第22页，共30页，2023年，2月20日，星期三第八章：中间代码生成：赋值语句寻址数组元素数组元素寻址的翻译模式：312-314页Elist综合属性array：指向符号表数组名表项的指针Elist继承属性ndim：Elist的维数Limit(array,j)：array指向符号表数组名表项的数组的第j维的元素个数Elist.place：临时变量，保存根据Elist的下标表达式计算出来的值L有两个属性Place：（8-6）第二项Offset：（8-6）第一项例8.2：图8-18数组赋值语句x:=A[y,z]的注释分析树23第23页，共30页，2023年，2月20日，星期三第八章：中间代码生成：赋值语句赋值语句中的类型转换图8-19：E->E1+E2的语义动作24第24页，共30页，2023年，2月20日，星期三第八章：中间代码生成：赋值语句记录域的访问为每个记录类型构造一个符号表（参8-14），把记录域的类型和相对地址信息记在域名字的符号表表项中，这样记录域的访问与其它名字的访问一样了。25第25页，共30页，2023年，2月20日，星期三第八章：中间代码生成概述三地址码声明语句赋值语句布尔表达式26第26页，共30页，2023年，2月20日，星期三第八章：中间代码生成：布尔表达式布尔表达式基本作用计算逻辑值控制流语句中的条件表达式27第27页，共30页，2023年，2月20日，星期三第八章：中间代码生成：布尔表达式计算逻辑值从左到右按与算术表达式相似的方式完全计算差别：布尔运算符vs算术运算符例8.3：表达式a<borc<dande<f图8-20：用数值表示布尔值的翻译模式图8-21：表达式a<borc<dande<f的翻译28第28页，共30页，2023年，2月20日，星期三第八章：中间代码生成：布尔表达式计算逻辑值短路代码即使不对布尔运算符生成代码并且不必生成整个表达式的代码，也可以把布尔表达式翻译成三地址码用代码序列中的位置表示表达式的值图8-21：根据到达语句101还是