|Is local register allocation NP-complete? firstname.lastname@example.org (1992-06-09)|
|Keywords:||optimize, theory, question|
|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).
-P Kolte (email@example.com)
Return to the
Search the comp.compilers archives again.