A unified approach to global program optimization
Gary A. Kildall · ACM SIGACT-SIGPLAN Symposium on Principles of Programming Languages (POPL) · 1973
A technique is presented for global analysis of program structure in order to perform compile time optimization of object code generated for expressions. The global expression optimization presented includes constant propagation, common subexpression elimination, elimination of redundant register load operations, and live expression analysis. A general purpose program flow analysis algorithm is developed which depends upon the existence of an "optimizing function." The algorithm is defined formally using a directed graph model of program flow structure, and is shown to be correct. Several optimizing functions are defined which, when used in conjunction with the flow analysis algorithm, provide the various forms of code optimization. The flow analysis algorithm is sufficiently general that additional functions can easily be defined for other forms of global code optimization.
Cited by 916 works. doi:10.1145/512927.512945
Authors
References
- Index Register Allocation
- Control flow analysis
- Compiling techniques for Boolean expressions and conditional statements in ALGOL 60
- Object code optimization
- ALGOL 60 implementation
- Compiler construction for digital computers
- On compiling algorithms for arithmetic expressions
- Programming languages and their compilers: Preliminary notes
- The Generation of Optimal Code for Arithmetic Expressions
- Global common subexpression elimination