Sparse code motion

ABSTRACT

In this article, we add a third dimension to partial redundancy elimination by considering code size as a further optimization goal in addition to the more classical consideration of computation costs and register pressure. This results in a family of sparse code motion algorithms coming as modular extensions of the algorithms for busy and lazy code motion. Each of them optimally captures a predefined choice of priority between these three optimization goals, e.g. code size can be minimized while (1) guaranteeing at least the performance of the argument program, or (2) even computational optimality. Each of them can further be refined to simultaneously reduce the lifetimes of temporaries to a minimum. These algorithms are well-suited for size-critical application areas like smart cards and embedded systems, as they provide a handle to control the code replication problem of classical code motion techniques. In fact, we believe that our systematic, priority-based treatment of trade-offs between optimization goals may substantially decrease development costs of size-critical applications: users may “play” with the priorities until the algorithm automatically delivers a satisfactory solution.

REFERENCES

• 1: Alfred V. Aho , John E. Hopcroft , Jeffrey Ullman , J. D. Ullman , J. E. Hopcroft, Data Structures and Algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1983
• 2: G. Araujo, S. Devadas, K. Keutzer, S. Liao, S. Malik, A. Sudaxsanam, S. Tjiang, and A. Wang. Challenges in code generation for embedded processors. In P. Marwedel and G. Goossens, editors, Code Generation for Embedded Processors. Kluwer Academic Publishers, 1995.
• 3: Preston Briggs , Keith D. Cooper, Effective partial redundancy elimination, Proceedings of the ACM SIGPLAN 1994 conference on Programming language design and implementation, p.159-170, June 20-24, 1994, Orlando, Florida, United States
• 4: Keith D. Cooper , Nathaniel McIntosh, Enhanced code compression for embedded RISC processors, ACM SIGPLAN Notices, v.34 n.5, p.139-149, May 1999
• 5: Keith D. Cooper , Philip J. Schielke , Devika Subramanian, Optimizing for reduced code space using genetic algorithms, ACM SIGPLAN Notices, v.34 n.7, p.1-9, July 1999
• 6: D. M. Dhamdhere, A fast algorithm for code movement optimisation, ACM SIGPLAN Notices, v.23 n.10, p.172-180, Oct. 1988 [doi>10.1145/51607.51621]
• 7: D. M. Dhamdhere. A new algorithm for composite hoisting and strength reduction optimisation (+ Corrigendum). Int. J. Comp. Math., 27:1 - 14 (-b 31- 32), 1989.
• 8: D. M. Dhamdhere, Practical adaption of the global optimization algorithm of Morel and Renvoise, ACM Transactions on Programming Languages and Systems (TOPLAS), v.13 n.2, p.291-294, April 1991 [doi>10.1145/103135.214520]
• 9: David R. Ditzel , Hubert R. McLellan , Alan D. Berenbaum, Design tradeoffs to support the C programming language in the CRISP microprocessor, Proceedings of the second international conference on Architectual support for programming languages and operating systems, p.158-163, October 1987, Palo Alto, California, United States
• 10: Karl-Heinz Drechsler , Manfred P. Stadel, A solution to a problem with Morel and Renvoise's “Global optimization by suppression of partial redundancies”, ACM Transactions on Programming Languages and Systems (TOPLAS), v.10 n.4, p.635-640, Oct. 1988 [doi>10.1145/48022.214509]
• 11: Karl-Heinz Drechsler , Manfred P. Stadel, A variation of Knoop, Rüthing, and Steffen's Lazy Code Motion, ACM SIGPLAN Notices, v.28 n.5, p.29-38, May 1993 [doi>10.1145/152819.152823]
• 12: Jens Ernst , William Evans , Christopher W. Fraser , Todd A. Proebsting , Steven Lucco, Code compression, ACM SIGPLAN Notices, v.32 n.5, p.358-365, May 1997
• 13: Christopher W. Fraser , Eugene W. Myers , Alan L. Wendt, Analyzing and compressing assembly code, ACM SIGPLAN Notices, v.19 n.6, p.117-121, June 1984
• 14: Rajiv Gupta , Rastislav Bodík, Register Pressure Sensitive Redundancy Elimination, Proceedings of the 8th International Conference on Compiler Construction, Held as Part of the European Joint Conferences on the Theory and Practice of Software, ETAPS'99, p.107-121, March 22-28, 1999
• 15: J. E. Hopcroft and R. M. Karp. An n~ algorithm for maximum matchings in bipartite graphs. SIAM Journal of Computing, 2(4):225 - 331, 1973.
• 16: W. W. Hwu , P. P. Chang, Efficient Instruction Sequencing with Inline Target Insertion, IEEE Transactions on Computers, v.41 n.12, p.1537-1551, December 1992 [doi>10.1109/12.214662]
• 17: Darko Kirovski , Johnson Kin , William H. Mangione-Smith, Procedure based program compression, Proceedings of the 30th annual ACM/IEEE international symposium on Microarchitecture, p.204-213, December 01-03, 1997, Research Triangle Park, North Carolina, United States
• 18: J. Knoop. Optimal Interprocedural Program Optimization: A new Framework and its Application. PhD thesis, Univ. of Kiel, Germany, 1993. LNCS Tutorial 1428, Springer-V., 1998.
• 19: Jens Knoop , Oliver Rüthing , Bernhard Steffen, Lazy code motion, ACM SIGPLAN Notices, v.27 n.7, p.224-234, July 1992
• 20: Jens Knoop , Oliver Rüthing , Bernhard Steffen, Optimal code motion: theory and practice, ACM Transactions on Programming Languages and Systems (TOPLAS), v.16 n.4, p.1117-1155, July 1994 [doi>10.1145/183432.183443]
• 21: Jens Knoop , Oliver Rüthing , Bernhard Steffen, Partial dead code elimination, Proceedings of the ACM SIGPLAN 1994 conference on Programming language design and implementation, p.147-158, June 20-24, 1994, Orlando, Florida, United States
• 22: Jens Knoop , Oliver Rüthing , Bernhard Steffen, The power of assignment motion, ACM SIGPLAN Notices, v.30 n.6, p.233-245, June 1995
• 23: Jens Knoop , Oliver Rüthing , Bernhard Steffen, Code Motion and Code Placement: Just Synonyms?, Proceedings of the 7th European Symposium on Programming: Programming Languages and Systems, p.154-169, March 28-April 04, 1998
• 24: Michael Kozuch , Andrew Wolfe, Compression of Embedded System Programs, Proceedings of the1994 IEEE International Conference on Computer Design: VLSI in Computer & Processors, p.270-277, October 10-12, 1994
• 25: J. K. F. Lee and A. J. Smith. Branch prediction strategies and branch target buffer design. IEEE Computer Magazine, pages 6- 22, Jan. 1984.
• 26: Charles Lefurgy , Peter Bird , I-Cheng Chen , Trevor Mudge, Improving code density using compression techniques, Proceedings of the 30th annual ACM/IEEE international symposium on Microarchitecture, p.194-203, December 01-03, 1997, Research Triangle Park, North Carolina, United States
• 27: S. Y. Liao , S. Devadas , K. Keutzer, Code density optimization for embedded DSP processors using data compression techniques, Proceedings of the 16th Conference on Advanced Research in VLSI (ARVLSI'95), p.272, March 27-29, 1995
• 28: Stan Liao , Srinivas Devadas , Kurt Keutzer , Steven Tjiang , Albert Wang, Storage assignment to decrease code size, ACM Transactions on Programming Languages and Systems (TOPLAS), v.18 n.3, p.235-253, May 1996 [doi>10.1145/229542.229543]
• 29: L. Lov~sz and M. D. Plummer. Matching theory. Annals o} Discrete Mathematics~ 29, 1986.
• 30: B. Marks. Compilation to compact code. IBM J. Research and Development, 24(6):684- 691, 1980.
• 31: Henry Massalin, Superoptimizer: a look at the smallest program, ACM SIGARCH Computer Architecture News, v.15 n.5, p.122-126, Oct. 1987
• 32: E. Morel , C. Renvoise, Global optimization by suppression of partial redundancies, Communications of the ACM, v.22 n.2, p.96-103, Feb. 1979 [doi>10.1145/359060.359069]
• 33: William Pugh, Compressing Java class files, ACM SIGPLAN Notices, v.34 n.5, p.247-258, May 1999
• 34: Amit Rao , Santosh Pande, Storage assignment optimizations to generate compact and efficient code on embedded DSPs, ACM SIGPLAN Notices, v.34 n.5, p.128-138, May 1999
• 35: O. Riithing. Code motion in the presence of critical edges without bidirectional data flow analysis. Science of Computer Programming. Special issue devoted to the 5th Int. Static Analysis Symposium (SAS'98). To appear. 31 pages.
• 36: O. Riithing. Interacting Code Motion Transformations: Their Impact and Their Complexity. PhD thesis, Univ. of Kiel, Germany, 1997. LNCS 1539, Springer-V., 1998.
• 37: Oliver Rüthing, Bidirectional Data Flow Analysis in Code Motion: Myth and Reality, Proceedings of the 5th International Symposium on Static Analysis, p.1-16, September 14-16, 1998
• 38: Oliver Rüthing, Optimal Code Motion in the Presence of Large Expressions, Proceedings of the 1998 International Conference on Computer Languages, p.216, May 14-16, 1998
• 39: Arthur Sorkin, Some comments on “A solution to a problem with Morel and Renvoise's 'Global optimization by suppression of partial redundancies'”, ACM Transactions on Programming Languages and Systems (TOPLAS), v.11 n.4, p.666-668, Oct. 1989 [doi>10.1145/69558.214513]
• 40: Apoorv Srivastava , Alvin M. Despain, Prophetic branches: a branch architecture for code compaction and efficient execution, Proceedings of the 26th annual international symposium on Microarchitecture, p.94-99, December 01-03, 1993, Austin, Texas, United States
• 41: Andrew Wolfe , Alex Chanin, Executing compressed programs on an embedded RISC architecture, Proceedings of the 25th annual international symposium on Microarchitecture, p.81-91, December 01-04, 1992, Portland, Oregon, United States

INDEX TERMS

Primary Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING

Additional Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES

  F. Theory of Computation
  F.3 LOGICS AND MEANINGS OF PROGRAMS

General Terms:
Algorithms, Design, Languages

Keywords:
busy code motion, code motion, code size, compuational optimality, embedded processors and systems, expression motion, lazy code motion, life-time optimality, partial redundancy elimination, space optimality