文档介绍：代码优化
第七章
本章要求
主要内容:代码优化的主要功能,局部优化、全局优化和循环优化的相关概念,各种优化技术
重点掌握:代码优化技术,基本块、流图、DAG的概念,必经结点、回边、循环的概念,各种优化技术。
代码优化所地位和作用:
概述
实际上很多地方可以对代码的执行效率进行改进,主要讲对中间代码的优化
代码优化:对程序进行等价变换,使得从变换后的程序出发,能够生成更有效的目标代码。
优化分类
按阶段分:
与机器无关的优化--对中间代码进行
依赖于机器的优化--对目标代码进行
根据优化所涉及的程序范围分成:
(1)局部优化:(基本块)
(2)循环优化:对循环中的代码进行优化
(3)全局优化:大范围的优化
优化的原则
等价原则:不改变运行结果
有效原则:优化后时间更短,占用空间更少
合算原则:应用较低的代价取得较好的优化效果
宗旨:
获得较好性能的代码(时间,空间)
等价
意图、结果之间要权衡
中间代码优化技术
优化工作
数据流分析(control-flow analysis)
控制流分析(data-flow analysis) 变换(transformations)
快速排序程序
void quicksort(int m,int n)
{ int i,j, 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);
}
(1) i :=m – 1
(2) j :=n
(3) T1:=4 * n
(4) v := a[T1]
(5) i := i + 1
(6) T2 := 4 * i
(7) T3 := a[T2]
(8) if T3 < v goto (5)
(9) j := j – 1
(10) T4 := 4 * j
(11) T5 := a[T4]
(12) if T5 > v goto (9)
(13) if i >= j goto (23)
(14) T6 := 4 * i
(15) x := a[T6]
(16) T7 := 4 * i
(17) T8 := 4 * j
(18) T9 := a[T8]
(19) a[T7] := T9
(20) T10 := 4 * j
(21) a[T10] := x
(22) goto (5)
(23) T11 := 4 * j
(24) x := a[T11]
(25) T12 := 4 * i
(26) T13 := 4 * n
(27) T14 := a[T13]
(28) a[T12] := T14
(29) T15 := 4 * n
(30) a[T15] := x
中间代码
基本块的优化
基本块:是指程序中一顺序执行的语句序列,其中只有一个入口语句和一个出口语句,入口是其第一个语句,出口是其最后一个语句
如果x:=y+z 则称对x定值, 引用y和z
在一个基本块内的一个名字, 在程序中的某个给定点是活跃的,是指如果在程序中它的值在该点之后被引用.
入口语句:
;或者,
(此处的转移语句包括各种控制的转向,如call,return,end,stop等) ;或者
。
执行:
对于一个基本块,执行时只能从其入口进入,从其出口退出