[工学]编译原理第10章.pptVIP

20 2 7 第十章优化 10 1概述10 2局部优化10 3循环优化10 4数据流分析 不介绍 20 2 7 什么是代码优化p272 含义是指对程序进行各种等价变换 使得从变换后的程序出发 能生成更有效的目标代码代码优化器的地位和结构 优化可在编译的各个阶段进行最主要的一类优化是在目标代码生成之前 对语义分析后的中间代码进行 编译前端 代码优化器 代码产生 控制流分析 数据流分析 代码变换 20 2 7 10 1概述优化的目的和原则p272 优化目的产生更高效的目标代码合理利用计算机资源优化原则等价不改变程序的运行结果高效运行时间较短 占用存储空间较小合算以较低的代价取得较好的优化效果例如优化算法虽然使最后生成的目标代码的运行时间缩短 占用空间减少 但是若优化算法本身运行是浪费了过多的时间和空间 则从总体上说就不一定合算 20 2 7 优化的分类 按阶段分成与机器无关的优化 对中间代码进行依赖于机器的优化 生成目标代码时进行根据优化时所涉及的程序范围分成局部优化在基本块内部进行优化循环优化对循环中的代码进行优化全局优化大范围的优化 涉及整个程序优化工作的基础控制流分析 data flowanalysis 数据流分析 control flowanalysis 变换 transformations 20 2 7 程序举例 例如P 0 forI 1to20doP P A I B I 翻译成三地址代码是 1 P 0 2 I 1 元素A I 的地址 base I 1 w I w A w 4 I A 4 3 T1 4 IA的可变 4 T2 A 4A的不变 5 T3 T2 T1 T3存A I 6 T4 4 I 7 T5 B 4 8 T6 T5 T4 T6存B I 9 T7 T3 T6 10 P P T7 增1 11 I I 1 12 ifI 20goto 3 进入循环前 循环体 问题 可采取哪些优化技术 20 2 7 优化技术举例 代码外提p276每次循环结果不改变的代码 1 P 0 2 I 1 4 T2 A 4 7 T5 B 4 删除公共子表达式p273删除多余运算避免重复计算 3 T1 4 I 5 T3 T2 T1 6 T4 8 T6 T5 T4 9 T7 T3 T6 10 P P T7 11 I I 1 12 ifI 20goto 3 T1 20 2 7 强度削弱p277例如将循环中的 变换为 提高运算速度 I每次增1T1每次增4外提 3 给T1赋初值新增 3 给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 3 T1 T1 4 12 ifI 20goto 5 20 2 7 复写传播p275例T6 T2 x T6 目的 使对某些变量的赋值变为无用 6 T4无用 T2 1 P 0 2 I 1 4 T2 A 4 7 T5 B 4 3 T1 4 1 5 T3 T2 T1 6 T4 T1 8 T6 T5 T1 9 T7 T3 T6 10 P P T7 11 I I 1 3 T1 T1 4 12 ifI 20goto 5 20 2 7 删除归纳变量p277例 11 I I 1 3 T1 T1 4T1 4 IT1与循环变量I保持线性关系T1称为归纳变量因为I在其它地方没有引用所以 12 中条件可变换为 12 ifT1 80goto 5 故 2 I 11 I的赋值无用 T1 80 20 2 7 删除无用代码p276例 2 I赋值无用 合并已知量例 3 直接计算 4 优化后 循环体内代码从10条减少到6条 相应代码也无用 删除 6 T4 11 I 20 2 7 优化技术简介p273 278 1 删除公共子表达式 删除多余运算 2 复写传播3 循环不变代码外提4 强度削弱 循环 5 删除归纳变量 变换循环控制条件 6 删除无用赋值7 合并已知量 20 2 7 10 2局部优化p279 定义局限于基本块范围内的优化主要内容基本块及流图基本块的DAG表示及其应用 20 2 7 基本块的定义和性质p279 基本块的定义是指程序中一顺序执行的语句序列 其中只有一个入口语句和一个出口语句 例如下基本块 1 T1 A B 2 T2 3 2 3 T3 T1 T2 4 X T3 5 C 2 6 T4 A B 7 T5 18 C 8 T6 T4 T5 9 Y T6 入口语句 出口语句 基本块的性质有唯一入口和唯一出口块内各个操作按序执行 不出现任何分叉 基本块内的语句要么全执行 要么全不执行 而不能只执行一部分 20 2 7 基本块入口语句的确定p279 确定规则1 程序的第一条语句 或者2 能由条件转移语句或无条件转移语句转移到的语句 或者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 共4个入口语句 规则2 规则1 规则2 规则3 对应4个基本块 20 2 7 划分基本块的算法p279 1 求出四元式程序中各个基本块的入口语句2 对以上求出的每一个入口语句 构造其所属的基本块 由该入口语句 1 到另一入口语句 不包括该入口语句 或者 2 到一转移语句 包括该转移语句 或者 3 到一停语句 包括该停语句 之间的语句序列组成3 凡未被纳入某一基本块的语句 都是程序中控制流程无法到达的语句 从而也是不会被执行到的语句 可把它们从程序中删除 20 2 7 划分基本块课堂练习 1 readC 2 A 0 3 B 1 4 A A B 5 ifB Cgoto 8 6 B B 1 7 goto 4 8 writeA 9 halt 共4个入口语句 规则2 规则1 规则2 规则3 对应4个基本块 20 2 7 程序流图构造举例p281 以基本块为结点 以程序控制流为有向边的一张有向图 用来描述程序 1 readX 2 readY 3 R XmodY 4 ifR 0goto 8 5 X Y 6 Y R 7 goto 3 8 writeY 9 halt 对应的程序流图 B1 B2 B3 B4 20 2 7 程序流图构造方法p280 程序流图按照程序的执行过程 用有向边把基本块连接起来 构成程序的控制流图构成特点G N E n0 N结点集 基本块集E有向边集 执行流程n0唯一首结点 入口语句是程序第一条语句的基本块有向边Bi Bj含义程序执行时 Bj紧接在Bi之后执行存在条件在程序序列中 1 ifBi出口不是无条件转移或停语句thenBj紧接在Bi之后 2 ifBi出口是goto S 或if goto S then S 是Bj的入口 20 2 7 程序流图构造课堂练习p281 对应的程序流图 20 2 7 常用局部优化技术p280 删除无用赋值设所有临时变量和C在以后无用 则除了计算X Y时要用到的变量保留外 删除其它赋值 2 5 6 7 1 T1 A B 2 T2 3 2 3 T3 T1 T2 4 X T3 5 C 2 6 T4 A B 7 T5 18 C 8 T6 T4 T5 9 Y T6 优化后只有5条代码 合并常数和已知量 2 编译时计算 2 7 编译时计算 7 2 T2 1 5 7 T5 20 复写传播 3 引用T2 3 8 引用T4 T5 8 删除多余运算 1 6 A B公共子表达式只需计算一次 6 6 T4 T1 3 T3 T1 1 5 8 T6 T1 20 进一步优化后只有3条代码 1 T1 A B 2 X T1 1 5 3 Y T1 20 20 2 7 基本块的DAG表示及其应用p281 基本块的DAG表示方法几种常见三地址代码及对应DAG表示基本块的DAG构造算法基本块的DAG应用 20 2 7 基本块的DAG表示举例p281 有向无环图 三地址代码 1 c a b 2 a c d 3 b a b 4 d c d 编号 结点标记 左指针 右指针 附加标记 0 a a0 1 b0 2 b0 标记 下边 c 附加标记 右边 3 1 2 c DAG结点建立顺序及结点对应表 d0 4 d0 a 5 3 4 a b 6 5 2 b d d DAG表示过程 删除多余运算 重建代码 1 c a b 2 a c d 3 d a 4 b a b 20 2 7 基本块的DAG表示p281 基本块的DAG DirectedAcyclicGraph结点带有标记或附加标记的DAG 标记 附加标记 叶结点标记是一个标识符 变量名 或常数代表该变量或常数的值举例 3 a0 变量a的初值表示该值由块外定值 以免与a的当前值混淆 内部结点标记是一个运算符代表其直接后继结点值进行该运算的结果举例 op 附加标记一个或多个变量可以附加到各个结点表示这些变量持有该结点所代表的值举例 b 3 a 3 a0 b 20 2 7 几种常见三地址代码及对应DAG形式 0型A B A B0 或 B A 1型A opB B0 op A 或 B op A 2型 A BopC B0 B C0 C op A 2型 A B C B0 B C0 C A 2型 D C B D0 D C0 C B0 B 2型 ifBropCgoto S B0 B C0 C rop S 变址取数 变址存数 条件转移 20 2 7 简介DAG的构造过程p282 函数NODE A 以名字A在对应表中查找结点 NODE A nDAG中已有标记为A的结点 编号为n NULLDAG中无标记为A的结点 构造DAG的大致过程对每一个三地址代码 按其类型不同分别构造0型A BNODE B NULL 新建叶结点标记B0附加标记A B0 A NODE B NULL 找到标记或附加标记为B的结点附加标记A B A B0 注意 附加标记A时 若DAG中原有附加标记为A的结点 则要把名字A从原结点的附加标记中删除 进入下一环节 20 2 7 简介DAG的构造过程p282 1型A opBNODE B NULL 新建叶结点ni 若B为常数 计算p opB 常数 2 NODE p j删除ni nj附加标记A 1 p A 2 p A 若B不为常数 ni标记B0 3 B0 op A NODE B NULLNODE B i 1 NODE p NULLni标记p附加标记A 3 新建结点nj 标记op附加标记A 4 已有代表opB的njnj再附加标记A A 5 无代表opB的结点 新建结点nj 标记op附加标记A op A 注意 附加标记A时 删除其它DAG结点附加标记的A 20 2 7 简介DAG的构造过程p282 2型A BopCNODE B NODE C NULL 新建叶结点ni njj i 1 若B C为常数 计算p BopC 2 NODE p k删ninj nk附加标记A 1 p A 2 p A 若B C不为常数 ni标记B0 nj标记C0 3 B0 op A NODE B NULLNODE B iNODE C NULLNODE C j 1 NODE p NULL删nj ni标记p附加A 3 新建结点nk 标记op附加标记A 4 已有代表BopC的nknk再附加A A 5 无代表BopC的结点 新建结点nk 标记op附加标记A C0 op A 注意 附加标记A时 删除其它A 20 2 7 仅含0 1 2型代码的基本块的DAG构造算法p282 开始 DAG为空 对基本块中每一条中间代码 依次执行以下步骤1 判定代码类型 如果NODE B 无定义 则构造一标记为B的叶结点并定义NODE B 为这个结点 如果当前代码是0型 则记NODE B 的值为n 转4 如果当前代码是1型 则转2 1 如果当前代码是2型 则 I 如果NODE C 无定义 则构造一标记为C的叶结点并定义NODE C 为这个结点 II 转2 2 20 2 7 2 合并已知量 1 如果NODE B 是标记为常数的叶结点 则转2 3 否则转3 1 2 如果NODE B 和NODE C 都是标记为常数的叶结点 则转2 4 否则转3 2 3 执行opB 令得到的新常数为P 如果NODE B 是处理当前代码时新构造出来的结点 则删除它 如果NODE P 无定义 则构造一用P做标记的叶结点n 置NODE P n 转4 4 执行BopC 令得到的新常数为P 如果NODE B 或NODE C 是处理当前代码时新构造出来的结点 则删除它 如果NODE P 无定义 则构造一用P做标记的叶结点n 置NODE P n 转4 20 2 7 3 找公共子表达式 1 检查DAG中是否已有一结点 其唯一后继为NODE B 且标记为op 如果没有 则构造该结点n 否则就把已有的结点作为它的结点并设该结点为n 转4 2 检查中DAG中是否已有一结点 其左后继为NODE B 其右后继为NODE C 且标记为op 如果没有 则构造该结点n 否则就把已有的结点作为它的结点并设该结点为n 转4 20 2 7 4 附加标记A 如果NODE A 无定义 则把A附加在结点n上并令NODE A n 否则先把A从NODE A 结点上附加标识符集中删除 注意 如果NODE A 是叶结点 则其标记A不删除 把A附加到新结点n上并令NODE A n 转处理下一代码 构造结束后 可由DAG重新生成原基本块的一个优化的代码序列 20 2 7 基本块的DAG构造举例p283 284 原代码 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 对应表 DAG构造过程 3 14 T0 1 3 14 T0 2 6 28 T1 2 6 28 T1 R0 3 R0 r0 4 r0 T2 5 3 4 T2 A 6 2 5 A B B T3 T3 T4 T4 T5 T5 T6 7 3 4 T6 B 删除其它B 8 6 7 B 合并已知量 删除多余运算 删除无用赋值 复写传播 A 6 28 T2 20 2 7 利用DAG优化举例p283 284 假设所有临时变量块外无用只保留A B 进一步优化代码 1 S1 R r 2 A 6 28 S1 3 S2 R r 4 B A S2 重建优化代码 1 T0 3 14 2 T1 6 28 3 T3 T1 4 T2 R r 5 T4 T2 6 A 6 28 T2 7 T5 A 8 T6 R r 9 B A T6