[科普中国]-源程序优化程序

简介

源程序优化程序是指对源程序的空间代价和时间代价进行优化的程序。优化是把程序变换为在时间、空间上改进了的而执行效果与原程序等价的高效执行程序的过程。其目标是设法从待优化程序中消除重复计算。优化的基础是控制流分析、数据流分析。 可分为局部或全局的；依赖于机器或不依赖于机器；依赖于语言或不依赖于语言的优化。

代码优化所谓代码优化是指对程序代码进行等价（指不改变程序的运行结果）变换。程序代码可以是中间代码（如四元式代码），也可以是目标代码。等价的含义是使得变换后的代码运行结果与变换前代码运行结果相同。优化的含义是最终生成的目标代码短（运行时间更短、占用空间更小），时空效率优化。原则上，优化可以在编译的各个阶段进行，但最主要的一类是对中间代码进行优化，这类优化不依赖于具体的计算机。

在不改变程序运行效果的前提下，对被编译的程序进行等价变换，使之能生成更加高效的目标代码1。

代码优化过程等价：不改变程序执行效果；

变换：引起程序形式上的变动。

途径改进、提高程序途径

1） 改进算法；

2） 在源程序级上等价变换；

3） 充分利用系统提供的程序库；

4） 编译时优化等。

控制流分析控制流分析（Control flow analysis）简称CFA，是一种确认程式控制流程的静态代码分析技术。控制流程会以控制流图来表示。对于函数编程语言及面向对象程式设计，CFA都是指计算控制流程的算法。

控制流分析一词最早是由Neil D. Jones及Olin Shivers[2]开始使用。对于像是Scheme之类有高阶函数的编程语言，不一定可以会程式中直接看出函数呼叫的目标，例如以下的程式片段

(lambda (f) (f x))

根据上述程式无法确认程序f是指什么，此情形下的控制流分析需考虑何时会执行此程式码，及当时的传入值。抽象释义、约束补偿及型别系统都可以用来进行控制流分析。

数据流分析数据流分析是一种用于收集计算机程序在不同点计算的值的信息的技术。一个程序的控制流图(control flow graph, CFG)被用来确定对变量的一次赋值可能传播到程序中的哪些部分。这些信息通常被编译器用来优化程序。数据流分析的一个典型的例子就是可到达定义的计算。进行数据流分析的最简单的一种形式就是对控制流图的某个节点建立数据流方程，然后通过迭代计算，反复求解，直到到达不动点。通过数据流分析，可以不必实际运行程序就能够发现程序运行时的行为，这样可以帮助大家理解程序。数据流分析被用于解决编译优化、 程序验证、调试、测试、并行、向量化和并行编程环境等问题。以下是数据流分析一些常见算法：

消除算法消除算法通过利用流图的结构属性减少解决数据流问题所需要的大量工作。通过连续的应用图的转换使流图归约到一个点， 图的转换就是使用图的分析或图的分裂去分析区间以获得一个派生图。在一个区间内，数据流的属性是由区间内头节点的数据流的属性来确定的。 这样可以延迟替代联立方程中的一些值。对于单向流问题，这些方法典型的复杂度为O(N) ，这里N是在归约图序列中节点的总数。尽管它们已经被用于解决一类受限制的双向问题，但消除算法不能被扩展到一般的双向数据流问题。

迭代算法最常用的用于求解数据流方程的方法是使用迭代算法。它由每个块的近似入口状态信息出发。然后应用转移函数基于这些入口状态信息计算出口状态信息。然后，使用连接运算符更新入口状态信息。最后两步将一直进行下去直至到达不动点: 即此时入口状态信息和出口状态信息都不再改变。

一个基本的求解数据流方程的算法是循环迭代算法:

fori← 1 toN

初始化节点i

while (有集合发生了改变)

fori← 1 toN

重新计算节点i处的集合

收敛性分析为了可用性的要求，迭代算法应该可以真正到达不动点。这可以通过对状态的值域的联合，转移函数以及连接运算符加上限制条件来保证。

值域应该是有界的且有序。(比如，不存在一个无限的递增链后向分析

活性变量分析计算每个程序点上的那些在重新定义前可以被潜在的使用的变量。这个的典型应用是用于死码删除，移除那些给变量赋值但之后变量未被使用的语句。块的入口状态是在上个块的末端仍然具有活性的变量的集合。