第七章目标代码生成

1、第7章目标代码生成 代码生成是指把语法分析后或者优化后代码生成是指把语法分析后或者优化后的中间代码的中间代码( (如四元式或三元式如四元式或三元式) )变换成目标变换成目标代码，所生成的目标代码一般有如下三种形代码，所生成的目标代码一般有如下三种形式：式：(1) (1) 能够立即执行的机器语言代码，它能够立即执行的机器语言代码，它们通常放在固定的存储区中并可直接执行，们通常放在固定的存储区中并可直接执行，如如PCPC机中后缀为机中后缀为.COM.COM或或.EXE.EXE的文件。的文件。(2) (2) 待装配的机器语言模块，其地址均为相待装配的机器语言模块，其地址均为相对地址，所以不能直接执行

2、。当需要执行时由连对地址，所以不能直接执行。当需要执行时由连接装配程序把它们与其它运行程序和库函数连接接装配程序把它们与其它运行程序和库函数连接起来，装配成可执行的机器语言代码，如起来，装配成可执行的机器语言代码，如PCPC机中机中后缀为后缀为.OBJ.OBJ的文件都属于待装配的模块的文件都属于待装配的模块( (文件文件) )。(3) (3) 汇编语言程序，必须通过汇编程序的汇汇编语言程序，必须通过汇编程序的汇编方可转换成可执行的机器语言代码，如编方可转换成可执行的机器语言代码，如PCPC机中机中后缀为后缀为.ASM.ASM的文件即为汇编语言程序。的文件即为汇编语言程序。一个高级语言程序的目标

3、代码要经常、反复使用，一个高级语言程序的目标代码要经常、反复使用，因此代码生成要着重考虑两个问题：一是如何使生成因此代码生成要着重考虑两个问题：一是如何使生成的目标代码较短，二是如何充分利用计算机的寄存器的目标代码较短，二是如何充分利用计算机的寄存器以减少目标代码中访问存储单元的次数。生成的目标以减少目标代码中访问存储单元的次数。生成的目标代码越短，寄存器的利用越充分，目标代码的质量也代码越短，寄存器的利用越充分，目标代码的质量也就越高。就越高。设计一个代码生成器需要考虑具体的机器结构、设计一个代码生成器需要考虑具体的机器结构、指令格式、字长及寄存器个数和种类，并且与指令的指令格式、字长及寄存

4、器个数和种类，并且与指令的语义和所用的操作系统、存储管理等都密切相关。语义和所用的操作系统、存储管理等都密切相关。7.1 7.1 一个简单代码生成器一个简单代码生成器一个简单的代码生成器，此生成器依次把每条中一个简单的代码生成器，此生成器依次把每条中间代码变换成目标代码，并且在一个基本块范围内考间代码变换成目标代码，并且在一个基本块范围内考虑如何充分利用寄存器的问题。一方面，在基本块中，虑如何充分利用寄存器的问题。一方面，在基本块中，当生成计算某变量值的目标代码时，尽可能地让该变当生成计算某变量值的目标代码时，尽可能地让该变量的值保留在寄存器中量的值保留在寄存器中( (即不编出把该变量的值存到

5、内即不编出把该变量的值存到内存单元的指令存单元的指令) )，直到该寄存器必须用来存放其它变量，直到该寄存器必须用来存放其它变量的值或已达基本块出口为止；另一方面，后续的目标的值或已达基本块出口为止；另一方面，后续的目标代码尽可能地引用变量在寄存器中的值而不访问内存。代码尽可能地引用变量在寄存器中的值而不访问内存。如一如一C C语言语句语言语句A=(B+C)A=(B+C)* *D+ED+E，翻译为四元式，翻译为四元式G G：T T1 1=B+C=B+CT T2 2=T=T1 1* *D DA=TA=T2 2+E+E如果不考虑代码的效率，可以简单地把每条中间代如果不考虑代码的效率，可以简单地把每条

6、中间代码码( (四元式四元式) )映射成若干条目标指令，如将映射成若干条目标指令，如将x=y+zx=y+z映射为映射为MOV AX, y MOV AX, y / /* *AXAX为寄存器为寄存器* */ /ADD AX, zADD AX, zMOV x, AXMOV x, AX其中，其中，x x、y y、z z均为数据区的内存变量。均为数据区的内存变量。上述四元式代码序列上述四元式代码序列G G可翻译为可翻译为(1) (1) MOV AX, B MOV AX, B (2) (2) ADD AX, CADD AX, C(3) (3) MOV TMOV T1 1, AX, AX(4) (4) MO

7、V AX, TMOV AX, T1 1 (5) (5) MUL AX, DMUL AX, D(6) (6) MOV TMOV T2 2, AX, AX(7) (7) MOV AX, TMOV AX, T2 2(8) (8) ADD AX, E ADD AX, E (9) (9) MOV A, AX MOV A, AX 从正确性来看，这种翻译不存在问题，但却存在冗余。从正确性来看，这种翻译不存在问题，但却存在冗余。指令序列中的指令序列中的(4)(4)和和(7)(7)两条指令是多余的；而两条指令是多余的；而T T1 1、T T2 2均是中间均是中间代码生成时产生的临时变量，它们在出了基本块后将不再

8、使代码生成时产生的临时变量，它们在出了基本块后将不再使用，故用，故(3)(3)、(6)(6)两条指令也可删去。因此，在考虑了效率和两条指令也可删去。因此，在考虑了效率和充分使用寄存器之后，应生成如下代码：充分使用寄存器之后，应生成如下代码：(1) (1) MOV AX, B MOV AX, B (2) (2) ADD AX, CADD AX, C(3) (3) MUL AX, DMUL AX, D(4) (4) ADD AX, E ADD AX, E (5) (5) MOV A, AXMOV A, AX为了实现这一目的，代码生成器就必须了解一些信息：为了实现这一目的，代码生成器就必须了解一些信

9、息：在产生在产生T T2 2=T=T1 1* *D D对应的目标代码时，为了省去指令对应的目标代码时，为了省去指令MOV AX, TMOV AX, T1 1，就必须知道就必须知道T T1 1的当前值已在寄存器的当前值已在寄存器AXAX中；为了省去中；为了省去MOV TMOV T1 1, AX, AX，就必须知道出了基本块后就必须知道出了基本块后T T1 1不再被引用。不再被引用。7.1.1 7.1.1 待用信息与活跃信息待用信息与活跃信息在一个基本块内的目标代码中，为了提高寄存器的使用效在一个基本块内的目标代码中，为了提高寄存器的使用效率，应将基本块内还要被引用的值尽可能地保留在寄存器中，率，

10、应将基本块内还要被引用的值尽可能地保留在寄存器中，而将基本块内不再被引用的变量所占用的寄存器尽早释放。每而将基本块内不再被引用的变量所占用的寄存器尽早释放。每当翻译一条四元式如当翻译一条四元式如A=B op CA=B op C时，需要知道在基本块中还有哪时，需要知道在基本块中还有哪些四元式要对变量些四元式要对变量A A、B B、C C进行引用，为此，需要收集一些待用进行引用，为此，需要收集一些待用信息。信息。在一个基本块中，四元式在一个基本块中，四元式i i对变量对变量A A定值，如果定值，如果i i后面的四后面的四元式元式j j要引用要引用A A且从且从i i到到j j的四元式没有其它对的四

11、元式没有其它对A A的定值点，则称的定值点，则称j j是四元式是四元式i i中对变量中对变量A A的待用信息，同时也称的待用信息，同时也称A A是活跃的。如果是活跃的。如果A A被多处引用，则构成了被多处引用，则构成了A A的待用信息链与活跃信息链。的待用信息链与活跃信息链。为了取得每个变量在基本块内的待用信息和活跃信息，为了取得每个变量在基本块内的待用信息和活跃信息，可从基本块的出口由后向前扫描，对每个变量建立相应的待用可从基本块的出口由后向前扫描，对每个变量建立相应的待用信息链与活跃信息链。信息链与活跃信息链。如果没有进行数据流分析并且临时变量不允许跨基本块如果没有进行数据流分析并且临时变

12、量不允许跨基本块引用，则把基本块中的临时变量均看作基本块出口之后的非活引用，则把基本块中的临时变量均看作基本块出口之后的非活跃变量，而把所有的非临时变量均看作基本块出口之后的活跃跃变量，而把所有的非临时变量均看作基本块出口之后的活跃变量。变量。如果某些临时变量能够跨基本块使用，则把这些临时变如果某些临时变量能够跨基本块使用，则把这些临时变量也看成基本块出口之后的活跃变量。量也看成基本块出口之后的活跃变量。假设变量的符号表内有待用信息和活跃信息栏，则计算变假设变量的符号表内有待用信息和活跃信息栏，则计算变量待用信息的算法如下：量待用信息的算法如下：(1) (1) 首先将基本块中各变量的符号表的待

13、用信息栏置为首先将基本块中各变量的符号表的待用信息栏置为“非待用非待用”，对活跃信息栏则根据该变量在基本块出口之后是，对活跃信息栏则根据该变量在基本块出口之后是否活跃而将该栏中的信息置为否活跃而将该栏中的信息置为“活跃活跃”或或“非活跃非活跃”。(2) (2) 从基本块出口到基本块入口由后向前依次处理各四元从基本块出口到基本块入口由后向前依次处理各四元式。对每个四元式式。对每个四元式i i：A=B op CA=B op C依次执行以下步骤：依次执行以下步骤： 把符号表中变量把符号表中变量A A的待用信息和活跃信息附加到四元式的待用信息和活跃信息附加到四元式i i上；上； 把符号表中变量把符号表

14、中变量A A的待用信息和活跃信息分别置为的待用信息和活跃信息分别置为“非非待用待用”和和“非活跃非活跃”； 把符号表中变量把符号表中变量B B和和C C的待用信息和活跃信息附加到四的待用信息和活跃信息附加到四元式元式i i上；上； 把符号表中变量把符号表中变量B B和和C C的待用信息置为的待用信息置为i i，活跃信息置为活跃信息置为“活跃活跃”。注意：以上次序不能颠倒，如果四元式出现注意：以上次序不能颠倒，如果四元式出现A=op B A=op B 或者或者A=BA=B形式，则以上执行步骤完全相同，只是其中不涉及变形式，则以上执行步骤完全相同，只是其中不涉及变量量C C。例例7.17.1 考察

15、基本块：考察基本块：(1) (1) T=AT=AB B(2) (2) U=AU=AC C(3) (3) V=T+UV=T+U(4) (4) D=V+UD=V+U其中，其中，A A、B B、C C、D D为变量，为变量，T T、U U、V V为中间变量。试求各变为中间变量。试求各变量的待用信息链和活跃信息链。量的待用信息链和活跃信息链。 解答解答 我们根据计算变量待用信息的算法得到各变量的我们根据计算变量待用信息的算法得到各变量的待用信息链和活跃信息链如表待用信息链和活跃信息链如表7.17.1所示。表中的所示。表中的“F”F”表示表示“非非待用待用”或或“非活跃非活跃”，“L”L”表示表示“活跃

16、活跃”，(1)(1)(4)(4)分别表示分别表示基本块中的四个四元式。待用信息链和活跃信息链的每列从左基本块中的四个四元式。待用信息链和活跃信息链的每列从左到右为每行从后向前扫描一个四元式时相应变量的信息变化情到右为每行从后向前扫描一个四元式时相应变量的信息变化情况况( (空白处表示没有变化空白处表示没有变化) )。表7.1 例7.1的待用信息链和活跃信息链 待 用 信 息 活 跃 信 息 变量名 初值 待 用 信 息 链 初值 活 跃 信 息 链 T F (3) F F L F A F (2) (1) L L L B F (1) L L C F (2) L L U F (4) (3) F F

17、 L L F V F (4) F F L F D F F L F 待用信息和活跃信息在四元式上的标记如下待用信息和活跃信息在四元式上的标记如下( (每个变量都先每个变量都先去掉待用信息链和活跃信息链最右的值，然后由右向左依次引去掉待用信息链和活跃信息链最右的值，然后由右向左依次引用所出现的值用所出现的值) )：(1) (1) T T(3)L(3)L=A=A(2)L(2)LB BFLFL(2) (2) U U(3)L(3)L=A=AFLFLC CFLFL(3) (3) V V(4)L(4)L=T=TFFFF+U+U(4)L(4)L(4) (4) D DFLFL=V=VFFFF+U+UFFFF7.

18、1.2 7.1.2 代码生成算法代码生成算法为了在代码生成中进行寄存器分配，需要随时掌握各寄存器为了在代码生成中进行寄存器分配，需要随时掌握各寄存器的使用情况，即它是处于空闲状态还是已分配给某个变量或已分的使用情况，即它是处于空闲状态还是已分配给某个变量或已分配给某几个变量。通常用一个寄存器描述数组配给某几个变量。通常用一个寄存器描述数组RVALUERVALUE动态地记录动态地记录各寄存器的当前状况，并用寄存器各寄存器的当前状况，并用寄存器R Ri i的编号作为它的下标。此外，的编号作为它的下标。此外，还需建立一个变量地址描述数组还需建立一个变量地址描述数组AVALUEAVALUE来记录各变量

19、现行值存放来记录各变量现行值存放的位置，即其是在某寄存器中还是在某内存单元中，或者同时存的位置，即其是在某寄存器中还是在某内存单元中，或者同时存在于某寄存器和某内存单元中，可以有如下表示：在于某寄存器和某内存单元中，可以有如下表示：RVALUERRVALUERi i=A =A / /* *寄存器寄存器R Ri i分配给变量分配给变量A A* */ /RVALUERRVALUERi i=A,B =A,B / /* *寄存器寄存器R Ri i分配给变量分配给变量A A和和B B* */ /RVALUERRVALUERi i= = / /* *未分配未分配* */ /AVALUEA=A AVALUE

20、A=A / /* *表示表示A A的值在内存中的值在内存中* */ /AVALUEA=AVALUEA=R Ri i / /* *表示表示A A的值在寄存器的值在寄存器R Ri i中中* */ /AVALUEA=AVALUEA=R Ri i,A,A / /* *表示表示A A的值既在寄存器的值既在寄存器R Ri i中又在内存中中又在内存中* */ /假设基本块中每个四元式的形式都是假设基本块中每个四元式的形式都是A=B op CA=B op C，则代码生成则代码生成算法是对每个四元式算法是对每个四元式i i：A=B op CA=B op C执行下述步骤：执行下述步骤：(1) (1) 调用函数调用

21、函数GETREG (iGETREG (i：A=B op C)A=B op C)返回存放返回存放A A值结果的寄值结果的寄存器存器R R。(2) (2) 通过地址描述数组通过地址描述数组AVALUE BAVALUE B和和AVALUE CAVALUE C确定出变量确定出变量B B和变量和变量C C的现行值存放位置的现行值存放位置BB和和CC；如果是存放在寄存器中，则如果是存放在寄存器中，则把寄存器取作把寄存器取作BB和和CC。(3) (3) 如果如果BRBR，则生成目标代码：则生成目标代码：MOV R, BMOV R, Bop R, Cop R, C否则生成目标代码：否则生成目标代码：op R,

22、 Cop R, C如果如果BB或或CC为为R R，则删除则删除AVALUE BAVALUE B或或AVALUE CAVALUE C中的中的R R。(4) (4) 令令AVALUEA=RAVALUEA=R并令并令RVALUER=ARVALUER=A，表示变量表示变量A A的现的现行值只在行值只在R R中且中且R R中的值只代表中的值只代表A A的现行值。的现行值。(5) (5) 如果如果B B和和C C的现行值在基本块中不再被引用，它们也不是的现行值在基本块中不再被引用，它们也不是基本块出口之后的活跃变量且它们的现行值存放在寄存器基本块出口之后的活跃变量且它们的现行值存放在寄存器R Rk k中，

23、中，则删除则删除RVALUE RVALUE R Rk k 中的中的B B和和C C以及以及AVALUE BAVALUE B中的中的R Rk k，使寄存器使寄存器R Rk k不再为不再为B B和和C C所占用。所占用。函数函数GETREG(iGETREG(i：A=B op C)A=B op C)用来得到存放用来得到存放A A的当前值的寄存的当前值的寄存器器R R；其算法如下：其算法如下：(1) (1) 如果如果B B的现行值在某寄存器的现行值在某寄存器R Ri i中，且该寄存器只包含中，且该寄存器只包含B B的的值，或者值，或者B B和和A A是同一标识符，或者是同一标识符，或者B B在该四元式

24、之后不再被引用，在该四元式之后不再被引用，则选取则选取R Ri i为所需寄存器并转为所需寄存器并转(4)(4)。(2) (2) 如有尚未分配的寄存器，则从中选取一个如有尚未分配的寄存器，则从中选取一个R Ri i为所需寄存为所需寄存器并转器并转(4)(4)。(3) (3) 从已分配的寄存器中选取一个从已分配的寄存器中选取一个R Ri i为所需寄存器为所需寄存器R R。选取选取原则为：占用原则为：占用R Ri i的变量的值也同时放在内存中，或者该值在基本的变量的值也同时放在内存中，或者该值在基本块中要在最远的位置才会引用到。这样，对寄存器块中要在最远的位置才会引用到。这样，对寄存器R Ri i所

25、含的变量所含的变量和变量在内存中的情况必须先做如下调整：和变量在内存中的情况必须先做如下调整：对对RVALUE RVALUE R Ri i 中的每一个变量中的每一个变量M M，如果如果M M不是不是A A或者或者M M既是既是A A又是又是C C却不是却不是B B，而，而B B又不在又不在RVALUE RVALUE R Ri i 中，则：中，则： 如果如果AVALUE AVALUE R Ri i 中不包含中不包含M M，则生成目标代码则生成目标代码MOV M, MOV M, R Ri i ； 当当M M不是不是A A时，如果时，如果M M是是B B或者或者M M是是C C且同时且同时B B也在

26、也在RVALUE RVALUE R Ri i 中，则令中，则令AVALUE M=M,RAVALUE M=M,R，否则令否则令AVALUE M=MAVALUE M=M； 删除删除RVALUE RVALUE R Ri i 中的中的M M。(4) (4) 给出给出R R，返回。返回。例例7.2 7.2 对例对例7.17.1，假设只有，假设只有AXAX和和BXBX是可用寄存器，用代码是可用寄存器，用代码生成算法生成目标代码及其相应的生成算法生成目标代码及其相应的RVALUERVALUE和和AVALUEAVALUE。 解答解答 用代码生成算法生成的目标代码及其相应的用代码生成算法生成的目标代码及其相应的

27、RVALUERVALUE和和AVALUEAVALUE，如表如表7.27.2所示。所示。对其它形式的四元式也可仿照上述算法生成其目标代码。对其它形式的四元式也可仿照上述算法生成其目标代码。这里特别要指出的是，对形如这里特别要指出的是，对形如A=BA=B的复写，如果的复写，如果B B的现行值在某的现行值在某寄存器寄存器R Ri i中，那么无需生成目标代码，只需在中，那么无需生成目标代码，只需在RVALUE RVALUE R Ri i 中增中增加一个加一个A(A(即把即把R Ri i同时分配给同时分配给B B和和A)A)，把，把AVALUE AAVALUE A改为改为R Ri i；而且而且如果其后如

28、果其后B B不再被引用，还可把不再被引用，还可把RVALUE RVALUE R Ri i 中的中的B B和和AVALUE BAVALUE B中的中的R Ri i删除。删除。处理完基本块中所有的四元式后，对现行只在某寄存器中的处理完基本块中所有的四元式后，对现行只在某寄存器中的每个变量，如果它在基本块出口之后是活跃的，则要用每个变量，如果它在基本块出口之后是活跃的，则要用MOVMOV指令指令把它在寄存器中的值存放到数据区以它命名的内存单元中。为进把它在寄存器中的值存放到数据区以它命名的内存单元中。为进行这一工作，我们利用寄存器描述数组行这一工作，我们利用寄存器描述数组RVALUERVALUE来决

29、定其中哪些变来决定其中哪些变量的现行值在寄存器中，再利用地址描述数组量的现行值在寄存器中，再利用地址描述数组AVALUEAVALUE来决定其中来决定其中哪些变量的现行值尚不在其内存单元中，最后利用活跃变量信息哪些变量的现行值尚不在其内存单元中，最后利用活跃变量信息来决定其中哪些变量是活跃的。例如，由例来决定其中哪些变量是活跃的。例如，由例7.27.2的表的表7.27.2查查RVALUERVALUE栏可知：栏可知：U U和和D D的值在寄存器中，而从的值在寄存器中，而从AVALUEAVALUE栏知栏知U U和和D D的值都不在的值都不在内存单元中，如果内存单元中，如果D D在基本块出口之后是活跃

30、变量，则在表在基本块出口之后是活跃变量，则在表7.27.2所所生成的目标代码后面还要生成一条目标代码：生成的目标代码后面还要生成一条目标代码：MOV D, AXMOV D, AX7.1.3 寄存器分配寄存器分配7.1.4 7.1.4 源程序到目标代码生成示例源程序到目标代码生成示例以以PCPC机的汇编语言作为目标代码，假定可用的寄存器为机的汇编语言作为目标代码，假定可用的寄存器为AXAX、BXBX、CXCX和和DXDX，则一则一C C语言源程序转换为四元式代码序列，然后再语言源程序转换为四元式代码序列，然后再转换为目标代码程序转换为目标代码程序( (转换中不考虑优化转换中不考虑优化) )的结果

31、如下：的结果如下：(1) (1) C C语言源程序语言源程序( (局部局部) )：while (ab)while (ab) if (m=n) a=a+1;if (m=n) a=a+1;elseelsewhile (k=h)while (k=h)x=x+2;x=x+2;m=n+xm=n+x* *(m+y);(m+y); (2) (2) 四元式代码序列：四元式代码序列：100 (j, a, b, 102)100 (j, a, b, 102)101 (j, _, _, 117 )101 (j, _, _, 117 )102 (j=, m, n, 104)102 (j=, m, n, 104)103

32、(j, _, _, 107 )103 (j, _, _, 107 )104 (+, a, 1, T104 (+, a, 1, T1 1) )105 (=, T105 (=, T1 1, _ , a ), _ , a )106 (j, _, _, 112)106 (j, _, _, 112)107 (j=, k, h, 109 )107 (j=, k, h, 109 )108 (j, _, _, 112)108 (j, _, _, 112)109 (+, x , 2, T109 (+, x , 2, T2 2 ) )110 (=, T110 (=, T2 2, _ , x ), _ , x )1

33、11 (j, _, _, 107 )111 (j, _, _, 107 )112 (+, m, y, T112 (+, m, y, T3 3) )113 (113 (* *, x, T, x, T3 3, T, T4 4 ) )114 (+, n , T114 (+, n , T4 4, T, T5 5) )115 (=, T115 (=, T5 5, _ , m ), _ , m )116 (j , _, _, 100)116 (j , _, _, 100)(3) (3) 目标代码程序目标代码程序( (汇编语言程序汇编语言程序) )：; File: ; File: compile.asmco

34、mpile.asm; ; * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *data segment ; data segment ; 定义数据段定义数据段 h h DWDW k k DW DW m m DWDW n n DWDW x x DWDW y y DWDW a a DWDW b b DWDWdata ends ; data ends ; 数据段定义结束数据段定义结束; ; * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *code segment code segment ; ; 定义代码段定义代码段main proc far