Optimal Code Generation for Expression Trees
Alfred V. Aho, S. C. Johnson · Journal of the ACM · 1976
This paper discusses algorithms which transform expression trees into code for register machines. A necessary and sufficient condition for optimality of such an algorithm is derived, which applies to a broad class of machines. A dynamic programming algorithm is then presented which produces optimal code for any machine in this class; this algorithm runs in time linearly proportional to the size of the input.
Cited by 242 works. doi:10.1145/321958.321970 Open-access PDF
Authors
References
- The Art of Computer Programming
- The Design and Analysis of Computer Algorithms
- Reducibility among Combinatorial Problems
- The complexity of theorem-proving procedures
- A system for typesetting mathematics
- On compiling algorithms for arithmetic expressions
- The Generation of Optimal Code for Arithmetic Expressions
- On arithmetic expressions and trees
- Complete Register Allocation Problems
- An axiomatic approach to code optimization for expressions