An empirical study on the granularity of pointer analysis in C programs

Tong Chen, Jin Lin, Wei Chung Hsu, Pen Chung Yew

Research output: Chapter in Book/Report/Conference proceedingConference contribution

3 Scopus citations

Abstract

Pointer analysis plays a critical role in modern C compilers because of the frequent appearances of pointer expressions. It is even more important for data dependence analysis, which is essential in exploiting parallelism, because complex data structures such as arrays are often accessed through pointers in C. One of the important aspects of pointer analysis methods is their granularity, the way in which the memory objects are named for analysis. The naming schemes used in a pointer analysis affect its effectiveness, especially for pointers pointing to heap memory blocks. In this paper, we present a new approach that applies the compiler analysis and profiling techniques together to study the impact of the granularity in pointer analyses. An instrumentation tool, based on the Intel's Open Resource Compiler (ORC), is devised to simulate different naming schemes and collect precise target sets for indirect references at runtime. The collected target sets are then fed back to the ORC compiler to evaluate the effectiveness of different granularity in pointer analyses. The change of the alias queries in the compiler analyses and the change of performance of the output code at different granularity levels are observed. With the experiments on the SPEC CPU2000 integer benchmarks, we found that 1) finer granularity of pointer analysis show great potential in optimizations, and may bring about up to 15% performance improvement, 2) the common naming scheme, which gives heap memory blocks names according to the line number of system memory allocation calls, is not powerful enough for some benchmarks. The wrapper functions for allocation or the user-defined memory management functions have to be recognized to produce better pointer analysis result, 3) pointer analysis of fine granularity requires inter-procedural analysis, and 4) it is also quite important that a naming scheme distinguish the fields of a structure in the targets.

Original languageEnglish (US)
Title of host publicationLanguages and Compilers for Parallel Computing - 15th Workshop, LCPC 2002, Revised Papers
PublisherSpringer Verlag
Pages157-171
Number of pages15
ISBN (Print)3540307818, 9783540307815
DOIs
StatePublished - 2005
Event15th Workshop on Languages and Compilers for Parallel Computing, LCPC 2002 - College Park, MD, United States
Duration: Jul 25 2002Jul 27 2002

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume2481 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Other

Other15th Workshop on Languages and Compilers for Parallel Computing, LCPC 2002
CountryUnited States
CityCollege Park, MD
Period7/25/027/27/02

Fingerprint Dive into the research topics of 'An empirical study on the granularity of pointer analysis in C programs'. Together they form a unique fingerprint.

Cite this