第九章 目标代码生成-20页PPT资料

删除公共 子表达式
t11=t2 x=a[t11] t12=t11 t13=t1 t14=a[t13] a[12]=t14 t14=t13 a[15]=x
在B1中t1=4*n;
目标代码生成
• 目标代码生成是编译最后一个阶段，它把 中间代码转换成汇编指令或可重定位的目 标代码。
• 对于语句 • x = y + z – m * 10; • 可以产生IBM PC汇编 指令
B6 t11=4*I x=a[t11] t12=4*I t13=4*n t14=a[t13] a[12]=t14 t14=4*n a[15]=x
t6=4*i x=a[t6] t7=4*i t8=4*j t9=a[t8] a[t7]=t9 t10=4*j a[t10]=x goto b2
B5
删除公共 子表达式
对中间代码进行变换加工以便在最后产生高效的目标代码
中间代码优化
• 对中间代码进行变换加工，以便在最后产 生高效的目标代码。
例：快速排序程序
Void quicksort(a,m,n); Int m,n,a[]; { int I,j; int v,x; if(n<=m) return; I=m-1;j=n;v=a[n] While(1){ Do {I=I+1;}while (a[I]<v); Do{j=j-1;}while(a[j]>v); If(I>=j)break; X=a[I];a[I]=a[j];a[j]=x; } X=a[I];a[I]=a[n];a[n]=x; Quicksort(m,j);quicksort(I+1,n); }
i=i+1 t2=4*i t3=a[t2] If t3<v goto B2 j=j-1 t4=4*j t5=a[t4] If t5<v goto B3 If I>=j goto b6

寄存器的使用准则
寄存器先行准则：尽可能把变量的值驻留到寄存器
中，尽可能用寄存器中的现行值，以减少访问内存
的次数。例：
1. (:=, 10, X) 2. (×, X, X, t1) 3. (-, X, t1, t2) 4. (:=, t2, X)
执行 1 后，把10装入到某寄存器
RX中，而不送到X的内存单元， 这样，2、3、4就可以直接从RX 中取值，而不用访问内存单元了
end GetReg
例：中间代码（三地址码）： (1) t1 := z * 6 (2) x := -4 (3) if x >= 76 goto (7) (4) x := x + 4 (5) y := t1 + x (6) goto (3)
指令种类
• 赋值 MOV • 比较 CMP • ≥转移 JLE • 转移 JMP • 累加 ADD • 相乘 MUL
寄存器的分配原则是选择代价最小的寄存器，这就涉 及到代价如何计算的问题。如果申请的是空闲寄存器，则 代价自然为0，否则属于剥夺性质。当一个寄存器R被剥夺 时，R的一些占有变量的现行值可能不在内存中，而且以后 可能引用，因此要产生一些回送现行值的Store指令（ST） 和重新装入寄存器的Load指令（LD）。则R的分配代价包括：
DL：取D（Dead）或 L（Live）。如果从K+1中间
代码开始，到A重新被赋值或基本块结束都没有引
用A，则A的DL值为D；否则为L。DL值在中间代码
步骤确定。例如：
1. (+，a，b，t1) 2. (-，t1，c，t2) 3. (×，t2，b，t3) 4. (:=，t3，x)
(+，D，L，L) (-ቤተ መጻሕፍቲ ባይዱD，D，L) (×，D，D，L) (:=，D，D)

● example
例1 请写出C function definition. 三地址码。 int f ( int x, int y ) { return x + y + 1; }
解：This will translate into the following three-address code:
entry f t1 = x + y t2 = t1 + 1 return t2
8.9 A Survey of Code Optimizations Techniques 代码优化技术考察
8.10 Simple Optimizations for the TINY Code Generator TINY代 码生成器的简单优化
8.1 Intermediate Code and Data Structures for Code Generation 中间代码和用于代码生成的数据结构
t2=fact*x
label L1
fact=t2
halt
解：Quadruple implementation for the three-address code
(rd, x , _ , _ ) (gt, x, 0, t1 ) (if_f, t1, L1, _ ) (asn, 1,fact, _ ) (lab, L2, _ , _ ) (mul, fact, x, t2 ) (asn, t2, fact, _ )
8.6 Code Generation in Commercial Compilers: Two Case Studies 商用编译器 中的代码生成：两个案例研究
8.7 TM: A Simple Target Machine TM：简单的目标机器 8.8 Code Generation for the Tiny Language TINY语言的代码生成器

• 代码优化在整个编译过程的位置
源程序 编译前端 中间代码 中间代码生成 中间代码 目标代码生成 目标程序 中间代码 中间代码优化 目标代码优化
程序员和编译器可能改上程序的位置
源程序 编译前端 中间代码 目标代码生成 目标程序
程序员可以改进 算法，改变循环
编译器可以改进过程调 用、循环和地址计算
编译器可以利用寄存器， 选择指令和窥孔优转换
3
7.1.1 数据类型
类型的合法性检查是判断数据类型是否与上下文的要求一致 数据类型是对该类型数据（变量或常量）的取值是否合法以 及对该类型数据的运算是否合法的一种说明。
4
7.1.2 数据结构
一个程序设计语言如允许使用的数组、记录、字符串、 表、栈等形式的数据结构，在编译程序中应为它们提供相 应的翻译。 为了能对数据结构中的元素进行引用，必须完成从逻辑结 构到能够访问这些数据元素的物理结构的映射。应考虑： １映射算法相对简单，根据逻辑结构容易计算出物理地址 ２从逻辑结构投影到物理结构时，不至于超界或存储溢出 ３使用的数据结构承担这种程序设计语言的主要功能 ４在这些数据结构定义相关的运算
25
• 指令选择
– 一个编译程序可以看成是一个转换系统，它把源程序转换成 等价的目标代码，也就是说，对源语言种各种语言结构，依 据语义确定相应的目标代码结构，即确定源语言于目标语言 之间的对应关系，确保正确实现语义。显然，能否建立这样 的关系直接影响到编译程序的质量。 – 目标机器指令系统的性质决定了指令选择的难以程度，指令 系统的一致性和完备性直接影响到这种对应关系的建立。如 果目标机器能一致地支持各种数据类型和寻址方式，不需特 别处理例外，这种对应关系的建立就容易得多。 – 指令执行速度和机器特点对产生目标代码的质量也十分重要。 显然，如果指令集合丰富的目标机器对于某种操作可提供集 中处理的时候，应该选择效率高、执行速度快的一种。