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.