Complete Register Allocation Problems
Ravi Sethi · SIAM Journal on Computing · 1975
The search for efficient register allocation algorithms dates back to the time of the first FORTRAN compiler for the IBM 704. The model we use in this paper is a single processor with an arbitrarily large number of general registers. The objective is to use as few registers as possible, under the,constraint that no stores into memory are permitted. The programs under consideration are sequences of assignment instructions. We show that, given a program and an integer k, determining if the program can be computed using k registers is polynomial complete. It should be noted that k can be any integer.
Cited by 202 works. doi:10.1137/0204020
Authors
References
- Reducibility among Combinatorial Problems
- Formal Languages and their Relation to Automata
- On compiling algorithms for arithmetic expressions
- The Generation of Optimal Code for Arithmetic Expressions
- An axiomatic approach to code optimization for expressions
- Optimization of Straight Line Programs
- Adapting optimal code generation for arithmetic expressions to the instruction sets available on present-day computers