资源描述
, , ,啊, , ,啊, , ,*,编译技术,*, , ,啊, , ,啊, , ,*,2004,年,12,月,28,日,*,代码优化,授课：胡静,代码优化授课：胡静,2024/8/14,编译技术,2,编译器的结构,出,错,处,理,语法分析程序,语义分析程序,目标代码生成程序,词法分析程序,中间代码生成程序,代码优化程序,表,格,管,理,2023/8/25编译技术2编译器的结构出语法分析程序语义分,2024/8/14,编译技术,3,概述,代码优化（,code optimization,）,指编译程序为了生成高质量的目标程序而做的各种加工和处理,目的：提高目标代码运行效率,时间效率（减少运行时间）,空间效率（减少内存容量）,原则：进行优化必须严格遵循“不能改变原有程序语义”原则。,2023/8/25编译技术3概述代码优化（code opti,2024/8/14,编译技术,4,代码优化分类,从优化的层次，与机器是否有关，分为：,独立于机器的优化：即与目标机无关的优化，通常是在中间代码上进行的优化。,与机器有关的优化：充分利用系统资源。（指令系统个，寄存器资源）。,从优化涉及的范围，分为：,局部优化：是指在基本块内进行的优化。,循环优化：对循环语句所生成的中间代码序列上所进行的优化。,全局优化：顾名思义，跨越多个基本块的全局范围内的优化。因此它是指在非线性程序段上（包括多个基本块，,GOTO,，循环）的优化。需要进行全局控制流和数据流分析，复杂。,2023/8/25编译技术4代码优化分类从优化的层次，与机器,2024/8/14,编译技术,5,优化所花费的代价和产生效果图,局部优化：只要做一些简单的处理便能得到明显的优化效果,循环优化：若要进一步提高优化效果，就要逐步付出更大的代价,全局优化：付出很大,代价，但是优化效果,不会非常明显,2023/8/25编译技术5优化所花费的代价和产生效果图局部,2024/8/14,编译技术,6,为什么要优化,有的大型计算程序一运行要花上几十分钟，甚至好几个小时，这时为优化即使付出些代价也是值得的,另外，程序中的循环往往要占用大量的计算时间。所以为减少循环执行时间所进行的优化对减少整个程序的运行时间有很大的意义,尤其对有实时要求的程序。如市场决策，供需及求益的平衡,至于简单的小程序（例如作业），或者在程序的调试阶段，花费许多代价去进行一遍一遍的优化就毫无必要了。,2023/8/25编译技术6为什么要优化有的大型计算程序一运,2024/8/14,编译技术,7,优化的基本方法,(1),优化应该是针对,中间代码或者目标代码,进行的，但此处为了说明方便，举例均为,源程序的形式,。,基本方法,1,：利用代数性质（代数变换）,编译时完成常量表达式的计算，整数类型与实数类型的转换,a:=5+6+x a:=11+x,设,x,为实型，,x:=3+1,可变换成,x:=4.0,下标变量引用时，其地址计算的一部分工作可以在编译时预先做好（运行时只需计算“可变部分”即可）,2023/8/25编译技术7优化的基本方法(1)优化应该是针,2024/8/14,编译技术,8,优化的基本方法,(2),基本方法,1,：利用代数性质（代数变换）,运算强度削弱：用一种需要较少执行时间的运算代替另一种运算，以减少运行时的运算强度，以及时空开销）,x2 x*x,3*x x+x+x,8*x, 4*x,等换成左移运算,x/2,，,x/16,等换成右移运算,x:=x+1 INC x,x/5 x*0.2,机器硬件提供的一些功能。,或者是和选择的指令集相关的功能。,2023/8/25编译技术8优化的基本方法(2)基本方法1：,2024/8/14,编译技术,9,优化的基本方法,(3),基本方法,2,：复写传播（,copy,）,复写语句：如,x:=y,这样的赋值语句称为复写语句。由于,x,和,y,值相同，所以当满足一定条件时，在该赋值语句下面出现的,x,可用,y,来代替，这就是复写传播。,例如,经过优化后，如果以后的语句中不再使用,x,，则,x:=y,可以删掉,2023/8/25编译技术9优化的基本方法(3)基本方法2：,2024/8/14,编译技术,10,优化的基本方法,(4),基本方法,2,：复写传播（,copy,）,如果上例中不是,x:=y,，而是,x:=3,，则复写传播变成了常量传播,常量传播会引起常量计算：,2023/8/25编译技术10优化的基本方法(4)基本方法2,2024/8/14,编译技术,11,优化的基本方法,(5),基本方法,3,：删除公共子表达式,具有相同值的子表达式在两个以上地方出现时，称它为共子表达式,(common sub-expression),可用,DAG,（,directed acyclic graph,有向无循环图）来表示具有公共子表达式的抽象语法树。,对公共子表达式只需要计算一次即可,2023/8/25编译技术11优化的基本方法(5)基本方法3,2024/8/14,编译技术,12,优化的基本方法,(6),基本方法,4,：删除冗余代码,冗余代码就是毫无实际意义的代码，又称死代码,(dead code),或无用代码,(useless code),。,2023/8/25编译技术12优化的基本方法(6)基本方法4,2024/8/14,编译技术,13,循环优化（,1,）,经验规则告诉我们：“程序运行时间的,80%,是由仅占源程序,20%,的部分执行的”。这,20%,的源程序就是循环部分，特别是多重循环的最内层的循环部分。因为减少循环部分的目标代码对提高整个程序的时间效率有很大作用。,2023/8/25编译技术13循环优化（1）经验规则告诉我们,2024/8/14,编译技术,14,循环优化（,1,）,经验规则告诉我们：“程序运行时间的,80%,是由仅占源程序,20%,的部分执行的”。这,20%,的源程序就是循环部分，特别是多重循环的最内层的循环部分。因为减少循环部分的目标代码对提高整个程序的时间效率有很大作用。,2023/8/25编译技术14循环优化（1）经验规则告诉我们,2024/8/14,编译技术,15,循环优化（,2,）,循环不变式的代码外提,不变表达式：不随循环控制变量改变而改变的表达式或子表达式。,2023/8/25编译技术15循环优化（2）循环不变式的代码,2024/8/14,编译技术,16,循环优化（,3,）,循环不变式的代码外提,不变表达式：不随循环控制变量改变而改变的表达式或子表达式。,2023/8/25编译技术16循环优化（3）循环不变式的代码,2024/8/14,编译技术,17,循环优化（,4,）,循环不变式的代码外提,如,如果,a,b,c,的值在改循环中不改变，则可将循环不变式移到循环之外，变为,从而可以减少计算次数,也称为频度削减,2023/8/25编译技术17循环优化（4）循环不变式的代码,2024/8/14,编译技术,18,循环优化（,5,）,循环展开：,它将构成循环体的代码（不包括控制循环的测试和转移部分），重复产生许多次（这可在编译时确定），而不仅仅是一次，以空间换时间。,2023/8/25编译技术18循环优化（5）循环展开：它将构,2024/8/14,编译技术,19,循环优化（,6,）,循环展开,循环一次执行,5,条语句才给一个变量赋初值。展开后，一条语句就能赋一个值，运行效率高。,优化在生成代码时进行，并不是修改源程序。,必须知道循环的终值，初值及步长。,但并不是所有展开都是合适的。如上例中循环展开后节省执行了转移和测试语句，但若循环体中不是一条而是,40,条语句，则展开后将有,40*30,条,=1200,，但省的仍是固定条数，就不算优化了。,2023/8/25编译技术19循环优化（6）循环展开,2024/8/14,编译技术,20,循环优化（,7,）,循环展开的实现步骤,1.,识别循环结构，确定循环的初值，终值和步长。,2.,判断。以空间换时间是否合算来决定是否展开。,3.,展开。重复产生循环体所需的代码个数。,2023/8/25编译技术20循环优化（7）循环展开的实现步,2024/8/14,编译技术,21,循环优化（,8,）,归纳变量的优化和条件判断的替换,归纳变量,(induction variable):,在每一次执行循环迭代的过程中，若某变量的值固定增加（或减少）一个常量值，则称该变量为归纳变量,(induction variable),。即若当前执行循环的第,j,次迭代。归纳变量的值应为,c*j+c,这里,c,和,c,都循环不变式。,2023/8/25编译技术21循环优化（8）归纳变量的优化和,2024/8/14,编译技术,22,循环优化（,9,）,归纳变量的优化和条件判断的替换,t1,、,t3,、,t6,都是归纳变量,2023/8/25编译技术22循环优化（9）归纳变量的优化和,2024/8/14,编译技术,23,循环优化（,10,）,其他循环优化方法,把多重嵌套的循环变成单层循环。,把,n,个相同形式的循环合成一个循环等。,in_line,展开,把过程（或函数）调用改为,in_line,展开可节省许多处理过程（函数）调用所花费的开销。,省去了函数调用时参数,压栈，保存返回地址等指,令。这也仅仅限于简单的,函数。,2023/8/25编译技术23循环优化（10）其他循环优化方,2024/8/14,编译技术,24,循环优化（,11,）,控制流方法：,2023/8/25编译技术24循环优化（11）控制流方法：,2024/8/14,编译技术,25,总结,2023/8/25编译技术25总结,2024/8/14,编译技术,26,Thanks for your time!,Questions & Answers,2023/8/25编译技术26,
展开阅读全文