home · mobile · calendar · bactac · 1999-2000 · 

BACTAC - Stafford

Avoiding the Pitfalls of Interprocedural Dependence Analysis
Grad Student, Department of Computer Science

Dependence-graph based program dependence analysis has been widely recognized as an efficient method for computing sets of statements in programs that can affect or be affected by a given statement. Knowledge of such dependencies is useful when performing a variety of software development and maintenance activities, as well as when performing a number of code optimizations. These activities are often relied upon for the construction of correct program executables, thus the correctness of underlying algorithms must be provable. However, much of the work in the dependence analysis community has been ad hoc; resulting in a gradual process of increasing the correctness of of the dependence graph through addition of new kinds of vertices and edges to capture missed control and data dependences. The resultant dependence representations are overly complicated and may as yet be unconservative. We extend the formal uni-procedure program dependence model developed by Podgurski for application to multi-procedure programs and describe its use in the construction of a less complicated interprocedural dependence graph that captures all control/data dependencies for multi-procedure programs where interprocedural communication can be in the form of procedure call/return, embedded halts, or non-local jumps. We do not address variable aliasing.

Department of Computer Science
University of Colorado Boulder
Boulder, CO 80309-0430 USA
May 5, 2012 (14:24)