Evaluating the effectiveness of pointer alias analyses

This paper describes an empirical comparison of the effectiveness of six co ntext-insensitive pointer analysis algorithms that use varying degrees of f low-sensitivity. Four of the algorithms are flow-insensitive, one is flow-s ensitive, and another is flow-insensitive, but uses precomputed flow-sensit ive information. The effectiveness of each analysis is quantified in terms of compile-time efficiency and precision. Efficiency is reported by measuri ng CPU time and memory consumption of each analysis. Precision is reported by measuring the computed solutions at the program points where a pointer i s dereferenced. The results of this paper will help implementors determine which pointer analysis is appropriate for their application. (C) 2001 Elsev ier Science B.V. All rights reserved.