第六章代码优化.ppt

2020 1 21 第六章 代码优化 1 第5章主要内容回顾 属性文法中间代码的形式四元式 也称为三地址代码 赋值语句的翻译布尔表达式的翻译控制流语句的翻译 2020 1 21 第六章 代码优化 2 第六章代码优化 优化技术概述基本块与局部优化控制流分析和循环优化数据流分析与优化 略 本章主要内容 2020 1 21 第六章 代码优化 3 6 1概述 代码优化编译时刻为改进目标程序的质量而进行的各项工作质量的改进 包括提高目标程序的时间效率和空间效率代码优化进行的是等价变换优化不能改变程序对给定输入的输出 也不能引起源程序原先不会出现的新错误变换所作的努力是值得的编译器优化源程序的额外开销应能从目标程序的运行中得到补偿 源代码 前端 中间代码 代码生成 目标代码 中间代码优化 目标代码优化 2020 1 21 第六章 代码优化 4 6 1概述 代码优化的分类依据是否与机器相关分 与机器相关的优化1 在目标代码生成之后进行 针对的是目标代码2 内容 寄存器优化 多处理器优化 特殊指令优化 无用指令消除等与机器无关的优化1 在中间代码生成之后进行 针对的是中间代码2 与机器无关的优化更具有普遍意义 可以适用于多种物理机器的代码生成程序依据优化所涉及的程序范围分 局部优化 针对基本程序块循环优化 针对循环体全局优化 针对整个程序 2020 1 21 第六章 代码优化 5 6 1概述 优化技术简介 1 删除多余运算 删除公共子表达式 3 6 计算出的值相等 4 I 且从 3 到 6 没有对I进行赋值 所以可以将 6 变换为T4 T1 2 代码外提减少循环中代码总数的一个重要办法是代码外提 这种将循环不变运算 即其结果独立于循环次数的表达式 提到循环前面 使之只在循环外计算一次 在这里 4 7 外提 T4 T1 2020 1 21 第六章 代码优化 6 6 1概述 3 强度削弱把强度大的运算换算成强度小的运算 如乘方变乘法 乘法变加法等等 对于本例中 由于T1与I是线性关系 每次I增1 T1增4 所以可以把循环中计算T1值的乘法运算变换成在循环前进行一次乘法运算 而在循环中将其变成加法运算 即 3 外提 在 12 前增加一条语句 3 T1 T1 4 1 P 0 2 I 1 4 T2 a 4 7 T5 b 4 3 T1 4 I 5 T3 T2 T1 6 T4 T1 8 T6 T5 T4 9 T7 T3 T6 10 P P T7 11 I I 1 12 IfI 20goto 3 B1 B2 3 T1 T1 4 2020 1 21 第六章 代码优化 7 6 1概述 4 变换循环控制条件在上面的代码中 I和T1始终保持T1 4 I的线性关系 这样可以把将 12 的循环控制条件I 20变换成T1 80 这样变换后整个程序的运行结果不变 但若I在循环后不会被引用 则四元式 11 可以从循环中删除 T1 80 2020 1 21 第六章 代码优化 8 6 1概述 5 合并已知量与复写传播在上面的四元式 3 计算4 I时 I必为1 所以 3 中的4 I的两个运算对象都是编译时的已知量 可在编译时计算出它的值 即 3 可变为T1 4 这叫合并已知量 另外 6 把T1的值复写到T4中 四元式 8 要引用T4的值 而 6 到 8 之间未改变T4和T1的值 则 8 可改为T6 T5 T1 之后运算结果保持不变 这种变换称为复写转播 1 P 0 2 I 1 4 T2 a 4 7 T5 b 4 3 T1 4 I 5 T3 T2 T1 6 T4 T1 8 T6 T5 T4 9 T7 T3 T6 10 P P T7 3 T1 T1 4 12 IfT1 80goto 5 B1 B2 3 T1 4 8 T6 T5 T1 2020 1 21 第六章 代码优化 9 6 1概述 6 删除无用代码T4和I未被引用 相关赋值语句可删除 1 P 0 2 I 1 4 T2 a 4 7 T5 b 4 3 T1 4 5 T3 T2 T1 6 T4 T1 8 T6 T5 T1 9 T7 T3 T6 10 P P T7 3 T1 T1 4 12 IfT1 80goto 5 B1 B2 2020 1 21 第六章 代码优化 10 6 2基本块与局部优化 基本块定义 一个连续的三地址 中间 代码序列只有一个入口语句 一个出口语句执行时从入口语句进入 从出口语句退出基本块的划分寻找入口语句1 程序的第一条语句2 转移语句的目标语句3 紧跟在条件转移语句后面的语句划分基本块的算法 1 求出所有入口语句 2020 1 21 第六章 代码优化 11 6 2基本块与局部优化 2 一个入口语句对应一个基本块 构造某入口语句对应的基本块的方法是 该基本块由该入口语句到下一入口语句 不包括下一入口语句 或到一转移语句 包括该转移语句 或到一停语句 包括该停语句 之间的代码序列组成 3 凡未被纳入某一基本块的语句 都是程序中控制流程无法到达的语句 可以删除 例子 对于右图中的代码段 由规则1 语句 1 是入口语句 由规则2 语句 3 是入口语句 由规则3 跟随语句 12 的语句是入口语句 这样 语句 1 和 2 构成一个基本块B1 语句 3 12 构成一个基本块B2 2020 1 21 第六章 代码优化 12 6 2基本块与局部优化 基本块内可进行的优化 删除公共子表达式 删除无用代码 复写传播 合并已知量等 参考优化技术简介 1 5 6是局部优化 即基本块优化 基本块优化的实现基本块的DAG表示叶结点标记为变量名字或常数 表示该结点代表该变量或常数的值内部结点标记为运算符号 代表此运算符号作用于其子结点计算出来的值结点可附加一个或多个标识符 表示这些标识符具有该结点所代表的值 2020 1 21 第六章 代码优化 13 6 2基本块与局部优化 DAG的构造三地址代码有如下三种形式 1 x yopz 2 x opy 3 x y函数node id 返回最新建立的与id联系的结点DAG的构造算法 依次考察每一条三地址代码1 若node y node z 没有定义 分别建立标记为y和z的结点2 对于 1 寻找是否有一个标记为op的结点 它的左结点为node y 右结点为node z 如果有 在此结点的附加标识符表中增加x 否则 建立一个这样的标记为op的结点 并在此结点的附加标识符表中增加x 如果node y 和node z 都是标记为常数的叶结点 则执行yopz 即合并已知量 令得到的新常数p 如果node y 或node z 是处理当前四元式时新构造出来的结点 则删除它 如果node p 无定义 则构造一用p做标记的叶结点n 2020 1 21 第六章 代码优化 14 6 2基本块与局部优化 3 对于 2 寻找是否有一个标记为op的结点 它的唯一结点为node y 如果有 在此结点的附加标识符表中增加x 否则 建立一个这样的标记为op的结点 并此结点的附加标识符表中增加x 如果node是标记为常数的叶结点 则执行opy 即合并已知量 令得到的新常数为p 如果node y 是处理当前四元式时构造出来的结点 则删除它 如果node p 无定义 则构造一用p做标记的结点n 4 对于 3 在node y 的附加标识符表中增加x5 在增加标识符x之前删除其他结点上附加标识符中的x 如果存在 6 对于2 和3 如果x得到的是常数 在一个该常数的结点中标记x 或建立一个标记为x的结点 2020 1 21 第六章 代码优化 15 6 2基本块与局部优化 例子 1 T0 3 14 2 T1 2 T0 3 T2 R r 4 A T1 T2 5 B A 6 T3 2 T0 7 T4 R r 8 T5 T3 T4 9 T6 R r 10 B T5 T6 n1 3 14 T0 n2 6 28 T1 n3 R n4 r n5 T2 n6 A B T3 T4 T5 n7 T6 n8 B 2020 1 21 第六章 代码优化 16 6 2基本块与局部优化 利用DAG进行优化按照构造DAG的顺序重写代码可得优化代码例子 如上例 1 T0 3 14 2 T1 6 28 3 T3 6 28 4 T2 R r 5 T4 T2 6 A 6 28 T2 7 T5 A 8 T6 R r 9 B A T6 2020 1 21 第六章 代码优化 17 6 2基本块与局部优化 合并了已知量删除了无用赋值公共子表达式只计算了一次如果T0 T6在基本块后面不被引用 则代码可进一步优化为 1 S1 R r 2 A 6 28 S1 3 S2 R r 4 B A S2DAG提供的其他信息 在基本块外被定值并在基本块内被引用的所有标识符 就是作为叶子结点上标记的那些标识符 在基本块内被定值且该值能在基本块外被引用的所有标识符 就是DAG各结点上的那些附加标识符 1 T0 3 14 2 T1 6 28 3 T3 6 28 4 T2 R r 5 T4 T2 6 A 6 28 T2 7 T5 A 8 T6 R r 9 B A T6 2020 1 21 第六章 代码优化 18 课上练习 练习1 对于基本块P S0 2S1 3 S0S2 T CS3 T CR S0 S3H RS4 3 S1S5 T CS6 S4 S5H S6 S2 1 试应用DAG进行优化 2 假定只有R H在基本块出口是活跃的 试写出优化后的四元式序列 2020 1 21 第六章 代码优化 19 6 2课上练习 1 构造DAG S0 2S1 3 S0S2 T CS3 T CR S0 S3H RS4 3 S1S5 T CS6 S4 S5H S6 S2 n1 2 S0 n2 1 5 S1 n3 T n4 C n5 S2 n7 R H S4 n6 S3 S5 S6 n8 H 2020 1 21 第六章 代码优化 20 6 2课上练习 2 利用DAG进行优化 按照构造DAG的顺序重写代码可得优化代码为 S0 2S4 2S1 1 5S2 T CS3 T CS5 S3R 2 S3S6 RH S6 S2 3 若只有R H在基本块出口是活跃的 优化后的四元式序列为 S2 T CS3 T CR 2 S3H R S2 2020 1 21 第六章 代码优化 21 6 3控制流分析和循环优化 程序流图一个程序可以用一个控制流程图 流图 来表示一个程序的流图是个三元组G N E n0 N是流图的结点集合 流图中的结点是程序基本块n0是N中的元素 称为首结点 该结点包含程序的第一条语句 n0到流图中任何结点都有通路E是有向边集合 有向边代表程序的流程 有向边如下构造 当以下条件之一成立时 从i到j画一条有向边 1 基本块j在程序中的位置紧跟在基本块i之后 并且基本块i的出口语句不是无条件转移语句或停机语句2 基本块i的出口语句是转移语句 并且转移目标是j的入口语句 2020 1 21 第六章 代码优化 22 6 3控制流分析和循环优化 例子 构造以下程序的流图 1 readx 2 ready 3 r xmody 4 ifr 0goto 8 5 x y 6 y r 7 goto 3 8 writey 9 halt 8 writey 9 halt 1 readx 2 ready B1 3 r xmody 4 ifr 0goto 8 B2 5 x y 6 y r 7 goto 3 B3 B4 2020 1 21 第六章 代码优化 23 6 3控制流分析和循环优化 循环循环是程序中可能反复执行的代码序列循环由流图中的结点序列构成这些结点是强连通的 有且仅有一个称之为入口结点的结点必经结点 称流图中结点d是结点n的必经结点 如果从首结点出发 每条到达n的路径都要经过d 记为ddomn每个结点是它本身的必经结点首结点是所有结点的必经结点 2020 1 21 第六章 代码优化 24 6 3控制流分析和循环优化 例子 1 所有结点的必经结点2 自身的必经结点3 除1 2外所有结点的必经结点4 除1 2 3外所有结点的必经结点5 自身的必经结点6 自身的必经结点7 7 8 9 10的必经结点8 8 9 10的必经结点9 自身的必经结点10 自身的必经结点 2020 1 21 第六章 代码优化 25 6 3控制流分析和循环优化 回边 假设a b是流图中的一条有向边 如果bdoma 则称a b是流图的一条回边例子 见上例 回边有 7 4 10 7 4 3 8 3 9 1循环的查找一条回边对应一个循环查找回边n d的循环 1 d是循环的入口2 n是循环的一个出口3 若n等于d 循环只有一个结点4 否则 求n的前驱 以及前驱的前驱 直到d 这些结点都是循环中的结点 2020 1 21 第六章 代码优化 26 6 3控制流分析和循环优化 例子 见上例7 4 4 5 6 710 7 7 8 104 3 3 48 3 3 4 5 6 7 89 1 全部两个循环或者是不相交的或者一个完全包含在另一个里面 除非它们有相同的首结点 2020 1 21 第六章 代码优化 27 6 3控制流分析和循环优化 循环优化代码外提 对于循环中的某些代码 如果它产生的结果在循环中是不变的 可将其提到循环外 以减少循环中的计算量 这就是循环的代码外提 前置结点 1 新建的一个基本块2 循环入口结点的前面 代码外提的放置点3 入边是原指向循环入口结点的有向边4 唯一出边指向循环入口结点代码外提的例子 见概述关键是 寻找循环不变运算 2020 1 21 第六章 代码优化 28 6 3控制流分析和循环优化 强度削弱与删除归纳变量基本归纳变量I 循环中对I有唯一的赋值I I C或I I C C为循环不变量 归纳变量J 循环中J的值和I呈线性关系 J C1 I C2或J C1 I C2 C1 C2是循环不变量 对J可以进行强度削弱对基本归纳变量I的赋值可以删除例子 见概述关键是 寻找循环不变量 考察循环出口处变量的活跃情况 如果I在循环出口处是活跃的则不能删除对它的赋值 等 2020 1 21 第六章 代码优化 29 课上练习 练习2 试对下面的程序段进行尽可能多的优化 i 1j 10readkl x k iy j iz x ywriteji i 1