Complete Register Allocation Problems

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.