Computer Science

Graduate Research Forum Details

Specification and Solution of Multi-Source Data Flow Problems

Abstract

In multi-source data flow problems, a program may be modeled with a directed graph in which more than one type of edge is defined and information about the type of an edge considered along with the flow value it carries. Such problems occur in many advanced forms of data flow analysis, including interprocedural analysis, analysis of concurrent programs, bidirectional analysis, and a number of non-traditional forms. Although the classical lattice-theoretic approach is over 30 years old, there has been no extension of these unifying foundations that successfully encompasses multi-source problems. Traditionally, such analyses have been specified in a piecemeal fashion, typically with a set of complex parametric equations for which a solution algorithm and important theoretical properties must be worked out manually. Although foundational extensions have been fully realized for particular multi-source problem families, the solutions are specialized to their respective domains. An extension of the classical algebraic framework to the general multi-source case was presented by Masticola et al. in [MMR95], but the relation of their framework to the traditional equation-based specifications is highly ad hoc, and there is no attempt to provide a generic solution algorithm. In this talk, I will describe our efforts to address these lacunae. By viewing the specification of an analysis as itself a program in a very high-level language, we can exploit several key ideas from the literature on program transformation, database theory, and abstract interpretation of logic programs. In particular, we leverage this view in the development of a new approach to the generation of efficient solution algorithms for multi-source problems. The relation of such specifications to an underlying lattice framework completes the foundation.