Related articles |
---|
Is local register allocation NP-complete? pkolte@cs.clemson.edu (1992-06-09) |
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)
--
Return to the
comp.compilers page.
Search the
comp.compilers archives again.