Polymorphic splitting: an effective polyvariant flow analysis Export

@article{citeulike:4884, abstract = {This article describes a general-purpose program analysis that computes global control-flow and data-flow information for higher-order, call-by-value languages. The analysis employs a novel form of polyvariance called polymorhic splitting that uses let-expressions as syntactic clues to gain precision. The information derived from the analysis is used both to eliminate run-time checks and to inline procedure. The analysis and optimizations have been applied to a suite of Scheme programs. Experimental results obtained from the prototype implementation indicate that the analysis is extremely precise and has reasonable cost. Compared to monovariant flow analyses such as 0CFA, or analyses based on type inference such as soft typing, the analysis eliminates significantly more run-time checks. Run-time check elimination and inlining together typically yield a 20 to 40\% performance improvement for the benchmark suite, with some programs running four times as fast.}, address = {New York, NY, USA}, author = {Wright, Andrew K. and Jagannathan, Suresh}, citeulike-article-id = {4884}, citeulike-linkout-0 = {http://portal.acm.org/citation.cfm?id=271523}, citeulike-linkout-1 = {http://dx.doi.org/10.1145/271510.271523}, doi = {10.1145/271510.271523}, issn = {0164-0925}, journal = {ACM Trans. Program. Lang. Syst.}, keywords = {cfa, dependent-cfa}, month = {January}, number = {1}, pages = {166--207}, posted-at = {2004-12-23 17:02:30}, publisher = {ACM}, title = {Polymorphic splitting: an effective polyvariant flow analysis}, url = {http://dx.doi.org/10.1145/271510.271523}, volume = {20}, year = {1998} }

TY - JOUR ID - citeulike:4884 L3 - citeulike-article-id:4884 N2 - This article describes a general-purpose program analysis that computes global control-flow and data-flow information for higher-order, call-by-value languages. The analysis employs a novel form of polyvariance called polymorhic splitting that uses let-expressions as syntactic clues to gain precision. The information derived from the analysis is used both to eliminate run-time checks and to inline procedure. The analysis and optimizations have been applied to a suite of Scheme programs. Experimental results obtained from the prototype implementation indicate that the analysis is extremely precise and has reasonable cost. Compared to monovariant flow analyses such as 0CFA, or analyses based on type inference such as soft typing, the analysis eliminates significantly more run-time checks. Run-time check elimination and inlining together typically yield a 20 to 40% performance improvement for the benchmark suite, with some programs running four times as fast. IS - 1 JF - ACM Trans. Program. Lang. Syst. SN - 0164-0925 AD - New York, NY, USA EP - 207 TI - Polymorphic splitting: an effective polyvariant flow analysis PB - ACM VL - 20 SP - 166 KW - cfa KW - dependent-cfa AU - Wright, Andrew AU - Jagannathan, Suresh PY - 1998/01// UR - http://dx.doi.org/10.1145/271510.271523 ER -