Is local register allocation NP-complete?

pkolte@cs.clemson.edu
Tue, 9 Jun 1992 18:25:30 GMT

          From comp.compilers

Related articles
Is local register allocation NP-complete? pkolte@cs.clemson.edu (1992-06-09)
| List of all articles for this month |

Newsgroups: comp.compilers
From: pkolte@cs.clemson.edu
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 (pkolte@cs.clemson.edu)
--


Post a followup to this message

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