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.
- 1.A. V. Aho, J. E. Hopcroft, and J. D. Ullman. Data Structures and Algorithms. Addison-Wesley, 1983.]] Google ScholarDigital Library
- 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.]]Google Scholar
- 3.P. Briggs and K. D. Cooper. Effective partial redundancy elimination, in Proc. A CM SIGPLAN Conf. Prog. Lang. Design and impl. (PLDI'9,~), volume 29,6 of A CM SIGPLAN Not., pages 159- 170, 1994.]] Google ScholarDigital Library
- 4.K. D. Cooper and N. McIntosh. Enhanced code compression for embedded RISC processors. In Proc. A CM SIGPLAN Conf. on Prog. Lang. Design and Impl. (PLDI'99), volume 34,5 of ACM SIGPLAN Not., pages 139- 149, 1999.]] Google ScholarDigital Library
- 5.K. D. Cooper, P. J. Schielke~ and D. Subramanian. Optimizing for reduced code space using genetic algorithms. In Proc. A CM SIGPLAN Workshop on Languages, Compilers, and Tools for Embedded Systems (LCTES'99), volume 35,7 of ACM SIGPLAN Not., pages 1 - 9, 1999.]] Google ScholarDigital Library
- 6.D. M. Dhamdhere. A fast algorithm for code movement optimization. ACM SIGPLAN Not., 23(10):172- 180, 1988.]] Google ScholarDigital Library
- 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.]]Google ScholarCross Ref
- 8.D. M. Dhamdhere. Practical adaptation of the global optimization algorithm of Morel and l~envoise. A CM Trans. Prog. Lang. Syst., 13(2):291- 294, 1991. Tech. Corr.]] Google ScholarDigital Library
- 9.D. R. Ditzel, H. R. McLellan, and A. D. Berenbaum. Design tradeoffs to support the C programming language in the CRISP Microprocessor. In Proc. 2nd Int. Conf. on Architectural Support for Programming Languages and Operating Systems (ASPLOS II), volume 22,10 of ACM SIGPLAN Not., pages 158- 163, 1987.]] Google ScholarCross Ref
- 10.K.-H. Drechsler and M. P. Stadel. A solution to a problem with Morel and Renvoise's "Global optimization by suppression of partial redundancies". A CM Trans. Prog. Lang. Syst., 10(4):635 - 640, 1988. Tech. Corr.]] Google ScholarDigital Library
- 11.K.-H. Drechsler and M. P. Stadel. A variation of Knoop, l~iithing and Steffen's LAZY CODE MOTION. ACM SIG- PLAN Not., 28(5):29- 38, 1993.]] Google ScholarDigital Library
- 12.J. Ernst, W. Evans, C. W. Fraser, S. Lucco, and T. A. Proebsting. Code compression. In Proc. A CM SIGPLAN Conf. on Prog. Lang. Design and Impl. (PLDI'97), volume 32,5 of A CM SIGPLAN Not., pages 358- 365, 1997.]] Google ScholarDigital Library
- 13.C. W. Fraser, E. W. Myers, and A. L. Wendt. Analysing and compressing assembly code. A CM SIGPLAN Not., 19(6):117 - 121, 1984.]] Google ScholarDigital Library
- 14.R. Gupta and P~. Bodik. Register pressure sensitive redundancy elimination. In Proc. 8th int. Conf. on Compiler Construction (CC'99), LNCS 1575, pages 107- 121. Springer-V., 1999.]] Google ScholarDigital Library
- 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.]]Google ScholarCross Ref
- 16.Wen-mei W. Hwu and Pohua P. Chang. Efficient instruction sequencing with inline target insertion. IEEE Transactions on Computers, 41(12):1537- 1551, 1992.]] Google ScholarDigital Library
- 17.D. Kirovski, J. Kin, and W. H. Mangione-Smith. Procedure based program compression. In Proc. 30th Annual Int. Syrup. on Microarchitecture (MICRO-30), pages 204- 213, 1997.]] Google ScholarDigital Library
- 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.]]Google Scholar
- 19.J. Knoop, O, Riithing, and B. Steffen. Lazy code motion. In Proc. A CM SIGPLAN Conf. on Prog. Lang. Design and Impl. (PLDI'92), volume 27,7 of ACM SIGPLAN Not., pages 224- 234~ 1992.]] Google ScholarDigital Library
- 20.J. Knoop, O. Riithing, and B. Steffen. Optimal code motion: Theory and practice. A CM Trans. Prog. Lang. Syst., 16(4):1117-1155, 1994.]] Google ScholarDigital Library
- 21.J. Knoop, O. Riithing, and B. Steffen. Partial dead code elimination. In Proc. A CM SIGPLAN Conf. on Prog. Lang. Design and ImpI. (PLDI'94), volume 29,6 of ACM SIG- PLAN Not., pages 147- 158, 1994.]] Google ScholarDigital Library
- 22.J. Knoop, O. Riithing, and B. Steffen. The power of assignment motion, in Proc. A CM SIGPLAN Conf. on Prog. Lang. Design and Impl. (PLDI'95), volume 30,6 of ACM SIGPLAN Not., pages 233- 245, 1995.]] Google ScholarDigital Library
- 23.J. Knoop, O. Riithing, and B. Steffen. Code motion and code placement: Just synomyms? In Proc. 7th European Syrup. on Programming (ESOP'98), LNCS 1381, pages 154 - 169. Springer-V., 1998.]] Google ScholarDigital Library
- 24.M. Kozuch and A. Wolfe. Compression of embedded system programs. In Proc. IEEE Int. Conf. on Computer Design: VLSI in Computers and Processors (CD'9,~), pages 270- 277. IEEE Computer Society, Los Alamitos, CA, 1994.]] Google ScholarDigital Library
- 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.]]Google ScholarDigital Library
- 26.C. Lefurgy, P. Bird, I.-C. Chen, and T. Mudge. Improving code density using compression techniques. In Proc. 30th Annual Int. Syrup. on Microarchitecture (MICRO-30), pages 194- 203, 1997.]] Google ScholarDigital Library
- 27.S. Liao, S. Devadas, and K. Keutzer. Code density optimizations for embedded DSP processors using data compression techniques. In Proc. 15th Conf. on Advanced Research in VLSI, 1995.]] Google ScholarDigital Library
- 28.S. Liao, S. Devadas, K. Keutzer, S. Tjiang, and A. Wang. Storage assignment to decrease code size. A CM TOPLAS, i8(3):235 - 253, 1996.]] Google ScholarDigital Library
- 29.L. Lov~sz and M. D. Plummer. Matching theory. Annals o} Discrete Mathematics~ 29, 1986.]]Google Scholar
- 30.B. Marks. Compilation to compact code. IBM J. Research and Development, 24(6):684- 691, 1980.]]Google ScholarDigital Library
- 31.H. Massalin. Superoptimizer- A look at the smallest program, In Proc. 2nd Int. Conf. on Architectural Support for Programming Languages and Operating Systems (ASPLOS H), volume 22,10 of A CM SIGPLAN Not., pages 122 - 126, 1987.]] Google ScholarDigital Library
- 32.E. Morel and C. Renvoise. Global optimization by suppression of partial redundancies. Comm. A CM, 22(2):96- 103, 1979.]] Google ScholarDigital Library
- 33.W. Pugh. Compressing Java class files. In Proc. A CM SIG- PLAN Conf. on Prog. Lang. Design and Impl. (PLDI'99), volume 34,5 of A CM SIGPLAN Not., pages 247- 258, 1999.]] Google ScholarDigital Library
- 34.A. Rao and S. Pande. Storage assignment optimizations to generate compact and efficient code on embedded DSPs. In Proc. A CM SIGPLAN Conf. on Prog. Lang. Design and Impl. (PLDI'99), volume 34,5 of A GM SIGPLAN Not., pages 128- 138, 1999.]] Google ScholarDigital Library
- 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.]]Google Scholar
- 36.O. Riithing. Interacting Code Motion Transformations: Their Impact and Their Complexity. PhD thesis, Univ. of Kiel, Germany, 1997. LNCS 1539, Springer-V., 1998.]]Google Scholar
- 37.O. Riithing. Bidirectional data flow analysis in code motion: Myth and reality. In Proc. 5th Int. Static Analysis Symposium (SAS'98), LNCS 1503, pages 1- 16. Springer-V., 1998.]] Google ScholarDigital Library
- 38.O. Riithing. Optimal code motion in the presence of large expressions. In Proc. 6th Int. Conf. on Computer Languages (ICCL'98), pages 216- 225. IEEE Computer Society, Los Alamitos, CA, 1998.]] Google ScholarDigital Library
- 39.A. Sorkin. Some comments on a solution to a problem with Morel and Renvoise's "Global optimization by suppression of partial redundancies". A CM Trans. Prog. Lang. Syst., 11(4):666 - 668, 1989. Tech. Corr.]] Google ScholarDigital Library
- 40.A. Srivastava and A. M. Despain. Prophetic branches: A branch architecture for code compaction and efficient execution. In 26th Annual Int. Syrup. on Microarchitecture (MICRO-26), pages 94- 99, 1993.]] Google ScholarDigital Library
- 41.A. Wolfe and A. Chanin. Executing compressed programs on an embedded RISC architecture. In 25th Annual Int. Syrup. on Microarchitecture (MICRO-25), pages 81 - 91, 1992.]] Google ScholarDigital Library
Index Terms
- Sparse code motion
Recommendations
Optimal code motion: theory and practice
An implementation-oriented algorithm for lazy code motion is presented that minimizes the number of computations in programs while suppressing any unnecessary code motion in order to avoid superfluous register pressure. In particular, this variant of ...
An SSA-based algorithm for optimal speculative code motion under an execution profile
PLDI '11To derive maximum optimization benefits from partial redundancy elimination (PRE),it is necessary to go beyond its safety constraint. Algorithms for optimal speculative code motion have been developed based on the application of minimum cut to flow ...
An SSA-based algorithm for optimal speculative code motion under an execution profile
PLDI '11: Proceedings of the 32nd ACM SIGPLAN Conference on Programming Language Design and ImplementationTo derive maximum optimization benefits from partial redundancy elimination (PRE),it is necessary to go beyond its safety constraint. Algorithms for optimal speculative code motion have been developed based on the application of minimum cut to flow ...
Comments