Optimal code generation for expression trees
Alfred V. Aho, S. C. Johnson · 1975
We discuss the problem of generating code for a wide class of machines, restricting ourselves to the computation of expression trees. After defining a broad class of machines and discussing the properties of optimal programs on these machines, we derive a necessary and sufficient condition which can be used to prove the optimality of any code generation algorithm for expression trees on this class. We then present a dynamic programming algorithm which produces optimal code for any machine in the class; this algorithm runs in time which is linearly proportional to the number of vertices in an expression tree.
Cited by 24 works. doi:10.1145/800116.803770 Open-access PDF
Authors
References
- The Design and Analysis of Computer Algorithms
- Reducibility among Combinatorial Problems
- The complexity of theorem-proving procedures
- On compiling algorithms for arithmetic expressions
- The Generation of Optimal Code for Arithmetic Expressions
- Complete register allocation problems
- On arithmetic expressions and trees
- An axiomatic approach to code optimization for expressions
- Optimization of Straight Line Programs
- Characterizations of flowchartable recursions