Tue, 9 Jun 1992 18:25:30 GMT

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)

--

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.