A New Approach to Accurate and Effiecient Pointer Analysis for Large C and Object Oriented Programs

大型 C 和面向对象程序的准确高效指针分析的新方法

• 批准号: 9809478
• 负责人: Wen-mei Hwu
• 金额: $ 15.84万
• 依托单位: University of Illinois at Urbana-Champaign
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 1998
• 资助国家: 美国
• 起止时间: 1998-08-15 至 2000-07-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=9809478&HistoricalAwards=false
• 关键词: New; Approach; Accurate; Effiecient; Pointer

Pointer analysis has become one of the most critical components of modern C and C++ compilers. In Java, it is also critical to derive alias relations between object references to enable aggressive optimizations. The objective of this project is to develop an accurate and efficient pointer analysis framework based on the alias-pair approach. The key ideas are: (1) a new multirelation alias graph representation to allow accurate derivation of transitive alias relations, (2) a new interprocedural analysis framework based on the multirelation alias graph to derive accurate parameter and global alias information at very low cost, (3) a new context sensitive function-level analysis framework based on Static Single Assignment (SSA) forms to achieve high accuracy at low cost, (4) an iterative application of (2) and (3) to approach the accuracy of context sensitive analysis at much lower cost, and (5) to distinguish between maybe and definite aliases to make effective use of run-time disambiguation support in future high performance instruction set architectures. Theoretical results and empirical experiences based on prototype compiler implementation and large C, C++ and Java input programs are published to advance the state of the art of pointer analysis.

指针分析已经成为现代C和C++编译器中最关键的组成部分之一。在Java中，派生对象引用之间的别名关系以实现积极的优化也很关键。本项目的目标是开发一个基于别名对方法的准确高效的指针分析框架。 主要的想法是：（1）新的多关系别名图表示，以允许传递别名关系的准确导出，（2）新的基于多关系别名图的过程间分析框架，以非常低的成本导出准确的参数和全局别名信息，（3）新的基于静态单一分配（SSA）形式的上下文敏感函数级分析框架，以低成本实现高准确度，（4）（2）和（3）的迭代应用，以低得多的成本接近上下文敏感分析的准确性，以及（5）区分可能和确定的别名，以在未来的高性能指令集体系结构中有效地使用运行时消歧支持。 基于原型编译器实现和大型C，C++和Java输入程序的理论结果和经验发表，以推进指针分析的艺术状态。