Bottom-up and top-down context-sensitive summary-based pointer analysis

Erik M. Nystrom, Hong Seok Kim, Wen Mei W. Hwu

Research output: Contribution to journalArticle

Abstract

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 [1] 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.

Original languageEnglish (US)
Pages (from-to)165-180
Number of pages16
JournalLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume3148
StatePublished - Dec 1 2004

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint Dive into the research topics of 'Bottom-up and top-down context-sensitive summary-based pointer analysis'. Together they form a unique fingerprint.

  • Cite this