Variable-precision reaching definitions analysis

Ascertaining the reaching definitions from the source code can give views o f the linkages in that source code. These views can aid source code analyse s, such as impact analysis and program slicing, and tan assist in the rever se engineering and re-engineering of large legacy systems. Maintainers like to do such activities interactively and value fast responses from program analysis tools, Therefore the control of the trade off between accuracy and efficiency should be given to the maintainer. Since some real world progra ms, especially in languages like C, make much use of pointers, and efficien t points-to analysis should be integrated within the computation of the dat a dependencies during the process of ascertaining the reaching definitions. This paper proposes three different approaches to the analysis of the reach ing definitions based on different levels of precision, reflecting differen ces in their sensitivity to the calling context and the control flow. The l east precise approach produces an overestimate by an average of 41% of data dependencies compared to the approach with the highest degree of precision , The result for the least precise approach is conservative because all det ectable data dependencies are included, and is far faster than the more pre cise approaches, Runs on a test suite show an almost 2000 to 1 reduction in execution time by the least precise approach compared with the most precis e approach, The intermediate approach is more than 30 times faster than the most precise approach, and much more precise than the least precise one (a n average of 2% extra dependencies compared to the most precise approach), Therefore, while on medium size systems the intermediate approach could be a good compromise, on large systems the least precise approach becomes extr emely valuable, being the only one feasible, Copyright (C) 1999 John Wiley & Sons, Ltd.