Re: global optimizing compilers vs. unix/make/rcs development methodology

merlin@neuro.usc.edu (merlin) writes:


>Unfortunately, this general procedure makes it impossible for any globally
>optimizing compiler to see any more than a small part of the program which
>it is supposed to be globally optimizing at any one time.


>Is anyone working on updating make or developing compilers which are able
>do global optimization of procedures spanning huge source code trees?


First, let's get the terminology straight. A compiler performing global
optimizations works on a single subroutine at a time (here, "global"
distinguishes the compiler from those doing only "local" (basic block and
expression-level) optimizations). A compiler that looks at the whole
program is said to be doing "interprocedural analysis". A compiler that
does things like inlining or procedure cloning or cross-procedural code
motion is doing "interprocedural optimization".


It's probably not the best terminology, but if you use it, you'll be
able to understand the literature.


Now, back to the point of your question... Some people at Rice (mostly
before my time) did a lot of work on efficient interprocedural analysis,
especially focussing on the problems caused by large (i.e., realistic)
sources. The general scheme goes like this:


Each routine is analysed separately (and quickly) and a summary
file is created. Whenever a routine is edited, the summary
file is updated. Obviously, make can control this process.
Summary file contains lists of referenced and defined global
variables and parameters plus copies of all the call sites
inside the procedure.


A whole-program analysis is performed, using only the summary
files. Builds a call graph and solves several interprocedural
data-flow analysis problems. Typically can find variables
used and killed across each call site, variables aliased at a
call, and interprocedural constants. Results written to a
results file for each procedure. Will need to redo the
whole-program analysis whenever a summary file changes.


Individual routines are compiled, using a fairly traditional
global optimizing compiler. Difference is that it has access
to the results file for the routine. Will need to recompile
when the source file _or_ the results file changes.




A general introduction to the work is


    title="The Impact of Interprocedural Analysis and Optimization in
                                  the Rn Programming Environment",
    author="Keith D. Cooper and Ken Kennedy and Linda Torczon",
    pages="491--523",
    journal=toplas,
    year=1986,
    month=oct,
    volume=8,
    number=4




A recent paper that focuses on recompilation in this environment is


    author="Michael Burke and Linda Torczon",
    title="Interprocedural Optimization: Eliminating Unnecessary Recompilation",
    pages="367--399",
    journal=toplas,
    year=1993,
    month=jul,
    volume=15,
    number=3


The bibliographies of these papers will guide you to the rest of the
literature. Convex and Tera have compilers that are fairly close to my
description (though the Tera work is not yet available). I don't know if
anyone else does (the area's still fairly researchy).


Preston Briggs
--

Return to the comp.compilers page.
Search the comp.compilers archives again.