Wave Propagation and Deep Propagation for Pointer Analysis
Authors:
- Fernando Magno Quintao PereiraFPFernando Magno Quintao Pereira
- Daniel BerlinDBDaniel Berlin
- 1 March 2009
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 126-135
Abstract
This paper describes two new algorithms for solving inclusion based points-to analysis. The first algorithm, the wave propagation method, is a modified version of an early technique presented by Pearce et al; however, it greatly improves on the running time of its predecessor. The second algorithm, the deep propagation method, is a more light-weighted analysis, that requires less memory. We have compared these algorithms with three state-of-the-art techniques by Hardekopf-Lin, Heintze-Tardieu and Pearce-Kelly-Hankin. Our experiments show that deep propagation has the best average execution time across a suite of 17 well-known benchmarks, the lowest memory requirements in absolute numbers, and the fastest absolute times for benchmarks under 100,000 lines of code. The memory-hungry wave propagation has the fastest absolute running times in a memory rich execution environment, matching the speed of the best known points-to analysis algorithms in large benchmarks.Keywords
This publication has 15 references indexed in Scilit:
- Towards scalable flow and context sensitive pointer analysis2005
- Cloning-based context-sensitive pointer alias analysis using binary decision diagrams2004
- Efficient field-sensitive pointer analysis for C2004
- Online cycle detection and difference propagation for pointer analysis2004
- Modular interprocedural pointer analysis using access paths2000
- Off-line variable substitution for scaling points-to analysisACM SIGPLAN Notices, 2000
- Partial online cycle elimination in inclusion constraint graphs1998
- Points-to analysis in almost linear time1996
- On finding the strongly connected components in a directed graphInformation Processing Letters, 1994
- Depth-First Search and Linear Graph AlgorithmsSIAM Journal on Computing, 1972