文档介绍：部分冗余消除优化的
SSA 算法研究
（申请清华大学工学博士学位论文）
培 养 单 位： 计 算 机 科 学 与 技 术 系
学 科： 计 算 机 科 学 与 技 术
研 究 生： 周 虎 成
指 导 教 师： 陈 文 光 教 授
二〇一一 年 六 月
Sparse SSA Algorithm of Partial
Redundancy Elimination
Dissertation Submitted to
Tsinghua University
in partial fulfillment of the requirement
for the degree of
Doctor of Engineering
by
Zhou Hucheng
( Computer Science and Technology )
Dissertation Supervisor : Professor Chen Wenguang
June, 2011
关于学位论文使用授权的说明
本人完全了解清华大学有关保留、使用学位论文的规定，即：
清华大学拥有在著作权法规定范围内学位论文的使用权，其中包
括：（1）已获学位的研究生必须按学校规定提交学位论文，学校可以采
用影印、缩印或其他复制手段保存研究生上交的学位论文；（2）为教学
和科研目的，学校可以将公开的学位论文作为资料在图书馆、资料室等
场所供校内师生阅读，或在校园网上供校内师生浏览部分内容；（3）根
据《中华人民共和国学位条例暂行实施办法》，向国家图书馆报送可以公
开的学位论文。
本人保证遵守上述规定。
（保密的论文在解密后应遵守此规定）
作者签名： 导师签名：
日 期： 日 期：
摘 要
摘 要
表达式的部分冗余消除（Partial Redundancy Elimination，PRE）优化是非常重要
的体系结构无关的编译优化，作为全局的标量优化，它涵括循环不变量外提优化和公
共子表达式消除优化。由于安全性的限制，常规部分冗余消除优化不能够完全消除程
序中存在的部分冗余，也就不能够最优化程序性能。因此，有必要放松该安全性限
制，本文称之为前瞻部分冗余消除优化。
静态单点赋值（Static Single Assignment，SSA）形式由于包括内生的使用 —定义
关系，并且基于 SSA 的数据流分析复杂性只与问题的规模相关，而不取决于程序自
身的规模。所以，现代编译器大多基于 SSA 形式进行全局的稀疏数据流分析，进而
实现全局的标量优化。
本论文提出了基于 SSA 形式的前瞻部分冗余消除最优化算法，包括计算最优和
生命期最优。计算最优意味着程序执行时该目标表达式的计算次数最少，而生命期最
优是指新引入的变量的活跃范围最短。论文的主要贡献包括:
1. 给定应用程序剖析信息，首次提出基于 SSA 形式的最优化前瞻部分冗余消除算
法，本文称之为 MC-SSAPRE 算法。MC-SSAPRE 根据目标表达式 SSA 形式中
生成网络流，并得到该流网络的最小切割。本文还详细证明了根据最小切割的
代码移动满足计算最优和生命期最优。较之既往的工作，MC-SSAPRE 更为高
效，因为其基于 SSA 形式，数据流分析的复杂度从 O(N2) 降为 O(N)，并且会
生成更精简的网络流；MC-SSAPRE 只需要基本快执行频度信息，而不是更为
重量级的控