image placeholder

Prof. Ben Hardekopf’s paper, titled “Flow-Sensitive Pointer Analysis for Millions of Lines of Code,” wins the Best Paper Award at CGO’11 (Symposium on Code Generation and Optimization).

The International Symposium on Code Generation and Optimization (CGO) provides a premier venue to bring together researchers and practitioners working at the interface of hardware and software on a wide range of optimization and code generation techniques and related issues. The conferences spans the spectrum from purely static to fully dynamic approaches, including techniques ranging from pure software-based methods to architectural features and support.

The award-winning work is related to pointer analysis, a fundamental enabling technology for static program analysis: applications including code verification and bug finding, security analysis, code refactoring, code comprehension, parallelization and optimization, and many more all rely on the information provided by pointer analysis. Flow-sensitivity is an important dimension of precision for pointer analysis, however, historically flow-sensitive pointer analysis has been unable to scale to large programs (i.e., ones with millions of lines of code).

Prof. Ben Hardekopf and his collaborator, Prof. Calvin Lin at UT Austin, present a new flow-sensitive pointer analysis algorithm that is an order of magnitude faster than the existing state of the art, enabling for the first time flow-sensitive pointer analysis for programs with millions of lines of code. His flow-sensitive algorithm is based on a sparse representation of program code created by a staged, flow-insensitive pointer analysis. This new algorithm is actually a member of a new family of pointer analysis algorithms that opens new opportunities for precise pointer analysis that have yet to be explored.