Code Generation for a One-Register Machine
John L. Bruno, Ravi Sethi · Journal of the ACM · 1976
The majority of computers that have been built have performed all computations in devices called accumulators, or registers. In this paper, it is shown that the problem of generating minimal-length code for such machines is hard in a precise sense; specifically it is shown that the problem is NP-complete. The result is true even when the programs being translated are arithmetic expressions. Admittedly, the expressions in question can become complicated.
Cited by 96 works. doi:10.1145/321958.321971
Authors
References
- The Design and Analysis of Computer Algorithms
- The complexity of theorem-proving procedures
- On compiling algorithms for arithmetic expressions
- The Generation of Optimal Code for Arithmetic Expressions
- Computationally Related Problems
- A note on some compiling algorithms
- On arithmetic expressions and trees
- Complete Register Allocation Problems
- An axiomatic approach to code optimization for expressions
- Optimal code generation for expression trees