From mboxrd@z Thu Jan  1 00:00:00 1970
X-Spam-Checker-Version: SpamAssassin 3.4.4 (2020-01-24) on polar.synack.me
X-Spam-Level: 
X-Spam-Status: No, score=-0.8 required=5.0 tests=BAYES_00,INVALID_DATE
	autolearn=no autolearn_force=no version=3.4.4
Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!swrinde!zaphod.mps.ohio-state.edu!pacific.mps.ohio-state.edu!linac!att!bu.edu!inmet!ryer
From: ryer@inmet.inmet.com
Newsgroups: comp.lang.ada
Subject: Re: Reducing size of Ada's EXE files
Message-ID: <20600101@inmet>
Date: 19 Apr 91 13:28:00 GMT
References: <437@wrdis01.af.mil>
Nf-ID: #R:wrdis01.af.mil:437:inmet:20600101:000:2354
Nf-From: inmet.inmet.com!ryer    Apr 19 09:28:00 1991
List-Id: <comp.lang.ada>


1. Intermetrics compilers do dead code elimination.

2. Some Background, for those interested:

At link-time, almost any compiler does some sort of library searching to
resolve external references.  To do this requires that you start with the
object module(s) that were selected by the user, find the things they
reference, load them from the library, find the things they in turn reference, 
load them, and so on.  This is a transitive closure operation on the
reference graph.  Some people say "call graph", but it is important to
look at the data references too, so it is really the graph of ALL the
external references.

This processing is pretty essential, and it has the side effect of identifying
which "units" are and are not referenced directly or indirectly starting from
the main program.  Eliminating the unused units should be trivial.

However, the definition of "unit" is the rub.  To make this really effective,
each subprogram in a compilation unit must be a separately relocatable item
in the object module(s).  In package Math_Lib, the Sine, Cosine, and other
routines each need to be independently relocatable.  This means that if
Cosine invokes Sine, the call must be adjustable by the linker -- the compiler
must not just use a PC-relative branch based on an assumption that the
units in a compilation are located at known offsets from the start of the
compilation unit.   This does make a bit more work for the compiler, though
compared to everything else an Ada compiler has to do the impact is not
great.  It also vastly increases the number of external symbols and references
that the linker has to deal with.  Linker processing time is more than
linear with the number of symbols and references.  There is no excuse
for a linker going exponential, but some might be O(n**2) or worse
anyway.

3. Further Information on Intermetrics Compilers 

Our compilers generate separately relocatable portions of the
object module for each subprogram in a package, and for other things.
One example is the tables required at runtime to evaluate 'IMAGE and
'VALUE.  By making these separately relocatable, these tables are also
automatically excluded from the load module by the same transitive
closure mentioned above if there are no references to 'IMAGE or 'VALUE
for that particular type anywhere in the program.

Mike Ryer
Intermetrics