"""
代码优化概述
1. 代码优化
代码优化有局部优化循环优化窥孔优化等几种方法。
2. 什么是代码优化？
提高代码质量的技术通常称为代码优化。根据代码优化是否涉及具体的计算机来划分，代码优化可以分为两大类：
一类是与机器有关的优化，这类优化一般在目标代码上进行。具体有对寄存器的优化、多处理机的优化、特殊指令的优化等。有时也因为这种优化只观察中间代码或目标代码的相邻部分，对其进行优化，所以又称为窥孔优化。
另一类是与机器无关的优化，在中间代码上进行。根据优化对象所涉及的程序范围，又称为局部优化、循环优化和全局优化等。
3. 局部优化
局部优化（local）定义为应用于代码的线性部分的优化，也就是代码中没有转入或转出语句。一个最大的线性代码序列称为基本块的优化。
4. 局部优化的特点
范围小：局部优化仅在基本块内部进行，不涉及跨基本块的优化。 独立性：不依赖于目标机器的特性，因此可以在中间代码生成阶段完成。 通用性：适用于各种不同的编程语言和编译器。
5. 划分基本块
5.1 划分基本块的方法
基本块是指代码序列中一组顺序执行的语句序列。其中只有一个入口，一个出口。并且入口是基本块的第一个语句，出口时基本快的最后一个语句。因此划分基本块实质上就是要准确定义入口出口语句。
5.2 划分基本快的算法
5.2.1 确定入口语句
- 四元式序列的第一个语句。
- 由条件转移语句或无条件转移语句能转到的语句。
- 紧跟在条件转移语句后面的语句。
5.2.2 确定出口语句
- 下一个入口语句的前导语句。
- 转移语句（包括转移语句本身）。
- 停语句（包括停语句本身）。
5.2.3 构造基本块
- 删去那些不属于任何基本块的语句。
5.3 划分基本块的实例
- 四元式序列：read C, A =0, B = 1, L1: A = A + B, if BC goto L2, B = B + 1, goto L1, L2: write A, halt
- 根据算法，四元式（1）、（4）、（6）、（8）是入口语句，（3）、（5）、（7）、（9）是出口语句，因此分为四个基本块。
6. 基本块的DAG（无环路有向图）表示
6.1 DAG结点类型
- 0型四元式：后继结点为0，如四元式（1）。
- 1型四元式：有1个后继结点，如四元式（2）。
- 2型四元式：有2个后继结点，如四元式（3）、（4）、（5）。
- 3型四元式：有3个后继结点，如四元式（6）。
6.2 构造基本块的DAG实例
- 四元式序列：T0=3.14, T1=2T0, T2=R+r, A = T1 T2, B = A, T3 =2* T0, T4 = R+r, T5= T3 * T4, T6 = R -r, B = T5 * T6
- 按照算法顺序处理每一四元式后构造出DAG。
7. 利用DAG进行基本块的优化处理
7.1 DAG优化处理的基本思想
- 按照构造DAG结点的顺序，对每一个结点写出其相应的四元式表示。
7.2 DAG优化处理的实例
- 四元式序列：T0=3.14, T1=6.28, T3=6.28, T2=R+r, T4=T2, A=6.28T2, T5=A, T6=R-r, B=AT6
- 通过DAG优化，代码总数减少，合并已知量，删除公共子表达式，删除无用赋值。
7.3 DAG优化的进一步应用
- 如果在DAG中某结点上的标识符在该基本块后面不会被引用，可以不生成对该标识符赋值的中间代码。
- 如果某结点ni上没有任何附加标识符，或者n,上附加的标识符在基本块后面不会被引用，而且n,也没有前驱结点，这表明在基本块内和基本块后面都不会引用n,的值，于是可以不生成计算n,结点值的代码。
- 如果有两条相邻的代码A=C op D和B=A，其中第一条代码计算出来的A值，仅在第二条代码中被引用，则将DAG中相应结点重写成中间代码时，原来的两条代码可以优化为B=C op D。
7.4 DAG优化的效果
- 四元式序列（1）至（4）比优化前的代码更为简洁，但不是最优。
- 观察一组四元式：（1）S1=R-r，（2）S2=R+r，（3）A=6.28S2，（4）B=AS1，它们没有按照原来代码的顺序出现，是按低其他版序，即m，n, n和n，重写四元式，但要满足其中任一内部结点在其后销点之后微亚写并且转移语句（如果存在）仍然求本块的最后一个语句。后一组四元式生成的目标代的要好于前一组四元式的目标代码。
