文档介绍：第九章代码优化
通过程序变换(局部变换和全局变换)来改进程序,称为优化
介绍独立于机器的优化,即不考虑任何依赖目标机器性质的优化变换
流图中循环的识别
数据流分析
代码改进变换
优化的主要种类
代码改进变换的标准
代码变换必须保程序的含义
采取安全稳妥的策略
变换减少程序的运行时间平均达到一个可度量的值
变换所作的努力是值得的
优化的主要种类
本节所用的例子
i = m 1; j = n; v = a[n]; (1) i := m 1
while (1) { (2) j := n
do i = i +1; while(a[i]<v); (3) t1 := 4 * n
do j =j 1;while (a[j]>v); (4) v := a[t1]
if (i >= j) break; (5) i := i + 1
x=a[i]; a[i]=a[j]; a[j]=x; (6) t2 := 4 * i
} (7) t3 := a[t2]
x=a[i]; a[i]=a[n]; a[n]=x; (8) if t3 < v goto (5)
优化的主要种类
本节所用的例子
i = m 1; j = n; v = a[n]; (9) j := j 1
while (1) { (10) t4 := 4 * j
do i = i +1; while(a[i]<v); (11) t5 := a[t4]
do j =j 1;while (a[j]>v); (12) if t5>v goto (9)
if (i >= j) break; (13) if i >=j goto (23)
x=a[i]; a[i]=a[j]; a[j]=x; (14) t6 := 4 * i
} (15 ) x := a[t6]
x=a[i]; a[i]=a[n]; a[n]=x; . . .
优化的主要种类
i := m 1
j := n
t1 := 4 * n
v := a[t1]
i := i + 1
t2 := 4 * i
t3 := a[t2]
if t3 < v goto B2
B1
B2
j := j 1
t4 := 4 * j
t5 := a[t4]
if t5 > v goto B3
if i >= j goto B6
B4
B3
B5
B6
优化的主要种类
公共子表达式删除
B5 x=a[i]; a[i]=a[j]; a[j]=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 x=a[i]; a[i]=a[j]; a[j]=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
t6 := 4 * i
x := a[t6]
t8 := 4 * j
t9 := a[t8]
a[t6] := t9
a[t8] := x
goto B2
优化的主要种类
B5 x=a[i]; a[i]=a[j]; a[j]=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
t6 := 4 * i
x := a[t6]
t8 := 4 * j
t9 := a[t8]
a[t6] := t9
a[t8] := x
goto B2
x := a[t2]
t9 := a[t4]
a[t2] := t9
a[t4] := x
goto B2