Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!rice!titan!preston
From: preston@titan.rice.edu (Preston Briggs)
Newsgroups: comp.lang.misc
Subject: interprocedural analysis
Message-ID: <6563@brazos.Rice.edu>
Date: 11 Apr 90 19:47:20 GMT
References: <6526@brazos.Rice.edu> <14326@lambda.UUCP>
Sender: root@rice.edu
Organization: Rice University, Houston
Lines: 75

In article <14326@lambda.UUCP> jlg@lambda.UUCP (Jim Giles) writes:

>But, I don't see
>how you can to interprocedural analysis where separate compilation is
>involved.  Separate compilation implies that the compiler is completely
>unaware of the content of procedures other than the one currently
>being compiled.

Well, the scheme proposed by Cooper, Kennedy, and Torczon bends your
definition of separate compilation a little and I expect
the new ideas won't make everyone happy.  The hope is that
the ends justify the means.  The local doctrine is something like this:

Interprocedural analysis is divided into 3 parts,

  1) a local summary analysis of each procedure

  2) a global pass, constructing the call graph
	and solving the various data flow problems over the call graph

  3) local compilation and optimization, using the results of 2

The division of labor is such that (1) is run once per change.
That is, when a procedure has been edited and we do a make,
then we need to examine the changed procedure but no others.

(2) is re-run if any procedure changes, but is able to run without
examining the code for the procedures.  Instead, it uses the local 
information produced by (1).

(3) needs to run on a procedure if it has been changed,
or if the interprocedural information used by an earlier (3) has
been invalidated.  (For example, an earlier analysis might have
determined there was no aliasing for a procedure zap.  If aliases
are introduced somewhere up the call chain, zap must be recompiled.
On the other hand, if the aliases are later removed, zap need not
be recompiled to remain correct.  The recompilation question is
interesting and complex and will be covered in a forthcoming
TOPLAS paper.)

The information supplied to (3) includes:
    at a procedure entrance, for each argument, 
	all arguments and globals that might be aliased

    at a call site, 
	a list of all the variables that might be modified, and
	a list of all variables that might be referenced.


Implementing all this is interesting.  A minimalist approach might
use 3 tools as described above, all controlled by make.

At Rice, we've built a programming environment incorporating these ideas.
The function of (1) is incorporated into the editor
which spies upon the user as he types, and records information
about variables referenced and modified and about procedure calls.
It also does scanning, parsing, and error checking.  (2) works about
as described.  (3) is invoked by (2) when necessary and most
resembles a normal optimizing compiler, though with a simplified
front-end (no scanning, parsing, or error reporting).

A big consequence is that the system needs access to all the source.
Object libraries might be difficult, though interprocedural summary
information could be provided and used effectively.
It isn't necessary that (3) be done with a special compiler;
in fact, we used f77 for years and still use it on occasion.

So, ...
Not totally convenient and not totally suitable for all uses,
but still a way to accomplish interprocedural analysis in a timely
fashion while allowing (some sort of) separate compilation.

--
Preston Briggs				looking for the great leap forward
preston@titan.rice.edu