Path: utzoo!attcan!utgpu!jarvis.csri.toronto.edu!mailrus!csd4.milw.wisc.edu!uxc!deimos.cis.ksu.edu!rutgers!att!mcdchg!mcdphx!estinc!fnf
From: fnf@estinc.UUCP (Fred Fish)
Newsgroups: comp.sys.amiga.tech
Subject: Re: A68k and Manx AS
Message-ID: <87@estinc.UUCP>
Date: 14 May 89 05:23:36 GMT
References: <221@mindlink.UUCP> <262@xdos.UUCP> <8979@polya.Stanford.EDU>
Reply-To: fnf@estinc.UUCP (Fred Fish)
Organization: Enhanced Software Technologies, Inc.
Lines: 37

In article <8979@polya.Stanford.EDU> rokicki@polya.Stanford.EDU (Tomas G. Rokicki) writes:
>
>>>        - Bcc is converted to Bcc.S if possible (for backward
>>>            references only - forward references are too hard :-).
>
>>There were some assemblers on the PDP 11 (long ago, V6 Unix) that did
>>the forward references, too. Problematic due to an apparent necessity for
>>an indefinite number of passes or the equivalent, but when your text memory
>>space is only 64K I guess it may seem worth it.
>
>If you have memory available, it's not *that* difficult.  Simply maintain
>a list of `candidate' branches during the first pass.  A branch is a
>candidate if --> it's not already short and there isn't too much unmoveable
>code between it and it's target.  Now, simply run multiple passes over
>your branch list in *memory*, changing any appropriate ones to short, until
>it can no longer be done.  Now go back and update your symbol table.

Based on my experiences writing an experimental linker at Motorola for the
88K, which was capable of doing some object code optimizations at link time,
involving inserting or deleting instructions, I would recommend initially
assuming that ALL branches are short branches, and then changing the ones
that don't meet the criteria for short branches.  The main reason being
that if you are only expanding the code, once a branch target moves out
of range of a short branch, it will never move back in range, so you can
examine each branch independently of all the others.  If instead you are
trying to shrink the code by converting long branches to shorter branches,
there may be situations where examining each branch would appear to
result in no more conversions (terminating the loop), while simultaneously
shortening several branches would allow their targets to move into range.
In practice, two passes over the code is usually sufficient to find all
cases.  In rare cases, it would take three passes to find all cases.
I can't recall ever seeing more than three passes.

-Fred
-- 
# Fred Fish, 1835 E. Belmont Drive, Tempe, AZ 85284,  USA
# 1-602-491-0048           asuvax!{nud,mcdphx}!estinc!fnf