Write barrier removal by static analysis

ABSTRACT

We present a set of static analyses for removing write barriers in programs that use generational garbage collection. To our knowledge, these are the first analyses for this purpose. Our Intraprocedural analysis uses a flow-sensitive pointer analysis to locate variables that must point to the most recently allocated object, then eliminates write barriers on stores to objects accessed via one of these variables. The Callee Type Extension incorporates information about the types of objects allocated in invoked methods, while the Caller Context Extension incorporates information about the most recently allocated object at call sites that invoke the currently analyzed method. Results from our implemented system show that our Full Interprocedural analysis, which incorporates both extensions, can eliminate the majority of the write barriers in most of the programs in our benchmark set, producing modest performance improvements of up to 7% of the overall execution time. Moreover, by dynamically instrumenting the executable, we are able to show that for all but two of our nine benchmark programs, our analysis is close to optimal in the sense that it eliminates the write barriers for almost all store instructions observed not to create a reference from an older object to a younger object.

REFERENCES

• 1: A. W. Appel, Simple generational garbage collection and fast allocation, Software—Practice & Experience, v.19 n.2, p.171-183, February 1989 [doi>10.1002/spe.4380190206]
• 2: Josh Barnes and Piet Hut. A hierarchical O(N log N) force calculation algorithm. Nature, 1986.
• 3: Jon Louis Bentley. A parallel algorithm for constructing minimum spanning trees. In Journal of Algorithms, 1980.
• 4: Gianfranco Bilardi , Alexandru Nicolau, Adaptive bitonic sorting: an optimal parallel algorithm for shared-memory machines, SIAM Journal on Computing, v.18 n.2, p.216-228, April 1989 [doi>10.1137/0218014]
• 5: Brendon Cahoon , Kathryn S. McKinley, Data Flow Analysis for Software Prefetching Linked Data Structures in Java, Proceedings of the 2001 International Conference on Parallel Architectures and Compilation Techniques, p.280-291, September 08-12, 2001
• 6: Martin C. Carlisle , Anne Rogers, Software caching and computation migration in Olden, Proceedings of the fifth ACM SIGPLAN symposium on Principles and practice of parallel programming, p.29-38, July 19-21, 1995, Santa Barbara, California, United States
• 7: Craig David Chambers, The design and implementation of the self compiler, an optimizing compiler for object-oriented programming languages, Stanford University, Stanford, CA, 1992
• 8: A. Krishnamurthy , D. E. Culler , A. Dusseau , S. C. Goldstein , S. Lumetta , T. von Eicken , K. Yelick, Parallel programming in Split-C, Proceedings of the 1993 ACM/IEEE conference on Supercomputing, p.262-273, December 1993, Portland, Oregon, United States [doi>10.1145/169627.169724]
• 9: L. Guibas and J. Stolfl. General subdivisions and Voronoi diagrams. ACM Transactions on Graphics, 1985.
• 10: Urs Hölzle. A fast write barrier for generational garbage collectors. In OOPSLA '93 Garage Collection Workshop, 1993.
• 11: Antony L. Hosking and Richard L. Hudson. Remembered sets can also play cards. In OOPSLA '93 Garbage Collection Workshop, 1993.
• 12: Antony L. Hosking , J. Eliot B. Moss , Darko Stefanovic, A comparative performance evaluation of write barrier implementation, conference proceedings on Object-oriented programming systems, languages, and applications, p.92-109, October 18-22, 1992, Vancouver, British Columbia, Canada
• 13: Richard Jones , Rafael Lins, Garbage collection: algorithms for automatic dynamic memory management, John Wiley & Sons, Inc., New York, NY, 1996
• 14: Richard M. Karp. Probabilistic analysis of partitioning algorithms for the traveling-salesman problem in the plane. Mathematics of Operations Research, 1977.
• 15: G. Lomow, J. Cleary, B. Unger, and D. West. A performance study of Time Warp. In Proceedings of the SCS Multiconference on Distributed Simulation, pages 50-55, San Diego, California, 1988.
• 16: S. Lumetta , L. Murphy , X. Li , D. Culler , I. Khalil, Decentralized optimal power pricing: the development of a parallel program, Proceedings of the 1993 ACM/IEEE conference on Supercomputing, p.240-249, December 1993, Portland, Oregon, United States [doi>10.1145/169627.169718]
• 17: Hanan Samet. Computing perimeters of regions in images represented by quadtrees. IEEE Transactions on Pattern Analysis and Machine Intelligence, 1981.
• 18: David Ungar, Generation Scavenging: A non-disruptive high performance storage reclamation algorithm, Proceedings of the first ACM SIGSOFT/SIGPLAN software engineering symposium on Practical software development environments, p.157-167, April 1984
• 19: Benjamin Zorn. Barrier methods for garbage collection. Technical Report CU-CS-494-90, 1990.

INDEX TERMS

Keywords:
generational garbage collection, pointer analysis, program analysis, write barriers