编译原理--代码优化.pptVIP

第八章代码优化;8.1什么是代码优化;④变换循环控制条件：目的是删除那些纯粹为控制循环而设立的语句，因此又称删除归纳变量。

⑤合并量：对于那些编译时便可静态确定的运算结果事先运算出来，不必等到运行程序时再执行。

⑥复写传播：某些变量的值并未被改变，便赋给其他变量，那么可直接引用原值本身。

⑦删除无用赋值：有些变量在赋值后并未引用，却又被重新赋值了，称为无用赋值〔前面的赋值〕;3、优化分类;4、优化技术简介

1.删除多余运算

2.循环不变代码外提

3.强度削弱

4.变换循环控制条件

5.合并量与复写传播

6.删除无用赋值

例：

P:=0

forI:=1to20do

P:=P+A[I]*B[I];(1)P:=0

(2)I:=1

(3)T1:=4*I

(4)T2:=addr(A)-4

(5)T3:=T2[T1]

(6)T4:=4*I

(7)T5:=addr(B)-4

(8)T6:=T5[T4]

(9)T7:=T3*T6

(10)P:=P+T7

(11)I:=I+1

(12)ifI=20goto(3);;;;对程序以根本块为范围来讨论的优化，称为局部优化。

根本块：指程序中一顺序执行的语句序列，它只有一个入口语句和一个出口语句。

根本块的入口语句：

1.程序的第一个语句；或者，

2.条件转移语句或无条件转移语句的转移目标语句；或者

3.紧跟在条件转移语句后面的语句。;根本块的划分

1、求根本块入口语句

2、寻找根本块

⑴从入口语句到下一入口语句〔不包括该入口〕；

⑵从入口语句到下一转移语句〔包括转移语句〕；

⑶从入口语句到下一停止语句〔包括该停止语句〕。

3、根本块的整理

程序中所有根本块之外的语句为无用语句，应

删除。

根本块优化

在一个根本块内通常可实行三种优化：合并

量、删除无用赋值〔难判断〕以及删除多余运算。;例：

(1)read(C)

(2)A:=0

(3)B:=1

(4)L1:A:=A+B

(5)ifB=CgotoL2

(6)B:=B+1

(7)gotoL1

(8)L2:write(A)

(9)halt;2025/3/19;

根本块的DAG表示及其应用

;用;2025/3/19;2025/3/19;2025/3/19;例：;2025/3/19;2025/3/19;2025/3/19;2025/3/19;2025/3/19;2025/3/19;2025/3/19;2025/3/19;2025/3/19;控制流程图;2025/3/19;2025/3/19;2025/3/19;2025/3/19;;;循环的查找;8.4数据流分析;活泼变量的数据流分析;;;提取Def和LiveUse集合;从最后一个根本块开始由后往前计算，可以得到一定的解

LiveIn(B)=LiveUse(B)∪(LiveOut(B)-Def(B))

LiveOut(B)=∪LiveIn(i)i∈s(B);分析程序中所有变量的定值和引用之间的关系;2025/3/19;GEN;2025/3/19;2025/3/19;;2025/3/19;1;2025/3/19;B;B;当把循环中的不变运算s:A:=BopC外提时注意：;数据流问题的讨论合流问题;数据流问题的讨论路径问题;数据流问题的解不一定唯一;;例如，下面解是满足数据流方程的：