An Incremental Flow- and Context-Sensitive Pointer Aliasing Analysis

Jyh-Shiarn Yur, Barbara G. Ryder, William Landi

Abstract

Pointer aliasing analysis is used to determine if two object names containing dereferences and/or field selectors, (e.g., *p,q->t), may refer to the same location during execution.Such information is necessary for applications such as dataflow-based testers, program understanding tools, and debuggers, but is expensive to calculate with acceptable precision.Incremental algorithms update data flow information after a program change rather than recomputing it from scratch, under the assumption that the change impact will be limited.Two versions of a practical incremental pointer aliaaing algorithm have been developed, based on Land&Ryder flow-and context-sensitive alias analysis.Empirical results attest to the time savings over exhaustive analysis (a six-fold speedup on average), and the precision of the approximate solution obtained (on average same solution as exhaustive algorithm for 75% of the tests.)

BibTeX

@inproceedings{Yur-al:ICSE99,
  author    = {Jyh{-}Shiarn Yur and
               Barbara G. Ryder and
               William Landi},
  title     = {An Incremental Flow- and {Context-Sensitive} Pointer Aliasing Analysis},
  booktitle = {ICSE},
  pages     = {442--451},
  publisher = {{ACM}},
  year      = {1999},
}

An Incremental Flow- and Context-Sensitive Pointer Aliasing Analysis

Abstract

Related papers