Re: Vax span-dependent jumps

henry@zoo.toronto.edu (Henry Spencer)
Sun, 30 Dec 90 00:55:07 GMT

          From comp.compilers

Related articles
Vax span-dependent jumps chris@mimsy.umd.edu (1990-12-23)
Re: Vax span-dependent jumps henry@zoo.toronto.edu (1990-12-30)
Re: Vax span-dependent jumps lehotsky@aries.osf.org (1991-01-02)
Re: Vax span-dependent jumps ccplumb@spurge.uwaterloo.ca (1991-01-03)
| List of all articles for this month |

Newsgroups: comp.compilers
From: henry@zoo.toronto.edu (Henry Spencer)
Keywords: optimize, code, assembler
Organization: U of Toronto Zoology
References: <9012111913.AA07310@cs-sun-fsa.cpsc.ucalgary.ca> <14692@goofy.megatest.UUCP> <28765@mimsy.umd.edu>
Date: Sun, 30 Dec 90 00:55:07 GMT

In article <28765@mimsy.umd.edu> chris@mimsy.umd.edu (Chris Torek) writes:
>a special optimization, the assembler will sometimes% use something called
>`branch tunneling'...


Properly known as branch chaining; it's been around since at least the
Bliss-11 compiler. It wins on code size but typically loses on speed,
especially on modern machines where extra pipeline breaks really hurt.


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.


In practice, almost all branches are short and *any* reasonable algorithm
will work well enough. Things like iterative scanning of tables are
overkill; a simple FIFO buffer in the output stage, with branches made
long if if they are pushed out the end before their target is known,
will get almost all of them.
--
Henry Spencer at U of Toronto Zoology, henry@zoo.toronto.edu utzoo!henry
[It's true, the scheme that I used in the AIX assembler won't produce optimal
results, but since the code already was there and worked, I went with the
flow. On the other hand, perfect branch optimization is NP complete so
barring major positive news in the P=NP department, any perfect method is
very slow. A paper by Tom Szymanski in the CACM ten or so years ago tells
more than you'd ever want to know about the topic, I can dig up the reference
if there's interest. -John]
--


Post a followup to this message

Return to the comp.compilers page.
Search the comp.compilers archives again.