编译原理 优化
编译原理 优化
源程序 词法分析器 单词符号 出 表格管理 语法分析器 优化可在编译的 语法单位错备段进 优化是在目标代 中间代码生成器 码生成前,对语 四元式处 法分析得到的中 间代码进行的 优化段 与具体机器无关。 另一类重要的优 四元式 化是在生成目标 理代时进行的 与具体机器有关。 目标代码生成器 目标代码
词法分析器 语法分析器 中间代码生成器 优化段 源程序 单词符号 语法单位 四元式 表格管理 出错处理 目标代码生成器 四元式 目标代码 优化可在编译的 各个阶段进行。 但其中最主要的 优化是在目标代 码生成前，对语 法分析得到的中 间代码进行的， 与具体机器无关。 另一类重要的优 化是在生成目标 代码时进行的， 与具体机器有关
第十章优化 优化:对程序进行各种等价变换,使得从 变换后的程序出发,能生成更有效的目标 代码。 口等价:指不改变程序的运行结果。 口有效:指目标代码运行时间短,占用的存储空 间小。 编译前端 代码优化器 编译后端 控制流分析 数据流分析 代码变换 代码优化器的地位和结构
第十章 优化 ◼ 优化：对程序进行各种等价变换，使得从 变换后的程序出发，能生成更有效的目标 代码。 等价：指不改变程序的运行结果。 有效：指目标代码运行时间短，占用的存储空 间小。 编译前端 代码优化器 编译后端 控制流分析 数据流分析 代码变换 代码优化器的地位和结构
10.1概述 优化的目的是为了产生更高效的代码。由 优化编译程序提供的对代码的各种变换必 须遵循一定的原则: 口等价原则:经过优化后不应改变程序运行的 结果; 口有效原则:使优化后所产生的目标代码运行 时间较短,占用的存储空间较小; □合算原则:应尽可能以较低的代价取得较好 的优化效果
10.1 概述 ◼ 优化的目的是为了产生更高效的代码。由 优化编译程序提供的对代码的各种变换必 须遵循一定的原则： 等价原则：经过优化后不应改变程序运行的 结果； 有效原则：使优化后所产生的目标代码运行 时间较短，占用的存储空间较小； 合算原则：应尽可能以较低的代价取得较好 的优化效果
10.1概述 优化的三个不同级别: 局部优化 基于块的局部优化比较容易实现。 口循环优化 在程序的执行过程中,相当多的一部分时间花在 循环上,因此,循环优化比较重要 □全局优化 全局优化涉及整个程序的控制流和数据流分析, 因此实现代价较高
10.1 概述 ◼ 优化的三个不同级别： 局部优化 ◼ 基于块的局部优化比较容易实现。 循环优化 ◼ 在程序的执行过程中，相当多的一部分时间花在 循环上，因此，循环优化比较重要。 全局优化 ◼ 全局优化涉及整个程序的控制流和数据流分析， 因此实现代价较高
10.1概述 优化实施可从不同环节着手 1.源代码 选择合适的算法和实现语句,如排序时选择 快速排序比插入排序快。 2.设计语义动作 考虐产生更加高效的中间代码,并为后面的 代码优 如:在循环语句的头和尾对应的中间代码打上 标记,有助于后面的控制流和数据流分析:代 码的交叉处和交汇处也可以打上标记,以便子 识别程序流图中的直接前驱和直接后继。在 标代码 可以考虑怎样重复利用寄存器 选择指令;进行题式冼花季
10.1 概述 ◼ 优化实施可从不同环节着手 ◼ 1.源代码 ◼ 选择合适的算法和实现语句，如排序时选择 快速排序比插入排序快。 ◼ 2.设计语义动作 ◼ 考虑产生更加高效的中间代码，并为后面的 代码优化作准备。 ◼ 如：在循环语句的头和尾对应的中间代码打上 标记，有助于后面的控制流和数据流分析；代 码的交叉处和交汇处也可以打上标记，以便于 识别程序流图中的直接前驱和直接后继。在目 标代码这一级，可以考虑怎样重复利用寄存器， 如何选择指令，进行窥孔优化等
10.1概述 优化的种类(后面举例说明 □删除多余运算(或称删除公用子表达式) □复写传播 代码外提 □强度消弱 □变换循环控制条件 □合并已知量 □删除无用赋值
10.1 概述 ◼ 优化的种类（后面举例说明） 删除多余运算(或称删除公用子表达式) 复写传播 代码外提 强度消弱 变换循环控制条件 合并已知量 删除无用赋值
void quicksort(m,n);內快速排序 int m, n, int l, J5 int V, x; if(n≤=m) return fragment begins here*/ =m-1;j=n;v=a[n]; while(1)i do i=i+1; while(a [sv) if(>可 break; X=ac可=ai;a]=x; X=a[; at=a [ n; a [n=x /fragment ends here*/ d, quicksort(m, j); quicksort(i+1, n) 以下列出在两个 fragment直接代码的中间代码
void quicksort (m, n); /*快速排序*/ int m, n; { int i, j; int v, x; if (nv); if (i>=j) break; x=a [i]; a[i]=a [j]; a[j]=x; } x=a[i]; a[i]=a [n]; a [n]=x; /*fragment ends here*/ quicksort (m, j); quicksort (i+1, n); }以下列出在两个fragment直接代码的中间代码
i:=m-1 -n T1:=4n v:=aT B if i>=j goto B6 B4 i:=i+1 I2:=4*i x: =a T Bs x:=aTul T3: -aT 2 T:4 12 if T3v goto B 口中间代码程序段
❑中间代码程序段 i:=m-1 j:=n T1 :=4*n v:=a[T1 ] B1 i:=i+1 T2 :=4*i T3 :=a[T2 ] if T3v goto B3 B3 if i>=j goto B6 B4 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 T11:=4*i x:=a [T11] T12:=4*i T13:=4*n T14:=a [T13] a [T12]=T14 T15:= 4*n a [T15]=x B6
I-n J:=n T1:=4*n V:-a 匝 B ifi>= i goto B6」JB4 i:=i+1 64 1:=4*i I2:=4*i x:=a [ T6l B Bs x:=a, I-=4 5 6 a 12=4i ifT3v goto B3 口中间代码程序段 如果一个表达式E在前面已经计算过,并且之后E中变量的值没有改变,则称E 为公共子表达式。对公共子表达式可避免重复计算,称为删除公共子表达式
❑中间代码程序段 i:=m-1 j:=n T1 :=4*n v:=a[T1 ] B1 i:=i+1 T2 :=4*i T3 :=a[T2 ] if T3v goto B3 B3 if i>=j goto B6 B4 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 T11:=4*i x:=a [T11] T12:=4*i T13:=4*n T14:=a [T13] a [T12]=T14 T15:= 4*n a [T15]=x B6 如果一个表达式E在前面已经计算过，并且之后E中变量的值没有改变，则称E 为公共子表达式。对公共子表达式可避免重复计算，称为删除公共子表达式