吉林大学编译原理八中间代码优化.PPTVIP

第八章 中间代码优化 主要内容: 优化方法概述 基本块划分 常量表达式优化 公共表达式优化 循环不变式外提 8.1 优化方法概述 优化的目标：提高程序的质量,尤其是程序的运行速度。 优化的要求： 1.优化要保证程序的正确性； 2.优化后要使程序的运行速度有数量级上的提高； 3.优化要适度.如：f(1,2,3) . 优化的对象：循环内下标变量地址的计算. 优化方法的分类： 编译阶段的优化 1.编译前端的中间代码级的优化：此阶段的优化独立于目标机，具有通用性和移植性; (1) 局部优化:基本块内的优化。 ①常表达式优化（合并常数项） ②公共表达式优化（消除重复操作） (2)非局部优化:涉及的范围比基本块要大。 ①循环上的优化:循环不变表达式外提; ②全局优化； 2.编译后端的目标代码级的优化 有效而合理地使用机器资源。 典型的优化方法 常量表达式优化(合并常数) v = a*b+c, 若a = 2, b=3, c=5 则可用v = 11替换; u = v +3; 替换成u=14; 公共子表达式节省(消除重复操作) t = b*c; e = b*c+b*c; c=b*c+10; d=b*c+d; t = b*c; e = t+t; c=t+10;d = b*c+d; 典型的优化方法 循环不变量式提 while (k10) {a[k] = b*c; k=k+1} t = b*c; while(k10){a[k]=t;k=k+1;} 8.2 基本块划分 基本块 基本块 标号性中间代码有： ( LABEL , — , — , L ) ( ENTRY , Label , Size , Level ) ( WHILE , — , — , —) ( ENDIF , — , — , —) 转移性中间代码有： ( JMP , — , — , L ) ( JMP1 , E , — , L ) ( JMP0 , E , — , L ) ( ENDPROC , — , — , — ) ( ENDFUNC , — , — , — ) ( THEN , E , — , — ) ( ELSE , — , — , —) ( DO , E , — , —) ( ENDWHILE , — , — , — ) 基于四元式中间代码基本块的划分： 初始四元式为第一个基本块的入口； 遇转移性中间代码时，结束当前基本块，并把该转移性中间代码作为当前基本块的出口，下一条代码作为新基本块的入口； 遇标号性代码结束当前基本块，代码本身作为新基本块的入口； 遇（ASSIG, A, n ，X）时，如果X为引用型形参时结束当前块，并作为该块的出口。 基本块划分的例子 设有源程序如下： y := 1 ; L: if A and B then x := 0 else y := 0 ; x := x + 1 ; y := y – 1 ; while x + y 0 do x := x - 1 ; z := 0 ; 注：x,y为非引用型整数类型形参。 基本块划分的例子 8.3 常表达式局部优化 常表达式：任何时候都取固定常数值的表达式。 处理思想：针对每个基本块，如果一个四元式的两 个分量的值已知，则由编译器将其值计 算出来，并用所求的值替换原来的运算结 果变量,并删掉相应的中间代码。 例:假设有下列语句： a := m + 10 ; b := a + m ; c := a + b – d ; 并假设当执行第一个语句时，m总是取常数10 ，则上列语句可优化如下： a := 20 ; b := 30 ; c := 50 – d ; 原理： 常量定值表ConstDef：表元素为二元组(Var,Val)。如果在ConstDef中有元素（V，c),表示变量此时一定取常数值c，在V被更改之前出现的V均可替换成c。 基本块上常量表达式的局部优化算法： 基本块入口置ConstDef为空； 读当前四元式； 对当前四元式的分量利用ConstDef表进行值代换得新四元式newtuple； 如果新多元式newtuple 形如（?，A, B，t): 若A和B是常数，则计算A?B的值v，并将（t,v）填入ConsDef表。删除当前四元式。 如果新多元式newtuple形如（ASSIG，A, -, B）: 如果A是常数，则把（B,A）填入ConsDef表，若已有B项， 只