Quantifying Uncertainty in Points-To Relations

Constantino Ribeiro and Marcelo Cintra

The 19th International Workshop on Languages and Compilers for Parallel Computing (LCPC 2006)
New Orleans, Louisiana, November 2-4, 2006

---

Abstract

For programs that make extensive use of pointers, pointer analysis is often critical for the effectiveness of optimizing compilers and tools for reasoning about program behavior and correctness. Static pointer analysis has been extensively studied and several algorithms have been proposed, but these only provide approximate solutions. As such inaccuracy may hinder further optimizations, it is important to understand how short these algorithms come of providing accurate information about the points-to relations.

This paper attempts to quantify the amount of uncertainty of the points-to relations that remains after a state-of-the-art context- and flow-sensitive pointer analysis algorithm is applied to two well-known benchmark suites: SPEC integer and MediaBench. Unlike previous work that compared run-time behavior against less accurate context- and flow-insensitive algorithms, the goal of this work is to quantify the amount of uncertainty that is intrinsic to the applications and that defeat even the most accurate static analyses.

Experimental results show that for most of the benchmarks the static pointer analysis is very accurate, but for some benchmarks a significant fraction, up to 33%, of their accesses via pointer de-references cannot be statically fully disambiguated. As expected, we find that dynamically allocated memory objects is the main culprit for the inaccuracy of the static analysis. The run-time results show that most of this ambiguity disappears and a large fraction of the pointer de-references resolve into a single target.

---

  

START Conference Manager (V2.53.1)

Maintainer: rrgerber@softconf.com