Probabilistic pointer analysis for multithreaded programs

Mohamed A. El-Zawawy

ABSTRACT: The use of pointers and data-structures based on pointers results in circular memory references that are interpreted by a vital compiler analysis, namely pointer analysis. For a pair of memory references at a program point, a typical pointer analysis specifies if the points-to relation between them may exist, definitely does not exist, or definitely exists. The ``may be'' case, which describes the points-to relation for most of the pairs, cannot be dealt with by most compiler optimizations. This is so to guarantee the soundness of these optimizations. However, the ``may be'' case can be capitalized by the modern class of speculative optimizations if the probability that two memory references alias can be measured. Focusing on multithreading, a prevailing technique of programming, this paper presents a new flow-sensitive technique for probabilistic pointer analysis of multithreaded programs. The proposed technique has the form of a type system and calculates the probability of every points-to relation at each program point. The key to our approach is to calculate the points-to information via a post-type derivation. The use of type systems has the advantage of associating each analysis results with a justification (proof) for the correctness of the results. This justification has the form of a type derivation and is very much required in applications like certified code.

Download PDF

4 Downloads 1233 Views

College of Computer and Information Sciences, Al-Imam M.I.-S.I. University, Riyadh 11432, Kingdom of Saudi Arabia

* Corresponding author, E-mail: maelzawawy@cu.edu.eg

Received 13 Apr 2011, Accepted 3 Nov 2011