Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Path: utzoo!watmath!clyde!burl!ulysses!allegra!mit-eddie!godot!johnl
From: johnl@godot.UUCP
Newsgroups: net.lang
Subject: Re: Optimization technique wanted...
Message-ID: <438@ima.UUCP>
Date: Fri, 9-Nov-84 23:37:09 EST
Article-I.D.: ima.438
Posted: Fri Nov  9 23:37:09 1984
Date-Received: Sat, 10-Nov-84 10:22:42 EST
Lines: 22
Nf-ID: #R:sjuvax:-60100:ima:9800001:000:1296
Nf-From: ima!johnl    Nov  9 10:54:00 1984

Long vs. short branch optimization is an interesting problem.  It turns out
that generating perfectly optimal branches is NP-complete, i.e. there's no
known method that's better than enumerating the possibilities, although it's
possible that there is one that we haven't found one yet.  (If you find one,
please let me know.  You could even call collect.)

Fortunately, there are practical nearly-optimal schemes for real programs.
One was written up in CACM a few years ago.  In general, you start by assuming
that all of your branches might have to be long, although you pretend
that they're all short and assign tentative addresses that way.  Then you
interate over a table of all of the branch instructions that you have to make
a decision about, marking those that can definitely be short, even if all of
the undecided branches in their span turned out to be long.  When you find
that you can't mark any more, the unmarked ones are long and the marked ones
are short.

The Vax Unix assembler does this, and it usually turns out that 2 or 3 passes
over the table of branches do the trick.  This approach sometimes misses a
marginal case, but that's better than overoptimizing and generating bad
code.  I recommend the CACM article if you want to understand it better.

John Levine, ima!johnl