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

点击翻译按钮获取中文摘要

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.