Level by Level: Making Flow- and Context-Sensitive Pointer Analysis Scalable for Millions of Lines of Code

We present a practical and scalable method for flow- and contextsensitive (FSCS) pointer analysis for C programs. Our method analyzes the pointers in a program level by level in terms of their points-to levels, allowing the points-to relations of the pointers at a particular level to be discovered b...

Full description

Bibliographic Details
Main Authors: Hongtao Yu, Jingling Xue, Wei Huo, Xiaobing Feng, Zhaoqing Zhang
Other Authors: The Pennsylvania State University CiteSeerX Archives
Format: Text
Language:English
Subjects:
Algorithms
Languages
Performance Pointer Analysis
Alias Analysis
The Pointers
Online Access:http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.210.3191
http://www.cse.unsw.edu.au/~jingling/papers/cgo10.pdf
Description
Summary:We present a practical and scalable method for flow- and contextsensitive (FSCS) pointer analysis for C programs. Our method analyzes the pointers in a program level by level in terms of their points-to levels, allowing the points-to relations of the pointers at a particular level to be discovered based on the points-to relations of the pointers at this level and higher levels. This level-by-level strategy can enhance the scalability of the FSCS pointer analysis in two fundamental ways, by enabling (1) fast and accurate flowsensitive analysis on full sparse SSA form using a flow-insensitive algorithm and (2) fast and accurate context-sensitive analysis using a full transfer function and a meet function for each procedure. Our level-by-level algorithm, LevPA, gives rises to (1) a precise and compact SSA representation for subsequent program analysis and optimization tasks and (2) a flow- and context-sensitive MAY / MUST mod (modification) set and read set for each procedure. Our preliminary results show that LevPA can analyze some programs with over a million lines of C code in minutes, faster than the state-of-the-art FSCS methods.

Similar Items