1第八章第八章 目标代码生成目标代码生成一一 概述概述 1 目标代码的形式目标代码的形式 (1)能立即执行的目标代码；能立即执行的目标代码；(2)待装配的浮动目标代码待装配的浮动目标代码;(3)汇编语言目标代码汇编语言目标代码.2 目标代码生成原则目标代码生成原则 (1)生成的目标代码短而高效生成的目标代码短而高效;(2)充分利用寄存器充分利用寄存器,减少访问内存的次数减少访问内存的次数.2二二 计算机模型计算机模型 假设计算机只有四种类型的机器指令假设计算机只有四种类型的机器指令:指令类型指令类型 指令形式指令形式意义意义直接地址型直接地址型 op Ri,M(Ri)op(M)Ri寄存器型寄存器型 op Ri,Rj(Ri)op(Rj)Ri变址型变址型 op Ri,C(Rj)(Ri)op(Rj)+C)Ri间址型间址型 op Ri,*M(Ri)op(M)Ri op Ri,*Rj(Ri)op(Rj)Ri op Ri,*C(Rj)(Ri)op(Rj)+C)Ri3三三 代码生成器及辅助信息代码生成器及辅助信息 基本思想基本思想:当生成计算某变量值的目标代码时当生成计算某变量值的目标代码时,尽量让该变量尽量让该变量的值保存在某个寄存器中的值保存在某个寄存器中,直到该寄存器要用来存放其它变量的值直到该寄存器要用来存放其它变量的值或者基本块结束之前不再引用该变量的值或者基本块结束之前不再引用该变量的值,才把该变量的值存放才把该变量的值存放到存储器中到存储器中.为了能知道某变量的值是否在寄存器中为了能知道某变量的值是否在寄存器中,在那个寄存器中在那个寄存器中,是是否该送回内存中等否该送回内存中等,需要一些辅助信息需要一些辅助信息.1 待用信息待用信息 当翻译到四元式当翻译到四元式 A:=B op C 时时,我们需要知道基本块内后面我们需要知道基本块内后面的四元式是否还引用的四元式是否还引用 A B C,是哪些四元式引用是哪些四元式引用?定义定义:设四元式设四元式(i)对对A定值且到达四元式定值且到达四元式(j),四元式四元式(j)中引用中引用 A,则称则称 j 是四元式是四元式 i 的变量的变量A 的的待用信息待用信息;满足上述定义满足上述定义 的所有的所有 j,构成了构成了 A 的的待用信息集待用信息集.4采用如下方式表示待用信息集采用如下方式表示待用信息集,为每个四元式建立一个如下的表项为每个四元式建立一个如下的表项:定值名定值名 指针指针 引用名引用名1 指针指针 引用名引用名2 指针指针 A *B *C *A *B Nil C Nil 通过链表把通过链表把 A 的所有待用信息连接起来的所有待用信息连接起来.当执行到当执行到 A:=B op C时时,就可以检查待用信息链就可以检查待用信息链,确定确定 A B C 在该四元式之后是否还引在该四元式之后是否还引用用(若为若为 Nil,表示不再引用表示不再引用,此时此时,应将非活跃变量的寄存器释放应将非活跃变量的寄存器释放,存入内存中存入内存中).52 寄存器描述寄存器描述 假设系统可以使用的寄存器为假设系统可以使用的寄存器为:R1,R2,.,Rn 每个寄存器都需要描述是否被占用每个寄存器都需要描述是否被占用,被哪些变量占用被哪些变量占用?假设假设 RVALUE Ri 为集合类型为集合类型,用于描述寄存器用于描述寄存器 Ri 的使用情况的使用情况,也即哪些变量同时占用了也即哪些变量同时占用了 Ri.3 变量描述变量描述 在翻译过程中在翻译过程中,应了解基本块中的每个变量的存储状况应了解基本块中的每个变量的存储状况,确定确定变量的值是在寄存器中还是在内存中变量的值是在寄存器中还是在内存中?假设假设 AVALUE A 为集合类型为集合类型,用于描述变量用于描述变量 的存储情况的存储情况:AVALUE A=Ri A的有效值在寄存器中的有效值在寄存器中;M A的有效值在内存中的有效值在内存中;Ri,M 均有效均有效.64 代码生成算法代码生成算法 下面下面,仅讨论一般情形仅讨论一般情形 A:=B op C 的代码翻译的代码翻译,GetReg(A:=B op C)函数返回一个寄存器函数返回一个寄存器 R,存放变量存放变量 A的值的值.代码生成算法代码生成算法:(对四元式对四元式 A:=B op C)(1)令令 R=GetReg(A:=B op C);(2)由由 AVALUE A ,AVALUE B 确定确定 变量变量 B C 值的有值的有 效存储位置效存储位置 B,C (3)若若 B=R 生成生成 机器指令机器指令 op B,C 否则否则 生成机器指令生成机器指令 mov R,B op R,C 若若 B=R,则删除则删除 AVALUE B 中的中的 R;若若 C=R,则删除则删除 AVALUE C 中的中的 R;令令 AVALUE A =R;RVALUE R=A;7 (4)若若 B 的值在基本块内不再引用的值在基本块内不再引用,且且 AVALUE B=Ri 则产生目标指令则产生目标指令:mov Ri,B;删除删除 AVALUE B 中的中的 Ri;删除删除 RVALUE Ri 中的中的 B;/释放寄存器释放寄存器 Ri.(5)若若 C 的值在基本块内不再引用的值在基本块内不再引用,且且 AVALUE C=Ri 则产生目标指令则产生目标指令:mov Ri,C;删除删除 AVALUE C 中的中的 Ri;删除删除 RVALUE Ri 中的中的 C;/释放寄存器释放寄存器 Ri.(6)返回返回8 5 GetReg(A:=B op C)算法算法(1)若若 B 的值在的值在 R 中中,且且 RVALUER 只含只含 B,且且 (A=B 或或 B 的值在基本块内不再引用并且的值在基本块内不再引用并且 B 的值已存的值已存 入内存中入内存中)则则 return(R);(2)否则否则,若有尚未分配的若有尚未分配的 R 则则 return(R);(3)否则否则,从已分配的寄存器中选择一从已分配的寄存器中选择一 R,for(RVALUE R 中的每一变量中的每一变量 V)do 若若 V 的值不在内存中的值不在内存中,则则 Mov V,R;AVALUE V=M;RVALUE R=;return(R)9。