Efficient online cycle detection technique combining with Steensgaard points-to information

摘要

Pointer analysis is a key static analysis during compilation. Several client analyses and transformations rely on precise pointer information to optimize programs. Therefore, it is paramount to improve the efficiency of pointer analysis. A critical piece of an inclusion-based pointer analysis is online cycle detection. The efficiency of pointer analysis is significantly influenced by the efficacy of detecting cycles. Existing approaches perform poorly when they guess cycle formation in the constraint graph. Thus, the number of false cycle-detection triggers of the state-of-the-art methods is considerably high (over 99% on Standard Performance Evaluation Corporation (SPEC) benchmarks). In this paper, we propose bootstrapping as a way to improve cycle detection predictability of pointer analysis. The main idea is to run a sequence of increasingly precise analyses to feed into the next more precise analysis to improve the efficiency of the latter analysis. In this process, we develop a new notion of pointer equivalence called constraint equivalence. Using Steensgaard's fast unification algorithm as the bootstrap, we devise a new cycle detection method for Andersen's inclusion-based analysis. We measure the effectiveness of our approach using a suite of programs including SPEC 2000 benchmarks and two open-source programs, and find that our method can reduce the number of false cycle detections by almost 22x compared with a state-of-the-art method. This leads to an overall analysis time improvement of 18% on an average. Copyright (c) 2015 John Wiley & Sons, Ltd.