Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!tut.cis.ohio-state.edu!att!att!ima!spdcc!iecc!compilers-sender
From: lehotsky@aries.osf.org (Alan Lehotsky)
Newsgroups: comp.compilers
Subject: Re: Vax span-dependent jumps
Keywords: optimize, code, assembler
Message-ID: <17633@paperboy.OSF.ORG>
Date: 2 Jan 91 15:30:51 GMT
References: <9012111913.AA07310@cs-sun-fsa.cpsc.ucalgary.ca> <14692@goofy.megatest.UUCP> <28765@mimsy.umd.edu> <1990Dec30.005507.7842@zoo.toronto.edu>
Sender: compilers-sender@iecc.cambridge.ma.us
Reply-To: lehotsky@aries.osf.org (Alan Lehotsky)
Organization: Open Software Foundation
Lines: 65
Approved: compilers@iecc.cambridge.ma.us

Henry Spenser writes...

>Our moderator writes:
>>[... I wrote the original AIX assembler for the RT PC, another machine with
>>span-dependent jumps, by mutating the System III Vax assembler.  The code to
>>do span-dependent jumps was pretty straightforward, in pass 1 it assumed
>>they'd all be the long form and made a table of all of them, then between
>>passes 1 and 2 iterated over that table looking for branches that could be
>>converted to the short form...
>
>General comment:  this is theoretically the wrong approach, since there are
>sequences where the decisions interact so that branch X can be short only
>if branch Y is also short, and a one-at-a-time algorithm that starts with
>all of them long won't shorten them.

	Actually, the algorithm that Bliss uses is exactly the
	opposite.  The assumption is that ALL span-dependent
	instructions [SDI's] will be short.  For each SDI, two span
	values are calculated:

		- one assuming that all intervening SDI's are resolved
		  to their smallest size.  [Call this the MIN]

		- the other assuming that all SDI's are resolved long.
		  [Call this the MAX]

	Then you just iterate over the list of SDIs, and consider the
	three cases:

		1. The MIN and MAX are both small enough to reach with
		   the short form instruction.  [Resolve this SDI as
		   short and adjust all intervening SDI MAXs down]

		2. The MIN and the MAX are both larger than the short
		   form. [ Resolve this SDI as long and adjust all
		   intervening SDI MINs up]

		3. The MIN is small enough, but the MAX is larger than
		   the short form would allow.  [Wait for more
		   information]

	If at the end of an iteration, you have not found any
	candidates for case 1 or 2, then you are in a mutual
	dependency situation in which if all intervening SDIs were
	resolved short, then each SDI could be resolved short.  So,
	just resolve the rest of the SDIs as short.

	In the worst case, this algorithm could converge very slowly.
	In practice (measured on Bliss-32 and Bliss-16) it terminated
	after 3 or fewer iterations.

	(Of course, the Bliss-32 algorithm was actually more complex,
	as it combined 3 different possible lengths AND the ability to
	branch chain as well.  Back when B32 was written, memory was
	still more important than speed [remember, the 11/780 was
	supposed to be able to run with ONLY 256KB!!!!], so you could
	choose to optimize for space at the expense of the speed of
	branching to a branch.)

There are several papers on SDI and branch-chaining in the first 2
volumes of TOPLAS.
[See the next message for a short bibliography. -John]
-- 
Send compilers articles to compilers@iecc.cambridge.ma.us or
{ima | spdcc | world}!iecc!compilers.  Meta-mail to compilers-request.