清华大学：《编译原理》课程教学资源_第九章 代码优化

第9章代码优化 91代码优化概述 92局部优化 93控制流程分析和循环 94数据流分析举例

第9章 代码优化 9.1 代码优化概述 9.2 局部优化 9.3 控制流程分析和循环 9.4 数据流分析举例

9.1 何谓代码优化:为获得较好性能的代码而进行的变换 宗旨:等价变换 权衡(意图,结果) 阶段: Source front (LR) code—( target code end generator code 用户 中间代码优化 目标代码优化 代码优化的工作基础 数据流分析和控制流分析

9.1 何谓代码优化： 宗旨： 为获得较好性能的代码而进行的变换 等价变换 权衡 ( 意图，结果) 阶段： (source front (I.R) code ( target code) end generator code) 用户 中间代码优化 目标代码优化 代码优化的工作基础: 数据流分析和控制流分析

Diagram of the compilation process Source if(a>=b+1) program Lexical analysis Front end Syntax analysis (analysis) emantic analvsis Intermediate code gen Intermediate tl b+1 t2 representation a t1 if t2 goto LO IR optimization Back end (svnthesIs Object code gen Object code optimization Target 1d[8fp-16],s10 add810,1,10 program

直觉:哪个程序快?优化编译做到 样 int arr[10000] int arr[l0000]i void binkyo i void winky) i int li register int *pi for (l=0; i for (p=arr p< 10000;1++) arr+10000; arr l p++)

直觉:哪个程序快?—优化编译做到 一样. int arr[10000]; void Binky() { int i; for (i=0; i < 10000; i++) arr[i] = 1; } int arr[10000]; void Winky() { register int *p; for (p = arr; p < arr + 10000; p++) *p = 1; }

优化技术简介一常数合并 10*5+6-b; tmp =10i tmp1 =5 tmp tmpo x tmpl i tmp =6 tmp 4 tmp2+ tmp 3 i tmp tmp 4-bi tmp 5 i tmp0=56;

优化技术简介—常数合并 a = 10 * 5 + 6 - b; _tmp0 = 10 ; _tmp1 = 5 ; _tmp2 = _tmp0 * _tmp1 ; _tmp3 = 6 ; _tmp4 = _tmp2 + _tmp3 ; _tmp5 = _tmp4 – b; a = _tmp5 ; _tmp0 = 56 ;

优化技术简介—常数传播 tmp 4 =0 fo fO tmp 4 i f1 tmp 5 f1 tmp 5 tmp =2 i tmpb i

优化技术简介—常数传播 _tmp4 = 0 ; f0 = _tmp4 ; _tmp5 = 1 ; f1 = _tmp5 ; _tmp6 = 2 ; i = _tmp6 ; f0 = 0 ; f1 = 1 ; i = 2 ;

优化技术简介一代数化简 x+0 0+x Ⅹ大1= 1大 0/×=0 b & true = b b & false false b true = true b false b

优化技术简介—代数化简 x+0 = x 0+x = x x*1 = x 1*x = x 0/x = 0 x-0 = x b && true = b b && false = false b || true = true b || false = b

优化分类和优化工作 按阶段分: 表帶森盞的從化一对甘(潤娑 根据优化所涉及的程序范围分成 1)局部优化:(基本块) (2)循环优化:对循环中的代码进行优化 (3)全局优化:大范围的优化 优化工作 数据流分析(data- flow analysis) 控制流分析( controldata- flow analysis) 变换 transformations)

优化分类和优化工作 按阶段分: 与机器无关的优化---对中间代码进行 依赖于机器的优化--对目标代码进行 根据优化所涉及的程序范围分成: (1)局部优化:(基本块) (2)循环优化:对循环中的代码进行优化 (3)全局优化:大范围的优化 优化工作 数据流分析(data-flow analysis) 控制流分析(controldata-flow analysis) 变换 (transformations)

控制流分析 1)P:=0 (2)l:=1 3)T1:=4*I (4)T2:=adr(A)-4 (5)T3:=T2[T1 (6)T4=4I (7)Ts:=adr(B)-4 (8)T6:=T5[T4 (9)T7:=T3* (10)P:=P+T 7 (11)l:=I+1 (12)if K=20 goto(3)

控制流分析 (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)if I<=20 goto(3)

main() int xr y, Zi x=(1+20)大-× y =x*x+(x/y y=z=(x/y)/(x*x) 数据流分析 tmp1=1+20 X*xX/y tmp x =tmpl tmp2 tmp 3 tmp =x/y y tmp3 tmp 4 i tmp=x /y i tmp6=×x z tmp 5 /tmp i Z/

main() { int x, y, z; x = (1+20)* -x; y = x*x+(x/y); y = z = (x/y)/(x*x); } tmp1 = 1 + 20 ; tmp2 = -x ; x = tmp1 * tmp2 ; tmp3 = x * x ; tmp4 = x / y ; y = tmp3 + tmp4 ; tmp5 = x / y ; tmp6 = x * x ; z = tmp5 / tmp6 ; y = z ; 数据流分析 x*x x/y