Thu, 3 Jan 1991 11:31:57 PST

Related articles |
---|

Span-Dependent Instruction Bibliography johnl@iecc.cambridge.ma.us (John R. Levine) (1991-01-02) |

Re: Span-Dependent Instruction Bibliography preston@libya.rice.edu (1991-01-03) |

Re: Span-Dependent Instruction Bibliography norman@parc.xerox.com (Norman Adams) (1991-01-03) |

Re: Span-Dependent Instruction Bibliography markz@ssc.UUCP (1991-01-04) |

Newsgroups: | comp.compilers |

From: | Norman Adams <norman@parc.xerox.com> |

Keywords: | assembler, optimize, code |

Organization: | Compilers Central |

References: | <9101022304.AA22609@iecc.cambridge.ma.us> |

Date: | Thu, 3 Jan 1991 11:31:57 PST |

John Levine, comp.compilers moderator, writes:

Thomas G. Szymanski, "Assembling Code for Machines with Span-Dependent

Instructions", CACM 21:4, pp. 300-308, April 1978.

Describes the branch shrinking approach used in Unix assemblers,

an optimal two-pass algorithm which is more effective and in most

cases faster than the shrinking approach, and a proof that

minimizing program length is NP complete.

Span dependent branches are a restricted form of span-dependent

assembly expressions. Szymanski proves that minimizing arbitrary

span-dependent assembly expressions is NP-complete.

When faced with the task of writing a span-dependent branch minimizer

for the T assembler, I consulted a nearby theory powerhouse, Mike

Fischer. He said that nothing better than relaxation (Szymanski's

algorithm) was obvious, but "surely there is a better way." A few

years later, I got a paper from him in the mail. From that paper:

It is easy to see that a minimal size program can be obtained by

starting with all jumps short and traversing the program

repeatedly, converting short jumps to long on each pass as

necessary. A straightforward implementation of this strategy

however is quite ineffient since up to O(n) passes may be required

for a program containing n jumps [ each pass being O(n) ].

...

Using a monotonic priority set, we obtain an algorithm for optimal

assembly of jumps that runs in time O(n log n), independent of S

[ S is the maximum short jump distance ].

...

I assume the paper got published somewhere, but all I have is the

extended abstract:

Michael J. Fischer (Yale Univ), Micheal S. Paterson (Univ. of Warwick)

"Dynamic Monotone Priorities on Planar Sets (extended abstract)"

April 30, 1985

--

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.