Whole-program linear-constant analysis with applications to link-time optimization

ABSTRACT

Current link-time optimization techniques can reduce the power consumption and code size of embedded software [2]. Due to a lack of information, the stack frames of procedures are left untouched by link-time program optimizers. In this paper we present a practical whole-program linear-constant analysis [9] that allows to analyze the stack layout of a procedure. The analysis deals with the peculiarities of link-time program representation, namely the lack of high-level information and the huge size of the control flow graph. Even on a complete linux kernel, our analysis is practical in terms of computation time. The collected information consists of restricted affine equations between two registers, but it enables optimizations complementary to existing link-time optimization techniques. On a set of ARM benchmarks, the number of store operations decreases by up to 7% while the execution time, program size and power consumption are all further improved. This paper discusses both the practical issues of applying whole-program linear-constant propagation as well as its use in program optimization and understanding.

REFERENCES

• 1: G. Balakrishnan, R. Gruian, T. W. Reps, and T. Teitelbaum. Codesurfer/x86-a platform for analyzing x86 executables. In R. Bodík, editor, CC, volume 3443 of Lecture Notes in Computer Science, pages 250--254. Springer, 2005.
• 2: Bruno De Bus , Bjorn De Sutter , Ludo Van Put , Dominique Chanet , Koen De Bosschere, Link-time optimization of ARM binaries, ACM SIGPLAN Notices, v.39 n.7, July 2004
• 3: Saumya K. Debray , William Evans , Robert Muth , Bjorn De Sutter, Compiler techniques for code compaction, ACM Transactions on Programming Languages and Systems (TOPLAS), v.22 n.2, p.378-415, March 2000 [doi>10.1145/349214.349233]
• 4: Sumit Gulwani , George C. Necula, Discovering affine equalities using random interpretation, Proceedings of the 30th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.74-84, January 15-17, 2003, New Orleans, Louisiana, USA
• 5: M. Karr. Affine relationships among variables of a program. Acta Informatica, 6:133--151, 1976.
• 6: Markus Müller-Olm , Oliver Rüthing, On the Complexity of Constant Propagation, Proceedings of the 10th European Symposium on Programming Languages and Systems, p.190-205, April 02-06, 2001
• 7: M. Müller-Olm and H. Seidl. A note on karr's algorithm. In J. Díaz, J. Karhumäki, A. Lepistö, and D. Sannella, editors, ICALP, volume 3142 of Lecture Notes in Computer Science, pages 1016--1028. Springer, 2004.
• 8: Markus Müller-Olm , Helmut Seidl, Precise interprocedural analysis through linear algebra, Proceedings of the 31st ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.330-341, January 14-16, 2004, Venice, Italy
• 9: Mooly Sagiv , Thomas Reps , Susan Horwitz, Precise interprocedural dataflow analysis with applications to constant propagation, Theoretical Computer Science, v.167 n.1-2, p.131-170, Oct. 30, 1996
• 10: B. Schwarz, S. Debray, G. Andrews, and M. Legendre. PLTO: a link-time optimizer for the Intel IA-32 architecture. In Proceedings of the Workshop on Binary Translation (WBT), 9 2001.