Is local register allocation NP-complete?
Tue, 9 Jun 1992 18:25:30 GMT

          From comp.compilers

Related articles
Is local register allocation NP-complete? (1992-06-09)
| List of all articles for this month |

Newsgroups: comp.compilers
Keywords: optimize, theory, question
Organization: Compilers Central
Date: Tue, 9 Jun 1992 18:25:30 GMT

Do you know of an NP-completeness proof for the following local register
allocation problem ?

Given straight line code with n occurences of pseudo-registers, find a
mapping from the pseudo-registers to k real registers (or to memory) that
minimizes the number of occurences involving memory. Inserting Load/Store
instructions in the code is OK, but reordering the code is not allowed.

I believe this problem to be NP-complete, but I have not seen a proof.
Please tell me if you know of a proof (or a polynomial algorithm).

Thank you.
-P Kolte (

Post a followup to this message

Return to the comp.compilers page.
Search the comp.compilers archives again.