Code motion of control structures in high-level languages

ABSTRACT

One trend among programmers is the increased use of abstractions. Through encapsulation techniques, abstractions extend the repertory of data structures and their concomitant operations that are processed directly by a compiler. For example, a compiler might not offer sets or set operations in its base language, but abstractions allow a programmer to define sets in terms of constructs already recognized by the compiler. In particular, abstractions can allow new constructs to be defined in terms of other abstractions. Although significant power is gained through the use of layered abstractions, object code quality suffers as increasingly less of a program's data structures and operations are exposed to the optimization phase of a compiler. Multiple references to abstractions are also inefficient, since the interaction between abstractions is often complex yet hidden from a compiler. Abstractions are most flexible when they are cast in general terms; a specific invocation is then tailored by the abstraction to obtain the appropriate code. A sequence of references to such abstractions can be inefficient due to functional redundancy that cannot be detected at compile-time. By integrating the references, the offending segments of code can be moved to a more advantageous position. Although procedure integration materializes abstracted constructs, the abstractions can still be ineligible for optimization using current techniques; in particular, abstractions often involve loops and conditional branches that can obscure code that would otherwise be eligible for code motion.

REFERENCES

• 1: Frances E. Allen, Control flow analysis, ACM SIGPLAN Notices, v.5 n.7, p.1-19, July 1970
• 2: John Randal Allen, Dependence analysis for subscripted variables and its application to program transformations, 1983
• 3: {Banerjee79} Banerjee, U., Speedup of Ordinary Programs. Published by University of Illinois at Urbana-Champaign, Oct. 1979, DCS Report No. UIUCDCS-R-79--989.
• 4: {Burke84} Burke, M., An interval approach toward interprocedural analysis. Published by IBM, July, 1984, RC 10640 #47724.
• 5: {Chaitin81} Chaitin, G. J., Auslander, M. A., Chandra, A. K., Cocke, J., Hopkins, M. E., Markstein, P. W., Register allocation via coloring. <i>Computer Languages,</i> 1981, vol. 6, page 47--57.
• 6: G. J. Chaitin, Register allocation & spilling via graph coloring, Proceedings of the 1982 SIGPLAN symposium on Compiler construction, p.98-105, June 23-25, 1982, Boston, Massachusetts, United States
• 7: Keith Daniel Cooper, Interprocedural data flow analysis in a programming environment, 1983
• 8: Jeanne Ferrante , Karl J. Ottenstein, A program form based on data dependency in predicate regions, Proceedings of the 10th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.217-236, January 24-26, 1983, Austin, Texas [doi>10.1145/567067.567089]
• 9: Jeanne Ferrante , Karl J. Ottenstein , Joe D. Warren, The program Dependence Graph and its Use in Optimization, Proceedings of the 6th Colloquium on International Symposium on Programming, p.125-132, April 17-19, 1984
• 10: Jeanne Ferrante , Mary Mace, On linearizing parallel code, Proceedings of the 12th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.179-190, January 14-16, 1985, New Orleans, Louisiana, United States [doi>10.1145/318593.318636]
• 11: Susan L. Graham , Mark Wegman, A Fast and Usually Linear Algorithm for Global Flow Analysis, Journal of the ACM (JACM), v.23 n.1, p.172-202, Jan. 1976 [doi>10.1145/321921.321939]
• 12: Edward S. Lowry , C. W. Medlock, Object code optimization, Communications of the ACM, v.12 n.1, p.13-22, Jan. 1969 [doi>10.1145/362835.362838]
• 13: 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]
• 14: Eugene M. Myers, A precise inter-procedural data flow algorithm, Proceedings of the 8th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.219-230, January 26-28, 1981, Williamsburg, Virginia [doi>10.1145/567532.567556]
• 15: John H. Reif , Harry R. Lewis, Symbolic evaluation and the global value graph, Proceedings of the 4th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.104-118, January 17-19, 1977, Los Angeles, California [doi>10.1145/512950.512961]
• 16: {Reif81} Reif, J. H., Tarjan, R. E., Symbolic program analysis in almost linear time. <i>SIAM Journal of Computing,</i> Feb. 1981, vol. 11, no. 1, page 81--93.
• 17: {Reif82} Reif, J. H., Lewis, H. R., Efficent symbolic analysis of programs. Published by Harvard University, Aiken Computation Laboratory, 1982, no. TR-37--82.
• 18: {Schwartz73} Schwartz, J. T., On Programming, An Interim Report on the SETL Project, Installment II: The SETL Language and Examples of Its Use. Published by Computer Science Department, Courant Institute of Mathematical Sciences. New York University, Oct. 1973.
• 19: {Schwartz79} Schwartz, J. T., Sharir, M., A design for optimizations of the bitvectoring class. Published by Courant Institute of Mathematical Sciences. Computer Science Department, New York University., Sept. 1979, no. 17.
• 20: {Tarjan74} Tarjan, R. E., Testing flow graph reducibility. <i>Journal of Computer and Systems Sciences</i>, Dec. 1974, vol. 9, page 355--365.
• 21: Mark N. Wegman , Frank Kenneth Zadeck, Constant propagation with conditional branches, Proceedings of the 12th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.291-299, January 14-16, 1985, New Orleans, Louisiana, United States [doi>10.1145/318593.318659]
• 22: {Wolfe82} Wolfe, M. J., Optimizing Supercompilers for Supercomputers. Published by Computer Science Department, University of Illinois at Urbana-Champaign, 1982.