Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!swrinde!mips!zaphod.mps.ohio-state.edu!rpi!uupsi!cmcl2!lanl!cochiti.lanl.gov!jlg
From: jlg@cochiti.lanl.gov (Jim Giles)
Newsgroups: comp.lang.c
Subject: Re: low level optimization
Message-ID: <21703@lanl.gov>
Date: 17 Apr 91 22:15:14 GMT
References: <21527@lanl.gov> <15870@smoke.brl.mil> <21660@lanl.gov> <1991Apr17.190243.24691@watmath.waterloo.edu>
Sender: news@lanl.gov
Organization: Los Alamos National Laboratory
Lines: 43

In article <1991Apr17.190243.24691@watmath.waterloo.edu>, mhcoffin@tolstoy.waterloo.edu (Michael Coffin) writes:
|> [...]
|> Where in heaven's name did you get the idea that separate compilation
|> precludes interprocedural analysis?  [...]

Separate compilation and interprocedural analysis are (in the abstract)
mutually exclusive.  You can, of course, adopt some intermediate approach
in which _some_ interprocedural information is available at compile
time.  To the extent that you do this, you do _not_ have separate
compilation.  The only information available to the compiler about
procedures that are separately compiled are the names of routines
that the current procedure calls and the number and type of their
arguments and results (if any).  For a language which requires
separate compilation, _NO_OTHER_INFORMATION_ is known about an
external procedure.  The reason is that _all_ other characteristics
of an external procedure are allowed to _change_ without the need to
recompile any uses of that procedure.

The bottom line is that separate compilation implies that procedures
may be used together for which the _source_ of the separate routines
has never even existed in the same programming environment and only
the object code has been distributed.  Further, even the object code
of each may not be available at the time each of the other procedures
is compiled.  Hence, under separate compilation there may be no internal
information about other procedures used when a given procedure is compiled
because such information may not exist, may be speculative, or may 
subsequently change without notice.

To be sure, a great deal of research has been done on the consequences of
various compromises to separate compilation.  Some techniques require that
more information about externals be made available through interface specs
or header files.  Some techniques move some of the compilation process
into later tools (like the loader).  Indeed, by moving the code generation
and optimization phases of compilation into the loader, you can have the
benefits of full interprocedural analysis while technically remaining
compatible with language specifications which require separate compilation.
In fact, such a loader could 'inline' separately compiled procedures, do
constant folding, etc. across procedure boundaries and other amazing things.
Hypothetically, such an environment could optimize the infamous "hello
word" test code into a single system call. _I_ have not _seen_ production
quality compiler/loader combinations that do this.

J. Giles