Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!yale!mintaka!spdcc!iecc!compilers-sender
From: chris@mimsy.umd.edu (Chris Torek)
Newsgroups: comp.compilers
Subject: Vax span-dependent jumps
Keywords: design, code, optimize
Message-ID: <28765@mimsy.umd.edu>
Date: 23 Dec 90 08:59:22 GMT
References: <9012111913.AA07310@cs-sun-fsa.cpsc.ucalgary.ca> <14692@goofy.megatest.UUCP>
Sender: compilers-sender@iecc.cambridge.ma.us
Reply-To: chris@mimsy.umd.edu (Chris Torek)
Organization: U of Maryland, Dept. of Computer Science, Coll. Pk., MD 20742
Lines: 81
Approved: compilers@iecc.cambridge.ma.us
Old-Subject: Re: keyword lookup (Re: Hash specifics)

In article <14692@goofy.megatest.UUCP> megatest!djones@decwrl.dec.com
(Dave Jones) writes:
>Okay, yet one more thing: If you have a lot of keywords, and you compile this
>on an old, brain-damaged BSD compiler, remember to use the -J flag, which
>means, "Do not generate pseudo-random jumps." :-(

Minor correction: this is not what -J means.

The VAX architecture is particularly maddening when it comes to branches.
It has four different kinds of branches:

	conditional byte branches: b<cond> <relative displacement>
		(the condition can be `unconditional')
	unconditional word branches: brw <relative displacement>
	unconditional longword branches (`jumps'): jmp <address>

and `special' branches (built into instructions like acbl and sobgeq)
which are sometimes byte displacements and sometimes word displacements.
The BSD VAX assembler offers `pseudo branch' instructions for b<cond>
and for unconditional byte-or-word branches: j<cond> or `jbr'.  These
expand as necessary: a

		tstl	r9
		jlssu	label

will assemble to a `branch if less than (unsigned)' if `label' is within
a byte displacement; otherwise it will assemble to a `branch if greater
than or equal to unsigned; branch word to label', where the (new, reversed)
conditional branch merely branches AROUND the unconditional branch.  As
a special optimization, the assembler will sometimes% use something called
`branch tunneling', in which:

		tstl	r9
		jlssu	label
		...
	sneaky:	jbr	label
		...
	label:

assembles to the sequence `test, conditional branch to sneaky, ...,
unconditional branch to label'.  Here `sneaky' is within range of the
desired conditional branch but `label' is not.
-----
% I have never actually seen any tunneled branches, but there *is* code
  in the `as' source to do it.
-----

Now, all this is rather complicated, and quite difficult to do well.  If
you are not careful, a branch optimizer of this sort runs in O(n^3) time.
Sun Microsystems used to have such a branch optimizer in their assembler.
This was fixed after the assembler was observed to take more than 30 hours
of CPU time on a Sun-3 when assembling Pascal compiler output.  (To wit,
TeX.  The compiler itself had only run for perhaps 20 minutes.)

The BSD branch optimizer runs in O(n log n) time, as I recall.  It does
not do a perfect job.  In particular, it can only expand j<cond> branches
to b<not(cond)>+brw, and not to b<not(cond)>+jmp.  It cannot handle the
special instruction branches at all.  The `-J' flag tells the assembler
to turn *all* j<cond> branches into b<not(cond)>+jmp sequences, and to
turn all jbr branches into jmp branches.  This is rarely optimal.

The assembler should be improved to handle distant branches, someday; but
the need for this is rare, and the cost of doing it always seems unwarranted.
(Some people are hoping the VAX architecture will die before they have to
fix `as -J' :-) .)
-- 
In-Real-Life: Chris Torek, Univ of MD Comp Sci Dept (+1 301 454 7163)
Domain:	chris@cs.umd.edu	Path:	uunet!mimsy!chris
[Hmmn.  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.  Worked pretty well, better than IBM's assember
which only complained if you guessed wrong.  There were only two formats
rather than 3, but I don't see that 3 should have been that much harder.  I
didn't try to make the tunnel code work, time was limited and the win fairly
low.  -John]
-- 
Send compilers articles to compilers@iecc.cambridge.ma.us or
{ima | spdcc | world}!iecc!compilers.  Meta-mail to compilers-request.