A framework for call graph construction algorithms Export

@article{citeulike:276696, abstract = {A large number of call graph construction algorithms for object-oriented and functional languages have been proposed, each embodying different tradeoffs between analysis cost and call graph precision. In this article we present a unifying framework for understanding call graph construction algorithms and an empirical comparison of a representative set of algorithms. We first present a general parameterized algorithm that encompasses many well-known and novel call graph construction algorithms. We have implemented this general algorithm in the Vortex compiler infrastructure, a mature, multilanguage, optimizing compiler. The Vortex implementation provides a "level playing field" for meaningful cross-algorithm performance comparisons. The costs and benefits of a number of call graph construction algorithms are empirically assessed by applying their Vortex implementation to a suite of sizeable (5,000 to 50,000 lines of code) Cecil and Java programs. For many of these applications, interprocedural analysis enabled substantial speed-ups over an already highly optimized baseline. Furthermore, a significant fraction of these speed-ups can be obtained through the use of a scalable, near-linear time call graph construction algorithm.}, address = {New York, NY, USA}, author = {Grove, David and Chambers, Craig}, citeulike-article-id = {276696}, citeulike-linkout-0 = {http://portal.acm.org/citation.cfm?id=506316}, citeulike-linkout-1 = {http://dx.doi.org/10.1145/506315.506316}, doi = {10.1145/506315.506316}, issn = {0164-0925}, journal = {ACM Trans. Program. Lang. Syst.}, keywords = {abstract-model, algorithm, compiler}, month = {November}, number = {6}, pages = {685--746}, posted-at = {2007-05-29 10:11:45}, priority = {2}, publisher = {ACM}, title = {A framework for call graph construction algorithms}, url = {http://dx.doi.org/10.1145/506315.506316}, volume = {23}, year = {2001} }

TY - JOUR ID - citeulike:276696 L3 - citeulike-article-id:276696 N2 - A large number of call graph construction algorithms for object-oriented and functional languages have been proposed, each embodying different tradeoffs between analysis cost and call graph precision. In this article we present a unifying framework for understanding call graph construction algorithms and an empirical comparison of a representative set of algorithms. We first present a general parameterized algorithm that encompasses many well-known and novel call graph construction algorithms. We have implemented this general algorithm in the Vortex compiler infrastructure, a mature, multilanguage, optimizing compiler. The Vortex implementation provides a "level playing field" for meaningful cross-algorithm performance comparisons. The costs and benefits of a number of call graph construction algorithms are empirically assessed by applying their Vortex implementation to a suite of sizeable (5,000 to 50,000 lines of code) Cecil and Java programs. For many of these applications, interprocedural analysis enabled substantial speed-ups over an already highly optimized baseline. Furthermore, a significant fraction of these speed-ups can be obtained through the use of a scalable, near-linear time call graph construction algorithm. IS - 6 JF - ACM Trans. Program. Lang. Syst. SN - 0164-0925 AD - New York, NY, USA EP - 746 TI - A framework for call graph construction algorithms PB - ACM VL - 23 SP - 685 KW - abstract-model KW - algorithm KW - compiler AU - Grove, David AU - Chambers, Craig PY - 2001/11// UR - http://dx.doi.org/10.1145/506315.506316 ER -