代码优化
- 代码优化的含义是：对代码进行等价变换，使得变换后的代码具有更高的时间效率和空间效率。代码优化的目的是提高目标程序的质量。
- 优化分为局部优化、循环优化和全局优化
1、局部优化
1、基本块的划分方法：
基本块指程序中一顺序执行的语句序列，其中只有一个入口（该序列的第一个语句）和一个出口（该序列的最后一个语句）
在各个基本块范围内进行的优化叫局部优化。
-
基本块的划分：
从四元式序列确定满足以下条件的入口语句：- 四元式序列的第一个语句
- 能由条件转移语句或无条件转移语句转移到的语句
- 紧跟在条件转移语句后面的语句
出口
- 下一个入口语句的前导语句
- 转移语句（包括转移语句自身）
- 停语句（包括停语句自身）
695206989.jpg
2、DAG图的构建
DAG是一种有向图，常用于基本块的优化，图的叶节点（无后继的节点）以标识符（变量名）或常数作为标记，图的内部节点（有后继的节点）以一运算符作为标记。
-
为了DAG算法的需要，将四元式分成四类，算法只用0，1，2型四元式。
2074825103.jpg
（1）是0型四元式，后继节点数为0，（2）是1型四元式，有一个后继，（3）、（4）、（5）是2型四元式，有两个后继 （6）是3型四元式，有三个后继。大写字母表示四元式中的变量名（或常数），Node（A）表示A在DAG中相应的节点。
算法：
580404903.jpg1218775985.jpg
自己总结：352022156.jpg
练习：1706012149.jpg
3、DAG图实现基本块的优化
- 首先根据DAG图写出四元式序列：注意立即数是最优的，赋值比计算赋值优。
- 注意T是临时变量，A、B这些都是普通变量。
2、循环优化
1、程序流图与循环
控制流程图就是有唯一首节点的有向图，用三元组G=（N，E，n0）表示（节点集，边集，首节点）节点集就是基本块集，有向边表示如下：基本块i出口语句不是转向语句或停语句，i与紧随其后的基本块j有有向边。或者i出口转向j入口语句。
2、循环：程序流图里的一个节点序列强连通，任意两个节点都有至少一条通路，它们中有且只有一个入口节点。（从序列外某节点有一条有向边引导它，或他是程序流图的首节点。
3、找循环：
必经节点集：从流图首节点出发，到n的任意通路都要经过m，m是n的必经节点，记为mDOMn；流图中结点n的所有必经节点的集合称为节点n的必经结点集，极为D(n)。
DOM的性质：自反性：流图中任意节点a，都有aDOMa。传递性：aDOMb，bDOMc则aDOMc。反对称性：aDOMb,bDOMa,a=b。DOM是一个偏序关系，任何节点n的必经节点集是一个有序集。
必经节点的求法：一定包括自己好吧。。。。。。必经节点集就是前驱节点必经节点集的交集加自己没准。
找回边：假设ab是流图中的一条有向边，如果bDOMa，则a
b是流图中的一条回边。已知有向边n
d是一条回边，则由它组成的循环就是由结点d、结点n以及有通路到达n但该通路不经过d的所有结点组成的。
4、可规约流图：当且仅当一个流图除去回边后，其余边构成一个无环路流图。性质：1. 图中任何直观环路都是循环。2. 找到所有回边可以对应找出所有循环。3. 循环或嵌套或不相交（可能有公共入口节点），goto语句不可跳入循环。
练习：
5、循环优化
- 代码外题：对于一个循环L，存在循环不变运算S（不随循环次数变化）：A=BopC或A=opB或A=B，要满足下述条件：
1. S所在节点是L所有出口节点的必经节点。
2. A在L中其它地方未在定值
3. L中所有A引用只有S中A定值才可达
算法如下：
- 看L中各基本块的每个四元式，他的每个运算对象为常数或者在定值点L外，将此四元式标为不变运算。
- 依次查看尚未标记的四元式，如果.......，或者只有一个到达一定值点且该点上的四元式标记为不变运算，比如A=3,X=A+2，循环中A=3定值定值点可唯一到达的X=A+2也标记为不变运算。
- 不变运算提到L之外，（满足三条件，或者出循环后不活跃的话满足后俩就可以）
练习：
- 强度削弱：乘法外提里面换为加法，或者加法外提里面换成加一
练习：
- 删除归纳变量：循环中对变量I只有形如I=I
C的赋值，其中C为循环不变量，称I为基本归纳变量。J=C1*I
-
基本归纳变量：给自己定值，给其他归纳变量赋值，控制循环（给其他归纳变量赋值在强度削弱时已经撇清了），出循环不活跃可删。删除归纳变量就是变换循环控制条件。选一个M，尽量在循环中引用，出了循环活跃，有M和B关系。
删除归纳变量.jpg
参考171页例题。
