FRAMEWORKS FOR PRECISE PROGRAM ANALYSIS

Brian Richard Murphy, Ph.D.
Stanford University, 2002
Advisor: Monica Lam

Program analysis has become more frequently used for applications such
as automatic parallelization, debugging, and program comprehension.
These new applications require new methods that provide greater
precision at lower computational cost than traditional techniques
developed for program analysis in compilers.  However, these new
methods incur new costs in complexity of understanding and use.  To
facilicitate their use we need sound frameworks which support the
construction of analyses based upon them, allowing reuse without
constant reinvention for each application.

In the exploration of three difficult program analysis problems, we
resolved a number of issues involved in their solution, and developed
three frameworks which can help in the future to ease the task of
constructing analyses to solve related problems.  Some of our
frameworks have already been generalized and applied to other analyses
beyond those for which they were originally designed.

Automatic parallelizers are an important tool for shared-memory
multiprocessors, as they enable sequential code to realize improved
performance without extra programmer effort.  The SUIF automatic
parallelizer proved highly effective on scientific applications.
Essential to its success was a new framework for interprocedural
analysis which facilitated construction of the many analyses involved
in parallelization.  The technique of region-based analysis with
selective cloning it incorporated allows precise interprocedural
analysis results at low cost.

Parallelizer results can be improved by a more systematic treatment of
predicates in the program.  A general framework for a predicated
data-flow analysis provides this treatment, by associating predicates
with data-flow values in any analysis.  A predicated data-flow
analysis can approximate a feasible path analysis, or derive guards
for conditionally parallel loops.  Several issues prove critical:
sound treatment of approximation, avoiding an explosion of predicates
with scoping and normalization mechanisms, and reducing analysis costs
through a sparse formulation.

The technique of analysis with partial transfer functions makes it
possible to build precise and efficient interprocedural analyses for
languages with recursion and higher-order functions, but it is
underutilized due to its complexity and inscrutability.  We develop
a foundational framework for exploiting this promising technique to
facilitate more efficient interprocedural analyses.  This development
should serve as a foundation for continuing work.