Incremental Data Flow Analysis

Abstract

In this paper we present ACINCF and ACINCB, incremental update algorithms for forward and backward data flow problems, which are based on a linear equations model of Allen/Cocke interval analysis [Allen 77, Ryder 82a]. We have studied their performance on a robust structured programming language L. Given a set of localized program changes in a program in L, we can identify a priori the nodes in its flow graph whose corresponding data flow equations will be affected by the changes. We can characterize these affected nodes by their corresponding program structures and their relation to the original change sites.