28 Jan 2007 01:41:31 -0500

Related articles |
---|

Jump size optimization info... Orlando.Llanes@gmail.com (Orlando Llanes) (2007-01-08) |

Re: Jump size optimization info... kenrose@nc-sys.com (Ken Rose) (2007-01-11) |

Re: Jump size optimization info... sdn@svpal.org (Steven Nichols) (2007-01-12) |

Re: Jump size optimization info... sdn@svpal.org (Steven Nichols) (2007-01-12) |

Re: Jump size optimization info... anton@mips.complang.tuwien.ac.at (2007-01-12) |

Re: Jump size optimization info... gah@ugcs.caltech.edu (glen herrmannsfeldt) (2007-01-14) |

Re: Jump size optimization info... 148f3wg02@sneakemail.com (Karsten Nyblad) (2007-01-28) |

Re: Jump size optimization info... niktechc@niktech.com (Sandeep Dutta) (2007-01-31) |

Re: Jump size optimization info... Orlando.Llanes@gmail.com (Orlando Llanes) (2007-02-09) |

From: | Karsten Nyblad <148f3wg02@sneakemail.com> |

Newsgroups: | comp.compilers |

Date: | 28 Jan 2007 01:41:31 -0500 |

Organization: | Compilers Central |

References: | 07-01-023 07-01-040 |

Keywords: | assembler, optimize, theory |

Posted-Date: | 28 Jan 2007 01:41:31 EST |

*> [To get the genreral NP complete subtraction problem I'd think you*

*> could add branch chaining, e.g., if you have A->C and B->C, you can*

*> change that to A->B and B->C. -John]*

A way of making the problem NP-complete is to allow reordering of code.

In some cases you can save branches or save long branches by

reordering the code, e.g., by swapping the order of two basic blocks.

Unfortunately the CACM paper John referenced to proves that that is

NP-complete. The paper goes on to prove that the algorithm described

by Steven Nichols is optimal as long as you are forbidden to reorder

the code.

Karsten Nyblad

148f3wg02 at sneakemail dot com

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.