HyperLink   Bottom-up and Top-down Context-Sensitive Summary-based Pointer Analysis.
Publication Year:
  Erik M. Nystrom, Hong-Seok Kim, Wen-mei Hwu
  Proceedings of the 11th Static Analysis Symposium, August 2004

This paper addresses scalability and accuracy of summary-based context-sensitive pointer analysis formulated as a two-phase computation. The first phase, or bottom-up phase, propagates procedure summaries from callees to callers. Then, the second phase, or top-down phase, computes the actual pointer information. These two phases can be independently context-sensitive.

Having observed the problems that procedural side effects cause, we developed a bottom-up phase that constructs concise procedure summaries in a manner that permits their subsequent removal. This transformation results in an efficient two-phase pointer analysis in the style of Andersen that is simultaneously bottom-up and top-down context-sensitive. Context sensitivity becomes inherent to even a context-insensitive analysis allowing for an accurate and efficient top-down phase. The implemented context-sensitive analysis exhibits scalability comparable to that of its context-insensitive counterpart. For instance, to analyze 176.gcc, the largest C benchmark in SPEC 2000, our analysis takes 190 seconds as opposed to 44 seconds for the context-insensitive analysis. Given the common practice of treating recursive subgraphs context-insensitively, its accuracy is equivalent to an analysis which completely inlines all procedure calls.