摘要

  • Frances E. Allen 把程序优化从零散的提速技巧，推进为对控制路径、定义和使用关系的系统推理。
  • 区间、到达定义和活跃性分析给出的是有条件的静态事实；它们不是实际运行轨迹，也不证明源程序不存在未定义行为、数据竞争或数值风险。
  • Allen 的领导贡献应与 John Cocke、Reese T. Prosser、E. S. Lowry、C. W. Medlock、Kenneth Kennedy 以及 Stretch、Harvest、ACS 团队的工作并列记录。

优化器想把一条指令搬出循环。它先要问：操作数的哪些定义可能到达这里？途中会不会被重新赋值？后续路径还会不会使用结果？移动后，异常、外部可见操作或语言规定的求值顺序是否改变？

“看上去等价”在这里不够。优化器需要建立模型，计算模型上的关系，再在前提成立时执行变换。Frances E. Allen 的重要贡献，是把这种做法变成可复查的工程方法。

IBM 的人物史记载，Allen 1957 年加入公司，最初负责给新入职的科学人员讲授 FORTRAN。她后来参与 Stretch–Harvest，并在实验性的 Advanced Computing Systems 项目中推动编译器研究。2006 年，ACM 图灵奖资料以“优化编译技术的理论与实践”概括她的开创性工作；她也成为首位获得该奖的女性。

把这段历史缩成“Allen 发明了优化”反而会遮住真正的突破。她帮助编译器把结论写成范围明确的命题：在这些表示、假设和语义条件下，这个关系成立。力量恰恰来自有限。

控制流图描述的是可能路径

Allen 1970 年的 Control Flow Analysis 从一个基础问题出发：如果编译器要跨越单条语句分析表达式和数据，就必须知道程序可能怎样流动。论文以基本块为节点，以可能的控制转移为有向边；在其模型里，基本块是一段单入口、单出口的直线指令序列。

控制流边不是运行日志。它说明控制可以通过，并不说明某次执行已经通过。这是第一条证据边界。

Allen 随后用“区间”组织图结构。以 h 为首节点的区间，是一个最大单入口子图，其中每条闭合路径都包含 h。构造过程从入口开始；当一个节点的全部直接前驱都已进入区间，才把它加入。反复压缩后，分析得到更高层的区间图，不必枚举所有路径也能处理循环与流关系。

论文对前人贡献写得十分明确：Reese T. Prosser 早期研究布尔矩阵和连通矩阵，并引入支配概念；E. S. Lowry 与 C. W. Medlock 大幅扩展了支配研究；区间构造则归功于 John Cocke。保留这些名字，不会削弱 Allen，反而解释了一项研究怎样积累成工程基础。

“可能到达”不等于“实际提供了这个值”

Allen 与 Cocke 1976 年的 A Program Data Flow Analysis Procedure 把编译期定义—使用关系写成程序化步骤：哪些定义可能到达每个节点，哪些定义在每条边上仍然活跃。

若一个定义在起点基本块局部可用，并且至少存在一条到后续基本块的路径，途中没有对同一数据项重新定义，它便“到达”后者。“至少一条路径”决定了这是 may-analysis：结论保守地覆盖可能性，并不表明实际走过哪条路，也不表明某次运行中的值一定来自这个定义。

活跃性同样只回答一个明确问题：到达某点的定义，是否可能在后续被一个向上暴露的使用引用。它可以支持寄存器分配和无用代码删除，却不证明该值在每次运行中都存在、合法、安全。

这套程序以区间顺序排列边，结合位向量操作，并在同一框架中处理可归约与不可归约图。Allen 与 Cocke 还把 Kenneth Kennedy 标为活跃性算法的提出者，把 Richard Stasko 的数据结构想法，以及 Ullman、Hecht、Kildall、Schaefer、Schwartz 等人的重要贡献写入致谢。

优化目录不是全局最优预言机

Allen 与 Cocke 的 1971 年 A Catalogue of Optimizing Transformations 系统整理了公共子表达式消除、代码移动、强度削弱、冗余运算删除等变换。作者主动说明目录并不穷尽所有技术；当“最优”没有一般定义时，optimization 这个词本身就带有误导。论文主要讨论运行速度，其次是空间，而不是整个作业成本、系统拥塞或代码维护性。

这形成第二条边界：某次变换在给定语义下合法，不等于它让系统的一切指标都更好。允许的浮点重结合可能改变舍入结果；看似重复的读取，如果指向 volatile、共享或设备可见位置，或读取会触发异常，就不能随意删除。

因此，图结构之外还要有语言的求值规则、别名模型、异常语义和算术约定。并发程序又加入内存模型与同步顺序。中间表示可以把这些条件做成显式属性，却不能凭空消灭条件。

保持语义，并不等于证明程序整体正确

设想优化器完美完成自己的义务：在所有受语言规则和编译器前提覆盖的执行中，转换前后具有相同的规定行为。仍有很多主张没有得到证明。

源程序可能对某些输入触发未定义行为，两个线程可能发生数据竞争，一个数值算法可能放大舍入误差，需求本身可能写错，真实世界模型也可能不准确。编译器的证明不会自动向上覆盖这些层次。

这不是静态分析的缺陷。方法之所以有价值，就在于它能写下可检查的结论：给定这张图、这些定义与使用、这些语义前提，某个关系成立。问题出在组织把完整句子压缩成一个只写着“正确”的绿灯。

Allen 的职业史也需要同样精确。IBM 把她记为 Stretch–Harvest 的设计者与语言联络者，以及 ACS 编译器研究的核心人物。IEEE Computer Society 的档案把 1966 年 Program Optimization 报告、区间分析和优化变换目录串联起来。ACM 的 John Cocke 档案则保留 Cocke 自己在编译器优化中的奠基贡献。硬件团队、语言设计者和编译器工程师共同让抽象方法进入可运行系统。

更准确的结论也更有现实价值：Allen 没有让编译器宣称自己无所不知；她让它能够严谨地说明自己究竟知道什么。

来源