Code Generation for a One-Register Machine
Authors:
Open Access
- 1 July 1976
- journal article
- Published by Association for Computing Machinery (ACM) in Journal of the ACM
- Vol. 23 (3) , 502-510
Abstract
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.Keywords
This publication has 10 references indexed in Scilit:
- The Generation of Optimal Code for Stack MachinesJournal of the ACM, 1975
- Optimal code generation for expression trees1975
- Computationally Related ProblemsSIAM Journal on Computing, 1974
- Adapting optimal code generation for arithmetic expressions to the instruction sets available on present-day computersCommunications of the ACM, 1973
- An axiomatic approach to code optimization for expressionsJournal of the ACM, 1972
- An algorithm for computingSU(n) invariantsBIT Numerical Mathematics, 1971
- The Generation of Optimal Code for Arithmetic ExpressionsJournal of the ACM, 1970
- On arithmetic expressions and treesCommunications of the ACM, 1969
- On compiling algorithms for arithmetic expressionsCommunications of the ACM, 1967
- A note on some compiling algorithmsCommunications of the ACM, 1964