Repository logo
 

Flow- and Context-Sensitive Points-to Analysis using Generalized Points-to Graphs

Accepted version
Peer-reviewed

Type

Book chapter

Change log

Authors

Gharat, Pritam M. 
Khedker, Uday P. 
Mycroft, Alan 

Abstract

Bottom-up interprocedural methods of program analysis construct summary flow functions for procedures to capture the effect of their calls and have been used effectively for many analyses. However, these methods seem computationally expensive for flow- and context-sensitive points-to analysis (FCPA) which requires modelling unknown locations accessed indirectly through pointers. Such accesses are commonly handled by using placeholders to explicate unknown locations or by using multiple call-specific summary flow functions. We generalize the concept of points-to relations by using the counts of indirection levels leaving the unknown locations implicit. This allows us to create summary flow functions in the form of generalized points-to graphs (GPGs) without the need of placeholders. By design, GPGs represent both memory (in terms of classical points-to facts) and memory transformers (in terms of generalized points-to facts). We perform FCPA by progressively reducing generalized points-to facts to classical points-to facts. GPGs distinguish between may and must pointer updates thereby facilitating strong updates within calling contexts. The size of GPGs is linearly bounded by the number of variables and is independent of the number of statements. Empirical measurements on SPEC benchmarks show that GPGs are indeed compact in spite of large procedure sizes. This allows us to scale FCPA to 158 kLoC using GPGs (compared to 35 kLoC reported by liveness-based FCPA). Thus GPGs hold a promise of efficiency and scalability for FCPA without compromising precision.

Description

This is the accepted manuscript. The final version is available from Springer at http://dx.doi.org/10.1007/978-3-662-53413-7_11.

Title

Flow- and Context-Sensitive Points-to Analysis using Generalized Points-to Graphs

Keywords

Is Part Of

Book type

Publisher

Springer

ISBN

978-3-662-53413-7