第12章 代码生成

第12章代码生成•代码生成要考虑的主要问题•基本块的代码生成(在一个基本块范围内考虑如何充分利用寄存器的问题)•PL/0相关的代码生成•从DAG生成代码（略）——具体细节依赖于目标机器和操作系统共同的问题：1.充分利用寄存器基本块中全局寄存器分配：不把寄存器平均分配给各个变量使用，而是从可用的寄存器中分出几个，固定分配给几个变量单独使用。标准——以各变量在循环内需要访问主存单元的次数为标准。2.选择计算机指令系统3.选择计算次序代码生成需要考虑的主要问题P2763目标代码的三种形式(1)地址代真的机器代码(2)待装配的机器代码模块(3)汇编语言（宏汇编）机器指令形式(opsource,destination)ADDs,d//d+sSUBs,d//d-sMOVs,d//sd机器指令开销(cost)MOVR,M开销2ADD#1,R开销2MOVR0,R1开销1目标机器的地址方式地址方式形式地址开销直接地址MM1寄存器RR0间接寄存器*Rcontents(R)0索引(变址)c(R)c+contents(R)1间接索引(变址)*c(R)Contents(c+contents(R))1例a:=b+c1.MOVb,R0ADDc,R0cost=6MOVR0,a2.假定R0、R1和R2中分别包含a、b和c的地址:MOV*R1,*R0ADD*R2,*R0cost=23.假定R1和R2中分别包含b和c的值,并且b的值在这个赋值以后不再需要,则还可有ADDR2,R1MOVR1,acost=3例T4:=A+B-(E-(C+D))T1:=A+BMOVA,R0T2:=C+DADDB,R0T3:=E-T2MOVC,R1T4:=T1-T3ADDD,R1MOVR0,T1MOVE,R0SUBR1,R0MOVT1,R1SUBR0,R1MOVR1,T4例T2:=C+DMOVC,R0T3:=E-T2ADDD,R0T1:=A+BMOVE,R1T4:=T1-T3SUBR0,R1MOVA,R0ADDB,R0SUBR1,R0MOVR0,T4在一个基本块内考虑如何充分利用寄存器：l尽可能地让该变量的值保留在寄存器中l尽可能引用变量在寄存器中的值l对于基本块内不再被引用的变量迟早释放。简单的代码生成器（基本块内）定值：假如有四元式i：A∶＝BopC则称A在四元式i中被定值，i是A的定值点。在一个基本块内，对A的引用仅仅发生在定值点之后。但对A允许多次定值，并且多次引用。待用信息：若在一个基本块中，在i后面的四元式j中要引用A值，且从i到j之间没有其它对A的定值点，这时我们称j是四元式i中对变量A的待用信息或称下次引用信息，同时也称A是活跃的。若A被多处引用，则可构成待用信息链与活跃信息链。可从基本块的出口由后向前扫描，对每个变量建立相应的待用信息链和活跃信息链。假如有四元式i：A∶＝BopC对所有变量的两栏置初值：“待用信息”栏全部置为“非待用”，记为F“活跃信息”栏按在基本块出口处是否为活跃而置成“活跃”（L）或“非活跃”（F）。假定变量都是活跃的，临时变量都是非活跃的。在计算过程中，对于有“待用信息”的变量，直接标记相应的四元式序号符号表中增加“待用信息”栏和“活跃信息”栏计算待用信息的算法从基本块出口到入口由后向前依次处理每个四元式。对每个四元式i:A:=BopC，执行下述步骤：a)把符号表中变量A的待用信息和活跃信息附加到四元式上。b)把符号表中变量A的待用信息栏和活跃信息栏分别置为“非待用”和“非活跃”。（由于在i中对A的定值只能在i以后的四元式才能引用，因而对i以前的四元式来说，A是不活跃也不可能是待用的）。c)把符号表中变量B和C的待用信息和活跃信息附加到四元式i上。d)把符号表中变量B和C的待用信息栏置为“i”，活跃信息栏置为“活跃”。注意，以上a)和b)，c)和d)的次序不能错乱。若用A，B，C和D表示变量，用T，U，V表示中间变量，有四元式如下：(1)T:=A-B(2)U:=A-C(3)V:=T+U(4)D:=V+U其名字表中的待用信息和活跃信息如下表，用“F”表示“非待用”或“非活跃”，用“L”表示“活跃”。(1)(2)(3)(4)表示四元式序号。例：待用信息和活跃信息待用信息活跃信息变量名初值待用信息链初值活跃信息链AF(2)(1)LLLBF(1)LLCF(2)LLDFFLFTF(3)FFLFUF(4)(3)FFLLFVF(4)FFLF表中“待用信息链”与“活跃信息链”的每列从左至右为每从后向前扫描一个四元式时相应变量的信息变化情况，空白处为没变化。待用信息和活跃信息在四元式上的标记如下所示：(1)T(3)L:=A(2)L-BFL(2)U(3)L:=AFL-CFL(3)V(4)L:=TFF+U(4)L(4)DFL:=VFF+UFF2寄存器描述和地址描述为随时掌握各寄存器的情况，寄存器描述数组RVALUE:描述每个寄存器当前的状况变量地址描述数组AVALUE：表示变量的存放情况3基本块的代码生成算法假设只有A:=BopC的四元式序列A．对每个四元式i:A:=BopC，依次执行下述步骤：1．以四元式i:A:=BopC为参数，调用过程getreg(i:A:=BopC)。从getreg返回时，得到一寄存器R，用它作存放A现行值的寄存器；2．利用AVALUE[B]和AVALUE[C]，确定出B和C现行值存放位置B`和C`，如果其现行值在寄存器中，则把寄存器取作B`和C`；1．如B`≠R，则生成目标代码LDR，B`opR，C`否则，生成目标代码opR，C`如B`或C`为R，则删除AVALUE[B]或AVALUE[C]中的R2．令AVALUE[A]={R}，并令RVALUE[R]={A}，以表示变量A的现行值只在R中并且R中的值只代表A的现行值；3．如B或C的现行值在基本块中不再被引用，它们也不是基本块出口之后的活跃变量（由四元式i上的附加信息知道），并且其现行值在某个寄存器Rk中，则删除RVALUE[Rk]中的B或C以及AVALUE[B]或AVALUE[C]中的Rk，使该寄存器不再为B或C所占用。B．处理完基本块中所有四元式之后，对现行值在某寄存器R中的每个变量M，若它在出口之后使活跃的，则生成指令：STR，M，放到主存中。其中假定d在基本块的出口是活跃的。uvdutvcaubatcacabad::::)()()(:例代码序列语句生成的代码寄存器描述器地址描述器t:=a－bMOVa,R0SUBb,R0空寄存器t在R0中u:=a－cMOVa,R1SUBc,R1v:=t＋uADDR1,R0d:=v＋uSTR1,dd在R0中和存储器中t在R0中u在R1中u在R1中v在R1中d在R0中R0包含tR0包含tR1包含uR1包含uR0包含vR0包含dADDR1,R0从DAG生成目标代码四元式序列GT1:=A+BT2:=C+DT3:=E-T2T4:=T1-T3DAG:ABECDn9n3n8n1n2n7n6n4n5T4T1T3T2+--+例：赋值语句T4:=A+B-(E-(C+D))T4:=A+B-(E-(C+D))T1:=A+BMOVA,R0T2:=C+DADDB,R0T3:=E-T2MOVC,R1T4:=T1-T3ADDD,R1MOVR0,T1MOVE,R0SUBR1,R0MOVT1,R1SUBR0,R1MOVR1,T4T4:=A+B-(E-(C+D))T2:=C+DMOVC,R0T3:=E-T2ADDD,R0T1:=A+BMOVE,R1T4:=T1-T3SUBR0,R1MOVA,R0ADDB,R0SUBR1,R0MOVR0,T4原因：T4的计算紧跟在T1之后尽量使结点的求值紧接其最左变量的求值之后启发式排序算法(1)while存在未列入表的内部结点do(2)begin选取一个未列入表的但其全部父结点均已列入表的结点n;(3)将n列入表中;(4)whilen的最左子结点m不是叶结点并且其所有父结点均已列入表中do(5)begin将m列入表中;(6)n:=m(7)end(8)endT8:=d+eT6:=a+bT5:=T6-cT4:=T5*T8T3:=T4-eT2:=T6+T4T1:=T2*T3例:a[i]:=b+1:=ind+membconst1ind+constiregspconstaregsp++基于树重写的代码生成regi+{ADDRj,Ri}regiregj(1)regjconstc{MOV#c,Rj}(2)regimema{MOVa,Ri}(3)mem{MOVRi,a}(4)mem{MOVRj,*Ri}(5){MOVc(Rj),Ri}:=memaregi:=ind+memaregjregiconstcregiregj(6)regi{ADDc(Rj),Ri}(7)(8){INCRi}+regiindconstcregj+cost1{ADDRj,Ri}regiregiregiregiregj++(1)reg0consta{MOV#a,R0}(7)reg0{ADDSP,R0}+:=indmembconst1indconstiregspreg0reg0regsp+++indconstiregSP++reg0indconstiregSP+:=indreg0+membconst1+reg1const1:=indreg1reg0MOV#a,R0ADDSP,R0ADDi(SP),R0MOVb,R1INCR1MOVR1,*R0l命令式或过程式语言l应用式(Applicative)或函数式应用式语言：Lisp和ML语法：functionn(…function2(function1(data))…)逐个函数应用在数据上的变换，最终得到一个结果。l基于规则(rule_based)和面向对象(object_oriented)程序执行是通过检查使能条件，决定执行适当动作。语法：使能条件1→动作1使能条件2→动作2...使能条件n→动作n如prolog补充内容：程序设计语言的计算模型已经成为越来越重要的计算模式；面向对象的程序设计语言支持抽象数据类型和继承性，即将数据和对数据的操作放在一起，定义一组具有公共行为属性和数据类型的对象，由类机制将这组对象给予抽象表示。O-O程序设计四种应用环境：批处理环境，交互环境，嵌入式系统和编程环境l批处理环境：一个程序输入一组数据文件，处理这些数据，然后生成一组输出文件。l交互环境：程序在执行过程中直接和用户在显示控制台上交互，不断从键盘或鼠标接受输入，将输出发送到显示器上。l嵌入式系统环境：1.没有操作系统，没有文件，直接和非标准的I/O设备交互；2.出错处理非常重要；3.常常是实时地操作；4.常常是一个分布式系统（并行）描述并行任务的语言——并行编译系统语言应用环境编辑器(editors)调试器(debuggers)环境包括验证(verifiers)测试数据(testdatagenerator)打印(prettyprinters)语言设计：1.帮助独立编译(seperatecompilation)和将成分(component)汇编(assemblly)2.可设断点，追踪执行，帮助程序测试和debuggingl程序设计实现环境