3,循环优化
(1)代码外提
(2)强度削弱
?基本归纳变量, i有唯一定值, i,= i ?c
?同族归纳变量, j,= c1 ? i ? c2
则变成 j,= j ? c1 ? c,但 j必须在循环外赋初
值 j,＝ c1 * i ? c2
(3)删除归纳变量
即改用同族归纳变量作为判断条件
例如将 i > 10 改为 t3 > 100 + t1
因原来 t3,= 10 * i + t1,
而 100 ＋ t1 即 10 * 10 + t1
(1)i:=1
(2)if i>10 goto (16)
(3)t1:=2*j (4)t2:=10*i
(5)t3:=t2+t1 (6)t4:=a0-11
(7)t5:=2*j (8)t6:=10*i
(9)t7:=t6+t5 (10)t8:=a0-11
(11)t9:=t8[t7] (12)t10:=t9+1
(13)t4[t3]:=t10 (14)i:=i+1
(15)goto (2)
(16) …..,
优化之前 B1
B2
B3
B4
(1)i:=1
(4)t2:=10*i (5)t3:=t2+t1
(8)t6:=10*i (9)t7:=t6+t5
(11)t9:=t8[t7] (12)t10:=t9+1
(13)t4[t3]:=t10 (14)i:=i+1
(15)goto (2)
(16) …..,
(2)if i>10 goto (16)
(3)t1:=2*j (6)t4:=a0-11
(7)t5:=2*j (10)t8:=a0-11
代码外提后
B1
B2’
B2
B3
B4
(1)i:=1
(11)t9:=t8[t7] (12)t10:=t9+1
(13)t4[t3]:=t10 (14)i:=i+1
(4’)t2:=t2+10 (8’)t6:=t6+10
(5’)t3:=t3+10 (9’)t7:=t7+10
(15)goto (2)
(16) …..,
(2)if i>10 goto (16)
(3)t1:=2*j (6)t4:=a0-11
(7)t5:=2*j (10)t8:=a0-11
(4)t2:=10*i (8)t6:=10*i
(5)t3:=t2+t1 (9)t7:=t6+t5
强度削弱后 B1
B2’
B2
B3
B4
(1)i:=1
(11)t9:=t8[t7] (12)t10:=t9+1
(13)t4[t3]:=t10 (4’)t2:=t2+10
(8’)t6:=t6+10 (5’)t3:=t3+10
(9’)t7:=t7+10 (15)goto (2)
(16) …..,
(2’’)if t3>s goto (16)
(3)t1:=2*j (6)t4:=a0-11
(7)t5:=2*j (10)t8:=a0-11
(4)t2:=10*i (8)t6:=10*i
(5)t3:=t2+t1 (9)t7:=t6+t5
(2’)s:=100+t1
删除归纳变量后 B1
B2’
B2
B3
B4
另例,(1)PROD,= 0
(2)I,= 1
(3)T1,= 4 * I
(4)T2,= a0 – 4
(5)T3,= T2[T1]
(6)T4,= 4 * I
(7)T5,= b0 – 4
(8)T6,= T5[T4]
(9)T7,= T3 * T6
(10)PROD,= PROD + T7
(11)I,= I + 1
(12)if I ≤ 20 goto (3)
进行,(1)删除多余运算, 代码外提
(2)强度削弱
(3)变换循环控制条件, 复写传播, 合并已知量
(4)删除无用赋值
删除多余运算, 代码外提
(1)PROD,= 0
(2)I,= 1
(4)T2,= a0 – 4
(7) T5,= b0 – 4
(3) T1,= 4 * I
(5)T3,= T2[T1]
(6)T4,= T1
(8) T6,= T5[T4]
(9) T7,= T3 * T6
(10) PROD,= PROD + T7
(11) I,= I +1
(12)if I≤ 20 goto (3)
强度削弱
(1)PROD,= 0
(2)I,= 1
(4)T2,= a0 – 4
(7) T5,= b0 – 4
(3) T1,= 4 * I
(5)T3,= T2[T1]
(6)T4,= T1
(8) T6,= T5[T4]
(9) T7,= T3 * T6
(10) PROD,= PROD + T7
(11) I,= I +1
(3’)T1,= T1 + 4
(12) if I ≤ 20 goto (5)
变换循环控制条件, 合并已知量, 复写传播
(1)PROD,= 0
(2)I,= 1
(4)T2,= a0 – 4
(7) T5,= b0 – 4
(3) T1,= 4
(5)T3,= T2[T1]
(6)T4,= T1
(8) T6,= T5[T1]
(9) T7,= T3 * T6
(10) PROD,= PROD + T7
(11) I,= I +1
(3’)T1,= T1 + 4
(12) if T1 ≤ 80 goto (5)
删除无用赋值
(1)PROD,= 0
(4)T2,= a0 – 4
(7) T5,= b0 – 4
(3) T1,= 4
(5)T3,= T2[T1]
(8) T6,= T5[T4]
(9) T7,= T3 * T6
(10) PROD,= PROD + T7
(3’)T1,= T1 + 4
(12)if T1 ≤ 80 goto (5)
第四节 代码生成
1,代码生成的任务
将中间代码翻译成等价有效的目标代码
2,代码生成器的输入
中间代码，符号表
3,代码生成器的输出
目标代码 —— 绝对机器代码，可重定
位代码或汇编码
4,抽象机的指令形式
op 源, 目的
其中 op是操作码；源和目的是两个操作对象,
可以是内存地址, 寄存器或常数
（ 1） 直接地址型
op Ri,M (Ri) op (M) => Ri
（ 2） 寄存器型
op Ri,Rj (Ri) op (Rj) => Ri
（ 3） 变址型
op Ri,C(Rj) (Ri) op ((Rj) + C) => Ri
（ 4） 间接型
op Ri,*Rj (Ri) op ((Rj)) => Ri
op Ri,*M (Ri) op ((M)) => Ri
op Ri,*C(Rj) (Ri) op (((Rj) + C)) => Ri
（ 5） 其它几种常用指令
MOV Ri,M (Ri) => M
MOV M,Ri (M) => Ri
J x goto x
CMP A,B 比较 A 和 B, 设定 CJ
A < B 设 C J = 0
A = B 设 C J = 1
A > B 设 C J = 2
J rop x rop 与 C J 一致时, goto x
否则顺序执行下一指令
5,简单的代码生成方法
(1)p,x:= y op z 的翻译
MOV y,Ri
op Ri,z
结果 （ x 的值 ） 在寄存器 Ri中
(2)为 x 分配寄存器的方法
?y 本身占有寄存器 Ri，且 y在 p点后不再被
引用
?有空余的可用寄存器 Ri
?寄存器均被占用：保存副本，选择一
个 ——最好选择占用 Ri的变量在主存中已
有副本的；或者在 p点后该变量不再被引
用的；或者在离 p点最远处才被引用的。
举例,t,= a － b MOV a,R0
u,= a + c SUB R0,b
v,= a － t 翻译成 MOV a,R1
w,= v + u ADD R1,c
假设可用寄存器为 R0,R1 MOV R1,u
MOV a,R1
SUB R1,R0
MOV R1,v
ADD R1,u
6,循环中的寄存器的分配
(1)指令的执行代价
—— 该指令访问主存的次数
寄存器型 op Ri,Rj 执行代价为 1
直接地址型 op Ri,M 执行代价为 2
变址型 op Ri,C(Rj) 执行代价为 2
间址型 op Ri,*Rj 执行代价为 2
op Ri,*M 执行代价为 3
op Ri,*C(Rj) 执行代价为 3
(2)循环中某变量被固定分配了寄存器
后, 两种节省执行代价的情形,
(I)设 USE ( x,B ) 为 x在 B 中被定值前
的引用次数, 则循环 L执行一次, 可
省的执行代价为
?USE(x,B) B?L
(II)对基本块中定值基本块后的活跃变
量 x,省去指令 MOV Ri,Mx,可省
执行代价
?(2*LIVE(x,B))
由 （ I）,(II) 可得, 总共省的执行代价
?(USE(x,B)+2*LIVE(x,B))
B?L
B?L
a:=b+c
d:=d-b
e:=a+f
f:=a-d b:=d+f
e:=a-c
b:=d+c
acdef
cdef
bcdef
bcdef
B1
B2 B3
B4
例,
B1
B2
B3
B4
?
a b c d e f
1
1
2 2
2
2
1
1
1
1
1
1
1
2 2
2
1
2
1
4 6 3 6 4 4
若有三个可固定分配的寄存器,则 b,d可固定分配寄存器,
另一个分配给 a,e,f中的一个
第六章习题
6-1,6-2,6-3,6-5,6-7
第七章 运行时存储空间管理
第一节 变量及存储分配
程序投入运行的必要条件,
?一组可运行的代码
?一个运行环境：分配空间、提供运行信
息
一, 程序的存储空间
1,代码空间, 线性存放着目标指令序列
在 GAM中,当前执行的指令位置由指
令指针 ip指示。
2,数据空间
(1)内容, 变量、常数、控制和管理信
息、描述符等
(2)静态分配, 在运行前就可确定数据
空间的大小,在编译时刻就能进行的存储
分配
(3)动态分配, 运行时才能进行的存储
分配
?栈分配, 因变量生存期的嵌套性
?堆分配, 因生存期的随机交叉特性
二, 活动记录
一个程序单元的一次激活所需的信息管
理是通过相应的活动记录来实施的。一
个单元的每次激活，都应建立相应的活
动记录，它是单元实例的一部分。
1,活动记录的内容
(1)返回地址
(2)动态链和静态链
(3)形式单元
(4)局部变量或其描述符，以及临时变
量
返回地址
动态链
静态链
变量存储区
形式单元
2,活动记录的特点
除了变量存储区外,其余部分存储长
度编译时可以确定,则元素 i的地址可用下
式计算
D+offset(i)
其中,offset(i)是 i在活动记录中的位移 ; D是
活动记录的首地址
三, 变量的存储分配
1,静态变量, 不管在程序单元的哪一次
活动中,均绑定于相同的存储位置
条件是, 活动记录,变量的存储位置在
编译时可以确定
2,半静态变量, 编译时确定相对位置,
单元被激活后,x绑定于 D+offset(x)
条件是, 语言允许递归调用
3,半动态变量, 动态数组 ; 编译时在活
动记录中建立描述符
例, [1..m] int a;
[1..n] int b;
4,动态变量, 动态分配。编译时在活动
记录中为动态变量设置二个指针,一个指
向该变量的描述符,另一个指向该变量的
存储空间
四, 存储分配模式
1,静态分配
只允许静态变量,变量与存储区域的
绑定关系在编译时便可建立,并完成存储
分配。
不允许递归调用,不允许动态数组,不
允许动态类型的数据对象,即不允许有非
静态变量。如, FORTRAN语言。
2,栈式分配
?各单元之间的调用关系遵循“后进先出”
模式 ;
?活动记录的建立和撤消也满足“后进先
出”模式 ;
?用栈分配活动记录 ;
?分配方法, 当激活一个程序单元时,其活
动记录就动态地分配于栈顶。
R的活动记录
Q的活动记录
P的活动记录
如,P调用 Q,Q调用 R
..,
..,
..,
3,堆分配
由于动态变量表示的数据对象,它的长度、
个数都有可能在执行中改变,即在其生存期中
动态改变,就不可能在栈上为这样的对象作分
配。
出现下列情况时,必须用堆式分配,
(1)单元活动结束后,局部变量的值还需保留 ;
(2)调用单元与被调用单元的生存期不满足
嵌套关系,即出现交叉现象。
4,存储空间的组织
代码
静态数据
栈
堆
(1)代码外提
(2)强度削弱
?基本归纳变量, i有唯一定值, i,= i ?c
?同族归纳变量, j,= c1 ? i ? c2
则变成 j,= j ? c1 ? c,但 j必须在循环外赋初
值 j,＝ c1 * i ? c2
(3)删除归纳变量
即改用同族归纳变量作为判断条件
例如将 i > 10 改为 t3 > 100 + t1
因原来 t3,= 10 * i + t1,
而 100 ＋ t1 即 10 * 10 + t1
(1)i:=1
(2)if i>10 goto (16)
(3)t1:=2*j (4)t2:=10*i
(5)t3:=t2+t1 (6)t4:=a0-11
(7)t5:=2*j (8)t6:=10*i
(9)t7:=t6+t5 (10)t8:=a0-11
(11)t9:=t8[t7] (12)t10:=t9+1
(13)t4[t3]:=t10 (14)i:=i+1
(15)goto (2)
(16) …..,
优化之前 B1
B2
B3
B4
(1)i:=1
(4)t2:=10*i (5)t3:=t2+t1
(8)t6:=10*i (9)t7:=t6+t5
(11)t9:=t8[t7] (12)t10:=t9+1
(13)t4[t3]:=t10 (14)i:=i+1
(15)goto (2)
(16) …..,
(2)if i>10 goto (16)
(3)t1:=2*j (6)t4:=a0-11
(7)t5:=2*j (10)t8:=a0-11
代码外提后
B1
B2’
B2
B3
B4
(1)i:=1
(11)t9:=t8[t7] (12)t10:=t9+1
(13)t4[t3]:=t10 (14)i:=i+1
(4’)t2:=t2+10 (8’)t6:=t6+10
(5’)t3:=t3+10 (9’)t7:=t7+10
(15)goto (2)
(16) …..,
(2)if i>10 goto (16)
(3)t1:=2*j (6)t4:=a0-11
(7)t5:=2*j (10)t8:=a0-11
(4)t2:=10*i (8)t6:=10*i
(5)t3:=t2+t1 (9)t7:=t6+t5
强度削弱后 B1
B2’
B2
B3
B4
(1)i:=1
(11)t9:=t8[t7] (12)t10:=t9+1
(13)t4[t3]:=t10 (4’)t2:=t2+10
(8’)t6:=t6+10 (5’)t3:=t3+10
(9’)t7:=t7+10 (15)goto (2)
(16) …..,
(2’’)if t3>s goto (16)
(3)t1:=2*j (6)t4:=a0-11
(7)t5:=2*j (10)t8:=a0-11
(4)t2:=10*i (8)t6:=10*i
(5)t3:=t2+t1 (9)t7:=t6+t5
(2’)s:=100+t1
删除归纳变量后 B1
B2’
B2
B3
B4
另例,(1)PROD,= 0
(2)I,= 1
(3)T1,= 4 * I
(4)T2,= a0 – 4
(5)T3,= T2[T1]
(6)T4,= 4 * I
(7)T5,= b0 – 4
(8)T6,= T5[T4]
(9)T7,= T3 * T6
(10)PROD,= PROD + T7
(11)I,= I + 1
(12)if I ≤ 20 goto (3)
进行,(1)删除多余运算, 代码外提
(2)强度削弱
(3)变换循环控制条件, 复写传播, 合并已知量
(4)删除无用赋值
删除多余运算, 代码外提
(1)PROD,= 0
(2)I,= 1
(4)T2,= a0 – 4
(7) T5,= b0 – 4
(3) T1,= 4 * I
(5)T3,= T2[T1]
(6)T4,= T1
(8) T6,= T5[T4]
(9) T7,= T3 * T6
(10) PROD,= PROD + T7
(11) I,= I +1
(12)if I≤ 20 goto (3)
强度削弱
(1)PROD,= 0
(2)I,= 1
(4)T2,= a0 – 4
(7) T5,= b0 – 4
(3) T1,= 4 * I
(5)T3,= T2[T1]
(6)T4,= T1
(8) T6,= T5[T4]
(9) T7,= T3 * T6
(10) PROD,= PROD + T7
(11) I,= I +1
(3’)T1,= T1 + 4
(12) if I ≤ 20 goto (5)
变换循环控制条件, 合并已知量, 复写传播
(1)PROD,= 0
(2)I,= 1
(4)T2,= a0 – 4
(7) T5,= b0 – 4
(3) T1,= 4
(5)T3,= T2[T1]
(6)T4,= T1
(8) T6,= T5[T1]
(9) T7,= T3 * T6
(10) PROD,= PROD + T7
(11) I,= I +1
(3’)T1,= T1 + 4
(12) if T1 ≤ 80 goto (5)
删除无用赋值
(1)PROD,= 0
(4)T2,= a0 – 4
(7) T5,= b0 – 4
(3) T1,= 4
(5)T3,= T2[T1]
(8) T6,= T5[T4]
(9) T7,= T3 * T6
(10) PROD,= PROD + T7
(3’)T1,= T1 + 4
(12)if T1 ≤ 80 goto (5)
第四节 代码生成
1,代码生成的任务
将中间代码翻译成等价有效的目标代码
2,代码生成器的输入
中间代码，符号表
3,代码生成器的输出
目标代码 —— 绝对机器代码，可重定
位代码或汇编码
4,抽象机的指令形式
op 源, 目的
其中 op是操作码；源和目的是两个操作对象,
可以是内存地址, 寄存器或常数
（ 1） 直接地址型
op Ri,M (Ri) op (M) => Ri
（ 2） 寄存器型
op Ri,Rj (Ri) op (Rj) => Ri
（ 3） 变址型
op Ri,C(Rj) (Ri) op ((Rj) + C) => Ri
（ 4） 间接型
op Ri,*Rj (Ri) op ((Rj)) => Ri
op Ri,*M (Ri) op ((M)) => Ri
op Ri,*C(Rj) (Ri) op (((Rj) + C)) => Ri
（ 5） 其它几种常用指令
MOV Ri,M (Ri) => M
MOV M,Ri (M) => Ri
J x goto x
CMP A,B 比较 A 和 B, 设定 CJ
A < B 设 C J = 0
A = B 设 C J = 1
A > B 设 C J = 2
J rop x rop 与 C J 一致时, goto x
否则顺序执行下一指令
5,简单的代码生成方法
(1)p,x:= y op z 的翻译
MOV y,Ri
op Ri,z
结果 （ x 的值 ） 在寄存器 Ri中
(2)为 x 分配寄存器的方法
?y 本身占有寄存器 Ri，且 y在 p点后不再被
引用
?有空余的可用寄存器 Ri
?寄存器均被占用：保存副本，选择一
个 ——最好选择占用 Ri的变量在主存中已
有副本的；或者在 p点后该变量不再被引
用的；或者在离 p点最远处才被引用的。
举例,t,= a － b MOV a,R0
u,= a + c SUB R0,b
v,= a － t 翻译成 MOV a,R1
w,= v + u ADD R1,c
假设可用寄存器为 R0,R1 MOV R1,u
MOV a,R1
SUB R1,R0
MOV R1,v
ADD R1,u
6,循环中的寄存器的分配
(1)指令的执行代价
—— 该指令访问主存的次数
寄存器型 op Ri,Rj 执行代价为 1
直接地址型 op Ri,M 执行代价为 2
变址型 op Ri,C(Rj) 执行代价为 2
间址型 op Ri,*Rj 执行代价为 2
op Ri,*M 执行代价为 3
op Ri,*C(Rj) 执行代价为 3
(2)循环中某变量被固定分配了寄存器
后, 两种节省执行代价的情形,
(I)设 USE ( x,B ) 为 x在 B 中被定值前
的引用次数, 则循环 L执行一次, 可
省的执行代价为
?USE(x,B) B?L
(II)对基本块中定值基本块后的活跃变
量 x,省去指令 MOV Ri,Mx,可省
执行代价
?(2*LIVE(x,B))
由 （ I）,(II) 可得, 总共省的执行代价
?(USE(x,B)+2*LIVE(x,B))
B?L
B?L
a:=b+c
d:=d-b
e:=a+f
f:=a-d b:=d+f
e:=a-c
b:=d+c
acdef
cdef
bcdef
bcdef
B1
B2 B3
B4
例,
B1
B2
B3
B4
?
a b c d e f
1
1
2 2
2
2
1
1
1
1
1
1
1
2 2
2
1
2
1
4 6 3 6 4 4
若有三个可固定分配的寄存器,则 b,d可固定分配寄存器,
另一个分配给 a,e,f中的一个
第六章习题
6-1,6-2,6-3,6-5,6-7
第七章 运行时存储空间管理
第一节 变量及存储分配
程序投入运行的必要条件,
?一组可运行的代码
?一个运行环境：分配空间、提供运行信
息
一, 程序的存储空间
1,代码空间, 线性存放着目标指令序列
在 GAM中,当前执行的指令位置由指
令指针 ip指示。
2,数据空间
(1)内容, 变量、常数、控制和管理信
息、描述符等
(2)静态分配, 在运行前就可确定数据
空间的大小,在编译时刻就能进行的存储
分配
(3)动态分配, 运行时才能进行的存储
分配
?栈分配, 因变量生存期的嵌套性
?堆分配, 因生存期的随机交叉特性
二, 活动记录
一个程序单元的一次激活所需的信息管
理是通过相应的活动记录来实施的。一
个单元的每次激活，都应建立相应的活
动记录，它是单元实例的一部分。
1,活动记录的内容
(1)返回地址
(2)动态链和静态链
(3)形式单元
(4)局部变量或其描述符，以及临时变
量
返回地址
动态链
静态链
变量存储区
形式单元
2,活动记录的特点
除了变量存储区外,其余部分存储长
度编译时可以确定,则元素 i的地址可用下
式计算
D+offset(i)
其中,offset(i)是 i在活动记录中的位移 ; D是
活动记录的首地址
三, 变量的存储分配
1,静态变量, 不管在程序单元的哪一次
活动中,均绑定于相同的存储位置
条件是, 活动记录,变量的存储位置在
编译时可以确定
2,半静态变量, 编译时确定相对位置,
单元被激活后,x绑定于 D+offset(x)
条件是, 语言允许递归调用
3,半动态变量, 动态数组 ; 编译时在活
动记录中建立描述符
例, [1..m] int a;
[1..n] int b;
4,动态变量, 动态分配。编译时在活动
记录中为动态变量设置二个指针,一个指
向该变量的描述符,另一个指向该变量的
存储空间
四, 存储分配模式
1,静态分配
只允许静态变量,变量与存储区域的
绑定关系在编译时便可建立,并完成存储
分配。
不允许递归调用,不允许动态数组,不
允许动态类型的数据对象,即不允许有非
静态变量。如, FORTRAN语言。
2,栈式分配
?各单元之间的调用关系遵循“后进先出”
模式 ;
?活动记录的建立和撤消也满足“后进先
出”模式 ;
?用栈分配活动记录 ;
?分配方法, 当激活一个程序单元时,其活
动记录就动态地分配于栈顶。
R的活动记录
Q的活动记录
P的活动记录
如,P调用 Q,Q调用 R
..,
..,
..,
3,堆分配
由于动态变量表示的数据对象,它的长度、
个数都有可能在执行中改变,即在其生存期中
动态改变,就不可能在栈上为这样的对象作分
配。
出现下列情况时,必须用堆式分配,
(1)单元活动结束后,局部变量的值还需保留 ;
(2)调用单元与被调用单元的生存期不满足
嵌套关系,即出现交叉现象。
4,存储空间的组织
代码
静态数据
栈
堆
