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

第十一章代码优化 11.1什么是代码优化 11.2局部优化 11.3控制流程分析和循环 11.4数据流分析举例

第十一章代码优化 11．1 什么是代码优化 11．2 局部优化 11．3 控制流程分析和循环 11．4 数据流分析举例

何谓代码优化: 宗旨:获得较好性能的代码 等价 意图,结果,权衡 阶段: Source front LR code target code end generator code 用户 中间代码优化 目标代码优化

何谓代码优化： 宗旨： 获得较好性能的代码 等价 意图，结果，权衡 阶段： source front I.R code target code end generator code 用户 中间代码优化 目标代码优化

int arr[10000] int arr[10000] 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; }

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

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

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

优化技术简介—常数合并 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

优化技术简介一代数简化 b=5+a+10 tmpo=5 i tmpl= tmp t a i tmp2= tmp1 +10 i tmp i tmp0=15; tmpl =a tmpo i

优化技术简介—代数简化 b = 5 + a + 10 ; _tmp0 = 5 ; _tmp1 = _tmp0 + a ; _tmp2 = _tmp1 + 10 ; b = _tmp2 ; _tmp0 = 15 ; _tmp1 = a + _tmp0 ; b = _tmp1 ;

优化技术简介—降低运算强度 a)i大2=2大=立+i <<2 b)i/2=(int)(i*0.5) c)0-1=-1 d)f*2=2.0大f=f+f e)f/2.0=f+0.5

优化技术简介—降低运算强度 a) i*2 = 2*i = i+i = i<<2 b) i/2 = (int)(i*0.5) c) 0-1 = -1 d) f*2 = 2.0 * f = f + f e) f/2.0 = f*0.5

优化技术简介一复写传播 tmp =tmpl i tmp tmpl tmp3=tmp2大 tmpl tmpl tmp5=tmp3大 tmp = tmp3i tmpl i tmp 5 = tmp tmp5 tmp 3 tmp tmp5 t tmp 4

优化技术简介—复写传播 tmp2 = tmp1 ; tmp3 = tmp2 * tmp1; tmp4 = tmp3 ; tmp5 = tmp3 * tmp2 ; c = tmp5 + tmp4 ; tmp3 = tmp1 * tmp1 ; tmp5 = tmp3 * tmp1 ; c = tmp5 + tmp3 ;