Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Path: utzoo!mnetor!uunet!seismo!gatech!amdcad!tim
From: tim@amdcad.AMD.COM (Tim Olson)
Newsgroups: comp.lang.c
Subject: Re: Types
Message-ID: <18042@amdcad.AMD.COM>
Date: Mon, 24-Aug-87 12:31:23 EDT
Article-I.D.: amdcad.18042
Posted: Mon Aug 24 12:31:23 1987
Date-Received: Tue, 25-Aug-87 03:17:23 EDT
References: <7264@brl-adm.ARPA> <734@sdchema.sdchem.UUCP>
Reply-To: tim@amdcad.UUCP (Tim Olson)
Organization: Advanced Micro Devices
Lines: 50

In article <193@hobbes.UUCP> root@hobbes.UUCP (John Plocher) writes:
+-----
|One thing that has bothered me for a long time about the 808x compilers
|is the following:
|    When I was learning PDP-11 assembler we found out that the compilers
|could use branch instructions iff the target was less than +/- 128 bytes
|away.  If not, a jump instruction would be used.  Branches were short and
|fast, jumps were big and slow.  Obvious.
|    Along came the 808x and I find that there were 2 modes for addresses:
|short and fast -vs- big and slow; these addresses could be used for code
|and data.  Obviously the compiler/linker/loader should be the one to determine
|which to use, right?  I mean, if a data object is within 64K of someplace
|then "near" pointers could be used; if it is too far, use "far" pointers.
|  Boy was I pissed when I found out that things didn't work that way!
|
|		    AAAArrrrrgggghhhh!
|
|All that needs to done is to have each library routine avaliable in each
|combo of models, and a smart linker which can use them.
+-----

That has to be a pretty smart linker, as far as linkers go.  It is an
N-P complete problem to "optimally" change "far" references to "near"
references (and compact the code) at link time.

Here's the problem:

During pass1, the linker builds the symbol table of externally defined
addresses.  During pass2, it discovers that a "far" reference is really
"near".  It then changes the code at that location to be a near
reference (which usually reduces the size of the code at that point). 
It then has to fill the unused space with "nops" (dubious benifit) or
"compact" the code.

After compacting, *all* labels following the compacted reference have
been changed by the size of the code reduction (even local, "static"
labels, which don't normally get passed to the linker!).  Worse yet, the
compaction may have brought a label into "near" range that was
determined to be far, before.  So pass2 must be run over again.

There is research going on in this area, because it would benifit a
great many architectures.  A good paper to read on the subject is one
written by David Wall of DEC -- sorry, I can't find the paper so I can't
give a complete reference -- those that are interested can email me; I
should be able to find the reference for you.


	-- Tim Olson
	Advanced Micro Devices
	(tim@amdcad.amd.com)