Douglas R. Grundman

EECS Department
University of California, Berkeley
Technical Report No. UCB/CSD-91-620
December 1990

http://www2.eecs.berkeley.edu/Pubs/TechRpts/1991/CSD-91-620.pdf

Many valuable flow analysis algorithms never make their way into the optimization phase of a compiler because they are difficult to build and maintain. A major problem is the lack of suitable high-level abstractions for implementing analyzers. This report provides such an abstraction based on the directed graph, describes a programming language based on this formalism, and shows that it makes the implementation and use of analysis algorithms easy.

The report introduces the idea of viewing a flow analyzer as a graph transformer, motivating the choice of graphs as an underlying data type. A family of powerful yet easily specified primitive graph transformations based on a pattern-match and replacement paradigm is presented, along with an algorithm for performing graph pattern-matching. Implementations of some of the most complex analysis algorithms known are presented, showing that a language based on graphs and graph transformations is sufficient for performing flow analysis. This approach successfully addresses many of the difficulties commonly encountered building and combining analyzers without affecting the asymptotic time bounds of any algorithm thus implemented.

The system, including a library of pre-programmed reusable analyzers has been incorporated into a pre-existing compiler optimizer, replacing a hand-coded analyzer. Within this experimental setting, it is demonstrated that the system greatly facilitates the implementation and use of analyzers, that different algorithms for solving the same problem can be interchanged easily without disturbing the surrounding compiler, and that multiple algorithms can coexist and interact without the need for any special interfaces.

Advisor: Susan L. Graham

BibTeX citation:

@phdthesis{Grundman:CSD-91-620,
    Author = {Grundman, Douglas R.},
    Title = {Graph Transformations and Program Flow Analysis},
    School = {EECS Department, University of California, Berkeley},
    Year = {1990},
    Month = {Dec},
    URL = {http://www2.eecs.berkeley.edu/Pubs/TechRpts/1990/6375.html},
    Number = {UCB/CSD-91-620},
    Abstract = {Many valuable flow analysis algorithms never make their way into the optimization phase of a compiler because they are difficult to build and maintain. A major problem is the lack of suitable high-level abstractions for implementing analyzers. This report provides such an abstraction based on the directed graph, describes a programming language based on this formalism, and shows that it makes the implementation and use of analysis algorithms easy.  <p>The report introduces the idea of viewing a flow analyzer as a graph transformer, motivating the choice of graphs as an underlying data type. A family of powerful yet easily specified primitive graph transformations based on a pattern-match and replacement paradigm is presented, along with an algorithm for performing graph pattern-matching. Implementations of some of the most complex analysis algorithms known are presented, showing that a language based on graphs and graph transformations is sufficient for performing flow analysis. This approach successfully addresses many of the difficulties commonly encountered building and combining analyzers without affecting the asymptotic time bounds of any algorithm thus implemented.  <p>The system, including a library of pre-programmed reusable analyzers has been incorporated into a pre-existing compiler optimizer, replacing a hand-coded analyzer. Within this experimental setting, it is demonstrated that the system greatly facilitates the implementation and use of analyzers, that different algorithms for solving the same problem can be interchanged easily without disturbing the surrounding compiler, and that multiple algorithms can coexist and interact without the need for any special interfaces.}
}

EndNote citation:

%0 Thesis
%A Grundman, Douglas R.
%T Graph Transformations and Program Flow Analysis
%I EECS Department, University of California, Berkeley
%D 1990
%@ UCB/CSD-91-620
%U http://www2.eecs.berkeley.edu/Pubs/TechRpts/1990/6375.html
%F Grundman:CSD-91-620