Efficient Computation of Parameterized Pointer Information for Interprocedural Analyses

Abstract

Pointer information that is provided by many algorithms identifies a memory location using the same name throughout a program. Such pointer information is inappropriate for use in analyzing C programs because, using such information, a program analysis may propagate a large amount of spurious information across procedure boundaries. This paper presents a modular algorithm that efficiently computes parameterized pointer information in which symbolic names are introduced to identify memory locations whose addresses may be passed into a procedure. Because a symbolic name may identify different memory locations when the procedure is invoked under different callsites, using parameterized pointer information can help a program analysis reduce the spurious information that is propagated across procedure boundaries. The paper also presents a set of empirical studies, that demonstrate (a) the efficiency of the algorithm, and (b) the benefits of using parameterized pointer information over using non-parameterized pointer information in program analyses. The studies show that using parameterized pointer information may significantly improve the precision and the efficiency of many program analyses.