第十一章代码优化 11.1什么是代码优化 11.2局部优化 11.3控制流程分析和循环 11.4数据流分析举例
第十一章代码优化 11.1 什么是代码优化 11.2 局部优化 11.3 控制流程分析和循环 11.4 数据流分析举例
何谓代码优化: 宗旨:获得较好性能的代码 等价 意图,结果,权衡 阶段: source front >IR code target code end generator code 用户 中间代码优化 目标代码优化
何谓代码优化: 宗旨: 获得较好性能的代码 等价 意图,结果,权衡 阶段: source front I.R code target code end generator code 用户 中间代码优化 目标代码优化
int arr[10000]; int arr[10000]; void Binky(){ void Winky(){ int i; register int *p; for (i=0;i< for (p arr;p 10000;i++) arr+10000: arr[i]=1; p++) } *p=1; }
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)
优化技术简介一常数合并 a=10*5+6-b; tmp0=10; _tmp1=5; tmp2 tmp0 tmpl tmp3 =6 tmp4 tmp2 tmp3 tmp5 tmp4 b; a tmp5 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 ;
优化技术简介一常数传播 tmp4 =0; f0=0; f0 tmp4 i f1=1; tmp5 1; 1=2: f1 tmp5 i tmp6 =2 i=tmp6;
优化技术简介—常数传播 _tmp4 = 0 ; f0 = _tmp4 ; _tmp5 = 1 ; f1 = _tmp5 ; _tmp6 = 2 ; i = _tmp6 ; f0 = 0 ; f1 = 1 ; i = 2 ;
优化技术简介一代数简化 X+0=x 0+x= X X*1= X 1*x=X 0/x=0 X-0=X b &true =b b &falsefalse 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; _tmp0=5; _tmp1 tmpo a i tmp2 tmp1 10 b =tmp2 _tmp0=15; tmpl a tmpo
优化技术简介—代数简化 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=i+i=i<<2 b)i/2=(int)(i*0.5) 0)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
优化技术简介一复写传播 tmp2 tmpl tmp3 tmpl tmp3 tmp2* tmpl; tmpl tmp5 tmp3* tmp4 =tmp3 tmpl tmp5 tmp3* c tmp5 tmp3 tmp2 c tmp5 tmp4
优化技术简介—复写传播 tmp2 = tmp1 ; tmp3 = tmp2 * tmp1; tmp4 = tmp3 ; tmp5 = tmp3 * tmp2 ; c = tmp5 + tmp4 ; tmp3 = tmp1 * tmp1 ; tmp5 = tmp3 * tmp1 ; c = tmp5 + tmp3 ;