Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Path: utzoo!mnetor!uunet!swlabs!jack
From: jack@swlabs.UUCP (Jack Bonn)
Newsgroups: comp.lang.c
Subject: Re: Types
Message-ID: <296@swlabs.UUCP>
Date: Fri, 28-Aug-87 16:04:54 EDT
Article-I.D.: swlabs.296
Posted: Fri Aug 28 16:04:54 1987
Date-Received: Sun, 30-Aug-87 02:53:44 EDT
References: <7264@brl-adm.ARPA> <734@sdchema.sdchem.UUCP> <293@osupyr.UUCP> <200@hobbes.UUCP>
Organization: Software Labs, Ltd. Easton CT USA
Lines: 36
Summary: multi-pass solution

In article <200@hobbes.UUCP>, root@hobbes.UUCP (John Plocher) writes:
> Why couldn't this be done in the compiler when everything is still in
> 3-address form IN THE COMPILER?  Don't wait to do this until after the code
> has been generated!  Start off assuming that everything is "far", and go
> thru marking things that can be proved "near".  At this point, labels are
> still symbolic, and since we have an arbitrary data structure for the
> 3-address code there is no need for compaction or filling with 'nops'.

Why not generate source assembler that doesn't indicate whether the target
is near or far.  Then let the assembler choose the long or short form of
the jump depending on the worst case distance from the target.

I think I remember an assembler that did just the job that you are looking
for.  If I remember correctly, it was a three pass assembler that worked
like this for branch addresses:

1) Pass over the source and compute the range of address that each symbol
   can have.  The instruction location counter would actually be a pair
   of values, ilc.min and ilc.max.  Whenever an instruction is read, 
   increment these values appropriately.  For jumps, this would mean adding
   different values to ilc.min and ilc.max.

2) Make what is normally a pass 1 over the input.  The exception here is
   that whenever a jump instruction is read, compute the WORST CASE distance
   to the target.  Mark that jump instruction for pass 2 and update the ilc
   appropriately.

3) Do what is normally pass 2.

Of course there are cases where this is too pessimistic, since the "real"
solution is exponential (np-complete?).  But in real cases, this yields
results very close to optimum.

-- 
Jack Bonn, <> Software Labs, Ltd, Box 451, Easton CT  06612
seismo!uunet!swlabs!jack