Seminar by Dr. Satish Chandra
Searching for Pointer Analysis
Dr. Satish Chandra
IBM India Research Laboratory
IIT Delhi campus, Hauz Khas, New Delhi
Date: Monday, February 03, 2003
Time: 04:00 PM
Venue: CS-101
Abstract
When we wish to analyze a C program, a major hurdle that we encounter is to determine the behavior of indirect references, a.k.a. pointers. Without any information regarding pointer variables, humans, compilers, and program development tools must make pessimistic assumptions, which can lead to excessively conservative answers. Because "precise" pointer analysis is computationally expensive, practical algorithms to carry out the analysis strike a trade-off between the cost of the analysis and the accuracy of the results obtained. The problem is that it is unclear what is the degree or nature of the approximation computed by these practical algorithms, relative to exact results that could be computed in principle. In this talk, we characterize pointer analysis as a reachability problem on a program's state space. Reachability analysis can be performed approximately--but more efficiently--for a program to which certain basic program transformations have been applied. We show the source of approximation and efficiency in several existing pointer analysis algorithms in terms of these basic program transformations. In addition to giving a common framework for understanding diverse algorithms, our approach has allowed us to explore new combinations of these transformations to identify a new algorithm for pointer analysis.
About the Speaker
Dr Chandra has received his BTech degree in Computer Science and Engineering from IIT Kanpur in 1991. He completed his PhD from University of Wisconsin in 1997. Till recently he was working with AT&T Bells Labs in USA. Recently he has shifted to IBM Delhi. He has published entensively on Compiler Optimizations.