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.
Original language | English (US) |
---|---|
Pages (from-to) | 502-510 |
Number of pages | 9 |
Journal | Journal of the ACM (JACM) |
Volume | 23 |
Issue number | 3 |
DOIs | |
State | Published - Jul 1 1976 |
Keywords
- NP-complete
- arithmetic expressions
- basic blocks
- code optimization
- register allocation
- straight line programs
ASJC Scopus subject areas
- Software
- Control and Systems Engineering
- Information Systems
- Hardware and Architecture
- Artificial Intelligence