home · mobile · calendar · defenses · 1999-2000 · 

Thesis Defense - Stafford

A Formal, Language-Independent, and Compositional Approach to Interprocedural Control Dependence Analysis
Computer Science PhD Candidate

We present a new approach to identifying control dependencies in multi-procedure programs that is compositional, language-independent, and rigorously defined. Dependence relationships among the statements of a program are important to understand for various software development and maintenance purposes. The program's dependence graph is used as a base for various types of program analyses. A dependence graph represents the potential for one statement in a program to affect another in terms of the control and data dependencies among a program's statements.

We concentrate on the control aspect of program dependence analysis. Previous approaches to control dependence analysis either require that the entire program be available before dependencies can be computed or they ignore the potential for non-return from procedure calls. Our approach addresses the potential for non-return as well as providing the analyst with the option to compute control dependencies for procedures in isolation and then, at program composition time, compute interprocedural dependencies based on the previously computed intraprocedural dependencies and the program's call graph. Our model extends the definitions and structures associated with a previously defined model of uni-procedure program control dependencies for application to programs with more than one procedure. We define interprocedural forward dominance and a related program representation called the forward dominance forest. We describe its use to identify control dependencies in multi-procedure programs.

Committee: Alexander Wolf, Professor (Chair)
Clayton Lewis, Professor
Dirk Grunwald, Associate Professor
Benjamin Zorn, Associate Professor
Lori Clarke, University of Massachusetts Amherst
Debra Richardson, University of California, Irvine
Department of Computer Science
University of Colorado Boulder
Boulder, CO 80309-0430 USA
May 5, 2012 (14:20)