编译原理课件(hdu)CHAPTER10(Code Generation)

2020/2/171Chapter10CodeGeneration代码生成器（CodeGenerator）运行时存储管理（Run-timestoragemanagement）关于寄存器分配（Registerallocation）简单代码生成算法（ACode-GenerationAlgorithm）2020/2/17210代码生成代码生成器P513Fig.9.1输入：（经优化后的）三地址代码、符号表输出：目标代码2020/2/17310代码生成目标代码的形式绝对机器语言代码都是绝对地址，放在内存的固定地方，可立即执行可重定位的机器语言代码可重定位的多个目标模块，需经连接装配，然后执行汇编语言代码生成比较容易，但需汇编2020/2/17410代码生成运行时存储管理上一讲内容的具体实现P522-528Fig.9.4—9.62020/2/17510代码生成关于寄存器分配只考虑在一个基本块内如何分配寄存器以提高代码的运行效率分配的原则：计算引用的变量值和计算结果尽量放在寄存器中，直到寄存器不够用在离开基本块前将寄存器的内容放到内存中在一个基本块内后边不再被引用的变量所占用的寄存器应尽早释放2020/2/17610代码生成下次引用信息：x在语句I中定值x能够到达J语句，J中引用了x称J是I中变量x的下次引用信息同时，称x在点I是活跃的（因为在后面会被引用）2020/2/17710代码生成获取基本块内每个变量的下次引用信息和活跃信息符号表中每个变量的记录项都有下次引用信息栏和活跃信息栏假设每个变量在出口处活跃，临时变量不活跃从基本块的出口处向前扫描每一条三地址语句具体步骤如下：2020/2/17810代码生成1、置初值，对每个变量置为“无下次引用”，“活跃”或“非活跃”2、从基本块出口向前扫描每条三地址代码（I：x:=yopz）(1)把变量x的下次引用信息和活跃信息附加到语句标号I上2020/2/17910代码生成(2)把变量x的下次引用信息栏和活跃信息栏分别置为“无下次引用”和“非活跃”(3)把变量y和z的下次引用信息和活跃信息附加到语句标号I上(4)把变量y和z的下次引用信息栏置为“I”，活跃信息栏置为“活跃”2020/2/171010代码生成例子：（P539）基本块含有下面四条代码，A、B、C、D是变量，T、U、V是临时变量（1）T:=A-B（2）U:=A-C（3）V:=T+U（4）D:=V+U2020/2/1711变量名下次引用信息活跃信息初值初值AF(2)(1)LLLBF(1)LLCF(2)LLDFFLFTF(3)FFLFUF(4)(3)FFLLFVF(4)FFLF2020/2/171210代码生成表中列从左向右变化是从后向前扫描三地址代码的结果，F表示“无下次引用”和“非活跃”，L表示“活跃”标记了下次引用信息和活跃信息的三地址代码：（1）T[(3)L]:=A[(2)L]–B[FL]（2）U[(3)L]:=A[FL]–C[FL]（3）V[(4)L]:=T[FF]+U[(4)L]（4）D[FL]:=V[FF]+U[FF]2020/2/171310代码生成简单代码生成算法只考虑一个基本块范围内的目标代码生成寄存器描述器（针对每个寄存器）——记录每个寄存器的当前内容地址描述器（针对每个运行时刻名字）——记录每个名字存放的一个或多个地址寄存器描述器和地址描述器的具体实现（采用何种数据结构）不考虑2020/2/171410代码生成算法：P537函数getregP538例子：P539example9.5Fig9.102020/2/1715