We have presented a fully context-sensitive pointer analysis algorithm and have shown that it is very efficient for a set of C programs. This algorithm is based on the simple intuition that the aliases among the inputs to a procedure are the same in most calling contexts. Even though it is difficult to summarize the behavior of a procedure for all inputs, we can find partial transfer functions for the input aliases encountered in the program. This allows us to analyze a procedure once and reuse the results in many other contexts.
Even though our algorithm is still exponential in the worst case, we have so far found that it performs well. As long as most procedures are always called with the same alias patterns, our algorithm will continue to avoid exponential behavior. To be safe, after reaching some limit on the number of PTFs per procedure, we could easily generalize the PTFs instead of creating new ones.
Our analysis can handle all the features of the C language. We make conservative assumptions where necessary to ensure that our results are safe. Even though we may occasionally lose some precision due to these conservative assumptions, we believe it is important to handle the kinds of code found in real programs, even if they do not strictly conform to the ANSI standard.
Our success so far has been encouraging, and our next step is to experiment with large, real-world applications. Our preliminary evaluation suggests that our approach may scale well for larger inputs, since most procedures only require one PTF. We also need to use our pointer analysis in more compiler optimizations to determine if the results obtained are sufficiently precise. Although there is more work to be done, we believe this is a major step towards making pointer analysis practical.