编译原理－何炎祥-第十一章.pptVIP

第十一章 优 化 为了使目标程序运行时占用的存储空间尽可能少，需要的时间尽可能短，编译程序需要根据程序的等价变换原则对程序进行各种优化。最主要的优化是在目标代码生成以前对中间代码进行的各种变换，这一类优化通常是与机器无关的。与机器有关的优化在目标代码生成时，根据具体机器的特点进行。 本章简单讨论常用的一些优化方法。 11.1 基本块及其求法 基本块，是指程序中一顺序执行的语句序列，其中只有一个入口和一个出口，入口就是第一个语句，出口就是最后一个语句。对于一个基本块来说，执行时，只能从其入口进入，从其出口退出。 从四元式序列中确定基本块的方法： 第1步 确定入口语句； 第2步 对每一入口语句，构造其所属的基本块； 第3步 凡未包含在某一基本块中的语句，都是程序中控制流程不可达的语句，因此，可删除它们。 11.2 优化举例 合并已知常量 消除公共子表达式 外提循环不变运算 削弱运算强度 变换循环控制条件 11.3 利用变量的定义点进行优化 11.3.1 变量的定义点 ①赋值语句中左部变量的出现是该左部变量的定义点； ②输入语句的输入名表中的变量出现是该变量的定义点； ③一个变量可能作为过程语句或函数命名符的实参，而在调用中被赋予一个新的值，也可能是相应过程的全局量而在调用中被赋值。对于这两种情形，这个过程语句或函数命名符就是该变量的定义点。 11.3 利用变量的定义点进行优化 11.3.2 循环中不变式的外提 某一表达式是循环中的不变式，其充要条件是：该表达式中的所有运算对象或者是常量，或者是关于该循环的区域常量。利用循环的变量状态字很容易确定循环中有无不变式。 循环中不变式的外提就是把在循环执行中始终不变的式子提到循环外面。 11.3 利用变量的定义点进行优化 11.3.3 运算强度削弱 强度削弱就是用另一种执行较快的运算替代原来的运算。 如果循环中某一表达式满足 ① 是区域变量和区域常量（或常量）的线性表达式， ② 其中的区域变量是依循环线性变化的（例如定步长的循环控制变量）， 则这个线性表达式中的乘（除）法运算可以削弱成加（减）法运算。 11.3 利用变量的定义点进行优化 11.3.4 公共表达式的消除 一个子表达式为公共子表达式的充要条件是：该子表达式与另一在前面的子表达式形式上完全相同，而且该子表达式中的所有变量在这两个表达式之间无定义点。 公共表达式的消除就是第一次计算公共表达其结果，而在后面再用时，直接用结果。 11.3 利用变量的定义点进行优化 11.3.5 常量合并 如果运算对象是常数，那么，常量合并的过程可在语义分析或代码生成阶段中进行。每当调用语义子程序生成双边运算代码时，首先检查两个运算对象是否为常数，若是，则立即计算出运算结果，而无须生成目标指令。 11.4 循环优化 主要思路： ①以较少的指令替代直接转“数组元素地址计算子程序”。 ②把地址计算的工作拆开，能在编译时计算就在编译时计算（常量合并）；能在循环外面或较外层循环处计算，就尽量拿到外面计算（外提不变式）。 ③在内循环中，用加改变量的办法，使数组元素的地址随着循环控制变量值的变化而变化，不必每次都从头算起（强度削弱）。 11.5 借助DAG进行优化 若一有向图中任一通路都不是环路，则称该有向图为无环有向图(DAG)。 利用DAG来进行优化的主要思想：将一基本块中的每一个四元式依次表示成对应的一个DAG，再按原来构造DAG结点的顺序重写四元式序列，便可得到“合并已知常量”、“删除无用赋值”、“删除多余运算”后的等价基本块——优化了的基本块 。 11.6 并行分支的优化 一个系统有多台机器或CPU时，把可并行的程序段分支调度到多台上执行，再合并。从而既发挥了机器的效率又提高了程序的执行速度。 并行分支识别的主要工作在于寻找这种彼此独立的基本块，问题的难点在于： ① 任何两个基本块彼此独立的充要条件是什么？ ② 如何确切定义基本块？ 11.7 窥孔优化 窥孔优化是指：每次只查看所生成的目标代码中相邻的几条指令，并对它们进行优化，以获得等价的、更短的代码序列。 这种优化通常包括删去多余的存取指令、删去决不会执行的代码、充分利用机器指令特点等等。 这种优化可在中间代码级上进行，但更多的是在目标代码级上进行。 The end. * * *