Path: utzoo!utgpu!news-server.csri.toronto.edu!clyde.concordia.ca!mcgill-vision!snorkelwacker!tut.cis.ohio-state.edu!cs.utexas.edu!rice!titan.rice.edu!preston
From: preston@titan.rice.edu (Preston Briggs)
Newsgroups: comp.lang.misc
Subject: Re: Algol, and language design
Message-ID: <1990Aug2.224828.2867@rice.edu>
Date: 2 Aug 90 22:48:28 GMT
References: <23822@megaron.cs.arizona.edu>
Sender: news@rice.edu (News)
Organization: Rice University, Houston
Lines: 77

In article <23822@megaron.cs.arizona.edu> gudeman@cs.arizona.edu (David Gudeman) writes:
>In article  <1990Aug2.165229.28079@rice.edu> preston@titan.rice.edu (Preston Briggs) writes:
>]... many (most?) languages are
>]not very amenable to interprocedural optimization...
>]Currently, there are efficient methods for languages that have only
>]statically declared procedures (no procedure variables or parameters,
>]like people imagine when they wave their hands about interprocedural
>]optimization).  There are also versions that can handle procedure parameters
>](like Fortran).  Handling procedure-valued variables is very difficult
>]and isn't done well or efficiently.

>This is a little deceptive.  It is not a problem to do interprocedural
>optimization in a language that _allows_ procedure-valued variables,
>only for particular programs that _use_ such variables.  A C program
>that uses no procedure-valued variables can easily be detected (at
>link-time) and optimized as though such variables were not allowed.

Well, for research purposes, maybe.  Link-time optimization
means waiting 'til you have the entire program in one place
so you can optimize over the whole thing (think expensive).
Remember that every change means re-optimizing the entire
program (as you noted), including all the libraries you normally link in.

>Furthermore, a program that does use such variables doesn't have to
>suffer a huge performance hit unless the procedure variables are used
>all over the place and the procedures that are assigned to variables
>change a lot of global variables.  If the uses are fairly isolated, or
>the assigned procedures are well-behaved, then most of the program
>can be optimized as thought they weren't there.

In my sample languages (C, Oberon, Scheme), I tried to be fair and take 
into account normal usage.  C is perhaps a counter-example, and it's 
only included because it's relevant to most readers.

>The only real problem with procedure-valued variables (and
>interprocedural optimization in general) in C is that you have to do
>it at link time, over the whole program at once.  This problem could
>be reduced if C allowed more informative declarations.  Prototypes are
>a good start, but it would also be useful to allow extra declarations
>to specfy things like what globals are used and modified.

Even at link-time, procedure-valued variables are difficult.
If present, they can blow big holes in your call graph.

>Of course, these sorts of declarations can't be verified by the
>compiler because they depend on what procedures a given procedure
>calls.  So there is still some work for the linker to do.

Interprocedural analysis need not be done at link time.
At Rice, people have spent some years studying the problem and 
building systems that do interprocedural analysis.
Basically, we do things in 3 phases.  

1) Local analysis of each routine.

2) Global (interprocedural) analysis, using only the local
	summary information (that is, not looking at any program text).

3) Optimization of individual procedures.

(1) is only done when a file is changed.  We actually do it in our editor.
(2) is repeated whenever any local info has changed (almost always).
As part of (2), we notice which procedures need to be re-compiled
because their interprocedural info has changed (their text hasn't, but
they reference an interprocedural fact that has).

Interprocedural analysis typically finds facts like what variables
are referenced or changed across a call site, what parameters
are constant at a procedure entry, and what parameters might
be aliased (to each other or to a global).

I don't believe the interprocedural register allocation problem has been
solved satisfactorily.  None seem to acknowledge the recompilation
problem for large programs.
-- 
Preston Briggs				looking for the great leap forward
preston@titan.rice.edu