编译 第六章目标代码生成.ppt

第六章 目标代码生成,一 概述 1 目标代码的形式(1)能立即执行的目标代码；(2)待装配的浮动目标代码;(3)汇编语言目标代码.2 目标代码生成原则(1)生成的目标代码短而高效;(2)充分利用寄存器,减少访问内存的次数.,2,3,三 代码生成器及辅助信息 基本思想:当生成计算某变量值的目标代码时,尽量让该变量的值保存在某个寄存器中,直到该寄存器要用来存放其它变量的值或者基本块结束之前不再引用该变量的值,才把该变量的值存放到存储器中.为了能知道某变量的值是否在寄存器中,在那个寄存器中,是否该送回内存中等,需要一些辅助信息.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,表示不再引用,此时,应将非活跃变量的寄存器释放,存入内存中).,5,2 寄存器描述 假设系统可以使用的寄存器为:R1,R2,.,Rn 每个寄存器都需要描述是否被占用,被哪些变量占用?假设 RVALUE Ri 为集合类型,用于描述寄存器 Ri 的使用情况,也即哪些变量同时占用了 Ri.3 变量描述 在翻译过程中,应了解基本块中的每个变量的存储状况,确定变量的值是在寄存器中还是在内存中?假设 AVALUE A 为集合类型,用于描述变量 的存储情况:,AVALUE A=,Ri A的有效值在寄存器中;M A的有效值在内存中;Ri,M 均有效.,6,4 代码生成算法 下面,仅讨论一般情形 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,