Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Posting-Version: version B 2.10 5/3/83; site utzoo.UUCP
Path: utzoo!henry
From: henry@utzoo.UUCP (Henry Spencer)
Newsgroups: net.lang
Subject: Re: Re: Optimization technique wanted...
Message-ID: <4696@utzoo.UUCP>
Date: Wed, 28-Nov-84 12:46:32 EST
Article-I.D.: utzoo.4696
Posted: Wed Nov 28 12:46:32 1984
Date-Received: Wed, 28-Nov-84 12:46:32 EST
References: <438@ima.UUCP>, <258@scc.UUCP>
Organization: U of Toronto Zoology
Lines: 21

> Well, it depends on the architecture. On the 8086 and family, where jumps
> are relative  8 or 16 bit branch to the Program Counter register, we
> only have to keep the previous 256 bytes worth of instructions in a ring
> buffer.

You could do this on most any machine with span-dependent instructions.
But note that this algorithm leaves some jumps long unnecessarily, and
in fact isn't as good as the CACM algorithm, because of problems with what
one might call "feedback loops" when one jump is jumping over another.
I believe the CACM paper demonstrated formally that no algorithm which
initially assumes jumps are long, and then tries to shorten them, can
give optimal results.  You have to work the other way, lengthening jumps
only as necessary.

The "ring buffer" (actually it's a FIFO) for output code does get *most*
of the shortenable jumps, though, and it's nice and simple.
-- 
	"Make mine machine-readable!!"

				Henry Spencer @ U of Toronto Zoology
				{allegra,ihnp4,linus,decvax}!utzoo!henry