Pointer analysis : building a foundation for effective program analysis


Pointer analysis : building a foundation for effective program analysis

Show full record

Title: Pointer analysis : building a foundation for effective program analysis
Author: Hardekopf, Benjamin Charles
Abstract: Pointer analysis is a fundamental enabling technology for program analysis. By improving the scalability of precise pointer analysis we can make a positive impact across a wide range of program analyses used for many different purposes, including program verification and model checking, optimization and parallelization, program understanding, hardware synthesis, and more. In this thesis we present a suite of new algorithms aimed at improving pointer analysis scalability. These new algorithms make inclusion-based analysis (the most precise flow- and context-insensitive pointer analysis) over 4x faster while using 7x less memory than the previous state-of-the-art; they also enable flow-sensitive pointer analysis to handle programs with millions of lines of code, two orders of magnitude greater than the previous state-of-the-art. We present a formal framework for describing the space of pointer analysis approximations. The space of possible approximations is complex and multidimensional, and until now has not been well-defined in a formal manner. We believe that the framework is useful as a method to meaningfully compare the precision of the multitude of existing pointer analyses, as well as aiding in the systematic exploration of the entire space of approximations.
Department: Computer Sciences
Subject: Computer algorithms Computer programs Parallel programming (Computer science)
URI: http://hdl.handle.net/2152/18408
Date: 2009-05

Files in this work

Download File: hardekopfb48332.pdf
Size: 819.2Kb
Format: application/pdf

This work appears in the following Collection(s)

Show full record

Advanced Search


My Account