References

[1] O. Agesen, D. Detlefs, and J. E. Moss. Garbage collection and local variable type-precision and liveness in Java virtual machines. In Proceedings of the ACM SIGPLAN Conference on Programming Language Design and Implementation, pages 269279. ACM, 1998. [2] A. V. Aho, J. E. Hopcroft, and J. D. Ullman. The Design and Analysis of Computer Algorithms. Addison-Wesley, 1974. [3] A. V. Aho, M. S. Lam, R. Sethi, and J. D. Ullman. Compilers: Principles, Techniques, and Tools (2/e). Addison-Wesley Longman Publishing Co., Inc., 2006. [4] F. E. Allen. Control ow analysis. ACM SIGPLAN Notices, 5(7):119, 1970. [5] F. E. Allen. A basis for program optimization. In IFIP Congress (1), pages 385390. North Holland Publishing Company, 1971. [6] F. E. Allen. Interprocedural data ow analysis. In Proceedings of IFIP Congress 74, pages 398408. North Holland Publishing Company, 1974. [7] F. E. Allen and J. Cocke. A program data ow analysis procedure. Communications of the ACM, 19(3):137147, 1976. [8] B. Alpern, M. N. Wegman, and F. K. Zadeck. Detecting equality of variables in programs. In Proceedings of the ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, pages 111. ACM, 1988. [9] L. O. Andersen. Program Analysis and Specialization for the C Programming Language. PhD thesis, DIKU, University of Copenhagen, 1994. [10] A. W. Appel and M. Ginsburg. Modern Compiler Implementation in C. Cambridge University Press, 1998. [11] Andrew W. Appel. SSA is functional programming. ACM SIGPLAN Notices, 33(4):1720, 1998. [12] J. Banning. An ecient way to nd the side eects of procedure calls and aliases of variables. In Proceedings of the ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, pages 2941. ACM, 1979. [13] J. M. Barth. An interprocedural data ow analysis algorithm. In Proceedings of the ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, pages 119131. ACM, 1977.

371
2009 by Taylor & Francis Group, LLC

372

References

[14] Jerey M. Barth. A practical interprocedural data ow analysis algorithm. Communications of the ACM, 21(9):724736, 1978. [15] B. Blanchet. Escape analysis for object-oriented languages: application to Java. In Proceedings of the ACM SIGPLAN Conference on Object-oriented Programming Systems, Languages, and Applications, pages 2034. ACM, 1999. [16] B. Blanchet. Escape analysis for JavaT M : Theory and practice. ACM Transactions on Programming Languages and Systems, 25(6):713775, 2003. [17] R. Bodik, R. Gupta, and M. L. Soa. Complete removal of redundant computations. In Proceedings of the ACM SIGPLAN Conference on Programming Language Design and Implementation, pages 114. ACM, 1998. [18] P. Briggs, K. D. Cooper, T. J. Harvey, and L. T. Simpson. Practical improvements to the construction and destruction of static single assignment form. SoftwarePractice and Experience, 28(8):859881, 1998. [19] D. Callahan. The program summary graph and ow-sensitive interprocedural data ow analysis. In Proceedings of the ACM SIGPLAN Conference on Programming Language Design and Implementation, pages 4756. ACM, 1988. [20] D. Callahan, A. Carle, M. W. Hall, and K. Kennedy. Constructing the procedure call multigraph. IEEE Transactions on Software Engineering, 16(4):483487, 1990. [21] J. Choi, M. Burke, and P. Carini. Ecient ow-sensitive interprocedural computation of pointer-induced aliases and side eects. In Proceedings of the ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, pages 232245. ACM, 1993. [22] J. Choi, R. Cytron, and J. Ferrante. Automatic construction of sparse data ow evaluation graphs. In Proceedings of the ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, pages 5566. ACM, 1991. [23] J. Choi, M. Gupta, M. Serrano, V. C. Sreedhar, and S. Midki. Escape analysis for Java. In Proceedings of the ACM SIGPLAN Conference on Objectoriented Programming Systems, Languages, and Applications, pages 119. ACM, 1999. [24] J. Cocke. Global common subexpression elimination. ACM SIGPLAN Notices, 5(7):2024, 1970. [25] K. Cooper. Analyzing aliases of reference formal parameters. In Proceedings of the ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, pages 281290. ACM, 1985. [26] K. D. Cooper and K. Kennedy. Fast interprocedural alias analysis. In Proceedings of the ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, pages 4959. ACM, 1989.

2009 by Taylor & Francis Group, LLC

Data Flow Analysis: Theory and Practice

373

[27] T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein. Introduction to Algorithms, (2/e). The MIT Press and McGraw-Hill Book Company, 2001. [28] R. Cytron, J. Ferrante, B. K. Rosen, M. N. Wegman, and F. K. Zadeck. Eciently computing static single assignment form and the control dependence graph. ACM Transactions on Programming Languages and Systems, 13(4):451490, 1991. [29] B. A. Davey and H. A. Priestley. Introduction to Lattices and Order (2/e). Cambridge University Press, 2002. [30] D. M. Dhamdhere and U. P. Khedker. Complexity of bidirectional data ow analysis. In Proceedings of the ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, pages 397408. ACM, 1993. [31] D. M. Dhamdhere, B. K. Rosen, and F. K. Zadeck. How to analyze large programs eciently and informatively. In Proceedings of the ACM SIGPLAN Conference on Programming Language Design and Implementation, pages 212223. ACM, 1992. [32] E. Duesterwald, R. Gupta, and M. L. Soa. Demand-driven computation of interprocedural data ow. In Proceedings of the ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, pages 3748. ACM, 1995. [33] E. Duesterwald, R. Gupta, and M. L. Soa. A practical framework for demand-driven interprocedural data ow analysis. ACM Transactions on Programming Languages and Systems, 19(6):9921030, 1997. [34] M. Emami, R. Ghiya, and L. J. Hendren. Context-sensitive interprocedural points-to analysis in the presence of function pointers. In Proceedings of the ACM SIGPLAN Conference on Programming Language Design and Implementation, pages 242256. ACM, 1994. [35] M. F hndrich, J. S. Foster, Z. Su, and A. Aiken. Partial online cycle elimia nation in inclusion constraint graphs. In Proceedings of the ACM SIGPLAN Conference on Programming Language Design and Implementation, pages 8596. ACM, 1998. [36] M. F hndrich, J. Rehof, and M. Das. Scalable context-sensitive ow analysis a using instantiation constraints. In Proceedings of the ACM SIGPLAN Conference on Programming Language Design and Implementation, pages 253263. ACM, 2000. [37] S. Graham and M. Wegman. A fast and usually linear algorithm for global data ow analysis. Journal of ACM, 23(1):172202, 1976. [38] D. Grove and C. Chambers. A framework for call graph construction algorithms. ACM Transactions on Programming Languages and Systems, 23(6):685746, 2001.

2009 by Taylor & Francis Group, LLC

374

References

[39] D. Grove and L. Torczon. Interprocedural constant propagation: a study of jump function implementation. In Proceedings of the ACM SIGPLAN Conference on Programming Language Design and Implementations, pages 9099. ACM, 1993. [40] D. Grune, H. E. Bal, C. J. H. Jacobs, and K. G. Langendoen. Modern Compiler Design. John Wiley & Sons, 2000. [41] S. Hack. Register Allocation for Programs in SSA Form. PhD thesis, Universit t Karlsruhe, 2007. a [42] S. Hack, D. Grund, and G. Goos. Register allocation for programs in SSAform. In Proceedings of the International Conference on Compiler Construction, pages 247262. Springer-Verlag, 2006. [43] M. W. Hall and K. Kennedy. Ecient call graph analysis. ACM Letters on Programming Languages and Systems, 1(3):227242, 1992. [44] M. S. Hecht. Flow Analysis of Computer Programs. Elsevier North-Holland Inc., 1977. [45] M. S. Hecht and J. D. Ullman. Flow graph reducibility. In Proceedings of the ACM Symposium on Theory of Computing, pages 238250. ACM, 1972. [46] M. S. Hecht and J. D. Ullman. Characterization of reducible ow graphs. Journal of ACM, 21(3):367375, 1974. [47] M. Hind. Pointer analysis: havent we solved this problem yet? In Proceedings of the ACM SIGPLAN-SIGSOFT Workshop on Program Analysis for Software Tools and Engineering, pages 5461. ACM, 2001. [48] M. Hind, M. Burke, P. Carini, and J. Choi. Interprocedural pointer alias analysis. ACM Transactions on Programming Languages and Systems, 21(4):848 894, 1999. [49] J. B. Kam and J. D. Ullman. Global data ow analysis and iterative algorithms. Journal of ACM, 23(1):158171, 1976. [50] J. B. Kam and J. D. Ullman. Monotone data ow analysis frameworks. Acta Informatica, 7(3):305317, 1977. [51] A. Kanade, U. P. Khedker, and A. Sanyal. Heterogeneous xed points with application to points-to analysis. In Proceedings of the Asian Symposium on Programming Languages and Systems, pages 298314. Springer-Verlag, 2005. [52] A. Karkare, A. Sanyal, and U. P. Khedker. Eectiveness of garbage collection in MIT/GNU Scheme. CoRR, abs/cs/0611093, 2006. [53] B. Karkare. Complexity and Eciency Issues in Data Flow Analysis. PhD thesis, Indian Institute of Technology, Bombay, 2007.

2009 by Taylor & Francis Group, LLC

Data Flow Analysis: Theory and Practice

375

[54] B. Karkare and U. P. Khedker. An improved bound for call-strings based interprocedural analysis of bit vector frameworks. ACM Transactions on Programming Languages and Systems, 29(6):38, 2007. [55] K. Kennedy. A global ow analysis algorithm. International Journal of Computer Mathematic, 3(1):515, 1971. [56] K. Kennedy. Node listings applied to data ow analysis. In Proceedings of the ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, pages 1021. ACM, 1975. [57] K. Kennedy. A survey of data ow analysis techniques, 1981. In [77]. [58] R. Kennedy, S. Chan, S. Liu, R. Lo, P. Tu, and F. Chow. Partial redundancy elimination in SSA form. ACM Transactions on Programming Languages and Systems, 21(3):627676, 1999. [59] U. P. Khedker. Data ow analysis. In Y. N. Srikant and Priti Shankar, editors, The Compiler Design Handbook: Optimizations & Machine Code Generation. CRC Press, 2002. [60] U. P. Khedker and D. M. Dhamdhere. A generalized theory of bit vector data ow analysis. ACM Transactions on Programming Languages and Systems, 16(5):14721511, 1994. [61] U. P. Khedker and B. Karkare. Eciency, precision, simplicity, and generality in interprocedural data ow analysis: Resurrecting the classical call strings method. In Proceedings of the International Conference on Compiler Construction, pages 213228. Springer-Verlag, 2008. [62] U. P. Khedker, A. Sanyal, and A. Karkare. Heap reference analysis using access graphs. ACM Transactions on Programming Languages and Systems, 30(1):1, 2007. [63] G. Kildall. A unied approach to global program optimization. In Proceedings of the ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, pages 194206. ACM, 1973. [64] K. Knobe and V. Sarkar. Array SSA form and its use in parallelization. In Proceedings of the ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, pages 107120. ACM, 1998. [65] J. Knoop, O. R thing, and B. Steen. Lazy code motion. In Proceedings u of the ACM SIGPLAN Conference on Programming Language Design and Implementation, pages 224234. ACM, 1992. [66] W. Landi and B. G. Ryder. A safe approximate algorithm for interprocedural pointer aliasing. In Proceedings of the ACM SIGPLAN Conference on Programming Language Design and Implementation, pages 235248. ACM, 1992.

2009 by Taylor & Francis Group, LLC

376

References

[67] W. Landi, B. G. Ryder, and S. Zhang. Interprocedural side eect analysis with pointer aliasing. In Proceedings of the ACM SIGPLAN Conference on Programming Language Design and Implementation, pages 5667. ACM, 1993. [68] T. Lengauer and R. E. Tarjan. A fast algorithm for nding dominators in a owgraph. ACM Transactions on Programming Languages and Systems, 1(1):121141, 1979. [69] O. Lhot k and L. Hendren. Context-sensitive points-to analysis: is it worth a it? In Proceedings of the International Conference on Compiler Construction, pages 4764. Springer-Verlag, 2006. [70] E. S. Lowry and C. W. Medlock. Object code optimization. Communications of the ACM, 12(1):1322, 1969. [71] T. J. Marlowe and B. G. Ryder. Properties of data ow frameworks. Acta Informatica, 28(2):121163, 1990. [72] F. Martin. Experimental comparison of call string and functional approaches to interprocedural analysis. In Proceedings of the International Conference on Compiler Construction, pages 6375. Springer-Verlag, 1999. [73] C. E. McDowell. Reducing garbage in java. 33(9):8486, 1998. ACM SIGPLAN Notices,

[74] E. Morel and C. Renvoise. Global optimization by suppression of partial redundancies. Communications of the ACM, 22(2):96103, 1979. [75] R. Morgan. Building an Optimizing Compiler. Digital Press, 1998. [76] S. S. Muchnick. Advanced Compiler Design and Implementation. Morgan Kaufmann Publishing Co., 1997. [77] S. S. Muchnick and N. D. Jones. Program Flow Analysis : Theory and Applications. Prentice-Hall Inc., 1981. [78] M. M ller-Olm and O. R thing. On the complexity of constant propagation. u u In Proceedings of the European Symposium on Programming Languages and Systems, pages 190205. Springer-Verlag, 2001. [79] E. M. Myers. A precise inter-procedural data ow algorithm. In Proceedings of the ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, pages 219230. ACM, 1981. [80] F. Nielson, H. R. Nielson, and C. Hankin. Principles of Program Analysis. Springer-Verlag, 1998. [81] A. Reid, J. McCorquodale, J. Baker, W. Hsieh, and J. Zachary. The need for predictable garbage collection. In Proceedings of the ACM SIGPLAN Workshop on Compiler Support for System Software. ACM, 1999. [82] T. W. Reps, S. Horwitz, and S. Sagiv. Precise interprocedural dataow analysis via graph reachability. In Proceedings of the ACM SIGPLAN-SIGACT

2009 by Taylor & Francis Group, LLC

Data Flow Analysis: Theory and Practice

377

Symposium on Principles of Programming Languages, pages 4961. ACM, 1995. [83] S. E. Richardson and M. Ganapathi. Interprocedural optimizations : Experimental results. Software Practice and Experience, 19(2):149169, 1989. [84] B. K. Rosen. Monoids for rapid data ow analysis. SIAM Journal of Computing, 9(1):159196, 1980. [85] B. K. Rosen, M. N. Wegman, and F. K. Zadeck. Global value numbers and redundant computations. In Proceedings of the ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, pages 1227. ACM, 1988. [86] B. G. Ryder and M. C. Paull. Elimination algorithms for data ow analysis. ACM Computing Surveys, 18(3):277316, 1986. [87] M. Sagiv, T. Reps, and S. Horwitz. Precise interprocedural dataow analysis with applications to constant propagation. Theoretical Computer Science, 167(12):131170, 1996. [88] S. Sagiv, T. W. Reps, and R. Wilhelm. Parametric shape analysis via 3valued logic. ACM Transactions on Programming Languages and Systems, 24(3):217298, 2002. [89] R. Shaham, E. K. Kolodner, and M. Sagiv. On eectiveness of GC in Java. In International Symposium on Memory Management, pages 1217. ACM, 2000. [90] R. Shaham, E. K. Kolodner, and M. Sagiv. Heap proling for space-ecient java. In Proceedings of the ACM SIGPLAN Conference on Programming Language Design and Implementation, pages 104113. ACM, 2001. [91] R. Shaham, E. K. Kolodner, and M. Sagiv. Estimating the impact of heap liveness information on space consumption in Java. In Proceedings of the International Symposium on Memory Management, pages 6475. ACM, 2002. [92] R. Shaham, E. Yahav, E. K. Kolodner, and S. Sagiv. Establishing local temporal heap safety properties with applications to compile-time memory management. In Proceedings of the International Static Analysis Symposium, pages 483503. Springer-Verlag, 2003. [93] M. Sharir and A. Pnueli. Two approaches to interprocedural data ow analysis. In S. S. Muchnick and N. D. Jones, editors, Program Flow Analysis : Theory and Applications. Prentice-Hall Inc., 1981. [94] T. C. Spillman. Exposing side eects in a PL/I optimizing compiler. In Proceedings of IFIP Congress 71, pages 376381. North Holland Publishing Company, 1971. [95] V. C. Sreedhar and G. R. Gao. A linear time algorithm for placing -nodes. In Proceedings of the ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, pages 6273. ACM, 1995.

2009 by Taylor & Francis Group, LLC

Data Flow Analysis: Theory and Practice

378

[96] V. C. Sreedhar, R. Dz-Ching Ju, D. M. Gillies, and V. Santhanam. Translating out of static single assignment form. In Proceedings of the International Symposium on Static Analysis, pages 194210, 1999. [97] B. Steensgaard. Points-to analysis in almost linear time. In Proceedings of the ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, pages 3241. ACM, 1996. [98] R. E. Tarjan. Fast algorithms for solving path problems. Journal of ACM, 28(3):594614, 1981. [99] A. Tarski. A lattice-theoretical xpoint theorem and its applications. Pacic Journal of Mathematics, 5(2):285309, 1955. [100] J. D. Ullman. Fast algorithms for the elimination of common subexpressions. Acta Informatica, 2(3):191213, 1973. [101] V. Vyssotsky and P. Wegner. A graph theoretical FORTRAN source language analyzer. AT & T Bell Laboratories, Murray Hill, N. J., 1963. (Manuscript). [102] M. N. Wegman and F. K. Zadeck. Constant propagation with conditional branches. ACM Transactions on Programming Languages and Systems, 13(2):181210, 1991. [103] M. N. Wegman and F. K. Zadeck. Constant propagation with conditional branches. ACM Transactions on Programming Languages and Systems, 13(2):181210, 1991. [104] J. Whaley and M. S. Lam. Cloning-based context-sensitive pointer alias analysis using binary decision diagrams. In Proceedings of the ACM SIGPLAN Conference on Programming Language Design and Implementation. ACM, 2004. [105] R. Wilhelm and D. Maurer. Compiler Design. Addison-Wesley, 1995. [106] R. Wilhelm, T. W. Reps, and S. Sagiv. Shape analysis and applications. In Y. N. Srikant and Priti Shankar, editors, The Compiler Design Handbook: Optimizations & Machine Code Generation, pages 175218. CRC Press, 2002. [107] R. P. Wilson and M. S. Lam. Ecient context-sensitive pointer analysis for C programs. In Proceedings of the ACM SIGPLAN Conference on Programming Language Design and Implementation, pages 112. ACM, 1995.

378
2009 by Taylor & Francis Group, LLC